全国二级理论——1.2数据结构与算法 本套试题共50题。 1. 班级:格式如“19计应31”2. 学号:10位数完整格式3. 姓名:4. 在长度为n的有序线性表中进行二分查找,最坏情况下需要比较的次数是______。A. O(n)B. O(n2)C. O(log2n)D. O(nlog2n)5. 某二叉树共有845个结点,其中叶子结点有45个,则度为1的结点数为______。A. 400B. 754C. 756D. 不确定6. 在长度为64的有序线性表中进行顺序查找,最坏情况下需要比较的次数为______。A. 63B. 64C. 6D. 77. 下列叙述中正确的是______。A. 算法的复杂度用于衡量算法的控制结构B. 算法的有穷性是指算法的规模不能太大C. 程序可以作为算法的一种表达方式D. 算法的效率与数据的存储结构无关8. 设循环队列为Q(1:m),其初始状态为front=rear=m。经过一系列入队与退队运算后,front=20,rear=15。现要在该循环队列中寻找最小值的元素,最坏情况下需要比较的次数为______。A. 5B. 6C. m-5D. m-69. 下列叙述中正确的是______。A. 存储空间连续的数据结构一定是线性结构B. 存储空间不连续的数据结构一定是非线性结构C. 没有根结点的非空数据结构一定是线性结构D. 具有两个根结点的数据结构一定是非线性结构10. 循环队列的存储空间为Q(1:50)。经过一系列正常的入队与退队操作后,front=rear=25。后又成功地将一个元素退队,此时队列中的元素个数为______。A. 26B. 0C. 24D. 4911. 下列关于栈叙述正确的是______。A. 栈顶元素最先能被删除B. 栈顶元素最后才能被删除C. 栈底元素永远不能被删除D. 以上三种说法都不对12. 下列算法中,最坏情况下时间复杂度为O(log2n)的是______。A. 二分查找法B. 堆排序C. 快速排序D. 顺序查找法13. [(2)直接插入排序:每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。直接插入排序属于稳定的排序,最坏时间复杂度为O(n2)。]14. [(4)希尔排序:将整个无序序列分割成若干小的子序列分别进行插入排序。在最坏情况下,希尔排序所需的比较次数为O(n1.5)。]15. 以下数据结构中不属于线性数据结构的是______。A. 队列B. 线性表C. 二叉树D. 栈16. 下列关于队列的叙述中正确的是______。A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表17. 在排序过程中,每一次数据元素的移动会产生新的逆序的排序方法是______。A. 简单插入排序B. 快速排序C. 冒泡排序D. 以上说法均不正确18. 在线性表的链式存储结构中,其存储空间一般是不连续的,并且______。A. 前件结点的存储序号小于后件结点的存储序号B. 前件结点的存储序号大于后件结点的存储序号C. 前件结点的存储序号可以小于也可以大于后件结点的存储序号D. 以上选项都不对19. 设某二叉树的前序序列与中序序列均为ABCDEFGH,则该二叉树的后序序列为______。A. EFGHABCDB. HGFEDCBAC. DCBAHGFED. ABCDEFGH20. [所谓简单插入排序,是指将无序序列中的各元素依次插入到已经有序的线性表中。在简单插入排序中,每一次比较后最多移掉一个逆序,因此,这种排序方法的效率与冒泡排序法相同。在最坏情况下,简单插入排序需要n(n-1)/2次比较。]21. [(4)堆排序法:堆排序的方法为:①首先将一个无序序列建成堆。②然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。堆排序在最坏的情况下,其时间复杂度为O(nlog2n)。]22. 带链的栈与顺序存储的栈相比,其优点是______。A. 入栈与退栈操作方便B. 可以省略栈底指针C. 入栈操作时不会受栈存储空间的限制而发生溢出D. 以上选项都不是23. 设循环队列的存储空间为Q(1:m),初始状态为空。现经过一系列正常的入队与退队操作后,front=m,rear=m-1,此后从该循环队列中删除一个元素,则队列中的元素个数为______。A. 1B. m-2C. m-1D. 024. 下列排序方法中,最坏情况下时间复杂度最小的是______。A. 冒泡排序B. 快速排序C. 堆排序D. 希尔排序25. 下列叙述中正确的是______。A. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B. 循环队列中的元素个数随队头指针的变化而动态变化C. 循环队列中的元素个数随队尾指针的变化而动态变化D. 以上说法都不对26. 设循环队列的存储空间为Q(1:m),初始状态为空。现经过一系列正常的入队与退队操作后,front=m-1,rear=m,此后再向该循环队列中插入一个元素,则队列中的元素个数为______。A. m-1B. 1C. 2D. m27. 下列叙述中正确的是______。A. 线性表链式存储结构的存储空间一般要少于顺序存储结构B. 线性表链式存储结构与顺序存储结构的存储空间都是连续的C. 线性表链式存储结构的存储空间可以是连续的,也可以是不连续的D. 以上说法都不对28. 下列叙述中正确的是______。A. 在栈中,栈中元素随栈底指针与栈顶指针的变化而动态变化B. 在栈中,栈顶指针不变,栈中元素随栈底指针的变化而动态变化C. 在栈中,栈底指针不变,栈中元素随栈顶指针的变化而动态变化D. 上述三种说法都不对29. 下列叙述中错误的是______。A. 二分查找法只适用于顺序存储的线性有序表B. 所有二叉树都只能用二叉链表表示C. 有多个指针域的链表也有可能是线性结构D. 循环队列是队列的存储结构30. 设栈的顺序存储空间为 S(1:m),初始状态为top=0,则栈中的数据元素个数为______。A. m-topB. m-top+1C. topD. top-m31. 一个栈的初始状态为空。现将元素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. 设数据集合为D={1,2,3,4,5},下列数据结构B=(D,R)中为非线性结构的是______。A. R={(1,2),(2,3),(4,3),(3,5)}B. R={(1,2),(2,3),(3,4),(4,5)}C. R={(5,4),(4,3),(3,2),(2,1)}D. R={(2,5),(5,4),(3,2),(4,3)}33. 某二叉树共有400个结点,其中有99个度为1的结点,则该二叉树中的叶子结点数为______。A. 149B. 150C. 151D. 不可能有这样的二叉树34. 在具有2n个结点的完全二叉树中,叶子结点个数为______。A. n/2B. n+1C. n-1D. n35. 设栈的存储空间为S(1:50),初始状态为top=0。现经过一系列正常的入栈与退栈操作后,top=51,则栈中的元素个数为______。A. 1B. 50C. 0D. 不可能36. 设数据结构B=(D, R),其中:D={ a, b, c, d, e, f };R={ (a, b), (b, c), (c, d), (d, e), (e, f), (f, a) },该数据结构为______。A. 线性结构B. 循环队列C. 循环链表D. 非线性结构37. 下列叙述中错误的是______。A. 具有两个根结点的数据结构一定属于非线性结构B. 具有两个以上叶子结点的数据结构一定属于非线性结构C. 具有两个以上指针域的链式结构一定属于非线性结构D. 具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构38. 在快速排序法中,每经过一次数据交换(或移动)后______。A. 能消除多个逆序B. 只能消除一个逆序C. 不会产生新的逆序D. 消除的逆序个数一定比新产生的逆序个数多39. 设栈的顺序存储空间为S(1:m),初始状态为top=-1,则栈中的数据元素个数为______。A. top+1B. m-top+1C. m-topD. top-m40. 设二叉树共有500个结点,其中叶子结点有250个。则度为2的结点个数是______。A. 249B. 1C. 0D. 不可能有这样的二叉树41. 下列叙述中正确的是______。A. 循环队列是线性逻辑结构B. 循环队列是线性结构C. 循环队列是链式存储结构D. 循环队列是非线性存储结构42. 循环队列的存储空间为Q(0:59),初始状态为空。经过一系列正常的入队与退队操作后,front=25,rear=24。循环队列中的元素个数为______。A. 60B. 59C. 2D. 143. 下列叙述中错误的是______。A. 具有多个指针域的链表也可能是线性结构B. 循环队列属于线性结构C. 采用顺序存储的完全二叉树属于线性结构D. 具有两个以上根结点的数据结构一定是非线性结构44. 树的度为3,且有9个度为3的结点,5个度为1的结点,但没有度为2的结点。则该树总的结点数为______。A. 33B. 14C. 32D. 1945. 树的度为3,且有9个度为3的结点,20个叶子结点,但没有度为1的结点。则该树总的结点数为______。A. 30B. 29C. 47D. 不可能有这样的树46. 某二叉树的后序序列为DEBFGCA,中序序列为DBEAFCG,则前序序列为______。A. ACFGBDEB. ABCDEFGC. ABDECFGD. ADEBFGC47. 设某树的度为3,且度为3的结点数为5,度为1的结点数为6,没有度为2的结点。则该树中的叶子结点数为______。A. 11B. 22C. 20D. 不可能有这样的树48. 设栈的存储空间为S(1:60),初始状态为top=61。现经过一系列正常的入栈与退栈操作后,top=1,则栈中的元素个数为______。A. 59B. 0C. 1D. 6049. 某系统结构图如下图所示(n≥5),该系统结构图的最大扇出数是______。 A. 2B. 3C. nD. n+150. 某系统总体结构如下图所示,该系统结构图的宽度是______。 A. 5B. 4C. 3D. 251. 对如下二叉树进行后序遍历的结果为______。 A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA52. 某系统总体结构如下图所示,该系统结构图的深度是______。 A. 4B. 3C. 2D. 153. 某系统总体结构图如下图所示,该系统总体结构图的深度是______。 A. 7B. 6C. 3D. 2 提交成功!
全国二级理论——1.2数据结构与算法 本套试题共50题。 1. 班级:格式如“19计应31”2. 学号:10位数完整格式3. 姓名:4. 在长度为n的有序线性表中进行二分查找,最坏情况下需要比较的次数是______。A. O(n)B. O(n2)C. O(log2n)D. O(nlog2n)5. 某二叉树共有845个结点,其中叶子结点有45个,则度为1的结点数为______。A. 400B. 754C. 756D. 不确定6. 在长度为64的有序线性表中进行顺序查找,最坏情况下需要比较的次数为______。A. 63B. 64C. 6D. 77. 下列叙述中正确的是______。A. 算法的复杂度用于衡量算法的控制结构B. 算法的有穷性是指算法的规模不能太大C. 程序可以作为算法的一种表达方式D. 算法的效率与数据的存储结构无关8. 设循环队列为Q(1:m),其初始状态为front=rear=m。经过一系列入队与退队运算后,front=20,rear=15。现要在该循环队列中寻找最小值的元素,最坏情况下需要比较的次数为______。A. 5B. 6C. m-5D. m-69. 下列叙述中正确的是______。A. 存储空间连续的数据结构一定是线性结构B. 存储空间不连续的数据结构一定是非线性结构C. 没有根结点的非空数据结构一定是线性结构D. 具有两个根结点的数据结构一定是非线性结构10. 循环队列的存储空间为Q(1:50)。经过一系列正常的入队与退队操作后,front=rear=25。后又成功地将一个元素退队,此时队列中的元素个数为______。A. 26B. 0C. 24D. 4911. 下列关于栈叙述正确的是______。A. 栈顶元素最先能被删除B. 栈顶元素最后才能被删除C. 栈底元素永远不能被删除D. 以上三种说法都不对12. 下列算法中,最坏情况下时间复杂度为O(log2n)的是______。A. 二分查找法B. 堆排序C. 快速排序D. 顺序查找法13. [(2)直接插入排序:每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。直接插入排序属于稳定的排序,最坏时间复杂度为O(n2)。]14. [(4)希尔排序:将整个无序序列分割成若干小的子序列分别进行插入排序。在最坏情况下,希尔排序所需的比较次数为O(n1.5)。]15. 以下数据结构中不属于线性数据结构的是______。A. 队列B. 线性表C. 二叉树D. 栈16. 下列关于队列的叙述中正确的是______。A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表17. 在排序过程中,每一次数据元素的移动会产生新的逆序的排序方法是______。A. 简单插入排序B. 快速排序C. 冒泡排序D. 以上说法均不正确18. 在线性表的链式存储结构中,其存储空间一般是不连续的,并且______。A. 前件结点的存储序号小于后件结点的存储序号B. 前件结点的存储序号大于后件结点的存储序号C. 前件结点的存储序号可以小于也可以大于后件结点的存储序号D. 以上选项都不对19. 设某二叉树的前序序列与中序序列均为ABCDEFGH,则该二叉树的后序序列为______。A. EFGHABCDB. HGFEDCBAC. DCBAHGFED. ABCDEFGH20. [所谓简单插入排序,是指将无序序列中的各元素依次插入到已经有序的线性表中。在简单插入排序中,每一次比较后最多移掉一个逆序,因此,这种排序方法的效率与冒泡排序法相同。在最坏情况下,简单插入排序需要n(n-1)/2次比较。]21. [(4)堆排序法:堆排序的方法为:①首先将一个无序序列建成堆。②然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。堆排序在最坏的情况下,其时间复杂度为O(nlog2n)。]22. 带链的栈与顺序存储的栈相比,其优点是______。A. 入栈与退栈操作方便B. 可以省略栈底指针C. 入栈操作时不会受栈存储空间的限制而发生溢出D. 以上选项都不是23. 设循环队列的存储空间为Q(1:m),初始状态为空。现经过一系列正常的入队与退队操作后,front=m,rear=m-1,此后从该循环队列中删除一个元素,则队列中的元素个数为______。A. 1B. m-2C. m-1D. 024. 下列排序方法中,最坏情况下时间复杂度最小的是______。A. 冒泡排序B. 快速排序C. 堆排序D. 希尔排序25. 下列叙述中正确的是______。A. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B. 循环队列中的元素个数随队头指针的变化而动态变化C. 循环队列中的元素个数随队尾指针的变化而动态变化D. 以上说法都不对26. 设循环队列的存储空间为Q(1:m),初始状态为空。现经过一系列正常的入队与退队操作后,front=m-1,rear=m,此后再向该循环队列中插入一个元素,则队列中的元素个数为______。A. m-1B. 1C. 2D. m27. 下列叙述中正确的是______。A. 线性表链式存储结构的存储空间一般要少于顺序存储结构B. 线性表链式存储结构与顺序存储结构的存储空间都是连续的C. 线性表链式存储结构的存储空间可以是连续的,也可以是不连续的D. 以上说法都不对28. 下列叙述中正确的是______。A. 在栈中,栈中元素随栈底指针与栈顶指针的变化而动态变化B. 在栈中,栈顶指针不变,栈中元素随栈底指针的变化而动态变化C. 在栈中,栈底指针不变,栈中元素随栈顶指针的变化而动态变化D. 上述三种说法都不对29. 下列叙述中错误的是______。A. 二分查找法只适用于顺序存储的线性有序表B. 所有二叉树都只能用二叉链表表示C. 有多个指针域的链表也有可能是线性结构D. 循环队列是队列的存储结构30. 设栈的顺序存储空间为 S(1:m),初始状态为top=0,则栈中的数据元素个数为______。A. m-topB. m-top+1C. topD. top-m31. 一个栈的初始状态为空。现将元素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. 设数据集合为D={1,2,3,4,5},下列数据结构B=(D,R)中为非线性结构的是______。A. R={(1,2),(2,3),(4,3),(3,5)}B. R={(1,2),(2,3),(3,4),(4,5)}C. R={(5,4),(4,3),(3,2),(2,1)}D. R={(2,5),(5,4),(3,2),(4,3)}33. 某二叉树共有400个结点,其中有99个度为1的结点,则该二叉树中的叶子结点数为______。A. 149B. 150C. 151D. 不可能有这样的二叉树34. 在具有2n个结点的完全二叉树中,叶子结点个数为______。A. n/2B. n+1C. n-1D. n35. 设栈的存储空间为S(1:50),初始状态为top=0。现经过一系列正常的入栈与退栈操作后,top=51,则栈中的元素个数为______。A. 1B. 50C. 0D. 不可能36. 设数据结构B=(D, R),其中:D={ a, b, c, d, e, f };R={ (a, b), (b, c), (c, d), (d, e), (e, f), (f, a) },该数据结构为______。A. 线性结构B. 循环队列C. 循环链表D. 非线性结构37. 下列叙述中错误的是______。A. 具有两个根结点的数据结构一定属于非线性结构B. 具有两个以上叶子结点的数据结构一定属于非线性结构C. 具有两个以上指针域的链式结构一定属于非线性结构D. 具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构38. 在快速排序法中,每经过一次数据交换(或移动)后______。A. 能消除多个逆序B. 只能消除一个逆序C. 不会产生新的逆序D. 消除的逆序个数一定比新产生的逆序个数多39. 设栈的顺序存储空间为S(1:m),初始状态为top=-1,则栈中的数据元素个数为______。A. top+1B. m-top+1C. m-topD. top-m40. 设二叉树共有500个结点,其中叶子结点有250个。则度为2的结点个数是______。A. 249B. 1C. 0D. 不可能有这样的二叉树41. 下列叙述中正确的是______。A. 循环队列是线性逻辑结构B. 循环队列是线性结构C. 循环队列是链式存储结构D. 循环队列是非线性存储结构42. 循环队列的存储空间为Q(0:59),初始状态为空。经过一系列正常的入队与退队操作后,front=25,rear=24。循环队列中的元素个数为______。A. 60B. 59C. 2D. 143. 下列叙述中错误的是______。A. 具有多个指针域的链表也可能是线性结构B. 循环队列属于线性结构C. 采用顺序存储的完全二叉树属于线性结构D. 具有两个以上根结点的数据结构一定是非线性结构44. 树的度为3,且有9个度为3的结点,5个度为1的结点,但没有度为2的结点。则该树总的结点数为______。A. 33B. 14C. 32D. 1945. 树的度为3,且有9个度为3的结点,20个叶子结点,但没有度为1的结点。则该树总的结点数为______。A. 30B. 29C. 47D. 不可能有这样的树46. 某二叉树的后序序列为DEBFGCA,中序序列为DBEAFCG,则前序序列为______。A. ACFGBDEB. ABCDEFGC. ABDECFGD. ADEBFGC47. 设某树的度为3,且度为3的结点数为5,度为1的结点数为6,没有度为2的结点。则该树中的叶子结点数为______。A. 11B. 22C. 20D. 不可能有这样的树48. 设栈的存储空间为S(1:60),初始状态为top=61。现经过一系列正常的入栈与退栈操作后,top=1,则栈中的元素个数为______。A. 59B. 0C. 1D. 6049. 某系统结构图如下图所示(n≥5),该系统结构图的最大扇出数是______。 A. 2B. 3C. nD. n+150. 某系统总体结构如下图所示,该系统结构图的宽度是______。 A. 5B. 4C. 3D. 251. 对如下二叉树进行后序遍历的结果为______。 A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA52. 某系统总体结构如下图所示,该系统结构图的深度是______。 A. 4B. 3C. 2D. 153. 某系统总体结构图如下图所示,该系统总体结构图的深度是______。 A. 7B. 6C. 3D. 2 提交成功!
8. 设循环队列为Q(1:m),其初始状态为front=rear=m。经过一系列入队与退队运算后,front=20,rear=15。现要在该循环队列中寻找最小值的元素,最坏情况下需要比较的次数为______。A. 5B. 6C. m-5D. m-6
9. 下列叙述中正确的是______。A. 存储空间连续的数据结构一定是线性结构B. 存储空间不连续的数据结构一定是非线性结构C. 没有根结点的非空数据结构一定是线性结构D. 具有两个根结点的数据结构一定是非线性结构
10. 循环队列的存储空间为Q(1:50)。经过一系列正常的入队与退队操作后,front=rear=25。后又成功地将一个元素退队,此时队列中的元素个数为______。A. 26B. 0C. 24D. 49
18. 在线性表的链式存储结构中,其存储空间一般是不连续的,并且______。A. 前件结点的存储序号小于后件结点的存储序号B. 前件结点的存储序号大于后件结点的存储序号C. 前件结点的存储序号可以小于也可以大于后件结点的存储序号D. 以上选项都不对
20. [所谓简单插入排序,是指将无序序列中的各元素依次插入到已经有序的线性表中。在简单插入排序中,每一次比较后最多移掉一个逆序,因此,这种排序方法的效率与冒泡排序法相同。在最坏情况下,简单插入排序需要n(n-1)/2次比较。]
21. [(4)堆排序法:堆排序的方法为:①首先将一个无序序列建成堆。②然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。堆排序在最坏的情况下,其时间复杂度为O(nlog2n)。]
23. 设循环队列的存储空间为Q(1:m),初始状态为空。现经过一系列正常的入队与退队操作后,front=m,rear=m-1,此后从该循环队列中删除一个元素,则队列中的元素个数为______。A. 1B. m-2C. m-1D. 0
25. 下列叙述中正确的是______。A. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B. 循环队列中的元素个数随队头指针的变化而动态变化C. 循环队列中的元素个数随队尾指针的变化而动态变化D. 以上说法都不对
26. 设循环队列的存储空间为Q(1:m),初始状态为空。现经过一系列正常的入队与退队操作后,front=m-1,rear=m,此后再向该循环队列中插入一个元素,则队列中的元素个数为______。A. m-1B. 1C. 2D. m
27. 下列叙述中正确的是______。A. 线性表链式存储结构的存储空间一般要少于顺序存储结构B. 线性表链式存储结构与顺序存储结构的存储空间都是连续的C. 线性表链式存储结构的存储空间可以是连续的,也可以是不连续的D. 以上说法都不对
28. 下列叙述中正确的是______。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,A
32. 设数据集合为D={1,2,3,4,5},下列数据结构B=(D,R)中为非线性结构的是______。A. R={(1,2),(2,3),(4,3),(3,5)}B. R={(1,2),(2,3),(3,4),(4,5)}C. R={(5,4),(4,3),(3,2),(2,1)}D. R={(2,5),(5,4),(3,2),(4,3)}
36. 设数据结构B=(D, R),其中:D={ a, b, c, d, e, f };R={ (a, b), (b, c), (c, d), (d, e), (e, f), (f, a) },该数据结构为______。A. 线性结构B. 循环队列C. 循环链表D. 非线性结构
37. 下列叙述中错误的是______。A. 具有两个根结点的数据结构一定属于非线性结构B. 具有两个以上叶子结点的数据结构一定属于非线性结构C. 具有两个以上指针域的链式结构一定属于非线性结构D. 具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构