2014上数据结构期末图习题答案

2014 上 数据结构期末复习大纲

一. 期中前以期中考试试卷复习，算法要真正理解

二、二叉树、图、排序算法将是考试重点（占60%左右） 三、要掌握的算法 1. 二叉树的链表表示

2.建立二叉树的链表存储结构

3. 先序、中序、后序遍历二叉树（递归算法） 4. 遍历算法的应用（ 如求二叉树的结点数） 5.建立huffman树和huffman编码 6. 图的邻接矩阵表示和邻接链表表示 7.图的深度优先遍历和广度优先遍历算法 8. 有向图求最短路径（迪杰斯特拉算法）9. 直接插入排序算法 10. shell 排序(排序过程) 12. 堆排序 （排序过程）

1

练习题

1. 有8个结点的无向图最多有 B 条边。

A．14 B. 28 C. 56 D. 112 2. 有8个结点的无向连通图最少有 C 条边。

A．5 B. 6 C. 7 D. 8 3. 有8个结点的有向完全图最多有 C 条边。

A．14 B. 28 C. 56 D. 112 4. 用邻接表表示图进行广度优先遍历时，通常是采用 B 来实现算法的。 A．栈 B. 队列 C. 树 D. 图

5. 用邻接表表示图进行深度优先遍历时，通常是采用 A 来实现算法的。 A．栈 B. 队列 C. 树 D. 图

6. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是*

?0?1??1??1?1??0??1111101?001001??000100??100110?011010??001101?100010??A．0 2 4 3 1 5 6

B. 0 1 3 6 5 4 2 C. 0 4 2 3 1 6 5 D. 0 3 6 1 5 4 2

建议：0 1 3 4 2 5 6

（ C ）

7.已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按深度优先遍历的结点序列是( D )

A． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 6 8. 已知图的邻接矩阵同上题6，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（B ）

A． 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 6

9. 已知图的邻接矩阵同上题6，根据算法，则从顶点0出发，按广度优先遍历的结点序列是( C )

A． 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6

10.从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ C ）。

A．归并排序 B．冒泡排序 C．插入排序 D．选择排序

11. 从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ D ）。

A．归并排序 B．冒泡排序 C．插入排序 D．选择排序

12. 对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ D ）。 A．n+1 B．n C．n-1 D．n(n-1)/2

13.若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。

A．38，40，46，56，79，84 B．40，38，46，79，56，84 C．40，38，46，56，79，84 D．40，38，46，84，56，79

2

14. 堆是一种（ B ）排序。

A．插入 B．选择 C．交换 D．归并

15. 若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ B ）。

A．79，46，56，38，40，84 B．84，79，56，38，40，46 C．84，79，56，46，40，38 D．84，56，79，40，46，38 二、填空题（每空1分，共20分）

1. 图有 邻接矩阵 、 邻接表 等存储结构，遍历图有 深度优先遍历 、 广度优先遍历 等方法。

2. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。

2

3. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n) 。 4. n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 O(n+e) 。 5. 设有一稀疏图G，则G采用 邻接表 存储较省空间。 6.. 设有一稠密图G，则G采用 邻接矩阵 存储较省空间。 7. 图的逆邻接表存储结构只适用于 有向 图。 8. 图的深度优先遍历序列 不是 惟一的。

2

9.n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 O(n) ；若

采用邻接表存储时，该算法的时间复杂度为 O(n+e) 。

10. n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 2

O(n) ；若采用邻接表存储，该算法的时间复杂度为 O(n+e) 11. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按 路径长度 递增 的次序来得到最短路径的。

三 、简答题.

1. 已知如图所示的有向图，请给出该图的:

（1） 每个顶点的入/出度； （2） 邻接矩阵； （3） 邻接表； (4)逆邻接表。

3

2. 已知一个无向图的邻接表如图2所示，要求： （1）画出该无向图；

（2）根据邻接表，分别写出用DFS(深度优先搜索)和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。 V0 2 1 ∧ 6 5

V1 2 ∧ 3 0 4

V2 6 1 ∧ 3 0

2 4 ∧ 1 V3

V4 1 3 ∧

0 V5 6 ∧

5 V 6 2 0 ∧

图2 图的邻接表存储

答（1） v2

v3 v6

v1 v0

v5 v4

（2）根据该无向图的邻接表表示，从顶点V0开始的深度优先遍历序列为：V0、V2、V3、V1、V4、V6、V5。广度优先遍历序列为V0、V2、V5、V6、V1、V3、V4。

4

3.、图3所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0

到其余各顶点的最短路径, 写出执行算法过程中各步的状态。

V5 100 60 30 V0 V4 0 ∞ 10 ∞ 30 100

∞ 0 5 ∞ ∞ ∞ 10 20 10 ∞ ∞ 0 50 ∞ ∞ V1 ∞ ∞ ∞ 0 ∞ 10

∞ ∞ ∞ 20 0 60 5 V3 50 ∞ ∞ ∞ ∞ ∞ 0 V2 (b) 带权邻接矩阵 (a) 有向带权图

