《数据结构简明教程》练习题及参考答案VIP专享VIP免费

《数据结构简明教程》练习题及参考答案练习题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)=-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(j=i;j--)s++;答：语句s的执行次数。（7）设n为问题规模，求以下算法的时间复杂度。voidfun1(intn){intx=0,i;for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)x++;}答：其中x++语句属基本运算语句，=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，则，该程序段的时间复杂度为O(n2)。上机实验题1有一个整型数组a，其中含有n个元素，设计尽可能好的算法求其中的最大元素和次大元素，并采用相关数据测试。解：maxs算法用于返回数组a[0..n-1]中的最大元素值max1和次大元素值max2，max1和max2设计为引用类型。对应的程序...