【数据结构】第2章线性表课后题整理

灰太狼 2022-11-27 02:00 200阅读 0赞

《数据结构》严蔚敏第2版 第二章线性表课后题答案

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]

## 1、选择题 ##

（1）顺序表中第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地 址是（ ）。  
A．110 B．108 C．100 D．120  
答案：B  
解释：。。

100 102 104 106 108 
    1   2   3   4   5

（2）在 n 个结点的顺序表中，算法的时间复杂度是 O(1)的操作是（ ） 。  
A．访问第 i 个结点（1≤ i≤ n）和求第 i个结点的直接前驱（2≤ i≤ n）  
B．在第 i 个结点后插入一个新结点（1≤ i≤ n）  
C．删除第 i 个结点（1≤ i≤ n）  
D．将 n 个结点从小到大排序  
答案：A  
解释：在顺序表中插入一个结点的时间复杂度都是 O(n2)，排序的时间复杂度为 O(n2)或 O(nlog2n)。顺序表是一种随机存取结构，访问第 i 个结点和求第 i 个结点的直接前驱都可以直接 通过数组的下标直接定位，时间复杂度是O(1)。

（3） 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为（ ） 。  
A．8 B．63.5 C．63 D．7  
答案：B  
解释：平均要移动的元素个数为：n/2。

（4）链接存储的存储结构所占存储空间（ ） 。  
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针  
B．只有一部分，存放结点值  
C．只有一部分，存储表示结点间关系的指针  
D．分两部分，一部分存放结点值，另一部分存放结点所占单元数  
答案：A

（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ） 。  
A．必须是连续的  
B．部分地址必须是连续的  
C．一定是不连续的  
D．连续或不连续都可以  
答案：D

（6）线性表Ｌ在（ ）情况下适用于使用链式结构实现。  
A．需经常修改Ｌ中的结点值  
B．需不断对Ｌ进行删除插入  
C．Ｌ中含有大量的结点  
Ｄ．Ｌ中结点结构复杂  
答案：B  
解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。

（7）单链表的存储密度（ ） 。  
A．大于 1 B．等于1 C．小于1 D．不能确定  
答案：C  
解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之 比，假设单链表一个结点本身所占的空间为 D，指针域所占的空间为 N，则存储密度为： D/(D+N)，一定小于1

（8）将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（ ） 。  
A．n B．2n-1 C．2n D．n-1  
答案：A  
解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需要用 第二个表中的第一个元素依次与第一个表的元素比较，总计比较n 次

（9）在一个长度为 n 的顺序表中，在第i 个元素（1≤ i≤ n+1）之前插入一个新元素时须向 后移动（ ）个元素。  
A．n-i B．n-i+1 C．n-i-1 D．I  
答案：B

(10) 线性表L=(a1，a2,……an)，下列说法正确的是（ ）。  
A．每个元素都有一个直接前驱和一个直接后继  
B．线性表中至少有一个元素  
C．表中诸元素的排列必须是由小到大或由大到小  
D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。  
答案：D

(11) 创建一个包括n 个结点的有序单链表的时间复杂度是（ ） 。  
A．O(1) B．O(n) C．O(n^2) D．O(nlog2n)  
答案：C  
解释：单链表创建的时间复杂度是O(n)，而要建立一个有序的单链表，则每生成一个 新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O(n^2)

(12) 以下说法错误的是（ ） 。  
A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时 实现的效率低  
B．顺序存储的线性表可以随机存取  
C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活  
D．线性表的链式存储结构优于顺序存储结构  
答案：D  
解释：链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。  
【随机存取、顺序存取、随机存储、顺序存储】真是太容易混了。。。参考[这篇][Link 1]  
1、存取结构：分为随机存取和非随机存取（又称顺序存取）  
（1）、顺序存取：单链表，不能通过下标访问了，只能按照存储顺序存取，与存储位置有关，例如链表  
（2）、随机存取：顺序表，可以通过下标直接访问的那种数据结构，与存储位置无关，例如数组  
2、存储结构：分为顺序存储结构和随机存储结构  
（1）、顺序存储结构：顺序表  
（2）、随机存储结构：单链表

(13) 在单链表中，要将 s所指结点插入到 p 所指结点之后，其语句应为（ ）。  
A．s->next=p+1; p->next=s;  
B．(\*p).next=s; (\*s).next=(\*p).next;  
C．s->next=p->next; p->next=s->next;  
D．s->next=p->next; p->next=s;  
答案：D

(14) 在双向链表存储结构中，删除p 所指的结点时须修改指针（ ）。  
A．p->next->prior=p->prior; p->prior->next=p->next;  
B．p->next=p->next->next; p->next->prior=p;  
C．p->prior->next=p; p->prior=p->prior->prior;  
D．p->prior=p->next->next; p->next=p->prior->prior;  
答案：A

