数据结构原理与分析--01343--18日下-复习资料

1、数据结构原理与分析-01343-18日下-复习资料一、填空1. 线性表是具有 n个什么的有限序列数 据元素 。2. 邻接表的存储结构以下图的深度优先遍历类似于二叉树的先序遍历。3. 在一棵二叉树的二叉链表中，空指针域 数等于非空指针域数加24. 某二叉树的前序和后序序列正好相反，那么该二叉树一定是什么二叉树高度等于其结点数。5. 对于栈操作数据的原那么是后进先出 6. 结点前序为xyz的不同二叉树，所具有 的不同形态为5 。7. 设长度为n的链队列用单循环链表表 示，假设只设头指针，那么入队操作的时间复 杂度为On。8. 在一棵高度为h假定树根结点的层号为0的完全二叉树中，所含结点个数不小于2

2、h 。9. 具有n个顶点的有向无环图最多可包含有向边的条数是nn-1/2 。10. 因此在初始为空的队列中插入元素a,b,c,d 以后，紧接着作了两次删除操作， 此时的队尾元素是 d .11. 假设二叉树中度为 2的结点有15个，度 为1的结点有10个，那么叶结点的个数16。12. 对于一棵满二叉树，m个树叶，n个结点，深度为h,那么n=2h + 1-1 。13. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于n+114. 用邻接表表示图进行深度优先遍历时， 通常用来实现算法的辅助结构是栈。15. 堆的形状是一棵完全二叉树。16. 假设在一棵非空树中，某结点A有3个兄弟结点包括A自身，

3、B是A的双亲结点， 那么B的度为4 。17. 任何一个无向连通图的最小生成树 有 一棵或多棵18. 在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该只有左子树上的所有结点。19. 排序方法中，从未排序序列中依次取出 元素与已排序序列中的元素进行比拟，将 其放入已排序序列的正确位置上的方法， 称为插入排序。20. 对于一棵满二叉树，m个树叶，n个结点，深度为h,那么n=2h + 1-1 。21. 具有n个顶点的有向图最多可包含的有向边的条数是nn-1。22. 某二叉树的前序和后序序列正好相同，那么该二叉树一定是什么样的二叉树空或只有一个结点。23. 栈和队列的主要区别在于插入删除运算的限定

4、不一样。24. 串是任意有限个字符构成的序列25. 对有14个数据元素的有序表 R14进行折半搜索，搜索到 R3的关键码等于给 定值，此时元素比拟顺序依次为R6,R2 , R4 , R3。26. 深度为h且有多少个结点的二叉树称为满二叉树2h+1-1。27. 在含n个顶点e条边的无向图的邻接矩 阵中，零元素的个数为n2-2e 。28. 在一个有向图中，所有顶点的入度之和与所有顶点出度之和的倍数为1。29. 邻接表的存储结构以下图的广度优先遍 历类似于二叉树的按层遍历。30. 设高度为h的二叉树上只有度为0和度为2的结点，那么此类二叉树中所包含的结 点数至少为2h-1。31. 假设一棵二叉树具有

5、10个度为2的结点，5个度为1的结点，那么度为 0的结点个数 是1132. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于n+133. 假设一棵二叉树有11个度为2的结点，那么该二叉树的叶结点的个数是12。34. 对有n个记录的表按记录键值有序建 立二叉查找树，在这种情况下，其平均查 找长度的量级为On35. 设森林F中有三棵树，第一、第二和第 三棵的结点个数分别为 m1,m2和m3,那么森 林F对应的二叉树根结点上的右子树上结点个数是m2+m3。36. 对有18个元素的有序表作二分折半 查找，那么查找A3的比拟序列的下标为9、4、2、 3。37. 假设要在O 1 的时间复杂度上实现两

6、个循环链表头尾相接，那么应对两个循环链 表各设置一个指针，分别指向各自的尾结点。38. 深度为h的满二叉树所具有的结点个数是2h+1-1 。39. 设高度为h的二叉树上只有度为0和度为2的结点，那么此类二叉树中所包含的结 点数至少为2h-1 40. 如果T2是由有序树T转换而来的二叉树，那么T中结点的先根序列就是T2中结点的先根序列。41. 有n个叶子的哈夫曼树的结点总数为2n-1 。42. 设长度为n的链队列用单循环链表表 示，假设只设头指针，那么入队操作的时间复 杂度为On。43. 假设二叉树中度为2的结点有15个，度 为1的结点有10个，那么叶子结点的个数 为16。44. 假设某完全二叉

