《第2章 线性表及其应用》习题解答(7)

第2章 线性表及其应用

SubPoly(p3,p1); cout<<\ DispPoly(p3); /////p4<=p*p1///////// p4=MulPoly(p,p1); cout<<\ DispPoly(p4); }

程序运行结果为：

create p:

输入多项式的系数和相应的指数(expn=-1结束):

2 1 5 8 -3.1 11 0 0

P=+2X^1+5X^8-3.1X^11 create p1:

输入多项式的系数和相应的指数(expn =-1结束): 7 0 -5 8 11 9 0 0

P=+7X^0-5X^8+11X^9 p2=p+p1:

P=+7X^0+2X^1+11X^9-3.1X^11 p3=p-p1:

P=-7X^0+2X^1+10X^8-11X^9-3.1X^11 p4=p*p1:

P=+14X^1+35X^8-10X^9+22X^10-21.7X^11-25X^16+55X^17+15.5X^19-34.1X^20

2.7 习 题

一、简答题

1．分别从线性表的存储密度、访问操作、修改和删除操作，这三个方面讨论其顺序存储和链式存储各有哪些优缺点？

2．描述链表中，头结点、头指针、首元结点（第一个元素结点）三个概念的区别。 3．简述在单链表中设置头结点的作用（至少说出两条好处）。

4．在单链表、单循环链表、双链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除掉？若可以，其时间复杂度各是多少？ 5．画出执行下列各语句后各指针及链表的示意图。

L=new LNode; P=L; for(i=1;i<=4;i++)

{P->next=new LNode;P=P->next;P->data=i*2-1;} P->next=NULL;

for(i=4;i>=1;i--)Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++)Del_LinkList(L,i); 6．间述以下算法的功能。

int Func(LinkList &L)

{ //L是无表头结点的单链表 if(L&&L->next){

Q=L; L=L->next;P=L; while(P->next)P=P->next;

P->next=Q; Q->next=NULL;return(1); }

else return(0); } 二、填空题

1．对于线性表的两种基本存储结构，如果表中元素的总数基本稳定，并且很少进行插入和删除操作，但是要求以最快的速度提取或修改线性表中的元素，应该选用（ ）存储

-.43.-

《数据结构与算法》

结构。

2．在长度为n的顺序表中插入或删除一个元素，分别需要平均移动（ ）个元素，执行以上操作时，移动元素的具体个数与（ ）有关。

3．顺序表中逻辑上相邻的数据元素的物理位置（ ）紧相邻。单链表中逻辑上相邻的数据元素的物理位置（ ）紧相邻。

4．如果系统语言不支持指针类型的变量，并且在元素总数变化不大的情况下，要求以最快的速度对线性表执行插入和删除操作，那么线性表应该选用（ ）存储结构。 5．已知L是带头结点的非空单链表，且P结点既不是首元结点也不是尾元结点，试从下面提供的答案中选择合适的语句序列。

a.删除P结点的直接后继结点的语句序列是（ ）。 b.删除P结点的直接前驱结点的语句序列是（ ）。 c.删除P结点的语句序列是（ ）。 d.删除首元结点的语句序列是（ ）。 e.删除尾元结点的语句序列是（ ）。 ⑴ P=P->next; ⑵ P->next=P;

⑶ P->next=P->nexe->next; ⑷ P=P->next->next;

⑸ while(P!=NULL)P=P->next;

⑹ while(Q->next!=NULL){P=Q;Q=Q->next;} ⑺ while(P->next!=Q)P=P->next;

⑻ while(P->next->next!=Q)P=P->next; ⑼ while(P->next->next!=NULL)P=P->next; ⑽ Q=P;

⑾ Q=P->next; ⑿ P=L;

⒀ L=L->next; ⒁ delete Q; 三、解答题

1．编写一函数，在线性顺序表L中求出最大元素以及该元素在表中的位置（假设L中的元素不重复）。

2．编程实现，逆置顺序表L中的所有元素（假设L中的元素为整数），并求出所用算法中基本操作的频度。

