许昌学院数据结构试题库.pdf

1、 数据结构概念 1. 相互之间存在一种或多种特定关系的数据元素的集合，逻辑结构， 存储结构 2. 线性，树，图 3. 数据结构S中：元素的集合为：A，B，C，D，E，F，G，H，I，关 系的集合为：， ，则S的逻辑结构为（ ） （A） 集合 （B）线性 (C) 树 (D)图 4. 数据元素之间存在一对多关系的数据结构是（ ） （A）线性表 （B）队列 (C)二叉树 (D)AOV-网 5. 以下数据结构中，属于线性结构的有（ ） （A） 线性表 （B） 树 (C) 二叉树 (D) 图 6. 存储结构是逻辑结构在计算机中的实现。( ) 7. 非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。 ( ) 8. 非空线性表中任意一个数据元素都有且仅有一个直接后继元素。 ( ) 9. 顺序存储结构只能用来存放线性结构；链式存储结构只能存放非线 性结构。 ( ) 10. 算法就是程序。 ( ) 11. 一种逻辑结构可以采用不同的存储方式存放在计算机中。 ( ) 2、 线性表 12. 前驱，前驱，后继，后继 13. 地址连续，一定相邻，不一定相邻 14. 一定相邻，不一定相邻 15. 一半，表长和插入或删除位置。 16. 链式 17. 指针 18. 空值（NULL），头结点 19. s-next=p-next p-next=s 20. b+(i-1)*k 21. p-next = s-next , s 22. L-dataj-1= L-dataj; L-last+ 23. L-dataj-1=L-dataj 24. 下列有关线性表的叙述中，正确的是（ ）。 (A)一个线性表是n个数据元素的有限序列 (B)线性表中任何一个元素有且仅有一 个直接前驱 (C)线性表中任何一个元素有且仅有一个直接后继 (D)以上说法都不正确 25. 顺序表是线性表的（ ）。 (A)链式存储结构 (B) 顺序存储结构 (C) 索引存储结构 (D) 散列存储结构 26. 从一个长度为n的顺序表中删除第i个元素(1in)时,需向前移动 （ ）个元素。 (A)n-i (B)n-i+1 (C)n-i- 1 (D)i 27. 一个长度为n的顺序表中第i个位置上插入新元素(1in+1)时,需 向后移动（ ）个元素。 (A)n-i (B)n-i+1 (C)n-i- 1 (D)i 28. 下面的定义是（ ）。 typedef struct node int data ; struct node * next ; linklist; (A)顺序表 (B)单链表 (C)双向链表 (D)二叉链表 29. 下面的定义是（ ）。 typedef struct int dataMaxsize ; int last ; seqlist; (A)顺序表 (B)单链表 (C)静态链表 (D)循环队列 30. 单链表的一个存储结点包含（ ）。 (A)数据域或指针域 (B)指针域或链域 (C)指针域和链域 (D)数据域和链域 31. 单链表中，增加头结点的目的是为了（ ）。 (A)使单链表至少有一个结点 (B) 标示表结点中首结点的位置 (C)方便运算的实现 (D)说明单链表是线性表的链式存储实现 32. 对于单链表表示法，以下说法错误的是（ ）。 (A)指向链表的第一个结点的指针，称为头指针 (B)单链表的每一个结点都被一个指针所指 (C)终端结点的指针域就为NULL (D)尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表 33. 有一个含头结点的单链表，头指针为head，则判断其是否为空的条 件是（ ）。 (A) head = = NULL (B) head-next = = NULL (C) head-next = = head (D) head != NULL 34. 在带头结点的非空单链表H中，指针p指向某的结点，求p结点的前 驱结点指针q的算法是（ B ）。 (A)q=H ; while(q!=p) q=q-next; (B) q=H ; while(q-next!=p) q=q-next; (C) q=H-next ; while(q!=p) q=q-next; (D) q=H-next ; while(q-next!=p) q=q- next; 35. 在带头结点的单链表H中，求单链表长度len的算法是（ A ）。 (A) len=0,p=H ; while(p-next!=NULL) len + ; p=p-next; (B) len=0,p=H-next ; while(p-next!=NULL) len + ; p=p-next; (C) len=1,p=H ; while(p!=NULL) p=p-next; len + ; (D) len=1,p=H-next ; while(p-next!=NULL) p=p-next; len + ; 36. 假设指针p指向单链表中的某一结点,s为某结点指针，则在p指针后 面插入结点s的操作是（ ）。 (A) p-next=s;s=p-next; (B)p-next=s;s-next=p-next; (C) s-next=p-next;p-next=s; (D)s-next=p;p-next=s; 37. 假设指针p指向单链表中的某一结点,s为某结点指针，则在p指针前 面插入结点s的操作是（ ）。描述错误，无参考答案 (A) s-next=p-next;p-next=s; (B)p-next=s; s-next=p-next; (C) p-next=s ; s=p-next; (D)s-next=p ; p-next=s; 38. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的 语句是（ ）。 (A)p=p-next; (B)p-next =p-next -next ; (C)p-next =p; (D)p=p- next-next; 39. 某线性表中最常用的操作是存取序号为i的元素及其前驱的值，可 采用的存储的方式是（ ）。 (A)顺序表 (B)单向链表 (C)双向循环链表 (D)单向循环链表 40. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结 构为（ ）。 (A)顺序表 (B)用头指针表示的单循环链表 (C)用尾指针表示的单循环链表 (D)单 链表 41. 在单链表中，头结点是必不可少的。( 错 ) 42. 在单链表中，头结点的作用是简化运算。( 对 ) 43. 在线性表的顺序存储结构中，逻辑上相邻的数据元素在物理位置上 也是相邻的。( 对 ) 44. 在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上 也是相邻的。( 错 ) 45. 只要内存足够大，采用链式存储结构的线性表长度不受限制。( 对 ) 3、 栈和队列 46. 栈，队列 47. 后进先出（LIFO），先进先出（FIFO） 48. 先进先出（FIFO） 49. 后进先出（LIFO）,Elemtype dataMaxsize ,int top; 50. sp-top+; sp-datasp-top=x; 51. 先进先出（FIFO），front = (rear+1)%Maxsize 52. 顺序 53. front = (rear+1)%Maxsize 54. sp-datasp-top；sp-top-; 55. 栈操作的原则是（ ）。 (A)先进先出 (B)后进先出 (C)栈顶插入 (D) 栈顶删除 56. 栈的两种常用存储结构分别为 (A)顺序存储结构和链式存储结构 (B)顺序存储结构和散列存储结构 (C)链式存储结构和索引存储结构 (D)链式存储结构和散列存储结构 57. 有一栈，元素A，B，C，D依次进栈 ,则以下出栈序列中不可能得到 的是（ ）。 (A) D、C、B、A (B) C、B、A、D (C) A、B、C、D (D) D、C、A、B 58. 一个栈的入栈序列是A,B,C,D,E,则不可能的出栈序列是（ ）。 (A)EDCBA (B)DECBA (C)DCEAB (D)ABCDE 59. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不 同排列个数为 1 2 3 4 5 图 (A)4 (B)5 (C)6 (D)7 60. 循环队列是队列的（ ）。 (A)顺序存储结构（B）链式存储结构(C)索引存储结构(D)散列存储结构 61. 设循环队列中数组的下标范围是1n，其头尾指针分别是f、r，则 队列中元素个数为（ ）。 (A)r - f (B)r f + 1 (C)(r f + 1)mod n (D)( r f + n ) mod n 62. 在循环队列中(少用一个存储空间)，队满的条件是（ ）。 (A)(rear+1)%maxsize=front (B)raer=front (C)(front+1)%maxsize=rear (D)rear=0 63. 循环队列的队满条件为（ ）。 (A) (sq.rear+1) % mazsize =(sq.front+1) % maxsize; (B) (sq.rear+1) % maxsize =sq.front+1 (C) sq.(rear+1) % maxsize =sq.front (D) sq.rear =sq.front 64. 设数组datam作为循环队列SQ的存储空间，front为头指针，rear 为尾指针，执行出队操作,其头指针的值为（ ）。 (A) front=front+1 (B) front=(front+1)%(m-1) (C) front=(front-1)%m (D) front= (front+1)%m 65. 栈和队列与线性表的逻辑结构相同。( 对 ) 66. 栈只能在栈顶进行插入和删除。( 对 ) 67. 队列只能在队首进行删除，在队尾进行插入。( 对 ) 68. 队列只能在队尾进行删除，在队首进行插入。( 错 ) 4、 字符串，数组，广义表 69. 顺序，行，列 70. LOC(a1)+（i-1）*K 71. 2358，2220 11 15 m = 6 n = 6 t = 9 14 91 22 11 32 3 36 28 41 22 43 -6 61 -15 63 28 72. 1126，1192 73. n*(n+1)/2 74. 42 75. 稀疏矩阵，顺序 76. 5 77. (b) 78. 3 79. (a,b) 80. 81. 串是（ ）。 (A)一些符号构成的序列 (B)有限个字母构成的序列 (C)一个以上的字符构成的序列 (D)有限个字符构成的序列 82. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的 子串，函数Scopy(s,t)的功能为复制串t到s。若字符串 S=“SCIENCESTUDY”，则调用函数Scopy(P,Sub(S,1,7)后得到（ ）。 (A)P=“SCIENCE” (B)P=“STUDY” (C)S=“SCIENCE ” (D)S=“STUDY” 83. 设有一个二维数组A68,假设A00存放位置在1000,每个元素 占6个空间，按行优先存储，则A36的存储位置是 (A)1180 (B)1126 (C)126 (D)180 84. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第 五个元素的地址是_。 (A)110 (B)108 (C)100 (D)120 85. 为了节省存储空间，将n阶对称矩阵A(下标从1开始)中包括主对角 线元素在内的下三角部分的所有元素按照行序为主序方式存放在一 维数组B1:n(n+1)/2中，对任意下三角部分的元素aij(ij)在数 组B的下标k是_。 (A)i(i-1)/2+j-1 (B)i(i-1)/2+j (C)i(i+1)/2+j-1 (D)i(i+1)/2+j 86. 基于三元组的稀疏矩阵，对每个非零元素aij,可以用一个（ ） 唯一确定。 (A)非零元素 (B)三元组(i,j,aij) (C) aij (D) i,j 87. 广义表A=(),(a),(b,(c,(D)的长度为_。 (A)2 (B)3 (C)4 (D)5 88. 空串与由空格组成的串没有区别。( 错 ) 89. 对称矩阵的压缩存储是指对矩阵中的值相同的元素只分配一个存储 空间。(对 ) 90. 对称矩阵的压缩存储是指对矩阵中的规律元素只分配一个存储空 间。( 对 ) 91. N阶下三角矩阵压缩存储需要n*(n+1)/2个存储空间。( 对 ) 92. 三元组表是稀疏矩阵的顺序存储结构。( 对 ) 5、 树型结构： 93. 2i-1 94. 2k-1 95. n0= n2+1 96. 2i ，2i+1 97. 31 98. 2h-1 99. n/2 1 n n/2+1 100. n+1 101. 顺序，二叉链表 102. 后序：DEBFCA 103. Inorder(root-Lchild); Visit(root-data); Inorder(root-Rchild); 104. 请对给定的二叉树的存储结构，将二叉树的先序遍历输出结点递归 算法补充完整： Visit(root-data); preorder (root-Lchild); preorder (root-Rchild); 105. count=0 countleaf(t-rchild, 106. 最短，较近。 107. 2m-1 108. 33 109. 按照二叉树的定义，具有3个结点的二叉树有_种形态。 (A)3 (B)4 (C)5 (D)6 110. 3个结点可构成（ ）个不同形态的二叉树。 (A)2 B 3 C 4 D 5 111. 二叉树是非线性数据结构，它（ ）。 (A)不能用顺序存储结构存储; (B)不能用链式存储结构存储; (C)顺序存储结构和链式存储结构都能存储; (D)顺序存储结构和链式存储结构都不能使用 112. 下列陈述中正确的是（ ）。 (A)二叉树是度为2的树 (B)二叉树中结点只有一个孩子时无左右之分 (C)二叉树中必有度为2的结点 (D)二叉树中最多只有两棵子树，并且有左右之分 113. 设有一棵22个结点的完全二叉树，那么整棵二叉树有（ ）个度 为0的结点? (A)6 (B)7 (C)8 (D)11 114. 某非空二叉树共有叶结点15个，没有度为1的结点，则该树共有（ ）个结点。 (A)29 (B)28 (C)27 (D)不能确定 115. 已知完全二叉树有26个结点，则整棵二叉树有（ ）个度为1的结 点？ (A)1 (B)0 (C)2 (D)不确定 116. 将一棵有50个结点的完全二叉树编号，根结点为1，每层从左到右 依次编号，则编号为49的结点的双亲结点的编号是（ ）。 (A)23 (B) 24 (C) 25 (D)26 117. 对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编 号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编 号，则可采用（ ）方法实现编号。 (A) 前序遍历 (B) 中序遍历 (C) 后序遍历 (D) 从根开始进行层次遍历 118. 一棵二叉树有n个结点，要按某顺序对该二叉树中的结点编号， （号码为1-n），编号须具有如下性质：二叉树中任一结点V，其编 号等于其左子树中结点的最大编号加1。而其右子树中结点的最小 编号等于V的编号加1。试问应按（ ）遍历顺序编号。 F E D B A C 图 (A)前根 B中根 C后根 D层次 119. 已给如图的二叉树，它的中序遍历序列是（ ）。 (A)ABECDF (B)ABCDEF (C)CBDAEF (D)CDBFEA 120. 某二叉树的中序遍历为：BDAEC，后序遍历为：DBECA，则前序遍历 为（ ）。 (A)ABDCE (B)ADBCE (C)ABDEC (D)BDACE 121. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列 为（ ）。 (A)DEBAFC (B)DEFBCA (C)DEBCFA (D)DEBFCA 122. 在有n个叶子结点的哈夫曼树中，其结点总数为（ ）。 (A)不确定 (B)2n (C)2n+1 (D) 2n-1 123. 哈夫曼树的带权路径长度是（ ）。 (A) 所有结点权值之和 (B) 所有叶结点带权路径长度之和 (C) 权结点的值 (D) 除根以外所有结点权值之和 124. 下列说法正确的是（ ）。 (A) 树的先根遍历序列与其对应的二叉树的先根遍历序列相同 (B) 树的先根遍历序列与其对应的二叉树的后根遍历序列相同 (C) 树的后根遍历序列与其对应的二叉树的先根遍历序列相同 (D) 树的后根遍历序列与其对应的二叉树的后根遍历序列相同 125. 对于一棵任意二叉树，若叶子结点数为n0，度为2的结点个数为 n2，则有n2= n0+1。( 错 ) 126. 对于一棵任意二叉树，若叶子结点数为n0，度为2的结点个数为 n2，则有n0= n2+1。( 对 ) 127. 深度为n的非空二叉树的第i层最多有2n-1 个结点。( 错 ) 128. 非空二叉树的第i层最多有2i-1 个结点。( 错 ) 129. 二叉树中，任何一个结点的度为2。( 错 ) 130. 二叉树中每个结点的两棵子树是有序的。( 对 ) 131. 具有12个结点的完全二叉树有4层深。( 对 ) 132. 具有12个结点的完全二叉树有5个度为2的结点。( 对 ) 133. 线索二叉树是在二叉树的所有结点的存储结构中增加先驱和后继指 针得到的。( 错 ) 134. 已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉 树。( 对 ) 135. 已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉 树。( 错 ) 136. 哈夫曼树中不存在度为1的分支结点。( 对 ) 137. 有n个叶子结点的哈夫曼树共有2n-1个结点。( 对 ) 6、 图型结构： 138. 连通 139. 邻接矩阵和邻接表 140. 深度，广度 141. 123456，123564 142. n-1 143. 出 144. 入 145. 对称；第i行或第i列的非零元素个数；邻接表的长度 146. 一个具有n个顶点的简单无向图最多（ ）条边。 (A)n (B)n(n-1) (C)n(n-1)/2 (D)2n 147. 有8个结点的无向连通图最少有（ ）条边。 (A)5 (B) 6 (C)7 (D)8 148. 一个具有n个顶点的无向完全图的边数为 (A) n(n+1)/2 (B) n(n-1)/2 (C) n(n-1) (D) n(n+1) b a d c e f 图 149. 任何一个带权的无向连通图的最小生成树 (A)只有一棵 (B)有一棵或多棵 (C)一定有多棵 (D) 可能不存在 150. 已知一个有向图，则从顶点a出发进行深度优先遍历，不可能得 到的DFS序列为 (A) a d b e f c B .a d c e f b C .a d c b f e (D) a d e f c b 151. 对下图1所示的带权有向图，从顶点1到5 的最短路径为（ ）。 (A)1,4,5 (B)1,2,3,5 (C)1,4,3,5 (D)1,2,4,3,5 5 1 2 3 4 图 152. 已给图，哪一项是该图的拓扑排序？ (A)1，2，3，4，5 (B)1，3，2，4，5 (C)1，2，4，3，5 (D)1，2，3，5，4 153. 某有向图由m个顶点和n条边组成，使用邻接表进行存储，则该邻接 表由m个头结点和n个表结点组成。( 对 ) 154. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的 存储空间大小只与图中结点个数有关，而与图的边数无关。( 对 ) 155. 有n个结点的无向完全图有n*(n-1)/2条边。( 对 ) 156. 有n个结点的有向完全图有n*(n-1)/2条边。( 错 ) 157. 某无向图由m个顶点和n条边组成，使用邻接表进行存储，则该邻接 表由m个头结点和n个表结点组成。(错 ) 158. 有向图中所有顶点的入度之和等于所有顶点的出度之和。( 对 ) 159. 普里姆算法是采用“加边法”构造最小生成树的。( 错 ) 160. AOE 网是一种带权的无环连通图。( 错 ) 161. AOE 网是一种带权的有向无环图。( 对 ) 162. AOE网所表示的工程至少所需要的时间等于从源点到汇点的最长路 径长度。( 对 ) 163. AOE网来表示工程计划时，从源点到汇点的最短路径表示了关键路 径。( 错 ) 164. AOV网的拓扑序列是唯一的。( 错 ) 165. 带权连通图的最小生成树的权值之和是它的生成树的权值之和中最 小的。( 对 ) 166. 带权连通图的最小生成树的权值之和一定小于它的其它生成树的权 值之和。( 对 ) 167. 迪杰斯特拉（Dijkstra）算法是按照最短路径长度递增的顺序产生 所有的最短路径。( 对 ) 7、 查找排序 168. 顺序， 有序 169. 顺序 170. 小 171. 升序 172. 在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11， 16，2，13，9，21，4，所得到的二叉排序树是【 】。自己画画 173. 5 174. 结点的左子树深度与右子树深度之差 -1，0，1 175. 哈希函数、处理冲突的方法、哈希表的装填因子。哈希表中元素个 数/哈希表的长度 176. 在数值无规律的线性表中进行检索的方法是【顺序查找 】 。 177. 内，外 178. 比较，移动 179. 35，14，35，48，55，77，62，98 180. 27 38 13 49 76 97 65 181. 设有散列函数H(k)=k mod 13散列表为T012，用线性探测再散 列。假定在某一时刻T的状态为： T:012345 8085 182. 下一个被插入的关键码是42，其插入的位置是: 【 4 】。 183. 请将直接选择排序算法补充完整： void SelectSort(RecordType R,int length) n = length; for(i=1;i=【 n-1 】;i+) k=【 i 】; for(j=i+1;j=n;j+) if(Rj.key Rk.key ) k=【 j 】; if (【 k!=i 】) x=Ri;Ri=Rk;Rk=x; 184. 以下简单选择排序算法，请将算法补充完整: void SelectSort(RecordType R , int length) n=length; for ( i=1 ; i= n-1 ; i+) ; for ( j=i+1; j=n ; j+ ) if ( Rj.key R .key ) k=j; if (k!=i) x=Ri ; Ri=Rk ; Rk=x; 见183题 185. 以下是直接选择排序的算法。请分析算法，并在横线上填充适当的 语句。 void select(seqlist r,int n) for(i=1;i=【 】;i+)/*每次循环，选择出一 个最小键值*/ k=i; for(j=i+1;j=n;j+) if(rj.keyrk.key) 【 】; if(【 】)swap(rk,ri）;/*函数 swap(rk,ri）交换rk和ri的位置*/ 见183题 186. 以下为直接插入排序的算法。请分析算法，并在_上填充适 当的语句。 void straightsort(seqlist r,int n) for(i=【 2 】;i=n;i+) r0=ri; j=i-1; while(r0.keyrj.key) rj+1= 【 rj 】; j-; rj+1= 【 r0 】; 187. 直接插入排序的基本操作是：将第i个记录插入到前i-1个已排好序 的记录中。请将如下的直接插入排序算法补充完整： void InsSort ( RecordType R , int length) for(i=2 ; i=length ; i+) R0= 【 】; for(j = i-1; 【 】; j-) Rj+1=Rj ; R【 】=R0; 见186题 188. 请将如下的折半查找算法补充完整： int BinSrch （SqList L, KeyType k） low=1 ; high=L.length;/*置区间初值*/ while( low=high) mid=【 】; if (k= =L.rmid. key) return（mid）; else if (【 】) high=mid-1; else 【 】; return (0);见189题 189. 如下算法是折半查找算法，请将算法补充完整： typedef struct KeyType key; OtherType other_data; RecordType; typedef struct RecordType rMaxsize; int length; RecordList; int BinSrch (RecordList L,KeyType k) Low=1; High= n-1 ; while ( low=high ) mid = (Low + High)/2; if ( k= L.rmid.key) return (mid); else if ( k L.rmid.key) highmid-1 ; else Low=mid+1; return (0); 190. 如下算法是设置监视哨的顺序查找法，请将算法补充完整: typedef struct KeyType key; OtherType other_data; RecordType; typedef struct RecordType rMaxsize; int length; RecordList; int SeqSearch(RecordList L,KeyType k) L.data0.key =k; i=L.length; while(L.ri.key!= k ) i-; return( i ); 191. 单链表适用于( )查找 (A)顺序查找 (B)折半查找 (C)顺序查找，也能折半查找 (D)随机 192. 对12个记录的有序表作折半查找，当查找失败时，最多需要比较（ ） 次关键字。 (A)3 (B)4 (C)5 (D) 6 193. 对线性表进行二分查找时，要求线性表必须（ ）。 (A)以顺序方式存储 (B)以链接方式存储 (C)以顺序方式存储，且数据元素有序 (D)以链接方式存储，且数据方式有 序 194. 在关键字序列（12，23，34，45，56，67，78，89，91）中二分查 找关键字为45，89和12的结点时，所需进行的比较次数分别为（ ）。 (A)4，4，3 (B)4， 3， 3 (C)3，4，4 (D)3，3，4 195. 设有序表的关键字序列为1，4，6，10，18，35，42，53，67， 71，78，84，92，99，当用二分查找法查找健值为84的结点时， 经（ ）次比较后查找成功。 (A) 2 (B) 3 (C) 4 (D) 12 196. 在有11个关键字的有序表中进行折半查找，查找成功时的最少比较 次数和最多比较次数分别是（ A ）。 (A) 1和4 (B) 3和4 (C) 1和3 (D) 4和5 197. 在有11个关键字的有序表中进行折半查找，查找失败时的最少比较 次数和最多比较次数分别是（ B ）。 (A) 1和4 (B) 3和4 (C) 1和3 (D) 4和5 198. 在索引顺序表中查找一个元素，可用的且最快的方法是（ ）。 (A)用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 (B)用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 (C)用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 (D)用二分查找法确定元素所在块，再用二分查找法在相应块中查找 199. 已知含10个结点的二叉排序树是一棵完全二叉树，该二叉排序树在 等概率情况下查找成功的平均查找长度等于（ ）。 (A)1.0 (B)2.9 (C)3.4 (D)5.5 200. 适于对动态查找表进行高效率查找的组织结构是（ ）。 (A)有序表 (B)分块有序表 (C)二叉排序树 (D) 线性链表 201. 一组记录得关键字为（46，79，56，38，40，84），以第一个记录 为基准利用快速排序的方法，一次划分结果是（ ）。 (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 202. 已知一组关键字为25，48，36，72，79，82，23，40，16，35， 其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的 结果是（ ）。 (A)25，36，48，72，23，40，79，82，16，35 (B)25，36，48，72，16，23，40，79，82，35 (C)25，36，48，72，16，23，35，40，79，82 (D)16，23，25，35，36，40，48，72，79，82 203. 已知一组关键字为25，48，36，72，79，82，23，40，16，35， 进行一趟基数排序的结果是（ ）。 (A)25，36，48，72，23，40，79，82，16，35 (B)40，72，82，23，25，35，36，16，48，79 (C)16，25，23，36，35，48，40，72，79，82 (D)16，23，25，35，36，40，48，72，79，82 204. 已知一组关键字为25，48，36，72，79，82，23，40，16，35， 进行一趟冒泡排序的结果是（ ）。 (A)25，36，48，72，79，23，40，16，35，82 (B)25，48，36，72，79，82，23，40，16，35 (C)23，25，36，48，40，16，35，72，79，82 (D)16，23，25，35，36，40，48，72，79，82 205. 已知一组关键字为25，48，36，72，79，82，23，40，16，35， 进行堆排序时，初始建大根堆的结果是（ ）。 (A)25，36，48，72，79，23，40，16，35，82 (B)82，79，36，72，49，25，23，40，16，35 (C)82，79，25，72，49，36，23，40，16，35 (D)82，49，36，72，79，25，23，40，16，35 206. 用某种排序方法对关键字序列（25，84，21，47，15，27，68， 35，20）进行排序时，序列的变化情况如下，则所采用的排序方法 是 （ ）。 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 (A)选择排序 (B)希尔排序 (C)归并排序 (D)快速排序 207. 插入排序在（ ）情况下效率最高。 (A)被排序的数据中有多个相同的数据元素 (B)被排序的数据已基本有序 (C)被排序的数据完全无序 (D)被排序的数据中最大值和最小 值相差悬殊 208. 下列排序算法中，在初始数据有序时，花费的时间反而最多是（ ）。 (A)堆排序 (B)冒泡排序 (C)快速排序 (D)希尔排序 209. 从未排序序列中选择一个元素，该元素将未排序序列分成前后两个 部分，前一部分中所有元素都小于等于所选元素。后一部分中所有 元素都大于等于所选元素，而所选元素处在排序的最终位置。这种 排序方法称为（ ）排序法。 (A)插入排序 (B)希尔排序 (C)快速排序 (D)堆排序 210. 快速排序在（ ）情况下效率最高。 (A)被排序的数据中有多个相同的数据元素 (B)被排序的数据已基本有序 (C)被排序的数据完全无序 (D)被排序的数据中最大值和最小 值相差悬殊 211. 在下列方法中，排序所花时间不受初始数据排列特征影响的算法是 （ ）？ (A)直接插入排序 (B) 简单选择排序 (C) 快速排序 (D)都不是 212. 直接插入排序的算法复杂性是（ ）。？ (A)O（n2） (B) O（nlogn） (C) O(n) (D) O(logn) 213. 用单链表表示的有序表可以使用折半查找方法来提高查找速度。( 错 ) 214. 折半查找方法适用于按值有序的线性链表的查找。( 错 ) 215. 折半查找方法适用于按值有序的顺序链表的查找。( 对 ) 216. 非空二叉排序树的任意一棵子树也是二叉排序树。( 对 ) 217. 哈希表的查找效率主要取决于所选择的哈希函数与处理冲突的方法 和装填因子。( 对 ) 218. 内部排序是指排序过程在内存中完成的排序。( 对 ) 219. 直接插入排序的最好情况是数据元素基本有序。( 对 ) 220. 快速排序的最好情况是数据元素基本有序。( 错 ) 221. 快速排序是稳定的排序方法。( 错 ) 222. 冒泡排序是稳定的排序方法。( 对 ) 223. 冒泡排序属于插入类排序。( 错 ) 224. 选择排序过程中元素之间的比较次数与原始序列的状态无关。( 对 ) 225. 用二叉链表存储包含n个结点的二叉树，结点的2n个指针区域中有 n+1个为空指针。( 对 ) 226. 用二叉链表存储包含n个结点的二叉树，结点的2n个指针区域中有 n-1个为空指针。( 错 ) 8、 算法应用及分析： 227. 如图所示二叉树，求 （1）画出二叉链表存储结构 （2）给出三种遍历次序 （3）给出中序线索二叉链表，中序线索二叉树。 （4）画出对应的树或森林。 先序：ABDGCEHF 中序：DGBAEHCF后序：GDBHEFCA 228. 已知叶结点的权值集合为5，7，2，3，6，9，要求给出哈夫曼 树，并计算带权路径长度WPL值。 WPL：（2+3）*4+（6+7）*2+5*3+9*2=79 229. 有一份电文中共使用五种字符：a,b,c,d,e,它们的出现频率依次为 4，7，5，2，9，请画出对应的编码赫夫曼树（请按照左子树根结 点的权小于等于右子树根结点的权的次序构造），求出每个字符的 赫夫曼编码。 a 011 b 10 c 00 d 010 e 11 230. 假设用于通讯的电文由8个字母组成，根据给定的字符出现频率， 构造Huffman树，并确定各个字符的Huffman编码。要求(1)画出 Huffman树(左子树权值小于右子树权值)，(2)写出每个字符的 Huffman编码。 A：0.07 B:0.19 C:0.02 D:0.06 E:0.32 F:0.03 G：0.21 H：0.10 A 1010 B 00 C 10000 D 1001 E 11 F 10001 G 01 H 1011 231. 有一份电文中共使用六种字符，每种字符及出现频率为如下列表， 要求(1)构造哈夫曼树(要求左子树根结点的权值小于等于右子树根 结点的权值)，(2)写出每个字符的哈夫曼编码。 A：0.28 B:0.23 C:0.12 D: 0.17 E:0.09 F:0.11 A : 10 B : 01 C: 110 D : 111 E: 000 F: 001 232. 无向图如图G1所示， 011010 100110 100111 011011 111101 001110 1A 2B 3C 4D 5E 6F （1）给出该图的邻接矩阵 （2）给图该图的邻接表 （3）按所给定的邻接矩阵存储结构，从A顶点出发，写出深度优先遍历的顶点序列，和广度优 先遍历的顶点序列。 邻接矩阵： 深度优先：ABDCEF 广度优 先：ABCEDF 没有画邻接表的图 233. 有如图所示的有向图 （1）给出它的邻接矩阵存储结构 （2）给出它的邻接表存储结构。 01010 00110 00001 00101 00000 （3）写出从1顶点出发进行深度优先搜索的序列，和广度优先搜索的序列。 12354 12435 234. 如下所示为图的邻接矩阵， 要求(1)画出该图； (2)按存储结构给出从C顶点开始的深度优先遍历序列，和 深度优先搜索生成树。 (3)按存储结构给出从C顶点开始的广度优先遍历序列，和 广度优先搜索生成树。 235. 请用图示的方法表示，用PRIM算法（普里姆）构造最小生成树的过 程。（从0结点开始） 236. 下图所示带权有向图，求从顶点1到其它顶点的最短路径。 237. 假定一个待散列存储的线性表为（32，75，63，48，94，25，36， 18，70），散列地址空间为0,1,11,若采用除留余数法 H(key)=key % 11构造散列函数，用线性探测法处理冲突,试给出它 们对应的散列表。 238. 假定一个待散列存储的线性表为（25，6，12，14，39，53），散 列地址空间为0,1,9,若采用除留余数法构造散列函数和线性 探测法处理冲突。( 其中H(key)=key MOD 7) （1） 试给出它们对应的散列表， （2） 并求出等概率条件下，查找成功时的平均查找长度和查找失败时的平均查找长 度。 0123456789 14 251263953 H(25)=4 H(6)=6 H(12)=5 H(14)=0 H(39)=4 H1(39)= (4+1)%10=5 H2(39)=6 H3(39)=7 H(53)=4 H1(53)=5 H2(53)=6 H3(53)=7 H4(53)=8 成功：ASL=(1+1+1+1+5+5)/6 = 13/6 失败：ASL=（2+1+1+