严蔚敏数据结构题集c语言版期末用.docxVIP

严蔚敏数据结构C语言版答案详解 1.1简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符 号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1. 2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由 具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型 通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数 据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实 现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3设有数据结构(D, R),其中 D = {dl,〃2,d3,〃4}, R = {r}, r= {(dl,d2),(d2,d3),(d3,d4)} 试按图论中图的画法惯例画出其逻辑结构图。 1.6在程序设计中，常用下列三种不同的出错处理方式： 用exit语句终止执行并报告错误； 以函数的返回值区别正确返回或错误返回； 设置一个整型变最的函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自的优缺点。 解：(l)exit常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。 以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。 用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。 1.7在程序设计中，可采用下列三种方法实现输出和输入： 通过scanf和printf语句； 通过函数的参数显式传递； 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制, 较为烦琐，如果出现错误，则会引起整个系统的崩溃。 通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。 通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程 序的维护较为困难。 1.8设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： i=l; k=0; wh订e(i=n-l) { @ k += 10*i; i++； } i=l; k=0; do { @ k += 10*i; i++； } while(i=n-l); i=l; k=0; wh订e (i=n-l) { i++； @ k += 10*i; } k=0; for(i=l; i=n; i++) { for(j=i; j=n; j++) @ k++; } for(i=l; i=n; i卄){ for(j=l; j=i; j++) { for(k=l; k=j; k++) @ x += delta; } i=l; j=0; wh订e(i+j=n) { @ if(ij) j++; else i++; } x=n; y=0; 〃n是不小于1的常数 while(x= (y+l)*(y+l)) { @ y++; } x=91; y=100： while(y0) { @ if(x100) { x -= 10; y―; } else x++; 解：(1) n-1 ⑵n-1 n-1 n+(nT) + (n-2)+...+匸巴凹 Z(/ + l)22 Z(/ + l) 2 1+(1+2)+ (1+2+3)+...+ (1+2+3+. ..+n) = V TOC \o 1-5 \h \z [n 1 n 1 n 导+ 1)畑 / i=\ 乙 /=l 乙 i=\ =—n(n +1)( 2m +1) + 丄并(m + 1) = —n(n +1)(2 比 + 3) 1 1 n [_、/并」向下取整 1100 1?9假设n为2的乘幕，并且n2,试求下列算法的时间复杂度及变量count的值(以n的函数形式表示)。 int Time(int n) { count = 0; x=2; while(xn/2) { x *= 2; count++; } return count; } 解:(?(log2 n) count=log2 n — 2 l.n已知有实现同一功