数据结构与算法(一)
(总分78,考试时间90分钟)
一、选择题
1. 计算机算法指的是 ______，它必须具备输入、输出，可执行性、确定性和有穷性。
A. 计算方法 B. 排序方法
C. 解决问题的有限运算序列 D. 调度方法
2. 设计一个“判别在表达式中左、右括号是否配对出现”的算法，采用 ______ 数据结构最佳。
A. 线性表的顺序存储结构 B. 栈
C. 队列 D. 线性表的链式存储结构
3. 若对一棵二叉树进行中序遍历得到的结果是(B，D，A，G，H，E，C，F)，进行后序遍历的结果是DBHGEFCA，那么这棵二叉树进行前序遍历得到的结果是 ______。
A. (A， B， D， C， E， G， H，
B. (A， B， D， C， E， H， G，
C. (D，B，A，C，E，G，H，
D. 无法确定
4. 一个队列的入列序号是1，2，3，4，则队列的输出系列是 ______。
A. 4，3，2，1 B. 1，2，3，4
C. 1，4，3，2 D. 3，2，4，1
5. 对关键字序列(11，12，13，14，15)采用对半查算法查关键字11，则关键字之间比较次数为 ______。
A. 1 B. 2
C. 3 D. 4
6. 如果以链表为栈的存储结构，则出栈操作是 ______。
A. 必须判别栈是否为满 B. 必须判别栈是否为空
数据结构与算法分析答案C. 判别栈元素的类型 D. 对栈不作任何判别
7. 在算法设计基本方法中， ______ 是从初始条件出发，逐次推出所需求的结果。
A. 递推 B. 递归
C. 列举法 D. 归纳法
8. 分析算法的目的是 ______。
A. 出数据结构的合理性 B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档
9. 若完全二叉树共有n个结点，且从根结点开始，按层序(每层从左到右)用正整数 0，1，2，…，n-1，从小到大对结点编号，则对于编号为k的结点，错误的是 ______。
A. 若k＞0，则该结点的父结点编号为[k/2]([]表示取整)
B. 若2k＞n-1，则编号为k的结点无右子树，但可能有左子树
C. 若2k+1＜=n-1，则编号为k的结点的右子结点编号为2k+1
D. 若k=0，则该结点肯定没有父结点
10. 用数组A[0…m-1]存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为 ______。
A. (rear-front+rmod m
B. (rear-front+m+1)mod m
C. (rear-front+m-1)mod m
D. (rear-front-m-1)mod m
11. 采用顺序查方法查长度为n的线性表时，每个元素的平均查长度为 ______。
A. n B. n/2
C. (n+1)/2 D. (n-1)/2
12. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用 ______ 排序法。
A. 希尔排序 B. 冒泡排序
C. 堆排序 D. 快速排序
13. 链栈与顺序栈相比，有一个比较明显的优点是 ______。
A. 插入操作更加方便 B. 通常不会出现栈满情况
C. 不会出现栈空的情况 D. 删除操作更加方便
14. 对线性表进行二分法检索。其前提条件是 ______ 。
A. 线性表以顺序方式存储，并且按关键码值排好序
B. 线性表以顺序方式存储，并且按关键码的检索频率排好序
C. 线性表以链接方式存储，并且按关键码值排好序
D. 线性表以链接方式存储，并且按关键码的检索频率排好序
15. 下列关于数据结构的叙述中，正确的是 ______。
A. 实际应用中，队列的顺序存储结构一般采用循环队列的形式
B. 递推算法结构程序一般比递归算法结构程序更精练
C. 树是一种线性结构
D. 用一维数组存储二叉树，总是以先序遍历的顺序存储各结点
16. 完全二叉树中，若一个结点是叶结点，则它没有 ______。
A. 左子结点 B. 右子结点
C. 左子结点和左子结点 D. 左子结点、右子结点和兄弟结点
17. 下面关于数据结构的叙述中，正确的是 ______。
A. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高
B. 链表中的每一个结点都包含恰好一个指针
C. 包含n个结点的二叉排序树的最大检索长度为log2n
D. 将一棵树转换为二叉树后，根结点没有右子树
18. 一组记录的排序码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为 ______。
A. 79，46，56，38，40，84
B. 84，79，56，38，40，46
C. 84，79，56，46，40，38
D. 84，56，79，40，46，38
19. 下述几种排序方法中， ______ 是最简单的交换类排序方法。
A. 冒泡排序 B. 插入排序
C. 快速排序 D. 选择排序
20. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 ______。
A. 希尔排序 B. 冒泡排序
C. 插入排序 D. 选择排序
21. 二分法查 ______ 存储结构。
A. 只适合于链式 B. 只适合于顺序
C. 既适合于顺序也适合于链式 D. 既不适合于顺序也不适合于链式
22. 对含有n个关键词的序列进行冒泡法排序，最少的比较次数是 ______ 。
A. n B. n-1
C. n/2 D. n-2
23. 下面关于二叉树的叙述中正确的是 ______。
A. 度为2的树称为二叉树 B. 二叉树的度肯定是2
C. 二叉树中所有结点的度都是2 D. 由3个结点可以构造出5种不同的二叉树
24. 对给定的整数序列(541，132，984，746，518，181，946，314，205，827)进行从小到大的排序时，采用快速排序(以中间元素518为基准)的第一趟扫描结果是 ______ 。
A. (181，132，314，205，541，518，946，827，746，984)
B. (541，132，827，746，518，181，946，314，205，984)
C. (205，132，314，181，518，746，946，984，541，827)
D. (541，132，984，746，827，181，946，314，205，518)
25. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈S，一个元
素出栈后即进入栈队列Q，若6个元素出队的顺序是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是 ______。
A. 6 B. 4
C. 3 D. 2
26. 按照二叉树的定义，深度为5的二叉树至多有 ______ 个结点。
A. 16 B. 32
C. 10 D. 31
27. 采用二分查方法查长度为n的线性表时，每个元素的平均查长度为 ______。
A. O(log2
B. O(
C. O(nlog2
D. O(n2)
28. 以下叙述正确的是 ______。
A. 线性表的线性存储结构优于链表存储结构 B. 在树形结构中，树根结点没有前驱结点
C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出
二、填空题
1. 一个算法通常由对数据对象的运算和操作以及算法的 【1】 两种基本要素组成。
2. 算法复杂度包括时间复杂度和空间复杂度。对空间复杂度一般可以用平均态和最坏情况复杂性来衡量：而对于空间复杂度，一般指执行该算法所需要的 【2】 。
3. 在数据结构的图形结构中，每个结点的前驱结点数和后续结点数可以 【3】 个。
4. 在树中，一个结点的直接子结点的个数称为该结点的 【4】 。
5. 设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最小结点数为 【5】 。
6. 已知一棵二叉树前序序列和中序序列分别为A，B，D，E，G，C，F，H和D，B， G，E，A，C，H，F，则该二叉树的后序序列为 【6】 。
7. 从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列正确位置上的方法，称为 【7】 。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论