7、树的深度为h,那么该完全二叉树中具有的结点数至少是2h 1。45. 叉树的前序和后序序列正好相反，那么该二叉树一定是什么二叉树度等于其结点数。46. 初始序列已经按键值有序时，用直接插入算法进行排序，需要比拟的次数为n-1。47. 接表表示图进行广度优先遍历时，为实现算法通常采用的辅助结构是队列。48. 用冒泡排序法对序列18,16,14,12,10,8 从小到大进行排序，需要进行的比拟次数是15。49. 有n个顶点的图采用邻接矩阵表示，那么该矩阵的大小为n*n 。50. 6个顶点的无向图成为一个连通图至少 应有边的条数是5。51. 单链表中，增加头结点的目的是为了方便运算的实现。52. 在线

8、索二叉树中，结点*t没有左子树的充要条件是t->ltag=1。53. 按照二叉树的定义,具有3个结点的二 叉树有多少种5。54. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施 加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是快 速排序55. 二分查找法要求查找表中各元素的键值必须是递增或递减。56. 线性表的长度是指表中的元素个数57. 将长度为m的单链表连接在长度为n的单链表之后的算法的时间复杂度为On。58 .有一个有序表为1 , 3 ,9 ,12,32 , 41,45, 62, 75, 77, 82, 95, 100，当二分查找值为82

9、的结点时，查找成功的比拟次 数是4。.59. 假设在一棵非空树中，某结点A有3个兄弟结点包括A自身，B是A的双亲结点， 那么B的度为4。60. 深度为h的满二叉树具有的结点个数为2h+1-1 。61. 用二叉链表存储树，那么根结点的右指针 是空。62. 个无向图中，所有顶点的度数之和等于 所有边数1倍。63. 单链表表示的链式队列的队头在链表的什么位置链头。64. 线性表的长度是指表中的元素个数65. 某二叉树的前序和后序序列正好相同，那么该二叉树一定是什么样的二叉树空或只有一个结点。66. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于n+1 。67. 一个具有n个顶点e条边的无向图

10、中， 采用邻接表表示，那么所有顶点的邻接表的 结点总数为2e 。68. 链栈和顺序栈相比，有一个较明显的优点是通常不会出现栈满的情况。69. 对于键值序列72,73,71,23,94,16,5,68,76,103用筛选法建堆，开始结点的键值必须为94。70. 在图形结构中，每个结点的前驱结点数 和后续结点数可以有任意多个。71. 对有n个记录的有序表采用二分查找， 其平均查找长度的量级为 Olog2n。72. 在一棵高度为h假定树根结点的层号 为0的完全二叉树中，所含结点个数不小 于2h。73. 假设一棵二叉树有10个叶结点，那么该二 叉树中度为2的结点个数为9。74. 设有一个顺序栈 S,元

11、素S1, S2, S3, S4, S5, S6依次进栈，如果 6个元素的出 栈顺序为 S2, S3, S4, S6, S5, S1,那么顺 序栈的容量至少应为 3。75. 对于一棵二叉树，设叶子结点数为n0,次数为2的结点数为n2,那么n0和n2的关 系是 n0= n2 + 1。76. 假设一棵二叉树有12个叶结点，那么该二 叉树中度为2的结点个数为11。77. 二叉树的存储结构有顺序存储结构和 链式存储结构。78. 深度为h且有2k-1个结点的二叉树称 为满二叉树。设根结点处在第1层。79. 图的深度优先搜索方法类似于二叉树 的先序遍历。80. 哈夫曼树是带权路径长度最小的二叉树。81. 在

12、线索二叉树中，线索是指向结点在某 遍历次序下的前驱或后继结点的指针。82. 栈可以作为实现递归函数调用的一种 数据结构。83. 一般树的存储结构有双亲表示法、 孩子 兄弟表示法和孩子链表表示法。84. 将数据元素2,4,6,8,10,12,14,16,18,20依次存于一个一维数组中，然后采用折半查找元素12,被比拟过的数组元素的下标依次为5, 7,6 。85. 图的深度优先遍历序列不是唯一的。86. 假设二叉树的一个叶子结点是某子树的 中根遍历序列中的第一个结点，那么它必是 该子树的后跟遍历中的第一个结点。87. 图的遍历是指从图中某一顶点出发访问图中全部顶点且使每一顶点仅被_ 访问一次。8

