作业：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依次存放于一维数组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);
2-4 已知顺序表L递增有序。设计一个算法，将a和b插入L中，要求保持L递增有序且以较高的效率实现。
先用折半查法查询位置，然后移动
void insert(int L[],int a,int b)//a<b
{
    int i=0,p,q;
    n= length(L);//L现有长度
    //查确定a、b的位置
    for(;i<n;i++)
    {
        if( L[i]<=a&&(a<L[i+1]||i==n-1) )
        {
            p = i+1; //a的最终位置
            n++;
            break;
        }
    }
    for(;i<n;i++)
    {
        if( L[i]<=b&&(b<L[i+1]||i==n-1) )
        {
            q = i+2; //b的最终位置
            n++;
            break;
        }
    }
    //移动元素，插入a，b
    for(i=n+1;i>q;i--)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。