3.6 习题

一、选择题

1.线性结构中的一个结点代表一个（ ）。

A.数据元素

B.数据项

C.数据

D.数据结构

2.顺序表是线性表的（ ）。

A.链式存储结构

B.顺序存储结构

C.索引存储结构

D.散列存储结构

3.对顺序表上的插入、删除算法的时间复杂度分析来说，通常以（ ）为标准操作。

A.条件判断

B.结点移动

C.算术表达式

D.赋值语句

4.在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为（ ）。

A.n

B.n／2

C.（n-1）／2

D.（n＋1）／2

5.带头结点的单链表head为空的条件是（ ）。

A.head＝NULL

B.head-＞next＝NULL

C.head-＞next＝head

D.head！＝NULL

6.在双循环链表的p结点之后插入s结点的操作是（ ）。

A.p-＞next＝s；s-＞prior＝p；p-＞next-＞prior＝s；s-＞next＝p-＞next；

B.p-＞next＝s；p-＞next-＞prior＝s；s-＞prior＝p：s-＞next＝p-＞next；

C.s-＞prior＝p；s-＞next＝p-＞next；p-＞next＝s；p-＞next-＞prior＝s；

D.s-＞prior＝p；s-＞next＝p-＞next；p-＞next-＞pror＝s；p-＞next＝s；

7.在一个单链表中，若p结点不是最后结点。在p之后插入结点s，则执行（ ）。

A.s-＞next＝p；p-＞next＝s；

B.s-＞next＝p-＞next；p-＞next＝s；

C.s-＞next＝p-＞next；p＝s；

D.p-＞next＝s；s-＞next＝p；

8.循环链表的主要优点是（ ）。

A.不再需要头指针了

B.已知某个结点的位置后，容易找到它的直接前驱

C.在进行插入、删除操作时，能更好地保证链表不断开

D.从表中任一结点出发都能扫描到整个链表

9.设有一顺序栈s，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是（ ）。

A.2

B.3

C.5

D.6

10.设有一顺序栈已经含有3个元素，如图3-29所示，元素a4正等待入栈。以下序列中不可能出现的出栈序列是（ ）。

A.a3，a1，a4，a2

B.a3，a2，a4，a1

C.a3，a4，a2，a1

D.a4，a3，a2，a1

11.若一个栈的输入序列是1，2，3，4，…，n，输出序列的第一个元素是n，则第i个输出元素是（ ）。

A.不确定

B.n-i

C.n-i＋1

D.n-i-1

12.循环队列的队满条件为（ ）。

A.（sq.rear＋1）%maxsize＝＝（sq.front＋1）%maxsize；

B.（sq.rear＋1）%maxsize＝＝sq.front＋1；

C.（sq.rear＋1）%maxsize＝＝sq.front；

D.sq.rear＝＝sq.front；

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

A.e，d，c，b，a

B.d，e，c，b，a

C.d，c，e，a，b

D.a，b，c，d，e

14.一个队列的入队序列是1，2，3，4，则队列的可能的输出序列是（ ）。

A.4，3，2，1

B.1，2，3，4

C.1，4，3，2

D.3，2，4，1

二、判断题

1.顺序存储的线性表可以随机存取。（ ）

2.顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。（ ）

3.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（ ）

4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。

（ ）

5.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（ ）

6.在单链表中，可以从头结点开始查找任何一个元素。（ ）

7.线性表的链式存储结构优于顺序存储结构。（ ）

8.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。（ ）

9.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。（ ）

10.顺序存储方式只能用于存储线性结构。（ ）

11.在顺序栈栈满情况下，不能再入栈，否则会产生“上溢”。（ ）

12.若一个栈的输入序列为1，2，3，…，n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai＝i＋1（i＝1，2，…，n）。（ ）

13.循环队列中元素个数为rear-front。（ ）

14.一个栈的输入序列是1，2，3，4，则在栈的输出序列中可以得到4，3，1，2。（ ）

15.一个栈的输入序列是1，2，3，4，则在栈的输出序列中可以得到1，2，3，4。（ ）

三、填空题

1.线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接____外，其他结点有且仅有一个直接____；除终端结点没有直接____外，其他结点有且仅有一个直接____。

2.线性表的逻辑结构是____结构，其所含结点的个数称为线性表的。

3.非空的单循环链表head的尾结点（由指针p所指）满足。

4.对于一个具有n个结点的单链表，在p所指结点后插入一个结点的时间复杂度为____，在给定值为x的结点后插入新结点的时间复杂度为。

5.在顺序表中插入或删除一个元素，平均需要移动____元素，具体移动的元素个数与____有关。

6.在单链表中，若p和s是两个指针，且满足p-＞next与s相同，则语句p-＞next＝s-＞next的作用是____s指向的结点。

7.在单链表中，指针p所指结点为最后一个结点的条件是____。

8.在具有n个单元的循环队列中，队满时共有____个元素。

9.假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为____。

10.栈的逻辑特点是____，队列的逻辑特点是____，两者的共同特点是____。

11.____可以作为实现递归函数调用的一种数据结构。

12.在队列中，新插入的结点只能添加到____。

四、应用题

1.何时选用顺序表，何时选用链表作为线性表的存储结构为宜？

2.下列算法的功能是什么？

3.若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？

4.设有字符串为3*-y-a／y＾2，试利用栈写出将其转换为3y-*ay2＾／-的操作过程。假定用X代表扫描该字符串过程中顺序取一个字符入栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS。

5.按照运算符优先法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程：9-2*4＋（8＋1）／3。

五、算法设计题

1.设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。

2.设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C。

3.已知由单链表表示的线性表中，含有3类字符的数据元素（如字母字符、数字字符和其他字符），试编写算法构造3个以循环链表表示的线性表，使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这3个表的结点空间，头结点可另辟空间。

4.双循环链表中，设计满足下列条件的算法。

（1）在值为x的结点之前插入值为y的结点。

（2）在值为x的结点之后插入值为y的结点。

（3）删除值为x的结点。