数据结构期末 复习题

.1.1 单项选择题

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。

① A．操作对象 Ｂ．计算方法 Ｃ．逻辑存储 Ｄ．数据映象 ② A．结构 Ｂ．关系 Ｃ．运算 Ｄ．算法 2. 数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②有限集合。

① A．算法 Ｂ．数据元素 Ｃ．数据操作 Ｄ．逻辑结构 ② A．操作 Ｂ．映象 Ｃ．存储 Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成①。

A．动态结构和静态结构 Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构 Ｄ．内部结构和外部结构 4. 线性表的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取②的存储结构。

A．随机存取 B．顺序存取 C．索引存取 D．散列存取 5. 算法分析的目的是①，算法分析的两个主要方面是②。

① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系

C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性

C. 可读性和文档性 D. 数据复杂性和程序复杂性 6. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法

C. 解决问题的有限运算序列 D. 调度方法

② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 7. 线性表的逻辑顺序与存储顺序总是一致的，这种说法①。 A. 正确 B. 不正确

8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址①。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 9. 在以下的叙述中，正确的是①。

A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式和先进后出

10. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法①。

1

A. 正确 B. 不正确

1.2 填空题（将正确的答案填在相应的空中

1. 数据逻辑结构包括线性结构、树形结构和图形结构三种类型，树形结构和图形结构合称为非线性结构。

2. 在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。

3. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点，叶子结点没有后续结点，其余每个结点的后续结点可以任意多个。

4. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

6. 算法的五个重要特性是__有穷性、确定性、可行性、输入、输出 7. 下面程序段的时间复杂度是O（m*n）

