全国二级理论——1.2数据结构与算法 本套试题共50题。 1. 班级:格式如“19计应31”2. 学号:10位数完整格式3. 姓名:4. 一个栈的初始状态为空,现将元素A,B,C,D,E依次入栈,然后依次退栈三次,并将退栈的三个元素依次入队(原队列为空),最后将队列中的元素全部退出。则元素退队的顺序为______。A. ABCB. CBAC. EDCD. CDE5. 下列叙述中错误的是______。A. 在双向链表中,可以从任何一个结点开始直接遍历到所有结点B. 在循环链表中,可以从任何一个结点开始直接遍历到所有结点C. 在线性单链表中,可以从任何一个结点开始直接遍历到所有结点D. 在二叉链表中,可以从根结点开始遍历到所有结点6. 设循环队列为Q(1:m),其初始状态为front=rear=m。经过一系列入队与退队运算后,front=15,rear=20。现要在该循环队列中寻找最大值的元素,最坏情况下需要比较的次数为______。A. 4B. 6C. m-5D. m-67. 下列数据结构中,能用二分法进行查找的是______。A. 顺序存储的有序线性表B. 线性链表C. 二叉链表D. 有序线性链表8. 某二叉树共有150个结点,其中有50个度为1的结点,则______。A. 不存在这样的二叉树B. 该二叉树有49个叶子结点C. 该二叉树有50个叶子结点D. 该二叉树有51个叶子结点9. 设数据元素的集合D={1,2,3,4,5},则满足下列关系R的数据结构中为线性结构的是______。A. R={(1,2),(3,2),(5,1),(4,5)}B. R={(1,3),(4,1),(3,2),(5,4)}C. R={(1,2),(2,4),(4,5),(2,3)}D. R={(1,3),(2,4),(3,5),(1,2)}10. [所谓简单插入排序,是指将无序序列中的各元素依次插入到已经有序的线性表中。在简单插入排序中,每一次比较后最多移掉一个逆序,因此,这种排序方法的效率与冒泡排序法相同。在最坏情况下,简单插入排序需要n(n-1)/2次比较。]11. n个顶点的强连通图的边数至少有______。A. n-1B. n(n-1)C. nD. n+112. 冒泡排序在最坏情况下的比较次数是______。A. n(n+1)/2B. nlog2nC. n(n-1)/2D. n/213. 设循环队列为Q(1: m),其初始状态为front=rear=m。经过一系列入队与退队运算后,front=30,rear=10。现要在该循环队列中作顺序查找,最坏情况下需要比较的次数为______。A. 19B. 20C. m-19D. m-2014. 某二叉树共有13个结点,其中有4个度为1的结点,则叶子结点数为______。A. 5B. 4C. 3D. 215. 若某二叉树中的所有结点值均大于其左子树上的所有结点值,且小于右子树上的所有结点值,则该二叉树遍历序列中有序的是______。A. 前序序列B. 中序序列C. 后序序列D. 以上说法均不正确16. 希尔排序法属于哪一种类型的排序法______。A. 交换类排序法B. 插入类排序法C. 选择类排序法D. 建堆排序法17. 某循环队列的存储空间为Q(1:m),初始状态为front=rear=m。现经过一系列的入队操作和退队操作后,front=m-1,rear=m,则该循环队列中的元素个数为______。A. 0B. m-1C. mD. 118. 在下列选项中,哪个不是一个算法一般应该具有的基本特征______。A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报19. 设循环队列的存储空间为Q(1:m),初始状态为空。现经过一系列正常的入队与退队操作后,front=m,rear=m-1,此后从该循环队列中删除一个元素,则队列中的元素个数为______。A. 1B. m-2C. m-1D. 020. 下列关于二叉树的叙述中,正确的是______。A. 叶子结点总是比度为2的结点少一个B. 叶子结点总是比度为2的结点多一个C. 叶子结点数是度为2的结点数的两倍D. 度为2的结点数是度为1的结点数的两倍21. 下列关于栈的描述中错误的是______。A. 栈是先进后出的线性表B. 栈只能顺序存储C. 栈具有记忆作用D. 对栈的插入与删除操作中,不需要改变栈底指针22. 下列叙述中正确的是______。A. 栈是"先进先出"的线性表B. 队列是"先进后出"的线性表C. 循环队列是非线性结构D. 有序线性表既可以采用顺序存储结构,也可以采用链式存储结构23. 线性表的链式存储结构与顺序存储结构相比,链式存储结构的优点有______。A. 节省存储空间B. 插入与删除运算效率高C. 便于查找D. 排序时减少元素的比较次数24. 下列叙述中正确的是______。A. 栈与队列都只能顺序存储B. 循环队列是队列的顺序存储结构C. 循环链表是循环队列的链式存储结构D. 循环队列不是队列的顺序存储结构25. 下列叙述中正确的是______。A. 二分查找法只适用于顺序存储的有序线性表B. 二分查找法适用于任何存储结构的有序线性表C. 算法的时间复杂度是指设计算法的工作量D. 二分查找法适用于有序双向链表26. 对长度为n的线性表排序,在最坏情况下,比较次数不是n(n-1)/2的排序方法是______。A. 快速排序B. 冒泡排序C. 直接插入排序D. 堆排序27. 栈和队列的共同点是______。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点28. [(1)快速排序:通常,快速排序被认为是所有同数量级O(nlogn)的排序方法中,其平均性能最好。但是,若初始记录序列按关键字有序或基本有序时,快速排序将蜕化为起泡排序,其时间复杂度为O(n2)。]29. 设栈的顺序存储空间为 S(1:m),初始状态为top=0,则栈中的数据元素个数为______。A. m-topB. m-top+1C. topD. top-m30. 一个栈的初始状态为空。现将元素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,A31. 循环队列的存储空间为Q(1:40),初始状态为front=rear=40。经过一系列正常的入队与退队操作后,front=rear=15,此后又退出一个元素,则循环队列中的元素个数为______。A. 39,或0且产生下溢错误B. 40C. 15D. 1432. 下列叙述中正确的是______。A. 在循环队列中,队头指针和队尾指针的动态变化决定队列的长度B. 在循环队列中,队尾指针的动态变化决定队列的长度C. 在带链的队列中,队头指针与队尾指针的动态变化决定队列的长度D. 在带链的栈中,栈顶指针的动态变化决定栈中元素的个数33. 设栈的存储空间为S(1:50),初始状态为top=0。现经过一系列正常的入栈与退栈操作后,top=51,则栈中的元素个数为______。A. 1B. 50C. 0D. 不可能34. 设数据结构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. 非线性结构35. 某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后,front=rear=10。该队列中的元素个数为______。A. 1B. 0C. 1或0D. 不确定36. 设有一个栈与一个队列的初始状态均为空。现有一个序列A,B,C,D,E,F,G,H。先分别将序列中的前4个元素依次入栈,后4个元素依次入队;然后分别将栈中的元素依次退栈,再将队列中的元素依次退队。最后得到的序列为______。A. D,C,B,A,E,F,G,HB. D,C,B,A,H,G,F,EC. A,B,C,D,E,F,G,HD. A,B,C,D,H,G,F,E37. 下列叙述中正确的是______。A. 数组是长度固定的线性表B. 矩阵是非线性结构C. 对线性表只能作插入与删除运算D. 线性表中各元素的数据类型可以不同38. 设一棵度为3的树,其中度为2,1,0的结点数分别为3,4,15。则该树中总结点数为______。A. 30B. 22C. 55D. 不可能有这样的树39. 下列叙述中正确的是______。A. 线性链表可以有多个指针域B. 有两个以上指针域的链表是非线性结构C. 只有一个指针域的链表一定是线性结构D. 线性链表最多可以有两个指针域40. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入队和入栈,然后依次轮流退队和出栈,则输出序列为______。A. A,H,C,F,E,D,G,BB. G,E,C,A,B,D,F,HC. D,C,B,A,E,F,G,HD. A,B,C,D,H,G,F,E41. 某二叉树有49个度为2的结点,4个度为1的结点,30个叶子结点,则______。A. 不可能有这样的二叉树B. 该二叉树只能有83个结点C. 这样的二叉树不惟一D. 该二叉树共有103个结点42. 设栈与队列初始状态为空。首先A,B,C,D,E依次入栈,再F,G,H,I,J依次入队;然后依次出队至队空,再依次出栈至栈空。则输出序列为______。A. E,D,C,B,A,F,G,H,I,JB. E,D,C,B,A,J,I,H,G,FC. F,G,H,I,J,A,B,C,D,ED. F,G,H,I,J,E,D,C,B,A43. 对长度为8的数组进行快速排序,最多需要的比较次数为______。A. 28B. 64C. 56D. 844. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队,然后依次轮流退队和出栈,则输出序列为______。A. B,G,D,E,F,C,H,AB. G,B,E,D,C,F,A,HC. D,C,B,A,E,F,G,HD. A,B,C,D,H,G,F,E45. 下列各组算法中,最坏情况下其时间复杂度相同的是______。A. 冒泡排序与快速排序B. 直接插入排序与希尔排序C. 简单选择排序与堆排序D. 快速排序与希尔排序46. 某二叉树的后序序列为DEBFGCA,中序序列为DBEAFCG,则前序序列为______。A. ACFGBDEB. ABCDEFGC. ABDECFGD. ADEBFGC47. 设某树的度为3,且度为3的结点数为4,度为1的结点数为9,没有度为2的结点。则该树中的叶子结点数为______。A. 9B. 1C. 4D. 不可能有这样的树48. 设二叉树的前序序列为ABCDEF,中序序列为ABCDEF,则该二叉树的后序序列为______。A. FEDCBAB. ABCDEFC. DEFCBAD. CBAFED49. 某系统结构图如下图所示(n≥5),该系统结构图的最大扇出数是______。 A. 2B. 3C. nD. n+150. 某系统总体结构如下图所示,系统结构图的最大扇入数是______。 A. 2B. 3C. 4D. 551. 设二叉树如下,则中序序列为______。 A. ABDEGCFHB. DBGEAFHCC. DGEBHFCAD. ABCDEFGH52. 对下列二叉树进行前序遍历的结果为______。 A. DYBEAFCZXB. YDEBFZXCAC. ABDYECFXZD. ABCDEFXYZ53. 某系统结构图如下图所示,该系统结构图的深度是______。 A. 4B. 3C. 2D. 1 提交成功!
全国二级理论——1.2数据结构与算法 本套试题共50题。 1. 班级:格式如“19计应31”2. 学号:10位数完整格式3. 姓名:4. 一个栈的初始状态为空,现将元素A,B,C,D,E依次入栈,然后依次退栈三次,并将退栈的三个元素依次入队(原队列为空),最后将队列中的元素全部退出。则元素退队的顺序为______。A. ABCB. CBAC. EDCD. CDE5. 下列叙述中错误的是______。A. 在双向链表中,可以从任何一个结点开始直接遍历到所有结点B. 在循环链表中,可以从任何一个结点开始直接遍历到所有结点C. 在线性单链表中,可以从任何一个结点开始直接遍历到所有结点D. 在二叉链表中,可以从根结点开始遍历到所有结点6. 设循环队列为Q(1:m),其初始状态为front=rear=m。经过一系列入队与退队运算后,front=15,rear=20。现要在该循环队列中寻找最大值的元素,最坏情况下需要比较的次数为______。A. 4B. 6C. m-5D. m-67. 下列数据结构中,能用二分法进行查找的是______。A. 顺序存储的有序线性表B. 线性链表C. 二叉链表D. 有序线性链表8. 某二叉树共有150个结点,其中有50个度为1的结点,则______。A. 不存在这样的二叉树B. 该二叉树有49个叶子结点C. 该二叉树有50个叶子结点D. 该二叉树有51个叶子结点9. 设数据元素的集合D={1,2,3,4,5},则满足下列关系R的数据结构中为线性结构的是______。A. R={(1,2),(3,2),(5,1),(4,5)}B. R={(1,3),(4,1),(3,2),(5,4)}C. R={(1,2),(2,4),(4,5),(2,3)}D. R={(1,3),(2,4),(3,5),(1,2)}10. [所谓简单插入排序,是指将无序序列中的各元素依次插入到已经有序的线性表中。在简单插入排序中,每一次比较后最多移掉一个逆序,因此,这种排序方法的效率与冒泡排序法相同。在最坏情况下,简单插入排序需要n(n-1)/2次比较。]11. n个顶点的强连通图的边数至少有______。A. n-1B. n(n-1)C. nD. n+112. 冒泡排序在最坏情况下的比较次数是______。A. n(n+1)/2B. nlog2nC. n(n-1)/2D. n/213. 设循环队列为Q(1: m),其初始状态为front=rear=m。经过一系列入队与退队运算后,front=30,rear=10。现要在该循环队列中作顺序查找,最坏情况下需要比较的次数为______。A. 19B. 20C. m-19D. m-2014. 某二叉树共有13个结点,其中有4个度为1的结点,则叶子结点数为______。A. 5B. 4C. 3D. 215. 若某二叉树中的所有结点值均大于其左子树上的所有结点值,且小于右子树上的所有结点值,则该二叉树遍历序列中有序的是______。A. 前序序列B. 中序序列C. 后序序列D. 以上说法均不正确16. 希尔排序法属于哪一种类型的排序法______。A. 交换类排序法B. 插入类排序法C. 选择类排序法D. 建堆排序法17. 某循环队列的存储空间为Q(1:m),初始状态为front=rear=m。现经过一系列的入队操作和退队操作后,front=m-1,rear=m,则该循环队列中的元素个数为______。A. 0B. m-1C. mD. 118. 在下列选项中,哪个不是一个算法一般应该具有的基本特征______。A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报19. 设循环队列的存储空间为Q(1:m),初始状态为空。现经过一系列正常的入队与退队操作后,front=m,rear=m-1,此后从该循环队列中删除一个元素,则队列中的元素个数为______。A. 1B. m-2C. m-1D. 020. 下列关于二叉树的叙述中,正确的是______。A. 叶子结点总是比度为2的结点少一个B. 叶子结点总是比度为2的结点多一个C. 叶子结点数是度为2的结点数的两倍D. 度为2的结点数是度为1的结点数的两倍21. 下列关于栈的描述中错误的是______。A. 栈是先进后出的线性表B. 栈只能顺序存储C. 栈具有记忆作用D. 对栈的插入与删除操作中,不需要改变栈底指针22. 下列叙述中正确的是______。A. 栈是"先进先出"的线性表B. 队列是"先进后出"的线性表C. 循环队列是非线性结构D. 有序线性表既可以采用顺序存储结构,也可以采用链式存储结构23. 线性表的链式存储结构与顺序存储结构相比,链式存储结构的优点有______。A. 节省存储空间B. 插入与删除运算效率高C. 便于查找D. 排序时减少元素的比较次数24. 下列叙述中正确的是______。A. 栈与队列都只能顺序存储B. 循环队列是队列的顺序存储结构C. 循环链表是循环队列的链式存储结构D. 循环队列不是队列的顺序存储结构25. 下列叙述中正确的是______。A. 二分查找法只适用于顺序存储的有序线性表B. 二分查找法适用于任何存储结构的有序线性表C. 算法的时间复杂度是指设计算法的工作量D. 二分查找法适用于有序双向链表26. 对长度为n的线性表排序,在最坏情况下,比较次数不是n(n-1)/2的排序方法是______。A. 快速排序B. 冒泡排序C. 直接插入排序D. 堆排序27. 栈和队列的共同点是______。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点28. [(1)快速排序:通常,快速排序被认为是所有同数量级O(nlogn)的排序方法中,其平均性能最好。但是,若初始记录序列按关键字有序或基本有序时,快速排序将蜕化为起泡排序,其时间复杂度为O(n2)。]29. 设栈的顺序存储空间为 S(1:m),初始状态为top=0,则栈中的数据元素个数为______。A. m-topB. m-top+1C. topD. top-m30. 一个栈的初始状态为空。现将元素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,A31. 循环队列的存储空间为Q(1:40),初始状态为front=rear=40。经过一系列正常的入队与退队操作后,front=rear=15,此后又退出一个元素,则循环队列中的元素个数为______。A. 39,或0且产生下溢错误B. 40C. 15D. 1432. 下列叙述中正确的是______。A. 在循环队列中,队头指针和队尾指针的动态变化决定队列的长度B. 在循环队列中,队尾指针的动态变化决定队列的长度C. 在带链的队列中,队头指针与队尾指针的动态变化决定队列的长度D. 在带链的栈中,栈顶指针的动态变化决定栈中元素的个数33. 设栈的存储空间为S(1:50),初始状态为top=0。现经过一系列正常的入栈与退栈操作后,top=51,则栈中的元素个数为______。A. 1B. 50C. 0D. 不可能34. 设数据结构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. 非线性结构35. 某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后,front=rear=10。该队列中的元素个数为______。A. 1B. 0C. 1或0D. 不确定36. 设有一个栈与一个队列的初始状态均为空。现有一个序列A,B,C,D,E,F,G,H。先分别将序列中的前4个元素依次入栈,后4个元素依次入队;然后分别将栈中的元素依次退栈,再将队列中的元素依次退队。最后得到的序列为______。A. D,C,B,A,E,F,G,HB. D,C,B,A,H,G,F,EC. A,B,C,D,E,F,G,HD. A,B,C,D,H,G,F,E37. 下列叙述中正确的是______。A. 数组是长度固定的线性表B. 矩阵是非线性结构C. 对线性表只能作插入与删除运算D. 线性表中各元素的数据类型可以不同38. 设一棵度为3的树,其中度为2,1,0的结点数分别为3,4,15。则该树中总结点数为______。A. 30B. 22C. 55D. 不可能有这样的树39. 下列叙述中正确的是______。A. 线性链表可以有多个指针域B. 有两个以上指针域的链表是非线性结构C. 只有一个指针域的链表一定是线性结构D. 线性链表最多可以有两个指针域40. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入队和入栈,然后依次轮流退队和出栈,则输出序列为______。A. A,H,C,F,E,D,G,BB. G,E,C,A,B,D,F,HC. D,C,B,A,E,F,G,HD. A,B,C,D,H,G,F,E41. 某二叉树有49个度为2的结点,4个度为1的结点,30个叶子结点,则______。A. 不可能有这样的二叉树B. 该二叉树只能有83个结点C. 这样的二叉树不惟一D. 该二叉树共有103个结点42. 设栈与队列初始状态为空。首先A,B,C,D,E依次入栈,再F,G,H,I,J依次入队;然后依次出队至队空,再依次出栈至栈空。则输出序列为______。A. E,D,C,B,A,F,G,H,I,JB. E,D,C,B,A,J,I,H,G,FC. F,G,H,I,J,A,B,C,D,ED. F,G,H,I,J,E,D,C,B,A43. 对长度为8的数组进行快速排序,最多需要的比较次数为______。A. 28B. 64C. 56D. 844. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队,然后依次轮流退队和出栈,则输出序列为______。A. B,G,D,E,F,C,H,AB. G,B,E,D,C,F,A,HC. D,C,B,A,E,F,G,HD. A,B,C,D,H,G,F,E45. 下列各组算法中,最坏情况下其时间复杂度相同的是______。A. 冒泡排序与快速排序B. 直接插入排序与希尔排序C. 简单选择排序与堆排序D. 快速排序与希尔排序46. 某二叉树的后序序列为DEBFGCA,中序序列为DBEAFCG,则前序序列为______。A. ACFGBDEB. ABCDEFGC. ABDECFGD. ADEBFGC47. 设某树的度为3,且度为3的结点数为4,度为1的结点数为9,没有度为2的结点。则该树中的叶子结点数为______。A. 9B. 1C. 4D. 不可能有这样的树48. 设二叉树的前序序列为ABCDEF,中序序列为ABCDEF,则该二叉树的后序序列为______。A. FEDCBAB. ABCDEFC. DEFCBAD. CBAFED49. 某系统结构图如下图所示(n≥5),该系统结构图的最大扇出数是______。 A. 2B. 3C. nD. n+150. 某系统总体结构如下图所示,系统结构图的最大扇入数是______。 A. 2B. 3C. 4D. 551. 设二叉树如下,则中序序列为______。 A. ABDEGCFHB. DBGEAFHCC. DGEBHFCAD. ABCDEFGH52. 对下列二叉树进行前序遍历的结果为______。 A. DYBEAFCZXB. YDEBFZXCAC. ABDYECFXZD. ABCDEFXYZ53. 某系统结构图如下图所示,该系统结构图的深度是______。 A. 4B. 3C. 2D. 1 提交成功!
4. 一个栈的初始状态为空,现将元素A,B,C,D,E依次入栈,然后依次退栈三次,并将退栈的三个元素依次入队(原队列为空),最后将队列中的元素全部退出。则元素退队的顺序为______。A. ABCB. CBAC. EDCD. CDE
5. 下列叙述中错误的是______。A. 在双向链表中,可以从任何一个结点开始直接遍历到所有结点B. 在循环链表中,可以从任何一个结点开始直接遍历到所有结点C. 在线性单链表中,可以从任何一个结点开始直接遍历到所有结点D. 在二叉链表中,可以从根结点开始遍历到所有结点
6. 设循环队列为Q(1:m),其初始状态为front=rear=m。经过一系列入队与退队运算后,front=15,rear=20。现要在该循环队列中寻找最大值的元素,最坏情况下需要比较的次数为______。A. 4B. 6C. m-5D. m-6
9. 设数据元素的集合D={1,2,3,4,5},则满足下列关系R的数据结构中为线性结构的是______。A. R={(1,2),(3,2),(5,1),(4,5)}B. R={(1,3),(4,1),(3,2),(5,4)}C. R={(1,2),(2,4),(4,5),(2,3)}D. R={(1,3),(2,4),(3,5),(1,2)}
10. [所谓简单插入排序,是指将无序序列中的各元素依次插入到已经有序的线性表中。在简单插入排序中,每一次比较后最多移掉一个逆序,因此,这种排序方法的效率与冒泡排序法相同。在最坏情况下,简单插入排序需要n(n-1)/2次比较。]
13. 设循环队列为Q(1: m),其初始状态为front=rear=m。经过一系列入队与退队运算后,front=30,rear=10。现要在该循环队列中作顺序查找,最坏情况下需要比较的次数为______。A. 19B. 20C. m-19D. m-20
17. 某循环队列的存储空间为Q(1:m),初始状态为front=rear=m。现经过一系列的入队操作和退队操作后,front=m-1,rear=m,则该循环队列中的元素个数为______。A. 0B. m-1C. mD. 1
19. 设循环队列的存储空间为Q(1:m),初始状态为空。现经过一系列正常的入队与退队操作后,front=m,rear=m-1,此后从该循环队列中删除一个元素,则队列中的元素个数为______。A. 1B. m-2C. m-1D. 0
20. 下列关于二叉树的叙述中,正确的是______。A. 叶子结点总是比度为2的结点少一个B. 叶子结点总是比度为2的结点多一个C. 叶子结点数是度为2的结点数的两倍D. 度为2的结点数是度为1的结点数的两倍
25. 下列叙述中正确的是______。A. 二分查找法只适用于顺序存储的有序线性表B. 二分查找法适用于任何存储结构的有序线性表C. 算法的时间复杂度是指设计算法的工作量D. 二分查找法适用于有序双向链表
28. [(1)快速排序:通常,快速排序被认为是所有同数量级O(nlogn)的排序方法中,其平均性能最好。但是,若初始记录序列按关键字有序或基本有序时,快速排序将蜕化为起泡排序,其时间复杂度为O(n2)。]
30. 一个栈的初始状态为空。现将元素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
31. 循环队列的存储空间为Q(1:40),初始状态为front=rear=40。经过一系列正常的入队与退队操作后,front=rear=15,此后又退出一个元素,则循环队列中的元素个数为______。A. 39,或0且产生下溢错误B. 40C. 15D. 14
32. 下列叙述中正确的是______。A. 在循环队列中,队头指针和队尾指针的动态变化决定队列的长度B. 在循环队列中,队尾指针的动态变化决定队列的长度C. 在带链的队列中,队头指针与队尾指针的动态变化决定队列的长度D. 在带链的栈中,栈顶指针的动态变化决定栈中元素的个数
34. 设数据结构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. 非线性结构
36. 设有一个栈与一个队列的初始状态均为空。现有一个序列A,B,C,D,E,F,G,H。先分别将序列中的前4个元素依次入栈,后4个元素依次入队;然后分别将栈中的元素依次退栈,再将队列中的元素依次退队。最后得到的序列为______。A. D,C,B,A,E,F,G,HB. D,C,B,A,H,G,F,EC. A,B,C,D,E,F,G,HD. A,B,C,D,H,G,F,E
40. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入队和入栈,然后依次轮流退队和出栈,则输出序列为______。A. A,H,C,F,E,D,G,BB. G,E,C,A,B,D,F,HC. D,C,B,A,E,F,G,HD. A,B,C,D,H,G,F,E
42. 设栈与队列初始状态为空。首先A,B,C,D,E依次入栈,再F,G,H,I,J依次入队;然后依次出队至队空,再依次出栈至栈空。则输出序列为______。A. E,D,C,B,A,F,G,H,I,JB. E,D,C,B,A,J,I,H,G,FC. F,G,H,I,J,A,B,C,D,ED. F,G,H,I,J,E,D,C,B,A
44. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队,然后依次轮流退队和出栈,则输出序列为______。A. B,G,D,E,F,C,H,AB. G,B,E,D,C,F,A,HC. D,C,B,A,E,F,G,HD. A,B,C,D,H,G,F,E