习题二
一、选择题
1．以下关于线性表的叙述正确的是（ ）。
Ⅰ 线性表中每个数据元素都有一个前驱和一个后继
II 线性表中所有元素必须按由小到大或由大到小的顺序排列
III 线性表是由有限个相同类型的数据元素所构成的序列
IV 线性表基本操作的实现取决于采用哪一种存储结构，存储结构不同，实现的算法也不同
A．Ⅰ，II，III
B．II，III，IV
C．III，IV
D．III
2．设线性表有n个元素，以下操作中，（ ）在顺序表上实现比链表上实现效率更高。
A．输出第i个（0≤i≤n-1）数据元素的值
B．交换第1个数据元素与第2个数据元素的值
C．顺序输出这n个数据元素的值
D．输出与给定值x相等的数据元素在线性表中的序号
3．假设在顺序表{a1，a2，…，an}中，每一个数据元素所占的存储单元的数目为4，且第1个数据元素的存储地址为100，则第7个数据元素的存储地址是（ ）。
A．106
B．107
C．124
D．128
4．设线性表有n个元素，严格说来，以下操作中，（ ）在顺序表上实现比链表上实现效率更高。
Ⅰ 输出第i个（0≤i≤n-1）数据元素的值
II 交换第3个数据元素与第4个数据元素的值
III 顺序输出这n个数据元素的值
A．Ⅰ
B．Ⅰ，II
C．Ⅰ，III
D．II，III
5．在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ ）存储方式。
A．顺序表
B．用头指针标识的循环单链表
C．用尾指针标识的循环单链表
D．双向链表
6．在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s，则修改链指针的C语言语句序列是（ ）。
A．s-＞next=p；q-＞next=s
B．p-＞next=s-＞next；s-＞next=p
C．q-＞next=s-＞next；s-＞next=p
D．p-＞next=s；s-＞next=q
7．在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ ）。
A．O（1）
B．O（log2n）
C．O（n）
D．O（n2）
8．要将一个顺序表{a1，a2，…，an}中第i个数据元素ai（1≤i≤n）删除，需要移动（ ）个数据元素。
A．i
B．n-i-1
C．n-i
D．n-i+1
9．在带头结点的双向循环链表中的p结点之后插入一个新结点s，其修改链指针的C语言语句序列是（ ）。
A．p-＞next=s；s-＞prior=p；p-＞next-＞prior=s；s-＞next=p-＞prior；
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-＞next=p-＞next；s-＞prior=p；p-＞next-＞prior=s；p-＞next=s；
10．顺序表的存储密度（ ），而单链表的存储密度（ ）。
A．小于1
B．等于1
C．大于1
D．不能确定
二、填空题
1．线性表是由n（n≥0）个数据元素所构成的__________，其中n为数据元素的个数，称为线性表的__________，n=0的线性表称为__________。
2．线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其他每一个数据元素有且仅有一个_____，有且仅有一个______。
3．线性表通常采用_____和______两种存储结构。若线性表的长度确定或变化不大，则适合采用_______存储结构进行存储。
4．在顺序表{a1，a2，…，an}中的第i（1≤i≤n+1）个位置之前插入一个新的数据元素，会引起_______个数据元素的移动操作。
5．在表长为n的顺序表中查找值为x的数据元素时，查找成功时需与元素比较的平均次数是_______。
6．在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行________存取。
7．顺序表中逻辑上相邻的数据元素，其物理位置_______相邻，而在单链表中逻辑上相邻的数据元素，其物理位置________相邻。
8．在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是________。
9．在一个单链表中p所指结点之前插入一个s所指结点时，可执行如下操作：
s-＞next=______；p-＞next=s；t=p-＞data；p-＞data=______；s-＞data=_______
10．在一个单链表中删除p所指结点时，可执行如下操作：
q=p-＞next；p-＞data=q-＞data；p-＞next=_________；
三、判断题
1．在顺序表中逻辑上相邻的元素，其对应的物理位置也是相邻的。
2．线性表的顺序存储空间一旦分配，则其大小固定，不能在程序执行时进行改变。
3．所谓随机存取，就是通过首地址和元素的位序号值可以在O（1）的时间内找到指定的元素。
4．顺序存储的线性表不支持随机存取。
5．在顺序表上进行插入或删除操作时需要移动元素的个数与待插入或待删除元素的位置无关。
6．单链表不是一种随机存取的存储结构。
7．顺序存储是动态的存储结构，链式存储结构是静态的存储结构。
8．线性表的唯一存储形式是链表。
9．线性表的长度是线性表所占用的存储空间的大小。
10．一个循环链表可能由给定的头指针或尾指针唯一标识。
四、算法设计题
1．设计算法，实现对顺序表就地逆置的操作。所谓逆置，就是把{a1，a2，…，an}变成{an，an-1，…，a1}；所谓就地，就是指逆置后的数据元素仍存储在原来顺序表的存储空间中，即不为逆置后的顺序表另外分配存储空间。
2．已知顺序表{a1，a2，…，an}中的数据元素类型为整型int，试设计一个在时间和空间两方面都尽可能高效的算法，实现将顺序表循环右移k位的操作。即原来顺序表为{a1，a2，…，an-k，an-k+1，…，an}，循环向右移动k位后变成{an-k+1，…，an，a1，a2，…，an-k}。
3．已知顺序表{a1，a2，…，an}中的数据元素类型为整型int，设计一个时间与空间上尽可能高效的算法，将其调整为左、右两部分，左边所有数据元素为奇数，右边所有数据元素为偶数。
4．一个长度为L（L≥1）的升序序列S，处在第[L/2]个位置的数称为S的中位数，其中[L/2]的运行符“[]”表示对运算结果L/2取整。例如：若序列S1=（11，13，15，17，19），则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如：若S2=（2，4，6，8，20），则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间上都尽可能高效的算法，找出两个序列A和B的中位数。
5．设计算法，实现对带头结点的单链表就地逆置的操作。
6．设计算法，实现删除不带头结点的单链表中数据域值等于x的第一个结点的操作。若删除成功，则返回被删除结点的位序号；否则，返回0。
7．设计算法，找出已知两个链表的第一个公共结点。所谓两个链表有公共结点，就是指两个链表从某个结点开始，它们的next都指向同一个结点，这个开始结点就是两个链表的第一个公共结点。
8．设计算法，实现将一个用循环链表表示的稀疏多项式分解成两个多项式的操作，并使两个多项式中各自仅含奇次项或偶次项。要求利用原循环链表中的存储空间构成这两个链表。