3、求解过程如下表所示。 终点 从v0到各终点的D值和最短路径的求解过程 i=1 V1 V2 ∞ 10 (v0,v2) V3 V4 ∞ 30 60 (v0,v2,v3) 30 100 (v0,v5) V4 (v0,v4) (v0,v4) V5 Vj S 100 (v0,v5) V2 90 (v0,v4,v5) V3 {v0,v2,v3,v4} 60 (v0,v4,v3,v5) V5 {v0,v2,v3,v4,v5} 50 (v0,v4,v3) i=2 ∞ i=3 ∞ i=4 ∞ i=5 ∞ 无 {v0,v2} {v0,v2,v4}

4. 设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。 （1）.直接插入排序

（2）希尔排序（增量选取5，3，1） （3）快速排序 （1）直接插入排序

[2 12] 16 30 28 10 16* 20 6 18 [2 12 16] 30 28 10 16* 20 6 18 [2 12 16 30] 28 10 16* 20 6 18 [2 12 16 28 30] 10 16* 20 6 18 [2 10 12 16 28 30] 16* 20 6 18 [2 10 12 16 16* 28 30] 20 6 18 [2 10 12 16 16* 20 28 30] 6 18 [2 6 10 12 16 16* 20 28 30] 18 [2 6 10 12 16 16* 18 20 28 30]

5

（2） 希尔排序（增量选取5，3，1）

10 2 16 6 18 12 16* 20 30 28 （增量选取5） 6 2 12 10 18 16 16* 20 30 28 （增量选取3） 2 6 10 12 16 16* 18 20 28 30 （增量选取1） （3）快速排序 枢轴

12 [6 2 10] 12 [28 30 16* 20 16 18] 6 [2] 6 [10] 12 [28 30 16* 20 16 18 ] 28 2 6 10 12 [18 16 16* 20 ] 28 [30 ] 18 2 6 10 12 [16* 16] 18 [20] 28 30 16* 2 6 10 12 16* [16] 18 20 28 30

5. 设待排序的关键字序列为{30，60,8,40,70,12,10}，试使用堆排序， （1）画出将无序数据建成初始堆的图， （2）画出将第二个数排定顺序时的堆的图。 答（1）初始堆序列 为 70 60 12 40 30 8 10

70126040 （2）

30810

601281240104010

308 交换60和8

3060 四、程序填空题

1、 根据有向图的邻接矩阵求出序号为numb的顶点的度数(邻接矩阵可参考简答题第三题),

请填写算法中下划线的空白处。 int degree2(Graph & ga, int numb)

{ int i,j,d=0;

for(j=0; j

if(ga.arcs[ numb ][j]!=0 && ga.arcs[ numb ][j]!=MAXINT) d++ ;

for(i=0; i

if(ga.arcs[ I ][ numb ]!=0 && ga.arcs [ I ][ numb ]!=MAXINT) d++; return (d); }

2.. 已知r[1..n]是n个记录的递增有序表，用折半查找法查找关键字（key）为k的记录。如果查找失败，，则输出“ 失败”，函数返回值为0；否则输出“成功”，函数返回值为该

6

记录的序号值。

Int binary_search(struct recordtype r[ ],int n ,keytype k) /* r[1..n] 为N 个记录的递增有序表，k 为关键字 */ { int mid,low=1,hig=n; while( low<=hig) { mid=(low+hig)/2;

if(k

else if(k==r[mid].key){ printf(“ 成功”)；(2) return mid ;} else (3) low=mid+1 ; } if(low>high) printf(“失败”); return(0);

}

3. 建立huffman 树

void HuffmanCoding(HuffmanTree &HT, int *w,int n) // 算法6.12

{ // w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n<=1) return; m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用 for(p=HT+1,i=1;i<=n;++i,++p,++w) {

(*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; }

for(;i<=m;++i,++p) (*p).parent=0;

for(i=n+1;i<=m;++i) // 建赫夫曼树

{ // 在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 select(HT,i-1,s1,s2);

ht[s1].parent==I; ht[s2].parent==I; ht[i].lchild=s1; ht[i].lchild=s2; ht[i].weight=ht[s1].weight+ht[s2].weight;

7

} }

六．编程题

1.期中考试 二个程序题（循环队列入队出队、用栈处理进制转换（P48 算法3.1） 2. 以二叉链表作为二叉树的存储结构，编写以下算法： (看实习题)

（1）写出先序、中序、后序遍历二叉树的递归算法； （1）统计二叉树的结点个数。

3. 带头结点的单链表的插入和删除算法。（书上P30 算法2.9，2.10） 答.1. 期中循环队列入队出队

#define MAX 20 typedef struct {

int qu[MAX];

int rear，length; }Queue;

Int EnQueue( Queue &q, int e) { if( q.length==MAX) return -1; q.rear=(q.rear+1)%max; q.length=q.length+1; q.qu[q.rear]=e; return 1; }

Int DeQueue( Queue &q, int &e) { int front;

if( q.length==0) return -1;

front=(q.rear+1+MAX-q.length)%max; e=q.qu[front]; q.length--; return 1; }

8

本文来源：https://www.bwwdw.com/article/69y.html