for (i=0;ii=s=0;

while (s9. 下面程序段的时间复杂度是O (n2) s=0;

for (i=0;i10. 下面程序段的时间复杂度是log3n

i=1;

while (i<=n) i=i*3; 1.3 算法设计题:

1. 试写一算法,自大到小依次输出顺序读入的三个数X,Y和Z的值. void print_descending(int x,int y,int z)//

12按从大到小顺序输出三个数 {

scanf(\"%d,%d,%d\

2

if(xy; //<->为表示交换的双目运算符,以下同 if(yz;

if(xy; //冒泡排序 printf(\"%d %d %d\}//print_descending

习 题 二 顺序表示(线性表、栈和队列)

2.1 单项选择题

1. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是____。

A. 110 B. 108 C. 100 D. 120

2. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。 A. edcba B. decba C. dceab D. abcde

3. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____。

A. i B. n=i C. n-i+1 D. 不确定 4. 栈结构通常采用的两种存储结构是____。

A. 顺序存储结构和链式存储结构 B. 散列方式和索引方式 C. 链表存储结构和数组

D. 线性存储结构和非线性存储结构

5. 判定一个栈ST（最多元素为m0）为空的条件是____。 A. ST—> top !=0 B. ST—> top= =0 C. ST—> top !=m0 D. ST—> top= =m0

6. 判定一个栈ST（最多元素为m0）为栈满的条件是____。 A. ST—> top！=0 B. ST—> top= =0 C. ST—> top！=m0 D. ST—> top= =m0

7. 栈的特点是__先进后出__，队列的特点是__先进先出__。

8. 一个队列的入列序列是1，2，3，4，则队列的输出序列是____ 。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，1

9. 判定一个队列QU（最多元素为m0）为空的条件是____。

A. QU—>rear—QU—>front= =m0 B. QU—>rear—QU—>front-1= =m0 C. QU—>front= =QU—>rear D. QU—>front= =QU—>rear+1

10. 判定一个队列QU（最多元素为m0, m0+1= =Maxsize）为满队列的条件是____。

3

A. ((QU—>rear-QU—>front)+ Maxsize)% Maxsize = =m0 B. QU—>rear—QU—>front-1= =m0 C. QU—>front= =QU—>rear D. QU—>front= =QU—>rear+1

11. 判定一个循环队列QU（最多元素为m0）为空的条件是____。 A. QU—>front= =QU—>rear B. QU—>front！=QU—>rear

C. QU—>front= =（QU—>rear+1）%m0 D. QU—>front！=（QU—>rear+1）%m0

12. 判定一个循环队列QU（最多元素为m0）为满队列的条件是____。 A. QU—>front= =QU—>rear B. QU—>front！=QU—>rear

C. QU—>front= =（QU—>rear+1）%m0 D. QU—>front！=（QU—>rear+1）%m0

13. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。

A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 14. 栈和队列的共同点是____。

A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 2.2 填空题（将正确的答案填在相应的空中）

1. 向量、栈和队列都是_线性___结构，可以在向量的_任何___位置插入和删除元

素；对于栈只能在_栈顶___插入和删除元素；对于队列只能在__队尾__插入元素和__队首__删除元素。

2. 向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需

向后移动__ n-i+1__个元素。

3. 向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动n-i个元

素。

4. 向栈中压入元素的操作是_先移动栈顶指针，后存入元素 ___。 5. 对栈进行退栈时的操作是_先取出元素，后移动栈顶指针___。 6. 在一个循环队列中，队首指针指向队首元素的_前一个位置___。 7.

从循环队列中删除一个元素时，其操作是__先移动队首元素，后取出元素 8. 在具有n个单元的循环队列中，队满时共有__ n-1__个元素。

9. 一个栈的输入序列是12345，则栈的输出序列43512是_不可能的___。 10. 一个栈的输入序列是12345，则栈的输出序列12345是_可能的___。 2.3 算法设计题:

4

设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1, a2,…. an）逆置为(an, an-1,…., a1)。

按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2节例3—1的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：

A-B*C/D+E↑F

习 题 三 链表（线性表、栈和队列）

3.1 单项选择题

1. 不带头结点的单链表head为空的判定条件是____。

A. head= =NULL B. head—＞next= =NULL C. head—＞next= =head D. head!=NULL 2. 带头结点的单链表head为空的判定条件是____。

A. head= =NULL B. head—＞next= =NULL C. head—＞next= =head D. head!=NULL

3. 非空的循环单链表head的尾结点（由p所指向）满足____。 A. p—＞next= =NULL B. p= =NULL C. p—＞next= =head D. p= =head

4. 在循环双链表的p所指结点之后插入s所指结点的操作是____。

A. p—＞right=s; s—＞left=p; p—＞right—＞left=s; s—＞right=p—＞right; B. p—＞right=s; p—＞right—＞left=s; s—＞left=p; s—＞right=p—＞right; C. s—＞left=p; s—＞right=p—＞right; p—＞right=s; p—＞right—＞left=s; D. s—＞left=p; s—＞right=p—＞right; p—＞right—＞left=s; p—＞right=s;

5. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。

A. s—＞next=p—＞next; p—＞next=s; B. p—＞next=s—＞next; s—＞next=p; C. q—＞next=s; s—＞next=p; D. p—＞next=s; s—＞next=q; 6. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。 A. s—＞next=p; p—＞next=s;

B. s—＞next=p—＞next; p—＞next=s; C. s—＞next=p—＞next; p=s;

5

D. p—＞next=s; s—＞next=p;

7. 在一个单链表中，若删除p所指结点的后续结点，则执行____。 A. p—＞next= p—＞next—＞next；

B. p= p—＞next; p—＞next= p—＞next—＞next； C. p—＞next= p—＞next; D. p= p—＞next—＞next；

9.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。

A. n B. n/2 C. (n-1)/2 D. (n+1)/2

10. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____。

A. O（1） B.O（n） C. O (n2) D.O (nlog2n) 11. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是____。 A. O（1） B.O（n） C. O (n2) D.O (nlog2n) 12. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行____。

(不带空的头结点) A. HS—＞next=s;

B. s—＞next= HS—＞next; HS—＞next=s; C. s—＞next= HS; HS=s;

D. s—＞next= HS; HS= HS—＞next;

13. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行____。

(不带空的头结点)

A. x=HS; HS= HS—＞next; B. x=HS—＞data;

C. HS= HS—＞next; x=HS—＞data; D. x=HS—＞data; HS= HS—＞next; 3.2 填空题（将正确的答案填在相应的空中） 1. 单链表是_线性表 ___的链接存储表示。 2. 可以使用__双链表__表示树形结构。

3. 在双链表中，每个结点有两个指针域，一个指向_前驱结点___，另一个指向__后续结点__。

4. 在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作： ⑴ s—＞next=__ p—＞next __; ⑵ p—＞next=s; ⑶ t=p—＞data;

⑷ p—＞data=__ s—＞data __; ⑸ s—＞data=__ t

5. 在一个单链表中删除p所指结点时，应执行以下操作： q= p—＞next;

p—＞data= p—＞next—＞data;

p—＞next=_ p—＞next—＞next ___;

6

free(q);

6. 带有一个头结点的单链表head为空的条件是__ head—＞next= =NULL __。

7. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s—＞next=_p—＞next和p—＞next=s __的操作。

8. 非空的循环单链表head的尾结点（由p所指向），满足条件___ p—＞next= head _。

9. 在栈顶指针为HS的链栈中，判定栈空的条件是_ HS= =NULL ___。

10. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是__ O(1)__；在给定值为x的结点后插入一个新结点的时间复杂度是__ O（n）__。

3.3 算法设计题:

1. 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。 2. 试写一算法，实现单链表的就地逆置。

假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

习 题 五 数 组

5.1 单项选择题（其中A[i..j]表示下标从i到j） 1. 常对数组进行的两种基本操作是____。 A. 建立与删除 B. 索引和修改 C. 查找和修改 D. 查找与索引

2. 二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M 至少需要__①__个字节；M的第8列和第5行共占__②__个字节。 ① A. 90 B. 180 C. 240 D. 540 ② A. 108 B. 114 C. 54 D. 60

4. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是____。 A. 80 B. 100 C.240 D. 270

5. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为____。 A. SA+141 B. SA+144 C. SA+222 D. SA+225

6. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为____。 A. SA+141 B. SA+180 C. SA+222 D. SA+225

5.2 填空题（将正确的答案填在相应的空中，其中A[i,j]表示下标从i到j）

7

1. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是__ LOC (A[0][0])+(n*i+j)*k __。

2. 二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是____。

3. 二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是____。 5.3 算法设计题:

1. 假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。

2. 假设系数矩阵A和B均以三元组顺序表作为存储结构。试写出满足以下条件的矩阵相加的算法：假设三元组顺序表A的空间足够大，将矩阵B加到矩阵A上，不增加A，B之外的附加空间，你的算法能否达到O（m+n）的时间复杂度？其中m和n分别为A，B矩阵中非零元的数目。

3．试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。 4．求下列广义表操作的结果：

（1） GetTail[GetHead[((a,b),(c,d))]];

（2） GetTail[GetHead[GetTail[((a,b),(c,d))]]]

习题答案

5.1 1. C 2. D,B 4. C 5. C 6. B 5.2 1. LOC (A[0][0])+(n*i+j)*k 2. 326 3. 1208

习 题 六 树 和 二 叉 树

6.1 单项选择题

1. 如图8.7所示的4棵二叉树，__C__不是完全二叉树。

（A）

（B）8

（C）（D）图8.7 4棵二叉树

2. 如图8.8所示的4棵二叉树，___B_是平衡二叉树。

（A）（B）（C）（D）图8.8 4棵二叉树

3. 在线索化二叉树中，t所指结点没有左子树的充要条件是____。 A. t—＞left=NULL B. t—＞ltag=1 C. t—＞ltag=1且t—＞left=NULL D. 以上都不对

4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法____。 A. 正确 B. 错误

5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法____。 A. 正确 B. 错误

6. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法____。 A. 正确 B. 错误

7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。

A. 2h B. 2h-1 C. 2h+1 D. h+1 8. 如图8.9所示二叉树的中序遍历序列是____。

9

A. abcdgef B. dfebagc C. dbaefcg D. defbagc

abcdgef图8.9 一棵二叉树

9. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____。

A. acbed B. decab C. deabc D. cedba

10．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。

A．a在b的右方 B．a在b的左方 C．a是b的祖先 D．a是b的子孙

11. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。

A．15 B．16 C．17 D．47

12.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是____。

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca

13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法____。 A. 正确 B. 错误

14. 按照二叉树的定义，具有3个结点的二叉树有____种。 A. 3 B. 4 C. 5 D. 6

15. 一棵二叉树如图8.10所示，其中序遍历的序列为____。

10

A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh

abcdefg图8.10 一棵二叉树h

16. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论____是正确的。

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D. 以上都不对

17. 深度为5的二叉树至多有____个结点。 A. 16 B. 32 C. 31 D. 10

18. 在一非空二叉树的中序遍历序列中，根结点的右边____。

A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 19. 树最适合用来表示____。

A. 有序数据元素 B. 无序数据元素

C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据

20. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对

21. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用____存储结构。

A. 二叉链表 B. 广义表存储结构 C. 三叉链表 D. 顺序存储结构 22. 对一个满二叉树，m个树叶，n个结点，深度为h，则____ 。

11

A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1

23. 如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序为____。 A. uwvts B. vwuts C. wuvts D. wutsv 24.具有五层结点的二叉平衡树至少有____个结点。 A. 10 B. 12 C. 15 D. 17

25. 设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是____。 A. n在m右方 B. n是m祖先 C. n在m左方 D. n是m子孙

6.2 填空题（将正确的答案填在相应的空中）

1. 有一棵树如图8.12所示，回答下面的问题： ⑴ 这棵树的根结点是__k1__；

⑵ 这棵树的叶子结点是_k2 k4 k5 k7___； ⑶ 结点k3的度是__2__； ⑷ 这棵树的度是_3___； ⑸ 这棵树的深度是__4__；

⑹ 结点k3的子女是__k5 k6__； ⑺ 结点k3的父结点是__k1__；

k1k2k3k4k5k6k7图8.12 一棵树2. 指出树和二叉树的三个主要差别_树的结点个数至少为1，而二叉树的结点个数可以为0___、树中结点的最大度数没有，而二叉树结点的最大度数为2____、树的结点无左、右之分，而二叉树的结点有左、右之分____。

3. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题___。

4. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图8.13所示，则该二叉树的链接表示形式为____。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 12 e a f d g c j l h b

5. 深度为k的完全二叉树至少有_2k1___个结点。至多有21____个结点，若按自上而

k2k下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是__21__。

6. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n0=n21____。

7. 一棵二叉树的第i（i≥1）层最多有__2i1___个结点；一棵有n（n>0）个结点的满二叉

树共有__2[log2n+1]-1 __个叶子和___n-2[log2n+1]-1 _个非终端结点。

8. 结点最少的树为只有一个结点的树____，结点最少的二叉树为空的二叉树___。

9. 现有按中序遍历二叉树的结果为abc，问有_5___种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是__ _。

10. 根据二叉树的定义，具有三个结点的二叉树有__5___种不同的形态，它们分别是____。 11. 由如图8.17所示的二叉树，回答以下问题： ⑴ 其中序遍历序列为_dgbaechif___； ⑵ 其前序遍历序列为_abdgcefhi___； ⑶ 其后序遍历序列为__gdbeihfca__； ⑷ 该二叉树的中序线索二叉树为____； ⑸ 该二叉树的后序线索二叉树为____； ⑹ 该二叉树对应的森林是____。

abcadefbcdgheifg图8.20 一棵树图8.17 一棵二叉树12. 已知一棵树如图8.20所示，转化为一棵二叉树，表示为____。

13. 以数据集{4，5，6，7，10，12，18}为结点权值所构造的Huffman树为____，

13

623725191813121096745图8.22 Huffman树其带权路径长度为_165

6.3 算法设计题:

1．试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。 2. 一棵度为2的树与一棵二叉树有何区别?

3. 一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少? 4. 证明:一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系: n0=(k-1)n1+1

5. 请对下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。

A

B C

D F E

GH

6. 画出和下列已知序列对应的树T：

树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBFG。

7. 假设用于通讯的电文仅有八个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这八个字母设计哈夫曼编码。使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。 8. 假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。 9. 编写按层次顺序（同一层自左至右）遍历二叉树的算法。

14

习 题 七 图

7.1 单项选择题

1. 在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4

2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 3. 一个有n个顶点的无向图最多有____条边。

A. n B. n(n-1) C. n(n-1)/2 D. 2n 4. 具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20

5. 具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8

6. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2

7. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2

8. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ① A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e C.2e D. n+e

9. 已知一个图如图9.5所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b

abced图 9.5 一个无向图f10. 已知一有向图的邻接表存储结构如图9.6所示。

15

1 3 2 ^

2 ^ 3 4 5 4 ^

5 2 4 图9.6 一个有向图的邻接表存储结构

⑴ 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。 A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2

⑵ 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。 A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2

11. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 12. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历

13. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。 A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C. 宽度优先遍历算法 D. 深度优先遍历算法

7.2 填空题（将正确的答案填在相应饿空中） 1. n个顶点的连通图至少__ n-1 __条边。 2. 在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于__1; __，否则等于__0 __。

3. 在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于___1 _。

4. 已知图G的邻接表如图9.7所示，其从顶点v1出发的深度有限搜索序列为_ V1 v2 v3 v6 v5 v4

_，其从顶点v1出发的宽度优先搜索序列为v1_ v2__ v5 v4_ v3 v6。

16

V1 V2 V5 V4 ^

v2 v3 V5 ^

v3 V6 ^

v4 ^

v5 V4 V6 V3 ^

v6 ^

图9.7 图G的邻接表 5. 已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是_求矩阵第i列非零元素之和___。

6.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是__将矩阵第i行全部置为零 __。 7.3

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

1 5 （1）每个顶点的入/出度；

（2）邻接距阵； （3）邻接表； （4）逆邻接表； 6（5）强连通分量。 24

17

3 2．请用克鲁斯卡尔普里姆两种算法分别构造最小生成树：

（1）

a b c d f 16 11 15 15 15 13 16 14 12 e 21

（2） 12 1 6 6 15 16

4 7 2 20 9

12 4 3 5

3. 试列出下图中全部的拓扑排序序列。

3 1 2

4 5

4. 请用图示说明从顶点a到其余各顶点之间的最短路径。

b d 6

a

e c

18

132 5 10 5 f 习题答案

7.1 1. C 2. B 3. C 4. A 5. A 6. C 7. D 8. AC 9. DB 10. CB 11. A 12. D 7.2 1. n-1 2. 1;0 3. 1

4. v1,v2,v3,v6,v5, v4；v1,v2,v5,v4,v3, v6

5. 求矩阵第i列非零元素之和 6. 将矩阵第i行全部置为零

1 5 7.3

1.

6

24

2. (1)． a

11

15c b d 1412

f e （2） 12

1 6 6

4 7 5 2

9 4 5 3 1523

19

152634 156234 561234 34 W=6 512634 b W=5 d 5123 3 a 2 3 3 c 4 e W=3 W=7 20

f W=9 4

5162