数据结构习题集

数据结构习题集

一、判断题：

1. 图可以没有边，但不能没有顶点。（?） 2. 在无向图中，（v1，v2）和（v2，v1）是两条不同的边。（X） 3. 邻接表只能用于有向图的存储。（X） 4. 一个图的邻接矩阵表示是唯一的。（?）

5. 用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的

边数有关。（X） 6. 有向图不能进行广度优先遍历。（X）

7. 若一个无向图以顶点v1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一

确定该图。（?）

8. 存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵上三角（或下三角）部分就可以了。（?） 9. 用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。（X） 10. 若从一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，

则该图一定是连通的。（?）

11. 二分查找法要求待查表的关键字值必须有序。（） 12. 对有序表而言，采用二分查找部总比采用顺序查找法速度快。（） 13. 在二叉排序树中，根结点的值都小于孩子结点的值。（） 14. 15. 16. 17.

散列存储法的基本思想是由关键字的值决定数据的存储地址。（） 哈希表是一种将关键字转换为存储地址的存储方法。（） 选择好的哈希函数就可以避免冲突的发生。（）

在有序的顺序表和有序的链表上，均可以采用二分查找来提高查找的速度。（）

18. 采用分块查找，既能实现线性表所希望的查找速度，又能适应动态变化的需要。（） 19. 哈希查找的效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。（） 20. 在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指

针域置空即可。（）

二、填空题：

1. 图常用的存储方式有邻接矩阵和 等。

2. 图的遍历有 和广度优先搜索等方法。

3. 有n条边的无向图邻接矩阵中，1的个数是 。 4. 有向图的边也称为 。

5. 图的邻接矩阵表示法是表示 之间相信关系的矩阵。

6. 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 。 7. n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为 。 8. n个顶点e条边的图若采用邻接表存储，则空间复杂度为 。 9. 设有一稀疏图G，则G采用 存储比较节省空间。 10. 设有一稠密图G，则G采用 存储比较节省空间。 11. 图的逆邻接表存储结构只适用于 图。 12. n个顶点的完全无向图有 条边。

13. 有向图的邻接表表示适于求顶点的 。

- 1 -

14. 有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点vi的 。 15. 对于具有n个顶点的图，其生成树有且仅有 条边。

16. 对有n个顶点e条弧的有向图，其邻接表表示中，需要 个结点。 17. 从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为

图的 。 18. 无向图的邻接矩阵一定是 矩阵。

19. 一个连通网的最小生成树是该图所有生成树中 最小的生成树。 20. 若要求一个稠密图G的最小生成树，最好用 算法来求解。 21. 顺序查找法，表中元素可以 存放。

22. 在分块查找方法中，首先查找 ，然后再查找相应的块。 23. 顺序查找、二分查找、分块查找都属于 查找。 24. 查找表所含元素个数在查找阶段是固定不变的。

25. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为 。 26. 对于长度为n的线性表，若进行二分查找，则时间复杂度为 。

27. 理想情况下，在散列表中查找一个元素的时间复杂度为 。

28. 在关键字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找关键字92，要比较 次才能找到。

29. 设有100个元素，用二分查找法查找时，最大的比较次数是 次。 30. 对于二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较，若比较结点值小，则继续在 子树中查找。 31. 二叉排序树是一种 查找表。

32. 哈希表是按 存储方式构造的存储结构。

33. 哈希法既是一种存储方法，又是一种 方法。

34. 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理 的方法。 35. 设散列函数H和键值k1、k2，若k1=k2，而H（k1）=H（k2），则称这种现象为 。 36. 处理冲突的两类主要方法是开放定址法和 。 37. 查找法的平均查找长度与元素个数n无关。

38. 在哈希函数H（key）=key%p中，P一般应取 。 39. 在查找过程中插入元素或删除元素操作的，称为 查找。

40. 各结点左、右子树深度之差的绝对值至多为 的二叉树称为平衡二叉树。 41. 数据的存储结构被分为顺序结构、链接结构、 、散列结构4种。索引结构 42. 在双向链表中，每个结点包含有两个指针域，一个指向其 结点，另一个指向其 结点。前驱 后继 43. 在一个图中，所有顶点的度数之和等于所有边数的 倍。2

44. 对于一棵具有n个结点的树，该树中所胡结点的度数之和为 。n-1 45. 假定一棵树的广义表表示为A（B（C（D，E），F，G（H，I，J）），K），则度为3的结点数为 个。2