3．编程实现，将一个顺序表A（假设A中的元素为整数）分拆成两个顺序表B、C，使A中大于等于0的元素存放到B中，小于0的元素存放到C中。

4．编写一函数，将两个递增有序的顺序表A和B归并成一个顺序表C，要求C是按元素值不减有序排列的（允许C中有相同值的元素）。

5．编程实现，求单链表L中的最大元素，并且删除该元素所在的结点。要求算法中基本操作的次数越少越好。

6．试编写一程序，将带有头结点的单循环链表逆置。

7．已知线性表A中的数据元素按照值非递减有序。编写一个算法，将元素e插入到线性表

-.44.-

第2章 线性表及其应用

A中适当位置并仍然保持A有序。试分别在顺序存储和链式存储两种方式下编写出实现该算法的程序。

8．在线性表L中可能有相同的元素。试设计一个算法删除表中所有多余的元素（相同元素仅保留第一个），使删除后表中的元素各不相同。分别在顺序存储和链式存储两种方式下编写出实现该算法的程序。

9．所谓约瑟夫（Josephu）问题是：设有n个人围成一圈并依次进行编号1，2，3，……，n。从某个位置i上的人开始报数，数到m的人出列。下一个人（第m+1个）又从1开始报数，再数到m的人又出列，依次重复下去，直到最后一个人出列为止。按照出列的先后可得一新的序列。试用循环链表作为存储结构，编出求解这一问题的程序。

10．在本章[例2.9]（1）的基础上，编出实现两个多项式Am(x)和Bn(x)相乘的程序。其中，每个多项式都用单链表表示。

2.8 上机实验

本章上机实验的主要目的在于帮助学生熟练掌握线性表的基本操作在两种存储结构上的实现，其中以各种链表的操作和应用为重点内容。

实验题目 约瑟夫(Joseph)环

【问题描述】

约瑟夫(Joseph)问题的一种描述是：编号为1,2,3,?,n的n个人按顺时针方向围坐一圈，每人有一个密码（正整数）。首先输入一个整数m，从第一个人开始报数1,2,3,?，报到m时停止报数。让报m的人出圈，显示输出该人的密码，并将该密码作为新的m值，从该位置顺时针方向上的下一个人开始重新从1开始报数，如此下去，直到所有人全部出圈为止。设计一个程序模拟该过程。 【基本要求】

（1）用顺序存储结构模拟约瑟夫问题，按照出圈的顺序依次输出每人的编号和密码； （2）利用单向循环链表存储结构模拟约瑟夫问题，依次输出每个出圈人的编号和密码； （3）用静态循环链表存储结构模拟约瑟夫问题，依次输出每个出圈人原来的编号和密码。 【测试数据】

m的初值为20，n=7，7个人的密码依次为：3,1,7,2,4,8,4，首先m的值为6，正确测试结果的编号序列为：6,1,4,7,2,3,5。 【实现提示】

程序运行后，首先要求用户输入人数n和报数上限的初始值m，然后依次读入n个人的密码。此题对于单向循环链表存储结构不需要“头结点”，并注意空表和非空表的判定。

第2章、部分习题参考答案

一、简答题

1．分别从线性表的存储密度、访问操作、插入（修改）和删除操作，这三个方面讨论其顺

-.45.-

《数据结构与算法》

序存储和链式存储各有哪些优缺点？

（1）存储密度：相对于顺序存储而言，链表中的一个结点比顺序表中的一个记录要多一个指针存储空间，所以通常情况下，链表的存储密度比顺序表的存储密度低。但是，如果顺序表的最大长度远大于实际的记录数时其存储密度将会大大降低。另一方面，顺序表要求较大的连续存储空间，这种分配方法会使系统空间中产生许多不可利用的空闲碎块，降低了空间资源的利用率。而链表中的结点在内存中不要求连续存放。

