《数据结构与算法》课后习题答案(29页).doc
《《数据结构与算法》课后习题答案(29页).doc》由会员分享,可在线阅读,更多相关《《数据结构与算法》课后习题答案(29页).doc(29页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、-数据结构与算法课后习题答案-第 29 页2.3 课后习题解答2.3.2 判断题1线性表的逻辑顺序与存储顺序总是一致的。()2顺序存储的线性表可以按序号随机存取。()3顺序表的插入和删除操作不需要付出很大的时间代价,因为每次操作平均只有近一半的元素需要移动。()4线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此属于同一数据对象。()5在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定相邻。()6在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻。()7线性表的链式存储结构优于顺序存储结构。()8在线性表的顺序存储结构中,插入和删除时移动
2、元素的个数与该元素的位置有关。()9线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。()10在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。()11静态链表既有顺序存储的优点,又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。()12线性表的特点是每个元素都有一个前驱和一个后继。()2.3.3 算法设计题1设线性表存放在向量Aarrsize的前elenum个分量中,且递增有序。试写一算法,将x 插入到线性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构(顺序存储的思想是用物
3、理上的相邻表示逻辑上的相邻,不一定将向量和表示线性表长度的变量封装成一个结构体),因为是顺序存储,分配的存储空间是固定大小的,所以首先确定是否还有存储空间,若有,则根据原线性表中元素的有序性,来确定插入元素的插入位置,后面的元素为它让出位置,(也可以从高下标端开始一边比较,一边移位)然后插入x ,最后修改表示表长的变量。int insert (datatype A,int *elenum,datatype x)/*设elenum为表的最大下标*/if (*elenum=arrsize-1) return 0;/*表已满,无法插入*/else i=*elenum; while (i=0 & Ai
4、x)/*边找位置边移动*/Ai+1=Ai;i-; Ai+1=x;/*找到的位置是插入位的下一位*/ (*elenum)+;return 1;/*插入成功*/时间复杂度为O(n)。2已知一顺序表A,其元素值非递减有序排列,编写一个算法删除顺序表中多余的值相同的元素。【提示】对顺序表A,从第一个元素开始,查找其后与之值相同的所有元素,将它们删除;再对第二个元素做同样处理,依此类推。void delete(Seqlist *A)i=0;while(ilast)/*将第i个元素以后与其值相同的元素删除*/k=i+1;while(klast&A-datai=A-datak)k+;/*使k指向第一个与Ai
5、不同的元素*/n=k-i-1;/*n表示要删除元素的个数*/for(j=k;jlast;j+)A-dataj-n=A-dataj; /*删除多余元素*/A-last= A-last -n; i+;3写一个算法,从一个给定的顺序表A中删除值在xy(xdatai是否介于x和y之间,若是,并不立即删除,而是用n记录删除时应前移元素的位移量;若不是,则将A-datai向前移动n位。n用来记录当前已删除元素的个数。void delete(Seqlist *A,int x,int y)i=0;n=0;while (ilast)if (A-datai=x & A-dataidatai 介于x和y之间,n自增
6、*/else A-datai-n=A-datai;/*否则向前移动A-datai*/i+;A-last-=n;4线性表中有n个元素,每个元素是一个字符,现存于向量Rn中,试写一算法,使R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间,元素移动次数最小。【提示】对线性表进行两次扫描,第一次将所有的字母放在前面,第二次将所有的数字放在字母之后,其它字符之前。int fch(char c)/*判断c是否字母*/if(c=a&c=A&c=0&c=9) return (1);else return (0);void process(char Rn)low=0;high=n-1;
7、while(lowhigh)/*将字母放在前面*/while(lowhigh&fch(Rlow) low+;while(lowhigh&!fch(Rhigh) high-;if(lowhigh)k=Rlow;Rlow=Rhigh;Rhigh=k;low=low+1; high=n-1;while(lowhigh)/*将数字放在字母后面,其它字符前面*/while(lowhigh&fnum(Rlow) low+;while(lowhigh&!fnum(Rhigh) high-;if(lowhigh) k=Rlow;Rlow=Rhigh;Rhigh=k;5线性表用顺序存储,设计一个算法,用尽可能少
8、的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表:(a1, a2, , am, b1, b2, , bn)改变为:(b1, b2, , bn , a1, a2, , am)。【提示】比较m和n的大小,若mn,则将表中元素依次前移m次;否则,将表中元素依次后移n次。void process(Seqlist *L,int m,int n) if(m=n) for(i=1;idata0;for(k=1;klast;k+)L-datak-1=L-datak;L-dataL-last=x;else for(i=1;idataL-last;for(k=L-last-1;k=0;k-
9、-)L-datak+1=L-datak;L-data0=x;6已知带头结点的单链表L中的结点是按整数值递增排列的,试写一算法,将值为x 的结点插入到表L中,使得L仍然递增有序,并且分析算法的时间复杂度。LinkList insert(LinkList L, int x) p=L; while(p-next & xp-next-data) p=p-next;/*寻找插入位置*/ s=(LNode *)malloc(sizeof(LNode);/*申请结点空间*/s-data=x; /*填装结点*/s-next=p-next; p-next=s; /*将结点插入到链表中*/ return(L);7
10、假设有两个已排序(递增)的单链表A和B,编写算法将它们合并成一个链表C而不改变其排序性。LinkList Combine(LinkList A, LinkList B)C=A;rc=C;pa=A-next;/*pa指向表A的第一个结点*/pb=B-next;/*pb指向表B的第一个结点*/free(B);/*释放B的头结点*/while (pa & pb)/*将pa、pb所指向结点中,值较小的一个插入到链表C的表尾*/ if(pa-datadata) rc-next=pa;rc=pa;pa=pa-next;elserc-next=pb;rc=pb;pb=pb-next;if(pa)rc-nex
11、t=pa;elserc-next=pb;/*将链表A或B中剩余的部分链接到链表C的表尾*/return(C);8假设长度大于1的循环单链表中,既无头结点也无头指针,p为指向该链表中某一结点的指针,编写算法删除该结点的前驱结点。【提示】利用循环单链表的特点,通过s指针可循环找到其前驱结点p及p的前驱结点q,然后可删除结点*p。viod delepre(LNode *s)LNode *p, *q;p=s;while (p-next!=s)q=p; p=p-next;q-next=s;free(p);9已知两个单链表A和B分别表示两个集合,其元素递增排列,编写算法求出A和B的交集C,要求C同样以元素
12、递增的单链表形式存储。【提示】交集指的是两个单链表的元素值相同的结点的集合,为了操作方便,先让单链表C带有一个头结点,最后将其删除掉。算法中指针p用来指向A中的当前结点,指针q用来指向B中的当前结点,将其值进行比较,两者相等时,属于交集中的一个元素,两者不等时,将其较小者跳过,继续后面的比较。LinkList Intersect(LinkList A, LinkList B)LNode *q, *p, *r, *s; LinkList C;C= (LNode *)malloc(sizeof(LNode);C-next=NULL;r=C;p=A; q=B;while (p & q ) if (p
13、-datadata) p=p-next; elseif (p-data=q-data) s=(LNode *)malloc(sizeof(LNode); s-data=p-data; r-next=s; r=s; p=p-next; q=q-next;else q=q-next;r-next=NULL; C=C-next; return C;10设有一个双向链表,每个结点中除有prior、data和next域外,还有一个访问频度freq域,在链表被起用之前,该域的值初始化为零。每当在链表进行一次Locata(L,x)运算后,令值为x的结点中的freq域增1,并调整表中结点的次序,使其按访问频度
14、的非递增序列排列,以便使频繁访问的结点总是靠近表头。试写一个满足上述要求的Locata(L,x)算法。【提示】在定位操作的同时,需要调整链表中结点的次序:每次进行定位操作后,要查看所查找结点的freq域,将其同前面结点的freq域进行比较,同时进行结点次序的调整。typedef struct dnodedatatype data;int freq;struct DLnode *prior,*next;DLnode,*DLinkList;DlinkList Locate(DLinkList L, datatype x)p=L-next;while(p&p-data!=x) p=p-next; /
15、*查找值为x的结点,使p指向它*/if(!p) return(NULL);/*若查找失败,返回空指针*/p-freq+;/*修改p的freq域*/while(p-prior!=L&p-prior-freqfreq)/*调整结点的次序*/ k=p-prior-data;p-prior-data=p-data;p-data=k;k=p-prior-freq;p-prior-freq=p-freq;p-freq=k;p=p-prior;return(p);/*返回找到的结点的地址*/3.3 课后习题解答 #3.3.1 选择题1向一个栈顶指针为Top的链栈中插入一个p所指结点时,其操作步骤为(C)。A
16、Top-next=p; Bp-next=Top-next;Top-next=p;Cp-next=Top;Top=p; Dp-next=Top;Top=Top-next;2对于栈操作数据的原则是(B)。A先进先出 B后进先出 C后进后出 D不分顺序3若已知一个栈的入栈序列是1,2,3,n,其输出序列为p1,p2,p3,pN,若pN是n,则pi是(D)。Ai Bn-i C n-i+1 D不确定4表达式a*(bc)d的后缀表达式是(B)。Aabcd*-+ Babc-*d+ Cabc*-d+ D+-*abcd5采用顺序存储的两个栈共享空间S1.m,topi代表第i个栈( i=1,2)的栈顶,栈1的底在
17、S1,栈2的底在Sm,则栈满的条件是(B)。Atop2-top1|=0 Btop1+1=top2Ctop1+top2=m Dtop1=top26一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是(C)。A edcba B decba Cdceab D abcde7在一个链队列中,若f,r分别为队首、队尾指针,则插入s所指结点的操作为(B)。Af-next=r;f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s;8用不带头结点的单链表存储队列时,在进行删除运算时(D)。A仅修改头指针 B仅修改尾指针C头、尾指针都要修改 D头、尾指针可能都
18、要修改9递归过程或函数调用时,处理参数及返回地址,要用一种称为(C)的数据结构。A队列 B静态链表 C栈 D顺序表10栈和队都是(C)。A顺序存储的线性结构 B链式存储的非线性结构C限制存取点的线性结构 D限制存取点的非线性结构3.3.2 判断题1栈和队列的存储,既可以采用顺序存储结构,又可以采用链式存储结构。()2任何一个递归过程都可以转换成非递归过程。()3若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。()4通常使用队列来处理函数的调用。()5循环队列通常用指针来实现队列的头尾相接。()3.3.3 简答题1循环队列的优点是什么?如何判别它的空和满?循环
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法 数据结构 算法 课后 习题 答案 29
限制150内