.
作业：1-1,7,8 2-1，2,4,7,9,11,13，19 3-2,3，7,8,13,14 4-3,9,13 5-1,2,6,8 5-1,2,6,7，8，12,14,17 习题1 绪论
1-1 名词解释：数据结构。
数据结构：相互之间存在一定关系的数据元素的集合
1-2 数据结构的基本逻辑结构包括哪四种?
⑴ 集合：数据元素之间就是“属于同一个集合”
⑵ 线性结构：数据元素之间存在着一对一的线性关系 ⑶ 树结构：数据元素之间存在着一对多的层次关系 ⑷ 图结构：数据元素之间存在着多对多的任意关系
1-3 数据结构一般研究的内容不包括( )。
(A) 集合的基本运算
(B) 数据元素之间的逻辑关系
(C) 在计算机中实现对数据元素的操作 (D) 数据元素及其关系在计算机中的表示 选D
数据的逻辑结构、数据的存储结构、数据的运算
1-4 算法包括哪五种特性?
2. 算法的五大特性：√
⑴ 输入：一个算法有零个或多个输入。 ⑵ 输出：一个算法有一个或多个输出。
⑶ 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ⑷ 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 ⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
1-5 简述算法及其时间复杂度。
1.算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。
.
.
算法复杂度(Algorithm Complexity)：算法占用机器资源的多少，主要有算法运行所需的机器时间和所占用的存储空间。
时间复杂度(Time Complexity)：算法运行所需要的执行时间，T(n)= O(f(n))。 空间复杂度(Space Complexity)：算法运行所需要的存储空间度量，S(n)= O(f(n))。
1-6 设数组A中只存放正数和负数。试设计算法，将A中的负数调整到前半区间，正数调整到后半区间。分析算法的时间复杂度。 A[n+1]
For(int i=n-1,j=0;i>j;i--) {
If(a[i]>0) continue; Else { A[n]=A[i]; A[i]=A[j]; A[j]=A[n]; J++; } }
时间复杂度为O(n)
1-7 将上三角矩阵 A=(aij)n?n 的非0元素逐行存于B[(n*(n+1)/2]中，使得 B[k]=aij 且 k=f1(i)+f2(j)+c (f1, f2不含常数项)，试推导函数f1, f2和常数c。 k+1=1+2+3+…+(i-1)+j k=1/2*i*(i-1)+j-1;
1-8 描述下列递归函数的功能。 int F(int m, int n) {
if (n>m) return F(n, m); else if (n==0) return m; else
{
r=m%n;
return F(n, r); }
}
求 m与n的最大公约数 1-9 编写递归算法： 0，m=0且n≥0 g(m, n)=
g(m-1, 2n)+n，m>0且n≥0
.
.
double g(double m,double n) {
If(m==0&&n>=0) return 0; else return g(m-1,2*n)+n; }
1-10 将下列递归过程改写为非递归过程。 void test(int &s) {
int x;
scanf (“%d”, &x); if (x==0) s=0; else
{
test(s); s+=x; } }
习题2 表
2-1 如果长度为n的线性表采用顺序存储结构存储，则在第i (1≤i≤n+1)个位置插入一个新元素的算法的时间复杂度为( )。
(A) O(1) (B) O(n) (C) O(nlog2n) (D) O(n2) B
需要让线性表移动n+1-i个
2-2 在一个有127个元素的顺序表中插入一个新元素，要求保持顺序表元素的原有(相对)顺序不变，则平均要移动( )个元素。
(A) 7 (B) 32 (C) 64 (D) 127
C n/2+1
2-3 将关键字2，4，6，8，10，12，14，16依次存放于一维数组A[0...7]中，如果采用折半查找方法查找关键字，在等概率情况下查找成功时的平均查找长度为( )。
(A) 21/8 (B) 7/2 (C) 4 (D) 9/2 A
3,2,3,1,3,2,3,4
公式法 1*2^0+2*2^1+3*2^2+…+i*2^(n-1);
.