复习题一及答案

第 1 页 共 9 页

复习题一

1. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( A )。

A. O(n) B. O(n/2)

C. O(1) D. O(n2)

2. 在有向图中每个顶点的度等于该顶点的( C )。

A. 入度 B. 出度

C. 入度与出度之和 D. 入度与出度之差

3. 下列排序算法中( C )是不稳定的排序算法。

A. 冒泡排序 B. 合并排序

C. 快速排序 . D. 插入排序

4. 在单链表中，q指向待删除结点的前驱，p指向待删除的结点，则删除节点的操作是( B )。

A. p=q->next；q->next=p->next; free (p);

B. q->next=p; q->next=p->next; free (p);.

C. p=q->next; free (p); q->next=p->next;

D. p=q->next; p=p->next; free (p);

5. 栈操作的基本原则( B ).

A. 先进先出 B. 先进后出 第 2 页 共 9 页 C. 只能进行插入 D. 只能进行删除

6. 设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次入栈，若有6个元素出栈的顺序是S2，S3，S4，S6，S5，S1。则该栈的容量至少应该是（ B ）。

A．2 B．3 C．4 D．5

9. 具有50个结点的完全二叉树，编号为19的结点的左孩子编号为( C )

A. 46 B. 39

C. 38 D. 不存在

10. 若一棵二叉树具有10个度为2的节点，5个度为1的节点，则度为零的节点个数是( B ).

A. 9 B. 11

C. 15 D. 不确定

11. 有n个顶点的无向图最多有( B )条边。

A. n-1 B. n*(n-1)/2

C. n*(n+1)/2 D. n*n

12. 对下图G，若从顶点a出发，按深度搜索法，进行遍历，则可能得到的一种顶点序列为( D )，按广度搜索法进行遍历，则可能得到的一种顶点序列为( B )。 第 3 页 共 9 页

A. a b e c f d B. a b c e f d

C. a e b c f d D. a e d f c b

13. 在一个无向图中，所有顶点度数之和等于所有边数( B )倍，在一个有向图中，所有顶点入度数之和等于所有顶点出度之和的( C )倍。

A. 1/2 B. 2

C. 1 D. 4

二、填空题：（每空1分，共10分）

1. 选择合适的存储结构，通常考虑的指标是空间复杂度和_时间复杂度__。

2. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度__O（n）_为，在表尾插入元素的时间复杂度为____O(1)___。

3. 在一棵二叉树中，第5层上的结点数最多为___16_。

4. 设有一空栈S及等待进栈的数据元素序列数据：2，3，4，5，6，7，8，9。依次进行push, push, pop, push, pop, push, push, pop, push, push,

pop 操作，完成此操作后，栈S的栈顶元素为____7____，栈底元素为____2___。

5. 在一棵树中，__叶子__结点没有后继结点，__根__节点没有前驱节点。 第 4 页 共 9 页 6. 假定一棵二叉树的结点个数为10，则它的高度至多为___10___，它的高度至少为____4____。

三、判断题：（每小题1分，共10分）

1. (X )线性表的特点是每个元素都有一个前驱和一个后继。

2. (V )直接选择排序是一种不稳定的排序方法 。

3. (X )二分查找只适用于有序表，包括有序的顺序表和有序的链表。

4. (X )链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。

5. (X )通常递归的算法简单、易懂、容易编写，而且执行的效率也高。

6. (X )对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。

7. (X )二叉树的度数为2。

8. (X )在n个顶点的无向图中，若边数大于n-1，则该图必是连通图。

9. (X )有e条边的无向图，在邻接表中有e个节点。

10. (X )单链表中从任何一个节点出发，都能访问到所有节点。

四、解答题：（每小题6分，共30分）

1. 对于给定的一组记录的关键字：｛23,13,17,21,30,60,58,28,30,90｝，试分别写出用简单选择排序的方法对其进行排序时，每一趟排序后的结果。

第 5 页 共 9 页 答： （13）[23 17 21 30 60 58 28 30 90]

（13 17）[23 21 30 60 58 28 30 90]

（13 17 21）[23 30 60 58 28 30 90]

（13 17 21 23）[30 60 58 28 30 90]

（13 17 21 23 28）[60 58 30 30 90]

（13 17 21 23 28 30）[58 60 30 90]

（13 17 21 23 28 30 30）[60 58 90]

（13 17 21 23 28 30 30 58）[60 90]

（13 17 21 23 28 30 30 58 60）[90]

13 17 21 23 28 30 30 58 60 90

2. 写出下面树的前序、中序、后序遍历序列；

前序：ABDGHECFIJ

中序：GDHBEACIJF

后序：GHDEBJIFCA 第 6 页 共 9 页

3. 设散列表的长度m=13；散列函数为H(X)=X mod m,给定的关键码序列为19,14,23,01,68,20,84,27,55,11,试分别画出用线性探查法解决冲突时所构造的散列表（闭散列）和开散列方法实现。并求出在等概率的情况下，这两种方法的搜索成功时的平均搜索长度;

4. 写出下图的的邻接矩阵表示及邻接表表示；

第 7 页 共 9 页

5. 如下图所示:

(1) 写出它的邻接表；

(2) 应用Prim算法(从A出发)，画出最小生成树，写出最小生成树的生成过程。

6、对给定的一组权值：3，3，7，7，11，13，17构造一棵Huffman树，并计算出树的带权路径长度。

第 8 页 共 9 页

五、 算法设计题：（每小题10分，共20分）

1. 设含有头结点的单链表L的结点结构定义为：

typedef struct node *link ;

typedef struct node{ ListItem element ;

link next;}Node;

假设head为指向表头结点的指针。

试写出算法：求单链表中值为最大的结点。

2. 用邻接矩阵实现赋权有向图，结构定义如下：P

Typedef struct graph *Graph;

Struct graph{ 第 9 页 共 9 页 Witem noEdge; /*无边标记*/

int n; /*顶点数*/

int e; /*边数*/

Witem **a; /*邻接矩阵*/

} AWDgraph;

试在邻接矩阵存储结构上实现图的入度的基本操作：InDegree(i,G)，即函数InDegree(i,G)返回赋权有向图G中顶点I的入度。