数据结构试题库

A

B

C D

E F G

H I

J

(2) 写出前序、中序、后序遍历次序。 (2)前序遍历：ABCEDFHGIJ

中序遍历：ECBHFDJIGA 后序遍历：ECHFJIGDBA (3) 画出后序线索二叉树。 后序线索化树见下图：

A NIL

B

C D

NIL E F G

H I

J

7、已知一棵二叉树先序遍历结果为ABCDEFGHIJ，中序遍历的结果为CBEDAHGIJF，试画出该二叉树

解答：由前序遍历结果可知该二叉树的根结点为Ａ。由此及中序遍历结果可知，该二叉树在中序遍历下的左、右子树为

CBED和HGIJF

依此可推出前序遍历的左、右子树的结点序列为 BCDE和FGHIJ

B和F又分别为左、右子树的根结点，进而又可推出以B为根结点的左、右子树，以及 以F为根结点的左、右子树。依此类推，可推出二叉树见下图。 A

B F

C D G

- 37 -

E H I

J

8、设a是含有n个元素的整数数组,写出一个求n个元素的平均值的递归定义。 解答：#include #define AVE(A,B) aver(A,B,0)

double aver(float *a,int n,int t) {

if (t!=n) return (a[t]/n+aver(a,n,t+1)); else return 0; }

int main(void) {

float a[]={1,5,9,13,17}; printf(\ return 0; }

9、设a是含有n个元素的整数数组:

(1) 写出求该数组中最大元素的递归定义。 int A :: Max (int n) //递归求最大值 {

if (n==1) return E[0]; int t=Max ( n-1 );

if (E[n-1]>t) return E[n-1]; else return t; }

(2) 写出求该数组中最小元素的递归定义。 int A :: Min (int n) //递归求最小值 {

if (n==1) return E[0]; int t=Min ( n-1 );

if (E[n-1]>t) return E[n-1]; else return t; }

10、设a是含有n个元素的整数数组: (1) 写出求n个整数之和的递归定义。 int A :: Sum (int n) //递归求数组之和 {

if (n==1) return E[0];

else return E[n-1]+Sum (n-1); }

- 38 -

(2) 写出求n个整数之积的递归定义。 int A :: Multi (int n) //递归求整数之积 {

if (n==1) return E[0];

else return E[n-1]*Multi (n-1); }

11、二维数组A[4][4](即A[0..3][0..3])的元素起始地址是loc(A[0][0])=1000,元素的长度为2,则LOC(A[2][2])的地址为多少?

答：LOC(A[2][2])= loc(A[0][0])+（2*4+2)*2=1000+20=1020

7 图

沈阳理工大学应用技术学院

信息与控制学院 计算机科学与技术教研室

2011-5-8

数据结构复习题：图 单选题

1、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的___1__倍。

2、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为___n__。 3、具有n个顶点的无向完全图，边的总数为_____条。

4、在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于_____ 。

- 39 -

5、在n个结点的线索二叉树中,线索的数目为___n+1___. 6、在二叉排序中,凡是新插入的结点,都是没有______的. 7、深度为5的二叉树至多有_______个结点. 8、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为_____s____。 9、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为_________。 10、在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为_____2e____。 11、在一个具有n个顶点的无向完全图中，所含的边数的_________。 12、在一个具有n个顶点的有向完全图中，所含的边数为_________。

13、在一个无权图中，若两顶点之间的路径长度为k，则该路径上的顶点数为____k+1_____。 14、对于一个具有n个顶点的无向连通图，它留念的连通分量的个数为____1_____。 15、若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用____1_____次深度优先于搜索遍历的算法。

16、在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为_________。 17、在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为_________。

18、在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为_________

19、在一个无权图的邻接表表示中，每个边结点至少包含____2_____域。

20、对于一个有向图，若一个顶点的度为k1,出度为k2,则对应邻接表中该顶点单链表中的边结点数为_________

21、对于一个有向图，若一个顶点的度为k1,出度为k2,则对应邻接表中该顶点单链表中的边结点数为_________。

22、对于一个无向图，下面_________说法是正确的。

23、在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的_________。

24、若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为_________。

25、若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为_________。

26、若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为_____1,2,4,5,3____。

29、在n个顶点的有向无环无权图的邻接矩阵中至少有____n(n+1)2_____个零元素。

数据结构判断题：图

1、有回路的图不能进行拓扑排序。

数据结构判断题答案：图 1、True

数据结构算法题：图

1、设计一个将邻接表转换为邻接矩阵的算法.

数据结构算法题答案：图

1、 void ListToMat(ALGraph *G,MGraph &g)

- 40 -