《数据构造课程课后习题答案..docx》由会员分享，可在线阅读，更多相关《数据构造课程课后习题答案..docx（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据构造课程课后习题答案.（数据构造简明教程）练习题及参考答案练习题11.单项选择题1线性构造中数据元素之间是关系。A.一对多B.多对多C.多对一D.一对一答：D2数据构造中与所使用的计算机无关的是数据的构造。A.存储B.物理C.逻辑D.物理和存储答：C3算法分析的目的是。A.找出数据构造的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改良D.分析算法的易懂性和文档性答：C4算法分析的两个主要方面是。A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性答：A5计算机算法指的是。A.计算方法B.排序方法C.求解问题的有限运算序列D.调度方法答：C
2、6计算机算法必须具备输入、输出和等5个特性。A.可行性、可移植性和可扩大性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性答：B2.填空题1数据构造包括数据的、数据的和数据的这三个方面的内容。数据构造简明教程答：逻辑构造存储构造运算2数据构造按逻辑构造可分为两大类，它们分别是和。答：线性构造非线性构造3数据构造被形式地定义为D,R，其中D是的有限集合，R是D上的有限集合。答：数据元素关系4在线性构造中，第一个结点前驱结点，其余每个结点有且只要1个前驱结点；最后一个结点后继结点，其余每个结点有且只要1个后继结点。答：没有没有5在树形构造中，树根结点没有结点，其余每个
3、结点有且只要个前驱结点；叶子结点没有结点，其余每个结点的后继结点数能够是。答：前驱1后继任意多个6在图形构造中，每个结点的前驱结点数和后继结点数能够是。答：任意多个7数据的存储构造主要有四种，它们分别是、和存储构造。答：顺序链式索引哈希8一个算法的效率可分为效率和效率。答：时间空间3.简答题1数据构造和数据类型两个概念之间有区别吗？答：简单地讲，数据构造定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。2简述线性构造、树形构造和图形构造的不同点。答：线性构造反映结点间的逻辑关系是一对一的，树形线性构造反映结点间的逻辑关系是一对多的，图在
4、构造反映结点间的逻辑关系是多对多的。3设有采用二元组表示的数据逻辑构造S=(D,R)，其中D=a,b,i，R=(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)，问相对于关系R，哪些结点是开场结点，哪些结点是终端结点？答：该逻辑构造为树形构造，其中a结点没有前驱结点，称为根结点，b、e、g、i结点没有后继结点，是终端结点，也称为叶子结点。4下面各函数是算法中语句的执行频度，n为问题规模，给出对应的时间复杂度：T1(n)=nlog2n-1000log2nT2(n)=3log2n-1000log2nT3(n)=n2-1000log2nT4(n)=2nlo
5、g2n-1000log2n答：T1(n)=O(nlog2n)，T2(n)=O()，T3(n)=O(n2)，T4(n)=O(nlog2n)。5分析下面程序段中循环语句的执行次数。intj=0,s=0,n=100;3log2n3doj=j+1;s=s+10*j;while(j=i;j-)s+;答：语句s的执行次数2)2)(3(3)1()1(12121-+=+-+=+-=-=-=nnnninniniinj。7设n为问题规模，求下面算法的时间复杂度。voidfun1(intn)intx=0,i;for(i=1;i数据构造简明教程#includevoidmaxs(inta,intn,int&max1,i
6、nt&max2)inti;max1=max2=a0;for(i=1;imax1)max2=max1;max1=ai;elseif(aimax2)max2=ai;voidmain()inta=1,4,10,6,8,3,5,7,9,2;intn=10;intmax1,max2;maxs(a,n,max1,max2);printf(最大元素值=%d,次大元素值=%dn,max1,max2);练习题21.单项选择题1数据在计算机存储器内表示时，物理地址与逻辑地址相对顺序一样并且是连续的，称之为。A.存储构造B.逻辑构造C.顺序存储构造D.链式存储构造答：C2在n个结点的顺序表中，算法的时间复杂度是O1
7、的操作是。A.访问第i个结点1in和求第i2in个结点的前驱结点B.在第i1in个结点后插入一个新结点C.删除第i个结点1inD.将n个结点从小到大排序答：A3向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。A.8B.63.5C.63D.7答：B4链式存储构造所占存储空间。A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只要一部分，存放结点值C.只要一部分，存储表示结点间关系的指针D.分两部分，一部分存放结点值，另一部分存放结点所占单元数答：A5线性表若采用链式存储构造时，要求内存中可用存储单元的地址。A.必须是连续的B.部分地址必须是连续
8、的C.一定是不连续的D.连续或不连续都能够答：D6一个线性表在情况下适用于采用链式存储构造。A.需经常修改其中的结点值B.需不断对其进行删除插入C.其中含有大量的结点D.其中结点构造复杂答：B7单链表的存储密度A.大于1B.等于1C.小于1D.不能确定答：C2.填空题1在顺序表中插入或删除一个元素时，需要平均移动元素，详细移动的元素个数与有关。答：表中一半表长和该元素在表中的位置2向一个长度为n的顺序表的第i个元素1in+1之前插入一个元素时，需向后移动个元素。答：n-i+13向一个长度为n的顺序表中删除第i个元素1in时，需向前移动个元素。答：n-i4在顺序表中访问任意一个元素的时间复杂度均
9、为，因而顺序表也称为的数据构造。答：O(1)随机存取5顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置相邻。答：一定不一定6在带头结点的单链表中，除头结点外，任一结点的存储位置由指示。答：其前驱结点的链域的值7在含有n个数据结点的单链表中要删除已知结点*p，需找到它的，其时间复杂度为。答：前驱结点的地址O(n)8含有nn1个结点的循环双向链表中，为空的指针域数为。答：05数据构造简明教程3.简答题1试比拟顺序存储构造和链式存储构造的优缺点。在什么情况下用顺序表比链表好？答：顺序存储构造中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元的地址必须是连续的。其优点
10、是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储构造中，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用灵敏；缺点是存储密度小，存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。2对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的平均个数为多
11、少？答：插入一个元素所需要移动的元素的平均个数为(n-1)/2，删除一个元素所需要移动的平均个数为n/2。3在链表中设置头结点的作用是什么？答：在链表中设置头结点后，不管链表能否为空表，头结点指针均不空，并使得对链表的操作如插入和删除在各种情况下统一，进而简化了算法的实现经过。4对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior域。所以共修改4个指针。对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入结点的nex
12、t域。所以共修改两个指针。5某含有nn1结点的线性表中，最常用的操作是在尾结点之后插入一个结点和删除第一个结点，则采用下面哪种存储方式最节省运算时间。单链表；仅有头指针不带头结点的循环单链表；双链表；仅有尾指针的循环单链表。答：在单链表中，删除第一个结点的时间复杂度为O(1)。插入结点需找到前驱结点，所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为O(n)。在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度O(n)，由于删除第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也为O(n)。在双链表中，删除第一个结点的时间复杂度为O(1)；在尾结点
13、之后插入一个结点，也需找到尾结点，对应的时间复杂度为O(n)。在仅有尾指针的循环单链表中，通过该尾指针能够直接找到第一个结点，所以删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点也就是在尾指针所指结点之后插入一个结点，时间复杂度也为O(1)。因而最节省运算时间。4.算法设计题1设计一个高效算法，将顺序表的所有元素逆置，要求算法空间复杂度为O(1)。解：遍历顺序表L的前半部分元素，对于元素L.datai0iL.length/2，将其与后半部分对应元素L.dataL.length-i-1进行交换。对应的算法如下：voidreverse(SqList&L)inti;ElemTypex;
14、for(i=0;ij)/表示L.datai和L.data0.j中所有元素都不一样j+;L.dataj=L.datai;L.length=j+1;/顺序表长度置新值本算法的时间复杂度为O(n2)，空间复杂度为O(1)。3设计一个算法从有序顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。解：在有序顺序表L中，所有重复的元素应是相邻存放的，用k保存不重复出现的元素个数，先将不重复的有序区看成是L.data0.0，置e=L.data0，用i从1开场遍历L的7数据构造简明教程所有元素：当L.dataie时，将它放在L.datak中，k增1，置e=L.datai，最后将L的length置为k。对
15、应的算法如下：voiddelsame1(SqList&L)/L为引用型参数inti,k=1;/k保存不重复的元素个数ElemTypee;e=L.data0;for(i=1;inext;/p指向*q的前驱结点while(q!=NULL&q-data!=x)p=q;q=q-next;if(q!=NULL)/找到值为x的结点p-next=q-next;free(q);return1;elsereturn0;/未找到值为x的结点5设计一个算法断定单链表L能否是递增的。解：断定链表L从第2个结点开场的每个结点的值能否比其前驱的值大。若有一个不成立，则整个链表便不是递增的；否则是递增的。对应的算法如下：i
16、ntincrease(SLink*L)SLink*pre=L-next,*p;/pre指向第一个数据结点p=pre-next;/p指向*pre结点的后继结点while(p!=NULL)if(p-data=pre-data)/若正序则继续判定下一个结点pre=p;/pre、p同步后移p=p-next;elsereturn0;return1;6有一个整数元素建立的单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数结点，B单链表中所有的奇数结点，且保持原来的相对次序。解：采用重新单链表的方法，由于要保持相对次序，所以采用尾插法建立新表A、B。用p遍历原单链表A的所有数据
17、结点，若为偶数结点，将其链到A中，若为奇数结点，将其链到B中。对应的算法如下：voidSplit(SLink*&A,SLink*&B)SLink*p=A-next,*ra,*rb;ra=A;B=(SLink*)malloc(sizeof(SLink);/建立头结点rb=B;/r总是指向B链表的尾结点while(p!=NULL)if(p-data%2=0)/偶数结点ra-next=p;/将*p结点链到A中ra=p;p=p-next;else/奇数结点rb-next=p;/将*p结点链到B中rb=p;p=p-next;ra-next=rb-next=NULL;本算法的时间复杂度为O(n)，空间复杂
18、度为O(1)。7有一个有序单链表从小到大排列，表头指针为L，设计一个算法向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。解：先建立一个待插入的结点，然后依次与链表中的各结点的数据域比拟大小，找到插入该结点的位置，最后插入该结点。对应的算法如下：voidinorderList(SLink*&L,ElemTypex)SLink*s,*p,*q;s=(SLink*)malloc(sizeof(SLink);/建立一个待插入的结点s-data=x;s-next=NULL;if(L=NULL|xdata)/若单链表为空或x小于第1个结点date域s-next=L;/把*s结点插入到头结点之后
19、9数据构造简明教程L=s;elseq=L;/寻找插入位置,p指向待比拟的结点,q指向p的前驱结点p=q-next;while(p!=NULL&xp-data)/若x小于p所指结点的data域值if(xp-data)q=p;p=p-next;s-next=p;/将s结点插入到*q和*p之间q-next=s;8有一个单链表L，其中可能出现值域重复的结点，设计一个算法删除值域重复的结点。并分析算法的时间复杂度。解：用p遍历单链表，用r遍历*p结点之后的结点，q始终指向*r结点的直接前驱结点，若r-data=p-data，则删除*r结点，否则q、r同步后移一个结点。对应的算法如下：voiddels1(
20、SLink*&L)SLink*p=L-next,*q,*r,*t;while(p!=NULL)q=p;r=q-next;while(r!=NULL)if(r-data=p-data)/r指向被删结点t=r-next;q-next=t;free(r);r=t;elseq=r;r=r-next;p=p-next;本算法的时间复杂度为O(n2)。9有一个递增有序单链表允许出现值域重复的结点，设计一个算法删除值域重复的结点。并分析算法的时间复杂度。解：由于是有序表，所以一样值域的结点都是相邻的。用p遍历递增单链表，若*p结点的值域等于其后结点的值域，则删除后者。对应的算法如下：voiddels(SLi
21、nk*&L)SLink*p=L-next,*q;while(p-next!=NULL)if(p-data=p-next-data)/找到重复值的结点q=p-next;/q指向这个重复值的结点p-next=q-next;/删除*q结点free(q);elsep=p-next;本算法的时间复杂度为O(n)。10有一个双链表L，设计一个算法查找第一个元素值为x的结点，将其与后继结点进行交换。解：先找到第一个元素值为x的结点*p，q指向其后继结点，此题是将*p结点移到*q结点之后，实现经过是：删除*p结点，再将其插入到*q结点之后。对应的算法如下：intswap(DLink*L,ElemTypex)D
22、Link*p=L-next,*q;while(p!=NULL&p-data!=x)p=p-next;if(p=NULL)/未找到值为x的结点return0;else/找到值为x的结点*pq=p-next;/q指向*p的后继结点if(q!=NULL)/*p结点不是尾结点p-prior-next=q;/先删除*p结点q-prior=p-prior;p-next=q-next;/将*p结点插入到*q结点之后if(q-next!=NULL)q-next-prior=p;q-next=p;p-prior=q;return1;else/*p结点是尾结点return0;/无法与后继结点交换，返回011对于有nn1个数据结点的循环单链表L，设计一个算法将所有结点逆置。11