大专考试数据结构题一、单项选择题（每题5分，共30分）1.以下说法正确的是（）。A．连能分量是无向图中的极小连通子图B．强连通分量是有向图中的极大强连通子图C．在一个有向图

Question

大专考试数据结构题
一、单项选择题（每题5分，共30分）
1. 以下说法正确的是（　　）。
A．连能分量是无向图中的极小连通子图
B．强连通分量是有向图中的极大强连通子图
C．在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧
D．对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图
2. 求解最短路径的Floyd算法的时间复杂度为(　　)。
A．O（n） B．O（n+c）
C．O（n*n） D．O（n*n*n）
3. 采用邻接表存储的图，其广度优先遍历类似于二叉树的（ ）。
A．按层次遍历 B．中序遍历
C．后序遍历 D．先序遍历
4. 假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判断队空的条件为（ ）。
A．front+1= =rear B．rear+1= =front
C．front= =0 D．front= =rear
5. 从一个顺序循环队列中删除元素时，首先需要（ ）。
A．前移队首指针 B．后移队首指针
C．取出队首指针所指位置上的元素 D．取出队尾指针所指位置上的元素
二、填空题（每空2分，共20分）
1. 在栈的运算中，栈的插入操作称为_________或_________，栈的删除操作称为或_________。
2. 当栈满的时候，再进行入栈操作就会产生_________，这种情况的溢出称为_________；当栈空的时候，如果再进行出栈操作，也会_________，这种情况下的溢出称为_________。
3. 串中字符的个数称为串的 。
4. 一个连通图的　　　是一个极小连通子图。
三、算法（10分）
请阅读下列算法，回答问题
PROCEDURE sort（r，n）
BEGIN
FOR i:=2 TO n DO
BEGIN
x:=r(i)；r(O):=x；j:=i-1；
WHILE x.key BEGIN
r(j+1):=r(j); j:=j-1
END;
r(j+1):=x
END
END;
问题一：这是什么类型的排序算法，该排序算法稳定吗？
问题二：设置r(O)的作用是什么？若将WHILE-DO 语句中判断条件改为x.key<=r(j).KEY,该算法将会有什么变化，是否还能正确工作？
四、应用题（共40分）
1、 分别论述在稠密索引文件和非稠密索引文件的查找一个记录时，首先查什么？然后查什么？
2、 散列表存储的基本思想是什么？
3、 对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？
4、 在执行某个排序方法的过程中，出现排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的。这种说法对吗？为什么？

Answer 1

单选
1 B2C 3D 4D 5B
填空
1 进栈，入栈，退栈
2 溢出 ，上溢，溢出，下溢
3 长度
4 生成树
算法
1 直接插入排序，稳定
2 r(O)有岗哨作用，改为x.key<=r(j).KEY,该算法不稳定了，能正确工作
应用题
1稠密索引文件查找记录：由于数据文件中记录不按关键字顺序排列，必须对每个记录建立一个索引记录（或索引项）。在索引项中进行“预查找”，即从索引项中便可确定待查找记录是否存在。
非稠密索引文件查找记录：首先要在非稠密索引中找到小于特定值的最大搜索码的索引项所在的位置，然后根据索引项中的记录指针找到文件中的记录。由于是非稠密索引，找到的记录不一定是我们需要的，因此还要根据顺序文件的搜索码链表（记录在逻辑上按照搜索码顺序链接起来形成的）去查找我们需要的记录即可。
2散列表存储的基本思想是用关键字的值决定数据元素的存储地址
3 遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。
4这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对4，3，2，1起泡排序就可否定本题结论。