13、8. 在一个图中，所有顶点的度数之和等于所有边的数目的2倍。89. 由一棵二叉树的后序序列和中序序列可唯一确定这棵二叉树。90. 在有序表12,24,36,48,60,72,84 中二分查找关键字 72时所需进行的关键字 比拟次数为2。91. 设根结点的层数为0,定义树的高度为树中层数最大的结点的层数加 1,那么高度 为k的二叉树具有的结点数目，最少为 k, 最多为2k-1。92. 在直接插入排序、直接选择排序、分划 交换排序、堆排序中稳定的排序方法有直 接插入排序。93. 具有100个结点的完全二叉树的叶子 结点数为50。94. 普里姆Prim算法适用于边稠密图。95. 在有n个叶子结点的哈

14、夫曼树中，其结 点总数为2n-1。96. 将一棵树转换成一棵二叉树后，二叉树根结点没有右子树。97. 矩阵采用压缩存储是为了节省空间98. 假设连通网络上各边的权值均不相同，那么该图的最小生成树有1棵。99. 设无向图G的顶点数为n,那么要使 G连 通最少有n-1条边。100 .栈和队列的共同特点是插入和删除均在端点处进行。101 .克鲁斯卡尔Kruskar算法适用于边稀疏图。102. 假设连通图的顶点个数为n,那么该图的生成树的边数为 n-1。103. 图的存储结构最常用的有邻接矩阵和邻接表。104. 由一棵二叉树的前序序列和中序序列 可唯一确定这棵二叉树。105. 队列中允许进行插入的一端

15、称为队尾。106. 拓扑排序输出的顶点数小于有向图的 顶点数，那么该图一定存在环。107. 在有序表15,23,24,45,48,62,85 中二分查找关键词23时所需进行的关键词比拟次数为2。108 .树中所有结点的度等于所有结点数加-1 。109. 在一个具有n个顶点的完全无向图的 边数为nn-1/2。110. 用分划交换排序方法对包含有n个关键的序列进行排序，最坏情况下执行的时间杂度为On2111. 一棵高度为h假定树根结点的层号为0的完全二叉树中，所含结点个数不小于2h。112. 假设长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中数据元素的个数是n-i

16、。113. 在非空二叉树的中序遍历序列中，二 叉树的根结点的左边应该只有左子树上 的所有结点。114. 假设一棵二叉树具有 45个度为2的结 点，6个度为1的结点，那么度为0的结点 个数是46 。115. 在一个有向图中，所有顶点的入度之 和等于所有边数4倍。116. 设输入序列为A,B,C,D,借助一个栈不可以得到的输出序列是D,A,B,C 。117. 一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的起始地 址为100,那么该数组的首地址是70。118. 设abcdef以所给的次序进栈，假设在进栈操作时，允许退栈操作，那么下面得不到的 序列为cbdef 。119. 一般情况下，

17、将递归算法转换成等价的非递归算法应该设置堆栈 。120 .假设长度为n的非空线性表采用顺序存 储结构，删除表的第i个数据元素，i的合法值应该121.是C. 1 < i < n 。122 .假设某线性表中最常用的操作是取第i个元素和删除最后一个元素，那么采用什么 存储方123.式最节省时间顺序表。124 .一组记录的关键字为 45, 80, 55, 40,42, 85，那么利用堆排序的方法建立的初始 堆为85, 80, 55, 40, 42, 45。125. 设有6000个无序的元素，希望用最快 的速度挑选出其中前 5个最大的元素，最好选用堆排序法。126. 排序方法中，从未排序序列

18、中挑选元 素，将其放入已排序序列的一端的方法， 称为选择排序。127. 带头结点的单链表head为空的判断条件是head->next=NULL。128. 在一个单链表中，假设删除 *p结点的 后继结点，那么执行p->n ext=p->n ext- >n ext 。129. 在一棵具有n个结点的二叉树中，所 有结点的空子树个数等于n+1130. 有向图中，以顶点v为终点的边的数目，称为顶点v的入度。131. 假设频繁地对线性表进行插入和删除操 作，该线性表应该采用的存储结构是链 式。132. 设一个栈的输入序列是1，2，3，4,5, 那么以下序列中，是栈的合法输出序列的

19、是3 2 1 5 4。133. 有数据53，30，37，12 ,45, 24, 96，从空二叉树开始逐个插入数据来形成二叉 查找树，假设希望高度最小，那么应选择下面 输入序列是37,24,12,30,53,45,96。134 .二叉树的第I层上最多含有结点数为2I 。135. 稀疏矩阵一般采用的压缩存储方法为三元组表。136. 某二叉树的前序和后序序列正好相同，那么该二叉树一定是什么样的二叉树空或只有一个结点。137. 假设长度为n的线性表采用顺序存储结 构，在表的第i个位置插入一个数据元素， 需要移动表中元素的个数是 n-i+1 。138. 设有数组Ai,j，数组的每个元素长度为3字节，i的

