35.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数 6．除根结点外，树上每个结点（ ）
A．可有任意多个孩子、任意多个双亲 B．可有任意多个孩子、一个双亲 C．可有一个孩子、任意多个双亲 D．只有一个孩子、一个双亲
7．具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（ ）个指针域为空。
A．50 B．99 C．100 D．101
20．设有k个结点，在用哈夫曼算法构造哈夫曼树的过程中，若第i次合并时已找到权最小的结点x和权次小的结点y，用T［x］.wt表示结点x的权值，已知T［x］.wt=m, T［y］.wt=n，则合并成新的二叉树后给新根结点的权值赋值的语句为__________。 21．在下列树中，结点H的祖先为__________。
30．分别写出下列二叉树的先根、中根、后根遍历序列。（6分）
17
第五章 图 真题
4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1
25.含有n个顶点和n-1条边的连通图G采用____________存储结构较省空间。 26.在图中，第一个顶点和最后一个顶点相同的路径称为____________。 32.下述题32图矩阵表示一个无向网，画出该无向网，并构造出其最小生成树。
3.由顶点V1，V2，V3构成的图的邻接矩阵为，则该图中顶点V1的出度为（ ）
A.0 B.1 C.2 D.3
14.设无向图的邻接表如题14图所示，则该图的边数为（ ）
题14图
A.4 B.5 C.10 D.20
25.在一个具有n个顶点的无向图中，顶点的度最大可达_____。
26.有向图G的邻接矩阵为A，如果图中存在弧
题32图
32.写出题32图所示的有向图的邻接矩阵及该图的所有拓扑排序序列。
11.有n个结点的无向图的边数最多为（ ）
A.n+1 B.n(n-1)/2 C.n(n+1) D.2n(n+1)
12.设图的邻接矩阵为，则该图为（ ）
A.有向图 B.无向图 C.强连通图 D.完全图
18
23.设有一稠密图G，则G采用__存储结构较省空间。设有一稀疏图G，则G采用__存储结构较省空间。
31.已知某图的邻接表存储结构如题31图所示： (1)画出该图。
(2)根据该邻接表从顶点A出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。
10.一个具有n个顶点的无向连通图，它所包含的连通分量数为（ ） A.0 B.1 C.n D.不确定 11.下列说法中不正确的是（ ）
A.无向图的极大连通子图称为连通分量
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D.有向图的遍历不可采用广度优先搜索算法
23.在无向图G的邻接矩阵A中，若A[i][j]等于0，则A[j][i]等于________。
27.对含有n个结点e条边的无向连通图，利用prim算法生成最小生成树的时间复杂度为________。 31.对于题31图，试给出： 1）邻接矩阵； 2）邻接表。
10.邻接矩阵为对称矩阵的图是( ) A.有向图 B.带权有向图 C.有向图或无向图 D.无向图 11.在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为( ) A.n-1 B.n C.n+1 D.n/2 22.一个具有4个顶点的无向完全图有_________条边。
23.一个有向图G中若有孤
33.已知无向图G的邻接表如题33图所示，请画出该无向图，并写出其按广度优先搜索时的访问序列。其中nil表示空。
19
10.有4个顶点的无向完全图的边数为( ) A.6 B.12 C.16 D.20
11.设图的邻接矩阵为，则该图为( ) A.有向图 B.无向图 C.强连通图 D.完全图
22.具有n个顶点的连通图至少需有__________条边。
23.在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于__________。
32.已知无向图G的邻接矩阵如题32图所示。请画出该无向图，并写出按深度优先搜索时的访问序列。
12．在一个具有n个顶点的无向图中，每个顶点度的最大值为（ ）A．n B.n-1 C.n+1 D.2(n-1) 13．关于无向图的邻接矩阵的说法中正确的是（ ） A．矩阵中非全零元素的行数等于图中的顶点数
B.第i行上与第i列上非零元素总和等于顶点Vi的度数 C.矩阵中的非零元素个数等于图的边数 D.第i行上非零元素个数和第i列上非零元素个数一定相等
23．第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶点外，其余顶点都不重复的回路，称为_______。
24．一个具有10个顶点的完全无向图中有_______条边。 33．已知连通网的邻接矩阵A如33题图 ， 试画出它所表示的连通网并画出该连通网的最小生成树。
11.有n个结点的有向完全图的弧数是（ ） A.n2 B.2n C.n(n-1) D.2n(n+1)
20