数据结构与算法分析课后习题答案

数据结构与算法分析课后习题答案数据结构与算法分析课后习题答案【篇一：《数据结构与算法》课后习题答案】>2.3.2判断题2．顺序存储的线性表可以按序号随机存取。（√）4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√）6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√）线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）2.3.3算法设计题a[arrsize]elenum个分量中，且递增x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元（也可以从高下标端开始一边比较，一边移位）x改表示表长的变量。tt(etex／设m为表的最大下(*elenum==arrsize-1) returnO; ／＊表已满，无法插入＊／else{i=*elenum;e(O ]x／.'.'1＿＿｝＿＿mreturn＊／｝｝时间复杂度为o(n)。a,其元素值非递减有序排序表中多余的值相同的元素。【提示】对顺序表a,有元素，将它们删除；再对第二个元素做同样处理，依此类推。voiddelete(seqlist*a){i=O;l(将第i个元素以后与其值相同的元素删＊／{k=i+1;while(k=a-lasta-data[i]==a-data[k])+/使K指向第一个与]＊／n表示要删除元素的个数＊／for(j＝k;j=a-last;j++)j-n]=a-data[j]／＊除多 余元素＊／a-last=a-last-n;i++;｝｝写个算，从一个 给定的序表a中删除值在x~y(x=y)之间所有元素，要求以较高的效率来实现。a,从前向后依次判断当前元素a-data[i]y之间，若是，并不立即删除，而是用n；若不是a-data[innvoiddelete(seqlist*a,intx,inty){i=O;n=O;while(ia-last){if(a-data[i]=x a-data[i]=y)n++;／＊若a-data[i] 千x和y之，｝n自＊／e i-n]=a-data[i]／＊否则向前动i++;｝a-last-=n;｝线性表中有nr[n]中，试写一算法，使r【提示】对线性表进行两次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在字母之后，其它字符之前。intfch(charc)/*判断c是否字母*/{if(c=ac=z||c=ac=z)return(1);elsereturn(0);}intfnum(charc) /*c是否数字*/{if(c=0c=9)return(1);elsereturn(0);}voidprocess(charr[n]){low=0;high=n-1;while(lowhigh)/*将字母放在前面*/{while(lowhighfch(r[low])) low++;while(lowhigh!fch(r[high])) high--;if(lowhigh){k=r[low];r[low]=r[high];r[high]=k;}}low=low+1;high=n-1;while(lowhigh)/*将数字放在字母后面，其它字符前面*/{while(lowhighfnum(r[low]))low++;while(lowhigh!fnum(r[high]))if(lowhigh){k=r[low];r[low]=r[high];r[high]=k;}}}线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间mn个元素进行整体互换。即将线性表：（a1,a2,…,am,b1,b2,…,bn）改变为：（b1,b2,…,bn,a1,a2,…,am）。mnm次；否则,n次。voidprocess(seqlist*l,intm,intn){if(m=n){x=l-data[0];for(k=1;k=l-last;k++)l-data[k-1]=l-data[k];l-data[l-last]=x;}elsefor(i=1;i=n;i++){x=l-data[l-last];for(k=l-last-1;k=0;k--)l-data[k+1]=l-data[k];l-data[0]=x;}}l中的结点是按整数值递增排列的，试写xll仍然递增有序，并且分析算法的时间复杂度。linklistinsert(linklistl,intx){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);}假设有两个已排序（递增）abc而不改变其排序性。linklistcombine(linklista,linklistb){c=a;rc=c;pa=a-next;/*pa指向表a的第一个结点*/pb=b-next;/*pb指向表b的第一个结点*/free(b); /*释放b的头结点*/while(pa pb)/*pa、pbc的表尾*/if(pa-datapb-data){rc-next=pa;rc=pa;pa=pa-next;}else{rc-next=pb;rc=pb;pb=pb-next;}if(pa)rc-next=pa;elserc-next=pb;/*将链表a或b中剩余的部分链接到链表c的表尾*/return(c);}1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点。【提示】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q，然后可删除结点*p。vioddelepre(lnode*s){lnode *p,*q;p=s;while(p-next!=s){q=p;p=p-next;}q-next=s;free(p);}ab分别表示两个集合，其元素递增排列，编abcc同样以元素递增的单链表形式存储。【提示】交集指的是两个单链表的元素值相同的结点的集合，为了c带有一个头结点，最后将其删除掉。算法中paqb中的当前结点，linklistintersect(linklista,linklistb){lnode*q,*p,*r,*s;linklistc;c=(lnode*)malloc(sizeof(lnode));c-next=null;r=c;p=a;q=b;while(pq)if(p-dataq-data)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;returnc;}priordatanext域外freqlocata(l,x)xfreq1，并调整表中结点的次序，使其按访问频度的非递增序列排列，以便使频繁访问的结点总是靠近表头。试写一个满足上述要求的locata(l,x)算法。【提示】在定位操作的同时，需要调整链表中结点的次序：每次进freqfreqtypedefstructdnode【篇二：数据结构课后习题答案】lass=txt>高等学校精品资源共享课程绪论第1章1.1什么是数据结构？1.2数据结构涉及哪几个方面？【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集合。【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，所以它们是两种不同的数据结构。线性结构的特点是什么？非线性结构的特点是什么？【答】：线性结构元素之间的关系是一对一的，在线性结构中只有系可以是一对多的或多对多的。1.5【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。1.6什么？（4）1个或多个输出（5）通过程序可以在计算机上实现算法。1.7有什么特点？【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基1.8算法的时间复杂度指的是什么？如何表示？【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算n的数据处理问题，用t(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常oof的一个上限。其它义如下：3十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程g)cf(ncfgcnn0nn≥n0)g是f的一个上限（f提供一个上限函数gn的（带一个常数系数1-1g函数及其1-1logn，没有给出对数基，原因是对1ablogan=logbn/logba,所以loganlogbn1/logbaa是一个常量。1-1常用的渐进函数辅助空间的个数。可以将它表示为问题规模的函数，并通过大写o符号表示空间复杂度。t(n)。（1）i++;（2）for(i=0;in;i++)if(a[i]x)x=a[i];（3）for(i=0;in;i++)for(j=0;jn;j++);（4）for(i=1;i=n-1;i++){k=i;for(j=i+1;j=n;j++)if(a[j]a[j+1])k=j;t=a[k];a[k]=a[i];a[i]=t;}（5）for(i=0;in;i++)for(j=0;jn;j++){++x;s=s+x;}【答】：（1）o（1）；（2）o（n）；（3）o（n2）；（4）o（n2）；（5）o（n2）42选择题n的顺序存储的线性表，当在任何位置上插入或删除（（a）。a．（n?1）/2e．n/2b．nc．n+1d．n?1g．(n?2)/2sqe1、e2、e3、e4、e5e6sq6个e2、e4、e3、e6、e5e1s的容量至少应该为（c）。a．6（b）ab．n?i+1c．id．n?i（4）ni向前移动（a）a．n?i间复杂度为（a）。a．o(n)b．o(1)c．o(n2)）。d．?+*abcdd．o(n3)（6）表达式a*(b+c)?d的后缀表达式是（bb．n?i+1c．n?i?1d．i（5）若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时b．4c．3d．2（3）设栈的输入序列为1、2、3…n，若输出序列的第一个元素为n，则第i个输出的元素为e），删除一个元素所需移动元素的平均个数a．abcd*+?b．abc+*d?c．abc*+d（7）队列是一种特殊的线性表，其特殊性在于（c）。ab．插入和删除在表的两端位置c（8）栈是一种特殊的线性表，具有（b）性质。a．先进先出b．先进后出c．后进后出d．顺序进出front指向队1rear1个位置，则循环队列中存放了n??1个元素，即循环队列满）。的条件为（ba．(rear+1)%n=front?1c．(rear)%n=frontb．(rear+1)%n=frontd．rear+1=front顺序循环队列中（6），front和队rear301个元素，再插2个元素后，frontrear的值分别为（d）。a．5和1b．2和4c．1和5d．4和2什么是顺序表？什么是栈？什么是队列？5【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表 现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出的特点。x序表的存储结构定义如下（文件名seqlist.h）：#includestdio.h#definen100typedefintdatatype;typedefstructdatatypedata[n];intlength;}seqlist;/*预定义最大的数据域空间*//*假设数据类型为整型*//*此处假设数据元素只包含一个整型的关键字域*//*线性表长度*//*预定义的顺序表类型*/countx（l,x）lxintcountx(seqlist*l,datatypex)intc=0;inti;for(i=0;il-length;i++)if(l-data[i]==x)c++;returnc;}aaa[0]等于原]2的最后一个元素等于原来的第一个元素。voidverge(seqlist*l){intt,i,j;i=0;j=l-length-1;while(ij){t=l-data[i];l-data[i++]=l-data[j];l-data[j--]=t;}}已知一个顺序表中的各结点值是从小到大有序的，设计一个算x【答】：顺序表的定义同题2.3，实现本题要求的算法程序如下：6voidinsertx(seqlist*l,datatypex){intif(l-lengthn){j=l-length-1;while(j=0 l-data[j]x){l-data[j+1]=l-data[j];j--;}l-data[j+1]=x;l-length++;}}将下列中缀表达式转换为等价的后缀表达式。(1)5+6*7(2)(5-6)/7(3)5-6*7*8(4)5*7-8(5)5*(7-6)+8/9(6)7*(5-6*8)-9【答】：(7)5+6*7(8)(5-6)/7(9)5-6*7*8(10)5*7-8(11)5*(7-6)+8/9(12)7*(5-6*8)-96+6-7/6-后7*8-79/+56n，队首指针和队尾front1,2,3,4n列火车通过调度站，请设计一个算方法一：算法思想：逐次输出所有可能，用回溯法。即：总体：对原始序列中的每一个元素，总是先入栈，后出栈入栈后的操作：a.该元素出栈；b.下一个元素入栈；（原始序列中）x：xxx的下一个子分支,x“退回”，7【篇三：数据结构课后习题答案】下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。存储结构：数据对象在计算机中的存储表示，也称为物理结构。抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。答案：专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。即相同的逻辑结构，可以对应不同的存储结构。3．简述逻辑结构的四种基本关系并画出它们的关系图。答案：集合结构数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。线性结构数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。树结构数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。图结构或网状结构数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图形结构或网状结构。其中树结构和图结构都属于非线性结构。四类基本逻辑结构关系图答案：顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的选择题在数据结构中，从逻辑上可以把数据结构分成（）a．动态结构和静态结构 b．紧凑结构和非紧凑结构c．线性结构和非线性结构d．内部结构和外部结构答案：c与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。abcd答案：c通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。数据具有同一特点每个数据元素都一样d答案：b以下说法正确的是（）。a．数据元素是数据的最小单位b．数据项是数据的基本单位c．数据结构是带有结构的各数据项的集合d答案：d据结构是带有结构的各数据元素的集合。算法的时间复杂度取决于（）。a．问题的规模答案：d解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态以下数据结构中，（）是非线性数据结构树 b．字符串c．队列 d．栈答案：a6（1）x=90;y=100;while(y0)if(x100){x=x-10;y--;}elsex++;答案：o(1)解释：程序的执行次数为常数阶。d．abc．计算机的配置（2）for(i=0;in;for(j=0;jm;j++)a[