严蔚敏数据结构课本源码及习题解析第01章 绪论.docx
第1章绪论一、基础知识题简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。数据(data)是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(data element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合。存储结构(物理结构)是数据结构在计算机中的表示(又称映像)。数据类型(data type)是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型(Abstract Data Type)是指一个数学模型以及定义在该模型上的一组操作。1.1 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。1.2 设有数据结构(D, R),其中D=dlzd2zd3,d4, R=r, r=(d1,d2),(d2,d3),(d3,d4)。试按图论中图的画法惯例画出其逻辑结构图。14试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。复数定义：ADT Complex /复数定义 a±bi 数据对象：D = a, b | a,b为实数数据关系：R = <a, b>>基本操作：InitComplex(&C, re, im) 操作结果：构造一个复数C,其实部和虚部分别为re和imDestroyCmoplex(&C) 操作结果：销毁复数C Get(C, k, &e) 初始条件：复数C已存在 操作结果：用e返回复数C的第k元的值 Put(&Cz k, e) 初始条件：复数C已存在 操作结果：改变复数C的第k元的值为e IsAscending(C) 初始条件：复数C已存在 操作结果：如果复数C的两个元素按升序排列，则返回1,否则返回0IsDescending(C) 初始条件：复数C已存在 操作结果：如果复数C的两个元素按降序排列，则返回工，否则返回0Max(C, &e) 初始条件：复数C已存在 操作结果：用e返回复数C的两个元素中值较大的一个Min(C, &e) 初始条件：复数C已存在 操作结果：用e返回复数C的两个元素中值较小的一个/i = k-1fibi = 1;i+；while(i<=m)/i = k( for(j=i-l, fibi=O; j>=i-k; j-) fibLi += fibj; i+； ) return fibm;) 假设有A、B、C、D、E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每 一行的形式为项目名称性另u校名成绩得分编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。typedef enum A, B, C, D, E SchoolName;typedef enum FEMALE, MALE SexType;typedef enum X, Y, Z Event; typedef struct(Event e;项目名称SexType sex;性别SchoolName school;校名 int score;得分Component;typedef struct(intmalesum;男团总分intfemalesum;女团总分inttotalsum;团体总分Sum;Component report n; /n条记录Sum result5;算法过程体中主要结构 for(i=0; i<n; i+)(对result report i. school进行处理)for(s=A; s<=E; s+)1，9 试编写算法，计算i!*N的值并存入数组aO.arrsiNeT的第iT个分量中。= 1,2,n)。假设计算机中允许的整数最大值为maxint,则当n>arrsize或对某个k(1Wk<n)使k!*2k>maxint时，应按出错处理。注意选择你认为较好的 出错处理方法。ttinclude <stdio. h>#include <limits.h>提供宏INT_MAX#include ”././课本算法实现/上。1绪论/Status. h"/*A01绪论*/*宏定义*/ttdefine arrsize 20数组长度define maxint INT_MAX最大的整数/*函数原型*/Status Algo_l_19(int i, int a);int main(int argc, char *argv) (int i, aEarrsize;i = 5;printf (计算i!*?. n' );if(Algo_l_19(i, a) =0K)printf ("作为示例，计算当i = %d 时，ai-l = %dn，z, i, ai-l); printf (Z，nz);return 0; )/*1|题L19：计算i!*2X存入ai-1, i起点为1|*/Status Algo_l_19(int i, int a口) (int j;if(i<l | i>arrsize) return ERROR;for(j=l; j<=i; j+) (if(j=l) aj-l = 2;elseif(maxint/( *j)<aj-) return OVERFLOW;aj-l = 2 * j * aj-2;)return OK; 试编写算法求一元多项式= 的值Pn(x),并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意/=0选择你认为较好的输入和输出方法。本题的输入为xo和m输出为Pn(x。)。ttinclude <stdio. h>include <math. h>提供pow原型/*函数原型*/int Algo_l_20(int a, int x, int n);int main(int argc, char *argv) (int a5 = -2, 3, 6, -8, 7;int n =：>int Xo = 3;printf ("作为示范，设定项数n = 5,变量Xo = 3,计算Pn(Xo).n");printf (/zP%d (%d) = %dn”, n, Xo, Algo_l_20 (a, Xo, n);printf Cn");return 0;)/*|题L20：计算多项式Pn(Xo)的值|I*/int Algo_l_20(int a, int x, int n) (int i;int tmp;for(i=l, tmp=0; i<=n; i+)tmp += ai-l*pow(x, i-1);return tmp;ADT Complex有理数定义：ADT RationalNumber有理数定义<数据对象：D=s, m | s,m为自然数，且m不为0数据关系：R=<sz m>>基本操作：InitRationalNumber(&Rz s, m) 操作结果：构造一个有理数R,其分子和分母分别为s和mDestroyRationalNumber(&R) 操作结果：销毁有理数R Get(Rz k, &e) 初始条件：有理数R已存在 操作结果：用e返回有理数R的第k元的值 Put(&Rz kz e) 初始条件：有理数R已存在 操作结果：改变有理数R的第k元的值为e IsAscending(R) 初始条件：有理数R已存在 操作结果：若有理数R的两个元素按升序排列，则返回T,否则返回。IsDescending(R) 初始条件：有理数R已存在 操作结果：若有理数R的两个元素按降序排列，则返回工，否则返回0Max(Rz &e) 初始条件：有理数R已存在 操作结果：用e返回有理数R的两个元素中值较大的一个Min(R, &e) 初始条件：有理数R已存在 操作结果：用e返回有理数R的两个元素中值较小的一个ADT RationalNumber试画出与下列程序段等价的框图。(l)product = 1;i = 1； while(i< = n)<product *= i; i+； (2)i=0; do < i+；while(i! = n) && (ai!=x);(3)switchcase x<y: z=y-x; break;case x=y: z=abs(x*y);break;default:z=(x-y)/abs(x)*abs(y);在程序设计中，常用下列三种不同的出错处理方式：(1)用exit语句终止执行并报告错误；(2)以函数的返回值区别正确返回或错误返回；(3)设置一个整型变量的函数参数以区别正确返回或某种错误返回。试讨论这三种方法各自的优缺点。(1) exit常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。优点是可以在程序的任何地方关闭程序，缺点是隐藏了故障信息。(2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。(3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速定位错误。1.20 在程序设计中，可采用下列三种方法实现输出和输入：(1)通过scanf和printf语句；(2)通过函数的参数显式传递；(3)通过全局变量隐式传递。试讨论这三种方法的优缺点。(工)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系 统的崩溃。(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。1.21 设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 = l; i< = n; i+ + )<for(j=i; j<=n; j+) k+;(5) for(i = l; i< = n; i+ + )for(j = l; j<=i; j+) for(k=l; k<=j; k+ + ) x += 1;(6) i = 1; j = 0;while(i+j <= n) if(i>j) j+; elsei +；)(7) x = n; y = 0;/n是不小于1的常数while(x >= (y+l)*(y+l) y+;(8) x = 91; y = 100;while(y>0) if(x>100)<x -= 10;y-;)elsex+ ;(1) n-l(3)(3)n-1(4)l + 2 + - + /? = -2(5)1 + (1 + 2) + .(1 + 2 + + )W)1/ 八 0-=Z -+1)(2 + 3) /=1 乙12(6)(7)(7)|_册(向下取整)(8)11001.9假设n为2的乘嘉，并且n>2,试求下列算法的时间复杂度及变量count的值(以n的函数形式表示)。int Time (int n)count = 0;while(x<n/2)count+;)return (count)/Time时间复杂度：OOogzn)count = logzn - 21,。按增长率由小至大的顺序排列下列各函数:210°, (3/2)n, (2/3)n, (4/3)n, nn, n3/2, n2/3, Vn, n!, n9 log2n, n/log2n. log2zn, logzClogzn)9 nlogzn, nlog2n各函数的排列次序如下：(2 / 3) 21(X) log2(Iog2 n) log2 n (log2 n)2 4n W n /log2 nn nlog2 n n3/2 (4/3) (3/2)2 陶" n nn1.110 已知有实现同一功能的两个算法，其时间复杂度分别为0(2")和O(n】o),假设现实计算机可连续运算的时间为IO： 秒(100多天)，又每秒可执行基本操作(根据这些操作来估算算法时间复杂度)105次。试问在此条件下，这两个算法可解问 题的规模(即n值的范围)各为多少？哪个算法更适宜？请说明理由。2n=1012n=40nio=loi2n = i6故第一种算法较适宜。由此可见，虽然一般情况下多项式阶的算法优于指数阶的算法，但高次多项式的算法在n的很大范围内不如某些指数阶的 算法。1.12设有以下三个函数：f(n) = 21n4+n2+1000, g(n) = 15n4+500n2, h(n) = 5000n3 5+nlogn请判断以下断言正确与否：(1) f(n)是 O(g(n)(2) h(n)是 O(f(n)(3) g(n)是 O(h(n)(4) h(n)是。(评)(5) h(n)是 O(nlogn)(T)对(2)错(3)错(4)对(5)错1.130 试设定若干n值，比较两函数M和50nlog2ii的增长趋势，并确定n在什么范围内时M的值大于SOnlogzn。 大约在n>450时，函数#的值才大于函数50nlog2n的值。1.140 判断下列各对函数f(n)和g(n),当n-8时，哪个函数增长更快?(1)/(n) = 102 4-ln(n!+10z?)g(n) = 2n4 + + 7(2) /5) = (ln(!)+ 5)2g()= 13”(3) f (n) = n2A 4- Vn4 4-1 g(n) = (ln(n!)2 + n(4) /() = 2(&+(2)2g() = J+5(1)g(n)快(2)g(n)快(3)f(n)快(4) f(n)快1.150 试用数学归纳法证明：(1)=( +D(2 +D / 6 (n > 0)i=l(2) £V =(x+i l)/(x 1)(xwl,N0)i=0(3) Z2"=2-1(h > 1)i=l(4) E(2/-D = n2(H >Di=(1)证明：当n=0时，左式二右式二0,结论显然成立。当n>0时，令n=k(k>0),假设力2 =k(k + l)(2k + l)/6(*)i=l成立，则当n=k+l时：k+lk2i2 = 2i2 + (k+l)2 i-1i-1= k(k + l)(2k +1)/6 +(k + l)2= (k + l)(k + 2)2(k + l) + l/6这就是说，当n=k+l时,(*)式也成立，因而(*)式在k>0时均成立。又k=0时,(*)式依然成立，故原式在n之0时均成立。至此，等式得证。(2)证明：当n=0时，左式二右式=1,结论显然成立。当n>0时，令n=k(k>0),假设£xi=(xk+Jl)/(X l) (XW1)(*)i=0成立，则当n=k+l时：k+lk£xi =+ xk+,i=oi=o=(xk+, -1) /(X - 1) + xk+,= (xk+2-l)/(x-l)这就是说，当口=1<+1时,(*)式也成立，因而(*)式在k>0时均成立。又k=0时,(*)式依然成立，故原式在n N 0时均成立。至此，等式得证。(3)证明：当n=l时，左式二右式二L结论显然成立。当n>l时，令n=k(k>l),假设E r1 = 2k -1()i=i成立，则当n=k+l时： k+lki=lkl=2k - 1 + 2k+,-1=2k+, -1这就是说，当n=k+l时,(*)式也成立，因而(*)式在k>l时均成立。又k=l时,(*)式依然成立，故原式在nN 1时均成立。 至此，等式得证。(4)证明：当n=l时，左式=右式=1,结论显然成立。当n>l时，令n=k(k>l),假设七(2i l) = k2()鼻1成立，则当n=k+l时： k+lk£(2i-l) = t(2i-l) + 2(k + l)-l i=l=k2 + 2(k +1) -1=(k + ip这就是说，当n=k+l时,(*)式也成立，因而(*)式在k>l时均成立。又k=l时,(*)式依然成立，故原式在nN 1时均成立。 至此，等式得证。二、算法设计题1.160 试写一算法，自大到小依次输出顺序读入的三个整数X, Y和Z的值。ttinclude <stdio. h>/*函数原型*/void Algo_l_16(int i, int j, int k);int main(int argc, char *argv) (int i, j, k;1 = 3;j = 7;k = 1;printf (作为示范，设定依次读入的三个整数为:%d %d %d. n i, j, k);printf(这三个数从大到小的顺序为：)；Algo_l_16(i, j, k);printf (，znz);return 0;)/*1I题L 16：将3个整数按从大到小顺序输出|*/void Algo_l_16(int i, int j, int )int tmp;if(i<j)(tmp = i;i = j；j = tmp;) if(j<k)(tmp = j;j = k;k = tmp;)if(i<j)(tmp = i;i = j；j = tmp;)printf (/z%d %d %dn", i, j, k);)1,7 已知k阶斐波那契序列的定义为fo=Oz fi=O, fk-2=0, fk-i = l；fn =+fn2+fnk, H k,k+ 1,.试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。include <stdio. h>Sinclude <stdlib. h>提供malloc、realloc> free exit原型ttinclude "./课本算法实现/上。1绪论/Status, h"/*A01绪论*/*函数原型*/int Algo_l_17_l(int k, int m);int Algo_l_17_2(int k, int m);int main(int argc, char *argv) (int k, m;k = 3;m = 10;printf(作为示范，求得%d阶斐波那契数列第%d项的值为：%d n, k, m, Algo_l_17_l(k, m);printf (作为示范，求得%d阶斐波那契数列第%u项的值为：%d n*, k, 2*m, Algo_l_17_2(k, 2*m);printf ( Anz);return 0;)/*1I题L 17：计算k阶斐波那契数列第m项的值|I*/*方法L递归算法*/int Algo_l_17_l (int k, int m)当m变大时，计算速度会递减(int i, value;if(k<2 | m<0)exit(OVERFLOW);if(m<k-l)return 0;else if (m=k-l)return 1; else (for(i=l, value=0; i<=k; i+)value += Algo_l_17_l(k, m-i);return value;I题L 17：计算k阶斐波那契数列第m项的值|/*方法2：递推(迭代)算法*/ int Algo_l_17_2(int , int m) (int i, j;int fibm+l;if(k<l | m<0) exit(OVERFLOW);i = 0;while(i<k-l)(fibi = 0;)
