1．调用一次深度优先遍历可以访问到图中的所有顶点。（ ）
2．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（ ） 3．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ） 4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ ）
5．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ ） 6．层次遍历初始堆可以得到一个有序的序列。（ ）
7．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ ） 8．线性表的顺序存储结构比链式存储结构更好。（ ） 9．中序遍历二叉排序树可以得到一个有序的序列。（ ） 10.快速排序是排序算法中平均性能最好的一种排序。（ ）
三、填空题(30分)
1．for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_________。
2．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为next）。 3．设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。
4．设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_________。
5．设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点数。 6．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________________。
7．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_____________________________________________。
8．简单选择排序和直接插入排序算法的平均时间复杂度为___________。
9．快速排序算法的空间复杂度平均情况下为__________，最坏的情况下为__________。 10.散列表中解决冲突的两种方法是_____________和_____________。
四、算法设计题(20分)
１．设计在顺序有序表中实现二分查找的算法。 ２．设计判断二叉树是否为二叉排序树的算法。 ３．在链式存储结构上设计直接插入排序算法 一、选择题
1．D 2．A 3．A 4．A 5．D 6．D 7．B 8．A 9．C 10．B 11．C 12．A 13．B 14．D 15．B
二、判断题
1．错 2．对 3．对 4．对 5．错 6．错 7．对 8．错 9．对 10．对
三、填空题 1. O(n)
2. s->next=p->next; p->next=s 3. (1，3，2，4，5)
4. n-1 5. 129 6. F==R
7. p->lchild==0&&p->rchild==0 8. O(n2)
9. O(nlog2n)， O(n)
10. 开放定址法，链地址法
四、算法设计题
1. 设计在顺序有序表中实现二分查找的算法。
struct record {int key; int others;}; int bisearch(struct record r[ ], int k) {
int low=0,mid,high=n-1; while(low<=high) {
mid=(low+high)/2;
if(r[mid].key==k) return(mid+1); else if(r[mid].key>k) high=mid-1; else low=mid+1; }
return(0); }
2. 设计判断二叉树是否为二叉排序树的算法。 int minnum=-32768,flag=1;
typedef struct node{int key; struct node *lchild,*rchild;}bitree; void inorder(bitree *bt) {
if (bt!=0) {inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild);} }
3. 在链式存储结构上设计直接插入排序算法
void straightinsertsort(lklist *&head) {
lklist *s,*p,*q; int t;
if (head==0 || head->next==0) return;
else for(q=head,p=head->next;p!=0;p=q->next) {
for(s=head;s!=q->next;s=s->next) if (s->data>p->data) break; if(s==q->next)q=p;
else{q->next=p->next; p->next=s->next; s->next=p; t=p->data;p->data=s->data;s->data=t;} } }
数据结构试卷（七）
一、选择题(30分)
1．设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。 (A) 2n (B) n (C) n/2 (D) n(n-1) 2．设无向图G中有n个顶点，则该无向图的最小生成树上有（ ）条边。 (A) n (B) n-1 (C) 2n (D) 2n-1
3．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（ ）。
(A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80 (C) 42，40，55，60，80，85 (D) 42，40，60，85，55，80 4．（ ）二叉排序树可以得到一个从小到大的有序序列。 (A) 先序遍历 (B) 中序遍历 (C) 后序遍历 (D) 层次遍历
5．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1
6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ ）。
23
(A) O(n) (B) O(nlog2n) (C) O(n) (D) O(n/2)
7．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0
8．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。 (A) 20 (B) 256 (C) 512 (D) 1024
9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。 (A) 1 (B) 2 (C) 3 (D) 4
10.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next;
二、判断题(20分)
1．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（ ） 2．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）
3．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（ ） 4．完全二叉树中的叶子结点只可能在最后两层中出现。（ ） 5．哈夫曼树中没有度数为1的结点。（ ）
6．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（ ） 7．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（ ） 8．由树转化成二叉树，该二叉树的右子树不一定为空。（ ） 9．线性表中的所有元素都有一个前驱元素和后继元素。（ ） 10.带权无向图的最小生成树是唯一的。（ ）
三、填空题(30分)
1. 设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结
点X的操作序列为_________=p；s->right=p->right；__________=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。 2. 设完全有向图中有n个顶点，则该完全有向图中共有________条有向条；设完全无向图中有n个顶点，
则该完全无向图中共有________条无向边。
3. 设关键字序列为(Kl，K2，?，Kn)，则用筛选法建初始堆必须从第______个元素开始进行筛选。 4. 解决散列表冲突的两种方法是________________和__________________。
5. 设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有
______个。
6. 高度为h的完全二叉树中最少有________个结点，最多有________个结点。
7. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是
__________________________________。
8. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果的是
__________________________________。
9. 设一棵二叉树的前序序列为ABC，则有______________种不同的二叉树可以得到这种序列。 10. 下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。
struct record {int key;datatype others;};
void quickpass(struct record r[], int s, int t, int &i) {
int j=t; struct record x=r[s]; i=s; while(i while (i _________________; } 四、算法设计题(20分) 1. 设计在链式结构上实现简单选择排序算法。 2. 设计在顺序存储结构上实现求子串算法。 3. 设计求结点在二叉排序树中层次的算法。 一、选择题 1．B 2．B 3．C 4．B 5．B 6．A 7．C 8．C 9．B 10．D 二、判断题 1．对 2．对 3．对 4．对 5．对 6．对 7．对 8．错 9．错 10．错 三、填空题 1. s->left=p，p->right 2. n(n-1)，n(n-1)/2 3. n/2