《数据结构》吕云翔编著第1章绪论习题解答.doc

《《数据结构》吕云翔编著第1章绪论习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构第一章绪论习题一、【单选题】1.（A）是数据的基本单位。Ａ、数据元素　Ｂ、数据对象　Ｃ、数据项　Ｄ、数据结构2.（C）是数据的不可分割的最小单位。Ａ、数据元素　Ｂ、数据对象　Ｃ、数据项　Ｄ、数据结构3.若采用非顺序映象，则数据元素在内存中占用的存储空间（C）。Ａ、一定连续　Ｂ、一定不连续　Ｃ、可连续可不连续4.若采用顺序映象，则数据元素在内存中占用的存储空间（A）。Ａ、一定连续　Ｂ、一定不连续　Ｃ、可连续可不连续5.在数据结构中，从逻辑上可以把数据结构分为（C）Ａ、动态结构和静态结构　Ｂ、紧凑结构和非紧凑结构Ｃ、线性结构和非线性结构　Ｄ、内部结构和外部结构6.在树形结构中，

2、数据元素间存在（B）的关系。Ａ、一对一　Ｂ、一对多　Ｃ、多对多　Ｄ、除同属一个集合外别无关系7.下列说法中错误的是（B）。Ａ、数据对象是数据的子集Ｂ、数据元素间关系在计算机中的映象即为数据的存储结构Ｃ、非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系Ｄ、抽象数据类型指一个数学模型及定义在该模型上的一组操作8.计算机算法指的是（C）。Ａ、计算方法　Ｂ、排序方法　Ｃ、解决问题的有限运算序列　Ｄ、调度方法9.下列不属算法特性的是（D）。Ａ、有穷性　Ｂ、确定性　Ｃ、零或多个输入　Ｄ、健壮性10.算法分析的目的是（C）。Ａ、找出数据结构的合理性　Ｂ、研究算法中的输入和输出

3、的关系Ｃ、分析算法的效率以求改进　Ｄ、分析算法的易读性和文档性11.算法分析的两个主要方面是（A）。Ａ、空间复杂性和时间复杂性　Ｂ、正确性和简明性Ｃ、可读性和文档性　Ｄ、数据复杂性和程序复杂性12.算法的计算量的大小称为算法的（A）。Ａ、效率　Ｂ、复杂性　Ｃ、现实性　Ｄ、难度13.在下面的程序段中，对x的赋值语句的频度为（C）。for(i=1;i<=n;++i)for(j=1;j<=n;++j)x=x+1;Ａ、2n　Ｂ、n　Ｃ、n2　Ｄ、log2n14.设n为正整数，则如下程序段中最后一行的语句频度在最坏情况下是（D）。for(i=n-1;i>=1;--i)for(j=1;j<=i

4、;++j)if(A[j]>A[j+1])A[j]←→A[j+1];Ａ、n　Ｂ、n(n-1)/2　Ｃ、n(n+1)/2　Ｄ、n2二、填空题1. 数据逻辑结构包括（ 集合 ）、（ 线性结构 ）、( 树形结构 )、( 图型结构 )四种类型，树型和图型结构合称（ 非线性结构 ）。 2. 对于给定的n 个元素，可以构造出的逻辑结构有（集合）、（线性结构）、（树形结构）和（图型结构）四种。 3. 算法的五个重要特性是（有穷性）、（确定性）、（可行性）、(输入)、(输出)。 4. 评价算法的性能从利用计算机资源角度看主要从（时间复杂度和空间复杂度）方面进行分析。 5. 线性结构中元素之间存在（一

5、对一）关系，树型结构中元素之间存在（一对多）关系，图型结构中元素之间存在（多对多）关系。6. 所谓数据的逻辑结构指的是数据元素之间的（逻辑关系）。 7. 在线性结构中，开始结点（没有）直接前驱结点，其余每个结点有且只有（一）个直接前驱结点。 8. 在树形结构中，根结点只有（一个），根结点无前驱，其余每个结点有且只有（一个）直接前驱结点；叶子结点没有（后继）结点，其余每个结点的后继结点可以（任意个）。 9. 在图形结构中，每个结点的前驱结点和后继结点可以有（任意个）。 10. 存储结构是逻辑结构的（物理）实现。 11. 一个算法的时空性能是指该算法的（时间复杂度）和（空间复杂度） 。

6、 12. 在一般情况下，一个算法的时间复杂性是（问题规模）的函数。 三、算法设计题1.判断n是否为一个素数，若是则返回逻辑值true，否则返回逻辑值false，并计算算法的时间复杂度。Public boolean prime(int m){     boolean flag=true;     if(m==1)flag=false; for(int i=2;i<=m-1;i++)      if(m%i==0)   { flag=false; break; }   return flag;  }该算法的时间复杂度为O()。2.计算的值，并计算算法的时间复杂度。方法1：时间复杂度为O

7、(nlogn)。publicclassTest3{publicstaticvoidmain(String[]args){intsum=0,fact,n,i，j;for(j=1;j<=n;j++){fact=1;for(i=1;i<=j;i++)fact*=i;sum+=fact;}System.out.println("sum="+sum);}}方法2：时间复杂度为O(n)。publicclassTest3{publicstaticvoidmain(String[]a