数据结构期末试卷

一、单选题（40分）

1.【单选题】（2分）

树的路径长度是从树根到每个结点的路径长度的（）。

A.平均值

OB.总和

C.最大值

D.最小值

2.【单选题】（2分）

某二叉树的先序序列和后续序列正好相反，则该二叉树一定是（）。

A.任一结点无右孩子

OB.空或只有一个结点

C.高度等于其结点数

D.任一结点无左孩子

3.【单选题】（2分）

若一棵完全二叉树的先序遍历序列为ABDHGECF,则以下说法错误的是（）。

A.结点C的深度为3

B.结点C是叶结点

C.结点C的高度为1

OD.结点C是A的右孩子结点

4.【单选题】（2分）

关于图的存储结构，（）是错误的。

A.若一个有向图的邻接矩阵的对角线以下的元素为0,则该图的拓扑序列必定存在；

OB.邻接表只用于有向图的存储，邻接矩阵适用于有向图和无向图；

C.使用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点数

有关，与边数无关；

D.存储无向图的邻接矩阵是对称的，故只需存储邻接矩阵的下三角部分

5.【单选题】（2分）

假设利用一个数组s□顺序存储一个栈，用top作为栈顶指针，top=-1表示栈空，当栈未满时，元素x进栈的

操作是（）。

A.s[++top]=x;

B.s[top--]=x;

C.s[--top]=x;

0D.s[top++]=x;

6.【单选题】（2分）

下列排序方法中，哪一个是稳定的排序方法？（）

OA.二分法插入排序

B.直接选择排序

C.希尔排序

D.快速排序

7.【单选题】（2分）

设散列表长m=14,散列函数为h（key）=keymod11,表中仅有4个结点h（15）=4,

h（38）=5,h（61）=6,h（84）=7,若采用线性探测法处理冲突，则关键字49的结点地址为（）。

OA.8

B.9

C.3

D.5

8.【单选题】（2分）

栈和队列具有相同的（）。

A.运算

OB.存储结构

C.抽象数据类型

D.逻辑结构

9.【单选题】（2分）

带头结点的双向循环链表L为空的判断条件是（）.

A.L->prior==NULL&8iL-next==L

B.L->prior==L&&L->next==NULL

C.L->prior=NULL&&L-next==NULL

OD.L->prior==L&&L->next==L

10.【单选题】（2分）

线性表的顺序存储结构是一种（）。

OA.顺序存取的存储结构

B.随机存取的存储结构

C.索引存取的存储结构

D.散列存取的存储结构

11.【单选题】（2分）

折半查找与二叉排序树的时间性能（）。

A.相同

B.数量级都是。（n）

OC.有时不同

D.完全不同

12.【单选题】（2分）

用直接插入排序方法对下面四个序列进行排序（从小到大），元素比较次数最少的是（）。

A.90,75,80,55,20,35,100,40

OB.20,35,55,40,75,80,90,100

C.35,40,20,55,70,100,90,80

D.100,35,40,90,80,55,20,75

13.【单选题】（2分）

在有n个叶结点的哈夫曼树中，非叶结点的总数是（）。

A.2n

OB.2n-1

C.n-1

D.n

14.【单选题】（2分）

以下说法正确的是（）

A.一个图的邻接矩阵表示不唯一,邻接表表示不唯一

B.一个图的邻接矩阵表示唯一，邻接表表示唯一

OC.一个图的邻接矩阵表示唯一，邻接表表示不唯一

D.一个图的邻接矩阵表示不唯一，邻接表表示唯一

15.【单选题】（2分）

在一棵二叉排序树上，查找关键字为35的结点，依次比较的关键字可能有（）。

A.46,28,18,36,35

OB.46,36,18,28,35

C.18,36,28,46,35

D.28,36,18,46,35

16.【单选题】（2分）

分别用下列序列构造二叉排序树，与用其他3个序列所构造的结果不同的是（）。

A.{100,120,110,130,80,60,90）

B.{100,80,60,90,120,130,110）

C.{100,80,90,60,120,110,130）

OD.{100,60,80,90,120,110,130）

17.【单选题】（2分）

对序列{15,9,7,8,20,-1,4}进行排序,进行一趟后数据的排列变为{4,9,-1,8.20,7,15）;则

采用的是（）排序。

OA.希尔

B.快速

C.冒泡

D.选择

18.【单壁】（2分）

设一组初始记录关键词为{55,63,50,38,75,80f30,60）,利用筛选法建立的初始〃隈堆为（）。

A.30,38,50,55,60,63,75,80

B.30,55,63,50,38,75,80,60

C.30,38,55,63,75,80,50,60

D.30,38,50,60,75,80,55,63

19.【单选题】(2分)

下面的程序段中，对x的赋值语句的频度为()。

for(k=1;k<=n;k++)

for(j=1;j<=n;j++)

x=x+1;

A.O(n)

0B.0(nA2)

C.0(2n)

D.O(logn)

20.【单选题】(2分)

在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是()。

A.0(1)

0B.0(n)

C.O(n2)

D.O(nlogn)

21•【简答题】(6分)

以关键字序列(230.309,675.141,927,779,594,090,338,822)为例,分别写出执行以下排序

算法的各趟排序结束时.关键字序列的状态。

(1)归并播序:(2)基数排序

有下列运行时间函数，分别写Hl相应的大。表示的运行时间。

(1)T(n)=2A6;

(2)T(n)=10n2+2n+50;

(3)T(n)=n3+50n2+1;

(4)T(n)=2T(n/2)+n,n>1;当n=1时，T(n)=1

23•【简答题】(5分)

将关键字｛9,10,14,30,11,12,7｝散列存储到散列表中，算列表的存储空间是一个下标从。开始的一

维数组，散列函数为H(Key)=(key*3)mod7,处理冲突的法规范为线性再散列发，要求装填因子为0.7。

(1)请画出所构造的散列表。

(2)分别计算出等概率情况下，查找成功和查找不成功的平均查找长度。

24.【简(6分)

有一个带头结点的单链表L,设计一个函数使其元素递减有序。其中单链表结构定义如下：

structLnode｛

intdata;

structLnode*next;

)；

25.【简答题】(5分)

将(for,case,while,class,protected,virtual,public,private,do,template,const,if,int)中的关键字依

次插入初态为空的二叉排序树中，请画出所得到的树T,然后画出删去for之后的一义排序树T；

设顶点表示村庄，有向边代表交通路线。若要建立一家医院，试问建立在那个村庄能使得各村庄总体上的交

通代价最小，写出计算过程。

编写函数判断以邻接矩阵存储的有向图是否存在一条从V