发布时间 : 星期日 文章山东专升本计算机专业数据结构练习题 - 图文更新完毕开始阅读
济南铁道职业技术学院 专升本辅导教材 数据结构
第六章 图 历年考试题
1．若
A．vi邻接于vj B．vj邻接于vi
C．vi和vj相互邻接
D．vi与vj不相邻接 2．在一个带权连通图G中，权值最小的边一定包含在G的（ ）
A．最小生成树中 B．深度优先生成树中 C．广度优先生成树中
D．深度优先生成森林中
3．下列数据组织形式中，（ ）的各个结点可以任意邻接。
A．集合
B．树形结构 C．线性结构
D．图状结构
4．邻接表是图的一种（ ）
A．顺序存储结构 B．链式存储结构 C．索引存储结构
D．散列存储结构 5．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（ A．G肯定不是完全图
B．G一定不是连通图
C．G中一定有回路 D．G有2个连通分量 6．一个带权的无向连通图的最小生成树（ ）
A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存在 7．下列有关图遍历的说法中不正确的是（ ）
A．连通图的深度优先搜索是一个递归过程
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法
D．图的遍历要求每一顶点仅被访问一次
8.n个顶点的有向完全图中含有向边的数目最多为( ) A.n-1 B.n C.n(n-1)/2 D.n(n-1)
9.已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为( ) A.a d b e f c B.a d c e f b C.a d c b f e D.a d e f c b
第 45 页 共 63 页
）
济南铁道职业技术学院 专升本辅导教材 数据结构
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 页