46. 一个算法应具备的5个特性为 、 、 、输入、输出。 有穷性 确定性 可行性

47. 以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为 。 37/12、

48. 对于线性表（18，25，63，50，42，32，90）进行散列存储时，若选用H(k)=k%9作为

散列函数，则散列地址为0的元素有 个，散列地址为5的元素有 个。3 2

- 2 -

49. 在双向循环链表中，每个结点的前驱指针为prior，后继指针为next。在指针P所指的

结点之后插入指针f所指的结点，其操作为 。

f->next=p->next; p->next->prior=f; f->prior=p; p-next=f;

50. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表

尾插入元素的时间复杂度为 。O（n） O(1) 51. 中缀表达式3+x*(2.4/5-6)所对应的后缀表达式为 。3 x 2.4 5 / 6 - * + 52. 假定一棵树的广义表表示为A（B（C（D，E），F，G（H，I，J）），K），则度为0的结点数为 个。 7

53. 对于线性表（18，25，63，50，41，32，90，66）进行散列存储时，若选用H(k)=k

作为散列函数，则散列地址为3的元素有 个，散列地址为8的元素有 个。1 2 54. 中缀算术表达式3+4/(25-(6+15))*8所对应的后缀算术表达式为 。

3 4 25 6 15 +－/8*+

55. 快速排序在平列情况下的时间复杂度为 ，在最坏情况下的时间复杂度为 。 O(nlog2n) O(n2) 56. 前序序列和中序序列相同的二叉树为 。单右枝二叉树或孤立结点 57. 每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 排序。 插入 58. 一个n×n的对称矩阵，如果以行或列为主序存入内存，则其容量为 。n(n+1)/2 59. 后缀表达式2 10 + 5 * 6 – 9 /的值为 。6

60. 对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为 ，右孩子

结点的编号为 。 2i 2i+1 61. 62. 63. 64.

假定一棵二叉树的结点数为18，则它的最小深度为 ，最大深度为 。 5 18 从一个栈删除元素时，首先取出 。栈顶元素

在线性表的 存储中，对每一个元素只能采用顺序查找。链接 一棵深度为5的满二叉树中的结点数为 个。31

65. 在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 域，另一个

叫 域。 元素值 指针 66. 当从一个小根堆中删除一个元素时，需要把堆尾元素填补到 位置，然后再按条件

把它逐层 调整。 堆顶 向下 67. 假定一棵树的广义表表示为A（B（C（D，E）,F,G(H,I,J））,k),则度为2的结点数为 个。2

68. 从有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素时，其查

找长度分别是 和 。1 3

69. 在散列表Hash查找中，评判一个散列函数优劣的两个主要条件是 和 。 值均匀分布于表空间以减少冲突 函数尽可能简单以方便计算 70. 后缀算术表达式24 8 + 3 * 4 10 7 - * /所对应的中缀自述表达式为 ，

其值为 。（24+8）*3、（4*（10－7）） 8

71. 在一个单链表HL中，指针域为next。若要向表头插入一个由指针P指向的结点，则应执行语句 。 p-next=HL;HL=p; 72. 假定一组记录的排序码为（46，79，56，38，40，80，25，34），在对其进行快速排序

的过程中，进行第一次划分后得到的排序码序列为 。40，34，25，38，46，80，56，79

73. 对于线性表（18，25，63，50，41，32，90，66）进行散列存储时，若选用H(k)=k

作为散列函数，则散列地址为0的元素有 个，散列地址为8的元素有 个。1 2

- 3 -

74. 若对一棵二叉树的结点编号从0开始顺序编码，按顺序存储，把编号为0的结点存储到

a[0]中，依次类推，则a[i]元素的左孩子元素为 ，右孩子元素为 。 2i+1 2i+2

75. 在一相具有n个顶点的无向完全图中，包含有 条边，在一个具有n个顶点的有向

完全图中，包含有 条边。 n(n-1)/2 n(n-1) 76. 在一棵高度为h的3叉树中，最多含有 个结点。（3h-1）/2

77. 对于一个顺序实现的共享栈S[1..n]，栈顶指针分别为top1和top2，top1由小到大，top2

由大到小，其判断下溢的条件是 ；判断上溢的条件是 。top1=0或top2=n+1; top1+1=top2

78. 在循环双向链表中表头结点的左指针域指向 结点，最后一个结点的右指针域

指向 结点。 表尾 表头