20、值为1至U 8，j的值为 1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为BA+180。139. 二维数组 A56的每个元素占5个单元，将其按行优先顺序存储在起始地址 为3000的连续的内存单元中，那么元素A45的存储地址为3145 。140. 一个具有n个顶点的图采用邻接矩阵 表示，那么该矩阵的大小为n*n 。141. 假设字符串“ 1234567"采用链式存储， 假设每个字符占用 1个字节，每个指针占 用2个字节，那么该字符串的存储密度为33.3 %。142. 假设在一棵非空树中，某结点 A有3个 兄弟结点包括 A自身，B是A的双亲结 点

21、，那么B的度为3 。143. 设有三个元素 X，Y，Z顺序进栈进 的过程中允许出栈，以下得不到的出栈排 列是ZXY。144. 树形结构的特点是：一个结点可以有多个直接后继。145. 使具有30个顶点的无向图成为一个连通图至少应有边的条数是29。146. 使具有9个顶点的无向图成为一个连 通图至少应有边的条数是8。147. 在顺序表n足够大中进行顺序查找，其查找不成功的平均长度是n+1 148. 设树T的度为4，其中度为1，2，3 和4的结点个数分别为 4，2，1，1那么T 中的叶子数为8。149. 栈的插入和删除操作进行的位置在栈顶。150. 假设一棵二叉树具有 20个度为2的结 点，6个度为

22、1的结点，那么度为 0的结点 个数是21。151. 一棵线索二叉树的线索个数比链接个 数多2个。152. 在循环 链表中，从任何一结点出发都 能访问到表中的所有结点。153. 在n个结点的顺序表中插入一个结点 需平均移动n/2个结点。154. 循环队列的引入，目的是为了克服假 溢出 。155. 假设连通网络上各边的权值均不相同，那么该图的最小生成树有1棵。156. 二叉树的遍历方式有三种：先序遍历、中序遍历、后序遍历。157. 假设一棵二叉树有15个叶结点，那么该二 叉树中度为2的结的点个数为14。158. 设某二叉树的后序遍历序列为ABKCBPM那么可知该二叉树的根为M。159. 数据结构的

23、三个方面：数据的逻辑结 构、物理结构、运算。160. 每个结点只有一个链接域的链表叫做 单链表。161. 组成串的数据元素只能是字符。162. 具有n个结点的二叉树采用链接结构 存储，链表中存放 NULL指针域的个数为n+1。163. 在一个无向图中，所有顶点的度数之 和等于所有边数2倍。164设二叉树根结点的层次为0, 棵高度为h的满二叉树中的结点个数是2h+1-1。165. 将一棵有50个结点的完全二叉树按 层编号，那么对编号为 25的结点X,该结点 有左孩子，无右孩子 。166. 树或树形的定义是什么？答：一 个树或树形就是一个有限非空的结点 集合T,其中有一个特别标出的称为该树 之根r

24、oot T的结点；其余除根外 T点划分成m 丁个不相交集合1'' m,而且这些集合的每一个又都是树。167在图形结构中，每个结点的前驱结点 数和后续结点数可以有任意多个。16 8.什么是树的路径长度？答：树的路径 长度是指从根结点到树中每个叶结点的路 径长度之和。二、选择1. 假设某线性表中最常用的操作是取第i个元素和删除最后一个元素，那么采用什么存储方式最节省时间A。A.顺序表B.单链表C.双链表D.单循环链表2. 在下述的排序方法中，不属于内排序方 法的是C。A. 插入排序法B.选择排序法C.拓扑排序 法D.归并排序法3. 以下四个关键词序列中，不是堆的序列 为C。A. 0

25、5,23,16,68,94,72,71,73B. 05,16,23,68,94,72,71,73C. 05,23,16,73,94,72,71,68D. 05,23,16,68,73,71,72,944. 以下排序算法中，某一趟结束后未必能选出一个元素放其最终位置上的是D 。A. 堆排序B.冒泡排序C.快速排序D. 直接插入排序5. 用孩子兄弟链表表示一棵树，假设要找到 结点x的第5个孩子，只要先找到 x的第 一个孩子，然后D。A.从孩子域指针连续扫描5个结点即可B.从孩子域指针连续扫描4个结点即可C. 从兄弟域指针连续扫描5个结点即可D.从兄弟域指针连续扫描4个结点即可6. 链栈和顺序栈相比

