数据结构习题集答案严蔚敏.docx
117页
细心整理第1章 绪论1.1 简述以下术语：数据，数据元素、数据对象、数据构造、存储构造、数据类型和抽象数据类型解：数据是对客观事物的符号表示在计算机科学中是指全部能输入到计算机中并被计算机程序处理的符号的总称 数据元素是数据的根本单位，在计算机程序中通常作为一个整体进展考虑和处理 数据对象是性质一样的数据元素的集合，是数据的一个子集 数据构造是相互之间存在一种或多种特定关系的数据元素的集合 存储构造是数据构造在计算机中的表示 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作是对一般数据类型的扩展1.2 试描述数据构造和抽象数据类型的概念与程序设计语言中数据类型概念的区分解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象一般数据类型由具体语言系统内部定义，干脆供应应编程者定义用户数据，因此称它们为预定义数据类型抽象数据类型通常由编程者定义，包括定义它所运用的数据和在这些数据上所进展的操作在定义抽象数据类型中的数据局部和操作局部时，要求只定义到数据的逻辑构造和操作说明，不考虑数据的存储构造和操作的具体实现，这样抽象层次更高，更能为其他用户供应良好的运用接口。
1.3 设有数据构造(D,R)，其中，，试按图论中图的画法惯例画出其逻辑构造图解：1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义〔有理数是其分子、分母均为自然数且分母不为零的分数〕 解：ADT Complex{ 数据对象：D={r,i|r,i为实数} 数据关系：R={
1) product=1; i=1; while(i<=n){ product *= i; i++; }(2) i=0; do { i++; } while((i!=n) && (a[i]!=x));(3) switch { case x 摸索讨这三种方法的优缺点解：(1)用scanf和printf干脆进展输入输出的好处是形象、直观，但缺点是须要对其进展格式限制，较为烦琐，假如出现错误，那么会引起整个系统的崩溃 (2)通过函数的参数传递进展输入输出，便于实现信息的隐藏，削减出错的可能 (3)通过全局变量的隐式传递进展输入输出最为便利，只需修变更量的值即可，但过多的全局变量使程序的维护较为困难1.8 设n为正整数试确定以下各程序段中前置以记号@的语句的频度：(1) i=1; k=0; while(i<=n-1){ @ k += 10*i; i++; }(2) i=1; k=0; do { @ k += 10*i; i++; } while(i<=n-1);(3) i=1; k=0; while (i<=n-1) { i++; @ k += 10*i; }(4) k=0; for(i=1; i<=n; i++) { for(j=i; j<=n; j++) @ k++; }(5) for(i=1; i<=n; i++) { for(j=1; j<=i; j++) { for(k=1; k<=j; k++) @ x += delta; }(6) i=1; j=0; while(i+j<=n) { @ if(i>j) j++; else i++; }(7) x=n; y=0; // n是不小于1的常数 while(x>=(y+1)*(y+1)) { @ y++; }(8) x=91; y=100; while(y>0) { @ if(x>100) { x -= 10; y--; } else x++; }解：(1) n-1 (2) n-1 (3) n-1 (4) n+(n-1)+(n-2)+...+1= (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)= = = (6) n (7) 向下取整 (8) 11001.9 假设n为2的乘幂，并且n>2，试求以下算法的时间困难度及变量count的值〔以n的函数形式表示〕。 int Time(int n) { count = 0; x=2; while(x 当n>438时，1.14 判定以下各对函数和，当时，哪个函数增长更快？(1) ，(2) ，(3) ，(4) ，解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快1.15 试用数学归纳法证明：(1) (2) (3) (4) 1.16 试写一算法，自大至小依次输出依次读入的三个整数X，Y和Z的值解：int max3(int x,int y,int z){ if(x>y) if(x>z) return x; else return z; else if(y>z) return y; else return z;}1.17 确定k阶斐波那契序列的定义为 ，，…，，； ， 试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现解：k>0为阶数，n为数列的第n项int Fibonacci(int k,int n){ if(k<1) exit(OVERFLOW);int *p,x; p=new int[k+1]; if(!p) exit(OVERFLOW); int i,j; for(i=0;i 解：typedef enum{A,B,C,D,E} SchoolName;。
