第一章绪论习题解析.doc

《第一章绪论习题解析.doc》由会员分享，可在线阅读，更多相关《第一章绪论习题解析.doc（4页珍藏版）》请在金锄头文库上搜索。

1、第一章 绪 论一，选择题1组成数据的基本单位是（）A数据项B数据类型C数据元素D数据变量数据（data）：对客观事物的符号表示，在计算机科学中指所有能输入到计算机并被计算机程序处理的符号的总称。数据元素（data element）：数据的基本单位。在计算机程序中通常作为一个整体进行考虑和处理。数据项（data item）：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。数据对象（data object）：性质相同的数据元素的集合，是数据的一个子集。数据结构（data structure）：相互之间存在一种或多种特定关系的数据元素的集合。（数据元素的集合、数据元素之间关系的集合） 数

2、据结构形式定义为：数据结构是一个二元组：Data_Structure=(D,S) D是数据元素的有限集，S是D上关系的有限集 结构（structure）：数据元素之间的关系。4种基本结构：集合、线性结构、树形结构、图状结构或网状结构。2数据结构是研究数据的（）以及它们之间的相互关系。A理想结构，物理结构 B理想结构，抽象结构C物理结构，逻辑结构 D抽象结构，逻辑结构逻辑结构又称逻辑关系，物理结构又称存储结构。数据结构在计算机中的表示称为数据的物理结构（存储结构），又称映像。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像、非顺序映像。 对应的两种存储结构：顺序存储结构、链式存储结构3

3、算法分析的两个主要方面是（ ）A正确性和简单性 B可读性和文档性C数据复杂性和程序复杂性 D时间复杂度和空间复杂度算法（algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法的5个特性：有穷性、确定性、可行性、输入、输出。算法设计的要求：正确性（correctness）、可读性（readability）、健壮性（robustness）、效率与低存储量需求。算法效率的度量：事后统计和事前分析估算。用高级程序语言编写的程序在计算机上运行时消耗的时间取决于：算法选用的策略、问题的规模、书写程序的语言（语言级别越高，执行效率越低）、编译程序所产生机

4、器代码的质量、机器执行指令的速度。时间复杂度（asymptotic time complexity）：以基本操作重复执行的次数作为算法的时间度量。 有时算法中基本操作重复执行次数随输入数据集不同而不同，所以一般讨论算法在最坏情况下的时间复杂度。空间复杂度（space complexity）4算法分析的目的是（）。A 找出数据结构的合理性 B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性5. 算法的时间复杂度取决于（ ）A问题的规模 B. 待处理数据的初态 C. A和B 以上都不是6一个算法应该是（ ）。 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和

5、C. 7. 下面关于算法说法错误的是（ ）A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的算法的确定性说的是指令不能有二义性。8从逻辑上可以把数据结构分为（ ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构9程序段 for ( i=n-1;i=1;i-) for (j=1jAj+1) Aj与Aj+1对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（ ）A O（n） B O(nlogn) C.O(n3) DO(n2) 10连续存储设计时

6、，存储单元的地址（ ）。A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续二，判断题1数据结构的抽象操作的定义与具体实现有关。 ( ) 2数据结构是数据对象与对象中数据元素之间关系的集合。 （ ） 数据元素 数据元素之间关系3在顺序存储结构中，有时也存储数据结构中元素之间的关系。 ( )4数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。 （ ）5算法和程序原则上没有区别，在讨论数据结构是两者是通用的。 （ ）6同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。 （ ）7数据的逻辑结构与数据元素本身的内容和形式无关。 （ ）

7、8算法的优劣与算法描述语言无关，但与所用计算机有关。 ( )9健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 ( )10算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。 ( ) 三，填空1数据的物理结构包括 数据元素 的表示和 数据元素间关系 的表示。2. 对于给定的n个元素,可以构造出的逻辑结构有 集合 ， 线性结构 ， 树形结构 ，_图状结构 _四种。3一个数据结构在计算机中 的表示 称为存储结构。4抽象数据类型的定义仅取决于它的一组_逻辑特性 _，而与_ 在计算机内部如何表示和实现 _无关，即不论其内部结构如何变化，只要它的_ 数

8、学特性 _不变，都不影响其外部使用。5线性结构中元素之间存在 一对一 关系,树形结构中元素之间存在 一对多 关系,图形结构中元素之间存在 多对多 关系。6一个算法有5个特性: 有穷性 、 确定性 、 可行性 ，有零个或多个输入、有一个或多个输出。?7已知如下程序段for （i:= n；i=1;i+） 语句1x:=x+1； 语句2for( j=n;j=i ;j+) 语句3 y:=y+1; 语句4语句1执行的频度为 1 n ；语句2执行的频度为 n ；语句3执行的频度为 n ；语句4执行的频度为 n2 。语句频度：指该语句重复执行的次数。(与时间复杂度区分)8在下面的程序段中，对的赋值语句的频度为

9、_n3_（表示为n的函数） for(i1;i=n;i+)for(j;j=i;j+)for(k1;k=j;j+)delta；9. 计算机执行下面的语句时，语句s的执行次数为 _ 。 for(i=l；i=i;j-) s; 10. 下面程序段的时间复杂度为_。(n1) sum=1； for (i=0;sumn;i+) sum+=1; 四，应用题1什么是数据? 它与信息是什么关系?2什么是数据结构? 数据结构是研究什么内容的学科？有关数据结构的讨论涉及哪三方面?3评价一个好的算法，从哪几方面考虑？4. 若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？5解释算法与程序的区别？6有

10、下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。（1）A=（K，R），其中：K=a，b，c，d，e，f，gR=rr=a，b，b，c，c，d，d，e，e，f，f，g（2）B=（K，R），其中：K=a，b，c，d，e，f，g，hR=rr=d，b，d，g，d，a，b，c，g，e，g，h，a，f（3）C=（K，R），其中：K=1，2，3，4，5，6R=rr=(1, 2)，(2, 3)，（2，4），（3，4），（3，5），（3，6），（4，5），（4,6）这里的圆括号对表示两结点是双向的。7分析以下程序段的时间复杂度。（1）a=0；b=1；for（i=2；i=n；i+）s=a+b；b=a；a=S；（2）inti，j，k；for（i=0；in；i+for（j=0；jn；j+cij=0；for（k=0；kn；k+cij=cij+aik+bkj；8求下列算法段的语句频度及时间复杂度（1）for(i=1; i=n; i+)for(j =1; j =i ; j+)x=x+1;（2）for （i=1;i=n;i+）for (j=1;j=i;j+)for ( k=1;k=j;k+)x=i+j-k;