A．图中有奇数个顶点 B、图中有偶数个顶点 C、图为无向图 D、图为有向图
19．在一个无向图中，所有顶点的度数之和等于所有边数的（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）。 A．1/2 B。2 C。1 D。4
20．若邻接表中的有奇数个表结点，则一定（ D ） A．图中有奇数个顶点 B。图中有偶数个顶点 C。图为无向图 D。图为有向图 21．下面关于AOE网的叙述中，不正确的是（ B ） A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某个关键活动提前完成，那么整个工程将会提前完成
二、填空题
1、29条边的无向连通图，至少有（ 9 ）个顶点，至多有（ 30 ）个顶点，有29条边的无向非连通图，至少有（ 10 ）个顶点。
2、n个顶点的强连通有向图G，最多有（n(n-1) ） 条边，最少有(n)边。
强连通图即是任何两个顶点之间有路径相通，当所有结点在一个环上时，必定是强连通图。
3、29条边的有向连通图，至少有（6 ）个顶点，至多有（29 ）个顶点，有29条边的有向非连通图，至少有（ 7 ）个顶点。
4、已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是（将矩阵第i行全部置为0）
1. 图有 邻接矩阵 、 邻接表 等存储结构，遍历图有 深度优先遍历 、 广度优先遍历 等方法。
2. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。
3. 如果n个顶点的图是一个环，则它有 n 棵生成树。 （以任意一顶点为起点，得到n-1条边）
4. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n2) 。
5. n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 O(n+e) 。
6. 设有一稀疏图G，则G采用 邻接表 存储较省空间。
7. 设有一稠密图G，则G采用 邻接矩阵 存储较省空间。
8. 图的逆邻接表存储结构只适用于 有向 图。
9. 已知一个有向图的邻接矩阵表示，删除所有从第i个顶点出发的方法是 将邻接矩阵的第i行全部置0 。 10. 图的深度优先遍历序列 不是 惟一的。
11. n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 O(n2) ；若采用
邻接表存储时，该算法的时间复杂度为 O(n+e) 。
12. n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接表存储，该算法的时间复杂度为 O(n+e) 。
41
13. 若要求一个稀疏图G的最小生成树，最好用 克鲁斯卡尔(Kruskal) 算法来求解。
14. 若要求一个稠密图G的最小生成树，最好用 普里姆(Prim) 算法来求解。
15. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。
16. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。
三、简答题（每题6分，共24分）
1.请对下图的无向带权图：
（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。
解：设起点为a。
?043?????? ??40559 ??3550550????? 最小生成树→ 7?6?554? ? ???9?703??? ????????6302?? ???554???2066?
0??PRIM算法是将顶点归并：
设初始顶点为a, 依次归并的
顶点集为：{a},{a,c},{a,c,b},{a,c,b,d},{a,c,b,d,h},
{a,c,b,d,h,g},{a,c,b,d,h,g,f}, {a,c,b,d,h,g,f,e}。所得最小生成树如上。 邻接表为： a 1 4 2 3 ^ b 0 4 2 5 3 5 4 9 ^ c 0 3 1 5 3 5 7 5 ^ d 1 5 2 5 4 7 5 6 6 5 7 4 ^ e 1 9 3 7 5 3 ^ f 3 6 4 3 6 2 ^ g 3 5 5 2 7 6 ^ h 3 4 2 5 6 6 ^ 克鲁斯卡尔算法是将连归并：依次归并的边集为：
{(f,g)}
{(f,g）,(e,f)},
42
{ (f,g）,(e,f) ,(a,c)},
{ (f,g）,(e,f) ,(a,c) ,(a,b)},
{ (f,g）,(e,f) ,(a,c) ,(a,b) ,(d,h)},
{ (f,g）,(e,f) ,(a,c) ,(a,b) ,(d,h), (d,g)},
{ (f,g）,(e,f) ,(a,c) ,(a,b) ,(d,h), (d,g)，(b,d)},
{ (f,g）,(e,f) ,(a,c) ,(a,b) ,(d,h), (d,g)，(b,d), }, 所有的顶点同在一个连通分量上。 所得最小生成树如下。
第一章 绪论
1．下面是几种数据的逻辑结构S=(D，R)，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构。
D={a，b，c，d，e，f} R={r}
(a) r={
(b) r={ for(j=0；j for(i=0；i for(j=0；j While(i 3．在数据结构中，与所使用的计算机无关的是 。 A．存储结构 B．物理结构 C．物理和存储结构 D．逻辑结构 4．非线性结构中每个结点 。 A．无直接前驱结点 B．只有一个直接前驱和直接后继结点 C．无直接后继结点 D．可能有多个直接前驱和多个直接后继结点 5．可以把数据的逻辑结构划分成 。 A．内部结构和外部结构 B．动态结构和静态结构 C．紧凑结构和非紧凑结构 D．线性结构和非线性结构 第二章 线性表 一、单项选择题 1．下面关于线性表叙述中，错误的 是_(1)_。 (1)：A．顺序表必须占用一片地址连续的存储单元 43 B．链表不必占用一片地址连续的存储单元 C．顺序表可以随机存取任一元素 D．链表可以随机存取任一元素 2．在表长为n的单链表中，算法时间复杂度为O(n)的操作是 (2)。 (2)：A．查找单链表中第i个结点 B．在p结点之后插入一个结点 C．删除表中第一个结点 D．删除p结点的直接后继结点 3．单链表的存储密度 (3) 。 (3)：A．大于1 B．等于1 C．小于1 D．不能确定 4．在表长为n的顺序表中，算法的时间复杂度为O(1)的操作是 (4) 。 (4)：A．在第n个结点之后插入一个结点 B．在第i个结点前插入一个新结点 C．删除第i个结点 D．求表长 5．在下列链表中不能从当前结点出发访问到其余各结点的是（5）。 (5)：A．单链表 B．单循环链表 C．双向链表 D．双向循环链表 6．在设头、尾指针的单链表中，与长度n有关的操作是（6）。 (6)：A．删除第一个结点 B．删除最后一个结点 C.在第一个结点之前插入一个结点 D.在表尾结点后插入一个结点 7.设p结点是带表头结点的双循环链表中的结点，则 (1)在p结点后插入s结点的语句序列中正确的是 （7）。 （7）：A.s->next=p->next；p->next->prior=s； p->next=s；s->next=p->next； B.p—>next=s；S—>next=p—>next； p—>next—>prior=s；s—>next=p； C.p->next=s；p—>next—>prior=s； s->next=p—>next；S—>next=p； D.p->next->prior=s；p->next=s； s->next=p->next；s->next=p； (2)在p结点之前插入s结点的语句序列中正确的是(8)。 (8)：A.s->prior=p->prior；p->prior->next p->prior=s；s->next=p； B.p->prior=s；p->prior->next=s; s->prior=p->prior；s->next=p; C.p->prior->next=s；p->prior=s; s->prior=p->prior；s->next=p; D.p->prior=s；s->next=p； p->prior->next=s；s->prior=p->prior; 8．下列关于链表说法错误的是 (9) 。 (9)：A.静态链表中存取每一个元素的时间相同 B．动态链表中存取每一个元素的时间不同 C．静态链表上插入或删除一个元素不必移动其他元素 D．动态链表上插入或删除一个元素不必移动其他元素 9．在链表中最常用的操作是在最后一个数据元素之后插入一个数据元素和删除第一个数据元素，则最节省运算时间的存储方式是 (10) 。 (10)：A.仅有头指针的单链表 B．仅有头指针的单循环链表 C．仅有头指针的双向链表 D．仅有尾指针的单循环链表 二、填空题 1．单链表中每个结点需要两个域，一个是数据域，另一个是 (1) 。 2．链表相对于顺序表的优点是 (2) 和 (3) 操作方便。 3．表长为n的顺序表中，若在第j个数据元素(1≤i≤n+1)之前插入一个数据元素，需要向后移动 (4) 个数据元素；删除第j个数据元素需要向前移动 (5) 个数据元素；在等概率的情况下， 44