数据结构线性表课后答案.docx

《数据结构线性表课后答案.docx》由会员分享，可在线阅读，更多相关《数据结构线性表课后答案.docx（9页珍藏版）》请在优知文库上搜索。

1、第2章线性表1.选择题（1）顺序表 中第一个元素的存储地址是100,每一个元素的 长度为2,则第5个 元素的地址是（）。A. 110B . 108 C. 100D . 120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。（2）在n个结点的顺序表中，算法的时间复杂度是O（I）的操作是（）。A.访问第i个结点（in）和求第i个结点的直接前驱（2inext=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-nex

2、t; 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

3、-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-net=q; p-next-prior=q; 答案：C.算法设计题(D将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来 两个链表的存储空间不此外占用其它的存储空间。表中不允许有重复的数据。题目分析合并后的新表使用头指针 指向， 和 分别是链表 和

4、的工作指针初始 化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 和 均为到 达表尾结点时，挨次摘取其中较小者重新链接在 表的最后。如果两个表中的元素相等， 只摘取 表中的元素，删除 表中的元素，这样确保合并后表中无重复的元素。当一 个表到达表尾结点，为空时，将非空表的剩余元素直接链接在 表的最后。算法描述合并链表 和 ，合并后的新表使用头指针 指向和 分别是链表 和 的工作指针初始化为相应链表的第一个结点 用 的头结点作为的头结点取较小者 中的元素，将 链接在 的后面，指针后移取较小者 中的元素，将 链接在 的后面， 指针后移相等时取 中的元素，删除 中的元素插入剩余段释放的头

5、结点(2)将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用 原来两个链表的存储空间不此外占用其它的存储空间。表中允许有重复的数据。题目分析合并后的新表使用头指针 指向， 和 分别是链表 和 的工作指针初始 化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 和 均为到 达表尾结点时，挨次摘取其中较小者重新链接在 表的表头结点之后，如果两个表中的 元素相等，只摘取 表中的元素，保留 表中的元素。当一个表到达表尾结点，为空 时，将非空表的剩余元素挨次摘取，链接在 表的表头结点之后。算法描述合并链表 和 ，合并后的新表使用头指针 指向和 分别是链表 和 的工作指针初始

6、化为相应链表的第一个结点用 的头结点作为 的头结点只要存在一个非空表，用指向待摘取的元素表为空，用指向表为空，用指向指针后移指针后移取较小者(包括相等)中的元素，用指向指针后移取较小者 中的元素，用 指向指针后移将指向的结点插在表的表头结点之后释放的头结点(3)已知两个链表 和 分别表示两个集合，其元素递增罗列。请设计算法求出 与 的交集，并存放于 链表中。题目分析惟独同时浮现在两集合中的元素才浮现在结果表中合并后的新表使用头指针 指 向。 a和 分别是链表a和的工作指针初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 a和均为到达表尾结点时，如果两个表中相等的元素时，摘取

7、a表中的元素，删除 表中的元素；如果其中一个表中的元素较小时， 删除此表中较小的元素，此表的工作指针后移。当链表 a和有一个到达表尾结点，为空时，挨次删除另一个非空表中的所有元素。算法描述d x( LinkList ankListnkLista= La next; pb= next;a和 分别是链表a和的工作指针初始化为相应链表的第个结点= pc= a用；a的头结点作为 的头结点 le( pa& & pb)a data=d=ata) 交集并入结果表中。 next= pa; pc= pa; pa= pa next;u= pb; pb= next; delete u; elsea datadata

8、) u=pa; pa=pa next; delete u;)else u= pb; =next; delete u; )Ie(Pa) u= pa;a=pa nextu; ; (Ie 蜂e放结点空间Ie(pb)u=pb;=ne;x t ；释(10放Ie结te点U空间next=null; 置链表尾标记。delete ;释放 的头结点 (4)已知两个链表和分别表示两个集合，其元素递增罗列。请设计算法求出两 个集合 和 的差集(即仅由在 中浮现而不在 中浮现的元素所构成的集合)，并以 同样的形式存储，同时返回该集合的元素个数。题目分析求两个集合 和 的差集是指在 中删除 和 中共有的元素，即删除链表中

9、的相 应结点所以要保存待删除结点的前驱，使用指针指e向前驱结点。a和分别是链表 a和的工作指针初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表a和均为到达表尾结点时，如果a表中的元素小于表中的元素，e置为a表的工作指针a删除 表中的元素；如果其中一个表中的元素较小时，删除此 表中较小的元素，此表的工作指针后移。当链表 a和 有一个为空时，挨次删除另一个非空表中的所有元素。算法描述Oider (eLn ne List L LinkList ) Lb, int n差集的结果存储于单链表L中，n是结果集合中元素个数，调用时为pa= L next; pb=L next;P和P分别是链

10、表L和L的工作指针初始化为相应链表的第一个结点pre= La;/7pre为L中P所指结点的前驱结点的指针(pe )p(p dat) d Prte=Pa; Pa=Pnext; *n+ ; 链表中当前结点指针后移else ( p data ) d =t next; /链表中当前结点指针后移else pre next=p next; 处理， 中元素值相同的结点，应删除-pa; pa=p next; delete ；删除结点(5)设计算法将一个带头结点的单链表 其中表的结点为表中值小于零的结点，而表中的元素为非零整数，要求表利用分解为两个具有相同结构的链表、， 表的结点为表中值大于零的结点(链表的结点)。题目分析表的头结点使用原来表的头结点，为 结点开始，挨次取其每一个结点P，判断结点 P表新申请一个头结点。从表的第一个