习题1
1-1 什么是数据、数据元素、原子元素？它们有何区别？
1-2 什么是数据类型、原子数据类型、结构数据类型、抽象数据类型、虚拟数据类型、固有数据类型？它们之间的关系怎样？
1-3 数据结构与软件的关系是什么？解决实际问题时，选取（设计）数据结构的总则是什么？
1-4 如何理解数据（或抽象数据）类型及其实例？C++语言的数据类型char与boolean的值域是什么？分别定义了什么操作？
1-5 抽象数据类型（ADT）与面向对象方法有何关系？ADT的说明如何编写？使用ADT的优点有哪些？
1-6 为什么说数据元素之间的逻辑关系是数据内部组织的主要方面？什么是随机存取、顺序存取、直接存取？
1-7 逻辑结构与存储结构是什么关系？有何区别？
1-8 运算与运算实现是什么关系？有哪些相同点和不同点？什么是操作？
1-9 试描述数据结构的概念与高级程序设计语言中数据类型概念的区别。C++语言与Visual C++语言的区别。
1-10 举一个数据结构的例子，叙述其逻辑结构、存储结构和运算三方面的内容。
1-11 算法与程序有何不同？为何要引出算法的概念？如何评价算法的时间、空间复杂度及算法的好坏？
1-12 分析下列程序段的时间复杂度。
void odd（int n）
{ int i,j,x=0,y=0；
for（i=1;i<=n;i++）
if odd（i）
{ for（j=i;j<=n;j++）x++;
for（j=1;j<=i;j++）y++;
}
}
void recursive（int n）
{ if（n<=1） return 1; else return（recursive（n-1）+recursive（n-1））;}
1-13 设n为正整数，试确定下列各程序段中带下划线语句的频度。
（1）int i=1, k=0; while（i<=n-1）{ k=k+10*i; i=i+1; }
（2）int i=1, j=0; while（（i+j）<=n）if（i>j）j++; else i++;
（3）int x=91, y=100;
while（y>0）{ if（x>100）{ x=x-10; y--; } else x++; }
（4）int x=0;
for（int i=1; i<=n; i++）
for（int j=1; j<=i; j++）
for（int k=1; k<=j; k++）x++;
（5）int x=n, y=0; //n>1
while（x>=（y+1）*（y+1））y++;
1-14 考虑下列函数：f1(n)=n2，f2(n)=n2+1000n，f3(n)=n（如果n是奇数）或者f3(n)=n3（如果n是偶数），f4(n)=n（如果n≤100）或者f4(n)=n3（如果n≥100），指出对于不同的i和j（比如i, j=1, 2, 3, 4），是否存在fi(n)=O(fj(n))，fi(n)=Ω(fj(n))，Ω 的定义见习题1-17。
1-15 设有数据的逻辑结构为K=(D, S)，D={d1, d2, …, d9}，S={<d1, d2>,<d1, d8>,<d2, d3>,<d2, d4>,<d2, d5>,<d3, d9>,<d5, d6>,<d8, d9>,<d9, d7>,<d4, d7>,<d4, d6>}。试画出这个逻辑结构的图示。并确定对应关系集合S中哪些结点是开始结点，哪些结点是终端结点？
1-16 考虑以下函数：g1(n)=n2（当n为偶数时）或者g1(n)=n3（当n为奇数时），g2(n)=n（当0≤n≤100 时），g2(n)=n3（当n＞100 时），g3(n)=n2.5，指出gi(n)是否为O(gj(n))，以及gj(n)是否为Ω(gi(n))，i, j=1, 2, 3（O的定义见例1-7，Ω的定义见习题1-17）。
1-17 设T1(n)是Ω (f(n))，T2(n)是Ω (g(n))，问以下论断是否正确：
① T1(n)+T2(n)是Ω{max[f(n)×g(n)]}；
② T1(n)+T2(n)是Ω{max[f(n)×g(n)]}。
（Ω 的概念定义为：若f(n)是Ω[g(n)]，则表示存在着常数n0与c＞0，使得f(n)≥c×g(n)对于一切n≥n0成立。）
1-18 指出以下算法中的错误和低效（费时）之处，并将它改写成为一个既正确又高效的算法。
int last,i,k;int a[n]; //本算法从a[0]～a[last]中删除第i个元素起的k个元素
if（（i<0）||（i>last）||（k<0）||（last>n-1））
{ cerr<<“error:argument error”<<endl: exit（1）; }
else for（int count=1;count<=k;count++） //删除一个元素
for（int j=last;j>=i+1;j--） { a[j-1]=a[j];last--;}
1-19 已知k阶Fibonacci序列定义为F0=0, F1=0, …, Fk-2=0, Fk-1=1, Fn=Fn-1+Fn-2+…+Fn-k, n=k, k+1, …，试编写求任意k阶Fibonacci序列的算法（要求序列计算时，Fn的值不大于105），并分析算法时间复杂度。
1-20 设计求解下列问题的C++语言算法，并分析其最坏情况时间复杂度及其数量级。①在数组A[1…n]中查找值为k的元素，若找到，则输出其位置i（1≤i≤n），否则输出0 作为标志。② 找出数组A[1…n]中元素的最大值和次最大值（本题以数组元素的比较为标准操作）。
1-21 试采取逐步求精的方法用C++语言编写求最大公因子的算法，并分析算法的时间复杂度。
1-22 试编写一个求多项式Pn(x)=anxn +an-1xn-1+…+a1x +a0的值Pn(x0)的算法，要求所用的乘法次数最小，并确定算法中每一个语句的频度及整个算法的时间复杂度。
1-23 要求将整数1～100 的平方根分成两组，每组各50个数，使得一组中的各数之和尽可能接近另一组的各数之和。如果只有两分钟的机时可用来解决这个问题，那么应进行什么运算？
1-24 设下面过程的参数n取值为2的正方幂，亦即n=2, 4, 8, 16, …。当过程终止时，变量count的值作为n的函数应如何表示？
int n; int x=2,count=0; while（x<n） { x=x*2; count++;}
1-25 设A是一个整数数组，函数max(i, n)可求出A中从i到i+n-1的单元中的最大整数。为简便起见，可假设n是2的方幂。
int max（int i, int n）
{ int m1,m2;
if（n==1）return A[i];
else { m1=max（i,n/2）;m2=max（i+n/2,n/2）;
if（m1<m2） return m2;else return m1;}
}
（1）设max在最坏情况下的运行时间函数为T(n)，这里的n是max的第二个参数，表示要在n个整数中寻找最大的整数。试列出T(n)满足的递归方程，也即用若干常数及若干项T(j)（j<n）代表程序max中各语句的运行时间，并用它们表示整个程序的运行时间T(n)。
（2）在大O意义下给出T(n)的一个“精确”上界，即它也可作为大Ω意义下的下界。要求所给出的表达式尽可能简单。
1-26 某单位每个职工都有一张职工登记表。设想在任何组合的已知条件下（如只知道姓名、知道姓名和单位、知道姓名和性别，等等），如何存放这些登记表，以便能用最快的速度找到某个人的登记表。
1-27 某班本学期开设政治、数学、英语、数据结构和计算机原理5 门课程。n个学生平均成绩分优、良、及格和不及格4个等级：90分以上为优，80分至90分为良，60分至79分为及格，60分以下为不及格。用C++语言写出统计分析算法，并分析算法的时间复杂度。
1-28 已知有实现同一功能的两个等法，其时间复杂度分别为O(2n)及O(n10)。假设计算机可连续运行107秒，每秒可执行C++基本语句105次。试问：在此条件下，可解问题的规模是多大，即n的范围约为多少？用什么算法好，并说明理由是什么。
1-29 对下列4 种折半查找程序进行比较，这4个程序哪些是正确的？哪些效率更高？假定下列变量，以及常量n＞0。
程序A：
void binsearchA（int a[n], int x, int &k）
{ int i=0,j=n-1;
while（i<=j）
{ k=（i+j）/2;if（a[k]==x）return;if（x>a[k]）i=k+1;else j=k-1;}
}
程序B：
void binsearchB（int a[n],int x,int &k）
{ int i=0,j=n-1;
while（i<j）
{ k=（i+j）/2;if（a[k]==x） return;if（x>a[k]）i=k; else j=k; }
}
程序C：
void binsearchC（int a[n],int x,int &k）
{ int i=0,j=n-1;
while（i<=j） { k=（i+j）/2;if（x<=a[k]）j=k-1; if（x>=a[k] i=k+1; }
}
程序D：
void binsearchD（int a[n], int x, int &k）
{ int i=0,j=n-1;
while（i<j） { k=（i+j）/2; if（x<a[k]）j=k; else i=k+1; }
}
（提示：若所查找的元素存在，则程序必须终止于a[k]=x；若不存在具有值x的元素，则程序必须终止于a[k]≠x。）