26、，有一个较明显的优点是A。A.通常不会出现栈满的情况B.通常不会出现栈空的情况C插入操作更加方便D.删除操作更加方便7. 任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置C。A.肯定发生变化B.有时发生变化 C.肯定不发生变化D.无法确定8. 排序方法中，从未排序序列中挑选元素， 将其放入已排序序列的一端的方法，称为D。A.希尔排序B.冒泡排序C.插入排序D. 选择排序9. 堆是一种什么排序B。A.插入B.选择C.交换D.归并10. 以下排序方法中不稳定的排序是C。A.直接插入排序B.冒泡排序C.堆排序 D.归并排序11. 一个无向连通图的生成树是含有该连通图的全部顶点的A。A.

27、极小连通子图B.极大连通子图 C.极 小子图D.极大子图12. 如下陈述中正确的选项是 A 。A. 串是一种特殊的线性表 B.串的长度必须 大于零B. 串中元素只能是字母 D.空串就是空白串13. 快速排序不利于发挥其长处的情况是C。A 待排序数据量太大B待排序数据 相同值过多C待排序数据已根本有序D待排序数据值差过大14. 性表中采用折半查找法查找元素，该线性表必须满足C。A 元素按值有序B 采用顺序存储结构C 元素按值有序，且采用顺序存储结构D 元素按值有序，且采用链式存储结构15. r在排序前已按元素键值递增顺序排列，那么比拟次数较少的排序方法是A。A.直接插入排序B.快速排序C.归并排

28、序D.选择排序16. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时 间来看，通常递归过程比非递归过程BA.较快B.较慢 C .相同D.不确定17. 如果待排序序列中两个数据元素具有 相同的值，在排序后它们的位置发生颠倒， 那么称该排序是不稳定的。不稳定的排序方法是D。A.起泡排序 B .归并排序C.直 接插入法排序D .简单项选择择排序18. 将一棵有50个结点的完全二叉树按层编号，那么对编号为25的结点X,该结点B。 A.无左、右孩子B.有左孩子，无右孩子C. 有右孩子，无左孩子D.有左、右孩子19. 假设某链表最常用的操作是在最后一个 结点之后插入一个结点和删除最

29、后一个结点，那么采用那种存储方式最节省时间C。A.单链表B.双链表C.带头结点的双 循环链表D.单循环链表20. 以下排序算法中，第一趟排序完毕后, 其最大或最小元素一定在其最终位置上的 算法是D。A.归并排序B.直接插入排序C.快速 排序D.冒泡排序21. 树形结构最适合用来描述 C o A有 序的数据元素B无序的数据元素C数据元素之间具有层次关系的数据D数据元素之间没有关系的数据22. 设有7000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用方法是C。A.冒泡排序B.快速排序C.堆排序D.基数排序23.链表不具有的特点是(A)。A.可随机访问任一元素B.插入删除不需要

30、移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比24. 假设待排序对象序列在排序前已按其排 序码递增顺序排序，那么比拟次数最少的方 法排序是A oA.直接插入排序B .快速排序C.归并排序D .直接选择排序25. 以下关键字序列中是堆的序列为D。A. 16,72,31,23,94,53 B.94,23,31,72,16,53B. 16,53,23,94,31,72D.16,23,53,31,94,7226. 以下四个关键字序列中，那个序列不是 堆C oA. 05,23,16,68,94,72,71,73 B.05,16,23,68,94,72,71,73C. 05,23,16,7

31、3,94,72,71,68 D.05,23,16,68,73,71,72,9427. 下面4个序列中，满足堆的定义是 DoA. 13,27,49,76,76,38,85,97 B.C. 13,76,49,76,27,38,85,97 D.28. 采用线性探查法处理冲突所构成的散 列表上进行查找，可能要探测到多个位置， 在查找成功情况下，所探测的这些位置上 的键值D。A. 一定都是同义词B. 一定都不是同义词C.都相同D.不一定都是同义词29. 性表中采用折半查找法查找元素，该线性表必须满足C。A 元素按值有序B 采用顺序存储结构C 元素按值有序，且采用顺序存储结构D 元素按值有序，且采用链式存

32、储结构1. 对于一个队列，如果输入项序列由答：1,2,3,4 o2. 将表达式a+b *c+d - e+g*h答：后缀表达式为：ab+c*d+eg+h*-3. 对于一个栈，给出输入序列A, B,三、简答1,2,3,4所组成，试给出全部可能的输出序列。改写成后缀表达式。C,试给出全部可能的输出序列。答：解：输出序列为：ABC CBA,ACB,BAC,BCA4. 将算术表达式 a+b* c+d/e 转为后缀表达式。答：B . abcde/+*+5. 由权值为12, 6, 5, 9 ,10的五个叶子结点构造一棵哈夫曼树，请问该树的带权路径长度是多少? 答：权值为95 。6. 由二叉树的前序和后序遍历

