河南农业大学软件工程专业大二2017年数据结构期末考试题目

河南农业大学软件工程专业大二2017年数据结构期末考试题目

1. 描述一个求解问题的抽象数据类型由？两部分组成。 [填空题] *

_________________________________(答案：数据逻辑结构和抽象运算)

2. 算法具有？5个重要特征 [填空题] *

_________________________________(答案：有穷性、确定性、可行性、输入和输出)

3. 一个数据结构在计算机中的？称为存储结构 [填空题] *

_________________________________(答案：映像)

4. 通常从四个方面评价算法的质量？ [填空题] *

_________________________________(答案：正确性、易读性、强壮性、高效率(正确易读,强壮高效))

5. 算法的时间复杂度取决于？ [填空题] *

_________________________________(答案：问题的规模和待处理数据的初态)

6. 在分析算法的时间复杂度时，通常认为算法的执行时间是？的函数 [填空题] *

_________________________________(答案：问题规模)

7. 数据结构是一门研究程序设计中数据的元素以及他们之间的？等的学科 [填空题] *

_________________________________(答案：关系和运算)

8. 算法分析的主要任务之一是？ [填空题] *

_________________________________(答案：算法的执行时间和问题规模之间的关系)

9. 算法分析的目的是？ [填空题] *

_________________________________(答案：分析算法的效率以求改进)

10. 数据逻辑结构、数据元素、数据项在计算机中的映像分别称为？ [填空题] *

_________________________________(答案：存储结构、结点和数据域)

11. 在一个长度为n的顺序表(1<=i)中插入第i个元素时需向后移动？个元素，删除第i个元素需向前移动？个元素，时间复杂度都为？。 [填空题] *

_________________________________(答案：n-i+1、n-i、O(n))

12. 在一个长度为n的顺序表(0<=i)中插入第i个元素时需向后移动？个元素，删除第i个元素需向前移动？个元素，时间复杂度都为？。 [填空题] *

_________________________________(答案：n-i、n-i-1、O(n))

13. 在循环双链表中查找和删除尾结点时间复杂度为？ [填空题] *

_________________________________(答案：O(1))

14. 用不带头结点的单链表表示队列时，在运行删除运算时？ [填空题] *

_________________________________(答案：头尾指针都可能修改)

15. 单链表中设置头结点的作用是？ [填空题] *

_________________________________(答案：便于操作,存放信息)

16. 在带头结点的单链表中，当删除某一指定结点时，必须找到该结点的？ [填空题] *

_________________________________(答案：前驱_____结点)

17. 将两个各有n个元素的递增有序顺序表归并成一个有序顺序表，其最少的元素比较次数是？次，最多比较次数是？次 [填空题] *

_________________________________(答案：n、2n-1)

18. 两个长度分别为m、n的有序单链表，在采用二路归并算法产生一个有序单链表时，算法的时间复杂度为？ [填空题] *

_________________________________(答案：O(m+n))

19. 两个长度分别为m、n的有序顺序表，在采用二路归并算法产生一个有序顺序表时，最少的元素比较次数是？ [填空题] *

_________________________________(答案：MIN(m,n))

20. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较？个结点 [填空题] *

_________________________________(答案：(n+1)/2)

21. 在有n个元素的顺序表中的任意一位置插入一个元素所需移动元素的平均次数为？，删除任意一个元素所需移动元素的平均次数为？。 [填空题] *

_________________________________(答案：n/2、(n-1)/2)

22. 在长度为n的顺序表中，若删除第i个元素的概率是Pi，则删除元素时平均移动元素的次数是？ [填空题] *

_________________________________(答案：请设置答案)

23. 共享栈，栈空条件？栈满条件？ [填空题] *

_________________________________(答案：栈1空为top1==-1;栈2空为top2==MaxSize、topl==top2-1)

