DS期末复习卷（八）

一、选择题(30分)

1.字符串的长度是指（ C ）。
(A) 串中不同字符的个数 (B) 串中不同字母的个数
(C ) 串中所含字符的个数 (D) 串中不同数字的个数

2.建立一个长度为n的有序单链表的时间复杂度为（ C ）
(A) O(n) (B) O(1) © O(n^2) (D) O(log2n)

建立有序单链表的时间复杂度为O（n^2）

3.两个字符串相等的充要条件是（ C ）。
(A) 两个字符串的长度相等 (B) 两个字符串中对应位置上的字符相等
( C) 同时具备(A)和(B)两个条件 (D) 以上答案都不对

4.设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ B）。
(A) 99 (B) 97 ( C) 91 (D) 93

选一个素数作为模，能够减少发生冲突

5.在二叉排序树中插入一个关键字值的平均时间复杂度为（B ）。
(A) O(n) (B) O(log2n) ( C) O(nlog2n) (D) O(n%2)

6.设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( C )。
(A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4]
( C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]

1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6
456
4

7.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ B ）。
(A) 8 (B) 7 ( C) 6 (D) 5

假设二叉树的深度为k，则该二叉树最多有2^k - 1个节点，若k为6，则最多有2^6 - 1 = 63个节点，小于65。故该二叉树的深度为7，选B。

8.设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（ C ）个度数为0的结点。
(A) 5 (B) 6 (C ) 7 (D) 8

no=1+n2+2n3+=1+2+4=7

9.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（A ）。
(A) aedfcb (B) acfebd ( C) aebcfd (D) aedfbc

abedfc
aedfcb
acedfb

10.队列是一种（ A ）的线性表。
(A) 先进先出 (B) 先进后出 © 只能插入 (D) 只能删除

二、判断题

1、如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（ ）

对

2、设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（ ）

错
快速排序在基本有序的时候算法时间复杂度是最坏的，此时为o(n^2)。相反在越无序的时候时间复杂度越低，为O(nlogn)。

3、分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。
（ ）

对

4、二维数组和多维数组均不是特殊的线性结构。（ ）

错。
数组都是线性结构

5、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ ）

错
最坏情况下和树的高度一样，不可能比树的高度要大，在二叉搜索树中查找和二分查找相似。

6、如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（ ）

对
有向图的邻接表
一行单链表表示该行头结点的出度

7、非空的双向循环链表中任何结点的前驱指针均不为空。（ ）

对
循环链表是最后一个节点的指针域指向头节点，而不是指向第一个节点，所以双向循环链表是一整个完整的循环。

8、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（ ）

对

9、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（ ）

对

10、稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（ ）

对

三、填空题

1、设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为
_____________________________。

(49，13，27，50，76，38，65，97)
d=4
[49,76]为一个子序列
[38,13]一个子序列
[65,27]一个子序列
[97,50]一个子序列
各自排序后放回他们在总序列中对应的位置（就是原本的位置交换一下变成升序）。

2、下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。

t=(bitree *)malloc(sizeof(bitree))
bstinsert(t->rchild,k)

3、设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：
s->next=p->next; _________________;

p->next=s;

4、设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系
是p=和head=_（设结点中的两个指针域分别为llink和rlink）。

head->rlink
p->llink;

5、设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__________。

CABD

6、完全二叉树中第5层上最少有__________个结点，最多有_________个结点。

1
16（2^(h-1)）

7、设有向图中不存在有向边<Vi,Vj>，则其对应的邻接矩阵A中的数组元素A[i][j]的值等于____________。

0

8、设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为__________。

(13,27,38,49,97,76,65,50)
13,38,65,97,76,49,27,50
13,27,65,97,76,49,38,50
13,27,38,65,97,76,49,50
13,27,38,49,97,76,65,50

9、设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。

n-1
生成最小生成树需要包含图中各点，因此连接的边数为n- 1。

10、设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与___________相互交换
即可。

50

小根堆

四、算法设计题(20分)

1.设计一个在链式存储结构上统计二叉树中结点个数的算法。

void countnode(bitree* bt, int& count)
{if (bt != 0){count++; countnode(bt->lchild, count);countnode(bt->rchild, count);}
}

2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

typedef struct { int vertex[m]; int edge[m][m]; }gadjmatrix;
typedef struct node1 { int info; int adjvertex; struct node1* nextarc; }glinklistnode;
typedef struct node2 { int vertexinfo; glinklistnode* firstarc; }glinkheadnode;
void adjmatrixtoadjlist(gadjmatrix g1[], glinkheadnode g2[])
{int i, j; glinklistnode* p;for (i = 0; i <= n - 1; i++) g2[i].firstarc = 0;for (i = 0; i <= n - 1; i++) for (j = 0; j <= n - 1; j++)if (g1.edge[i][j] == 1){p = (glinklistnode*)malloc(sizeof(glinklistnode)); p->adjvertex = j;p->nextarc = g[i].firstarc; g[i].firstarc = p;p = (glinklistnode*)malloc(sizeof(glinklistnode)); p->adjvertex = i;p->nextarc = g[j].firstarc; g[j].firstarc = p;}
}