79. 每次从无序表中挑选出一个最大或最小元素，把它交换到有序表中的一端，此种排序方法叫 排序。选择

80. 对于一个以顺序实现的特环队列Q[0..m-1]，队头、队尾指针分别为f，r，其判空的条件是 ，判满的条件是 。r=f (r+1)%m=f 81. 假定一棵树的广义表表示为A（B（C（D，E）,F,G(H,I,J））,k)，则度为1的结点个数为 个。0

82. 在一棵树中， 没有前驱结点。树根结点

83. 以二分查找方法查找一个线性表时，此线性表必须是 存储的 表。顺序 有序

三、选择题

1. 在一个图中，所有顶点的度数之和等于图的边数的（）倍。

A.1/2 B.1 C.2 D.4

2. 在一个有向图中，所有顶点的度数之和等于所有顶点的出度之和的（）倍。 A.1/2 B.1 C.2 3. 对于一个具有n个顶点的有向图，边数最多有（）。

D.4

A.n B.n(n-1) C.n(n-1)/2 D.2n 4. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。 A.n B.n+1 C.n-1 5. 有8个结点的有向完全图有（）条边。 A.14 B.28 6. 深度优先遍历类似于二叉树的（）。 A.先序遍历 B.中序遍历 7. 广度优先遍历类似于二叉树的（）。

C.56

D.n/2 D.112 D.层次遍历 D.层次遍历 D.可能不存在 D.下标 D.n行任意列 D.n+e

C.后序遍历

A.先序遍历 B.中序遍历 C.后序遍历 8. 任何一个无向连通图的最小生成树（）。 A.只有一棵

B.一棵或多棵

C.一定有多棵

9. 无向图顶点v的度是关联于该顶点（）的数目。 A.顶点 B.边 C.序号

10. 有n个顶点的无向图的邻接矩阵是用（）数组存储的。 A.一维 B.n行n列 C.任意行n列 A.n-1 B.n+1 C.n 12. 在图的表示法中，表示形式唯一的是（）。

- 4 -

11. 对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（）。

A.邻接矩阵表示法 B.邻接表表示法

C.逆邻接表表示法 D.邻接表和逆邻接表表示法 13. 在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（）。 A.n B.e 14. 图1中，度为3的结点是（）。 A.v1 15. 图1是（）。

B.v2

C.2n C.v3

D.2e D.v4

A.连通图 B.强连通图 C.造成树 D.无环图 16. 图2所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种

顶点序列为（）。

A. a,b,e,c,d,f B. a,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b 17. 图2所示，从顶点a出发，按广度优先进行遍历， 18. 则可能得到的一种

顶点序列为（）。 A. a,b,e,c,d,f

B. a,b,e,c,f,d D. a,e,d,f,c,b C.哈夫曼算法

D.迪杰斯特拉算法

C. a,e,b,c,f,d 19. 最小生成树的构造可使用（）算法。 A.Prim算法 B.卡尔算法

20. 下面关于图的存储结构的叙述中正确的是（）。

A.用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关。 B.用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关。 C.用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关。 D.用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关。 21. 连通分量是（）的极大连通子图。 A.树 B.图 22. 查找表是以（）为查找结构。

C.无向图

D.有向图 D.文件 D.索引存储

A.集合 B.图 C.树 23. 顺序查找法适合于存储结构为（）的线性表。 A.散列存储 B.顺序存储或链接存储 C.压缩存储

24. 在表长为n的链表中进行线性查找，它的平均查找长度为（）。 A.ASL=n

B.ASL=(n+1)/2

C.ASL=

n?1

D.ASL≈log2n

25. 对线性表进行二分查找时，要求线性表必须（）。 A.以顺序方式存储 C.以链接方式存储

B.以链接方式存储，且结点按关键字有序排序 D.以顺序方式存储，且结点按关键字有序排序

26. 衡量查找算法主要标准是（）。

A.元素个数 B.平均查找长度 C.所需的存储量 D.算法难易程度

27. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（）查找方法。 A.分块

B.顺序

C.二分

D.散列

28. 链表适用于（）查找。 A.顺序 B.二分 C.随机 D.顺序或二分

29. 一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值

- 5 -

为82的结点时，（）次比较后查找成功。

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

30. 一个有序表为{4，6，10，12，20，30，50，70，88，100}，当二分查找值为58时，它

