数据结构导论真题分类整理详细

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,如果图中存在弧,则A[i][j]的值为____。

题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中若有孤,则在图G的拓扑序列中,顶点Vi,Vj和Vk的相对位置为_________。

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

联系客服:779662525#qq.com(#替换为@)