数据结构第1章绪论.doc

《数据结构第1章绪论.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第一章习题判断题1．数据元素是数据的最小单位。(×)2．记录是数据处理的最小单位。(×)3．数据的逻辑结构是指数据的各数据项之间的逻辑关系。(×)4．算法的优劣与算法描述语言无关，但与所用计算机有关。(×)5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(√)6．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。(×)7．程序一定是算法。(×)8．数据的物理结构是指数据在计算机内的实际存储形式。((√)9．数据结构的抽象操作的定义与具体实现有关。(×)10．在顺序存储结构中，有时也存储数据结构中元素之

2、间的关系。(×)11．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×)12．数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。((√)13．数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。(×)答案1．×2．×3．×4．×5．√6．×7．×8．√9．×10．×11．×12．√13．×填空题1．数据的物理结构包括____的表示和____的表示。2．对于给定的n个元素,可以构造出的逻辑结构有（1），（2），（3），（4）四种。3．数据的逻辑结构是指_____。4．一个数据结构在计算机中______称为存储

3、结构。5．抽象数据类型的定义仅取决于它的一组（1），而与（2）无关，即不论其内部结构如何变化，只要它的（3）不变，都不影响其外部使用。6．数据结构中评价算法的两个重要指标是_______。7．数据结构是研讨数据的（1）和（2），以及它们之间的相互关系，并对与这种结构定义相应的（3），设计出相应的（4）。8．一个算法具有5个特性:（1）、（2）、（3），有零个或多个输入、有一个或多个输出。9．已知如下程序段FORi:=n DOWNTO 1 DO  {语句1}BEGIN  x:=x+1；   {语句2}   FORj:=n DOWNTO i DO {语句3} 

4、 y:=y+1;    {语句4}END；语句1执行的频度为（1）；语句2执行的频度为（2）；语句3执行的频度为（3）；语句4执行的频度为（4）。10．在下面的程序段中，对ｘ的赋值语句的频度为______。 （表示为n的函数）FOR  i：＝１TOn　DOFOR　　j：＝１　TOi　DOFOR　k：＝1　TO　j　DO　ｘ：＝ｘ＋delta；11．下面程序段中带下划线的语句的执行次数的数量级是：____。  i：=1；WHILEi12．下面程序段中带下划线的语句的执行次数的数量级是()。  i:=1;  WHILEi

5、:=x+1;i:=i*2END；13．下面程序段中带有下划线的语句的执行次数的数量级是()。i：=n*nWHILEi<>1DOi:=idiv2;14．计算机执行下面的语句时，语句s的执行次数为_______。FOR(i=l；i=i;j--)s；15.下面程序段的时间复杂度为________。  (n>1)sum=1；for(i=0;sumsum

6、，2+2+1，2+1+1+1，1+1+1+1+1。①以下是该函数的程序段，请将未完成的部分填入，使之完整intf(m,n)intm,n;{if(m==1)return(1);if(n==1){return(2);}if(m

7、之间逻辑关系的总体而逻辑关系   是指数据元素之间的关联方式或称“邻接关系”4．表示（又称映像）5．（1）逻辑特性（2）在计算机内部如何表示和实现（3）数学特性6．算法的时间复杂度和空间复杂度7．（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法8．（1）有穷性（2）确定性（3）可行性9．（1）n+1（2）n(3）n(n+3)/2（4）n(n+1)/210．1+（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6O(n3)11.log2n12.nlog2n13.log2n214.(n+3)(n-2)/215.O(n)16.①

8、(1)1(2)1(3)f(m,n-1)(4)n②917.n(n-1