习　题　2

一、填空题

1.在顺序表中,逻辑上相邻的元素,其物理位置上＿＿＿＿相邻。

2.在单链表中,逻辑上相邻的元素,其物理位置上＿＿＿＿相邻。

3.设单链表中指针p指向结点s,若要删除s之后的结点（若存在）,则需修改指针的操作为＿＿＿＿＿＿＿＿。

4.在一个长度为n的顺序表中,如果要删除第i个元素,需移动＿＿＿＿个元素。

二、选择题

1.某线性表中最常用的操作是存取序号为i的元素和在最后进插入和删除运算,则采用（　　）存储方式的时间性能最好。

A.双向链表　　　　　　　　　　　　　B.双向循环链表

C.顺序表　　　　　　　　　　D.单向循环链表

2.在一个单链表中,已知q结点是p结点的前驱结点,若在q和p之间插入s结点,则须执行（　　）。

A.s－＞next＝p－＞next；p－＞next＝s　B.p－＞next＝s－＞next；s－＞next＝p

C.q－＞next＝s；s－＞next＝p　D.p－＞next＝s；s－＞next＝q

3.带头结点的单链表为空的判定条件是（　　）。

A.L＝NULL　B.L－＞next＝NULL

C.L－＞next＝head　D.L！＝NULL

4.某线性表中最常用的操作是存取第i元素及其前驱结点的值,则采用（　　）存储方式能节省时间。

A.双向链表B.双向循环链表

C.顺序表D.单向循环链表

5.已知一个带头结点的非空循环单链表,其尾指针是R,则其首元素结点的地址为（　　）。

A.R－＞next　B.＊（r－＞next－＞next）

C.＆（r－＞next－＞next）D.R－＞next－＞next

三、编程题

1.试设计一算法:从顺序表中删除自第i个元素开始的k个元素。

2.试将一个无序的顺序表A＝（11,17,45,23,87,56,19,25）,转换成一个按升序排列的有序顺序表（用链表实现）。

3.给出删除单链表中值为k的结点的算法。

4.试给出求单链表长度的算法。

5.试给出在有序链表中插入一值为k的结点的算法。

6.试将入口为head的有序单链表,按所给关键字k分成两个循环链表。其中,比k小的所有结点组成入口为h₁的循环链表,比k大的所有结点组成入口为h₂的循环链表。

7.试设计一算法来实现顺序表的逆置。

8.对于顺序表,写出下列操作的算法。

（1）从表中删除最小值的元素并由函数返回,空出的位置由最后一个元素补上,若为空表,则显示错误信息并退出运行。

（2）删除表中值为x的结点并由函数返回。

（3）向表中第i个元素之后插入一个值为x的元素。

（4）从表中删除值在x～y之间的所有元素。

（5）将表中的元素排成一个有序表。

（6）从有序表中删除值在x～y之间的所有元素。

9.对于单链表,写出下列操作的算法。

（1）根据一维数组建立一个单链表,使单链表中元素的顺序与数组的次序相同。

（2）统计单链表中值在x～y之间的所有结点个数。

（3）删除单链表中从第k个结点开始连续的j个结点。

（4）将该单链表分解为两个单链表,使其中一个单链表中仅含有奇数,另一个单链表中仅含有偶数。

（5）将另一个已经存在的单链表插入到该链表的第k个结点之后。

（6）将单链表中的所有元素排成一个有序序列。