(完整word版)数据结构考试题5

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写

上姓名和

学号。

一、单项选择题

(

每小题

2

分，共

20

小题，共计

40

分

) 

1

.

某算法的空间复杂度为

0(1),

则

。

A.

该算法执行不需要任何辅助空间

B.

该算法执行所需辅助空间大小与问题规模

n

无关

C.

该算法执行不需要任何空间

D.

该算法执行所需全部空间大小与问题规模

n

无关

2

.

在长度为

n

的顺序表中插入一个元素，对应算法的时间复杂度为

。

A.0(1) 

B.O(log

2

n) 

C.0(n) 

D.0(n

2

) 

3

.

设线性表中有

n

个元素，以下运算中，

在单链表上实现要比在顺序表上实现

效率更高。

A.

删除指定位置元素的后一个元素

B.

在最后一个元素的后面插入一个新元素

C.

顺序输出前

k

个元素

D.

交换第

i

个元素和第

n-i+1

个元素的值

(

i=1, 

2,…，

n) 

4

.

以下数据结构中元素之间为非线性关系的是

。

A.

栈

B.

队列

C.

线性表

D.

以上都不是

5

.

若一个栈用数组

data[1..n]

存储，初始栈顶指针

top

为

n+1,

则以下元素

x

进栈的正

确操作是

。

A.top++;data[top]=x; 

B.data[top]=x;top++; 

C.top-- ;data[top]=x; 

D.data[top]=x;top --; 

6

.

若某循环队列有队首指针

front

和队尾指针

rear,

在队不满时进队操作仅会改

变

。

A.front 

B.rear 

C.front 

和

rear 

D.

以上都不队

7

.

设循环队列中数组的下标是

0

〜

N-1,

其队头、队尾指针分别为

f

和

r(f

指向队首元

素的前

一位置，

r

指向队尾元素

)

，则其元素个数为

。

A.r-f 

B.r-f-1 

C.(r-f)%N+1 

D.(r-f+N)%N 

8

.

设树

T

的度为

4,

其中度为

1

、

2

、

3

、

4

的结点个数分别为

4

、

2

、

1

、

1,

则

T

中的

叶子结点个数是

。

A.5 

B.6 

C.7 

D.8 

9

. 

一棵哈夫曼树中共有

199

个结点，它用于多少个字符的编码

。

A.99 

B.100 

C.101 

D.199 

10

.

设森林

F

中有

4

棵树，第

1

、

2

、

3

、

4

棵树的结点个数分别为

a

、

b

、

c

、

d,

将森林

F

转换为一颗二叉树

B,

则二叉树

B

根结点的左子树上的结点个数是

。

A.a-1 

B.a 

C. a+b+c 

D.b+c+d