全国二级理论——1.2数据结构与算法 本套试题共50题。 1. 班级:格式如“19计应31”2. 学号:10位数完整格式3. 姓名:4. 下列关于栈叙述正确的是______。A. 栈顶元素最先能被删除B. 栈顶元素最后才能被删除C. 栈底元素永远不能被删除D. 以上三种说法都不对5. 在下列选项中,哪个不是一个算法一般应该具有的基本特征______。A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报6. 在单链表中,增加头结点的目的是______。A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现7. 下列叙述中正确的是______。A. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B. 循环队列中的元素个数随队头指针的变化而动态变化C. 循环队列中的元素个数随队尾指针的变化而动态变化D. 以上说法都不对8. 若某二叉树中的所有结点值均大于其左子树上的所有结点值,且小于右子树上的所有结点值,则该二叉树遍历序列中有序的是______。A. 前序序列B. 中序序列C. 后序序列D. 以上说法均不正确9. 某二叉树的前序序列为ABCDEFG,中序序列为DCBAEFG,则该二叉树的后序序列为______。A. EFGDCBAB. DCBEFGAC. BCDGFEAD. DCBGFEA10. 下列关于栈的描述正确的是______。A. 在栈中只能插入元素而不能删除元素B. 在栈中只能删除元素而不能插入元素C. 栈是特殊的线性表,只能在一端插入或删除元素D. 栈是特殊的线性表,只能在一端插入元素,而在另一端删除元素11. [希尔排序法属于插入类排序,但它对简单插入排序做了较大的改进。基本思想是:将整个无序序列分割成若干小的子序列分别进行插入排序。在希尔排序过程中,虽然对于每一个子表采用的仍是插入排序,但是,在子表中每进行一次比较久有可能移去整个线性表中的多个逆序,从而改善了整个排序过程的性能。最欢情况下,希尔排序所需要的比较次数为O(n1.5)。]12. [(1)冒泡排序法:是一种最简单的交换类排序法,它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n,则在最坏情况下,冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描,需要比较的次数为n(n-1)/2次。因此冒泡排序总的时间复杂度为O(n2)。]13. 下列各组排序法中,最坏情况下比较次数相同的是______。A. 冒泡排序与快速排序B. 简单插入排序与希尔排序C. 希尔排序与堆排序D. 快速排序与希尔排序14. 某二叉树的前序遍历序列为 ABCDE ,中序遍历序列为 CBADE ,则后序遍历序列为______。A. CBADEB. EDABCC. CBEDAD. EDCBA15. 算法的时间复杂度是指______。A. 设计该算法所需的工作量B. 执行该算法所需要的时间C. 算法中指令的条数D. 执行该算法时所需要的基本运算次数16. [(4)堆排序法:堆排序的方法为:①首先将一个无序序列建成堆。②然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。在最坏情况下,堆排序需要比较的次数为O(nlog2n)。]17. 下列叙述中正确的是______。A. 非线性结构只能采用链式存储结构B. 非线性结构只能用多重链表表示C. 所有数据结构既可以采用顺序存储结构,也可以采用链式存储结构D. 有的非线性结构也能采用顺序存储结构18. 下列排序方法中,最坏情况下比较次数最少的是______。A. 冒泡排序B. 简单选择排序C. 直接插入排序D. 堆排序19. 设有栈S和队列Q,初始状态均为空。首先依次将A,B,C,D,E,F入栈,然后从栈中退出三个元素依次入队,再将X,Y,Z入栈后,将栈中所有元素退出并依次入队,最后将队列中所有元素退出,则退队元素的顺序为______。A. DEFXYZABCB. FEDZYXCBAC. FEDXYZCBAD. DEFZYXABC20. 下列叙述中正确的是______。A. 二分查找法只适用于顺序存储的有序线性表B. 二分查找法适用于任何存储结构的有序线性表C. 算法的时间复杂度是指设计算法的工作量D. 二分查找法适用于有序双向链表21. [(3)简单选择排序法:对于长度为n的序列,选择排序需要扫描n-1遍,每一遍扫描均从剩下的子表中选出最小的元素,然后将该最小的元素与子表中的第一个元素进行交换。简单选择排序法在最坏情况下需要比较n(n-1)/2次。]22. [(2) 快速排序:通常,快速排序被认为是,所有同数量级(O(nlogn))的排序方法中,其平均性能最好。但是,若初始记录序列按关键字有序或基本有序时,快速排序将蜕化为起泡排序,其时间复杂度为O(n2)。]23. 下列关于算法的描述中错误的是______。A. 算法强调动态的执行过程,不同于静态的计算公式B. 算法必须能在有限个步骤之后终止C. 算法设计必须考虑算法的复杂度D. 算法的优劣取决于运行算法程序的环境24. 下列算法中,最坏情况下时间复杂度为O(log2n)的是______。A. 二分查找法B. 堆排序C. 快速排序D. 顺序查找法25. 某棵树中共有25个结点,且只有度为3的结点和叶子结点,其中叶子结点有7个,则该树中度为3的结点数为______。A. 8B. 7C. 不存在这样的树D. 626. 下列叙述中错误的是______。A. 在带链队列中,队头指针和队尾指针都是在动态变化的B. 在带链栈中,栈顶指针和栈底指针都是在动态变化的C. 在带链栈中,栈顶指针是在动态变化的,但栈底指针是不变的D. 栈和队列都是线性表,都可以采用链式存储结构27. 下列关于线性链表的叙述中,正确的是______。A. 各数据结点的存储空间可以不连续,但它们的存储顺序与逻辑顺序必须一致B. 各数据结点的存储顺序与逻辑顺序可以不一致,但它们的存储空间必须连续C. 进行插入和删除时,不需要移动表中的元素D. 以上三种说法都不对28. 下列叙述中正确的是______。A. 链表结点中具有两个指针域的数据结构可以是线性结构,也可以是非线性结构B. 线性表的链式存储结构中,每个结点必须有指向前件和指向后件的两个指针C. 线性表的链式存储结构中,每个结点只能有一个指向后件的指针D. 线性表的链式存储结构中,叶子结点的指针只能是空29. 下列排序方法中,最坏情况下时间复杂度(即比较次数)低于O(n2)的是______。A. 冒泡排序B. 快速排序C. 简单插入排序D. 堆排序30. 下列叙述中错误的是______。A. 对于各种特定的输入,算法的时间复杂度是固定不变的B. 算法的时间复杂度与使用的计算机系统无关C. 算法的时间复杂度与使用的程序设计语言无关D. 算法的时间复杂度与实现算法过程中的具体细节无关31. 下列叙述中正确的是______。A. 在线性链表中,头指针和链尾指针的动态变化决定链表的长度B. 在循环队列中,队尾指针的动态变化决定队列的长度C. 在循环链表中,头指针和链尾指针的动态变化决定链表的长度D. 在栈中,栈顶指针的动态变化决定栈中元素的个数32. 某二叉树的中序遍历序列为CBADE,后序遍历序列为CBADE,则前序遍历序列为______。A. CBADEB. CBEDAC. EDABCD. EDCBA33. 带链栈空的条件是______。A. top=bottom=-1B. top=-1 且 bottom=NULLC. top=NULL 且 bottom=-1D. top=bottom=NULL34. 下列叙述中错误的是______。A. 向量是线性结构B. 非空线性结构中只有一个结点没有前件C. 非空线性结构中只有一个结点没有后件D. 只有一个根结点和一个叶子结点的结构必定是线性结构35. 下列叙述中正确的是______。A. 能采用顺序存储的必定是线性结构B. 所有的线性结构都可以采用顺序存储结构C. 具有两个以上指针的链表必定是非线性结构D. 循环队列是队列的链式存储结构36. 某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后,front=10, rear=5。该队列中的元素个数为______。A. 4B. 5C. 不确定D. 637. 设循环队列的存储空间为Q(1:50),初始状态为front=rear=50。经过一系列正常的操作后,front-1=rear。为了在该队列中寻找值最大的元素,在最坏情况下需要的比较次数为______。A. 0B. 49C. 1D. 4838. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队,然后依次轮流退队和出栈,则输出序列为______。A. G,B,E,D,C,F,A,HB. D,C,B,A,E,F,G,HC. B,G,D,E,F,C,H,AD. A,B,C,D,H,G,F,E39. 设某树的度为3,且度为3的结点数为5,度为2的结点数为4,没有度为1的结点。则该树中的叶子结点数为______。A. 不可能有这样的树B. 12C. 24D. 1540. 下列叙述中正确的是______。A. 算法时间复杂度的度量与计算机存储空间有关B. 算法时间复杂度的度量与计算机运行速度有关C. 算法空间复杂度的度量与数据的存储结构无关D. 数据的处理效率与数据的存储结构有关41. 下列叙述中错误的是______。A. 循环队列是队列的存储结构B. 循环链表是循环队列的链式存储结构C. 具有两个指针域的链表不一定是线性结构D. 具有两个指针域的链表不一定是非线性结构42. 树的度为3,且有9个度为3的结点,5个度为1的结点,但没有度为2的结点。则该树总的结点数为______。A. 33B. 14C. 32D. 1943. 设元素集合为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)}44. 循环队列的存储空间为Q(1:50),初始状态为空。经过一系列正常的入队与退队操作后,front=24,rear=25。此时该循环队列中的元素个数为______。A. 1B. 49C. 50D. 2545. 设二叉树的前序序列为ABCDEF,中序序列为ABCDEF,则该二叉树的后序序列为______。A. FEDCBAB. ABCDEFC. DEFCBAD. CBAFED46. 设二叉树的前序序列为ABCDEF,中序序列为BDFECA,则该二叉树的深度为(根结点为第1层)______。A. 6B. 2C. 3D. 447. 设二叉树的前序序列为ABCDEF,中序序列为BDFECA,则该二叉树的后序序列为______。A. ABCDEFB. FEDCBAC. BDFECAD. CBAFED48. 设某树的度为3,且度为3的结点数为5,度为1的结点数为6,没有度为2的结点。则该树中的叶子结点数为______。A. 11B. 22C. 20D. 不可能有这样的树49. 设二叉树如下,则中序序列为______。 A. ABDEGCFHB. DBGEAFHCC. DGEBHFCAD. ABCDEFGH50. 设二叉树如下,则前序序列为______。 A. ABDEGCFHB. DBGEAFHCC. DGEBHFCAD. ABCDEFGH51. 对下列二叉树进行前序遍历的结果为______。 A. DYBEAFCZXB. YDEBFZXCAC. ABDYECFXZD. ABCDEFXYZ52. 某系统总体结构如下图所示,该系统结构图的深度是______。 A. 4B. 3C. 2D. 153. 设有下列二叉树,此二叉树中序遍历的结果为______。 A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA 提交成功!
全国二级理论——1.2数据结构与算法 本套试题共50题。 1. 班级:格式如“19计应31”2. 学号:10位数完整格式3. 姓名:4. 下列关于栈叙述正确的是______。A. 栈顶元素最先能被删除B. 栈顶元素最后才能被删除C. 栈底元素永远不能被删除D. 以上三种说法都不对5. 在下列选项中,哪个不是一个算法一般应该具有的基本特征______。A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报6. 在单链表中,增加头结点的目的是______。A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现7. 下列叙述中正确的是______。A. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B. 循环队列中的元素个数随队头指针的变化而动态变化C. 循环队列中的元素个数随队尾指针的变化而动态变化D. 以上说法都不对8. 若某二叉树中的所有结点值均大于其左子树上的所有结点值,且小于右子树上的所有结点值,则该二叉树遍历序列中有序的是______。A. 前序序列B. 中序序列C. 后序序列D. 以上说法均不正确9. 某二叉树的前序序列为ABCDEFG,中序序列为DCBAEFG,则该二叉树的后序序列为______。A. EFGDCBAB. DCBEFGAC. BCDGFEAD. DCBGFEA10. 下列关于栈的描述正确的是______。A. 在栈中只能插入元素而不能删除元素B. 在栈中只能删除元素而不能插入元素C. 栈是特殊的线性表,只能在一端插入或删除元素D. 栈是特殊的线性表,只能在一端插入元素,而在另一端删除元素11. [希尔排序法属于插入类排序,但它对简单插入排序做了较大的改进。基本思想是:将整个无序序列分割成若干小的子序列分别进行插入排序。在希尔排序过程中,虽然对于每一个子表采用的仍是插入排序,但是,在子表中每进行一次比较久有可能移去整个线性表中的多个逆序,从而改善了整个排序过程的性能。最欢情况下,希尔排序所需要的比较次数为O(n1.5)。]12. [(1)冒泡排序法:是一种最简单的交换类排序法,它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n,则在最坏情况下,冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描,需要比较的次数为n(n-1)/2次。因此冒泡排序总的时间复杂度为O(n2)。]13. 下列各组排序法中,最坏情况下比较次数相同的是______。A. 冒泡排序与快速排序B. 简单插入排序与希尔排序C. 希尔排序与堆排序D. 快速排序与希尔排序14. 某二叉树的前序遍历序列为 ABCDE ,中序遍历序列为 CBADE ,则后序遍历序列为______。A. CBADEB. EDABCC. CBEDAD. EDCBA15. 算法的时间复杂度是指______。A. 设计该算法所需的工作量B. 执行该算法所需要的时间C. 算法中指令的条数D. 执行该算法时所需要的基本运算次数16. [(4)堆排序法:堆排序的方法为:①首先将一个无序序列建成堆。②然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。在最坏情况下,堆排序需要比较的次数为O(nlog2n)。]17. 下列叙述中正确的是______。A. 非线性结构只能采用链式存储结构B. 非线性结构只能用多重链表表示C. 所有数据结构既可以采用顺序存储结构,也可以采用链式存储结构D. 有的非线性结构也能采用顺序存储结构18. 下列排序方法中,最坏情况下比较次数最少的是______。A. 冒泡排序B. 简单选择排序C. 直接插入排序D. 堆排序19. 设有栈S和队列Q,初始状态均为空。首先依次将A,B,C,D,E,F入栈,然后从栈中退出三个元素依次入队,再将X,Y,Z入栈后,将栈中所有元素退出并依次入队,最后将队列中所有元素退出,则退队元素的顺序为______。A. DEFXYZABCB. FEDZYXCBAC. FEDXYZCBAD. DEFZYXABC20. 下列叙述中正确的是______。A. 二分查找法只适用于顺序存储的有序线性表B. 二分查找法适用于任何存储结构的有序线性表C. 算法的时间复杂度是指设计算法的工作量D. 二分查找法适用于有序双向链表21. [(3)简单选择排序法:对于长度为n的序列,选择排序需要扫描n-1遍,每一遍扫描均从剩下的子表中选出最小的元素,然后将该最小的元素与子表中的第一个元素进行交换。简单选择排序法在最坏情况下需要比较n(n-1)/2次。]22. [(2) 快速排序:通常,快速排序被认为是,所有同数量级(O(nlogn))的排序方法中,其平均性能最好。但是,若初始记录序列按关键字有序或基本有序时,快速排序将蜕化为起泡排序,其时间复杂度为O(n2)。]23. 下列关于算法的描述中错误的是______。A. 算法强调动态的执行过程,不同于静态的计算公式B. 算法必须能在有限个步骤之后终止C. 算法设计必须考虑算法的复杂度D. 算法的优劣取决于运行算法程序的环境24. 下列算法中,最坏情况下时间复杂度为O(log2n)的是______。A. 二分查找法B. 堆排序C. 快速排序D. 顺序查找法25. 某棵树中共有25个结点,且只有度为3的结点和叶子结点,其中叶子结点有7个,则该树中度为3的结点数为______。A. 8B. 7C. 不存在这样的树D. 626. 下列叙述中错误的是______。A. 在带链队列中,队头指针和队尾指针都是在动态变化的B. 在带链栈中,栈顶指针和栈底指针都是在动态变化的C. 在带链栈中,栈顶指针是在动态变化的,但栈底指针是不变的D. 栈和队列都是线性表,都可以采用链式存储结构27. 下列关于线性链表的叙述中,正确的是______。A. 各数据结点的存储空间可以不连续,但它们的存储顺序与逻辑顺序必须一致B. 各数据结点的存储顺序与逻辑顺序可以不一致,但它们的存储空间必须连续C. 进行插入和删除时,不需要移动表中的元素D. 以上三种说法都不对28. 下列叙述中正确的是______。A. 链表结点中具有两个指针域的数据结构可以是线性结构,也可以是非线性结构B. 线性表的链式存储结构中,每个结点必须有指向前件和指向后件的两个指针C. 线性表的链式存储结构中,每个结点只能有一个指向后件的指针D. 线性表的链式存储结构中,叶子结点的指针只能是空29. 下列排序方法中,最坏情况下时间复杂度(即比较次数)低于O(n2)的是______。A. 冒泡排序B. 快速排序C. 简单插入排序D. 堆排序30. 下列叙述中错误的是______。A. 对于各种特定的输入,算法的时间复杂度是固定不变的B. 算法的时间复杂度与使用的计算机系统无关C. 算法的时间复杂度与使用的程序设计语言无关D. 算法的时间复杂度与实现算法过程中的具体细节无关31. 下列叙述中正确的是______。A. 在线性链表中,头指针和链尾指针的动态变化决定链表的长度B. 在循环队列中,队尾指针的动态变化决定队列的长度C. 在循环链表中,头指针和链尾指针的动态变化决定链表的长度D. 在栈中,栈顶指针的动态变化决定栈中元素的个数32. 某二叉树的中序遍历序列为CBADE,后序遍历序列为CBADE,则前序遍历序列为______。A. CBADEB. CBEDAC. EDABCD. EDCBA33. 带链栈空的条件是______。A. top=bottom=-1B. top=-1 且 bottom=NULLC. top=NULL 且 bottom=-1D. top=bottom=NULL34. 下列叙述中错误的是______。A. 向量是线性结构B. 非空线性结构中只有一个结点没有前件C. 非空线性结构中只有一个结点没有后件D. 只有一个根结点和一个叶子结点的结构必定是线性结构35. 下列叙述中正确的是______。A. 能采用顺序存储的必定是线性结构B. 所有的线性结构都可以采用顺序存储结构C. 具有两个以上指针的链表必定是非线性结构D. 循环队列是队列的链式存储结构36. 某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后,front=10, rear=5。该队列中的元素个数为______。A. 4B. 5C. 不确定D. 637. 设循环队列的存储空间为Q(1:50),初始状态为front=rear=50。经过一系列正常的操作后,front-1=rear。为了在该队列中寻找值最大的元素,在最坏情况下需要的比较次数为______。A. 0B. 49C. 1D. 4838. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队,然后依次轮流退队和出栈,则输出序列为______。A. G,B,E,D,C,F,A,HB. D,C,B,A,E,F,G,HC. B,G,D,E,F,C,H,AD. A,B,C,D,H,G,F,E39. 设某树的度为3,且度为3的结点数为5,度为2的结点数为4,没有度为1的结点。则该树中的叶子结点数为______。A. 不可能有这样的树B. 12C. 24D. 1540. 下列叙述中正确的是______。A. 算法时间复杂度的度量与计算机存储空间有关B. 算法时间复杂度的度量与计算机运行速度有关C. 算法空间复杂度的度量与数据的存储结构无关D. 数据的处理效率与数据的存储结构有关41. 下列叙述中错误的是______。A. 循环队列是队列的存储结构B. 循环链表是循环队列的链式存储结构C. 具有两个指针域的链表不一定是线性结构D. 具有两个指针域的链表不一定是非线性结构42. 树的度为3,且有9个度为3的结点,5个度为1的结点,但没有度为2的结点。则该树总的结点数为______。A. 33B. 14C. 32D. 1943. 设元素集合为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)}44. 循环队列的存储空间为Q(1:50),初始状态为空。经过一系列正常的入队与退队操作后,front=24,rear=25。此时该循环队列中的元素个数为______。A. 1B. 49C. 50D. 2545. 设二叉树的前序序列为ABCDEF,中序序列为ABCDEF,则该二叉树的后序序列为______。A. FEDCBAB. ABCDEFC. DEFCBAD. CBAFED46. 设二叉树的前序序列为ABCDEF,中序序列为BDFECA,则该二叉树的深度为(根结点为第1层)______。A. 6B. 2C. 3D. 447. 设二叉树的前序序列为ABCDEF,中序序列为BDFECA,则该二叉树的后序序列为______。A. ABCDEFB. FEDCBAC. BDFECAD. CBAFED48. 设某树的度为3,且度为3的结点数为5,度为1的结点数为6,没有度为2的结点。则该树中的叶子结点数为______。A. 11B. 22C. 20D. 不可能有这样的树49. 设二叉树如下,则中序序列为______。 A. ABDEGCFHB. DBGEAFHCC. DGEBHFCAD. ABCDEFGH50. 设二叉树如下,则前序序列为______。 A. ABDEGCFHB. DBGEAFHCC. DGEBHFCAD. ABCDEFGH51. 对下列二叉树进行前序遍历的结果为______。 A. DYBEAFCZXB. YDEBFZXCAC. ABDYECFXZD. ABCDEFXYZ52. 某系统总体结构如下图所示,该系统结构图的深度是______。 A. 4B. 3C. 2D. 153. 设有下列二叉树,此二叉树中序遍历的结果为______。 A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA 提交成功!
7. 下列叙述中正确的是______。A. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B. 循环队列中的元素个数随队头指针的变化而动态变化C. 循环队列中的元素个数随队尾指针的变化而动态变化D. 以上说法都不对
10. 下列关于栈的描述正确的是______。A. 在栈中只能插入元素而不能删除元素B. 在栈中只能删除元素而不能插入元素C. 栈是特殊的线性表,只能在一端插入或删除元素D. 栈是特殊的线性表,只能在一端插入元素,而在另一端删除元素
11. [希尔排序法属于插入类排序,但它对简单插入排序做了较大的改进。基本思想是:将整个无序序列分割成若干小的子序列分别进行插入排序。在希尔排序过程中,虽然对于每一个子表采用的仍是插入排序,但是,在子表中每进行一次比较久有可能移去整个线性表中的多个逆序,从而改善了整个排序过程的性能。最欢情况下,希尔排序所需要的比较次数为O(n1.5)。]
12. [(1)冒泡排序法:是一种最简单的交换类排序法,它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n,则在最坏情况下,冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描,需要比较的次数为n(n-1)/2次。因此冒泡排序总的时间复杂度为O(n2)。]
16. [(4)堆排序法:堆排序的方法为:①首先将一个无序序列建成堆。②然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。在最坏情况下,堆排序需要比较的次数为O(nlog2n)。]
17. 下列叙述中正确的是______。A. 非线性结构只能采用链式存储结构B. 非线性结构只能用多重链表表示C. 所有数据结构既可以采用顺序存储结构,也可以采用链式存储结构D. 有的非线性结构也能采用顺序存储结构
19. 设有栈S和队列Q,初始状态均为空。首先依次将A,B,C,D,E,F入栈,然后从栈中退出三个元素依次入队,再将X,Y,Z入栈后,将栈中所有元素退出并依次入队,最后将队列中所有元素退出,则退队元素的顺序为______。A. DEFXYZABCB. FEDZYXCBAC. FEDXYZCBAD. DEFZYXABC
20. 下列叙述中正确的是______。A. 二分查找法只适用于顺序存储的有序线性表B. 二分查找法适用于任何存储结构的有序线性表C. 算法的时间复杂度是指设计算法的工作量D. 二分查找法适用于有序双向链表
21. [(3)简单选择排序法:对于长度为n的序列,选择排序需要扫描n-1遍,每一遍扫描均从剩下的子表中选出最小的元素,然后将该最小的元素与子表中的第一个元素进行交换。简单选择排序法在最坏情况下需要比较n(n-1)/2次。]
22. [(2) 快速排序:通常,快速排序被认为是,所有同数量级(O(nlogn))的排序方法中,其平均性能最好。但是,若初始记录序列按关键字有序或基本有序时,快速排序将蜕化为起泡排序,其时间复杂度为O(n2)。]
23. 下列关于算法的描述中错误的是______。A. 算法强调动态的执行过程,不同于静态的计算公式B. 算法必须能在有限个步骤之后终止C. 算法设计必须考虑算法的复杂度D. 算法的优劣取决于运行算法程序的环境
26. 下列叙述中错误的是______。A. 在带链队列中,队头指针和队尾指针都是在动态变化的B. 在带链栈中,栈顶指针和栈底指针都是在动态变化的C. 在带链栈中,栈顶指针是在动态变化的,但栈底指针是不变的D. 栈和队列都是线性表,都可以采用链式存储结构
27. 下列关于线性链表的叙述中,正确的是______。A. 各数据结点的存储空间可以不连续,但它们的存储顺序与逻辑顺序必须一致B. 各数据结点的存储顺序与逻辑顺序可以不一致,但它们的存储空间必须连续C. 进行插入和删除时,不需要移动表中的元素D. 以上三种说法都不对
28. 下列叙述中正确的是______。A. 链表结点中具有两个指针域的数据结构可以是线性结构,也可以是非线性结构B. 线性表的链式存储结构中,每个结点必须有指向前件和指向后件的两个指针C. 线性表的链式存储结构中,每个结点只能有一个指向后件的指针D. 线性表的链式存储结构中,叶子结点的指针只能是空
30. 下列叙述中错误的是______。A. 对于各种特定的输入,算法的时间复杂度是固定不变的B. 算法的时间复杂度与使用的计算机系统无关C. 算法的时间复杂度与使用的程序设计语言无关D. 算法的时间复杂度与实现算法过程中的具体细节无关
31. 下列叙述中正确的是______。A. 在线性链表中,头指针和链尾指针的动态变化决定链表的长度B. 在循环队列中,队尾指针的动态变化决定队列的长度C. 在循环链表中,头指针和链尾指针的动态变化决定链表的长度D. 在栈中,栈顶指针的动态变化决定栈中元素的个数
37. 设循环队列的存储空间为Q(1:50),初始状态为front=rear=50。经过一系列正常的操作后,front-1=rear。为了在该队列中寻找值最大的元素,在最坏情况下需要的比较次数为______。A. 0B. 49C. 1D. 48
38. 设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队,然后依次轮流退队和出栈,则输出序列为______。A. G,B,E,D,C,F,A,HB. D,C,B,A,E,F,G,HC. B,G,D,E,F,C,H,AD. A,B,C,D,H,G,F,E
40. 下列叙述中正确的是______。A. 算法时间复杂度的度量与计算机存储空间有关B. 算法时间复杂度的度量与计算机运行速度有关C. 算法空间复杂度的度量与数据的存储结构无关D. 数据的处理效率与数据的存储结构有关
43. 设元素集合为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)}
44. 循环队列的存储空间为Q(1:50),初始状态为空。经过一系列正常的入队与退队操作后,front=24,rear=25。此时该循环队列中的元素个数为______。A. 1B. 49C. 50D. 25