发布时间 : 星期日 文章数据结构试题库更新完毕开始阅读2ba1d59cad51f01dc381f108
{ int i,j,n=G->n; ArcNode *p;
for (i=0;i { p=G->adjlist[i].firstarc; while (p!=NULL) { g.edges[i][p->adjvex]=1; p=p->nextarc; } } g.vexnum=n;g.arcnum=G->e; } 数据结构复习题：图 填空题 1、在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____出度_____，对于有向图来说等于该顶点的_____出度数_____。 2、已知一个无向图的邻接矩阵如下所示，则从顶点A出发按深度优先搜索遍历得到的顶点序列为__________，按广度优先搜索遍历得到的顶点序列为__________。 A B C D E F ┏0 1 1 0 1 0┓A ┃1 0 1 0 1 1┃B ┃1 1 0 1 0 0┃C ┃0 0 1 0 0 1┃D ┃1 1 0 0 0 1┃E ┗0 1 0 1 1 0┛F 3、对二叉排序树进行______遍历,可以得到按关键字从小到大排列的结点序列. 4、任何一棵子树的结点个数减边数等于_____,总边数等于各结点__度___之和. 5、己知一棵完全二叉树中共有562个结点，则该树中共有___281___个叶子结点. 6、在一个具有n个顶点的无向完全图中，包括有____________条边，在一个具有n个顶点的有向完全图中，包含有_____n(n-1)_______条件。 7、已知一个连通图的边集为{(1,2)3,(1,3)6,(1,4)8,(2,3)4,(2,5)10,(3,5)12,(4,5)2}，则度为３的顶点个数有____________个。 8、一个有向图的顶点集为{a,b,c,d,e,f},边集为{ 12、在有向图的邻接和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有_____出度_______和______入度______结点。 13、一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)},从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。 14、根据图的存储结构进行某种次序的遍历，从某顶点出发得到的顶点序列是______不唯一______的 - 41 - 数据结构复习题：图 问答题 1、无向图G如下图： B E / \\ / \\ A D G \\ / \\ / C F 试给出 (1)该图的邻接矩阵。 图G的邻接矩阵 ┏０ １ １ ０ ０ ０ ０┓ ┃１ ０ ０ １ ０ ０ ０┃ ┃１ ０ ０ １ ０ ０ ０┃ A＝┃０ １ １ ０ １ １ ０┃ ┃０ ０ ０ １ ０ ０ １┃ ┃０ ０ ０ １ ０ ０ １┃ ┗０ ０ ０ ０ １ １ ０┛ (2)该图的邻接表。 邻接表如见： ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ １│Ａ│ ┼→─┤Ｂ│ ┼→─┤Ｃ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ２│Ｂ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ３│Ｃ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐ ┌─┬─┐ ４│Ｄ│ ┼→─┤Ｂ│ ┼→─┤Ｃ│ ┼→┤Ｅ│＾├→─┤Ｆ│＾│ (3)从A出发的“深度优先”遍历序列。 ABDEGFC (4)从A出发的“广度优先”遍历序列。 ABCDEFG 2、用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是否有关? 答：设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n2，即顶点个数的平方，与图的边数无关。 3、对于稠密图和稀疏图,就存储空间而言,采用邻接矩阵和邻接表哪个更好些? 答：稠密图采用邻接矩阵好，稀疏图采用邻接表好。 4、请回答下列关于图的一些问题: (1) 有n个顶点的有向强连通图最多有多少条边?这样的图应该是什么形状? 最多有n(n-1)条边 (2) 有n个顶点的有向强连通图最少有多少条边?这样的图应该是什么形状? 最少有 n条边 (3) 表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵? - 42 - 106，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律） 5、对n个顶点的无向图和有向图,采用邻接矩阵和邻接表表示时,如何判别下列有关问题? (1) 图中有多少条边? (2) 任意两个顶点i和j是否有边相连? (3) 任意一个顶点的度是多少? 答：无向图采用邻接表时，⑴ 边表中的结点个数之和除以2。⑵ 第i个边表中是否含有结点j。⑶ 该顶点所对应的边表中所含结点个数。 6、己知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树的先序线索二叉树. 答：二叉树及线索二叉树（略）。 a b f c d g e h i j 先序序列为：abcdefghij 7、下列整数序列由选序遍历一棵二叉排序树得到:50,40,30,45,65,55,70,80.试构造一棵这样的二叉排序树. 答： 50 40 65 30 45 55 70 80 9 查找 - 43 - 沈阳理工大学应用技术学院 信息与控制学院 计算机科学与技术教研室 2011-5-8 数据结构复习题：查找 单选题 1、二分法查找___只适用于顺序__存储结构。 2、已知一个有序表为(12、18、24、35、47、50、62、83、90、115、134)，当二分查找值为90的元素时，___2__次比较后查找成功；当二分查找值为47的元素时，__4___次比较后查找成功。 3、散列函数有一个共同性质，即函数值应当以___同等概率__取其值域的每个值。 4、设散列地址空间为0～m－1,k为关键字，用p去除k，将所得的余数作为k的散列地址，即H(k)＝k % p。为了减少发生冲突的频率，一般取p为___小于m的最大素数__。 5、在一个无向图中,所有顶点的度之和等于边数的______倍。 6、一个有n个顶点的无向图最多有______条边。 7、具有6个顶点的无向图至少应有______条边才能确保是一个连通图。 8、在一个具有n个顶点的无向图中,要连通全部顶点至少需要__n-1___条边。 9、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵大小是______。 10、带权有向图G用邻接矩阵A存储,则vi 的入度等于A中______。 11、无向图的邻接矩阵是一个______。 12、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是______. 13、采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法. 14、采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法. 15、一个无向连通图的生成树是含有该连通图的全部顶点的___极小连通子图___. 16、任何一个无向连通图______最小生成树. 17、对于含有n个顶点的带权连通图,它的最小生成树是指图中任意一个___由n个顶点构成的边的权值之和最小的连通子图___. 18、设有无向图G=(V,E)和G`=(V`,E`),如G`是G的生成树,则下面不正确的说法是______. 19、若一个有向图中的顶点不能排成一个拓扑序列,则可断定该有向图___含有顶点数目大于1的强连通分 - 44 -