(15) 在双向循环链表中，在 p 指针所指的结点后插入 q 所指向的新结点，其修改指针的操 作是（ ） 。  
A．p->next=q; q->prior=p; p->next->prior=q; q->next=q;  
B．p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;  
C．q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;  
D．q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;  
答案：C

## 2、算法设计题 ##

(1)将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表 的存储空间，不另外占用其他的存储空间。表中不允许有重复的数据

//18、有序单链表并集_递增 空间O(1)
    void MergeOrderList(LinkList &LA, LinkList &LB, LinkList &LC)
    {
        //已知单链表LA和LB的元素按值递增排列
     //归并LA和LB得到新的单链表LC，LC的元素也按值递增排列，不允许有重复
        LC = new LNode;                 
        LC = LA;                        //用LA的头结点作为LC的头结点
        LNode *pa = LA->next;           //指针pa和pb的初值分别指向两个表的首元结点
        LNode *pb = LB->next;
        LNode *pc = LC;                 //指针pc的初值指向LC的头结点
        LNode *q;
        while(pa && pb)                 //LA和LB均未到达表尾
        {
        
            if(pa->data > pb->data)     //“摘取”两表中值较小的结点插入到LC的最后
            {
        
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }
            else if(pa->data < pb->data)     
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next;
            }
            else                        //当两表值相等时，将pa的插入到LC的最后，pb的删除                
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next;
                q = pb;
                pb = pb->next;
                delete q;
            }
        }
        pc->next = pa ? pa : pb;        //将非空表的剩余端插入到所指结点之后
        delete LB;                      //释放LB的头结点
    }

(2)将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个 链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。

//18、有序单链表并集_非递增 空间O(1)
    void MergeOrderList(LinkList &LA, LinkList &LB, LinkList &LC)
    {
        //已知单链表LA和LB的元素按值非递增排列
     //归并LA和LB得到新的单链表LC，LC的元素也按值非递增排列，允许有重复
        LC = new LNode;                 
        LC = LA;                        //用LA的头结点作为LC的头结点
        LNode *pa = LA->next;           //指针pa和pb的初值分别指向两个表的首元结点
        LNode *pb = LB->next;
        LNode *pc = LC;                 //指针pc的初值指向LC的头结点
        while(pa && pb)                 //LA和LB均未到达表尾
        {
        
            if(pa->data > pb->data)     //“摘取”两表中值较大的结点插入到LC的最后
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next;
            }
            else
            {
        
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }
        }
        pc->next = pa ? pa: pb;         //将非空表的剩余端插入到所指结点之后
        delete LB;                      //释放LB的头结点
    }

(3)已知两个链表A和B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出 A与B的交集，并存放在A链表中。

//19、有序单链表交集_递增
    void MixOrderList(LinkList &LA, LinkList &LB, LinkList &LC)
    {
        //已知单链表LA和LB的元素按值递增排列
     //归并LA和LB得到新的单链表LC，LC的元素也按值递增排列
        LC = new LNode;
        LC = LA;
        LNode *pa = LA->next;
        LNode *pb = LB->next;
        LNode *pc = LC;
        LNode *q;
        while(pa && pb)
        {
        
            if(pa->data > pb->data)
            {
        
                q = pb;
                pb = pb->next;
                delete q;
            }
            else if(pa->data < pb->data)
            {
        
                q = pa;
                pa = pa->next;
                delete q;
            }
            else
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next;
                q = pb;
                pb = pb->next;
                delete q;
            } 
        }
        while(pa)
        {
        
            q = pa;
            pa = pa->next;
            delete q;
        }
        while(pb)
        {
        
            q = pb;
            pb = pb->next;
            delete q;
        }
        pc->next = NULL;
        delete LB;
    }

(4)巳知两个链表 A和 B分别表示两个集合，其元素递增排列。请设计算法 求出两个集合 A 和B的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储， 同时返回该集合的元素个数。

//20、有序单链表差集_递增
    void DifferOrderList(LinkList &LA, LinkList LB, LinkList &C, int &m)
    {
        //将LA中存在且LB中不存在的元素存放在LA中，同时返回该集合的元素个数
        m = 0;
        LC = new LNode;
        LC = LA;
        LNode *pa = LA->next;
        LNode *pb = LB->next;
        LNode *pc = LC;
        LNode *q;
        while(pa && pb)
        {
        
            if(pa->data > pb->data)         //LA的大于LB的，LB向后移
                pb = pb->next;
            else if(pa->data < pb->data)    //LA，小于LB的，添加到LC
            {
        
                pc = pa;
                pa = pa->next;
                m++;
            }
            else                            //若相同，删除LA中的结点
            {
        
                pc->next = pa->next;
                q = pa;
                pa = pa->next;
                delete q;
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/2c0faf6e25e6464489b0c117a1f0524a.png
[Link 1]: https://www.cnblogs.com/hi3254014978/p/9929955.html