下载掌阅APP，畅读海量书库
立即打开
一、单项选择题
1. 线性表的顺序存储结构是一种（ ）的存储结构，线性表的链接存储结构是一种（ ）的存储结构。
A. 顺序存取
B. 随机存取
C. 索引存取
D. 散列存取
2. 顺序表中逻辑上相邻的元素的物理位置（ ）。单链表中逻辑上相邻的元素的物理位置（ ）。
A. 一定是连续的
B. 部分是连续的
C. 一定不连续
D. 不一定连续
3. 链表不具有的特点是（ ）。
A. 插入、删除不需要移动元素
B. 不需要事先估计存储空间
C. 所需空间与线性表长度成正比
D. 可以随机访问任一个元素
4. 判断不带头结点的单链表head指针是否为空的条件是（ ）。
A. head==NULL
B. head-＞next==NULL
C. head-＞next==head
D. head！=NULL
5. 判断带头结点的单链表head指针为空的条件是（ ）。
A. head==NULL
B. head-＞next=NULL
C. head-＞next==head
D. head！=NULL
6. 非空的循环单链表head的尾结点（由p所指向）满足（ ）。
A. p-＞next=NULL
B. p=NULL
C. p-＞next=head
D. p=head
7. 在一个单链表中，已知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；
8. 在一个单链表中，若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；
9. 在一个单链表中，若删除p所指结点的后续结点，则执行（ ）。
A. p-＞next=p-＞next-＞next；
B. p=p-＞next；p-＞next=p-＞next-＞next；
C. p-＞next=p-＞next；
D. p=p-＞next-＞next；
10. 对于n个元素建立一个有序单链表的最好时间复杂度是（ ）。
A. O （1）
B. O （ n ）
C. O （ n 2 ）
D. O （ n log 2 n ）
二、填空题
1. 在顺序表中插入或删除一个元素，需要平均移动__________个元素，具体移动的元素个数与__________有关。
2. 对一个线性表分别进行遍历和逆置运算，其最好的时间复杂度分别为__________和__________。
3. 线性表的两种存储结构分别是__________和__________。
4. 在双向链表中，每个结点有__________个指针域，一个指向__________，一个指向__________。
5. 在一个非空单链表中，p指针所指结点既不是首元结点也不是尾元结点，在p指针所指结点之后插入结点s可执行如下操作：
s-＞next=__________；p-＞next=s；
6. 在一个非空单链表中，p指针所指结点既不是首元结点也不是尾元结点，在p指针所指结点之前插入结点s可执行如下操作：
提示：仿照上一题完成插入，然后交换两个节点的值即可。
s-＞next=__________；p-＞next=s；
t=p-＞data；p-＞data=__________；s-＞data=t；
7. 在一个非空单链表中，p指针所指结点既不是首元结点也不是尾元结点，删除p指针指向的结点可执行如下操作：
提示：题目中只给出了一个结点指针。
q=p-＞next；
p-＞data=p-＞next-＞data；
p-＞next=__________；
free（q）；
三、简答题
1. 线性表可用顺序表或链表存储。试问：
（1）两种存储表示各有哪些主要优缺点？
（2）如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变，在此情况下，应选用哪种存储表示？为什么？
（3）若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时应采用哪种存储表示？为什么？
2. 描述以下3个概念的区别：头指针、头结点和首元结点。
3. 下面的C语言函数实现从一个无头结点的单链表中删除首元结点，找出并修改函数中的错误。
四、算法设计题
1. 从顺序表中删除具有最小值的元素并由函数返回最小值，空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
2. 从顺序表中删除具有给定值 x 的所有元素。
3. 从顺序表中删除所有值在给定值 s 和 t （要求 s 小于 t ）之间的元素。
4. 从顺序表中删除所有重复的元素，使所有元素的值均不同。如对于线性表（2，8，9，2，5，5，6，8，7，2），则执行此算法后变为（2，8，9，5，6，7）。注意：表中元素未必是排好序的，且每个值的第一次出现应当保留。
5. 将元素为整数的顺序表（ a 1 ， a 2 ，…， a n ）重新排列为以 a 1 为界的两部分： a 1 前面的值均比 a 1 小， a 1 后面的值都比 a 1 大，要求时间复杂度为 O （ n ）。
6. 用尾部插入法来创建单链表，即每次生成的新结点均插入在链表的尾部。
7. 根据一个元素类型为整型的单链表生成两个单链表，使得第一个单链表中包含原单链表中所有元素值为奇数的结点，使得第二个单链表中包含原单链表中所有元素值为偶数的结点，原有单链表保持不变。
8. 设表La和Lb中各元素值均递增有序。试写一算法，使得La和Lb合并后的新表中的元素仍保持递增有序。
9. 求循环链表中结点的个数。
10. 已知一个单链表，设计一个复制单链表的算法。
11. 已知一个无序单链表，表中结点的data字段为正整数。设计一个算法按递增次序打印表中结点的值。
12. 已知一个单链表，输出该链表中倒数第 k 个结点的元素。
提示：考虑算法的效率，考虑链表为空、 k =0等特殊情况。
13. 已知一个单链表，判断在该单链表中是否存在一个环。