数据结构试题期中期末考试【含答案】

数据结构期中考试含答案

一、单选题（共35题）

1、（2分）

一个栈的入栈序列是：a, b, c, d, e，则栈的不可能 的输出序列是（ C ）。

A.edcba

B.decba

C.dceab

D.abcde

2、（2分）

建立一个含n个元素的单链表的时间复杂度是（ B ）。

A.O(1)

B.O(n)

C.O(n^2)

D.O(nlogn)

3、（2分）

下列序列中，不是线性表的是（ C ）。

A.（‘A’，‘B’，‘C’，‘D’，‘E’）

B.（‘AB’，‘CDE’）

C.（‘AB’，25，‘DE’）

D.（5，7，2，51，4）

4、（2分）

线性表L=(a1，a2,……an)，下列说法正确的是（ D ）。

A.每个元素都有一个直接前驱和一个直接后继

B.表中诸元素的排列必须是由小到大或由大到小

C.线性表中至少有一个元素

D.除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

5、（2分）

用链接方式存储的队列，在进行删除运算时（D ）。

A.仅修改头指针

B.仅修改尾指针

C.头、尾指针都要修改

D.头、尾指针可能都要修改

6、（2分）

以下对数组的描述，正确的是（ C ）。

A.存取数组中各元素的时间各不相同

B.对数组元素可进行访问、插入和删除操作

C.数组可看成是线性表的扩展

D.数组各元素的数据类型可以不同

7、（2分）

设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（B ）。

A.2

B.3

C.4

D.6

8、（2分）

广义表A=（a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail(A)))))的值是（ C ）

A.（g)

B.(d)

C.d

D.c

9、（2分）

广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ D ）。

A． (g)

B． (d)

C． c

D． d

10、（2分）

设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ C ）。

A．13

B．32

C．33

D．40

11、（2分）

算法的时间复杂度与（ B ）有关。

A.程序设计语言

B.问题规模

C.计算机硬件性能

D.编译程序质量

12、（2分）

在线性表的链式存储结构中，能从当前结点出发访问任一点的存储结构是（ D ）。

A.单链表

B.双向链表

C.循环链表

D.B和C

13、（2分）

若一个栈的进栈序列为1，2，3，4，则合法 的出栈序列是（ C ）。

A.1，4，2，3

B.4，1，2，3

C.3，2，1，4

D.4，3，1，2

14、（2分）

从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较（ D ）个结点。

A.n

B.n/2

C.(n-1)/2

D.(n+1)/2

15、（2分）

用双向链表表示线性表时，较之单链表更容易进行（ D ）。

A.结点的插入

B.结点的删除

C.线性表的扩充

D.对结点的访问

16、（2分）

在双向链表存储结构中，删除p所指的结点时须修改指针（ B ）。

A.p->prior=p->next->next; p->next=p->prior->prior;

B.p->next->prior=p->prior; p->prior->next=p->next;

C.p->next=p->next->next; p->next->prior=p;

D.p->prior->next=p; p->prior=p->prior->prior;

17、（2分）

在下面各种链表结构中，能在O(1)时间内完成在指定结点P之前插入元素X的结构是（ D ）。

A.不带表头的单链表

B.单向循环链表

C.带表头结点的单链表

D.双向循环链表

18、（2分）

若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ C ）种情况。

A.5，4，3，2，1

B.2，1，5，4，3

C.4，3，1，2，5

D.2，3，5，4，1

19、（2分）

设广义表L=((a,b,c))，则L的长度和深度分别为（ C ）。

A．1和1

B．1和3

C．1和2

D．2和3

20、（2分）

在数据结构中，从逻辑上可以把数据结构分成（ B ）。

A.动态结构和静态结构

B.线性结构和非线性结构

C.紧凑结构和非紧凑结构

21、（2分）

以下与数据的存储结构无关的术语是（ C ）。

A.顺序队列

B.链表

