一、单选题
C01、在一个图中，所有顶点的度数之和等于图的边数的倍。
A)1/2 B)1 C)2 D)4
B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。
A)1/2 B)1 C)2 D)4
B03、有8个结点的无向图最多有条边。
A)14 B)28 C)56 D)112
C04、有8个结点的无向连通图最少有条边。
A)5 B)6 C)7 D)8
C05、有8个结点的有向完全图有条边。
A)14 B)28 C)56 D)112
B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。
A)栈 B)队列 C)树 D)图
A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。
A)栈 B)队列 C)树 D)图
A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。
A)O(n) B)O(e) C)O(n+e) D)O(n2)
C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。
A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2
B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。
A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6
D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。
A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3
A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。
A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2
A13、图的深度优先遍历类似于二叉树的。
A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历
D14、图的广度优先遍历类似于二叉树的。
A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历
B15、任何一个无向连通图的最小生成树。
A)只有一棵 B)一棵或多棵 C)一定有多棵 D)可能不存在
A16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。
A)n、2e B)n、e C)n、n+e D)2n、2e
C17、判断有向图是否存在回路，可以利用___算法。
A)关键路径 B)最短路径的Dijkstra C)拓扑排序 D)广度优先遍历
A18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。
A)图中每个顶点的入度 B)图中每个顶点的出度 C)图中弧的条数 D)图中连通分量的数目
C19、求最短路径的Dijkstra算法的时间复杂度是___。
A)O(n) B)O(n+e) C)O(n2) D)O(n*e)
B20、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为。
A)O(n) B)O(n+e) C)O(n2) D)O(n*e)
D21、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中。
A)第i行非∞的元素之和 B)第i列非∞的元素之和
C)第i行非∞且非0的元素个数 D)第i列非∞且非0的元素个数
C22、一个有n个顶点的无向图最多有条边。
A)n B)n(n-1) C)n(n-1)/2 D)2n
D23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。
A)n B)(n-1)2 C)n-1 D)n2
A24、对某个无向图的邻接矩阵来说，。
A)第i行上的非零元素个数和第i列的非零元素个数一定相等
B)矩阵中的非零元素个数等于图中的边数
C)第i行上，第i列上非零元素总数等于顶点v i的度数
D)矩阵中非全零行的行数等于图中的顶点数
D25、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为。
A)abecdf B)acfebd C)aebcfd D)aedfcb
B26、已知图的表示如上题，若从顶点a出发按广度搜索法进行遍历，则可能得到的一种顶点序列为。
A)abcedf B)abcefd C)aebcfd D)acfdeb
C27、有向图的邻接表存储结构如下图所示，则根据有向图的深度遍历算法，从顶点v1出发得到的顶点序列是。
A)v1,v2,v3,v5,v4 B)v1,v2,v3,v4,v5 C)v1,v3,v4,v5,v2 D)v1,v4,v3,v5,v2
B28、有向图的邻接表存储结构如上题所示，则根据有向图的广度遍历算法，从顶点v1出发得到的顶点序列是。
A)v1,v2,v3,v4,v5 B)v1,v3,v2,v4,v5 C)v1,v2,v3,v5,v4 D)v1,v4,v3,v5,v2
A29、一个图中有n个顶点且包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用次深度优先遍历算法。
A)k B)1 C)n-k D)n
D30、以下不正确的说法是。
A)无向图中的极大连通子图称为连通分量
B)连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C)图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D)有向图的遍历不可采用广度优先搜索方法
A31、图中有关路径的定义是___。
A)由顶点和相邻顶点序偶构成的边所形成的序列 B)由不同顶点所形成的序列
C)由不同边所形成的序列 D)上述定义都不是
B32、设无向图的顶点个数为n，则该图最多有___条边。
A)n-1 B)n(n-1)/2 C)n(n+1)/2 D)n
A33、一个n 个顶点的连通无向图，其边的个数至少为___。
A)n-1 B)n C)n+1 D)nlogn
B34、要连通具有n 个顶点的有向图，至少需要___条边。
A)n-l B)n C)n+l D)2n
B35、在一个无向图中，所有顶点的度数之和等于所有边数___倍。
A)1/2 B)2 C)1 D)4
C36、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的___倍。
A)1/2 B)2 C)1 D)4
A37、用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为___。
A)5 B)6 C)8 D)9
A38、用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是___。
A)逆拓扑有序 B)拓扑有序 C)无序的 D)原顺序
B39、下列___的邻接矩阵是对称矩阵。
A)有向图 B)无向图 C)AOV网 D)AOE网
BBD40、从邻接阵矩可以看出，该图共有①个顶点；如果是有向图该图共有②条弧；如果是无向图，则共有③条边。
① A)9 B)3 C)6 D)1 E)以上答案均不正确
② A)5 B)4 C)3 D)2 E)以上答案均不正确
③ A)5 B)4 C)3 D)2 E)以上答案均不正确
B41、当一个有N 个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是___。
B42、下列说法不正确的是___。
A)图的遍历是从给定的源点出发每一个顶点仅被访问一次 B)图的深度遍历不适用于有向图
C)遍历的基本算法有两种：深度遍历和广度遍历 D)图的深度遍历是一个递归过程
D43、无向图G=(V,E)，其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是___。
A)abecdf B)acfebd C)aebcfd D)aedfcb
D44、如图所示，在5个序列“aebdfc、acfdeb、aedfcb、aefdcb、aefdbc”，符合深度优先遍历的序列有___个。
A)5 B)4 C)3 D)2
CC45、图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是①，进行广度优先遍历得到的顶点序列是②。
① A)1354267 B)1347652 C)1534276 D)1247653 E)以上答案均不正确
② A)1534267 B)1726453 C)l354276 D)1247653 E)以上答案均不正确
B46、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为___。
A)O(n) B)O(n+e) C)O(n2) D)O(n3)
CABA47、下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为①，下面步骤重复n-1次：②；③；最后：④。
① A)VT，ET 为空 B)VT为所有顶点，ET为空
C)VT为网中任意一点，ET为空 D)VT为空，ET为网中所有边
② A)选i属于VT，j不属于VT，且(i,j)上的权最小 B)选i属于VT，j不属于VT，且(i,j)上的权最大
C)选i不属于VT，j不属于VT，且(i,j)上的权最小 D)选i不属于VT，j不属于VT，且(i,j)上的权最大
③ A)顶点i加入VT，(i,j)加入ET B)顶点j加入VT，(i,j)加入ET
C)顶点j加入VT，(i,j)从ET中删去 D)顶点i,j加入VT，(i,j)加入ET
④ A)ET中为最小生成树 B)不在ET中的边构成最小生成树
C)ET 中有n-1条边时为生成树，否则无解 D)ET中无回路时，为生成树，否则无解
A48、下面不正确的是___。
①求从指定源点到其余各顶点的Dijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义；
②利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)；(图用邻接矩阵表示)
③Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。
A)①②③ B)① C)①③ D)②③
A49、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
A)V1,V3,V4,V6,V2,V5,V7 B)V1,V3,V2,V6,V4,V5,V7 C)V1,V3,V4,V5,V2,V6,V7 D)V1,V2,V5,V3,V4,V6,V7
D50、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是___。
A)G中有弧
C)G中没有弧
A51、关键路径是事件结点网络中___。
A)从源点到汇点的最长路径 B)从源点到汇点的最短路径 C)最长回路 D)最短回路
C52、下面关于求关键路径的说法不正确的是___。
A)求关键路径是以拓扑排序为基础的
B)一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C)一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D)关键活动一定位于关键路径上
B53、下列关于AOE网的叙述中，不正确的是___。
A)关键活动不按期完成就会影响整个工程的完成时间
B)任何一个关键活动提前完成，那么整个工程将会提前完成
C)所有的关键活动提前完成，那么整个工程将会提前完成
D)某些关键活动提前完成，那么整个工程将会提前完成
二、填空题
01、在有向图中，以顶点v为终点的边的数目称为v的入度。
02、含n个顶点的无向连通图中至少含有n-1条边。
03、图的存储结构表示有邻接矩阵、邻接表、十字链表、邻接多重表等多种存储结构。
04、图的存储结构中，十字链表可以看成是有向图的邻接表和逆邻接表结合起来得到的一种链表。
05、遍历图的2种常见方法是深度遍历和广度遍历。
06、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。
07、如果n个顶点的图是一个环，则它有n棵生成树。
08、n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为O(n2)。若采用邻接表存储，则空间复杂度为O(n+e)。
09、图的逆邻接表存储结构只适用于有向图。
10、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是将邻接矩阵的第i行全部置0。
11、图采用邻接矩阵表示，则计算第i个顶点入度的方法是求邻接矩阵第i列非0元素之和。
12、用邻接矩阵表示图时，则判断任意两个顶点vi和vj之间是否有路径相连，只需要检查第i行第j列的元素是否为0即可。
13、用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为O(n2)；用克鲁斯卡尔(Kruskal)算法的时间复杂度是O(elog2e)。
14、对稀疏图最好用克鲁斯卡尔(Kruskal)算法求最小生成树，对稠密图最好用普里姆(Prim)算法来求解最小生成树。
15、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。
16、拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。
17、有向图G用邻接矩阵存储，则第i行的所有元素之和等于顶点i的出度。
18、有n个顶点的强连通有向图G至少有n条弧。
19、设有向图G的邻接矩阵为A，如果图中不存在弧
20、在n个顶点的无向图中，若边数>n-1，则该图必是连通图，此断言是错误的。(正确/错误)
21、在有n个顶点的有向图中，每个顶点的度最大可达2(n-1)。
22、若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑排序序列必定存在。(存在/不存在)
23、一个有向无环图的拓扑排序序列不一定是唯一的。(一定/不一定)
24、判断一个无向图是一棵树的条件是有n个顶点，n-1条边的无向连通图。
25、有向图G 的强连通分量是指有向图的极大强连通子图。
26、一个连通图的生成树是一个极小连通子图。
27、具有10个顶点的无向图，边的总数最多为45。
28、若用n表示图中顶点数目，则有n(n-1)/2条边的无向图成为完全图。
29、G 是一个非连通无向图，共有28条边，则该图至少有9个顶点。
30、在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要n条弧。
31、构造n个结点的强连通图，至少有n条弧。
32、有n个顶点的有向图，至少需要量n条弧才能保证是连通的。
33、N 个顶点的连通图用邻接矩阵表示时,该矩阵至少有2(N-1)个非零元素。
34、在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的度；对于有向图来说等于该顶点的出度。
35、在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是第i列非0元素个数。
36、对于一个具有n 个顶点e 条边的无向图的邻接表的表示，则表头向量大小为n，邻接表的边结点个数为2e。
37、已知一无向图G=(V,E)，其中V={a,b,c,d,e} E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a 开始遍历图，得到的序列为abecd，则采用的是深度优先遍历方法。
38、一无向图G(V,E)，其中V(G)={1,2,3,4,5,6,7}， E(G)={(1,2), (1,3), (2,4), (2,5), (3,6), (3,7), (6,7), (5,1)}，对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G'(V,E'), V(G')=V(G), E(G')= {(1,3), (3,6), (7,3), (1,2), (1,5), (2,4)}，则采用的遍历方法是广度优先遍历。
39、为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需队列存放被访问的结点以实现遍历。
40、构造连通网最小生成树的两个典型算法是普里姆(prim)算法和克鲁斯卡尔(Kruskal)算法。
41、Prim(普里姆)算法适用于求边稠密的网的最小生成树；kruskal(克鲁斯卡尔)算法适用于求边稀疏的网的最小生成树。
42、下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个节点V1，V2，．．．，Vn，用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
(1)若(Vi,Vj)是边，则A(i,j)的值等于(V i,V j)边上的权值，若(Vi,Vj)不是边，则A(i,j)的值是一个比任何边的权都大的数，矩阵的对角线元素全为0。
(2)构造最小生成树过程中，若节点Vi 已包括进生成树，就把相邻矩阵的对角线元素A(i,i)置成1，若(Vi,Vj)已包括进生成树，就把矩阵元素A(i,j)置成负值。
(3)算法结束时，相邻矩阵中为负的元素指出最小生成树的边。
43、有一个用于n 个顶点连通带权无向图的算法描述如下：(1)设集合T1与T2，初始均为空；(2)在连通图上任选一点加入T1；(3)以下步骤重复n-1 次：a)在i属于T1，j不属于T1的边中选最小权的边；b)该边加入T2。上述算法完成后，T2 中共有n-1条边，该算法称普里姆算法，T2 中的边构成图的最小生成树。
44、有向图G可拓扑排序的判别条件是不存在环。
45、Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生，该算法弧上的权出现负值情况时，不能正确产生最短路径。
46、有向图G=(V,E),其中 V(G)={0,1,2,3,4,5}，用
47、上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为75。
48、在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为关键路径。
49、当一个AOV 网用邻接表表示时，可按下列方法进行拓扑排序。
(1)查邻接表中入度为0的顶点，并进栈；
(2)若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj 的直接后继Vk，对Vk 入度处理，处理方法
是V k度减1，若V k入度己减到零，则V k顶点入栈；
(3)若栈空时，输出顶点数小于图的顶点数，说明有环，否则拓扑排序完成。
三、判断题
√01、树中的结点和图中的顶点就是指数据结构中的数据元素。
×02、在n 个结点的无向图中，若边数大于n-1,则该图必是连通图。
×03、有e 条边的无向图，在邻接表中有e 个结点。
×04、有向图中顶点V 的度等于其邻接矩阵中第V 行中的1 的个数。
√05、强连通图的各顶点间均可达。
×06、强连通分量是无向图的极大强连通子图。
×07、连通分量指的是有向图中的极大连通子图。
×08、十字链表是无向图的一种存储结构。
√09、无向图的邻接矩阵可用一维数组存储。
×10、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。
√11、有n 个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。
×12、有向图的邻接矩阵是对称的。
×13、无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
×14、邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。
√15、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。
×16、一个有向图的邻接表和逆邻接表中结点的个数可能不等。
×17、广度遍历生成树描述了从起点到各顶点的最短路径。
×18、不同的求最小生成树的方法最后得到的生成树是相同的。
√19、连通图上各边权值均不相同，则该图的最小生成树是唯一的。
√20、在图G 的最小生成树G1 中，可能会有某条边的权值超过未选边的权值。
×21、拓扑排序算法把一个无向图中的顶点排成一个有序序列。
×22、拓扑排序算法仅能适用于有向无环图。
√23、无环有向图才能进行拓扑排序。
×24、有环图也能进行拓扑排序。
×25、拓扑排序的有向图中，最多存在一条环路。
×26、任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。
×27、既使有向无环图的拓扑序列唯一，也不能唯一确定该图。
√28、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。
×29、对一个AOV 网，从源点到终点的路径最长的路径称作关键路径。
√30、关键路径是AOE 网中从源点到终点的最长路径。
×31、在表示某工程的AOE 网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。
×32、在AOE 图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。
√33、在AOE 图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。
×34、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。
四、简答题
01、写出下面有向图的所有强连通分量。
答：3个，分别是：a,bce,dfg
02、已知图的邻接表如下，画出图G的所有连通分量。
答：
03、如下图，分别用普里姆算法和克鲁斯卡尔算法从顶点1开始求最小生成树，写出按次序产生边的序列。说明：边用(i,j)方式表示。
答：普里姆算法产生边的序列：(1,3),(3,4),(4,6),(6,5),(1,2)
克鲁斯卡尔算法产生边的序列：(4,6),(1,3),(4,3),(6,5),(1,2)
04、如下图，写出所有的拓扑序列，并求在添加什么边之后仅可能有惟一的拓扑序列。
答：v1,v2,v3,v4
v1,v3,v2,v4
v2,v1,v3,v4
05、已知如图所示的有向图，请给出该图的:
(1) 每个顶点的入/出度；(2) 邻接矩阵；(3) 邻接表；(4) 逆邻接表。
答：
(1) 每个顶点的入/出度 (2) 邻接矩阵
(3) 邻接表 (4) 逆邻接表
06、写出无向带树图的邻接矩阵，并按普里姆算法填写表格中的内容，最后画出最小生成树；
(1)邻接矩阵为：
lowcost 7 2
Vex lowcost 0 0 0 f
3
0 0 0 {a,c,b,d,h,g,f
}
{e}
Vex lowcost 0 0 0 0 0 0 0 {a,c,b,d,h,g,f
,e}
{ }
07、按克鲁斯卡尔算法写出下面无向带权图求最小生成树产生的边序列。
答：
fg(2)→ac(3)→fe(3)→ab(4)→dh(4)→bd(5)→dg(5)
08、已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
答：
09、利用Dijkstra算法填写表格求图中从顶点a到其他各顶点间的最短路径，并写出最终结果。
a→c：2(a,c)
a→f：6(a,c,f)
a→e：10(a,c,e)
a→d：11(a,c,f,d)
a→g：14(a,c,f,d,g)
a→b：15(a,b)
10、求出下图中从顶点1出发到其余各顶点的最短路径。
答：
11、设图G=(V，E)，V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6>，<6，5>，<5，4>，<6，4>}。画出图G，并写出图G中顶点的所有拓扑序列。
答：
1，2，3，6，5，4
1，3，2，6，5，4
1，3，6，2，5，4
五、代码填空题
01、图的存储结构定义如下：
typedef struct ArcCell
{ VRType adj; /*图中有1/0表示是否有边，网中表示边上的权值*/
/* InfoType *info; 与边相关的信息*/
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{ VertexType vexs[MAX_VERTEX_NUM]; /*顶点向量*/
AdjMatrix arcs; /*邻接矩阵*/
int vexnum,arcnum; /*图中当前顶点数和边数*/
} MGraph;
(1) 请写出下面函数实现的功能：顶点在顶点向量中的定位。
int LocateVex(MGraph G,VertexType v)
{ int i;
for(i=0;i if (strcmp(v,G.vexs[i])==0) break; return i; } (2) 下面函数的功能是在图中查找第1个邻接点，请填空。 int FirstAdjVex(MGraph G,int v) { int j,p=-1; for(j=0;j if (G.arcs[v][j].adj==1) { p=j; break;} return p; } (3) 下面函数的功能是在图中查找下一个邻接点，请填空。 int NextAdjVex(MGraph G,int v,int w) { int j,p=-1; for(j=w+1;j if (G.arcs[v][j].adj==1) { p=j; break;} return p; } 02、已知图的邻接表表示的形式说明如下： #define MaxNum 80 typedef struct node { int adjvex; //邻接点域 struct node *next; //链指针域 } EdgeNode; //边表结点结构描述 typedef struct { char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 } VertexNode; //顶点表结点结构描述 typedef struct { VertexNode adjlist[MaxNum]; //邻接表 int n,e; } AlGraph; //邻接表结构描述 下列算法输出图G的深度优先生成树(或森林)的边，阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。 typedef enum {FALSE,TRUE} Boolean; Boolean visited[MaxNum]; void DFSForest(AlGraph *G) { for(i=0; i for(i=0;i if (!visited[i]) DFSTree(G,i);} void DFSTree(AlGraph *G, int i) { visited[i]=TRUE; p=G->adjlist[i].firstedge; while(p!=NULL) { if (!visited[p->adjves]) { printf(G->adjlist[i].vertex, G->adjlist[p->adjvex].vertex); DSFTree(G, p->adjvex);} p=p->next; } } 六、算法设计题 01、编写编历算法，完成对图的深度优先搜索和广度优先搜索。 答：深度优先搜索：课本P169算法7.4和算法7.5 广度优先搜索：课本P170算法7.6 02、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。 答：Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 { InitALGraph(G); scanf("%d",&v); if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf("%d",&a); if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;m G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) { t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))<0) return ERROR; if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode)); if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p; else { for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; } p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList 03、试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。提示：要删除所有从第i个顶点出发的边，即将邻接矩阵的第i行全部置0。 答：//本题中的图G均为有向无权图。 Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) { G.arcs[i][j].adj=0; G.arcnum--; } return OK; }//Delete_Arc 04、有n个顶点的有向图的邻接表定义如下： #define MaxNum 80 typedef struct ArcNode { int adjvex; //邻接点域 struct ArcNode *nextarc; //链指针域 } ArcNode; //边表结点结构描述 typedef struct VNode { VertexType data; //顶点域 ArcNode *firstedge; //边表头指针 } VNode,AdjList[MaxNum]; //顶点向量结点结构描述 typedef struct { AdjList vertices; //邻接表 int vexnum,arcnum; } AlGraph; //邻接表结构描述 设计算法分别实现以下要求 (1)求出图G中每个顶点的出度； (2)求出图G中出度最大的一个顶点，输出该顶点号及其信息； (3)计算图G中出度为0的顶点数； (4)判断图G中是否存在弧 答：本题答案见实验部分 05、试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点v i到顶点v j的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 答： int visited[MAXSIZE]; //指示顶点是否在当前路径上 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 { if(i==j) return 1; //i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else }//exist_path_DFS 解2：(以上算法似乎有问题：如果不存在路径，则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。) int visited[MAXSIZE]; //指示顶点是否在当前路径上 int level＝1;//递归进行的层数 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 { if(i==j) return 1; //i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--) { level++; k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else if (level==1) return 0; }//exist_path_DFS 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。 习题六树和二叉树6.1 单项选择题 (A) (B) (C) (D) 图8.7 4棵二叉树 1. 如图8.7所示的4棵二叉树，_ _不是完全二叉树。 图8.8 4棵二叉树 2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。 3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__o A. t —> left二NULL B. t —> ltag=1 C. t —> ltag=1 且t —> left=NULL D. 以上都不对 4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说 法_B__ o A.正确 B. 错误 5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 _A__。 A.正确 B. 错误 6. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法 _B_o A.正确 B. 错误 7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为—B__o A. 2h B. 2h-1 C. 2h+1 D. h+1 a 8. 如图8.9所示二叉树的中序遍历序列 B o 图8.9 一棵二叉树 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 9. 已知某二叉树的后序遍历序列是d abec，中序遍历序 列是debac，它的前序遍历 序列是D ___ 。 A. acbed B. decab C. deabc D. cedba 10. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 11?假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结 点数为个。B A. 15 B. 16 C. 17 D. 47 12. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是D _____ 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 小于其右孩子的值。这种说法__B__ o A.正确 B. 错误 14. 按照二叉树的定义，具有3个结点的二叉树有_。__种。 A. 3 B. 4 C. 5 D. 6 15. 一棵二叉树如图8.10所示，其中序遍历的序列为 第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 解： int InsList(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf("表已满无法插入！")； return(ERROR); } while(i<=L->last&&L->elem[i] } } 2.6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。 解： int Delete(Linklist,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink>=maxk||L->next->data>=maxk||mink+1=maxk) { printf("参数不合法！"); return ERROR; } else { while(p->next->data<=mink) p=p->next; q=p->next; while(q->data P175: 5. 设有关系模式R(A,B,C,D)，函数依赖F={A→C, C→A, B→AC, D→AC，BD→A } 1)求R的所有候选键。 2)求出F的最小函数依赖集Fmin。 3)根据函数依赖关系，确定关系模式R属于第几范式。 4)将R分解为3NF，并保持无损连接性和函数依赖性。 答：1）属性分类为: L类:B,D ; LR类:A,C; R类:无; N类:无 因为（BD）+=ABCD ,所以BD是唯一候选键. 2） ●函数依赖F={A→C, C→A, B→AC, D→AC, BD→A }右部分解为单属性为 F={A→C, C→A, B→A, B→C, D→A, D→C, BD→A } ●因为B+=ABC,所欲BD→A，D为左部多余的属性.将D去掉，则 F={A→C, C→A, B→A, B→C, D→A, D→C } ●冗余函数依赖: 因为B+=ABC,所以B→A多余,去掉. 因为D+=ACD,所以D→A多余,去掉. 所以Fmin={A→C, C→A, B→C, D→C } 4)根据算法4.6，以及Fmin，F中没有X→Y，XY=R的函数依赖，也没有属性在F的函数依赖中左右都无关。所以将Fmin中的各个函数依赖单独构成一个关系模式， 对于Fmin中每一个函数依赖： A→C：表中数据不改变； C→A：将A中所有b给为a1； 表中没有都是a的行，所以不是无损连接的。 因此根据算法 4.7，将候选键作为一个关系模式加入到ρ中，所以结果为ρ={AC,BC,DC，BD} 6.设有关系模式R(A,B,C,D)，函数依赖F={A→C, C→A, B→AC, D→AC } 1)求（AD）+，B+。 2)求出R 的所有候选键。 3)求出F的最小函数依赖集Fmin。 4)根据函数依赖关系，确定关系模式R属于第几范式。 5)将R分解为3NF，并保持无损连接性和函数依赖性 6)略 答： 第二章习题 一判断题 1．线性表的逻辑顺序与存储顺序总是一致的。× 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。× 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。× 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。×9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。× 11.线性表中每个元素都有一个直接前驱和一个直接后继。（×） 12.线性表中所有元素的排列顺序必须由小到大或由小到小。（×） 13.静态链表的存储空间在可以改变大小。（×） 14.静态链表既有顺序存储结构的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 15.静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加。（） 16.静态链表与动态链表的插入、删除操作类似，不需要做元素的移动。（） 17.线性表的顺序存储结构优于链式结构。（×） 18.在循环单链表中，从表中任一结点出发都可以通过前后的移动操作扫描整个循环链表。（×） 19.在单链表中，可以从头结点开始查找任何一个结点。（） 20.在双链表中，可以从任何一结点开始沿同一方向查找到任何其他结点。（×） 二单选题 (请从下列A，B，C，D选项中选择一项) 1．线性表是( ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 ，在任何位置上插入或删除操作都是等概率的。插n．对顺序存储的线性表，设其长度为2． 入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) （n -1）/2 (D) n 数据结构试题? 一、?单选题（每题 2 分，共20分） 1.1.???? 对一个算法的评价，不包括如下（ B ）方面的内容。 A．健壮性和可读性B．并行性 C．正确性 D．时空复杂度 2.2.???? 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点， 则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.3.???? 对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种（ D ）。 A．有向图 B．无向图 C．无向无环图D．有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同 D．高于二分查找 7.7.???? 若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。 A．值 B．函数 C．指针 D．引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有 相同的（ A ）。 A．行号B．列号 C．元素值 D．非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O(n) D．O(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M： N）的联系时，称这种结构为图（或图结构）。 2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 单元练习1 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（ㄨ）（3）数据元素是数据的最小单位。 （ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。 （ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（7）数据的存储结构是数据的逻辑结构的存储映像。 （√）（8）数据的物理结构是指数据在计算机内实际的存储形式。 （ㄨ）（9）数据的逻辑结构是依赖于计算机的。 （√）（10）算法是对解题方法和步骤的描述。 二．填空题 （1）数据有逻辑结构和存储结构两种结构。 （2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 （4）树形结构和图形结构合称为非线性结构。 （5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。 （6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。 （7）数据的存储结构又叫物理结构。 （8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。（9）线性结构中的元素之间存在一对一的关系。 （10）树形结构结构中的元素之间存在一对多的关系， （11）图形结构的元素之间存在多对多的关系。 （12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。 （13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。 （14）算法是一个有穷指令的集合。 （15）算法效率的度量可以分为事先估算法和事后统计法。 （16）一个算法的时间复杂性是算法输入规模的函数。 （17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n 的函数。 （18）若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为 O （nlog2n）。 （19）若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 O 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 数据结构课程作业_A 交卷时间：2017-08-09 10:08:51 一、单选题 1. (7分)设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点：第五章 展开解析 答案 C 解析第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点：第九章 展开解析 答案 D 解析第九章第一节有序表的查找 (7分)设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点：第七章 展开解析 答案 A 解析第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点：第六章 展开解析 答案 A 解析第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 得分： 7 知识点：第三章 展开解析 答案 A 解析第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点：第九章 展开解析 答案 B 解析第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点：第六章 展开解析 答案 C 解析第六章第六节二叉树的性质 数据结构（本科）试卷7 一、选择题（每小题1分，共10分） 1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 2.带头结点的单链表first为空的判定条件是： A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL; 3.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为 对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（），在被调用程序中可直接操纵实际参数。 A. 空间 B. 副本 C. 返回地址 D. 地址 5.在一棵树中，（）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点 6.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A. 2 B. 1 C. 0 D. –1 7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长 度为（）的值除以9。 A. 20 B. 18 C. 25 D. 22 8.在有向图中每个顶点的度等于该顶点的（）。 A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差 9.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于 O(nlog2n)。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序 10.当α的值较小时，散列存储通常比其他存储方式具有（）的查找速度。 A. 较慢 B.较快 C. 相同 二、填空题（每小题1分，共10分） 1.二维数组是一种非线性结构，其中的每一个数组元素最多有____2___个直接前驱（或直 接后继）。 2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中， A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_ 数据结构习题 第一章绪论 1.6 在程序设计中，常用下列三种不同的出错处理方式： 1) 用exit语句终止执行并报告错误； 2) 以函数的返回值区别正确返回或错误返回； 3) 设置一个整形变量的函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自的优缺点。 1.7 在程序设计中，可采用下列三种方法实现输出和输入： 1) 通过scanf和printf语句； 2) 通过函数的参数显示传递； 3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： 5) for (i = 1; i <= n; i++ ) { for (j = 1; j <= i; j++) { for (k = 1; k <= j; k++) { @ x += delta; } } } 答案：n*(n+1)*(n+2) =1+（1+2）+（1+2+3）+...+(1+2+3+...+n) =∑ =+ n i i i 1 2 / )1 ( * =1/2*∑ =+ n i i i i 1 * =n*(n+1)*(2n+1)/12 +n*(n+1)/4 =n*(n+1)*(n+2)/6 7) x = n; //n是不小于1的常数 y = 0; while (x >= (y + 1) * (y + 1)) { @ y++; } 答案：n向下取整 8) x = 91; y = 100; while (y > 0) { @ if (x > 100) { x -= 10; y--;} else { x++; } } 答案：if 执行次数为1100， if 判断内部执行为100次 1.19 试编写算法，计算i!·2i （i = 0, 1, …, n-1）的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT ，则当n > arrsize 或对某个k （0 ≤ k ≤ n-1）使k!·2k > MAXINT 时，应按出错处理。注意选择你认为较好的出错处理方法。 1.20 试编写算法求一元多项式∑==n i i i x a x 0n )(P 的值P n (x 0)，并确定算法中每一语句的执行 次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为a i （i=0, 1, …, n ）、x 0和n ，输出为P n (x 0)。 1. 下面程序段的执行次数为（ A ） for(i=0;i＜n-1;i++) for(j=n;j＞i;j--) state; A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2) 2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （ B ）A. 110 B .108 C. 100 D. 120 3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）A. edcba B .decba C. dceab D. abcde 4. 循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前 队列中的元素个数是（ D ） A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front 5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head D. head!=NULL 6．在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行（ B） A. s-next=p;p-next=s; B .s-next=p-next;p-next=s; C. s-next=p-next;p=s; D. p-next=s;s-next=p; 7. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均 比较多少个结点（ D ）A. n B .n2 C. (n-1)2 D. (n+1)28．从一个栈顶指针为HS 的链栈中删除一个结点时，用x保存被删结点的值，则执行( D )A. x=HS;HS=HS-next;B .x=HS-data;C. HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表，其特殊性体现在( B ) A. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字 符11．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的 范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存 储时下列哪一元素的起始地址相同( B ) A. M[2][4] B .M[3][4] C. M[3][5] D. M[4][4] 12. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10， 从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为 ( C )A. SA+144 B .SA+180 C. SA+222 D. SA+225 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 第二章习题 1. 描述以下三个概念的区别：头指针，头结点，首元素结点。 2. 填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4. 设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5. 写一算法，从顺序表中删除自第i个元素开始的k个元素。 6. 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7. 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8. 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 一、单项选择题 1.逻辑关系是指数据元素间的（） A．类型 B．存储方式 C．结构 D．数据项 2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构 为( ) A．顺序表 B.用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear 为队尾指针，则执行出队操作后其头指针front值为（） A．front=front+1 B．front= (front+1)%(m-1) C．front=(front-1)%m D．front=(fro nt+1)%m 4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别 为队头指针和队尾指针，则判断队满的条件为( )。 A．rear％n==front B．(front+l)％n==rear C．rear％n-1==front D．(rear+l)％n==front 5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别 为队头指针和队尾指针，则判断队空的条件为( )。 A．rear％n==front B．front+l=rear C．rear==front D．(rear+l)％n=front 6.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。 ( ) A. 90 B. 91 C. 92 D. 93 7.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的所有结点 D. 只有左子树上的部分结点 8.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。 A. n B. 2n C. n/2 D. n*n 9.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利 用（）。 A. 求关键路径的方法 B.求最短路径的方法 C. 深度优先遍历算法 D.广度优先遍历算法 10.对线性表进行二分查找时，要求线性表必须( )。 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 （一） （二） （三） （四） （五） （六） （七 ）（八 ） （九 ） （十 ） 9 12 15 17 19 21 24 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 （一） （二） （三 ） （四 ） （五 ） （六） （七） （八） （九） （十 ） 27 28 29 31 33 35 37 38 39 40 数据结构试卷(一) 、单选题(每题 栈和队列的共同特点是(A ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 用链接方式存储的队列，在进行插入运算时 (C ). 头、尾指针都要修改 头、尾指针可能都要修改 (D ) 线性表 2分，共20分) 1. 2. A. C. 3. A. 4. 仅修改头指针 B. 仅修改尾指针 D. 以下数据结构中哪一个是非线性结构? 队列 B.栈 C. 设有一个二维数组 A[m][ n]，假设 个空间，问 676(10)，每个元素占 制表示。 .688 D. 二叉树 A[2][2]存放位置在 (10)存放在什么位置？脚注(10)表示用10进 A[0][0] 存放位置在644(10), A[3][3] .678 C C ） 。 B. A 5.树最适合用来表示( A.有序数据元素 C.元素之间具有分支层次关系的数据 二叉树的第k 层的结点数最多为(D ). k .2 -1 B.2K+1 C.2K-1 若有18个元素的有序表存放在一维数组 6. A 7. 692 D . 696 D. 无序数据元素 乙间无联系的数 据 元素之 f k-1 D. 2 A[19]中，第一个元素放 A[1]中，现进行二 分查找，则查找 A : 3 ]的比较序列的下标依次为 (C ) A. 1 , 2, 3 B. 9 , 5, 2, 3 C. 9 , 5, 3 D. 9 , 4, 2, 3 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 D. O 8. A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，若选用 H (K ) =K %9作为散列函数，则散列地址为 1的元素有(D )个， A . 1 B . 2 C . 3 10. 设有6个结点的无向图，该图至少应有 ( A.5 B.6 C.7 D.8 二、填空题(每空 1分，共26分) 1.通常从四个方面评价算法的质量： _ 高效率 _______ 和―强壮性 _______ 。 1. 一个算法的时间复杂度为(n 3 +nlog 2n+14n)/ n 2 ,其数量级表示为 —o(n) ____________________ 。 2. 假定一棵树的广义表表示为 A (C, D (E , F , G , H( I , J )),则树中所含的结点数为 __________ 个，树的深度为 ____________ ，树的度为 ___________ 。 .4 条边才能确保是一个连通图。 正确性 易读性数据结构试题及答案(免费)
数据结构书面作业练习题
数据结构课后习题答案
数据结构第二章课后习题题解
数据结构DB课后题部分答案
数据结构第2章基础习题 作业
数据结构试题及答案
(完整版)数据结构课后习题及解析第二章
《数据结构》课后参考答案
数据结构习题与答案
数据结构试题(含答案)
数据结构课程作业
数据结构试题(附有答案)
数据结构作业
武汉大学数据结构考试题(附答案)
数据结构试题及答案
数据结构课后习题及解析第二章
数据结构练习附答案
十套数据结构试题与答案
相关主题
文本预览