一、习题

（一）选择题（题目中的链表如果不特别指出就是带头结点的链表）

1.下述各项中属于顺序存储结构优点的是（ ）。

A.存储密度大 B.插入运算方便

C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示

2.下面关于线性表的叙述中，错误的是（ ）。

A.线性表采用顺序存储，必须占用一片连续的存储单元

B.线性表采用顺序存储，便于进行插入和删除操作

C.线性表采用链接存储，不必占用一片连续的存储单元

D.线性表采用链接存储，便于插入和删除操作

3.线性表是具有n个（ ）的有限序列。

A.表元素 B.字符

C.数据元素 D.数据项

4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A.顺序表 B.双链表

C.双循环链表 D.单循环链表

5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A.单链表 B.不带头结点的单循环链表

C.双链表 D.不带头结点且有尾指针的单循环链表

6.静态链表中指针指示的是（ ）。

A.内存地址 B.数组下标

C.链表中下一元素在数组中的地址 D.左、右孩子地址

7.链表不具有的特点是（ ）。

A.插入、删除不需要移动元素 B.可随机访问任一元素

C.不必事先估计存储空间 D.所需空间与线性长度成正比

8.将两个有n个元素的有序表归并成一个有序表，其最少比较次数为（ ）。

A.n B.2n-1 C.2n D.n-1

9.单链表L（带头结点）为空的判断条件是（ ）。

A.L==NULL B.L-＞next==NULL

C.L-＞next！=NULL D.L！=NULL

10.在一个具有n个结点的有序单链表中插入一个新结点仍然保持有序的时间复杂度是（ ）。

A.O（1） B.O（n） C.O（n²） D.O（nlog₂n）

11.在一个长度为n（n＞1）的带头结点的单链表h上，另设有尾指针r（指向尾结点），执行（ ）操作与链表的长度有关。

A.删除单链表中的第一个结点

B.删除单链表中的最后一个结点

C.在单链表第一个元素前插入一个新结点

D.在单链表最后一个元素后插入一个新结点

12.在一个双链表中，在p结点之后插入结点q的操作是（ ）。

A.q-＞prior=p；p-＞next=q；p-＞next-＞prior=q；q-＞next=p-＞next；

B.q-＞next=p-＞next；p-＞next-＞prior=q；p-＞next=q；q-＞prior=p；

C.p-＞next=q；q-＞prior=p；q-＞next=p-＞next；p-＞next-＞prior=q；

D.q-＞prior=p；p-＞next=q；q-＞next=p-＞next；p-＞next-＞prior=q；

13.在一个双链表中，在p结点之前插入q结点的操作是（ ）。

A.p-＞prior=q；q-＞next=p；p-＞prior-＞next=q；q-＞prior=p-＞prior；

B.q-＞prior=p-＞prior；p-＞prior-＞next=q；q-＞next=p；p-＞prior=q-＞next；

C.q-＞next=p；p-＞next=q；q-＞prior-＞next=q；q-＞next=p；

D.p-＞prior-＞next=q；q-＞next=p；q-＞prior=p-＞prior；p-＞prior=q；

14.在一个双链表中，删除p结点的操作是（ ）（结点空间释放语句省略）。

A.p-＞prior-＞next=p-＞next；p-＞next-＞prior=p-＞prior；

B.p-＞prior=p-＞prior-＞prior；p-＞prior-＞prior=p；

C.p-＞next-＞prior=p；p-＞next=p-＞next-＞next；

D.p-＞next=p-＞prior-＞prior；p-＞prior=p-＞prior-＞prior；

15.非空的单循环链表L（带头结点）的终端结点（由p所指向）满足（ ）。

A.p-＞next==NULL B.p==L

C.p-＞next==L D.p-＞next==L&&p！=L

16.带头结点的双循环链表L为空的条件是（ ）。

A.L==NULL B.L-＞next-＞prior==NULL