（2）访问操作：顺序表中的元素存储在一个连续的地址空间中，可以对表中的元素进行随机访问。由于链式存储结构的特点，不能随机访问链表中的每一个结点，只能从链表的头指针开始逐个向后访问。

（3）插入和删除操作：对顺序表进行插入或删除操作时，往往需要向后或向前移动大量元素，所以该操作的时间开销很大；而对于链表在进行插入或删除操作时，仅仅是简单的指针赋值运算即可完成。

2．描述链表中，头结点、头指针、首元结点（第一个元素结点）三个概念的区别。 （1）首元结点：是指链表中存储线性表中第一个数据元素的结点。

（2）头结点：在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素。

（3）头指针：头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 3．简述在单链表中设置头结点的作用（至少说出两条好处）。 在单链表中设置头结点的作用是：（1）可以统一表示空链表和非空链表；（2）对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。

4．在单链表、单循环链表、双链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除掉？若可以，其时间复杂度各是多少？

（1）在单链表中若仅知道指针p指向某结点，不知道头指针，则不能将结点p从相应的链表中删除掉。

（2）在有n个结点的单循环链表中，删除结点p的时间复杂度为O(n)。 （3）在有n个结点的双链表中，删除结点p的时间复杂度为O(1)。 5．画出执行下列各语句后各指针及链表的示意图。 （1）LinkList L=new LNode,p=L;

for(i=1;i<5;i++){ p->next=new LNode;p=p->next;p->data=i*2-1;} p->next=NULL; 运行结果为：

（2）在程序段(1)的基础上画出以下程序段运行结果的示意图。 for(i=4;i>0;i--)Ins_LinkList(L,i+1,i*2); 运行结果为：

（3）在程序段(2)的基础上画出以下程序段运行结果的示意图。 for(i=1;i<4;i++)Del_LinkList(L,i); 运行结果为：

-.46.-

第2章 线性表及其应用

6．间述以下算法的功能。

int Func(LinkList &L)

{ //L是无表头结点的单链表 if(L&&L->next){

Q=L; L=L->next;P=L; while(P->next)P=P->next;

P->next=Q; Q->next=NULL;return(1); }

else return(0); } 二、填空题

1．对于线性表的两种基本存储结构，如果表中元素的总数基本稳定，并且很少进行插入和删除操作，但是要求以最快的速度提取或修改线性表中的元素，应该选用（顺序）存储结构。 2．在长度为n的顺序表中插入或删除一个元素，分别需要平均移动（插入操作平均移动元素的次数为：n/2，删除操作平均移动元素的次数为：(n-1)/2）个元素，执行以上操作时，移动元素的具体个数与（具体位置）有关。

3．顺序表中逻辑上相邻的数据元素的物理位置（一定）紧相邻。单链表中逻辑上相邻的数据元素的物理位置（不一定）紧相邻。

4．如果系统语言不支持指针类型的变量，并且在元素总数变化不大的情况下，要求以最快的速度对线性表执行插入和删除操作，那么线性表应该选用（静态链表）存储结构。

5．已知L是带头结点的非空单链表，且P结点既不是首元结点也不是尾元结点，试从下面提供的答案中选择合适的语句序列。

a.删除P结点的直接后继结点的语句序列是（ ）。 b.删除P结点的直接前驱结点的语句序列是（ ）。 c.删除P结点的语句序列是（ ）。 d.删除首元结点的语句序列是（ ）。 e.删除尾元结点的语句序列是（ ）。 ⑴ P=P->next; ⑵ P->next=P;

⑶ P->next=P->nexe->next; ⑷ P=P->next->next;

⑸ while(P!=NULL)P=P->next;

⑹ while(Q->next!=NULL){P=Q;Q=Q->next;} ⑺ while(P->next!=Q)P=P->next;

⑻ while(P->next->next!=Q)P=P->next; ⑼ while(P->next->next!=NULL)P=P->next; ⑽ Q=P;

⑾ Q=P->next; ⑿ P=L;

-.47.-

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《第2章 线性表及其应用》习题解答(7)在线全文阅读。