将依次与（）比较大小，查找结果失败。 A.30，88，70，50 B.20，70，30，50 C.20，50 D.30，88，50 31. 对有14个元素的有序表A[1..14]作二分查找，查找元素A[4]时的被比较元素依次为（）。 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]

32. 有一个长度为12的有序表，按二分查找法对其进行查找，在表内各元素等概率情况下

查找成功所需要的平均比较次数为（）。

A.35/12 B.37/12 C.39/12 D.43/12

33. 采用分块查找时，若线性表共有625个元素，查找每个元素的概率相等，假设采用顺序查找来确定结点所在的块时，每块分（）个结点最佳。 A.6 B.10 C.25 D.625 34. 下列（）不是利用查找表中数据元素的关系进行查找的方法。 A.平衡二叉树 B.有序表的查找 C.散列查找 D.二叉排序树的查找 35. 设哈希表长m=14，哈希函数H(key)=key。表中已有4个结点：addr(15)=4，addr(38)=5，

addr(61)=6，addr(84)=7，其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是（）。 A.8 B.3 C.5 36. 对包含n个元素的散列表进行查找，平均查找长度为（）。 A.O（n） B.O(log2n) 37. 冲突是指（）。

A.两个元素具有相同的序号 C.不同键值对应相同的存储地址

2

D.9

D.不直接依赖于n

C.O(n)

B.两个元素的键值不同 D.两个元素的键值相同

D.外查找

38. 在查找过程中，不做增加、删除或修改的查找称为（）。 A.静态查找 B.内创造 C.动态查找

39. 已知8个元素为{34，76，45，18，26，54，92，65}，按照依次插入结点的方法生成一

棵二叉树，最后两层上结点的总数为（）。 A.1 B.2 C.3 40. 不可能生成右图所示的二叉排序树的关键字序列是（）。 A.4 5 3 1 2 B.4 2 5 3 1 41. 动态查找包括（）查找。 A.顺序表 B.二叉排序树

C.4 5 2 1 3 C.有序表

D.4 D.4 2 3 1 5 D.索引顺序表

42. 二分查找要求被查找的表是（）。C A.键值有序的链接表 C.键值有序的顺序表

B.链接表但键值不一定有序 D.顺序表但键值不一定有序

43. Substr(“DATA STRUCTURE”,5,9)=( )。A A.”STRUCTURE” B.”ASTUCTUR” C.”DATA STRUCTRUE 44. 从一个循环顺序队列删除元素时，首先需要（ ）。B A.前移一位队首指针 B.后移一位队首指针

C.取出队首指针所在位置上的元素 D.取出队尾指针所在位置上的元素 45. 在有n个叶子结点的Huffman树中，其结点总数为（）。D A.不确定 B.2n C.2n+1 D.2n-1

- 6 -

46. 线索化二叉树中某结点D，没有左孩子的主要条件是（）。B A.D->Lchild=NULL B.D->ltag=1 47. 广义表((a))，其表头是（）B

C.D->rchild C.()

D.D->ltag=0 D.((a))

A.a B.(a) 48. 栈的插入与删除操作在（）进行。A

A．栈顶 B．栈底 C．任意位置 D．指定位置 49. 设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针操作为（）。A

A．p->next=p->next->next C．p=p->next->next A．数据项

B．p=p->next D．p->next=p C．数据元素

D．数据变量

50. 组成数据结构的基本单位是（）。C

B．数据类型

51. 如果以链表作为栈的存储结构，则退栈操作时（）C A．必须判别栈是否满 B．对栈不作任何操作 C．必须判别栈是否空 D．判别栈元素的类型 52. 在一个循环队列中，队首指针指向队首元素的（）位置。A A．前一个 B．后一个 53. 二叉树第i层上至多有（）结点。C A．2i B．2i

C．当前 C．2i-1

D．后面 D．2i-1

54. 线性表采用链式存储时，其地址（）。D A．必须是连续的 B．部分地址必须是连续的

C．一定是不连续的 D．连续与否均可以 55. 一个栈的入栈序列是abcde，则栈的不可能的输出序列是（）。D A．edcba B．decba C．abcde D．dceab 56. 在用邻接表表示图的情况下，建立图的算法的时间复杂度是（）。A A．O（n+e） B．O(n2 ) C．O(n×e) D．O(n3) 57. 设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能顺序数列为（）B A．3，2，5，6，4，1 C．2，4，3，5，1，6 58.

四、应用题：