C.L-＞prior==NULL D.L-＞prior==L&&L-＞next==L

17.线性表是（ ）。

A.一个有限序列，可以为空 B.一个有限序列，不可以为空

C.一个无限序列，可以为空 D.一个无限序列，不可以为空

18.线性表采用链表存储时，其结点地址（ ）。

A.必须是连续的 B.一定是不连续的

C.部分地址必须是连续的 D.连续与否均可以

19.线性表的静态链表存储结构与顺序存储结构相比，其优点是（ ）。

A.所有的操作算法实现简单 B.便于随机存取

C.便于插入和删除 D.便于利用零散的存储空间

20.设线性表有n个元素，以下操作中，（ ）在顺序表上实现比在链表上实现效率更高。

A.输出第i（1≤i≤n）个元素值 B.交换第1个元素与第2个元素的值

C.顺序输出这n个元素的值 D.输出与给定值x相等的元素在线性表中的序号

21.对于一个线性表，既要求能够快速地进行插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用（ ）存储结构。(www.daowen.com)

A.顺序 B.链式 C.散列（Hash表）

22.需要分配较大的连续空间，插入和删除不需要移动元素的线性表，其存储结构为（ ）。

A.单链表 B.静态链表 C.顺序表 D.双链表

23.如果最常用的操作是取第i个元素的前驱结点，则采用（ ）存储方式最节省时间。

A.单链表 B.双链表 C.单循环链表 D.顺序表

24.与单链表相比，双链表的优点之一是（ ）。

A.插入、删除操作更简单 B.可以进行随机访问

C.可以省略表头指针或表尾指针 D.访问前后相邻结点更灵活

25.在顺序表中插入一个元素的时间复杂度为（ ）。

A.O（1） B.O（log₂n） C.O（n） D.O（n²）

26.在顺序表中删除一个元素的时间复杂度为（ ）。

A.O（1） B.O（log₂n） C.O（n） D.O（n²）

27.对于一个具有n个元素的线性表，建立其单链表的时间复杂度为（ ）。

A.O（1） B.O（log₂n） C.O（n） D.O（n²）

28.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（ ）存储结构最节省运算时间。

A.单链表 B.给出表头指针的循环单链表

C.双链表 D.带头结点的循环双链表

29.线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，则采用（ ）存储方式最节省时间。

A.单链表 B.仅有头结点的单循环链表

C.双链表 D.仅有尾结点指针的单循环链表

30.设有两个长度为n的单链表（带头结点），结点类型相同，若以h1为头结点指针的链表是非循环的，以h2为头结点指针的链表是循环的，则（ ）。

A.对于两个链表来说，删除开始结点的操作，其时间复杂度分别为O（1）和O（n）

B.对于两个链表来说，删除终端结点的操作，其时间复杂度都是O（n）

C.循环链表要比非循环链表占用更多的内存空间

D.h1和h2是不同类型的变量

31.若设一个顺序表的长度为n。那么，在表中顺序查找一个值为x的元素时，在等概率的情况下，查找成功的数据平均比较次数为（①）。在向表中第i（1≤i≤n+1）个元素位置插入一个新元素时，为保持插入后表中原有元素的相对次序不变，需要从后向前依次后移（②）个元素。在删除表中第i（1≤i≤n）个元素时，为保持删除后表中原有元素的相对次序不变，需要从前向后依次前移（③）个元素。

① A.n B.n/2 C.（n+1）/2 D.（n-1）/2

② A.n-i B.n-i+1 C.n-i-1 D.i

③ A.n-i B.n-i+1 C.n-i-1 D.i

（二）综合应用题

1.基础题

（1）线性表可用顺序表或链表存储。试问：

1）如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变，在此情况下，应选用哪种存储表示？为什么？

2）若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时应采用哪种存储表示？为什么？

（2）为什么在单循环链表中设置尾指针比设置头指针更好？

（3）设计一个算法，将顺序表中的所有元素逆置。

