济南铁道职业技术学院 专升本辅导教材 数据结构
10．顶点数为n、边数为n(n-1)/2的无向图称为_____________。 1．一个具有n个顶点的有向完全图的弧数为________________。
12．若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的________。
13.若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为________。
14、 在用于表示有向图的邻接矩阵中, 对第i行的元素进行累加, 可得到第i 个顶点的（ ）度, 而对第j列的元素进行累加, 可得到第j个顶点的（ ）度。
15、 一个连通图的生成树是该图的（ ）连通子图。若这个连通图有n个顶点, 则它的生成树有（ ）条边。
16、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。 (1) 对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为（ A ），所有边链表中边结点的总数为（ B ）。
(2) 采用邻接表存储的图的深度优先遍历算法类似于树的（ C ）。 (3) 采用邻接表存储的图的广度优先遍历算法类似于树的（ D ）。
(4) 判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ E ）。 供选择的答案
A：① n ② n+1 ③ n-1 ④ n+e B：① e/2 ② e ③ 2e ④ n+e
C~D：① 中根遍历 ② 先根遍历 ③ 后根遍历 ④ 按层次遍历 E：① 求关键路径的方法 ② 求最短路径的Dijkstra方法 ③ 深度优先遍历算法 ④ 广度优先遍历算法
17．已知无向图G的邻接表如下，请写出其从顶点V2开始的深度优先搜索的序列。（4分）
18．下列函数MDFSForest的功能是，对一个采用邻接矩阵作存储结构的图进行深度优先搜索遍历，输出所得深度优先生成森林中各条边。请在空缺处填入合适内容，使其成为一个完整的算法。 #define MaxMun 20 //图的最大顶点数 typedef struct {
char vexs [MaxNum]; //字符类型的顶点表 int edges [MaxNum][MaxNum]; //邻接矩阵 int n, e; //图的顶点数和边数
}MGraph; //图的邻接矩阵结构描述 typedef enum {FALSE, TRUE} Boolean; Boolean visited [MaxNum];
void MDFSTree (MGraph *G, int i); void MDFSForest (MGraph *G) {
第 46 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
}
int i, k;
for (i=0; i
visited [i] = (1) ; for (k = 0; k
void MDFSTree (MGraph *G, int i) {
int j;
visited [i]=TRUE; for (j=0; j
if ( (2) ) {
printf (〃<%c, %c>〃G -> vexs [i], G -> vexs [j]); (3) ; }
} ｝
19．已知无向图G的邻接矩阵如下，假设对其每行元素访问时必须从右到左，请写出从V0开始的深度优先搜索的序列。（4分）
V0V1V2V3V4????????01100?10111??11011?
?01101?01110??v1v2v3v4v021、下列算法是根据一个带权图的邻接矩阵存储结构G1建立该图的邻接表存储结构G2，请填入合适的内
容，使其成为一个完整的算法。
void convertM(MGraph *G1,ALGraph *G2) {
int i,j;
EdgeNode * p; G2->n=G1->n; G2->e=G1->e;
for(i=0;i
G2->adjlist[i].vertex=G1->vexs[i]; G2->adjlist[i].firstedge= (1) ; }
for (i=0;i
for (j=0;j
if(G1->edges[i][j] 第 47 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 { p=(EdgeNode *) malloc(sizeof(EdgeNode)); p->weight= (2) ; p->adjvex=j; p->next=G2->adjlist[i].firstedge; (3) ; } } 22、写出求连通网络的最小生成树的Prim算法的实现。 23、写出求连通网络的最小生成树的克鲁斯卡尔算法的实现。 第七章 查找 习 题 7．1 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)用来惟一区分文件中不同记录的属性或属性组称为主关键字。 ( ) (2)查找成功与否的关键在于是否按主关键字查找。 ( ) (3)顺序文件必须用一片地址连续的存储空间来存放。 ( ) (4)只有在顺序存储结构上才能采用顺序查找方法。 ( ) (7)只要按值有序排列的线性表采用顺序存储结构就可以采用折半查找方法。 ( ) (8)建立稠密索引的优点是节省存储空间。 ( ) (9)分块查找的效率与文件中的记录被分成多少块有关。 ( ) (10)分块查找过程是首先查找索引表，然后再到相应的块中具体查找记录。 ( ) (11)B-树和B十树都是用来实现动态索引的。 ( ) (12)在B-树上可以进行顺序查找。 ( 1 (13)在B+树上可以进行顺序查找。 ／ 1 (14)采用散列方法存储线性表，不能存储数据元素之间的关系。 ( ) (15)在散列文件中进行查找不涉及关键字的比较。 ( ) (16)散列冲突是指同一个关键字对应了多个不同的散列地址。 ( ) (17)散列表的负载因子等于存人散列表中的关键字的个数。 ( ) (18)在散列表的查找过程中，关键字的比较次数与表中关键字的数目直接相关。 ( ) (19)在利用线性探测法处理冲突的散列表中，散列函数值相同的关键字总是存放在一片地址连续的存储单元中。 (20)在采用链地址法处理冲突的散列表中，散列函数值相同的关键字是链接在同一个链表中的。 ( ) 7．2单项选择题。 (1)衡量查找算法性能好坏的主要标准是 。 A．参加比较的关键字值的多少 B．被查找的关键字值在关键字序列中的位置 C.关键字序列中是否存在被查找关键字值 D．关键字值的平均比较次数的多少 (2)顺序查找方法的优点之一是— 。 · A．对于被查找对象几乎没有限制 B．适合排序连续顺序文件的查找 C.适合链接顺序文件的查找 D．查找时间效率高 第 48 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 (3)对线性表采用折半查找，该线性表必须 。 A．元素按值有序排列 B．采用顺序结构 C．元素按值有序排列，并且采用顺序存储结构 n元素按值有序排列，并且采用链式存储结构 (4)下面的说法中，不正确的是——。 A．折半查找方法不适用于按值有序链接的链表的查找 B．折半查找方法适用于按值有序的顺序表的查找 C.折半查找方法适用于按关键字值大小有序排列的顺序文件的查找 D．折半查找方法适用于排序连续顺序文件的查找 (5)在有序表(k1，k2，?，k9，)中采用折半查找方法查找99次，其中，至少有一个元素被比较了99次，该元素是——。 A．K99 B．k50 C．K49 D．k1 (6)为了实现分块查找，线性表必须采用——结构。 A．顺序存储 B．链式存储 C．索引存储 D．散列存储 (7)只能在顺序存储结构上才能实现的查找方法是 法。 A．顺序查找 B．树型查找 C．折半查找 D．散列查找 (8)在具有15个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录，需要进行——次关键字的比较。 A．0 B．4 C．5 D．15 (9)若在100个记录中查找其中任意一个记录，最多只要比较5次，则所采用的查找方法可能是——。 A．折半查找 B．树型查找 C．分块查找 D．散列查找 (10)若在n个记录中查找其中任意一个记录至少要比较2次，则所采用的查找方法可能是 A．分块查找 B‘折半查找 C．树型查找 D．散列查找 (11)折半查找过程可以利用一棵称之为判定树的二叉树来描述。在长度为12的序列中进行折半查找对应的判定树的根结点的右孩子的值(某元素在序列中的位置)是——。 A．7 B．8 C．9 D．10 (12)若在序列中采用折半查找方法进行查找，用来描述该查找过程的判定树的形状与——有关。 A．序列中元素的值 B．序列中元素的排列次序 C．序列中元素的类型 D．序列中元素的个数 (13)在某序列中采用折半查找方法查找某个元素，依次被比较过的元素在该序列中的位置只能是——。 A．10，15，12，18，19 B．10，15，12，13，14 C．10，15，16，18，19 D．10，15，11，13，14 (14)在某序列中采用折半查找方法查找某个元素，依次被比较过的元素在该序列中的位置不可能是——。 A．10，5，7，8，9 B．10，5，2，1 C．10，5，6，7，8 D．10，5，7，6 (15)将数据元素2，4，6，8，10，12，14，16，18，20依次存放于一个一维数组中，然后采用折半查找方法查找元素12，被比较过的数组元素的下标依次为——。 A．10，16，12 B．10，12，16 C．4，7，5 D．4，5，7 (16)索引文件中的索引表具有的特点是————。 A．索引项按关键字值有序，并且由用户提供 B．索引项按关键字值有序，并且由系统提供 第 49 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 C．索引项按关键字值无序，并且由用户提供 D．索引项按关键宇值无序，并且由系统提供 (17)m阶B-树中的m是指——。 A．每个结点至少具有m棵子树 B．每个结点最多具有m棵子树 C．分支结点中包含的关键字的个数 D．m阶B-树的深度 (18)下面关于B-树和B+树的叙述中，不正确的是——。 A．B-树和B+树都是平衡的多分树 B．B-树和B+树都可以用于文件的索引结构 D．B—树和B+树都能有效地支持随机检索 (19)下面的命题中，不成立的是 。 A．m阶B-树中的每一个分支结点的子树的数量都小于或等于m。 B．m阶B-树中的每一个分支结点的子树的数量都大于或等于m／2上取整 C．m阶B-树中的任何一个结点的子树的深度都相等。 D．m阶B—树中有k个子树的分支结点包含k—1个关键字。 (20)评价散列函数质量好坏的标准是——。 A．函数是否简单 B．计算是否快 C．是否是解析式 D．函数的取值是否均匀 (21)在一个初始状态为空的散列表中依次插入关键字序列(MON，TUE，WED，THU，FRI， SAT，SUN)，散列函数为H(key)：i％7，其中，i为关键字key的第一个字母在英文字母表中的序号，地址值域为[0：6]，采用线性再散列法处理冲突。 (22)在具有n个元素的序列中进行查找，平均查找长度为O(n)的方法是——。 A．顺序查找方法 B．散列查找方法 C．分块查找方法 D．树型查找方法 7．3 填空题。 (1)文件的逻辑结构是指——，文件的物理结构是指——。 (2)文件在物理结构中通常有——、——和——三种组织方式。 (3)文件的关键字是——。 (4)文件最基本操作是 和 。 (5)对线性表采用折半查找方法，该线性表必须采用——存储结构，并且——。 (6)在按值有序的线性表(5，8，11，12，15，20，32，41，57)中采用折半查找法查找20需要进行——次元素间的比较。 (7)具有n个结点的判定树的深度h = —— 。 (8)若每个记录的查找概率相等，则在具有n个记录的顺序文件中采用顺序查找法的平均查 找长度ASL=——。 (9)在具有n个记录的排序连续顺序文件中采用折半查找法的平均查找长度ASL=？ (10)索引文件的索引表中的一个索引项是——之间的对照关系。 (11)索引文件包括——和——两个部分。 (12)索引表的特点是——，并且——。 (13)在索引文件中查找一个记录的过程是先查——，然后——。 (14)具有144项的表分成——块最好，若每块的最佳长度为8，则平均查找长度为—— (15)在3阶B-树上，每个分支结点包含的子树的数目最多为——，最少为——。 (16)一棵B+树上通常有两个头指针(即查找的人口指针)，其中一个指向——，另一个指向——。 第 50 页 共 63 页