24. 循环队列对空条件：_________对满条件：_________最多存储的元素个数为：_________队首指针为：_________队尾指针为：_________ [填空题] *

空1答案：real==front

空2答案：front=(real+1)%N

空3答案：(real-font+N)%N

空4答案：(rear-n+N)%N

空5答案：(front+n)%N

25. 链队，在进行插入或删除运算时？ [填空题] *

_________________________________(答案：头、尾指针可能都要修改)

26. 共享栈，当？时才产生上溢 [填空题] *

_________________________________(答案：两个栈的栈顶在栈空间的某一位置相遇)

27. 若某堆栈的输入序列是 1，2，3， …，n，输出序列的第一个元素为 n，则第 i 个输出元素为？ [填空题] *

_________________________________(答案：n-i+1)

28. 如果用单链表表示链式栈，则栈顶一般设在链表的？ [填空题] *

_________________________________(答案：链头)

29. 链栈与顺序栈相比，比较明显的优点是？ [填空题] *

_________________________________(答案：不会出现空间浪费问题)

30. 适合用作链队的链表是：_________最不适合用作链队的链表是：_________最不适合用作链栈的链表是：_________ [填空题] *

空1答案：带队首指针和队尾指针的非循环单链表

空2答案：只带队首指针的非循环双链表

空3答案：只有表头指针没有表尾指针的循环单链表

31. 共享栈的好处是？ [填空题] *

_________________________________(答案：节省存储空间,降低上溢出发生的几率)

32. 串的长度是指？ [填空题] *

_________________________________(答案：串中所含字符的个数)

33. 含n个不同字符的串的子串个数为？ [填空题] *

_________________________________(答案：n(n+1)/2+1)

34. 在串匹配中一般将主串称为：_________将子串称为：_________ [填空题] *

空1答案：目标串

空2答案：模式串

35. 两个字符串相等的充要条件是 [填空题] *

_________________________________(答案：两个字符串的长度相等且两个字符串中对应位置上的字符相等)

36. 串是一种特殊的线性表，其特殊性体现在 [填空题] *

_________________________________(答案：数据元素是一个字符)

37. 设有两个串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为 [填空题] *

_________________________________(答案：模式匹配)

38. 设有两个串 s 和 t，判断t是否为s子串的算法称为 [填空题] *

_________________________________(答案：串匹配)

39. 空串和空格串的区别： [填空题] *

_________________________________(答案： 空串是指不含任何字符的串,其长度为0,它是任意串的子串。仅含有空格字符的串称为空格串,其长度为串中空格字符的个数。)

40. 在BF模式匹配算法中，当模式串位j与目标串位i比较时两字符不相等，则i的位移方式是：_________j的位移方式是：_________ [填空题] *

空1答案：i=i-j+1

空2答案：j=0

41. 在KMP模式匹配中用next数组存放模式串的部分匹配信息，当模式串位j于目标串位i比较时两字符不相等，则i的位移方式是：_________j的位移方式是：_________ [填空题] *

空1答案：i不变

空2答案：j=next[j]

42. 在KMP模式匹配中用next数组存放模式串的部分匹配信息，当模式串位j于目标串位i比较时两字符相等，则i的位移方式是：_________j的位移方式是：_________ [填空题] *

空1答案：i++

空2答案：j++

43. 数组特点： [填空题] *

_________________________________(答案：数据元素数目固定、相同的数据类型、唯一的下标对应、随机存储结构)

44. 一维数组ai的存储地址公式： [填空题] *

_________________________________(答案：LOC(ai)=LOC(a1)+(i-1)k)

45. 特殊矩阵包括 [填空题] *

_________________________________(答案：对称矩阵、上(下)三角矩阵和对角矩阵)

46. 上三角矩阵公式 [填空题] *

_________________________________(答案：请设置答案)

47. 下三角矩阵公式 [填空题] *

_________________________________(答案：请设置答案)

48. 对称矩阵公式： [填空题] *