（4）设计一个算法，从一给定的顺序表L中删除下标i～j（i≤j，包括i、j）的所有元素，假定i、j都是合法的。

（5）有一个顺序表L，其元素为整型数据，设计一个算法，将L中所有小于表头元素的整数放在前半部分，大于表头元素的整数放在后半部分。

（6）有一个递增非空单链表，设计一个算法删除值域重复的结点。例如，{1，1，2，3，3，3，4，4，7，7，7，9，9，9}经过删除后变成{1，2，3，4，7，9}。

（7）设计一个算法删除单链表L（有头结点）中的一个最小值结点。

（8）有一个线性表，采用带头结点的单链表L来存储。设计一个算法将其逆置。要求不能建立新结点，只能通过表中已有结点的重新组合来完成。

（9）设计一个算法，将一个头结点为A的单链表（其数据域为整数）分解成两个单链表A和B，使得A链表只含有原来链表中data域为奇数的结点，而B链表只含有原链表中data域为偶数的结点，且保持原来的相对顺序。

2.思考题

（1）有N个个位正整数存放在int型数组A[0，…，N-1]中，N为已定义的常量且N≤9，数组A[]的长度为N，另给一个int型变量i，要求只用上述变量（A[0]～A[N-1]与i，这N+1个整型变量）写一个算法，找出这N个整数中的最小者，并且要求不能破坏数组A[]中的数据。

（2）写一个函数，逆序打印单链表中的数据，假设指针L指向了单链表的开始结点。

（3）试编写一个函数，以不多于3n/2的平均比较次数，在一个有n个整数的顺序表A中找出最大值和最小值。

（4）设A=（a₁，a₂，…，am）和B=（b₁，b₂，…，b_n）均为顺序表，A'和B'分别是除去最大公共前缀后的子表。例如，A=（b，e，i，j，i，n，g），B=（b，e，i，f，a，n，g），则两者的最大公共前缀为b、e、i，在两个顺序表中除去最大公共前缀后的子表分别为A'=（j，i，n，g），B'=（f，a，n，g）。若A'=B'=空表，则A=B。若A'=空表且B'≠空表，或两者均不为空且A'的第一个元素值小于B'的第一个元素值，则A＜B，否则A＞B。试编写一个函数，根据上述方法比较A和B的大小。

二、真题精选

（一）选择题

1.求整数n（n≥0）阶乘的算法如下，其时间复杂度是（ ）。

A.O（log₂n） B.O（n） C.O（nlog₂n） D.O（n²）

2.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ）。

A.O（n） B.O（m×n） C.O（min（m，n）） D.O（max（m，n））

3.下列程序段的时间复杂度是（ ）。

A.O（log₂n） B.O（n） C.O（nlog₂n） D.O（n²）

（二）综合应用题

1.已知一个带有表头结点的单链表，结点结构为：

假设该链表只给出了头指针head。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k（k为正整数）个位置上的结点。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。

要求：

（1）描述算法的基本设计思想。

（2）描述算法的详细实现步骤。

（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++语言实现），关键之处请给出简要注释。

2.设将n（n＞1）个整数存放到一维数组R中。设计一个在时间和空间两方面尽可能高效的算法。将R中保存的序列循环左移P（0＜P＜n）个位置，即将R中的数据由（X₀，X₁，…，X_n-1）变换为（X_p，X_p+1，…，X_n-1，X₀，X₁，…，X_p-1）。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

（3）说明你所设计的算法的时间复杂度和空间复杂度。

3.已知一个整数序列A=（a₀，a₁，…，a_n-1），其中0≤ai＜n（0≤i＜n）。若存在a_p1=a_p2=…=a_pm=x且m＞n/2（0≤p_k＜n，1≤k≤m），则称x为A的主元素。例如，A=（0，5，5，3，5，7，5，5），则5为主元素；又如A=（0，5，5，3，5，1，5，7），则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。