数据结构与算法第1章参考答案08.doc

习题参考答案一选择题 1.从逻辑上可以把数据结构分为（C)两大类。A.动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构 2.在下面的程序段中，对x的斌值语句的频度为（C)。for( t1；kn;k）for（j=1;jn; j）x=x十1；A. O(2n) B. O (n) C. O (n2) D. O（1og2n)3.采用链式存储结构表示数据时，相邻的数据元素的存储地址（C)。A.一定连续 B一定不连续C.不一定连续 D.部分连续，部分不连续4.下面关于算法说法正确的是（D）。 A.算法的时间复杂度一般与算法的空间复杂度成正比B.解决某问题的算法可能有多种，但肯定采用相同的数据结构C.算法的可行性是指算法的指令不能有二义性D.同一个算法，实现语言的级别越高，执行效率就越低5.在发生非法操作时，算法能够作出适当处理的特性称为（B）。A.正确性 B.健壮性 C.可读性 D.可移植性二、判断题1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）2.顺序存储方式的优点是存储密度大，且插人、删除运算效率高。（）3.数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（）4.算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（）5.算法必须有输出，但可以没有输人。（）三、筒答题1常见的逻辑结构有哪几种，各自的特点是什么？常用的存储结构有哪几种，各自的特点是什么？【答】常见的四种逻辑结构： 集合结构：数据元素之间是“属于同一个集合” 线性结构：数据元素之间存在着一对一的关系 树结构：数据元素之间存在着一对多的关系 结构：数据元素之间存在着多对多的关系。常见的四种存储结构有：顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链接存储：对逻辑上相邻的元素不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点的其他信息。散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。2简述算法和程序的区别。【解答】一个算法若用程序设计语言来描述，则它就是一个程序。算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。3.试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算这3方面的内容。【解答】略。4.运算是数据结构的一个重要方面。试举例说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同，使得两个结构具有显著不同的特性。【解答】比如顺序栈和循环队列，二者的逻辑结构都是线性结构，都采用顺序存储方式存储，但它们的运算不同，栈限定元素的插入和删除在栈顶进行，队列限定元素在队尾插入、在队首删除，因此它们是截然不同的数据结构。5分析下列程序段中带标号“语句的执行频度(n为正整数）。（1) j1；k=0;while（j=n-1）j；k=j; *【解答】 n-1（2）i=0；s=0；n=100；do i+；s10*i；*while!(in&s 0)if (x100) x-=10; y-; else x;解答 10006.写出下列各程序段关于n的时间复杂度。（1） a1；m1；while（an）m= a;a*3；解答O(n)（2）设n是偶数。for（i=1，s0；in；i）for（j=2*i；jn；j）s；解答 O（n2）（3）for（i=1；i=n-1；i）ki；for(j=i1；j=n;j）if(RjRj1）kj；tRk；Rk=Ri；Ri=t；解答 O（n2）7.计算一元n次多项式P( x，n）=a0alxa2x2anxn“的值，输人x,n，a0，al，an，输出多项式P(x，n)的值。设计算法求解，请选择合适的输人、输出格式，要求算法具有较好的时间性能。【解答】将一元n次多项式做如下改写：P( x，n）=a0alxa2x2anxn =a0x(ala2xanxn-1) =a0x(alx(a2x(a3+x(an-1xan)按指数递减次序输人各系数，即输人次序为an，an-1，a2，a0 算法如下：main( )s0;scanf(”%f ,&x);for(k=n; k=1；k-） scanf (% f”,&a）； s=s*x+a； printf（”P（x,n）=%f”，s）；分析：该算法仅使用了n次乘法和n次加法，来完成一元n次多项式的求值问题，具有较好的时间和空间性能。