数据结构（Java语言版）模拟试卷3（含参考答案）x.pdfVIP

数据结构试卷（三）

一、选择题(每题2分，共20分)

1.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，

09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，

03，08，03，09}，则数据结构A是(B)。

A.线性结构

B.树形结构

C.物理结构

D.图形结构

2.下面程序的时间复杂度为(B)。

1i=1

2s=0

3whilei=n:

4i+=1

5t=1

6forjinrange(1,i):

7t=t*j

8s=s+t

A.O(n)

2

B.O(n)

3

C.O(n)

4

D.O(n)

3.设指针变量p指向单链表中的结点A，若删除单链表中的结点A，则需要修改指针的操

作序列为(A)。

A.q=p.next；p.data=q.data；p.next=q.next；

B.q=p.next；q.data=p.data；p.next=q.next；

C.q=p.next；p.next=q.next；

D.q=p.next；p.data=q.data；

4.设有n个待排序的记录关键字，在堆排序中需要(A)个辅助记录单元。

A.1

B.n

C.nlogn

2

D.n2

5.设一组记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快

速排序结束后的结果为(A)。

A.10，15，14，18，20，36，40，21

B.10，15，14，18，20，40，36，21

C.10，15，14，20，18，40，36，21

D.15，10，14，18，20，36，40，21

6.设二叉排序树中有n个结点，则二叉排序树的平均查找长度为(B)。

A.O(1)

B.O(logn)

2

C.O（n）

2

D.O(n)

7.设无向图G中有n个顶点、e条边，则其对应的邻接表中的表头结点和表结点的个数分

别为(D)。

A.n、e

B.e、n

C.2n、e

D.n、2e

8.设某强连通图中有n个顶点，则该强连通图中至少有(C)条边。

A.n(n-1)

B.n+1

C.n

D.n(n+1)

9.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关

键字，则用下列(B)方法可以达到此目的。

A.快速排序

B.堆排序

C.归并排序

D.插入排序

10.下列4种排序中(D)的空间复杂度最大。

A.插入排序

B.冒泡排序

C.堆排序

D.归并排序

二、填空题(每空1分，共20分)

1.数据的物理结构主要包括顺序存储结构和链式存储结构两种情况。

2.设一棵完全二叉树中有500个结点，则该二叉树的深度为____9_____；若用二叉链表作

为该完全二叉树的存储结构，则共有_____501____个空指针域。

3.设输入序列为（1，2，3），则经过栈的作用后可以得到___5______种不同的输出序列。

4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上的所有元素之和

等于顶点i的_____出度____，第i列上的所有元素之和等于顶点i的___入度______。

5.设哈夫曼树中共有n个结点，则该哈夫曼树中有____0_____个度数为1的结点。

6.设有向图G中有n个顶点、e条有向边，所有的顶点入度数之和为d，e和d的关系为

____e=d_____。

7.____中序_____遍历二叉排序树中