_________________________________(答案：请设置答案)

49. 对角矩阵公式 [填空题] *

_________________________________(答案：当b=1,k=2i+j)

50. 特殊矩阵采用压缩存储的目的是：_________采用常规压缩存储后仍然具有：_________ [填空题] *

空1答案：节省存储空间

空2答案：随机存取特性

51. 稀疏矩阵的压缩存储方式主要有：_________前者属于：_________后者属于_________ [填空题] *

空1答案：三元组和十字链表

空2答案：顺序存储结构

空3答案：链式存储结构

52. 广义表中的数据元素是有相对次序的 [判断题] *

对(正确答案)

错

53. 广义表可以共享 [判断题] *

对(正确答案)

错

54. 将一个n阶下（上）三角矩阵采用压缩存储，共存储 [填空题] *

_________________________________(答案：n(n+1)/2+1)

55. 矩阵a[m][n]和矩阵b[n][p]相乘，其时间复杂度为 [填空题] *

_________________________________(答案：O(mnp))

56. 对稀疏矩阵采用压缩存储的缺点之一是无法根据行、列号直接计算矩阵元素的存储地址 [判断题] *

对(正确答案)

错

57. 稀疏矩阵用十字链表表示优点在于便于实现增加或减少矩阵中非零元素的操作 [判断题] *

对(正确答案)

错

58. 对于含有n个结点的树（或者二叉树），无论度为多少，其分支数或所有结点度之和均为 [填空题] *

_________________________________(答案：n-1)

59. 树的存储结构主要有 [填空题] *

_________________________________(答案：双亲存储结构、孩子链存储结构、孩子兄弟链存储结构)

60. 一棵二叉树的第 i(i≥1)层最少有：_________个结点：，最多有_________个结点 [填空题] *

空1答案：1

空2答案：请设置答案

空3答案：请设置答案

61. 一棵有 n（n>0）个结点的满二叉树共：_________个叶子和_________个非终端结点 [填空题] *

空1答案：n+1/2

空2答案：n-1/2

62. 在含有n个结点的二叉链中，总指针域为：_________个，非空指针域为_________，空指针域为_________ [填空题] *

空1答案：2n

空2答案：n-1

空3答案：n+1

63. [填空题] *

_________________________________(答案：请设置答案)

. 树的逻辑表示方法有： [填空题] *

_________________________________(答案：树型表示法、文氏图表示法、凹入表示法、括号表示法)

65. 二叉树和二次树的区别： [填空题] *

_________________________________(答案：二次树至少有一个结点的度为2,而二叉树没有这个要求。二次树不分左右子树,而二叉树是严格区分的。)

66. 完全二叉树中层序编号为i的结点，若2i<=n，则编号为i的结点为 [填空题] *

_________________________________(答案：分支结点,否则为叶子结点)

67. n个结点的二叉树的最大高度是：_________，最小高度是 [填空题] *

68. 设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共有?个空指针域 [填空题] *

_________________________________(答案：2m)

69. 设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是 [填空题] *

_________________________________(答案：高度等于其结点数(只有一个叶子结点))

70. 先序和中序相同的条件是二叉树中 [填空题] *

_________________________________(答案：每个结点最多只有一个右孩子)

71. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树 [判断题] *

对(正确答案)

错

72. n 个结点的线素二叉树上含有的线索数为 [填空题] *

_________________________________(答案：n+l)

73. [填空题] *

_________________________________(答案：请设置答案)

74. 若二叉树采用二叉链存储结构，如果要交换其所有分支结点的左、右子树位置，利用 [填空题] *

_________________________________(答案：后序遍历)

75. [填空题] *

_________________________________(答案：请设置答案)

76. [填空题] *

_________________________________(答案：请设置答案)

77. 只要已知完全二叉树的任何一种遍历序列就可以唯一确定该二叉树 [判断题] *

对(正确答案)

错

