数据结构与算法一有答案.docx
《数据结构与算法一有答案.docx》由会员分享，可在线阅读，更多相关《数据结构与算法一有答案.docx（10页珍藏版）》请在冰点文库上搜索。
数据结构与算法一有答案
数据结构与算法
（一）
一、选择题
1.分析算法的目的是______。
A.找出数据结构的合理性
B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进
D.分析算法的易懂性和文档
答案：
C
2.计算机算法指的是______，它必须具备输入、输出，可执行性、确定性和有穷性。
A.计算方法
B.排序方法
C.解决问题的有限运算序列
D.调度方法
答案：
C
3.下列关于数据结构的叙述中，正确的是______。
A.实际应用中，队列的顺序存储结构一般采用循环队列的形式
B.递推算法结构程序一般比递归算法结构程序更精练
C.树是一种线性结构
D.用一维数组存储二叉树，总是以先序遍历的顺序存储各结点
答案：
A
4.在算法设计基本方法中，______是从初始条件出发，逐次推出所需求的结果。
A.递推
B.递归
C.列举法
D.归纳法
答案：
A
5.设计一个“判别在表达式中左、右括号是否配对出现”的算法，采用______数据结构最佳。
A.线性表的顺序存储结构
B.栈
C.队列
D.线性表的链式存储结构
答案：
B
6.一个队列的入列序号是1，2，3，4，则队列的输出系列是______。
A.4，3，2，1
B.1，2，3，4
C.1，4，3，2
D.3，2，4，1
答案：
B
7.用数组A[0…m-1]存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为______。
A.（rear-front+re）modm
B.（rear-front+m+1）modm
C.（rear-front+m-1）modm
D.（rear-front-m-1）modm
答案：
A
8.链栈与顺序栈相比，有一个比较明显的优点是______。
A.插入操作更加方便
B.通常不会出现栈满情况
C.不会出现栈空的情况
D.删除操作更加方便
答案：
B
9.如果以链表为栈的存储结构，则出栈操作是______。
A.必须判别栈是否为满
B.必须判别栈是否为空
C.判别栈元素的类型
D.对栈不作任何判别
答案：
B
10.以下叙述正确的是______。
A.线性表的线性存储结构优于链表存储结构
B.在树形结构中，树根结点没有前驱结点
C.栈的操作方式是先进先出
D.队列的操作方式是先进后出
答案：
B
11.设栈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
答案：
C
12.下面关于数据结构的叙述中，正确的是______。
A.顺序存储方式的优点是存储密度大，且插入、删除运算效率高
B.链表中的每一个结点都包含恰好一个指针
C.包含n个结点的二叉排序树的最大检索长度为log2n
D.将一棵树转换为二叉树后，根结点没有右子树
答案：
D
13.下面关于二叉树的叙述中正确的是______。
A.度为2的树称为二叉树
B.二叉树的度肯定是2
C.二叉树中所有结点的度都是2
D.由3个结点可以构造出5种不同的二叉树
答案：
D
14.若对一棵二叉树进行中序遍历得到的结果是（B，D，A，G，H，E，C，F），进行后序遍历的结果是DBHGEFCA，那么这棵二叉树进行前序遍历得到的结果是______。
A.（A，B，D，C，E，G，H，F）
B.（A，B，D，C，E，H，G，F）
C.（D，B，A，C，E，G，H，F）
D.无法确定
答案：
A
15.按照二叉树的定义，深度为5的二叉树至多有______个结点。
A.16
B.32
C.10
D.31
答案：
D
16.完全二叉树中，若一个结点是叶结点，则它没有______。
A.左子结点
B.右子结点
C.左子结点和左子结点
D.左子结点、右子结点和兄弟结点
答案：
C
17.若完全二叉树共有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，则该结点肯定没有父结点
答案：
B
18.二分法查找______存储结构。
A.只适合于链式
B.只适合于顺序
C.既适合于顺序也适合于链式
D.既不适合于顺序也不适合于链式
答案：
B
19.对线性表进行二分法检索。
其前提条件是______。
A.线性表以顺序方式存储，并且按关键码值排好序
B.线性表以顺序方式存储，并且按关键码的检索频率排好序
C.线性表以链接方式存储，并且按关键码值排好序
D.线性表以链接方式存储，并且按关键码的检索频率排好序
答案：
A
20.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为______。
A.n
B.n/2
C.（n+1）/2
D.（n-1）/2
答案：
C
21.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为______。
A.O（log2n）
B.O（n）
C.O（nlog2n）
D.O（n2）
答案：
A
22.对关键字序列（11，12，13，14，15）采用对半查找算法查找关键字11，则关键字之间比较次数为______。
A.1
B.2
C.3
D.4
答案：
B
23.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是______。
A.希尔排序
B.冒泡排序
C.插入排序
D.选择排序
答案：
D
24.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用______排序法。
A.希尔排序
B.冒泡排序
C.堆排序
D.快速排序
答案：
C
25.下述几种排序方法中，______是最简单的交换类排序方法。
A.冒泡排序
B.插入排序
C.快速排序
D.选择排序
答案：
A
26.对含有n个关键词的序列进行冒泡法排序，最少的比较次数是______。
A.n
B.n-1
C.n/2
D.n-2
答案：
B
27.对给定的整数序列（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）
答案：
C
28.一组记录的排序码为（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
答案：
B
二、填空题
1.一个算法通常由对数据对象的运算和操作以及算法的两种基本要素组成。
答案：
控制结构
2.算法复杂度包括时间复杂度和空间复杂度。
对空间复杂度一般可以用平均态和最坏情况复杂性来衡量：
而对于空间复杂度，一般指执行该算法所需要的。
答案：
内存空间
3.在数据结构的图形结构中，每个结点的前驱结点数和后续结点数可以个。
答案：
任意多
4.在树中，一个结点的直接子结点的个数称为该结点的。
答案：
一次数/度
5.设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最小结点数为。
答案：
k+1
6.已知一棵二叉树前序序列和中序序列分别为A，B，D，E，G，C，F，H和D，B，G，E，A，C，H，F，则该二叉树的后序序列为。
答案：
D，G，E，B，H，P，C，A
7.从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列正确位置上的方法，称为。
答案：
希尔排序
8.从未排序序列中挑选元素，将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为。
答案：
选择排序
9.在表为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为。
答案：
n+1
10.在插入排序、希尔排序、选择排序、堆排序和快速排序中，平均比较次数最少的排序是。
答案：
快速排序
11.在堆排序和快速排序中，若只从最坏情况下排序最快并且要节省内存考虑，则应选择方法。
答案：
堆排序
升级会员 