综合练习（一）
课程名称：
算法与数据结构
总分：
100
分
答题时长：
120
分钟
出卷人：
刘辉
一
、单项选择题：(共
20
题，
40
分)
1
、
顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。
A.
110
B.
108
C.
100
D.
120
2
、
设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ ）。
A.
2
B.
3
C.
4
D.
6
3
、
以下不属于线性表的查找方法的是（ ）
A.
顺序查找
B.
树表的查找
C.
折半查找
D.
分块查找
4
、
用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。
A.
栈
B.
队列
C.
树
D.
图
5
、
在顺序查找算法中使用监视哨可以免去查找过程中每一步都要检测整个表是否查找完毕，下面循环语句正确的是（ ）
A.
for(i= ST.length; i>=1; - -i);
B.
for(i= ST.length; ST.elem[i].key！=key; --i);
C.
for(i= ST.length-1; i>=0; - -i);
D.
for(i= ST.length; ST.elem[i].key==key; --i);
6
、
下列对查找表经常进行的操作不正确的是（）
A.
查询某个“特定的”数据元素是否在表中
B.
检索某个“特定的”数据元素的各种属性
C.
在查找表中插入或删除一个数据元素
D.
对查找表进行排序或筛选
7
、
若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。
A.
非连通
B.
连通
C.
强连通
D.
有向
8
、
一个具有1025个结点的二叉树的高h为（ ）。
A.
11
B.
10
C.
11至1025之间
D.
10至1024之间
9
、
以下说法错误的是（ ）。
A.
求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B.
顺序存储的线性表可以随机存取
C.
由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D.
线性表的链式存储结构优于顺序存储结构
10
、
对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。
A.
先序
B.
中序
C.
后序
D.
从根开始按层次遍历
11
、
单链表的存储密度（ ）。
A.
大于1
B.
等于1
C.
小于1
D.
不能确定
12
、
假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（ ）。
A.
808
B.
818
C.
1010
D.
1020
13
、
设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（ ）。
A.
BA+141
B.
BA+180
C.
BA+222
D.
BA+225
14
、
线性表L=(a1，a2,……an)，下列说法正确的是（ ）。
A.
每个元素都有一个直接前驱和一个直接后继
B.
线性表中至少有一个元素
C.
表中诸元素的排列必须是由小到大或由大到小
D.
除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。
15
、
以下说法正确的是（ ）。
A.
数据元素是数据的最小单位
B.
数据项是数据的基本单位
C.
数据结构是带有结构的各数据项的集合
D.
一些表面上很不相同的数据可以有相同的逻辑结构
16
、
下面（ ）方法可以判断出一个有向图是否有环。
A.
深度优先遍历
B.
拓扑排序
C.
求最短路径
D.
求关键路径
17
、
一个递归算法必须包括（ ）。
A.
递归部分
B.
终止条件和递归部分
C.
迭代部分
D.
终止条件和迭代部分
18
、
线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。
A.
必须是连续的
B.
部分地址必须是连续的
C.
一定是不连续的
D.
连续或不连续都可以
19
、
分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。
A.
（100，80， 90， 60， 120，110，130）
B.
（100，120，110，130，80， 60， 90）
C.
（100，60， 80， 90， 120，110，130）
D.
(100，80， 60， 90， 120，130，110)
20
、
一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。
A.
250
B.
500
C.
254
D.
501
二
、
简答题
：(共
4
题，
20
分)
1
、
试对图6.36所示的AOE-网：
2
、
写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。
3
、
已知图6.32所示的有向图，请给出：
① 每个顶点的入度和出度；
② 邻接矩阵；
③ 邻接表；
④ 逆邻接表。
4
、
存储结构由哪两种基本的存储方法实现？
三
、
问答题
：(共
5
题，
40
分)
1
、
以二叉链表作为二叉树的存储结构，编写算法：求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
2
、
将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下： Typedef struct {int top[2],bot[2]; //栈顶和栈底指针 SElemType *V; //栈数组 int m; //栈最大可容纳元素个数 }DblStack
3
、
假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。
4
、
以二叉链表作为二叉树的存储结构，编写算法：输出二叉树中从每个叶子结点到根结点的路径。
5
、
以二叉链表作为二叉树的存储结构，编写算法：交换二叉树每个结点的左孩子和右孩子。