78. 对于二叉树，在后序序列中，任一结点的后面都不会出现它的子孙结点 [判断题] *

对(正确答案)

错

79. 二叉树的前序遍历序列和后序遍历序列中，叶结点之间的相对次序不变 [判断题] *

对(正确答案)

错

80. 顺序存储结构下的数据元素为层次遍历结果 [判断题] *

对(正确答案)

错

81. 完全有向图的邻接矩阵是对称的 [判断题] *

对(正确答案)

错

82. 深度优先遍历可以找到所有路径，而广度优先遍历可以找到最短路径 [判断题] *

对(正确答案)

错

83. 如果一个有向图的拓扑序列是唯一的，则图中必定 [填空题] *

_________________________________(答案：仅有一个顶点的入度为0,一个顶点的出度为0)

84. 一个AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条 [判断题] *

对(正确答案)

错

85. 一个AOE网的关键路径不一定是唯一的，但其关键路径长度一定是唯一的 [判断题] *

对(正确答案)

错

86. n个结点完全无向图的边数为：_________，n个结点完全有向图的边数为_________ [填空题] *

空1答案：n(n-1)/2

空2答案：n(n-1)

87. 对于邻接矩阵而言：无向图的边数=矩阵中1元素个数的和/2，有向图的边数=矩阵中1元素个数的和 [判断题] *

对(正确答案)

错

88. 对于邻接表而言：无向图的边数=边结点个数的和/2，有向图的边数=边结点个数的和 [判断题] *

对(正确答案)

错

. 设图G是一个含有n个顶点的连通图，其中任意一条简单路径的长度不会超过 [填空题] *

_________________________________(答案：n-1)

90. 设某无向图中有n个顶点e条边，则建立该图邻接矩阵的时间复杂度为：_________，建立该图邻接表的时间复杂度为：_________ [填空题] *

空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+1

94. 要连通具有 n 个顶点的有向图，至少需要?边 [填空题] *

_________________________________(答案：n)

95. 在有向图的邻接表存储结构中，顶点 v 在边表中出现的次数是 [填空题] *

_________________________________(答案：顶点 v 的入度)

96. 有向图采用邻接矩阵存储，某一行中非零元素的个数等于 [填空题] *

_________________________________(答案：对应顶点的出度)

97. 图的广度优先遍历算法用到辅助队列，每个顶点最多进队？次 [填空题] *

_________________________________(答案：1)

98. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用深度优先遍历算法 [判断题] *

对(正确答案)

错

99. 若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图 [填空题] *

_________________________________(答案：含有顶点数目大于一的强连通分量)

100. 简单路径是指除了起点和终点外任何一个顶点在这条路径上不重复出现 [判断题] *

对(正确答案)

错

101. 任何一个含两个或以上顶点的带权无向图有？最小生成树 [填空题] *

_________________________________(答案：一颗或多颗)

102. 一个连通图的生成树是含有该连通图的全部顶点的 [填空题] *

_________________________________(答案：极小连通子图)

103. 在用Prim和Kruskal算法构造最小生成树时，前者更适合于稠密图，后者更适合于稀疏图 [判断题] *

对(正确答案)

错

104. Dijkstra算法的时间复杂度为 [填空题] *

_________________________________(答案：O(n2))

105. Dijkstra算法是按？的顺序方法求出图中从某顶点到其余顶点的最短路径 [填空题] *

_________________________________(答案：长度递增)

106. Dijkstra算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生，该算法在边上的权出现负值情况时不能正确产生最短路径。 [判断题] *

对(正确答案)

错

107. 在有n个顶点的有向图中，每个顶点的度最大可达 [填空题] *

_________________________________(答案：2(n-1))

108. 一个含有n个顶点的有向图仅有唯一的拓扑序列，则该图的边数为 [填空题] *

