全国二级理论——1.2数据结构与算法 本套试题共50题。 1. 班级：格式如“19计应31”2. 学号：10位数完整格式3. 姓名：4. 下列各排序法中，最坏情况下的时间复杂度最低的是______。A. 冒泡排序B. 快速排序C. 希尔排序D. 堆排序5. 下列关于队列的叙述中正确的是______。A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表6. 设某二叉树的前序序列与中序序列均为ABCDEFGH，则该二叉树的后序序列为______。A. EFGHABCDB. HGFEDCBAC. DCBAHGFED. ABCDEFGH7. 设有序线性表的长度为n，则在有序线性表中进行二分查找，最坏情况下的比较次数为______。A. n(n-1)/2B. nC. nlog2nD. log2n8. [(4)希尔排序：将整个无序序列分割成若干小的子序列分别进行插入排序。在最坏情况下，希尔排序所需的比较次数为O(n1.5)。]9. 若某二叉树中的所有结点值均大于其左子树上的所有结点值，且小于右子树上的所有结点值，则该二叉树遍历序列中有序的是______。A. 前序序列B. 中序序列C. 后序序列D. 以上说法均不正确10. 算法的有穷性是指______。A. 算法程序的运行时间是有限的B. 算法程序所处理的数据量是有限的C. 算法程序的长度是有限的D. 算法只能被有限的用户使用11. 下列关于算法的描述中错误的是______。A. 算法强调动态的执行过程，不同于静态的计算公式B. 算法必须能在有限个步骤之后终止C. 算法设计必须考虑算法的复杂度D. 算法的优劣取决于运行算法程序的环境12. 在单链表中，增加头结点的目的是______。A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现13. [(3)快速排序：通常，快速排序被认为是，所有同数量级(O(nlogn))的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]14. 下列叙述中正确的是______。A. 线性表链式存储结构的存储空间一般要少于顺序存储结构B. 线性表链式存储结构与顺序存储结构的存储空间都是连续的C. 线性表链式存储结构的存储空间可以是连续的，也可以是不连续的D. 以上说法都不对15. 下列叙述中正确的是______。A. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B. 循环队列中的元素个数随队头指针的变化而动态变化C. 循环队列中的元素个数随队尾指针的变化而动态变化D. 以上说法都不对16. 在最坏情况下______。A. 快速排序的时间复杂度比冒泡排序的时间复杂度要小B. 快速排序的时间复杂度比希尔排序的时间复杂度要小C. 希尔排序的时间复杂度比直接插入排序的时间复杂度要小D. 快速排序的时间复杂度与希尔排序的时间复杂度是一样的17. 某二叉树的中序序列为BDCA，后序序列为DCBA，则前序序列为______。A. DCBAB. BDCAC. ABCDD. BADC18. 设数据元素集合为{A，B，C，D，E，F}，下列关系为线性结构的是______。A. R={ (D,F),(E,C),(B,C),(A,B),(C,F) }B. R={ (D,E),(E,A),(B,C),(A,B),(C,F) }C. R={ (A,B),(C,D),(B,A),(E,F),(F,A) }D. R={ (D,E),(E,A),(B,C),(F,B),(C,F) }19. 在下列几种排序方法中，要求内存量最大的是______。A. 插入排序B. 选择排序C. 快速排序D. 归并排序20. [（4）堆排序法：堆排序的方法为：①首先将一个无序序列建成堆。②然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。]21. 下列叙述中正确的是______。A. 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B. 顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C. 顺序存储结构能存储有序表，链式存储结构不能存储有序表D. 链式存储结构比顺序存储结构节省存储空间22. 设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为______。A. 5B. 6C. m-5D. m-623. 下列叙述中正确的是______。A. 有多个指针域的链表有可能是线性结构。B. 有多个指针域的链表一定是非线性结构。C. 有两个指针域的链表一定是二叉树的存储结构。D. 只有一个根结点的数据结构一定是线性结构。24. 为了降低算法的空间复杂度，要求算法尽量采用原地工作(in place)。所谓原地工作是指______。A. 执行算法时不使用任何存储空间B. 执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化C. 执行算法时不使用额外空间D. 执行算法时所使用的额外空间固定（即不随算法所处理的数据空间大小的变化而变化）25. 为了对有序表进行对分查找，则要求有序表______。A. 只能顺序存储B. 只能链式存储C. 可以顺序存储也可以链式存储D. 任何存储方式26. 下列叙述中正确的是______。A. 非线性结构只能采用链式存储结构B. 非线性结构只能用多重链表表示C. 所有数据结构既可以采用顺序存储结构，也可以采用链式存储结构D. 有的非线性结构也能采用顺序存储结构27. [(2) 快速排序：通常，快速排序被认为是，所有同数量级（O(nlogn)）的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]28. [(1)冒泡排序法：是一种最简单的交换类排序法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要比较的次数为n(n-1)/2次。因此冒泡排序总的时间复杂度为O(n2)。]29. 下列叙述中正确的是______。A. 堆可以用完全二叉树表示，其中序遍历序列是有序序列B. 多重链表必定是非线性结构C. 任何二叉树只能采用链式存储结构D. 排序二叉树的中序遍历序列是有序序列30. 某二叉树共有400个结点，其中有99个度为1的结点，则该二叉树中的叶子结点数为______。A. 149B. 150C. 151D. 不可能有这样的二叉树31. 设数据集合为D={1,2,3,4,5,6}，下列数据结构B=(D,R)中为线性结构的是______。A. R={(1,2),(2,3),(3,4),(4,5),(6,5)}B. R={(1,2),(2,3),(6,5),(3,6),(5,4)}C. R={(5,4),(3,4),(3,2),(4,3),(5,6)}D. R={(1,2),(2,3),(4,3),(4,5),(5,6)}32. 在具有2n个结点的完全二叉树中，叶子结点个数为______。A. n/2B. n+1C. n-1D. n33. 在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为______。A. 3n/4B. nC. n/2D. n/434. 设一棵树的度为3，其中度为3，2，1的结点个数分别为4，1，3。则该棵树中的叶子结点数为______。A. 11B. 10C. 12D. 不可能有这样的树35. 下列叙述中正确的是______。A. 解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的B. 解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的C. 解决一个问题的算法是唯一的D. 算法的时间复杂度与计算机系统有关36. 下列叙述中错误的是______。A. 算法的时间复杂度与问题规模无关B. 算法的时间复杂度与计算机系统无关C. 算法的时间复杂度与空间复杂度没有必然的联系D. 算法的空间复杂度与算法运行输出结果的数据量无关37. 下列叙述中错误的是______。A. 若二叉树没有叶子结点，则为空二叉树B. 循环队列空的条件是队头指针与队尾指针相同C. 带链栈的栈底指针是随栈的操作而动态变化的D. 若带链队列中只有一个元素，则队头指针与队尾指针必定相同38. 设数据结构B=(D, R)，其中D={ a, b, c, d, e, f } ，R={ (f, a),(d, b), (e, d), (c, e), (a, c) } ，该数据结构为______。A. 线性结构B. 循环队列C. 循环链表D. 非线性结构39. 设某棵树的度为3，其中度为3,1,0的结点个数分别为3,4,15。则该树中总结点数为______。A. 30B. 22C. 35D. 不可能有这样的树40. 下列叙述中错误的是______。A. 具有多个指针域的链表也可能是线性结构B. 循环队列属于线性结构C. 采用顺序存储的完全二叉树属于线性结构D. 具有两个以上根结点的数据结构一定是非线性结构41. 要在具有n个元素的有序顺序表中删除一个元素，删除后仍是有序顺序表，则在最坏情况下需要移动的元素个数为______。A. n-1B. nC. n/2D. n+142. 下列叙述中正确的是______。A. 向量是顺序存储的线性结构B. 只有一个根结点和一个叶子结点的结构必定是线性结构C. 非线性结构只能采用链式存储结构D. 所有非线性结构都能采用顺序存储结构43. 某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为______。A. 1B. 0C. 20D. 不确定44. 树的度为3，且有9个度为3的结点，5个度为1的结点，但没有度为2的结点。则该树总的结点数为______。A. 33B. 14C. 32D. 1945. 设元素集合为D={1，2，3，4，5，6}。B=(D,R)为线性结构所对应的R是______。A. R={(4,5),(6,1),(5,6),(1,3),(2,4),(3,2)}B. R={(6,1),(5,6),(1,3),(2,4),(3,2)}C. R={(6,1),(5,6),(1,3),(3,4),(3,2)}D. R={(6,1),(5,6),(2,3),(2,4),(3,2)}46. 循环队列的存储空间为Q(1:60)，初始状态为空。经过一系列正常的入队与退队操作后，front=24，rear=25。循环队列中的元素个数为______。A. 1B. 2C. 59D. 6047. 下列各组算法中，最坏情况下其时间复杂度相同的是______。A. 冒泡排序与快速排序B. 直接插入排序与希尔排序C. 简单选择排序与堆排序D. 快速排序与希尔排序48. 假设栈和队列初始状态为空。首先，A,B,C,D依次入栈，X,Y,Z依次入队；然后先将队中元素依次退队，再将栈中元素依次退栈。则退出的所有元素依次为______。A. A,B,C,D,Z,Y,XB. D,C,B,A,X,Y,ZC. A,B,C,D,X,Y,ZD. X,Y,Z,D,C,B,A49. 设二叉树如下，则后序序列为______。 A. ABDEGCFHB. DBGEAFHCC. DGEBHFCAD. ABCDEFGH50. 对下列二叉树进行中序遍历的结果是______。 A. ACBDFEGB. ACBDFGEC. ABDCGEFD. FCADBEG51. 某系统结构图如下图所示，该系统结构图的宽度是______。 A. 5B. 4C. 2D. 152. 设二叉树如下，则中序序列为______。 A. ABDEGCFHB. DBGEAFHCC. DGEBHFCAD. ABCDEFGH53. 对下列二叉树进行前序遍历的结果为______。 A. DYBEAFCZXB. YDEBFZXCAC. ABDYECFXZD. ABCDEFXYZ 提交成功！
全国二级理论——1.2数据结构与算法 本套试题共50题。 1. 班级：格式如“19计应31”2. 学号：10位数完整格式3. 姓名：4. 下列各排序法中，最坏情况下的时间复杂度最低的是______。A. 冒泡排序B. 快速排序C. 希尔排序D. 堆排序5. 下列关于队列的叙述中正确的是______。A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表6. 设某二叉树的前序序列与中序序列均为ABCDEFGH，则该二叉树的后序序列为______。A. EFGHABCDB. HGFEDCBAC. DCBAHGFED. ABCDEFGH7. 设有序线性表的长度为n，则在有序线性表中进行二分查找，最坏情况下的比较次数为______。A. n(n-1)/2B. nC. nlog2nD. log2n8. [(4)希尔排序：将整个无序序列分割成若干小的子序列分别进行插入排序。在最坏情况下，希尔排序所需的比较次数为O(n1.5)。]9. 若某二叉树中的所有结点值均大于其左子树上的所有结点值，且小于右子树上的所有结点值，则该二叉树遍历序列中有序的是______。A. 前序序列B. 中序序列C. 后序序列D. 以上说法均不正确10. 算法的有穷性是指______。A. 算法程序的运行时间是有限的B. 算法程序所处理的数据量是有限的C. 算法程序的长度是有限的D. 算法只能被有限的用户使用11. 下列关于算法的描述中错误的是______。A. 算法强调动态的执行过程，不同于静态的计算公式B. 算法必须能在有限个步骤之后终止C. 算法设计必须考虑算法的复杂度D. 算法的优劣取决于运行算法程序的环境12. 在单链表中，增加头结点的目的是______。A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现13. [(3)快速排序：通常，快速排序被认为是，所有同数量级(O(nlogn))的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]14. 下列叙述中正确的是______。A. 线性表链式存储结构的存储空间一般要少于顺序存储结构B. 线性表链式存储结构与顺序存储结构的存储空间都是连续的C. 线性表链式存储结构的存储空间可以是连续的，也可以是不连续的D. 以上说法都不对15. 下列叙述中正确的是______。A. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B. 循环队列中的元素个数随队头指针的变化而动态变化C. 循环队列中的元素个数随队尾指针的变化而动态变化D. 以上说法都不对16. 在最坏情况下______。A. 快速排序的时间复杂度比冒泡排序的时间复杂度要小B. 快速排序的时间复杂度比希尔排序的时间复杂度要小C. 希尔排序的时间复杂度比直接插入排序的时间复杂度要小D. 快速排序的时间复杂度与希尔排序的时间复杂度是一样的17. 某二叉树的中序序列为BDCA，后序序列为DCBA，则前序序列为______。A. DCBAB. BDCAC. ABCDD. BADC18. 设数据元素集合为{A，B，C，D，E，F}，下列关系为线性结构的是______。A. R={ (D,F),(E,C),(B,C),(A,B),(C,F) }B. R={ (D,E),(E,A),(B,C),(A,B),(C,F) }C. R={ (A,B),(C,D),(B,A),(E,F),(F,A) }D. R={ (D,E),(E,A),(B,C),(F,B),(C,F) }19. 在下列几种排序方法中，要求内存量最大的是______。A. 插入排序B. 选择排序C. 快速排序D. 归并排序20. [（4）堆排序法：堆排序的方法为：①首先将一个无序序列建成堆。②然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。]21. 下列叙述中正确的是______。A. 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B. 顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C. 顺序存储结构能存储有序表，链式存储结构不能存储有序表D. 链式存储结构比顺序存储结构节省存储空间22. 设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为______。A. 5B. 6C. m-5D. m-623. 下列叙述中正确的是______。A. 有多个指针域的链表有可能是线性结构。B. 有多个指针域的链表一定是非线性结构。C. 有两个指针域的链表一定是二叉树的存储结构。D. 只有一个根结点的数据结构一定是线性结构。24. 为了降低算法的空间复杂度，要求算法尽量采用原地工作(in place)。所谓原地工作是指______。A. 执行算法时不使用任何存储空间B. 执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化C. 执行算法时不使用额外空间D. 执行算法时所使用的额外空间固定（即不随算法所处理的数据空间大小的变化而变化）25. 为了对有序表进行对分查找，则要求有序表______。A. 只能顺序存储B. 只能链式存储C. 可以顺序存储也可以链式存储D. 任何存储方式26. 下列叙述中正确的是______。A. 非线性结构只能采用链式存储结构B. 非线性结构只能用多重链表表示C. 所有数据结构既可以采用顺序存储结构，也可以采用链式存储结构D. 有的非线性结构也能采用顺序存储结构27. [(2) 快速排序：通常，快速排序被认为是，所有同数量级（O(nlogn)）的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]28. [(1)冒泡排序法：是一种最简单的交换类排序法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要比较的次数为n(n-1)/2次。因此冒泡排序总的时间复杂度为O(n2)。]29. 下列叙述中正确的是______。A. 堆可以用完全二叉树表示，其中序遍历序列是有序序列B. 多重链表必定是非线性结构C. 任何二叉树只能采用链式存储结构D. 排序二叉树的中序遍历序列是有序序列30. 某二叉树共有400个结点，其中有99个度为1的结点，则该二叉树中的叶子结点数为______。A. 149B. 150C. 151D. 不可能有这样的二叉树31. 设数据集合为D={1,2,3,4,5,6}，下列数据结构B=(D,R)中为线性结构的是______。A. R={(1,2),(2,3),(3,4),(4,5),(6,5)}B. R={(1,2),(2,3),(6,5),(3,6),(5,4)}C. R={(5,4),(3,4),(3,2),(4,3),(5,6)}D. R={(1,2),(2,3),(4,3),(4,5),(5,6)}32. 在具有2n个结点的完全二叉树中，叶子结点个数为______。A. n/2B. n+1C. n-1D. n33. 在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为______。A. 3n/4B. nC. n/2D. n/434. 设一棵树的度为3，其中度为3，2，1的结点个数分别为4，1，3。则该棵树中的叶子结点数为______。A. 11B. 10C. 12D. 不可能有这样的树35. 下列叙述中正确的是______。A. 解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的B. 解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的C. 解决一个问题的算法是唯一的D. 算法的时间复杂度与计算机系统有关36. 下列叙述中错误的是______。A. 算法的时间复杂度与问题规模无关B. 算法的时间复杂度与计算机系统无关C. 算法的时间复杂度与空间复杂度没有必然的联系D. 算法的空间复杂度与算法运行输出结果的数据量无关37. 下列叙述中错误的是______。A. 若二叉树没有叶子结点，则为空二叉树B. 循环队列空的条件是队头指针与队尾指针相同C. 带链栈的栈底指针是随栈的操作而动态变化的D. 若带链队列中只有一个元素，则队头指针与队尾指针必定相同38. 设数据结构B=(D, R)，其中D={ a, b, c, d, e, f } ，R={ (f, a),(d, b), (e, d), (c, e), (a, c) } ，该数据结构为______。A. 线性结构B. 循环队列C. 循环链表D. 非线性结构39. 设某棵树的度为3，其中度为3,1,0的结点个数分别为3,4,15。则该树中总结点数为______。A. 30B. 22C. 35D. 不可能有这样的树40. 下列叙述中错误的是______。A. 具有多个指针域的链表也可能是线性结构B. 循环队列属于线性结构C. 采用顺序存储的完全二叉树属于线性结构D. 具有两个以上根结点的数据结构一定是非线性结构41. 要在具有n个元素的有序顺序表中删除一个元素，删除后仍是有序顺序表，则在最坏情况下需要移动的元素个数为______。A. n-1B. nC. n/2D. n+142. 下列叙述中正确的是______。A. 向量是顺序存储的线性结构B. 只有一个根结点和一个叶子结点的结构必定是线性结构C. 非线性结构只能采用链式存储结构D. 所有非线性结构都能采用顺序存储结构43. 某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为______。A. 1B. 0C. 20D. 不确定44. 树的度为3，且有9个度为3的结点，5个度为1的结点，但没有度为2的结点。则该树总的结点数为______。A. 33B. 14C. 32D. 1945. 设元素集合为D={1，2，3，4，5，6}。B=(D,R)为线性结构所对应的R是______。A. R={(4,5),(6,1),(5,6),(1,3),(2,4),(3,2)}B. R={(6,1),(5,6),(1,3),(2,4),(3,2)}C. R={(6,1),(5,6),(1,3),(3,4),(3,2)}D. R={(6,1),(5,6),(2,3),(2,4),(3,2)}46. 循环队列的存储空间为Q(1:60)，初始状态为空。经过一系列正常的入队与退队操作后，front=24，rear=25。循环队列中的元素个数为______。A. 1B. 2C. 59D. 6047. 下列各组算法中，最坏情况下其时间复杂度相同的是______。A. 冒泡排序与快速排序B. 直接插入排序与希尔排序C. 简单选择排序与堆排序D. 快速排序与希尔排序48. 假设栈和队列初始状态为空。首先，A,B,C,D依次入栈，X,Y,Z依次入队；然后先将队中元素依次退队，再将栈中元素依次退栈。则退出的所有元素依次为______。A. A,B,C,D,Z,Y,XB. D,C,B,A,X,Y,ZC. A,B,C,D,X,Y,ZD. X,Y,Z,D,C,B,A49. 设二叉树如下，则后序序列为______。 A. ABDEGCFHB. DBGEAFHCC. DGEBHFCAD. ABCDEFGH50. 对下列二叉树进行中序遍历的结果是______。 A. ACBDFEGB. ACBDFGEC. ABDCGEFD. FCADBEG51. 某系统结构图如下图所示，该系统结构图的宽度是______。 A. 5B. 4C. 2D. 152. 设二叉树如下，则中序序列为______。 A. ABDEGCFHB. DBGEAFHCC. DGEBHFCAD. ABCDEFGH53. 对下列二叉树进行前序遍历的结果为______。 A. DYBEAFCZXB. YDEBFZXCAC. ABDYECFXZD. ABCDEFXYZ 提交成功！
11. 下列关于算法的描述中错误的是______。A. 算法强调动态的执行过程，不同于静态的计算公式B. 算法必须能在有限个步骤之后终止C. 算法设计必须考虑算法的复杂度D. 算法的优劣取决于运行算法程序的环境
13. [(3)快速排序：通常，快速排序被认为是，所有同数量级(O(nlogn))的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]
14. 下列叙述中正确的是______。A. 线性表链式存储结构的存储空间一般要少于顺序存储结构B. 线性表链式存储结构与顺序存储结构的存储空间都是连续的C. 线性表链式存储结构的存储空间可以是连续的，也可以是不连续的D. 以上说法都不对
15. 下列叙述中正确的是______。A. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B. 循环队列中的元素个数随队头指针的变化而动态变化C. 循环队列中的元素个数随队尾指针的变化而动态变化D. 以上说法都不对
16. 在最坏情况下______。A. 快速排序的时间复杂度比冒泡排序的时间复杂度要小B. 快速排序的时间复杂度比希尔排序的时间复杂度要小C. 希尔排序的时间复杂度比直接插入排序的时间复杂度要小D. 快速排序的时间复杂度与希尔排序的时间复杂度是一样的
18. 设数据元素集合为{A，B，C，D，E，F}，下列关系为线性结构的是______。A. R={ (D,F),(E,C),(B,C),(A,B),(C,F) }B. R={ (D,E),(E,A),(B,C),(A,B),(C,F) }C. R={ (A,B),(C,D),(B,A),(E,F),(F,A) }D. R={ (D,E),(E,A),(B,C),(F,B),(C,F) }
20. [（4）堆排序法：堆排序的方法为：①首先将一个无序序列建成堆。②然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。]
21. 下列叙述中正确的是______。A. 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B. 顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C. 顺序存储结构能存储有序表，链式存储结构不能存储有序表D. 链式存储结构比顺序存储结构节省存储空间
22. 设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为______。A. 5B. 6C. m-5D. m-6
23. 下列叙述中正确的是______。A. 有多个指针域的链表有可能是线性结构。B. 有多个指针域的链表一定是非线性结构。C. 有两个指针域的链表一定是二叉树的存储结构。D. 只有一个根结点的数据结构一定是线性结构。
24. 为了降低算法的空间复杂度，要求算法尽量采用原地工作(in place)。所谓原地工作是指______。A. 执行算法时不使用任何存储空间B. 执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化C. 执行算法时不使用额外空间D. 执行算法时所使用的额外空间固定（即不随算法所处理的数据空间大小的变化而变化）
26. 下列叙述中正确的是______。A. 非线性结构只能采用链式存储结构B. 非线性结构只能用多重链表表示C. 所有数据结构既可以采用顺序存储结构，也可以采用链式存储结构D. 有的非线性结构也能采用顺序存储结构
27. [(2) 快速排序：通常，快速排序被认为是，所有同数量级（O(nlogn)）的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]
28. [(1)冒泡排序法：是一种最简单的交换类排序法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要比较的次数为n(n-1)/2次。因此冒泡排序总的时间复杂度为O(n2)。]
31. 设数据集合为D={1,2,3,4,5,6}，下列数据结构B=(D,R)中为线性结构的是______。A. R={(1,2),(2,3),(3,4),(4,5),(6,5)}B. R={(1,2),(2,3),(6,5),(3,6),(5,4)}C. R={(5,4),(3,4),(3,2),(4,3),(5,6)}D. R={(1,2),(2,3),(4,3),(4,5),(5,6)}
33. 在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为______。A. 3n/4B. nC. n/2D. n/4
35. 下列叙述中正确的是______。A. 解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的B. 解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的C. 解决一个问题的算法是唯一的D. 算法的时间复杂度与计算机系统有关
36. 下列叙述中错误的是______。A. 算法的时间复杂度与问题规模无关B. 算法的时间复杂度与计算机系统无关C. 算法的时间复杂度与空间复杂度没有必然的联系D. 算法的空间复杂度与算法运行输出结果的数据量无关
37. 下列叙述中错误的是______。A. 若二叉树没有叶子结点，则为空二叉树B. 循环队列空的条件是队头指针与队尾指针相同C. 带链栈的栈底指针是随栈的操作而动态变化的D. 若带链队列中只有一个元素，则队头指针与队尾指针必定相同
38. 设数据结构B=(D, R)，其中D={ a, b, c, d, e, f } ，R={ (f, a),(d, b), (e, d), (c, e), (a, c) } ，该数据结构为______。A. 线性结构B. 循环队列C. 循环链表D. 非线性结构
45. 设元素集合为D={1，2，3，4，5，6}。B=(D,R)为线性结构所对应的R是______。A. R={(4,5),(6,1),(5,6),(1,3),(2,4),(3,2)}B. R={(6,1),(5,6),(1,3),(2,4),(3,2)}C. R={(6,1),(5,6),(1,3),(3,4),(3,2)}D. R={(6,1),(5,6),(2,3),(2,4),(3,2)}
48. 假设栈和队列初始状态为空。首先，A,B,C,D依次入栈，X,Y,Z依次入队；然后先将队中元素依次退队，再将栈中元素依次退栈。则退出的所有元素依次为______。A. A,B,C,D,Z,Y,XB. D,C,B,A,X,Y,ZC. A,B,C,D,X,Y,ZD. X,Y,Z,D,C,B,A