严蔚敏数据结构题集C语言版答案.docx

《严蔚敏数据结构题集C语言版答案.docx》由会员分享，可在线阅读，更多相关《严蔚敏数据结构题集C语言版答案.docx（133页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、可以失败,不可以失志。可以失望,不可以绝望。只要眷恋奇迹,会得到奇迹的眷恋。 严蔚敏数据结构C语言版答案详解第1章绪论1 .!简述下列术语:数据数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型解:数据是对客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为个整体进行考虑和处理数据对象是性质相同的数据元素的集合是数据的个子集数据结构是相互之间存在种或多种特定关系的数据元素的集合存储结构是数据结构在计算机中的表示数据类型是个值的集合和定义在这个值集上的组操作的总称抽象数据类型是指个数学模型以及定义在该模型

2、上的组操作是对一般数据类型的扩展1. 2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别解:抽象数据类型包含一般数据类型的概念但含义比一般数据类型更广、更抽象一般数据类型由具体语言系统内部定义直接提供给编程者定义用户数据因此称它们为预定义数据类型抽象数据类型通常由编程者定义包括定义它所使用的数据和在这些数据上所进行的操作在定义抽象数据类型中的数据部分和操作部分时要求只定义到数据的逻辑结构和操作说明不考虑数据的存储结构和操作的具体实现这样抽象层次更高更能为其他用户提供良好的使用接口1.3 设有数据结构(DR)其中试按图论中图的画法惯例画出其逻辑结构图解:1.4 试仿照三元组的

3、抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其 分子、分母均为自然数且分母不为零的分数)解:ADT Complex 数据对象：D=r i I r i为实数 数据关系：R=基本操作:InitRationalNumber(&R s m)操作结果:构造个有理数R 其分子和分母分别为s和mDestroyRationalNumber(&R) 操作结果:销毁有理数RGet (R k &e)操作结果:用e返回有理数R的第k元的值 Put(&Rk e)操作结果:改变有理数R的第k元的值为e IsAscending(R)操作结果：若有理数R的两个元素按升序排列 则返回1 否则返回IsDescen

4、ding(R)操作结果:若有理数R的两个元素按降序排列 则返回1 否则返回Max (R &e)操作结果:用e返回有理数R的两个元素中值较大的个 Min(R&e)操作结果：用e返回有理数R的两个元素中值较小的个 ADT RationalNumber1.5 试画出与下列程序段等价的框图(1) product=l; i=l;while (i=n)product *- i;i+;)(2) i=0;do i+; while(i!=n) & (ai!=x);(3) switch case xy: z=y-x; break;case x=y: z=abs(x*y); break;default: z=(x-

5、y)/abs(x)*abs(y);)1.6 在程序设计中常用下列三种不同的出错处理方式:(1)用exit语句终止执行并报告错误;(2)以函数的返回值区别正确返回或错误返回;(3)设置个整型变量的函数参数以区别正确返回或某种错误返回试讨论这三种方法各自的优缺点解:(l)exit常用于异常错误处理它可以强行中断程序的执行返回操作系统(2)以函数的返回值判断正确与否常用于子程序的测试便于实现程序的局部控制(3)用整型函数进行错误处理的优点是可以给出错误类型便于迅速确定错误1.7 在程序设计中可采用下列三种方法实现输出和输入：(1)通过scanf和printf语句:(2)通过函数的参数显式传递;(3)

6、通过全局变量隐式传递试讨论这三种方法的优缺点解:(1)用scanf和printf直接进行输入输出的好处是形象、直观 但缺点是需要对其进行格式控制较为烦琐如果出现错误则会引起整个系统的崩溃(2)通过函数的参数传递进行输入输出便于实现信息的隐蔽 减少出错的可能(3)通过全局变量的隐式传递进行输入输出最为方便 只需修改变量的值即可但过多的全局变量使程序的维护较为困难1.8 设n为正整数试确定下列各程序段中前置以记号的语句的频度:(1) i=l; k=0;while(i=n-l) k += 10*i： i+;)(2) i=l; k=0;do k += 10*i; i+； while(i=n-l);(3

7、) i=l; k=0;while (i=n-l) i+； k += 10*i;)(4) k=0;for(i=l; i=n; i+) for(j=i; j=n; j+) k+;)(5) for(i=l; i=n; i+) for(j=l; j=i; j+) for(k=l; k=j; k+) x += delta;)(6) i=l： j=0;while(i+jj) j+; else i+;(7) x=n; y=0;/ n是不小于1的常数while(x=(y+l)*(y+l) y+;(8) x=91; y=100;while(y0) if(x100) x -= 10; y; else x+;)解:

8、(1) n-1(2) n-1n-1(4) n+(nT) + (n-2)+.+1=(5) 1+(1+2) + (1+2+3)+. +(1+2+3+. +n)-(6) n(7)向下取整(8) 11001.9假设n为2的乘累并且n2试求下列算法的时间复杂度及变量count的值(以n的函数形式表示)int Time(int n) count = 0; x=2;while(x438时1. 14判断下列各对函数和 当时哪个函数增长更快?(1)(2)(3)(4)解:(l)g(n)快(2)g(n)快(3)f(n)快(4) f(n)快 1.15试用数学归纳法证明：(1)(2)(3)(4)1.16 试写算法自大至

9、小依次输出顺序读入的三个整数X丫和Z的值解：int max3(int xint yint z)(if(xy)if(xz) return x;else return z;elseif(yz) return y;else return z;1.17 一知k阶斐波那契序列的定义为试编写求k阶斐波那契序列的第m项值的函数算法 k和m均以值调用的形式在函数参数表中出现解:k0为阶数n为数列的第n项int Fibonacci(int kint n)(if(kl) exit(OVERFLOW);int *px;p二new intk+1;if(!p) exit(OVERFLOW);int ij；for(i=0

10、;ik+l;i+)if(ik-l) pi=0;else pi=l;for(i=k+l;in+l;i+)x=p0;for(j=0;jk;j+) pj=pj+U;pk=2*pk-l-x;return p|_k;1.18 假设有ABCDE五个高等院校进行田径对抗赛 各院校的单项成绩均已存入计算机 并构成一张表 表中每一行的形式为 项目名称 性别 校名 成绩 得分 编写算法 处理上述表格以统计各院校的男、女总分和团体总分 并输出解: typedef enum(A BCDE SchoolName;typedef enumFemaleMale SexType; typedef struct char ev

11、ent 3; 项目 SexType sex;SchoolName school; int score; Component;typedef structint Mal eSum;男团总分int Ferna 1 eSum; 女团总分 int TotalSum; /团体总分 Sum;Sum SumScore(SchoolName sn Component a int n) Sum temp;temp. MaleSum=0;temp. FemaleSum=O;temp. TotalSum=0;int i;for(i=0;iarrsize或对某个使时应按出错处理注意选择你认为较好的出错处理方法解:#i

12、nclude#include#define MAXINT 65535#define ArrSize 100int fun(int i);int main()(int ik：int aArrSize;cout“Enter k:;cink;if(kArrSize-l) exit(0);for(i=0;iMAXINT) exit(0);else ai=2*i*ai-l;for(i=0;iMAXINT) exit(O); else coutai*)return 0;1.20试编写算法求一元多项式的值的值并确定算法中每语句的执行次数和整个算法的时间复杂度 注意选择你认为较好的输入和输出方法本题的输入为和

13、输出为解:#include#includedefine N 10double polynomail(int aint idouble xint n);int main() (double x;int ni；int aN;cout”输入变量的值x:;cinx;cout输入多项式的阶次n:;cinn;if(nN-l) exit(0);cout”输入多项式的系数a0an:;for (i=0; i=n; i+) cinai;coutThe polynomail value is polynomail (anxn)0) return an-i+polynomail(a i-1xn) *x;else re

14、turn an;本算法的时间复杂度为。(n)第2章线性表2.!描述以下三个概念的区别:头指针头结点首元结点(第一个元素结点)解:头指针是指向链表中第一个结点的指针首元结点是指链表中存储第一个数据元素的结点头结点是在首元结点之前附设的个结点该结点不存储数据元素其指针域指向首元结点其作用主要是为了方便对链表的操作它可以对空表、非空表以及首元结点的操作进行统处理2.2 填空题解：(1)在顺序表中插入或删除个元素需要平均移动表中一半元素具体移动的元素个数与元素在表中的位置有关(2)顺序表中逻辑上相邻的元素的物理位置必定紧邻单链表中逻辑上相邻的元素的物理位置不一定紧邻(3)在单链表中除了首元结点外任结点

15、的存储位置由其前驱结点的链域的值指示(4)在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理2.3 在什么情况下用顺序表比链表好?解：当线性表的数据元素在物理位置上是连续存储的时候用顺序表比用链表好其特点是可以进行随机存取2.4 对以下单链表分别执行下列各程序段并画出结果示意图解:2. 5画出执行下列各行语句后各指针及链表的示意图L=(LinkList)malloc(sizeof(LNode); P=L; for(i=l;inext=(LinkLi st)malloc(sizeof(LNode);P=P-next; P-data=i*2-l;)P-next=NULL;for(i=

16、4;i=l;i) Ins_LinkList(Li+1i*2);for(i=l;inext=S;(2) P-next=P-next-next;(3) P-next=S-next;(4) S-next=P-next：(5) S-next=L;(6) S-next=NULL;(7) Q=P;(8) while(P-next!=Q) P=P-next;(9) wh i1e(P-next!=NULL) P=P-next;(10) P=Q;(11) P=L;(12) L=S;(13) L=P;解:a. (4) (1)b. (7) (11) (8) (4) (1)c. (5) (12)d. (9) (1)

17、(6)2.7已知L是带表头结点的非空单链表且P结点既不是首元结点也不是尾元结点试从下列提供的答案中选择合适的语句序列a.删除P结点的直接后继结点的语句序列是b.删除P结点的直接前驱结点的语句序列是c,删除P结点的语句序列是d.删除首元结点的语句序列是e.删除尾元结点的语句序列是(1) P=P-next;(2) P-next=P;(3) P-next=P-next-next;(4) P=P-next-next;(5) wh i1e(P!=NULL) P=P-next;(6) while(Q-next!=NULL) P=Q; Q=Q-next; (7) while(P-next!=Q) P=P-n

18、ext;(8) while(P-next-next!=Q) P=P-next：(9) while(P-nextnext!=NULL) P=P-next;(10) Q=P；(11) Q=P-next;(12) P=L;(13) L=L-next;(14) free(Q);解:a. (11) (3) (14)b. (10)(12)(8)(3)(14)c. (10)(12)(7)(3)(14)d. (12)(11)(3)(14)e. (9)(11)(3)(14)2.8 一知P结点是某双向链表的中间结点 试从下列提供的答案中选择合适的语句序列a.在P结点后插入S结点的语句序列是b.在P结点前插入S结点

19、的语句序列是c.删除P结点的宜接后继结点的语句序列是d.删除P结点的直接前驱结点的语句序列是e,删除P结点的语句序列是(1) P-next=P-next-next;(2) P-priou=P-priou-priou;(3) P-next=S;(4) P-priou=S;(5) S-next=P;(6) S-priou=P;(7) S-next=P-next;(8) S-priou=P-priou;(9) P-priou-next=P-next;(10) P-pr i ou-next=P;(11) P-next-priou=P;(12) P-next-priou=S;(13) P-priou-n

20、ext=S;(14) P-next-priou=P-priou;(15) Q=P-next;(16) Q=P-priou;(17) free(P);(18) free(Q);解:a. (7) (3) (6) (12)b. (8) (4) (5) (13)c. (15) (1) (11) (18)d. (16) (2) (10) (18)e. (14) (9) (17)2.9 简述以下算法的功能(1) Status A(LinkedList L) L是无表头结点的单链表 if(L & L-next) Q=L;L=L-next; P=L;while(P-next) P=P-next; P-next

21、=Q; Q-next=NULL;) return OK; )(2) void BB(LNode *s LNode *q) p=s;while(p-next!=q) p=p-next; p-next =s;void AA(LNode *pa LNode *pb) /pa和pb分别指向单循环链表中的两个结点 BB(papb);BB(pb pa);)解:(1)如果L的长度不小于2 将L的首元结点变成尾元结点(2)将单循环链表拆成两个单循环链表2.10 指出以下算法中的错误和低效之处 并将它改写为个既正确又高效的算法Status DeleteK(SqList &a int i int k) (本过程从

22、顺序存储结构的线性表a中删除第i个元素起的k个元素 if (il | I ka. length) return INFEASIBLE;参数不合法 else for (count=l;count=i+l;j) a. elemj-i=a. elemj; a. length; return OK; 解:Status DeleteK(SqList &aint iint k)从顺序存储结构的线性表a中删除第i个元素起的k个元素注意i的编号从开始int j;if(ia. length-11 Ika. length-i) return INFEASIBLE;for(j=0;j0xB. length?A. l

23、ength:B. length;for(i=0;iB. elemi) j=l;if (A. elemik) j=l;if(B. lengthk) j=-l;if (A. length=B. length) j=0; return j;2.13试写算法在带头结点的单链表结构上实现线性表操作Located x);解:int LocateElem L(LinkList &LElemType x) (int i=0;LinkList p=L;while(p&p-data!=x) p=p-next;i+；)if(!p) return 0;else return i;2. 14试写一算法在带头结点的单链表

24、结构上实现线性表操作Length(L)解:返回单链表的长度int ListLength_L(LinkList &L) int i=0;LinkList p=L;if(p) p=p-next;while (p) p=p-next;i+；return i;2. 15已知指针ha和hb分别指向两个单链表的头结点 并且已知两个链表的长度分别为m和n 试写算法将这两个链表连接在起 假设指针he指向连接后的链表的头结点 并要求算法以尽可能短的时间完成连接运算 请分析你的算法的时间复杂度解:void MergeListL(LinkList &haLinkList &hbLinkList &hc) (Link

25、List pa pb;pa=ha;pb二hb;while (pa-next&pb-next) pa=pa-next; pb=pb-next;if(!pa-next) hc=hb; while(pb-next) pb=pb-next; pb-next=ha-next; else he=ha; while(pa-next) pa=pa-next; panext二hb-next; 2. 16已知指针la和lb分别指向两个无头结点单链表中的首元结点 下列算法是从表!a中删除自第i个元素起共len个元素后 将它们插入到表1b中第i个元素之前 试问此算法是否正确?若有错 请改正之Status Delete

26、AndlnsertSub(LinkedList la LinkedList lb int i int j int len)if(i0|Ij0|len0) return INFEASIBLE; p=la; k=l;while(ki) p=p-next; k+;q 二P； while (knext; k+;s=lb; k=l;while(knext; k+;s)next二p; q)next二s-next; return OK; 解:Status DeleteAndlnsertSub(LinkList &la LinkList &lb int i int j int len) (LinkList p

27、 q s prev=NULL;int k=l;if(i0|Ij0|len0) return INFEASIBLE; /在la表中査找第i个结点 p二la;while(p&knext; k+;)if(!p)return INFEASIBLE;/在!a表中查找第i+Ien-1个结点 q=p； k=l;while(q&knext; k+;if(!q)return INFEASIBLE;/完成删除 注意i=l的情况需要特殊处理 if(!prev) la=q-next; else prev-next=q-next;/将从la中删除的结点插入到1b中if(j-l) q-next=lb;lb=p;)else

28、 s=lb; k=l;while (s&knext;k+;if(!s)return INFEASIBLE;q-next=s-next;s-next=p; 完成插入)return OK;2.1?试写算法在无头结点的动态单链表上实现线性表操作Insert(L ib)并和在带头结点的动态单链表上实现相同操作的算法进行比较2. 18试写一算法实现线性表操作Deleted1)并和在带头结点的动态单链表上实现相同操作的算法进行比较2) 19已知线性表中的元素以值递增有序排列并以单链表作存储结构试写一高效的算法删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素) 同时释放被删结点空间并分析

29、你的算法的时间复杂度(注意mink和maxk是给定的两个参变量它们的值可以和表中的元素相同也可以不同)解:Status ListDelete_LdinkList &LElemType minkElemType maxk)LinkList p prev=NULL;if(minkmaxk)return ERROR;P=L;prev=p;p=p-next;while (p&p-datadatanext;else prevnext=p-next;q=P；p=p-next;free (q);)return OK;2. 20同2. 19题条件试写一高效的算法删除表中所有值相同的多余元素(使得操作后的线性表

30、中所有元素的值均不相同) 同时释放被删结点空间并分析你的算法的时间复杂度解:void ListDelete_LSameNode(LinkList &L) (LinkList pqprev;P二L；prev=p;p=pnext;while(p) prev=p;p=p_next;if(p&pdataprevdata) prev-next=p-next;q=P；p=p-next;free(q);2.21试写一算法 实现顺序表的就地逆置即利用原表的存储空间将线性表逆置为解:/Z顺序表的逆置Status ListOppose_Sq(SqList &L) int i;ElemType x;for(i=0;

31、inext;Lnext=NULL;while (p)q=P； p=p-next;q)next二L一next;L-next=q;)return OK;2. 23设线性表试写一个按下列规则合并AB为线性表C的算法 即使得当时;线性表AB和C均以单链表作存储结构且C表利用A表和B表中的结点空间构成注意:单链表的长度值m和n均未显式存储解:/将合并后的结果放在C表中 并删除B表Status ListMerge L(LinkList &ALinkList &BLinkList &C) LinkList pa pb qa qb；pa=A-next;pb=B-next;C=A;while (pa&pb)qa

32、=pa;qb=pb;pa=pa-next;pb=pDnext;qb-next=qa-next;qanext=qb;if(!pa)qb-next二pb;pb 二B;free(pb); return OK;2.24假设有两个按元素值递增有序排列的线性表A和B均以单链表作存储结构请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序 允许表中含有值相同的元素)排列的线性表C并要求利用原表(即A表和B表)的结点空间构造C表解:/将合并逆置后的结果放在C表中 并删除B表Status ListMergeOppose_L(LinkList &ALinkList &BLinkList &C)LinkL

33、ist pa pbqaqb;pa=A;pb 二B;qa=pa; /保存pa的前驱指针 qb=pb; /保存pb的前驱指针 pa=pa-next;pb=pb-next;A)next二NULL;C=A;while(pa&pb)if(pa-datapb-data)qa=pa;pa二pa-next;qanext二Anext;将当前最小结点插入A表表头A-next=qa;) else qb=pb;pb=pb-next;qb-next=A-next;将当前最小结点插入A表表头A-next=qb;while (pa) qa=pa; pa=panext; qa-next=A-next; A-next=qa;w

34、hile (pb) qb=pb; pb二pb-next; qb-next=A-next; A-next=qb;)pb=B;free (pb);return OK;2. 25假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元 素值各不相同)现要求另辟空间构成一个线性衣C其元素为A和B中元素的交集且表C中的元素有依值递增有序排列试对顺序表编写求C的算法解:/Z将A、B求交后的结果放在C表中Status ListCross Sq(SqList &ASqList &BSqList &C)int i=0j=0k=0;while(iA. length & jB. length) if (A. elemiB. elemj) j+; elseListInsert_Sq(CkA.elemi);i+； k+;return OK;2.26 要求同2.25题试对单链表编写求C的算法解:/Z将A、B求交后的结果放在C表中 并删除B表Status ListCross L(LinkList &ALinkList &BLinkList &C)(LinkList papbqaqb pt； pa=A;pb二B;qa=pa; /保存pa的前驱指针 qb=pb; /保存pb的前驱指针 pa=pa-next;pb=pb-next;C=A;while(pa&p