_________________________________(答案：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条边的无向图，矩阵中零元素的个数为：_________,采用压缩方式存储矩阵中零元素的个数为。：_________ [填空题] *

空1答案：n*n-2e

空2答案：n(n+1)/2-e

116. 对箱排序的改进和推广的算法是 [填空题] *

_________________________________(答案：基数排序)

117. 拓扑排序算法中利用一个栈保存入度为0的顶点，目的是减少找入度为0的顶点的时间，提高效率 [判断题] *

对(正确答案)

错

118. 折半查找要求线性表必须以顺序方式存储，且元素按关键字有序排列，不适合在链式存储结构上实现 [判断题] *

对(正确答案)

错

119. 顺序查找时间复杂度为：_________,折半查找时间复杂度为：_________ [填空题] *

空1答案：O(n)

空2答案：O(log2n)

120. [填空题] *

_________________________________(答案：请设置答案)

121. 分块查找的ASL不仅与表长有关，而且与每一块中的元素个数有关。效率介于顺序查找和折半查找之间 [填空题] *

_________________________________(答案：请设置答案)

122. 向一颗二叉排序树中插入一个结点均是以叶子结点插入的，所需的关键字比较次数最多是树的高度 [判断题] *

对(正确答案)

错

123. 二叉排序树的中序序列是一个递增有序序列 [判断题] *

对(正确答案)

错

124. 给定结点个数的平衡二叉树的高度不一定是唯一的 [判断题] *

对(正确答案)

错

125. 设计哈希表主要是设计哈希函数和哈希冲突解决方法 [判断题] *

对(正确答案)

错

126. 同义词是指两个不同关键字的元素，其哈希函数值相同，这种冲突称为同义词冲突 [判断题] *

对(正确答案)

错

127. 非同义词冲突是指哈希函数值不相同的两个元素争夺同一个后继哈希地址，导致出现堆积或聚集现象 [判断题] *

对(正确答案)

错

128. 在采用线性探测法处理冲突的哈希表中，所有同义词在表中不一定相邻 [判断题] *

对(正确答案)

错

129. 评价哈希函数好坏的标准是 [填空题] *

_________________________________(答案：哈希函数的取值是否均匀)

130. 在哈希存储中，装填因子的值越大，则存取元素时发生冲突的可能性就越大。值越小，存取元素时发生冲突的可能性就越小 [判断题] *

对(正确答案)

错

131. 为了能有效地应用 HASH 查找技术，必须解决的两个问题是 [填空题] *

_________________________________(答案：构造一个好的 HASH 函数和确定解决冲突的方法)

132. 假设m个关键字互为同义词，若用线性探测法把这m个关键字存入散列表中，至少要进行的探查次数是 [填空题] *

_________________________________(答案：m(m+1)/2)

133. 设二叉排序树中有 n 个结点，则在二叉排序树上查找或插入结点的平均时间复杂度为 [填空题] *

_________________________________(答案：O(log2n))

134. 在最坏情况下，利用插入操作构造一颗二叉排序树花费的代价为 [填空题] *

_________________________________(答案：O())

135. 当采用分块查找时，数据的组织方式为数据分成若干块，每块内数据无序，但块间必须有序，每块内最大或最小的数据组成索引块。 [判断题] *

对(正确答案)

错

136. 在采用分块查找时，若线性表有n个元素，则每块分为个结点最佳 [判断题] *

对(正确答案)

错

137. 分块查找方法先查找索引表，在查找数据表，至少要两次元素比较 [判断题] *

对(正确答案)

错

138. 不管是开放地址法还是拉链法，查找时间都与？有关 [填空题] *

_________________________________(答案：装填因子)

139. 在采用开放地址法解决冲突的哈希表中，发生堆积的原因主要是 [填空题] *

_________________________________(答案：解决冲突的算法选择不当)

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. 除了问题的规模和分量个数之外，还有基数大小是影响基数排序的时间复杂度的主要因素 [判断题] *

对(正确答案)

错