1. 有向图如图3所示，画出邻接矩阵和邻接表。

2. 已知一个无向图有6个结点，9条边。9条边依次为（0,1），（0,2），（0,4）， （0,5），（1,2），（2,3），（2,4），（3,4），（4,5）。试画出该无向图，并从顶点0出发， 分别写出按深度优先搜索和广度优先搜索进行遍历的结点序列。

3. 已知一个无向图的顶点集为{a,b,c,d,e}，其邻接矩阵如下，画出草图，写出从顶点a出

发按深度优先搜索进行遍历的结点序列。

0 1 0 0 1

1 0 0 1 0 0 0 0 1 1

0 1 1 0 1 1 0 1 1 0

4. 网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。

- 7 -

B．1，5，4，6，2，3 D．4，5，3，6，2，1

0 8 10 11 0 8 0 3 10 3 0 11 0 4 0 13 0

5. 已知某图G的邻接矩阵如下：

0 1 0 1 1 0 1 0 0 1 0 1 0 13 4 0 0 7 7 0

1 0 1 0

①画出相应的图；

②要使此图为完全图需要增加几条边。 6. 已知某有向图如图4所示，

①给出该图每个顶点的入度和出度； ②给出该图的邻接表； ③给出图4的邻接矩阵。 7. 根据图5，完成以下操作： ①写出无向带权图的邻接矩阵； ②设起点为a，求其最小生成树。 8. 给定网G如图6所示。 ①画出网G的邻接矩阵；

②画出网G的最小生成树。

9. 对于给定结点的关键字集合K={5，7，3，1，9，6，4，8，2，10}： ①试构造一棵二叉排序树；

②求等概率情况下的平均查找长度ASL。

10. 对于给定结点的关键字集合K={10，18，3，5，19，2，4，9，7，15}： ①试构造一棵二叉排序树；

②求等概率情况下的平均查找长度ASL。

11. 将数据序列：25，73，62，19，325，138，依次插

图所示的二叉排序树，并画出最后结果。

12. 对于给定结点的关键字集合K={1，12，5，8，3，10，7，13，9}： ①试构造一棵二叉排序树；

②在二叉排序列树BT中删除“12”后的树结构。

13. 对于给定结点的关键字集合K={34，76，45，18，26，54，92，38}： ①试构造一棵二叉排序树；

②求等概率情况下的平均查找长度ASL。

14. 对于给定结点的关键字集合K={4，8，2，9，1，3，6，7，5}：

- 8 -

入下

①试构造一棵二叉排序树；

②求等概率情况下的平均查找长度ASL。

15. 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查

找长度。

16. 二叉排序树如上右图所示，分别画出：

①删除关键字节5以后的二叉树，并要求其平均查找长度尽可能小； ②在原二叉排序树（即没有删除15）上，插入关键字20。

17. 给定结点的关键字序列为：19，1，23，1，68，20，84，27，55，11，10，79。

设散列表的长度为13，散列函数为：H(k)=K。试画出线性探测再散列解决

冲突时所构造的散列表，并求出其平均查找长度。

18. 给定结点的关键字序列为：47，7，29，11，16，92，22，8，3。哈希表的长度为11，

散列函数为：H(k)=K。试画出平方探测再散列解决冲突时所构造的散列表，并求出其平均查找长度。

19. 给定结点的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。设散

列表的长度为13，散列函数为：H(k)=K。试画出链地址法解决冲突时所构造的哈希表，并求出其平均查找长度。

20. 给定结点的关键字序列为：47，7，29，11，16，92，22，8，3。哈希表的长度为11，

散列函数为：H(k)=K。试画出链地址法解决冲突时所构造的哈希表，并求出其平均查找长度。 21. 已知一棵二叉树的中序遍历结果为DBHEAFICG，前序遍历结果为ABDEHCFIG，请画

出该二叉树。

22. 假定用于通信的电文仅由8个字母a,b,c,d,e,f,g,h组成，各个字母在电文中出现的频率分

别为5，25，3，6，10，11，36，4。试为这8个字母设计不等长Huffman 编码，并输

出该电文的总码数。 a b c d e f g h Huffman编码为：依字母次序 100 10 0000 0101 001 011 11 0001

电文总码数为：4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4＝257

23. 对于结点类型为Lnode的单链表，以下算法的功能为 。

