Question

在线等 各位大神们 快来啊啊！！

一、单项选择题（每题5分，共30分）
1. 在数据结构中，从逻辑上可以把数据结构分成（ C ）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构
C．线性结构和非线性结构 D．内部结构和外部结构
2. 设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（c ）。
A．连接 B．求子串
C．模式匹配 D．判子串
3. 一个n个顶点的连通无向图，其边的个数至少为（　A　）。
A．n-1 B．n
C．n+1 D．nlogn
4. 要连通具有n个顶点的有向图，至少需要（　b　）条边。
A．n-l B．n
C．n+l
5. 关键路径是事件结点网络中（　a　）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路
6.一个有n个顶点的无向连通图，它所包含的连通分量个数为（　b　）。
A．0 B．1
C．n D．n+1
二、填空题（每空2分，共20分）
1. 数据结构是指_逻辑结构________结构和_物理结构________结构两种，通常是指____逻辑结构_____结构。
2. 线性表的两种存储结构分别为___顺序存储方式______和___连接存储方式______。
3. 单链表是_________的链接存储表示。
4. 从一个栈删除元素时，首先取出_________，然后再使_________减1。
5. 一个字符串相等的充要条件是 和 。
三、算法（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<r(j).key DO
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

4. 要连通具有n个顶点的有向图，至少需要（　A　）条边。
A．n-l B．n
C．n+l
3. 单链表是__线性表_______的链接存储表示。
4. 从一个栈删除元素时，首先取出_栈顶元素________，然后再使__栈顶指针top_______减1。
5. 一个字符串相等的充要条件是 字符串长度 和 对应的每个字符都相等 。
问题一：这是什么类型的排序算法，该排序算法稳定吗？直接插入排序，稳定
问题二：设置r(O)的作用是什么？若将WHILE-DO 语句中判断条件改为x.key<=r(j).KEY,该算法将会有什么变化，是否还能正确工作？r(O)有岗哨作用，改为x.key<=r(j).KEY,该算法不稳定了，能正确工作