第1章 绪论
1、1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型与抽象数据类型。
解：数据就是对客观事物得符号表示。在计算机科学中就是指所有能输入到计算机中并被计算机程序处理得符号得总称。扬缡滞顏痈饜譚。 数据元素就是数据得基本单位，在计算机程序中通常作为一个整体进行考虑与处理。 数据对象就是性质相同得数据元素得集合，就是数据得一个子集。 数据结构就是相互之间存在一种或多种特定关系得数据元素得集合。 存储结构就是数据结构在计算机中得表示。
数据类型就是一个值得集合与定义在这个值集上得一组操作得总称。
抽象数据类型就是指一个数学模型以及定义在该模型上得一组操作。就是对一般数据类型得扩展。
1、2 试描述数据结构与抽象数据类型得概念与程序设计语言中数据类型概念得区别。
解：抽象数据类型包含一般数据类型得概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用得数据与在这些数据上所进行得操作。在定义抽象数据类型中得数据部分与操作部分时，要求只定义到数据得逻辑结构与操作说明，不考虑数据得存储结构与操作得具体实现，这样抽象层次更高，更能为其她用户提供良好得使用接口。泽覷陆饺鳍韧確。 1、3 设有数据结构(D,R)，其中
D??d1,d2,d3,d4?，R??r?，r???d1,d2?,?d2,d3?,?d3,d4??
试按图论中图得画法惯例画出其逻辑结构图。
解：
1、4 试仿照三元组得抽象数据类型分别写出抽象数据类型复数与有理数得定义（有理数就是其分子、分母均为自然数且分母不为零得分数）。覿榇驭驯賞亙淨。 解：
ADT Complex{
数据对象：D={r,i|r,i为实数} 数据关系：R={
InitComplex(&C,re,im)
操作结果：构造一个复数C，其实部与虚部分别为re与im DestroyCmoplex(&C)
操作结果：销毁复数C Get(C,k,&e)
操作结果：用e返回复数C得第k元得值 操作结果：改变复数C得第k元得值为e
操作结果：如果复数C得两个元素按升序排列，则返回1，否则返回0 Put(&C,k,e) IsAscending(C)
IsDescending(C)
操作结果：如果复数C得两个元素按降序排列，则返回1，否则返回0 操作结果：用e返回复数C得两个元素中值较大得一个 操作结果：用e返回复数C得两个元素中值较小得一个 Max(C,&e) Min(C,&e)
}ADT Complex ADT RationalNumber{
数据对象：D={s,m|s,m为自然数，且m不为0} 数据关系：R={
InitRationalNumber(&R,s,m)
操作结果：构造一个有理数R，其分子与分母分别为s与m DestroyRationalNumber(&R)
操作结果：销毁有理数R Get(R,k,&e)
操作结果：用e返回有理数R得第k元得值 操作结果：改变有理数R得第k元得值为e
操作结果：若有理数R得两个元素按升序排列，则返回1，否则返回0 操作结果：若有理数R得两个元素按降序排列，则返回1，否则返回0 操作结果：用e返回有理数R得两个元素中值较大得一个 操作结果：用e返回有理数R得两个元素中值较小得一个 Put(&R,k,e) IsAscending(R) IsDescending(R) Max(R,&e) Min(R,&e)
}ADT RationalNumber (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、5 试画出与下列程序段等价得框图。 1、6 在程序设计中，常用下列三种不同得出错处理方式： (1) 用exit语句终止执行并报告错误； (2) 以函数得返回值区别正确返回或错误返回； (3) 设置一个整型变量得函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自得优缺点。 解：(1)exit常用于异常错误处理，它可以强行中断程序得执行，返回操作系统。 (2)以函数得返回值判断正确与否常用于子程序得测试，便于实现程序得局部控制。 (3)用整型函数进行错误处理得优点就是可以给出错误类型，便于迅速确定错误。 1、7 在程序设计中，可采用下列三种方法实现输出与输入： (1) 通过scanf与printf语句； (2) 通过函数得参数显式传递； (3) 通过全局变量隐式传递。 试讨论这三种方法得优缺点。 解：(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= n(n?1) 2i(i?1) ?2i?1n (5) 1+(1+2)+(1+2+3)+、、、+(1+2+3+、、、+n)= 1n1n21n21n =?i(i?1)??(i?i)??i??i 2i?12i?12i?12i?1 = 111n(n?1)(2n?1)?n(n?1)?n(n?1)(2n?3) 12412 (6) n (7) ?n? 向下取整 (8) 1100 1、9 假设n为2得乘幂，并且n>2，试求下列算法得时间复杂度及变量count得值（以n得函数形式表示）。 东费觊绮轮稣軫。 int Time(int n) { } 解：o(log2count=log2count = 0; } return count; x=2; while(x x *= 2; count++; n) n?2 1、11 已知有实现同一功能得两个算法，其时间复杂度分别为O?2?与O?n?，假设现实计算机可连续 n10运算得时间为10秒（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）10次。试问在此条件下，这两个算法可解问题得规模（即n值得范围）各为多少？哪个算法更适宜？请说明理由。 龆鐐雳奮蔹癰帏。 75解：2n ?1012 10n=40 n=16 n?1012 则对于同样得循环次数n，在这个规模下，第二种算法所花费得代价要大得多。故在这个规模下，第一种算法更适宜。颗则砖節吗玑绻。 1、12 设有以下三个函数： f?n??21n4?n2?1000，g?n??15n4?500n3，h?n??500n3.5?nlogn 请判断以下断言正确与否： (1) f(n)就是O(g(n)) (2) h(n)就是O(f(n)) (3) g(n)就是O(h(n)) (4) h(n)就是O(n 3、5 ) (5) h(n)就是O(nlogn) 解：(1)对 (2)错 (3)错 (4)对 (5)错 1、13 试设定若干n值，比较两函数n与50nlog2值大于50nlog222n得增长趋势，并确定n在什么范围内，函数n2得 n得值。 解：n得增长趋势快。但在n较小得时候，50nlog2 当n>438时，n2n得值较大。 ?50nlog2n 1、14 判断下列各对函数 f?n?与g?n?，当n??时，哪个函数增长更快？ (1) (2) f?n??10n2?lnn!?10nf?n???ln?n!??5?2?3?，g?n??2n4?n?7 ，g?n??13n2.5 2(3) (4) f?n??n2.1?n4?1，g?n???ln?n!???n 3f?n??2?n??2n??，g?n??n?2n2??n5 解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 1、15 试用数学归纳法证明： (1) ?ii?1n2?n?n?1??2n?1?/6 ?n?0?