数据结构课程--课后习题答案

《数据结构简明教程》练习题及参考答案练习题11.单项选择题（1）线性结构中数据元素之间是（）关系。A.一对多B.多对多C.多对一D.一对一答：D（2）数据结构中与所使用的计算机无关的是数据的（）结构。A.存储B.物理C.逻辑D.物理和存储答：C（3）算法分析的目的是（）。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性答：C（4）算法分析的两个主要方面是（）。A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性答：A（5）计算机算法指的是（）。A.计算方法B.排序方法C.求解问题的有限运算序列D.调度方法答：C（6）计算机算法必须具备输入、输出和（）等5个特性。A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性答：B2.填空题（1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。答：①逻辑结构②存储结构③运算（2）数据结构按逻辑结构可分为两大类，它们分别是①和②。答：①线性结构②非线性结构（3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。数据结构简明教程答：①数据元素②关系（4）在线性结构中，第一个结点①前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点②后继结点，其余每个结点有且只有1个后继结点。答：①没有②没有（5）在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点；叶子结点没有③结点，其余每个结点的后继结点数可以是④。答：①前驱②1③后继④任意多个（6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（）。答：任意多个（7）数据的存储结构主要有四种，它们分别是①、②、③和④存储结构。答：①顺序②链式③索引④哈希（8）一个算法的效率可分为①效率和②效率。答：①时间②空间3.简答题（1）数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。（2）简述线性结构、树形结构和图形结构的不同点。答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。（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)=2nlog2n-1000log2n答：T1(n)=O(nlog2n)，T2(n)=O()，T3(n)=O(n2)，T4(n)=O(nlog2n)。（5）分析下面程序段中循环语句的执行次数。intj=0,s=0,n=100;do{j=j+1;s=s+10*j;}while(jn&&sn);答：j=0，第1次循环：j=1，s=10。第2次循环：j=2，s=30。第3次循环：j=3，s=60。3log2n3练习题及参考答案第4次循环：j=4，s=100。while条件不再满足。所以，其中循环语句的执行次数为4。（6）执行下面的语句时，语句s++的执行次数为多少？ints=0;for(i=1;in-1;i++)for(j=n;j=i;j--)s++;答：语句s的执行次数2)2)(3(3)1()1(12121nnnninniniinj。（7）设n为问题规模，求以下算法的时间复杂度。voidfun1(intn){intx=0,i;for(i=1;i=n;i++)for(j=i+1;j=n;j++)x++;}答：其中x++语句属基本运算语句，ninijninninnT1112)1()(1)(=O(n2)。（8）设n为问题规模，是一个正偶数，试计算以下算法结束时m的值，并给出该算法的时间复杂度。voidfun2(intn){intm=0;for(i=1;i=n;i++)for(j=2*i;j=n;j++)m++;}答：由于内循环j的取值范围，所以i≤n/2，则2/122/124/))12((ninijnininm，该程序段的时间复杂度为O(n2)。上机实验题1有一个整型数组a，其中含有n个元素，设计尽可能好的算法求其中的最大元素和次大元素，并采用相关数据测试。解：maxs算法用于返回数组a[0..n-1]中的最大元素值max1和次大元素值max2，max1和max2设计为引用类型。对应的程序如下：#includestdio.hvoidmaxs(inta[],intn,int&max1,int&max2){inti;max1=max2=a[0];for(i=1;in;i++)数据结构简明教程if(a[i]max1){max2=max1;max1=a[i];}elseif(a[i]max2)max2=a[i];}voidmain(){inta[]={1,4,10,6,8,3,5,7,9,2};intn=10;intmax1,max2;maxs(a,n,max1,max2);printf(最大元素值=%d,次大元素值=%d\n,max1,max2);}练习题21.单项选择题（1）数据在计算机存储器内表示时，物理地址与逻辑地址相对顺序相同并且是连续的，称之为（）。A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构答：C（2）在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）。A.访问第i个结点（1≤i≤n）和求第i（2≤i≤n）个结点的前驱结点B.在第i（1≤i≤n）个结点后插入一个新结点C.删除第i个结点（1≤i≤n）D.将n个结点从小到大排序答：A（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A.8B.63.5C.63D.7答：B（4）链式存储结构所占存储空间（）。A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只有一部分，存放结点值C.只有一部分，存储表示结点间关系的指针D.分两部分，一部分存放结点值，另一部分存放结点所占单元数答：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。5练习题及参考答案A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以答：D（6）一个线性表在（）情况下适用于采用链式存储结构。A.需经常修改其中的结点值B.需不断对其进行删除插入C.其中含有大量的结点D.其中结点结构复杂答：B（7）单链表的存储密度（）A.大于1B.等于1C.小于1D.不能确定答：C2.填空题（1）在顺序表中插入或删除一个元素时，需要平均移动（①）元素，具体移动的元素个数与（②）有关。答：①表中一半②表长和该元素在表中的位置（2）向一个长度为n的顺序表的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动（）个元素。答：n-i+1（3）向一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（）个元素。答：n-i（4）在顺序表中访问任意一个元素的时间复杂度均为（①），因此顺序表也称为（②）的数据结构。答：①O(1)②随机存取（5）顺序表中逻辑上相邻的元素的物理位置（①）相邻。单链表中逻辑上相邻的元素的物理位置（②）相邻。答：①一定②不一定（6）在带头结点的单链表中，除头结点外，任一结点的存储位置由（）指示。答：其前驱结点的链域的值（7）在含有n个数据结点的单链表中要删除已知结点*p，需找到它的（①），其时间复杂度为（②）。答：①前驱结点的地址②O(n)（8）含有n（n1）个结点的循环双向链表中，为空的指针域数为（）。答：03.简答题（1）试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：顺序存储结构中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元数据结构简明教程的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储结构中，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用灵活；缺点是存储密度小，存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。（2）对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的平均个数为多少？答：插入一个元素所需要移动的元素的平均个数为(n-1)/2，删除一个元素所需要移动的平均个数为n/2。（3）在链表中设置头结点的作用是什么？答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链表的操作（如插入和删除）在各种情况下统一，从而简化了算法的实现过程。（4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior域。所以共修改4个指针。对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入结点的next域。所以共修改两个指针。（5）某含有n（n1）结点的线性表中，最常用的操作是在尾结点之后插入一个结点和删除第一个结点，则采用以下哪种存储方式最节省运算时间。①单链表；②仅有头指针不带头结点的循环单链表；③双链表；④仅有尾指针的循环单链表。答：在单链表中，删除第一个结点的时间复杂度为O(1)。插入结点需找到前驱结点，所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为O(n)。在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度O(n)，因为删除第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也为O(n)。在双链表中，删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点，也需找到尾结点，对应的时间复杂度为O(n)。在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点也就是在尾指针所指结点之后插入一个结点，时间复杂度也为O(1)。因此④最节省运算时间。7练习题及参考答案4.算法设计题（1）设计一个高效算法，将顺序表的所有元素逆置，要求算法空间复杂度为O(1)。解：遍历顺序表L的前半部分元素，对于元素L.data[i]（0≤i＜L.length/2），将其与后半部分对应元素L.data[L.length-i-1]进行交换。对应的算法如下：voidreverse(SqList&L){inti;ElemTypex;for(i=0;iL.length/2;i++){x=L.data[i];//L.data[i]与L.data[L.length-i-1]交换L.data[i]=L.data[L.length-i-1];L.data[L.length-i-1]=x;}}本算法的时间复杂度为O(n)。（2）设计一个算法从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。解：对于顺序表L，用i从1开始遍历其元素，设L.data[0.