《数据结构》习题集答案（C语言版）严蔚敏

(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

n(n?1) (4) n+(n-1)+(n-2)+...+1=

2 (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=?i?1ni(i?1) 21n1n21n21n =?i(i?1)??(i?i)??i??i

2i?12i?12i?12i?1111n(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) { count = 0; x=2; while(x

return count;

}

解：o(log2n) count=log2n?2

1.11 已知有实现同一功能的两个算法，其时间复杂度分别为O?2n?和O?n10?，假设现实计算机可连续运算的时间为107秒（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）105次。试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由。

解：2n?1012 n10?1012

n=40 n=16

则对于同样的循环次数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(n3.5) (5) h(n)是O(nlogn)

解：(1)对 (2)错 (3)错 (4)对 (5)错

1.13 试设定若干n值，比较两函数n2和50nlog2n的增长趋势，并确定n在什么范围内，函数n2的值大于50nlog2n的值。

解：n2的增长趋势快。但在n较小的时候，50nlog2n的值较大。

当n>438时，n2?50nlog2n

1.14 判断下列各对函数f?n?和g?n?，当n??时，哪个函数增长更快？

(1) f?n??10n2?lnn!?10n，g?n??2n4?n?7

3??(2) f?n???ln?n!??5?，g?n??13n2.5

2(3) f?n??n2.1?n4?1，g?n???ln?n!???n

22(4) f?n??2?n???2n?，g?n??n?n??n5

32解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 1.15 试用数学归纳法证明：

(1) ?i2?n?n?1??2n?1?/6

i?1nn?n?0? ?x?1,n?0?

(2) ?xi??xn?1?1?/?x?1?

i?0n(3) ?2i?1?2n?1

i?1n?n?1? ?n?1?

(4) ??2i?1??n2

i?11.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阶斐波那契序列的定义为

f0?0，f1?0，…，fk?2?0，fk?1?1； fn?fn?1?fn?2???fn?k，n?k,k?1,?

试编写求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

if(i

for(i=k+1;i

for(j=0;j

return p[k]; }

1.18 假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为 项目名称 性别 校名 成绩 得分 编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。

解：

typedef enum{A,B,C,D,E} SchoolName; typedef enum{Female,Male} SexType; typedef struct{

char event[3]; //项目 SexType sex;

SchoolName school; int score; } Component; typedef struct{

int MaleSum; //男团总分 int FemaleSum; //女团总分 int TotalSum; //团体总分 } Sum;

Sum SumScore(SchoolName sn,Component a[],int n) {

Sum temp;

temp.MaleSum=0; temp.FemaleSum=0; temp.TotalSum=0; int i;

for(i=0;i

if(a[i].school==sn){

if(a[i].sex==Male) temp.MaleSum+=a[i].score;

if(a[i].sex==Female) temp.FemaleSum+=a[i].score; } }

temp.TotalSum=temp.MaleSum+temp.FemaleSum; return temp; } 1.19 试编写算法，计算i!*2i的值并存入数组a[0..arrsize-1]的第i-1个分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为maxint，则当n>arrsize或对某个k?1?k?n?，使k!?2k?maxint时，应按出错处理。注意选择你认为较