一、单选题（共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(nnext ==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)。( × )