《2022年DS第二章课后习题答案 .pdf》由会员分享，可在线阅读，更多相关《2022年DS第二章课后习题答案 .pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章线性表2.1 填空题(1)一半插入或删除的位置(2)静态动态(3)一定不一定(4)头指针头结点的next 前一个元素的next 2.2 选择题(1)A (2) DA GKHDA EL IAF IFA(IDA) (3)D (4)D (5) D 2.3 头指针： 在带头结点的链表中，头指针存储头结点的地址；在不带头结点的链表中，头指针存放第一个元素结点的地址；头结点： 为了操作方便， 在第一个元素结点前申请一个结点，其指针域存放第一个元素结点的地址，数据域可以什么都不放；首元素结点：第一个元素的结点。2.4 已知顺序表L 递增有序，写一算法，将X 插入到线性表的适当位置上，以保持线性表的有序
2、性。void InserList(SeqList *L,ElemType x) int i=L-last; if(L-last=MAXSIZE-1) return FALSE; /顺序表已满while(i=0 & L-elemix) L-elemi+1=L-elemi; i-; L-elemi+1=x; L-last+; 2.5 删除顺序表中从i 开始的 k 个元素int DelList(SeqList *L,int i,int k) int j,l; if(iL-last) printf(The Initial Position is Error!); return 0; if(k=L-la
3、st) L-last=L-last-k; /*modify the length*/ 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 10 页 - - - - - - - - - - for(j=i-1,l=i+k-1;llast;j+,l+) L-elemj=L-eleml; L-last=L-last-k; return 1; 2.6 已知长度为n 的线性表A 采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为 O(1)的算法，删除线性表中所有值为item 的数据元素。算法 1 v
4、oid DeleteItem(SeqList *L,ElemType item) int i=0,j=L-last; while(ij) while(ielemi!=item) i+; while(ielemi=item) j-; if(ielemi=L-elemj; i+; j-; L-last=i-1; 算法 2 void DeleteItem (SeqList *L,ElemType e) int i,j; i=j=0; while(L-elemi!=e & ilast) i+; j=i+1; while(jlast) while(L-elemj=e & jlast) j+; if(jl
5、ast) L-elemi=L-elemj; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 10 页 - - - - - - - - - - i+; j+; L-last=i-1; 2.7 编写算法，在一非递减的顺序表L 中，删除所有值相等的多余元素。要求时间复杂度为O(n)，空间复杂度为O(1)。void DeleteRepeatItem(SeqList *L) int i=0,j=1; while(jlast) if(L-elemi=L-elemj) j+; else L-elemi+1=
6、L-elemj; i+; j+; L-last=i; 2.8 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink 且小于 maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度。void DelData(LinkList L,ElemType mink,ElemType maxk) Node *p=L-next,*pre=L; while(!p & p-data next; while(p) if(p-data maxk) break; else 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下
7、载 名师归纳 - - - - - - - - - -第 3 页，共 10 页 - - - - - - - - - - pre-next=p-next; free(p); p=pre-next; T(n)=O(n); 2.9 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2., an）逆置为（ an, an-1,., a1） 。（1） 以一维数组作存储结构。（2） 以单链表作存储结构。(略) (1) void ReverseArray(ElemType a,int n) int i=0,j=n-1; ElemType t; while(inext; L-n
8、ext=NULL; while(p!=NULL) q=p-next; p-next=L-next; L-next=p; p=q; 2.10 已知一个带有表头结点的单链表, 假设链表只给出了头指针L。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的data 域的值，并返回1；否则，至返回0。 （提示：设置两个指针，步长为k）int SearchNode(LinkList L,int k) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - -
9、- -第 4 页，共 10 页 - - - - - - - - - - Node *p=L,*q; int i=0; while(inext; if(p=NULL) return 0; /不存在倒数第k 个元素q=L-next; while(p-next!=NULL) /p到终点时， q 所指结点为倒数第k 个q=q-next; p=p-next; printf(%d,q-data); return 1; 2.11 把元素递增排列的链表A 和 B 合并为 C,且 C 中元素递减排列,使用原空间。 （头插法）LinkList ReverseMerge(LinkList *A, LinkList
10、*B) LinkList C; Node *pa=A-next,*pb=B-next; /pa和 pb 分别指向A,B 的当前元素A-next=NULL; C=A; while(pa!=NULL & pb!=NULL) if(pa-data data) /*将 pa 的元素前插到pc 表 */ temp=pa-next; pa-next=C-next; C-next=pa; pa=temp; else temp=pb-next; pb-next=C-next; C-next=pb; pb=temp; /*将 pb 的元素前插到pc 表*/ while(pb!=NULL) temp=pa-nex
11、t; pa-next=C-next; C-next=pa; pa=temp; /*将剩余 pa 的元素前插到pc表*/ while(pb!=NULL) temp=pb-next; pb-next=C-next; C-next=pb; pb=temp; /*将剩余 pb 的元素前插到pc表*/ return hc; 2.12 一单链表， 以第一个元素为基准，将小于该元素的结点全部放到前面，大于该结点的元素全部放到后面。时间复杂度要求为O(n) ，不能申请新空间。void AdjustList(LinkList L) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎
12、下载 名师归纳 - - - - - - - - - -第 5 页，共 10 页 - - - - - - - - - - Node *pFlag=L-next,*q=L-next-next,*temp=NULL; pflag-next=NULL; while(q!=NULL) if(q-data data) /插到链表首端 temp=q-next; q-next=L-next; L-next=q; q=temp; Else /插到 pFlag 结点后面 temp=q-next; q-next=pFlag-next; pFlag-next=q; q=temp; 2.13 假设有一个循环链表的长度大
13、于1，且表中既无头结点也无头指针。已知s 为指向链表某个结点的指针，试编写算法在链表中删除指针s 所指结点的前驱结点。void DelPreNode(Node* s) Node* p=s; while(p-next-next!=s) p=p-next; free(p-next); p-next=s; 2.14 已知由单链表表示的线性表中含有三类字符的数据元素（如字母字符、 数字字符和其他字符） ，试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。/L 为待拆分链表/Lch 为拆分后的字母链；Lnum 为拆分后
14、的数字链，Loth 为拆分后的其他字符链/Lch,Lnum,Loth均已被初始化为带头结点的单循环链表，采用头插法void splitLinkList(LinkList L,LinkList Lch,LinkList Lnum,LinkList Loth) Node *p=L-next; while(p!=NULL) if( (p-data =a & p-datadata = A & p-datanext; p-next=Lch-next; Lch-next=p; p= temp; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - -
15、- - - - - -第 6 页，共 10 页 - - - - - - - - - - else if(p-data =0 & p-datanext; p-next=Lnum-next; Lnum-next=p; p= temp; else temp=p-next; p-next=Loth-next; Loth-next=p; p= temp; 2.15 设线性表 A=(a1, a2,am)，B=(b1, b2, ,bn)，试写一个按下列规则合并A、B 为线性表C的算法，使得：C= (a1, b1,am, bm, bm+1,bn)当 m n 时；或者C= (a1, b1,an, bn, an+
16、1,am) 当 mn 时。线性表 A、 B、C均以单链表作为存储结构，且 C表利用 A表和 B表中的结点空间构成。注意：单链表的长度值m和 n 均未显式存储。/将 A 和 B 合并为 C,C 已经被初始化为空单链表void MergeLinkList(LinkList A,LinkList B,LinkList C) Node *pa=A-next ，*pb=B-next,*pc=C; int tag=1; while(pa & pb) if(tag) pc-next=pa-next; pc=pc-next; pa=pa-next; tag=1; else pc-next=pb-next; p
17、c=pc-next; pb=pb-next; tag=0; if(pa) pc-next=pa-next; else pc-next=pb-next; s 2.16 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。/A 为循环单链表，表示某多项式；将A 拆分为 B 和 C /其中 B 只含奇次项， C 只含偶次项；奇偶按照幂次区分/B,C 均已被初始化为带头结点的单链表void SplitPolyList(PolyList A,PolyList B,PolyList C) PolyNode *pa=A-ne
18、xt,*rb=B,*rc=C; while(pa) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 10 页 - - - - - - - - - - if(pa-exp%2=0) /偶次项rc-next=pa-next; rc=rc-next; pa=pa-next; else /奇次项rb-next=pa-next; rb=rb-next; pa=pa-next; rb-next=NULL; rc-next=NULL; 2.17 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个
19、结点的data 域存放一个二进制位。并在此链表上实现对二进制数加1 的运算。void BinAdd(LinkList l) /*用带头结点的单链表L 存储二进制数，实现加1 运算 */ Node *q,*r, *s; q=l-next; r=l; while(q!=NULL) /*查找最后一个值域为0的结点 */ if(q-data = 0) r = q; q = q-next; if (r != l) r-data = 1; /*将最后一个值域为0 的结点的值域赋为1*/ else /*未找到值域为0 的结点 */ s=(Node*)malloc(sizeof(Node); /*申请新结点存
20、放最高进位*/ s-data=1; /*值域赋为1*/ s-next=L-next; L-next = s; /*插入到头结点之后*/ r = s; r = r-next; while(r!=NULL) /*将后面的所有结点的值域赋为0*/ r-data = 0; r = r-next; 2.18 多 项 式 P(x) 采用书中所述链接方法存储。写一算法，对给定的x 值，求 P(x) 的值。double Compute(PolyList PL,double x) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - -
21、-第 8 页，共 10 页 - - - - - - - - - - double sum=0; PolyNode *p=PL-next; while(p) sum=sum+p-coef*pow(x,p-exp); p=p-next; return sum; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 10 页 - - - - - - - - - - 文档编码：KDHSIBDSUFVBSUDHSIDHSIBF-SDSD587FCDCVDCJUH 欢迎下载 精美文档欢迎下载 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 10 页 - - - - - - - - - -