全国二级理论——1.2数据结构与算法 本套试题共50题。 1. 班级：格式如“19计应31”2. 学号：10位数完整格式3. 姓名：4. 一个栈的初始状态为空，现将元素A,B,C,D,E依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队（原队列为空），最后将队列中的元素全部退出。则元素退队的顺序为______。A. ABCB. CBAC. EDCD. CDE5. [(3)快速排序：通常，快速排序被认为是，所有同数量级(O(nlogn))的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]6. 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是______。A. ABCEDB. DBCEAC. CDABED. DCBEA7. [(2)希尔排序：将整个无序序列分割成若干小的子序列分别进行插入排序。在最坏情况下，希尔排序所需的比较次数为O(n1.5)。]8. 在下列选项中，哪个不是一个算法一般应该具有的基本特征______。A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报9. 下列与队列结构有关联的是______。A. 函数的递归调用B. 数组元素的引用C. 多重循环的执行D. 先到先服务的作业调度10. 下列数据结构中，能用二分法进行查找的是______。A. 顺序存储的有序线性表B. 线性链表C. 二叉链表D. 有序线性链表11. 下列关于线性链表的叙述中，正确的是______。A. 各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B. 各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C. 进行插入和删除时，不需要移动表中的元素D. 以上三种说法都不对12. [(1)快速排序：通常，快速排序被认为是所有同数量级O(nlogn)的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]13. 某二叉树的深度为7，其中有64个叶子结点，则该二叉树中度为1的结点数为______。A. 0B. 1C. 2D. 6314. [希尔排序法属于插入类排序，但它对简单插入排序做了较大的改进。基本思想是：将整个无序序列分割成若干小的子序列分别进行插入排序。在希尔排序过程中，虽然对于每一个子表采用的仍是插入排序，但是，在子表中每进行一次比较久有可能移去整个线性表中的多个逆序，从而改善了整个排序过程的性能。最欢情况下，希尔排序所需要的比较次数为O(n1.5)。]15. 下列叙述中正确的是______。A. 所谓有序表是指在顺序存储空间内连续存放的元素序列B. 有序表只能顺序存储在连续的存储空间内C. 有序表可以用链接存储方式存储在不连续的存储空间内D. 任何存储方式的有序表均能采用二分法进行查找16. 已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是______。A. 堆排序B. 直接插入排序C. 快速排序D. 直接选择排序17. 下列链表中，其逻辑结构属于非线性结构的是______。A. 二叉链表B. 循环链表C. 双向链表D. 带链的栈18. 设栈的顺序存储空间为S(1:m)，初始状态为top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为______。A. m+1B. 1C. 不可能D. m19. 一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为______。A. 4B. 16C. 10D. 620. 算法的空间复杂度是指______。A. 算法在执行过程中所需要的计算机存储空间B. 算法所处理的数据量C. 算法程序中的语句或指令条数D. 算法在执行过程中所需要的临时工作单元数21. 某二叉树的中序序列为BDCA，后序序列为DCBA，则前序序列为______。A. DCBAB. BDCAC. ABCDD. BADC22. 数据的存储结构是指______。A. 存储在外存中的数据B. 数据所占的存储空间量C. 数据在计算机中的顺序存储方式D. 数据的逻辑结构在计算机中的表示23. 深度为7的二叉树共有127个结点，则下列说法中错误的是______。A. 该二叉树有一个度为1的结点B. 该二叉树是满二叉树C. 该二叉树是完全二叉D. 该二叉树有64个叶子结点24. 用链表表示线性表的优点是______。A. 便于插入和删除操作B. 数据元素的物理顺序与逻辑顺序相同C. 花费的存储空间较顺序存储少D. 便于随机存取25. 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为______。A. 219B. 221C. 229D. 23126. 某二叉树中共有935个结点，其中叶子结点有435个，则该二叉树中度为2的结点个数为______。A. 64B. 66C. 436D. 43427. 下列关于算法复杂度叙述正确的是______。A. 最坏情况下的时间复杂度一定高于平均情况的时间复杂度B. 时间复杂度与所用的计算工具无关C. 对同一个问题，采用不同的算法，则它们的时间复杂度是相同的D. 时间复杂度与采用的算法描述语言有关28. 设循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。现经过一系列入队与退队操作后，front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为______。A. 1B. 2C. 3D. 5229. 下列叙述中正确的是______。A. 非线性结构可以为空B. 只有一个根结点和一个叶子结点的必定是线性结构C. 只有一个根结点的必定是线性结构或二叉树D. 没有根结点的一定是非线性结构30. 下列叙述中错误的是______。A. 二分查找法只适用于顺序存储的线性有序表B. 所有二叉树都只能用二叉链表表示C. 有多个指针域的链表也有可能是线性结构D. 循环队列是队列的存储结构31. 一个栈的初始状态为空。现将元素1,2,3,A,B,C依次入栈，然后再依次出栈，则元素出栈的顺序是______。A. 1,2,3,A,B,CB. C,B,A,1,2,3C. C,B,A,3,2,1D. 1,2,3,C,B,A32. 下列排序方法中，最坏情况下时间复杂度（即比较次数）低于O(n2)的是______。A. 冒泡排序B. 快速排序C. 简单插入排序D. 堆排序33. 下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是______。A. 在顺序存储的线性表中寻找最大项B. 在顺序存储的线性表中进行顺序查找C. 在顺序存储的有序表中进行对分查找D. 在链式存储的有序表中进行查找34. 设表的长度为n。下列查找算法中，在最坏情况下，比较次数最少的是______。A. 顺序查找B. 有序表的二分查找C. 寻找最大项D. 寻找最小项35. 下列叙述中错误的是______。A. 向量是线性结构B. 非空线性结构中只有一个结点没有前件C. 非空线性结构中只有一个结点没有后件D. 只有一个根结点和一个叶子结点的结构必定是线性结构36. 设表的长度为n。在下列算法中，最坏情况下时间复杂度最高的是______。A. 有序链表查找B. 循环链表中寻找最大项C. 希尔排序D. 堆排序37. 设顺序表的长度为16，对该表进行简单插入排序。在最坏情况下需要的比较次数为______。A. 120B. 60C. 30D. 1538. 下列叙述中正确的是______。A. 快速排序适用于链式存储的线性表B. 快速排序法适用于顺序存储的线性表C. 链式存储的线性表不可能排序D. 堆排序适用于非线性结构39. 下列叙述中正确的是______。A. 循环链表中至少有一个结点B. 双向链表有两个头指针C. 双向链表有两个头结点D. 循环链表是循环队列的链式存储结构40. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队，然后依次轮流出栈和退队，则输出序列为______。A. G,B,E,D,C,F,A,HB. B,G,D,E,F,C,H,AC. D,C,B,A,E,F,G,HD. A,B,C,D,H,G,F,E41. 设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则按层次输出（从上到下，同一层从左到右）的序列为______。A. DGHEBIJFCAB. JIHGFEDCBAC. GHIJDEFBCAD. ABCDEFGHIJ42. 树的度为3，且有9个度为3的结点，20个叶子结点，但没有度为1的结点。则该树总的结点数为______。A. 30B. 29C. 47D. 不可能有这样的树43. 树的度为3，且有9个度为3的结点，20个叶子结点，但没有度为1的结点。则该树中度为2的结点数为______。A. 7B. 0C. 1D. 不可能有这样的树44. 某二叉树有49个度为2的结点，4个度为1的结点，则______。A. 该二叉树共有103个结点B. 该二叉树的结点数不确定C. 该二叉树共有101个结点D. 不可能有这样的二叉树45. 循环队列的存储空间为Q(1:50)，初始状态为空。经过一系列正常的入队与退队操作后，front=25，rear=25。此时该循环队列中的元素个数为______。A. 0或50B. 0C. 50D. 2546. 循环队列的存储空间为Q(1:50)，初始状态为空。经过一系列正常的入队与退队操作后，front=24，rear=25。此时该循环队列中的元素个数为______。A. 1B. 49C. 50D. 2547. 设二叉树的前序序列为ABCDEF，中序序列为ABCDEF，则该二叉树的深度为（根结点为第1层）______。A. 4B. 2C. 3D. 648. 设二叉树的前序序列为ABCDEF，中序序列为BDFECA，则该二叉树的后序序列为______。A. ABCDEFB. FEDCBAC. BDFECAD. CBAFED49. 对如下二叉树进行后序遍历的结果为______。 A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA50. 某系统结构图如下图所示，该系统结构图的深度是______。 A. 4B. 3C. 2D. 151. 对下列二叉树进行中序遍历的结果是______。 A. ACBDFEGB. ACBDFGEC. ABDCGEFD. FCADBEG52. 对下列二叉树进行前序遍历的结果为______。 A. DYBEAFCZXB. YDEBFZXCAC. ABDYECFXZD. ABCDEFXYZ53. 设二叉树如下，则后序序列为______。 A. ABDEGCFHB. DBGEAFHCC. DGEBHFCAD. ABCDEFGH 提交成功！
全国二级理论——1.2数据结构与算法 本套试题共50题。 1. 班级：格式如“19计应31”2. 学号：10位数完整格式3. 姓名：4. 一个栈的初始状态为空，现将元素A,B,C,D,E依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队（原队列为空），最后将队列中的元素全部退出。则元素退队的顺序为______。A. ABCB. CBAC. EDCD. CDE5. [(3)快速排序：通常，快速排序被认为是，所有同数量级(O(nlogn))的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]6. 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是______。A. ABCEDB. DBCEAC. CDABED. DCBEA7. [(2)希尔排序：将整个无序序列分割成若干小的子序列分别进行插入排序。在最坏情况下，希尔排序所需的比较次数为O(n1.5)。]8. 在下列选项中，哪个不是一个算法一般应该具有的基本特征______。A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报9. 下列与队列结构有关联的是______。A. 函数的递归调用B. 数组元素的引用C. 多重循环的执行D. 先到先服务的作业调度10. 下列数据结构中，能用二分法进行查找的是______。A. 顺序存储的有序线性表B. 线性链表C. 二叉链表D. 有序线性链表11. 下列关于线性链表的叙述中，正确的是______。A. 各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B. 各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C. 进行插入和删除时，不需要移动表中的元素D. 以上三种说法都不对12. [(1)快速排序：通常，快速排序被认为是所有同数量级O(nlogn)的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]13. 某二叉树的深度为7，其中有64个叶子结点，则该二叉树中度为1的结点数为______。A. 0B. 1C. 2D. 6314. [希尔排序法属于插入类排序，但它对简单插入排序做了较大的改进。基本思想是：将整个无序序列分割成若干小的子序列分别进行插入排序。在希尔排序过程中，虽然对于每一个子表采用的仍是插入排序，但是，在子表中每进行一次比较久有可能移去整个线性表中的多个逆序，从而改善了整个排序过程的性能。最欢情况下，希尔排序所需要的比较次数为O(n1.5)。]15. 下列叙述中正确的是______。A. 所谓有序表是指在顺序存储空间内连续存放的元素序列B. 有序表只能顺序存储在连续的存储空间内C. 有序表可以用链接存储方式存储在不连续的存储空间内D. 任何存储方式的有序表均能采用二分法进行查找16. 已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是______。A. 堆排序B. 直接插入排序C. 快速排序D. 直接选择排序17. 下列链表中，其逻辑结构属于非线性结构的是______。A. 二叉链表B. 循环链表C. 双向链表D. 带链的栈18. 设栈的顺序存储空间为S(1:m)，初始状态为top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为______。A. m+1B. 1C. 不可能D. m19. 一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为______。A. 4B. 16C. 10D. 620. 算法的空间复杂度是指______。A. 算法在执行过程中所需要的计算机存储空间B. 算法所处理的数据量C. 算法程序中的语句或指令条数D. 算法在执行过程中所需要的临时工作单元数21. 某二叉树的中序序列为BDCA，后序序列为DCBA，则前序序列为______。A. DCBAB. BDCAC. ABCDD. BADC22. 数据的存储结构是指______。A. 存储在外存中的数据B. 数据所占的存储空间量C. 数据在计算机中的顺序存储方式D. 数据的逻辑结构在计算机中的表示23. 深度为7的二叉树共有127个结点，则下列说法中错误的是______。A. 该二叉树有一个度为1的结点B. 该二叉树是满二叉树C. 该二叉树是完全二叉D. 该二叉树有64个叶子结点24. 用链表表示线性表的优点是______。A. 便于插入和删除操作B. 数据元素的物理顺序与逻辑顺序相同C. 花费的存储空间较顺序存储少D. 便于随机存取25. 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为______。A. 219B. 221C. 229D. 23126. 某二叉树中共有935个结点，其中叶子结点有435个，则该二叉树中度为2的结点个数为______。A. 64B. 66C. 436D. 43427. 下列关于算法复杂度叙述正确的是______。A. 最坏情况下的时间复杂度一定高于平均情况的时间复杂度B. 时间复杂度与所用的计算工具无关C. 对同一个问题，采用不同的算法，则它们的时间复杂度是相同的D. 时间复杂度与采用的算法描述语言有关28. 设循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。现经过一系列入队与退队操作后，front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为______。A. 1B. 2C. 3D. 5229. 下列叙述中正确的是______。A. 非线性结构可以为空B. 只有一个根结点和一个叶子结点的必定是线性结构C. 只有一个根结点的必定是线性结构或二叉树D. 没有根结点的一定是非线性结构30. 下列叙述中错误的是______。A. 二分查找法只适用于顺序存储的线性有序表B. 所有二叉树都只能用二叉链表表示C. 有多个指针域的链表也有可能是线性结构D. 循环队列是队列的存储结构31. 一个栈的初始状态为空。现将元素1,2,3,A,B,C依次入栈，然后再依次出栈，则元素出栈的顺序是______。A. 1,2,3,A,B,CB. C,B,A,1,2,3C. C,B,A,3,2,1D. 1,2,3,C,B,A32. 下列排序方法中，最坏情况下时间复杂度（即比较次数）低于O(n2)的是______。A. 冒泡排序B. 快速排序C. 简单插入排序D. 堆排序33. 下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是______。A. 在顺序存储的线性表中寻找最大项B. 在顺序存储的线性表中进行顺序查找C. 在顺序存储的有序表中进行对分查找D. 在链式存储的有序表中进行查找34. 设表的长度为n。下列查找算法中，在最坏情况下，比较次数最少的是______。A. 顺序查找B. 有序表的二分查找C. 寻找最大项D. 寻找最小项35. 下列叙述中错误的是______。A. 向量是线性结构B. 非空线性结构中只有一个结点没有前件C. 非空线性结构中只有一个结点没有后件D. 只有一个根结点和一个叶子结点的结构必定是线性结构36. 设表的长度为n。在下列算法中，最坏情况下时间复杂度最高的是______。A. 有序链表查找B. 循环链表中寻找最大项C. 希尔排序D. 堆排序37. 设顺序表的长度为16，对该表进行简单插入排序。在最坏情况下需要的比较次数为______。A. 120B. 60C. 30D. 1538. 下列叙述中正确的是______。A. 快速排序适用于链式存储的线性表B. 快速排序法适用于顺序存储的线性表C. 链式存储的线性表不可能排序D. 堆排序适用于非线性结构39. 下列叙述中正确的是______。A. 循环链表中至少有一个结点B. 双向链表有两个头指针C. 双向链表有两个头结点D. 循环链表是循环队列的链式存储结构40. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队，然后依次轮流出栈和退队，则输出序列为______。A. G,B,E,D,C,F,A,HB. B,G,D,E,F,C,H,AC. D,C,B,A,E,F,G,HD. A,B,C,D,H,G,F,E41. 设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则按层次输出（从上到下，同一层从左到右）的序列为______。A. DGHEBIJFCAB. JIHGFEDCBAC. GHIJDEFBCAD. ABCDEFGHIJ42. 树的度为3，且有9个度为3的结点，20个叶子结点，但没有度为1的结点。则该树总的结点数为______。A. 30B. 29C. 47D. 不可能有这样的树43. 树的度为3，且有9个度为3的结点，20个叶子结点，但没有度为1的结点。则该树中度为2的结点数为______。A. 7B. 0C. 1D. 不可能有这样的树44. 某二叉树有49个度为2的结点，4个度为1的结点，则______。A. 该二叉树共有103个结点B. 该二叉树的结点数不确定C. 该二叉树共有101个结点D. 不可能有这样的二叉树45. 循环队列的存储空间为Q(1:50)，初始状态为空。经过一系列正常的入队与退队操作后，front=25，rear=25。此时该循环队列中的元素个数为______。A. 0或50B. 0C. 50D. 2546. 循环队列的存储空间为Q(1:50)，初始状态为空。经过一系列正常的入队与退队操作后，front=24，rear=25。此时该循环队列中的元素个数为______。A. 1B. 49C. 50D. 2547. 设二叉树的前序序列为ABCDEF，中序序列为ABCDEF，则该二叉树的深度为（根结点为第1层）______。A. 4B. 2C. 3D. 648. 设二叉树的前序序列为ABCDEF，中序序列为BDFECA，则该二叉树的后序序列为______。A. ABCDEFB. FEDCBAC. BDFECAD. CBAFED49. 对如下二叉树进行后序遍历的结果为______。 A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA50. 某系统结构图如下图所示，该系统结构图的深度是______。 A. 4B. 3C. 2D. 151. 对下列二叉树进行中序遍历的结果是______。 A. ACBDFEGB. ACBDFGEC. ABDCGEFD. FCADBEG52. 对下列二叉树进行前序遍历的结果为______。 A. DYBEAFCZXB. YDEBFZXCAC. ABDYECFXZD. ABCDEFXYZ53. 设二叉树如下，则后序序列为______。 A. ABDEGCFHB. DBGEAFHCC. DGEBHFCAD. ABCDEFGH 提交成功！
4. 一个栈的初始状态为空，现将元素A,B,C,D,E依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队（原队列为空），最后将队列中的元素全部退出。则元素退队的顺序为______。A. ABCB. CBAC. EDCD. CDE
5. [(3)快速排序：通常，快速排序被认为是，所有同数量级(O(nlogn))的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]
11. 下列关于线性链表的叙述中，正确的是______。A. 各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B. 各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C. 进行插入和删除时，不需要移动表中的元素D. 以上三种说法都不对
12. [(1)快速排序：通常，快速排序被认为是所有同数量级O(nlogn)的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。]
14. [希尔排序法属于插入类排序，但它对简单插入排序做了较大的改进。基本思想是：将整个无序序列分割成若干小的子序列分别进行插入排序。在希尔排序过程中，虽然对于每一个子表采用的仍是插入排序，但是，在子表中每进行一次比较久有可能移去整个线性表中的多个逆序，从而改善了整个排序过程的性能。最欢情况下，希尔排序所需要的比较次数为O(n1.5)。]
15. 下列叙述中正确的是______。A. 所谓有序表是指在顺序存储空间内连续存放的元素序列B. 有序表只能顺序存储在连续的存储空间内C. 有序表可以用链接存储方式存储在不连续的存储空间内D. 任何存储方式的有序表均能采用二分法进行查找
27. 下列关于算法复杂度叙述正确的是______。A. 最坏情况下的时间复杂度一定高于平均情况的时间复杂度B. 时间复杂度与所用的计算工具无关C. 对同一个问题，采用不同的算法，则它们的时间复杂度是相同的D. 时间复杂度与采用的算法描述语言有关
28. 设循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。现经过一系列入队与退队操作后，front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为______。A. 1B. 2C. 3D. 52
31. 一个栈的初始状态为空。现将元素1,2,3,A,B,C依次入栈，然后再依次出栈，则元素出栈的顺序是______。A. 1,2,3,A,B,CB. C,B,A,1,2,3C. C,B,A,3,2,1D. 1,2,3,C,B,A
33. 下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是______。A. 在顺序存储的线性表中寻找最大项B. 在顺序存储的线性表中进行顺序查找C. 在顺序存储的有序表中进行对分查找D. 在链式存储的有序表中进行查找
40. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队，然后依次轮流出栈和退队，则输出序列为______。A. G,B,E,D,C,F,A,HB. B,G,D,E,F,C,H,AC. D,C,B,A,E,F,G,HD. A,B,C,D,H,G,F,E
41. 设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则按层次输出（从上到下，同一层从左到右）的序列为______。A. DGHEBIJFCAB. JIHGFEDCBAC. GHIJDEFBCAD. ABCDEFGHIJ
45. 循环队列的存储空间为Q(1:50)，初始状态为空。经过一系列正常的入队与退队操作后，front=25，rear=25。此时该循环队列中的元素个数为______。A. 0或50B. 0C. 50D. 25
46. 循环队列的存储空间为Q(1:50)，初始状态为空。经过一系列正常的入队与退队操作后，front=24，rear=25。此时该循环队列中的元素个数为______。A. 1B. 49C. 50D. 25