全国二级理论——1.2数据结构与算法 本套试题共50题。 1. 班级：格式如“19计应31”2. 学号：10位数完整格式3. 姓名：4. 下列链表中，其逻辑结构属于非线性结构的是______。A. 二叉链表B. 循环链表C. 双向链表D. 带链的栈5. 某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为______。A. n+1B. n-1C. 2nD. n/26. 某二叉树共有845个结点，其中叶子结点有45个，则度为1的结点数为______。A. 400B. 754C. 756D. 不确定7. 栈和队列的共同点是______。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点8. 设循环队列为Q(1:m)，初始状态为front=rear=m。现经一系列入队与退队操作后，front=rear=m-1，则______。A. 该循环队列已空B. 该循环队列已满C. 该循环队列中有1个元素D. 该循环队列已空或已满9. 下列叙述中正确的是______。A. 算法的空间复杂度是指算法程序控制结构的复杂程度。B. 算法的空间复杂度与算法所处理的数据存储空间有关。C. 算法的空间复杂度是指算法程序中指令的条数。D. 压缩数据存储空间不会降低算法的空间复杂度。10. 已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是______。A. 堆排序B. 直接插入排序C. 快速排序D. 直接选择排序11. 下列叙述中正确的是______。A. 算法的效率只与问题的规模有关，而与数据的存储结构无关B. 算法的时间复杂度是指执行算法所需要的计算工作量C. 数据的逻辑结构与存储结构是一一对应的D. 算法的时间复杂度与空间复杂度一定相关12. 下列叙述中正确的是______。A. 算法复杂度是指算法控制结构的复杂程度B. 算法复杂度是指设计算法的难度C. 算法的时间复杂度是指设计算法的工作量D. 算法的复杂度包括时间复杂度与空间复杂度13. 算法的时间复杂度是指______。A. 设计该算法所需的工作量B. 执行该算法所需要的时间C. 算法中指令的条数D. 执行该算法时所需要的基本运算次数14. [假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。冒泡排序法与快速排序法本质上都是通过数据元素的交换来逐步消除线性表中的逆序。]15. 下列关于队列的叙述中正确的是______。A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表16. 设循环队列的存储空间为Q(1:35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为______。A. 15B. 16C. 20D. 0或3517. 算法分析的目的是______。A. 找出数据结构的合理性B. 找出算法中输入和输出之间的关系C. 分析算法的易懂性和可靠性D. 分析算法的效率以求改进18. 深度为5的完全二叉树的结点数不可能是______。A. 15B. 16C. 17D. 1819. 算法的空间复杂度是指______。A. 算法在执行过程中所需要的计算机存储空间B. 算法所处理的数据量C. 算法程序中的语句或指令条数D. 算法在执行过程中所需要的临时工作单元数20. 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为______。A. 219B. 221C. 229D. 23121. 下列叙述中正确的是______。A. 存储空间连续的数据结构一定是线性结构B. 存储空间不连续的数据结构一定是非线性结构C. 没有根结点的非空数据结构一定是线性结构D. 具有两个根结点的数据结构一定是非线性结构22. 某二叉树的前序遍历序列为 ABCDE ，中序遍历序列为 CBADE ，则后序遍历序列为______。A. CBADEB. EDABCC. CBEDAD. EDCBA23. 下列各组排序法中，最坏情况下比较次数相同的是______。A. 冒泡排序与快速排序B. 简单插入排序与希尔排序C. 希尔排序与堆排序D. 快速排序与希尔排序24. 在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是______。A. O(n)B. O(n2)C. O(log2n)D. O(nlog2n)25. 下列叙述中正确的是______。A. 非线性结构只能采用链式存储结构B. 非线性结构只能用多重链表表示C. 所有数据结构既可以采用顺序存储结构，也可以采用链式存储结构D. 有的非线性结构也能采用顺序存储结构26. 下列关于栈叙述正确的是______。A. 栈顶元素最先能被删除B. 栈顶元素最后才能被删除C. 栈底元素永远不能被删除D. 以上三种说法都不对27. 下列数据结构中，能用二分法进行查找的是______。A. 顺序存储的有序线性表B. 线性链表C. 二叉链表D. 有序线性链表28. 下列数据结构中为非线性结构的是______。A. 双向链表B. 循环队列C. 循环链表D. 二叉链表29. 某二叉树中共有350个结点，其中200个为叶子结点，则该二叉树中度为2的结点数为______。A. 149B. 150C. 199D. 不可能有这样的二叉树30. 在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为______。A. nB. (n+1)/2C. 3n/4D. n/431. 下列叙述中正确的是______。A. 在线性链表中，头指针和链尾指针的动态变化决定链表的长度B. 在循环队列中，队尾指针的动态变化决定队列的长度C. 在循环链表中，头指针和链尾指针的动态变化决定链表的长度D. 在栈中，栈顶指针的动态变化决定栈中元素的个数32. 在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为______。A. 3n/4B. nC. n/2D. n/433. 某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为______。A. 1B. 0C. 1或0D. 不确定34. 某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH。该完全二叉树的前序序列为______。A. ABCDEFGHB. ABDHECFGC. HDBEAFCGD. HDEBFGCA35. 下列叙述中正确的是______。A. 带链栈的栈底指针是固定的B. 若带链队列的队头指针与队尾指针相同，则队列为空C. 若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素D. 带链栈的栈底指针是随栈的操作而动态变化的36. 设一棵树的度为3，其中没有度为2的结点，且叶子结点数为6。该树中度为3的结点数为______。A. 不可能有这样的树B. 1C. 2D. 337. 下列叙述中正确的是______。A. 数组是长度固定的线性表B. 矩阵是非线性结构C. 对线性表只能作插入与删除运算D. 线性表中各元素的数据类型可以不同38. 设顺序表的长度为n。下列排序方法中，最坏情况下比较次数小于n(n-1)/2的是______。A. 简单插入排序B. 快速排序C. 堆排序D. 冒泡排序39. 设表的长度为20。则在最坏情况下，冒泡排序的比较次数为______。A. 90B. 20C. 19D. 19040. 设一棵树的度为3，共有27个结点，其中度为3，2，0的结点数分别为4，1，10。该树中度为1的结点数为______。A. 不可能有这样的树B. 13C. 11D. 1241. 设二叉树共有375个结点，其中度为2的结点有187个。则度为1的结点个数是______。A. 188B. 1C. 0D. 不可能有这样的二叉树42. 从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是______。A. 循环链表B. 双向链表C. 单向链表D. 二叉链表43. 下列叙述中错误的是______。A. 线性结构一定能采用顺序存储结构B. 非线性结构一定不能采用顺序存储结构C. 有的非线性结构也能采用顺序存储结构D. 线性结构也能采用链式存储结构44. 下列叙述中正确的是______。A. 快速排序也适用于线性链表B. 链表只能是非线性结构C. 链表可以是线性结构也可以是非线性结构D. 对分查找也适用于有序链表45. 下列叙述中错误的是______。A. 具有多个指针域的链表也可能是线性结构B. 循环队列属于线性结构C. 采用顺序存储的完全二叉树属于线性结构D. 具有两个以上根结点的数据结构一定是非线性结构46. 下列排序法中，每经过一次元素的交换会产生新的逆序的是______。A. 冒泡排序B. 快速排序C. 简单插入排序D. 简单选择排序47. 树的度为3，共有31个结点，但没有度为1和2的结点。则该树中度为3的结点数为______。A. 9B. 不可能有这样的树C. 10D. 148. 设某树的度为3，且度为3的结点数为5，度为2的结点数为4，没有度为1的结点。则该树中总的结点数为______。A. 24B. 12C. 15D. 不可能有这样的树49. 某系统总体结构如下图所示，系统结构图的最大扇入数是______。 A. 2B. 3C. 4D. 550. 某系统总体结构图如下图所示，该系统总体结构图的深度是______。 A. 7B. 6C. 3D. 251. 设有下列二叉树，此二叉树中序遍历的结果为______。 A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA52. 某系统总体结构如下图所示，该系统结构图的宽度是______。 A. 5B. 4C. 3D. 253. 某系统结构图如下图所示，该系统结构图的深度是______。 A. 4B. 3C. 2D. 1 提交成功！
全国二级理论——1.2数据结构与算法 本套试题共50题。 1. 班级：格式如“19计应31”2. 学号：10位数完整格式3. 姓名：4. 下列链表中，其逻辑结构属于非线性结构的是______。A. 二叉链表B. 循环链表C. 双向链表D. 带链的栈5. 某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为______。A. n+1B. n-1C. 2nD. n/26. 某二叉树共有845个结点，其中叶子结点有45个，则度为1的结点数为______。A. 400B. 754C. 756D. 不确定7. 栈和队列的共同点是______。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点8. 设循环队列为Q(1:m)，初始状态为front=rear=m。现经一系列入队与退队操作后，front=rear=m-1，则______。A. 该循环队列已空B. 该循环队列已满C. 该循环队列中有1个元素D. 该循环队列已空或已满9. 下列叙述中正确的是______。A. 算法的空间复杂度是指算法程序控制结构的复杂程度。B. 算法的空间复杂度与算法所处理的数据存储空间有关。C. 算法的空间复杂度是指算法程序中指令的条数。D. 压缩数据存储空间不会降低算法的空间复杂度。10. 已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是______。A. 堆排序B. 直接插入排序C. 快速排序D. 直接选择排序11. 下列叙述中正确的是______。A. 算法的效率只与问题的规模有关，而与数据的存储结构无关B. 算法的时间复杂度是指执行算法所需要的计算工作量C. 数据的逻辑结构与存储结构是一一对应的D. 算法的时间复杂度与空间复杂度一定相关12. 下列叙述中正确的是______。A. 算法复杂度是指算法控制结构的复杂程度B. 算法复杂度是指设计算法的难度C. 算法的时间复杂度是指设计算法的工作量D. 算法的复杂度包括时间复杂度与空间复杂度13. 算法的时间复杂度是指______。A. 设计该算法所需的工作量B. 执行该算法所需要的时间C. 算法中指令的条数D. 执行该算法时所需要的基本运算次数14. [假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。冒泡排序法与快速排序法本质上都是通过数据元素的交换来逐步消除线性表中的逆序。]15. 下列关于队列的叙述中正确的是______。A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表16. 设循环队列的存储空间为Q(1:35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为______。A. 15B. 16C. 20D. 0或3517. 算法分析的目的是______。A. 找出数据结构的合理性B. 找出算法中输入和输出之间的关系C. 分析算法的易懂性和可靠性D. 分析算法的效率以求改进18. 深度为5的完全二叉树的结点数不可能是______。A. 15B. 16C. 17D. 1819. 算法的空间复杂度是指______。A. 算法在执行过程中所需要的计算机存储空间B. 算法所处理的数据量C. 算法程序中的语句或指令条数D. 算法在执行过程中所需要的临时工作单元数20. 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为______。A. 219B. 221C. 229D. 23121. 下列叙述中正确的是______。A. 存储空间连续的数据结构一定是线性结构B. 存储空间不连续的数据结构一定是非线性结构C. 没有根结点的非空数据结构一定是线性结构D. 具有两个根结点的数据结构一定是非线性结构22. 某二叉树的前序遍历序列为 ABCDE ，中序遍历序列为 CBADE ，则后序遍历序列为______。A. CBADEB. EDABCC. CBEDAD. EDCBA23. 下列各组排序法中，最坏情况下比较次数相同的是______。A. 冒泡排序与快速排序B. 简单插入排序与希尔排序C. 希尔排序与堆排序D. 快速排序与希尔排序24. 在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是______。A. O(n)B. O(n2)C. O(log2n)D. O(nlog2n)25. 下列叙述中正确的是______。A. 非线性结构只能采用链式存储结构B. 非线性结构只能用多重链表表示C. 所有数据结构既可以采用顺序存储结构，也可以采用链式存储结构D. 有的非线性结构也能采用顺序存储结构26. 下列关于栈叙述正确的是______。A. 栈顶元素最先能被删除B. 栈顶元素最后才能被删除C. 栈底元素永远不能被删除D. 以上三种说法都不对27. 下列数据结构中，能用二分法进行查找的是______。A. 顺序存储的有序线性表B. 线性链表C. 二叉链表D. 有序线性链表28. 下列数据结构中为非线性结构的是______。A. 双向链表B. 循环队列C. 循环链表D. 二叉链表29. 某二叉树中共有350个结点，其中200个为叶子结点，则该二叉树中度为2的结点数为______。A. 149B. 150C. 199D. 不可能有这样的二叉树30. 在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为______。A. nB. (n+1)/2C. 3n/4D. n/431. 下列叙述中正确的是______。A. 在线性链表中，头指针和链尾指针的动态变化决定链表的长度B. 在循环队列中，队尾指针的动态变化决定队列的长度C. 在循环链表中，头指针和链尾指针的动态变化决定链表的长度D. 在栈中，栈顶指针的动态变化决定栈中元素的个数32. 在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为______。A. 3n/4B. nC. n/2D. n/433. 某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为______。A. 1B. 0C. 1或0D. 不确定34. 某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH。该完全二叉树的前序序列为______。A. ABCDEFGHB. ABDHECFGC. HDBEAFCGD. HDEBFGCA35. 下列叙述中正确的是______。A. 带链栈的栈底指针是固定的B. 若带链队列的队头指针与队尾指针相同，则队列为空C. 若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素D. 带链栈的栈底指针是随栈的操作而动态变化的36. 设一棵树的度为3，其中没有度为2的结点，且叶子结点数为6。该树中度为3的结点数为______。A. 不可能有这样的树B. 1C. 2D. 337. 下列叙述中正确的是______。A. 数组是长度固定的线性表B. 矩阵是非线性结构C. 对线性表只能作插入与删除运算D. 线性表中各元素的数据类型可以不同38. 设顺序表的长度为n。下列排序方法中，最坏情况下比较次数小于n(n-1)/2的是______。A. 简单插入排序B. 快速排序C. 堆排序D. 冒泡排序39. 设表的长度为20。则在最坏情况下，冒泡排序的比较次数为______。A. 90B. 20C. 19D. 19040. 设一棵树的度为3，共有27个结点，其中度为3，2，0的结点数分别为4，1，10。该树中度为1的结点数为______。A. 不可能有这样的树B. 13C. 11D. 1241. 设二叉树共有375个结点，其中度为2的结点有187个。则度为1的结点个数是______。A. 188B. 1C. 0D. 不可能有这样的二叉树42. 从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是______。A. 循环链表B. 双向链表C. 单向链表D. 二叉链表43. 下列叙述中错误的是______。A. 线性结构一定能采用顺序存储结构B. 非线性结构一定不能采用顺序存储结构C. 有的非线性结构也能采用顺序存储结构D. 线性结构也能采用链式存储结构44. 下列叙述中正确的是______。A. 快速排序也适用于线性链表B. 链表只能是非线性结构C. 链表可以是线性结构也可以是非线性结构D. 对分查找也适用于有序链表45. 下列叙述中错误的是______。A. 具有多个指针域的链表也可能是线性结构B. 循环队列属于线性结构C. 采用顺序存储的完全二叉树属于线性结构D. 具有两个以上根结点的数据结构一定是非线性结构46. 下列排序法中，每经过一次元素的交换会产生新的逆序的是______。A. 冒泡排序B. 快速排序C. 简单插入排序D. 简单选择排序47. 树的度为3，共有31个结点，但没有度为1和2的结点。则该树中度为3的结点数为______。A. 9B. 不可能有这样的树C. 10D. 148. 设某树的度为3，且度为3的结点数为5，度为2的结点数为4，没有度为1的结点。则该树中总的结点数为______。A. 24B. 12C. 15D. 不可能有这样的树49. 某系统总体结构如下图所示，系统结构图的最大扇入数是______。 A. 2B. 3C. 4D. 550. 某系统总体结构图如下图所示，该系统总体结构图的深度是______。 A. 7B. 6C. 3D. 251. 设有下列二叉树，此二叉树中序遍历的结果为______。 A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA52. 某系统总体结构如下图所示，该系统结构图的宽度是______。 A. 5B. 4C. 3D. 253. 某系统结构图如下图所示，该系统结构图的深度是______。 A. 4B. 3C. 2D. 1 提交成功！
8. 设循环队列为Q(1:m)，初始状态为front=rear=m。现经一系列入队与退队操作后，front=rear=m-1，则______。A. 该循环队列已空B. 该循环队列已满C. 该循环队列中有1个元素D. 该循环队列已空或已满
9. 下列叙述中正确的是______。A. 算法的空间复杂度是指算法程序控制结构的复杂程度。B. 算法的空间复杂度与算法所处理的数据存储空间有关。C. 算法的空间复杂度是指算法程序中指令的条数。D. 压缩数据存储空间不会降低算法的空间复杂度。
11. 下列叙述中正确的是______。A. 算法的效率只与问题的规模有关，而与数据的存储结构无关B. 算法的时间复杂度是指执行算法所需要的计算工作量C. 数据的逻辑结构与存储结构是一一对应的D. 算法的时间复杂度与空间复杂度一定相关
12. 下列叙述中正确的是______。A. 算法复杂度是指算法控制结构的复杂程度B. 算法复杂度是指设计算法的难度C. 算法的时间复杂度是指设计算法的工作量D. 算法的复杂度包括时间复杂度与空间复杂度
14. [假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。冒泡排序法与快速排序法本质上都是通过数据元素的交换来逐步消除线性表中的逆序。]
16. 设循环队列的存储空间为Q(1:35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为______。A. 15B. 16C. 20D. 0或35
21. 下列叙述中正确的是______。A. 存储空间连续的数据结构一定是线性结构B. 存储空间不连续的数据结构一定是非线性结构C. 没有根结点的非空数据结构一定是线性结构D. 具有两个根结点的数据结构一定是非线性结构
25. 下列叙述中正确的是______。A. 非线性结构只能采用链式存储结构B. 非线性结构只能用多重链表表示C. 所有数据结构既可以采用顺序存储结构，也可以采用链式存储结构D. 有的非线性结构也能采用顺序存储结构
30. 在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为______。A. nB. (n+1)/2C. 3n/4D. n/4
31. 下列叙述中正确的是______。A. 在线性链表中，头指针和链尾指针的动态变化决定链表的长度B. 在循环队列中，队尾指针的动态变化决定队列的长度C. 在循环链表中，头指针和链尾指针的动态变化决定链表的长度D. 在栈中，栈顶指针的动态变化决定栈中元素的个数
32. 在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为______。A. 3n/4B. nC. n/2D. n/4
35. 下列叙述中正确的是______。A. 带链栈的栈底指针是固定的B. 若带链队列的队头指针与队尾指针相同，则队列为空C. 若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素D. 带链栈的栈底指针是随栈的操作而动态变化的