33、序列能否唯一确定一棵二叉树。假设不能请举出反例。 答：不能唯一确定一棵二叉树。如以下图。厂、1122337.求出以下图所示有向图的邻接矩阵。答：有向图的邻接矩阵为:012340厂027OO1 J1OO0OOOOOO2OOOO05OO3OOOOOO0OO43OOOO40J8.有n个顶点的无向连通图至少有多少条边？有n个顶点的有向连通图至少有多少条边？答：有n个顶点的无向连通图至少有 n-1条边，有n个顶点的有向连通图至少有n条边。9 下面列举的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。试问， 哪些排序方法是稳定的？答：起泡排序，直接插入排序，归并排序是稳

34、定的。10. 为什么说树是一种非线性结构？树中的每个结点除了根结点外，其余每个结点有一个直接前驱，但有多个直接后继，所以说树是一种非线性结构。11. 一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A, B, C, D, E, F, G, H, I, J中序序列：C, B, A, F, E, D, I, H, J, G答：后序序列为： C, B, F, E, I, J, H, G, D, A12 试述顺序存储和链式存储的区别及各自的优缺点。答：数组占用连续的内存空间，链表不要求结点的空间连续。因此,1) 插入与删除操作：由于数组在插入与删除数据时需移动大量的数据元素，而链表只需要改

35、变一些指针的链接, 链表比数组易于实现数据的插入和删除操作。2) 内存空间的占用情况：因链表多了一个指针域，故较浪费空间，因此，在空间占用方面，数组优于链表。3) 数据的存取操作：访问链表中的结点必须从表头开始，是顺序的存取方式，而数组元素的访问是通过数组下标来实 现的，是随机存取方式，因此，在数据存取方面，数组优于链表。4) 数据的合并与别离：链表优于数组，因为只需要改变指针的指向13. 将表达式(a+b)-c*(d+e)-f)*(g+h)改写成后缀表达式。答：后缀表达式为：ab+cde+*-f-gh+*14. 将算术表达式 a*(b+c)-d 转为后缀表达式。答：abc+*d-15. 求出

36、以下图所示有向图的邻接表。答：有向图的邻接表为:V0V1AV2V3AMead12352° 341A34A116. 试找出中序序列和后序序列相同的所有二叉树。答：空树或缺右子树的单支树。17. 用邻接矩阵存储一个包含1000个顶点和1000条边的图，那么该图的邻接矩阵中有多少元素？有多少非零元素?答：该图的邻接矩阵中有 1000*1000个元素。该图的邻接矩阵中有2000个非零元素。18. 画出以下图中二叉树的顺序存储结构示意图。答：二叉树的顺序存储结构示意图为:15A14ABCD/+E*-。【1丨3丨 rrA0A2A619. 写出中缀表达式 A-(B+C/D)*E的后缀形式。 答：中

37、缀表达式 A-(B+C/D)*E的后缀形式是：20. 为什么用二叉树表示一般树？答：树的最直观表示是为树中结点设置指向子结点的指针域，对k叉树而言，每个结点除data域外，还有k个链接域。这样，对一个有n个结点的k叉树来说，共有n*k个指针域，其中n-1个不空，另外n(k-1)+1个指针域为空，因此， 空链接域的比例约为(k-1 ) /k ，于是导致大量的空间浪费。然而，如果采用二叉树表示一棵n个结点的树，那么树中共有2n个链接域，其中未用到的有n+1个，占所有指针域的比例约为1/2，空间浪费少很多。另外，因为任何树型结构都可以转换成二叉树，因此，通常用二叉树表示树型结构。21请指出一组权值(

38、7, 5, 2, 4)对应的哈夫曼树的带权路径长度。答：哈夫曼树的带权路径长度是35。22. 试找出前序序列和中序序列相同的所有二叉树。解答：空树或缺左子树的单支树。23. 完全二叉树用什么数据结构实现最适宜，为什么？答：完全二叉树用一维数组实现最适宜。因为完全二叉树保存在一维数组中时，数组内没有空洞，不存在空间浪费问 题；另外，顺序存储方式下，父子结点之间的关系可用公式描述，即父(或子)结点寻找子(或父)结点只需计 算一个公式，访问结点方便。但采用链表存储时就存在空间浪费问题，因为每个结点要另外保存两个链接域，并且寻 找结点也不容易。24. 求出以下图所示无向图的邻接矩阵。01230111精