void BB(Lnode *HL) { Lnode *p=HL; HL=NULL; While(p!=NULL { Lnode *q=p; P=p->next;

- 9 -

q->next=HL;

HL=q;

}

} 将一个单链表按逆序链接 24. 下面递归算法的功能是 。

五、程序填空题：

1. 图G为有向无权图，试在邻接矩阵存储结构上实现删除一条边（v,w）的操作：

DeleteArc(G,v,w)。若无顶点v或w，返回“ERROR”；若成功删除，则边数减1，并返

回“OK”。（提示：删除一条边的操作，可以将邻接矩阵的第i行全部置0） Status DeleteArc(MGraph &G,char v,char w)

//在邻接矩阵表示的图G上删除边（v,w）

{ if((i=LocateVex(G,v))<0) return ; if((j=LocateVex(G,v))<0) return ; if(G,arcs[i][j].adj)

{ G.arcs[i][j].adj= ; G.arcnum ;

}

Return ; }

2. 以下为向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法。请在横

线处将程序补充完整。

void Insert(BtreeNode *BST, const ElemType item){ if(BST=NULL){

BtreeNode *p=new BtreeNode; p->date=item;

BST=p;

}

else if(itemdate) ; else ; }

参考答案： p->left=p->right=NULL; Insert(BST->left,item); Insert(BST->right,item);

3.

六、算法题：

1. 编写一个无向图的邻接矩阵转换成邻接表的算法。

2. 已知有n个顶点的有向图邻接表，设计算法分别实现以下功能： ①求出图G中每个顶点的出度和入度；

②求出G中出度最大的一个顶点，输出其顶点序号； ③计算图中度为0的顶点数。

3. 设单向链表的结点是按关键字从小到大排列的，试写出对此链表进行查找的算法。如果

查找成功，则返回指向关键字为x的结点的指针，否则返回NULL。

4. 试设计一个在用开放地址法解决冲突的散列表上删除一个指定结点的算法。

- 10 -

5. 设给定的散列表存储空间为H[1-m]，每个单元可存放一个记录，H[i]的初始值为0，选取散列函数为H（R.key），其中key为记录R的关键字，解决冲突的方法为线性探测法，编写一个函数将某记录R填入到散列表H中。

6. 编写向类型为List的线性表L中第i个元素位置插入一个元素的算法，假定不需要对i

的值进行有效性检查，同时不需要检查存储空间是否用完。

void Insert(List &L, int i, ElemType x){ for(int j=L.size-1;j>=i-1;j--) L.list[j+1]=L.list[j];

L.list[i-1]=x; L.size++;

}

7. 编写对二叉树进行中序遍历的非递归算法。

void Inorder(BTreeNode *BT){ BtreeNode *s[10]; int top=-1;

BTreeNode *p=BT; while(top!=-1||p!=NULL){ top++; s[top]=p; p=p->left; }

if(top!=-1){ p=s[top]; top--;

cout<data<right; }

} }

8. 编写一个算法，返回搜索树中的关键码最小的元素值。

ElemType FindMax(BtreeNode BST){ if(BST=NULL){

cerr<<”不能在空树上查找最小值！”<

BtreeNode *t=BST; while(t->left!=NULL) t=t->left; return t->data;

}

- 11 -

5. 设给定的散列表存储空间为H[1-m]，每个单元可存放一个记录，H[i]的初始值为0，选取散列函数为H（R.key），其中key为记录R的关键字，解决冲突的方法为线性探测法，编写一个函数将某记录R填入到散列表H中。

6. 编写向类型为List的线性表L中第i个元素位置插入一个元素的算法，假定不需要对i

的值进行有效性检查，同时不需要检查存储空间是否用完。

void Insert(List &L, int i, ElemType x){ for(int j=L.size-1;j>=i-1;j--) L.list[j+1]=L.list[j];

L.list[i-1]=x; L.size++;

}

7. 编写对二叉树进行中序遍历的非递归算法。

void Inorder(BTreeNode *BT){ BtreeNode *s[10]; int top=-1;

BTreeNode *p=BT; while(top!=-1||p!=NULL){ top++; s[top]=p; p=p->left; }

if(top!=-1){ p=s[top]; top--;

cout<data<right; }

} }

8. 编写一个算法，返回搜索树中的关键码最小的元素值。

ElemType FindMax(BtreeNode BST){ if(BST=NULL){

cerr<<”不能在空树上查找最小值！”<

BtreeNode *t=BST; while(t->left!=NULL) t=t->left; return t->data;

}

- 11 -

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