C.有序表

D.链栈

22、（2分）

一个队列的输入序列是1,2,3,4，则队列的输出序列是（ D ）。

A.3,2,4,1

B.4,3,2,1

C.1,4,3,2

D.1,2,3,4

23、（2分）

链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ A ）。

A.x=top->data;top=top->link；

B.top=top->link;x=top->link；

C.x=top;top=top->link；

D.x=top->link；

24、（2分）

串下面关于串的的叙述中，（ B ）是不正确的？

A．串是字符的有限序列

B．空串是由空格构成的串

C．模式匹配是串的一种重要运算

D．串既可以采用顺序存储，也可以采用链式存储

25、（2分）

在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ C ）。

A.p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;

B.q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

C.q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

D.p->next=q; q->prior=p; p->next->prior=q; q->next=q;

26、（2分）

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

A.随机存取

B.链式存取

C.索引存取

D.散列存取

27、（2分）

如果以链表作为栈的存储结构，在出栈操作时，则（ C ）。

A.必须判断栈是否满

B.不需要判断栈是否空

C.必须判断栈是否空

D.对栈不作任何判别

28、（2分）

数组A[0…4,-3…-1,5…7]中含有元素的个数（ B ）。

A．55

B．45

C．36

D．16

29、（2分）

设有一个递归算法如下

int fact(int n) { //n大于等于0

if(n<=0) return 1;

else return n*fact(n-1); }

则计算fact(n)需要调用该函数的次数为（ A ）。

A.n+1

B.n-1

C.n

D.n+2

30、（2分）

假设以行序为主序存储二维数组A=array[1…100,1…100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（ B ）。

A．808

B．818

C．1010

D．1020

31、（2分）

能在Ｏ(1)时间内访问线性表的第i个元素的存储结构是（ A ）。

A.顺序存储结构

B.单向链表

C.单向循环链表

D.双向链表

32、（2分）

一个递归算法必须包括（C ）。

A.递归部分

B.迭代部分

C.终止条件和递归部分

D.终止条件和迭代部分

33、（2分）

循环队列存储在数组A[0…m]中，则入队列的操作为（ D ）

A.rear=rear+1

B.rear=(rear+)%m

C.rear=(rear+1)%m-1

D.rear=(rear+1)%(m+1)

34、（2分）

以下说法正确的是（ D ）。

A.数据元素是数据的最小单位

B.数据项是数据的基本单位

C.数据结构是带有结构的各数据项的集合

D.一些表面上很不相同的数据可以有相同的逻辑结构

35、（2分）

数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ D ）。

A.r-f

B.(n+f-r)%n

C.n+r-f

D.（n+r-f)%n

二、判断题（共15题）

1、一个非空广义表的表头总是一个单元素。( × )

2、算法分析只从时间复杂度角度进行分析，对空间开销无所谓。( × )

3、按行顺序存储的N*M二维数组a中，其中a[i][j]的地址表达是： a+i * N+j。( × )

4、线性表中的每个结点都有一个直接前驱和一个直接后继。( × )

5、数据项是最小的、有独立含义的、不可分割的单位。（ √ ）

6、栈和队列都是带限制操作的线性表。（ √ ）

7、带头结点head的循环单链表为空的判定条件是head->next ==head。 （ √ ）

8、空格串就是指长度为0的串。( × )

9、串是一种特殊的线性表，其特殊性体现在数据元素是单个字符。（ √ ）

10、在表头指针为head的单循环链表中，指针q指向尾结点的条件是 q->next == head。（ √ ）

11、数据结构包含了数据之间的逻辑结构和物理结构。（ √ ）

12、广义表((a,b,c))的深度和长度是一致的。( × )

13、一个非空广义表的表尾总是一个表元素。（ √ ）

14、链表的存取密度比顺序表大。( × )

15、广义表A=((a,b,c,d))的表尾tail(A)=(b,c,d)。( × )