39、选10 0 110 0 1答：无向图的邻接矩阵为:25. 请构造权值为 5 , 13, 21, 7, 18, 30, 41 的哈夫曼树。 答：哈夫曼树为：26. 我们已经知道，树的先根序列与其对应的二叉树的先根序列相同，树的后根序列与其对应的二叉树的中根序列相 同。那么利用树的先根遍历次序与后根遍历次序，能否唯一确定一棵树？请说明理由。答：能。因为树的先根序列与其对应的二叉树的先根序列相同，树的后根序列与其对应的二叉树的中根序列相同，而 二叉树的先根序列与二叉树的中根序列能唯一确定一棵二叉树，所以利用树的先根遍历次序与后根遍历次序，能唯一 确定一棵树。27. 请给出如以下图所示的权图的邻接矩阵

40、。0123 428.OOOOOOOOOOOOOOOOOO1OOOOOO5004求该二叉树的后序序列。中序序列：c, b, d, e, a, g, i , h, j , f 前序序列：a, b, c, d, e, f, g, h, i , j 答：该二叉树的后序序列为：c,e,d,b,i,j,h,g,f,a29.对半查找是否适合于以链接结构组织的表？ 答：对半查找不适合于以链接结构组织的表。30.请指出中序遍历二叉查找树的结点可以得到什么样的结点序列。 答：中序遍历二叉查找树的结点就可以得到从小到大排序的结点序列。 31把以下图中的森林转化为一棵二叉树。解答：森林转化成的二叉树如以下图。78精选

41、32. 指出一般树的存储结构有哪几种?答：树的存储结构有双亲表示法、孩子链表表示法和孩子兄弟表示法33. 试找出前序序列和后序序列相同的所有二叉树。答：空树或只有根结点的二叉树。34. 线性表有两种存储结构：一是顺序表，二是链表。试问：如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？答：选链式存储结构。它可动态申请内存空间，不受表长度(即表中元素个数)的影响，插入、删除时间复杂度为35. 求出以下图所示无向图的邻接表。答：无向图的邻接表为:V0V1V2V33A2AHead36. 一个图如下所示，假设从顶点0出发

42、求出其广度优先搜索序列。解答：广度优先搜索序列：0123456737. 一组记录的关键字为 (52, 56, 26, 12, 69, 85, 33, 48, 70)，给出快速排序的过程。解答：解：52, 56, 26, 12, 69, 85, 33, 48, 70第一趟排序33, 48, 26, 12, 52, 85, 69, 56, 70第二趟排序26, 12, 33, 4.52, 69, 56, 70, 85第三趟排序12,26,33, 48,_52,_56,70, 69, 85第四趟排序12,26,33, 4L52卫6,血 69,85第五趟排序12,26,33, 452卫6,屯 69,8

43、5 38. 下面列举的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。试问, 哪些排序方法是稳定的？起泡排序，直接插入排序，归并排序是稳定的。39. 一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, F, E, D, I, H, J, G 答：后序序列为:C, B, F, E, I, J, H, G, D, A40. 把以下图中的二叉树转化成森林。答案:41. 给定表(43,36,56,6,64,32,8,41),按数据元素在表中的次序构造一棵二叉查找树，并求其平

44、均查找长度。解答：根据给定表(43,36,56,6,64,32,8,41)，构造的二叉查找树如以下图；其平均查找长度为：23/8。42. 将以下图中的二叉树，转换成相应的森林。答：森林转化成的二叉树如以下图。DCBGEAHFIJK按后根遍历所得到的结点序列为DCEGBFHKJI，画出该43. 知二叉树按中根遍历所得到的结点序列为 树形结构，并按中根遍历序列进行线索化答：44. 对于以下图所示的二叉树，试分别写出先根遍历、中根遍历该树所得到的先根序列、中根序列。EICFJBGDKHLA答：先根遍历的结点序列：ABCEIFJDGHK，中遍历的结点序列:46.把以下图中的二叉树转化成森林。1，给出快

45、速排序的过程。47. 一组记录的关键字为 (52, 56, 26, 12, 69, 85, 33, 48, 70)解答：解：52, 56, 26, 12, 69, 85, 33, 48, 70第一趟排序33, 48, 26, 12, 52, 85, 69, 56, 70第二趟排序 26, 12, 33, 4玄52, 69, 56, 70, 85第三趟排序 12, 26, 33, 452卫6,屯 69, 85 第四趟排序 12, 26, 33, 4却2卫6,卫69,85 第五趟排序 12, 26, 33, 48, 52, 56, 70, 69, 8548.设记录的关键字集合 key=51,28,

