没有合适的资源?快使用搜索试试~ 我知道了~
第2章 线性表答案1
需积分: 0 0 下载量 148 浏览量
2022-08-08
18:31:59
上传
评论
收藏 72KB DOCX 举报
温馨提示
试读
35页
4.两种存储结构各有优缺点,应根据实际情况选用,不能笼统说哪一个好 7.集合中元素无逻辑关系 9.非空线性表第一个元素无前驱,最后一个元素无后继 6.O(1),
资源详情
资源评论
资源推荐
第 2 章 线性表
一.选择题
1.A
2.B
3.C
4.A
5.D
6.D
7.
D
8.C
9.B
10.B,
C
11.1
I
11.2
I
11.3
E
11.4
B
11.5
C
12.
B
13.
C
14.
C
15.
C
16.
A
17.
A
18.A
19.D
20.C
21.B
22.D
23.C
24.
B
25.
B
26.
A
27.
D
二.判断题
1. ×
2.√
3.
√
4.×
5.
×
6.
×
7.
×
8.
×
9.
×
10.
×
11.
×
12.
×
13.
×
14.
√
15.
×
16.
√
部分答案解释如下。
1、 头结点并不“仅起”标识作用,并且使操作统一。另外,头结点数据域可写入链表长度,
或作监视哨。
4.两种存储结构各有优缺点,应根据实际情况选用,不能笼统说哪一个好。
7.集合中元素无逻辑关系。
9.非空线性表第一个元素无前驱,最后一个元素无后继。
13.线性表是逻辑结构,可以顺序存储,也可链式存储。
三.填空题
1.顺序 2.(n-1)/2 3.py->next=px->next; px->next=py
4 .n-i+1
5.主要是使插入和删除等操作统一,在第一个元素之前插入元素和删除第一个结点不必
另作判断。另外,不论链表是否为空,链表指针不变。
6.O(1),O(n) 7.单链表,多重链表,(动态)链表,静态链表
8.f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;
9.p^.prior s^.prior^.next
10. 指针 11.物理上相邻 指针 12.4 2
13.从任一结点出发都可访问到链表中每一个元素。
14 . u=p->next; p->next=u->next; free(u); 15 . L->next->next==L
16.p->next!=null
17.L->next==L && L->prior==L 18.s->next=p->next;p->next=s;
19.(1) IF pa=NIL THEN return(true);
(2) pb<>NIL AND pa^.data>=pb^.data
(3) return(inclusion(pa,pb));
(4) pb:=pb^.next;
(5) return(false);
非递归算法:
(1)pre:=pb; (2) pa<>NIL AND pb<>NIL AND pb^.data>=pa^.data (3)pa:=pa^.next;
pb:=pb->next;
(4)pb:=pre^.next;pre:=pb;pa:=pa^.next;(5)IF pa=NIL THEN return(true) ELSE
return(false);
[注]:本题是在链表上求模式匹配问题。非递归算法中用指针 pre 指向主串中开始结点(初
始时为第一元素结点)。若主串与子串对应数据相等,两串工作指针 pa 和 pb 后移;否则,
主串工作指针从 pre 的下一结点开始(这时 pre 又指向新的开始结点),子串工作指针从子
串第一元素开始,比较一直继续到循环条件失败。若 pa 为空,则匹配成功,返回 true,否
则,返回 false。
20.A.VAR head:ptr B. new(p) C. p^.data:=k D. q^.next:=p E. q:=p(带头
结点)
21.(1)new(h);∥生成头结点,以便于操作。
(2)r^.next:=p; (3) r^.next:=q; (4) IF (q=NIL) THEN r^.next:=p;
22.A: r^.link^.data<>max AND q^.link^.data<>max
B: r:=r^.link C: q^.link D: q^.link E: r^.link F: r^.link
G: r:=s(或 r:= r^.link) H: r:=r^.link I: q^.link:=s^.link
23.(1)la (2)0 (3)j<i-1 (4)p↑.next (5)i<1
24.(1)head^.left:=s ∥head 的前驱指针指向插入结点
(2)j:=1;
(3)p:=p^.right ∥工作指针后移
(4)s^.left:=p
(5)p^.right^.left:=s; ∥p 后继的前驱是 s
(6)s^.left:=p;
25.(1)i<=L.last ∥L.last 为元素个数
(2)j:=j+1 ∥有值不相等的元素
(3)L.elem[j]:=L.elem[i] ∥元素前移
(4)L.last:=j ∥元素个数
26.(A)p^.link:=q;∥拉上链,前驱指向后继
(B)p:=q;∥新的前驱
(C)p^.link:=head;∥形成循环链表
(D)j:=0; ∥计数器,记被删结点
(E)q:=p^.link∥记下被删结点
(F)p^.link=q^.link ∥删除结点
27. (1)p:=r;∥r 指向工作指针 s 的前驱,p 指向最小值的前驱。
(2)q:=s;∥q 指向最小值结点,s 是工作指针
(3)s:=s^.link∥工作指针后移
(4)head:=head^.next;∥第一个结点值最小;
(5)p^link:=q^.link;∥跨过被删结点(即删除一结点)
28.(1) l^.key:=x;∥头结点 l 这时起监视哨作用
(2) l^.freq:=p^.freq ∥头结点起监视哨作用
(3) q->pre->next=q->next; q->next->pre=q->pre; ∥先将 q 结点从链表上摘
下
q^.next:=p; q^.pre:=p^.pre; p^.pre->next:=q; p^.pre:=q; ∥结点 q 插
入结点 p 前
(4) q^.freq=0 ∥链表中无值为 x 的结点,将新建结点插入到链表最后(头结点
前)。
29.(1)a^.key:=’@’∥a 的头结点用作监视哨,取不同于 a 链表中其它数据域的值
(2)b^.key:=p^.key∥b 的头结点起监视哨作用
(3)p:=p^.next∥找到 a,b 表中共同字母,a 表指针后移
(4)0(m*n)
30. C 部分:(1)p!=null ∥链表未到尾就一直作
(2)q ∥将当前结点作为头结点后的第一元素结点插入
31. (1)L=L->next; ∥暂存后继
(2)q=L; ∥待逆置结点
(3)L=p; ∥头指针仍为 L
32. (1) p^.next<>p
0
(2)r:= p^.next (3) p^.next:= q
0
;
(4) q
0
:= p; (5) p:=r
33. (1)r (2)NIL (3)x<head^.data (4)p^.data<x
(5)p:=p^.next (6)p^.data>=x; (7)r (8)p
(9)r (10)NIL (11)NIL
34.(1)pa!=ha ∥或 pa->exp!=-1
(2)pa->exp==0 ∥若指数为 0,即本项为常数项
(3)q->next=pa->next ∥删常数项
(4)q->next ∥取下一元素
(5)=pa->coef*pa->exp
(6)-- ∥指数项减 1
(7)pa ∥前驱后移,或 q->next
(8)pa->next ∥取下一元素
35.(1)q:=p; ∥q 是工作指针 p 的前驱
(2)p^.data>m ∥p 是工作指针
(3)r:=q; ∥r 记最大值的前驱,
(4)q:=p; ∥或 q:=q^.next;
(5)r^.next:=q^.next; ∥或 r^.next:=r^.next^.next 删最大值结点
36.(1)L->next=null ∥置空链表,然后将原链表结点逐个插入到有序表中
(2)p!=null ∥当链表尚未到尾,p 为工作指针
(3)q!=null ∥查 p 结点在链表中的插入位置,这时 q 是工作指针。
(4)p->next=r->next ∥将 p 结点链入链表中
(5)r->next=p ∥r 是 q 的前驱,u 是下个待插入结点的指针。
37.程序(a) PASCAL 部分(编者略)
程序(b) C 部分
(1)(A!=null && B!=null) ∥两均未空时循环
(2)A->element==B->element ∥两表中相等元素不作结果元素
(3)B=B->link ∥向后移动 B 表指针
(4)A!=null ∥将 A 表剩余部分放入结果表中
(5)last->link=null ∥置链表尾
四、应用题
1.(1)选链式存储结构。它可动态申请内存空间,不受表长度(即表中元素个数)的
影响,插入、删
除时间复杂度为 O(1)。
(2)选顺序存储结构。顺序表可以随机存取,时间复杂度为 O(1)。
2.链式存储结构一般说克服了顺序存储结构的三个弱点。首先,插入、删除不需移动
元素,只修改指针,时间复杂度为 O(1);其次,不需要预先分配空间,可根据需要动态申
请空间;其三,表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销,当空
间不允许时,就不能克服顺序存储的缺点。
3.采用链式存储结构,它根据实际需要申请内存空间,而当不需要时又可将不用结点
空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。
4.线性表 栈 队列 串 顺序存储结构和链式存储结构。
顺序存储结构的定义是:
CONST maxlen=线性表可能达到的最大长度;
TYPE sqlisttp=RECORD
elem:ARRAY[1..maxlen] OF ElemType;
last:0..maxlen;
END;
链式存储结构的定义是:
TYPE pointer=↑nodetype;
nodetype=RECORD
data:ElemType;
next:pointer;
END;
linklisttp=pointer;
5.顺序映射时,a
i
与 a
i+1
的物理位置相邻;链表表示时 a
i
与 a
i+1
的物理位置不要求相
邻。
6.在线性表的链式存储结构中,头指针指链表的指针,若链表有头结点则是链表的头
结点的指针,头指针具有标识作用,故常用头指针冠以链表的名字。头结点是为了操作的统
一、方便而设立的,放在第一元素结点之前,其数据域一般无意义(当然有些情况下也可存
放链表的长度、用做监视哨等等),有头结点后,对在第一元素结点前插入结点和删除第一
结点,其操作与对其它结点的操作统一了。而且无论链表是否为空,头指针均不为空。首元
结点也就是第一元素结点,它是头结点后边的第一个结点。
7.见上题 6。
8.(1)将 next 域变为两个域: pre 和 next,其值域均为 0..maxsize。初始化时,头结
点 ( 下 标 为 0 的 元 素 ) 其 next 域值为 1,其 pre 域值为 n ( 设 n 是 元 素 个 数 , 且
n<maxsize)
(2) stalist[stalist[p].pre].pre;
(3) stalist[p].next;
9. 在单链表中不能从当前结点(若当前结点不是第一结点)出发访问到任何一个结点,
链表只能从头指针开始,访问到链表中每个结点。在双链表中求前驱和后继都容易,从当前
结点向前到第一结点,向后到最后结点,可以访问到任何一个结点。
10.本题是链表的逆置问题。设该链表带头结点,将头结点摘下,并将其指针域置空。
然后从第一元素结点开始,直到最后一个结点为止,依次前插入头结点的后面,则实现了链
表的逆置。
11.该算法的功能是判断链表 L 是否是非递减有序,若是则返回“true”;否则返回“false
“。pre 指向当前结点,p 指向 pre 的后继。
12.q=p->next; p->next=q->next; free(q);
13. 设单链表的头结点的头指针为 head,且 pre=head;
while(pre->next!=p) pre=pre->next;
s->next=p; pre->next=s;
14.设单链表带头结点,工作指针 p 初始化为 p=H->next;
(1) while(p!=null && p->data!=X) p=p->next;
if(p= =null) return(null);∥查找失败
else return(p);∥查找成功
(2) while(p!=null && p->data<X ) p=p->next;
if(p==null || p->data>X) return(null);∥查找失败
else return(p);
(3) while(p!=null && p->data>X) p=p->next;
if(p==null || p->data<X) return(null); ∥查找失败
else return(p); ∥查找成功
15.本程序段功能是将 pa 和 pb 链表中的值相同的结点保留在 pa 链表中(pa 中与 pb 中不
同结点删除),pa 是结果链表的头指针。链表中结点值与从前逆序。S1 记结果链表中结点个
数(即 pa 与 pb 中相等的元素个数)。S2 记原 pa 链表中删除的结点个数。
16.设 q:=p^.llink; 则
q^.rlink:=p^.rlink; p^.rlink^.llink:=q; p^.llink:=q^.llink;
q^.llink^.rlink:=p; p^.rlink:=q; q^.llink:=p
17.(1)前两个语句改为:
p.llink^.rlink<- p^.rlink;
p^.rlink^.llink<- p^.llink;
(2)后三个语句序列应改为:
q^.rlink<- p^.rlink;∥以下三句的顺序不能变
p^.rlink^.llink<- q;
p^.rlink<- q;
18.mp 是一个过程,其内嵌套有过程 subp。
subp(s,q)的作用是构造从 s 到 q 的循环链表。
subp(pa,pb)调用结果是将 pa 到 pb 的前驱构造为循环链表。
subp(pb,pa)调用结果是将 pb 到 pa 的前驱(指在 L 链表中,并非刚构造的 pa 循环
链表中)构造为循环链表。
总之,两次调用将 L 循环链表分解为两个。第一个循环链表包含从 pa 到 pb 的前驱,L
中除刚构造的 pa 到 pb 前驱外的结点形成第二个循环链表。
19.在指针 p 所指结点前插入结点 s 的语句如下:
s->pre=p->pre; s->next=p; p->pre->next=s; p->pre=s;
20.(A) f1<>NIL 并且 f2<>NIL
(B) f1↑.data < f2↑.data
(C) f2↑.data<f1↑.data
(D) f3↑.data<f1↑.data
(E) f1<- f1↑.link 或 f2=f2↑.link;
21. 1)本算法功能是将双向循环链表结点的数据域按值自小到大排序,成为非递减(可
能包括数据域值相等的结点)有序双向循环链表。
2)(1)r->prior=q->prior;∥将 q 结点摘下,以便插入到适当位置。
(2)p->next->prior=q;∥(2)(3)将 q 结点插入
(3)p->next=q;
剩余34页未读,继续阅读
呆呆美要暴富
- 粉丝: 34
- 资源: 339
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0