数据结构期末考试题目.docx

《数据结构期末考试题目.docx》由会员分享，可在线阅读，更多相关《数据结构期末考试题目.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构期末考试题目1. 描述一个求解问题的抽象数据类型由？两部分组成。 _(答案：数据逻辑结构和抽象运算)2. 算法具有？5个重要特征 _(答案：有穷性、确定性、可行性、输入和输出)3. 一个数据结构在计算机中的？称为存储结构 _(答案：映像)4. 通常从四个方面评价算法的质量？ _(答案：正确性、易读性、强壮性、高效率(正确易读,强壮高效)5. 算法的时间复杂度取决于？ _(答案：问题的规模和待处理数据的初态)6. 在分析算法的时间复杂度时，通常认为算法的执行时间是？的函数 _(答案：问题规模)7. 数据结构是一门研究程序设计中数据的元素以及他们之间的？等的学科 _(答案：关系和运算)8.

2、 算法分析的主要任务之一是？ _(答案：算法的执行时间和问题规模之间的关系)9. 算法分析的目的是？ _(答案：分析算法的效率以求改进)10. 数据逻辑结构、数据元素、数据项在计算机中的映像分别称为？ _(答案：存储结构、结点和数据域)11. 在一个长度为n的顺序表(1=i)中插入第i个元素时需向后移动？个元素，删除第i个元素需向前移动？个元素，时间复杂度都为？。 _(答案：n-i+1、n-i、O(n)12. 在一个长度为n的顺序表(00）个结点的满二叉树共：_个叶子和_个非终端结点 空1答案：n+1/2空2答案：n-1/262. 在含有n个结点的二叉链中，总指针域为：_个，非空指针域为_，空

3、指针域为_ 空1答案：2n空2答案：n-1空3答案：n+163. _(答案：请设置答案)64. 树的逻辑表示方法有： _(答案：树型表示法、文氏图表示法、凹入表示法、括号表示法)65. 二叉树和二次树的区别： _(答案：二次树至少有一个结点的度为2,而二叉树没有这个要求。二次树不分左右子树,而二叉树是严格区分的。)66. 完全二叉树中层序编号为i的结点，若2i=n，则编号为i的结点为 _(答案：分支结点,否则为叶子结点)67. n个结点的二叉树的最大高度是：_，最小高度是 68. 设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共有?个空指针域 _(答案：2m)69

4、. 设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是 _(答案：高度等于其结点数(只有一个叶子结点)70. 先序和中序相同的条件是二叉树中 _(答案：每个结点最多只有一个右孩子)71. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树 对(正确答案)错72. n 个结点的线素二叉树上含有的线索数为 _(答案：n+l)73. _(答案：请设置答案)74. 若二叉树采用二叉链存储结构，如果要交换其所有分支结点的左、右子树位置，利用 _(答案：后序遍历)75. _(答案：请设置答案)76. _(答案：请设置答案)77. 只要已知完全二叉树的任何一种遍历序列就可以唯一确定该二叉

5、树 对(正确答案)错78. 对于二叉树，在后序序列中，任一结点的后面都不会出现它的子孙结点 对(正确答案)错79. 二叉树的前序遍历序列和后序遍历序列中，叶结点之间的相对次序不变 对(正确答案)错80. 顺序存储结构下的数据元素为层次遍历结果 对(正确答案)错81. 完全有向图的邻接矩阵是对称的 对(正确答案)错82. 深度优先遍历可以找到所有路径，而广度优先遍历可以找到最短路径 对(正确答案)错83. 如果一个有向图的拓扑序列是唯一的，则图中必定 _(答案：仅有一个顶点的入度为0,一个顶点的出度为0)84. 一个AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条 对(正确答案)

6、错85. 一个AOE网的关键路径不一定是唯一的，但其关键路径长度一定是唯一的 对(正确答案)错86. n个结点完全无向图的边数为：_，n个结点完全有向图的边数为_ 空1答案：n(n-1)/2空2答案：n(n-1)87. 对于邻接矩阵而言：无向图的边数=矩阵中1元素个数的和/2，有向图的边数=矩阵中1元素个数的和 对(正确答案)错88. 对于邻接表而言：无向图的边数=边结点个数的和/2，有向图的边数=边结点个数的和 对(正确答案)错89. 设图G是一个含有n个顶点的连通图，其中任意一条简单路径的长度不会超过 _(答案：n-1)90. 设某无向图中有n个顶点e条边，则建立该图邻接矩阵的时间复杂度为

7、：_，建立该图邻接表的时间复杂度为：_ 空1答案：O(n2)空2答案：O(n+e)91. 设无向图G 中有 n 个顶点，则该无向图中每个顶点的度数最多是 _(答案：n-1)92. 设连通图G 中有n 个顶点e 条边，则对应的最小生成树上有 _(答案：n-1)93. 若无向图G中含N个顶点，那么至少应有：_条边才可能是一个连通图，则保证图G在任何情况下都是连通的需要的边数最少是_ 空1答案：n-1空2答案：(n-1)(n-2)/2+194. 要连通具有 n 个顶点的有向图，至少需要?边 _(答案：n)95. 在有向图的邻接表存储结构中，顶点 v 在边表中出现的次数是 _(答案：顶点 v 的入度)

8、96. 有向图采用邻接矩阵存储，某一行中非零元素的个数等于 _(答案：对应顶点的出度)97. 图的广度优先遍历算法用到辅助队列，每个顶点最多进队？次 _(答案：1)98. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用深度优先遍历算法 对(正确答案)错99. 若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图 _(答案：含有顶点数目大于一的强连通分量)100. 简单路径是指除了起点和终点外任何一个顶点在这条路径上不重复出现 对(正确答案)错101. 任何一个含两个或以上顶点的带权无向图有？最小生成树 _(答案：一颗或多颗)102. 一个连通图的生成树是含有该连通图的全

9、部顶点的 _(答案：极小连通子图)103. 在用Prim和Kruskal算法构造最小生成树时，前者更适合于稠密图，后者更适合于稀疏图 对(正确答案)错104. Dijkstra算法的时间复杂度为 _(答案：O(n2)105. Dijkstra算法是按？的顺序方法求出图中从某顶点到其余顶点的最短路径 _(答案：长度递增)106. Dijkstra算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生，该算法在边上的权出现负值情况时不能正确产生最短路径。 对(正确答案)错107. 在有n个顶点的有向图中，每个顶点的度最大可达 _(答案：2(n-1)108. 一个含有n个顶点的有向图仅有唯一的

10、拓扑序列，则该图的边数为 _(答案：n-1)109. 一个有n个顶点、e条边的连通图采用邻接表表示，从某个顶点v出发进行DFS，则最大的递归深度是 _(答案：n)110. 一个有n个顶点、e条边的连通图采用邻接表表示，从某个顶点v出发进行BFS，则队列中最多的顶点个数是 _(答案：n-1)111. DFS时间复杂度为 _(答案：O(n2)112. 拓扑排序的时间复杂度是 _(答案：O(n+e)113. 如果图G存在拓扑排序序列，则G必为 _(答案：有向无环图)114. 若含有n个顶点的无向图恰好形成一个环，则它有n棵生成树 对(正确答案)错115. 用邻接矩阵表示有n个顶点和e条边的无向图，矩

11、阵中零元素的个数为：_,采用压缩方式存储矩阵中零元素的个数为。：_ 空1答案：nn-2e空2答案：n(n+1)/2-e116. 对箱排序的改进和推广的算法是 _(答案：基数排序)117. 拓扑排序算法中利用一个栈保存入度为0的顶点，目的是减少找入度为0的顶点的时间，提高效率 对(正确答案)错118. 折半查找要求线性表必须以顺序方式存储，且元素按关键字有序排列，不适合在链式存储结构上实现 对(正确答案)错119. 顺序查找时间复杂度为：_,折半查找时间复杂度为：_ 空1答案：O(n)空2答案：O(log2n)120. _(答案：请设置答案)121. 分块查找的ASL不仅与表长有关，而且与每一块

12、中的元素个数有关。效率介于顺序查找和折半查找之间 _(答案：请设置答案)122. 向一颗二叉排序树中插入一个结点均是以叶子结点插入的，所需的关键字比较次数最多是树的高度 对(正确答案)错123. 二叉排序树的中序序列是一个递增有序序列 对(正确答案)错124. 给定结点个数的平衡二叉树的高度不一定是唯一的 对(正确答案)错125. 设计哈希表主要是设计哈希函数和哈希冲突解决方法 对(正确答案)错126. 同义词是指两个不同关键字的元素，其哈希函数值相同，这种冲突称为同义词冲突 对(正确答案)错127. 非同义词冲突是指哈希函数值不相同的两个元素争夺同一个后继哈希地址，导致出现堆积或聚集现象 对

13、(正确答案)错128. 在采用线性探测法处理冲突的哈希表中，所有同义词在表中不一定相邻 对(正确答案)错129. 评价哈希函数好坏的标准是 _(答案：哈希函数的取值是否均匀)130. 在哈希存储中，装填因子的值越大，则存取元素时发生冲突的可能性就越大。值越小，存取元素时发生冲突的可能性就越小 对(正确答案)错131. 为了能有效地应用 HASH 查找技术，必须解决的两个问题是 _(答案：构造一个好的 HASH 函数和确定解决冲突的方法)132. 假设m个关键字互为同义词，若用线性探测法把这m个关键字存入散列表中，至少要进行的探查次数是 _(答案：m(m+1)/2)133. 设二叉排序树中有 n

14、 个结点，则在二叉排序树上查找或插入结点的平均时间复杂度为 _(答案：O(log2n)134. 在最坏情况下，利用插入操作构造一颗二叉排序树花费的代价为 _(答案：O()135. 当采用分块查找时，数据的组织方式为数据分成若干块，每块内数据无序，但块间必须有序，每块内最大或最小的数据组成索引块。 对(正确答案)错136. 在采用分块查找时，若线性表中共有n个元素，则每块分为个结点最佳 对(正确答案)错137. 分块查找方法先查找索引表，在查找数据表，至少要两次元素比较 对(正确答案)错138. 不管是开放地址法还是拉链法，查找时间都与？有关 _(答案：装填因子)139. 在采用开放地址法解决冲

15、突的哈希表中，发生堆积的原因主要是 _(答案：解决冲突的算法选择不当)140. 采用顺序查找方法查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为n次，若查找不成功，则比较关键字的次数为n次 对(正确答案)错141. 设某堆中有n 个结点，则在该堆中插入一个新结点的时间复杂度为 _(答案：O(log2n)142. 堆是完全二叉树，完全二叉树不一定是堆 对(正确答案)错143. 若表R的初始数据接近正序排列，则直接插入排序方法的比较次数最少 对(正确答案)错144. 对含有n个元素的数据序列进行简单选择排序，总的关键字比较次数是？，最好情况下元素移动次数为？次 _(答案：n(n-1)/2、0)145. 在堆排序过程中，由n个待排序的记录建立初始堆需要n/2次筛选，到排序结束需要进行n-1次筛选 对(正确答案)错146. _(答案：请设置答案)147. 除了问题的规模和分量个数之外，还有基数大小是影响基数排序的时间复杂度的主要因素 对(正确答案)错