46、38,86,70,90,7,30,40,251)时，各趟排序结束后的结果。 解答：各趟排序结束后的结果。初始状态：51 28388670 90 7304025第一趟排序(d=5):5173040259028388670第二趟排序(d=3):2873040258651389070第三趟排序(d=1):7252830384051708690，试写出对key进行渐减增量排序增量d = 5 , 3,49.有一棵二叉树如以下图所示，分别指出其前序、中序遍历的结点序列。答：它的前序序列为：ABCDEFGHIJ它的中序序列为：CDBAFGEIH。50.8个记录，对应的关键词为：25,84,21,47,15,

47、27,68,35,20写出快速排序的第一趟排序过程图示。答：初始键值序列25 84 21 47 15 27 68 35 20第一次交换25 84 21 47 15 27 68 35 20门=2 门=9第二次交换25 20 21 47 15 27 68 35 84i J f j扫描交叉25 20 21 15 47 27 68 35 84j f iRn与 R 互换25 20 21 15 47 27 68 35 84Rm fj.f分划表 15 20 21 25 47 27 68 35 8451.给定表(40,9,56,6,39,73,8,23),按数据元素在表中的次序构造一棵二叉查找树。答：二叉排序

48、树如下。CBAEDF试画出该二叉树。答：二叉查找树如下，平均查找长度为),按数据元素在表中的次序构造一棵二叉查找树，并求其平均查找长度。3。53. 根据以下图给出的二叉树，求出先序、中序遍历的结点序列。答：先序遍历为：abdcef，并给出堆(D)第3次交换8'.3241：(50) (56)(79 蠢中序遍历为：dbaefc54. 一组记录的关键字为(50, 79, 8, 56, 32, 41, 85),给出利用重建堆方法建立的初始堆(堆顶最大)排序的过程。答：1) 建立的初始堆为：85 , 79, 50, 56, 32, 41, 82 )堆排序的过程如下：(g)第6次交换55. 答：把

49、以下森林转化为56.数据序列为12,5,9,20,6,31,24，对该数据序列进行排序，试写出冒泡排序每趟的结果。答：初始键值序列第一趟排序5第二趟排序5第三趟排序5第四趟排序512 5 9 20 6 31 249 12 6 20 24 319 6 12 20 24 319 6 12 20 24 316 9 12 20 24 3157.给定表40,36,55,6,64,77,9,41),按数据元素在表中的次序构造一棵二叉查找树，并求其平均查找长度。答：森林转化成的二叉树如以下图。答：构造的二叉查找树如以下图，其平均查找长度为11/4。58. 对于以下图所示的二叉树，试分别写出先根遍历、中根遍历

50、和后根遍历该树所得到的先根序列、中根序列和后根序 列。解答：先根遍历的结点序列：ABCEIFJDGHKL中遍历的结点序列：EICFJBGDKHLA后根遍历的结点序列：IEJFCGKLHDBA59. 数据序列为12,5,9,20,6,31,24，对该数据序列进行排序，试写出归并排序每趟的结果。解答：初始键值序列 12 5 9 20 6 31 24第一趟排序5 12 9 20 6 31 24第二趟排序59 1220 6 2431第三趟排序56912 20 2431()中，用二分法查找关键词 36,进行多少次比拟后查找成功?60. 序表(5, 12, 17, 19, 23, 25, 30, 36,

51、45, 49, 58) 写出查找过程。解答：经过4次比拟查找成功。查找过程如下：5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58i=11m=61 j=115, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58 t f I i=7m=9j=11(B)第2次与45进行比拟(A)第1次与25进行比拟5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 585, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58i=7 j=8tm=7(C)第3次与30进行比拟i=8I i j=8m=8(D)

52、第4次与36进行比拟61. 一组记录的关键字为 (52, 56, 26, 12, 69, 85, 33, 48, 70)解答：52, 56, 26, 12, 69, 85, 33, 48, 70，给出快速排序的过程。第一趟排序33,48,26, 12, 52, 85,险 56,70第二趟排序26,12,33, 4玄52, 69,56, 70,85第三趟排序12,26,33, 4L52臣6,70. 69,85第四趟排序 12, 26, 33, 48526,卫 69,85第五趟排序12, 26, 33, 48, 52, 56, 70, 69, 8562. 某二叉树的后序序列为：ABCDEFG中序序列为：ACBGEDf给出它的前序序列。解：它的前序序列为： GCABFED63. 根据以下图给出的二叉树，求出中序和后序遍历的结点序列。ce解答0643解答4536566432406