数据结构-一文吃透线性表中链表题目

旧城等待， 2022-12-12 02:29 111阅读 0赞

**1.链表不具有的特点是 ( A)**

**A. 可随机访问任一元素**

**B. 插入删除不需要移动元素**

**C．不必事先估计存储空间**

**D．所需空间与线性表长度成正比**

### **答案解析** ###

**\[解析\] 链表采用的是链式存储结构，它克服了顺序存储结构的缺点：它的接点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。但是链式存储结构也有不****足****之处：①每个结点中的指针域需额外占有存储空间；②链式存储结构是一种非随机存储结构。**

**2.设单链表中指针p指向A，若要删除A的后继结点,则需修改指针的操作为(p->next=p->next->next;)。**

**3.非空的循环单链表由头指针head表示,则其尾结点(由指针p所指)满足(p->next=head)。**

### **答案解析** ###

**\[解析\] 循环链表也是一种链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。所以p→next为head，即p→next＝head。选项C正确**

**4.在有尾指针rear指示的循环单链表中，在表尾插入一个结点s的操作序列是s->next=(\[填空1\];\[填空2\]=s;(填空3);)删除开始结点的操作序列是q=(\[填空4\]);(\[填空5\]);delete q;**

**\[填空1\]rear->next**

**\[填空2\]rear->next**

**\[填空3\]rear=s**

**\[填空4\]rear->next->next**

**\[填空5\]rear->next->next=q->next**

**答案解析**

**\[解析\]s->next=rear->next;rear->next=s;rear=s;**

**q=rear->next->next;rear->next->next=q->next;delete q；**

![20201005164557869.png][]

**5.在一个单链表中，已知q所指结点是p所指结点的直接前驱,若在q和p之间插入s所指结点,则执行(B)操作。**

**A.s->next=p->next;p->next=s;**

**B.q->next=s;s->next=p;**

**C.p->next=s->next;s->next=p;**

**D.p->next=s;s->next=q;**

**答案解析**

**6.在具有n个结点的有序单链表中插入一个新结点并使链表仍然保持有序的时间复杂度是(B)。**

**A.O(1)**

**B.O(n)**

**C.O(n^2)**

**D.O(nlog2^n)**

### **答案解析** ###

**本题主要考核有序单链表上的插入操作及算法分析。对数据结构的任何操作都不能改变其原有的结构特性。因此，在有序单链表中插入一个新结点后，仍然要保持它的有序性。**  
**插入操作的关键是查找插入位置，主要时间也是花在插入位置的查找上。n个结点的单链表，有，n+1个可能插入的位置，即第一个结点之前和每一个结点之后。在第一个结点之前插入，需比较一次；在第一个结点之后插入需比较两次；……；在第，n个结点之后插入需查找次。**

**7.假设将线性表L存储在以head为头指针的不带头节点的单链表中，则当\[填空1\]时，表示线性表L是空表。假设将线性表L存储在以head为头指针的带头结点的单链表中，则当\[填空2\]时，表示线性表L是空表。**

**\[填空1\]head=NULL**

**\[填空2\]head->next=NULL**

### **答案解析** ###

**带头结点判空表的条件head->next == NULL**  
**不带头结点判空表的条件 ****head****== NULL；此时****head****是头指针**

**8.在循环双链表的p所指结点后插入s所指结点的操作是()**

**s->prior=\[填空1\];**

**s->next=\[填空2\];**

**p->next->prior=s;**

**p-next=\[填空3\];**

### **答案解析** ###

**\[填空1\]p**

**\[填空2\]p->next**

**\[填空3\]s**

**9.在一个单链表中p所指结点之后插入一个s所指结点时,应执行s->next=\[填空1\]和p->next=\[填空2\]的操作。**

**\[填空1\]p->next**

**\[填空2\]s**

**10.假设线性表只有4种基本操作:删除第一个元素;删除最后一个元素;在第一个元素前插入新元素;在最后一个元素之后插入新元素;则最好使用(C)**

**A.只设尾指针的循环单链表**

**B.只设尾指针的非循环双链表**

**C.只设头指针的循环双链表**

**D.同时设置头指针和尾指针的循环单链表**

### **答案解析** ###

**对于A的链表，删除最后一个结点p时，需要找到p的前一个结点，其时间复杂度为O(n)；对于B的链表，删除第一个结点的p时，需找到头结点，这里没给出头结点指针，故无法实现这种操作。对于C的链表，这4种操作的时间复杂度都为O(1)，对于D的链表，删除最后一个结点p时，需要找到p的前一个结点，其时间复杂度为O(n)。**

**11.****设n表示线性表中的元素个数,P表示每个指针所需的存储单元大小,E表示存储每个数据元素所需的存储单元大小，则使用单链表存储方式存储该线性表需要(\[填空1\])存储空间。**

**\[填空1\]n(P+E)**

**12.在如下数组A中存储了一个静态链表，表头指针为A\[0\].next,试写出该线性表。**

![2020100516484919.png][]

**\[填空1\]78，\[填空2\]50，\[填空3\]40，\[填空4\]60，\[填空5\]34，\[填空6\]90**

**13.****已知数组A\[n\]中的元素为整型，设计算法将其调整为左右两个部分，左边所有元素为奇数，右边所有元素为偶数，要求时间复杂度为O(n)。**

### **答案解析** ###

**【解答】 从数组的两端向中间比较，设置两个变量 i 和 j，初始时 i=0 ，j=n-1 ，若 A\[i\] 为偶数并且 A\[j\] 为奇数，则将 A\[i\] 与 A\[j\] 交换。具体算法如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70][]

**14.设单链表以非递减有序排列，****设计算法实现在单链表中删除值相同的多余结点。**

**注:请用文字或上传图片作答。**

**【解答】 从头到尾扫描单链表，若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1][]

**补充知识点：**

**1,2,3,4,5,.:递增排列**

**9,8,7,6,5.:递减排列**

**1,2,3,3,4,5,8,8,.:非递减排列**

**9,8,7,7,6,5,5,2,1,.:非递增排列**

**我是热爱生活，热爱编程，喜欢研究的呵呵哒！**

**如果喜欢的话，不妨点个赞收藏一下吧~**

如果有错误，欢迎指正~

[20201005164557869.png]: /images/20221123/843f1d9cf2fb48508e92f604ef1ee6f3.png
[2020100516484919.png]: /images/20221123/c7da5395896a42e5961dd8f7fffefc1c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70]: /images/20221123/41100d5c8d584fe2aaf5a996150c36fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1]: /images/20221123/581091e67f814b0f8241486ad6487321.png