数据结构复习

第一次测试

第一章绪论

数据元素是数据的基本单位。数据项是是组成数据元素的最小单位。数据对象是性质相同的数据元素的集合。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。①逻辑结构：线性结构，树结构，图结构。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型ADT。

算法的时间复杂度：取决于问题的规模和待处理数据的初态。由嵌套层次最深的语句的频度决定的。空间复杂度：对数据进行操作的辅助存储空间。

1.NlogN^2和NlogN具有相同的增长速度。T NlogN^2=2NlogN≈NlogN

2.N^2logN和NlogN^2具有相同的增长速度。F

3.(NlogN)/1000是O(N)的。F O(NlogN)>O(N)NlogN的增长速度大于N的增长速度，A是B的说明A的增长速度小于B

4.N^2/1000是O(N)的。F A是B的说明A的增长速度小于B,根据函数图像来判断

5.100logN是O(N)的。T

求整数n(n>=0)的阶乘的算法如下，其时间复杂度为（）。

long fact(long n)
{
if (n<=1) return 1；
return n*fact(n-1)；
}

C.Θ(n) 基本语句为n*fact(n-1)；执行次数为n次、

下列代码

for(i=0; i<n; i++)
  for(j=i; j>0; j/=2)
     printf(“%d\n”, j);

的时间复杂度是：D.O(NlogN) 我不知道呀

下面程序段的时间复杂度是（）。

x=90; y=100; while(y>0) if(x>100) { x=x-10; y--; } else x++;A.O(1)    根据代码可知，语句都是只执行l一次

9.下列代码

if ( A > B ) {
    for ( i=0; i<N; i++ )
        for ( j=N*N; j>i; j-- )
            A += B;
}
else {
    for ( i=0; i<N*2; i++ )
        for ( j=N*2; j>i; j-- )
            A += B;
}

的时间复杂度是：

C.O(N3)

10.素数一般指质数。质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的

自然数

//要判断一个整数N（>10）是否素数，我们需要检查3到 sqrt(N)之间是否存在奇数可以整除N。则这个算法的时间复杂度是：
int N;
scanf("%d",&N);
for(int i=3;i<=sqrt(N);i++)
{
	if.......
}

可以理解成循环sqrt(N)次

要判断一个整数N（>10）是否素数，我们需要检查3到N之间是否存在奇数可以整除N。则这个算法的时间复杂度是：A.O(sqrt(N))

第二章线性表

1.顺序表中第一个元素的存储地址是s100，每个元素的长度为L2，则第5n个元素的地址T是（）。T=s+(n-1)*L

2.若设一个顺序表的长度为n，那么，在表中顺序查找一个值为x的元素时，在等概率的情况下，查找成功的数据平均比较次数为 (n+1)/2。P27

3.在向表中第i个元素（1≤i≤n+1）位置插入一个新元素时，为保持插入后表中原有元素的相对次序不变，需要从后向前依次后移 n-i+1个元素。n-(i-1) 共n个元素，前i-1个元素不用动

4.在删除表中第i个元素时，同样地，为保持删除后表中原有元素的相对次序不变，需要从前向后依次前移n-i个元素。要被删除的第i个元素不用变。让后面的把他覆盖就行

#include<stdio.h>
#include<stdlib.h>//前面的std都是一样的 lib lib lib lib
#define MAXSIZE 100
typedef struct
{
   int *elem;//存储空间的基地址。数组指针elem指示顺序表的基地址
   int length;//顺序表的实际长度，可确定不同的顺序表
}SqList;

//顺序表的初始化函数
void InitList(SqList *L,int n)//长度为n，要改变顺序表L，
//形参为指针变量，l是指向顺序表的指针
{
   L->elem=(int*)malloc(sizeof(int)*n);
   //L->elem=(指针类型)malloc(sizeof(原类型int)*n(构造n个整型元素的顺序表空间));
   L->length=n;
   for(int i=0;i<n;i++)
   {
       scanf("%d",&L->elem[i]);
       //此处&为取地址符，与日常的输入语句一样 scanf("%d",&x);
   }
}

//顺序表的取值操作,取第i个元素
int GetElem(SqList L,int i,int *e)//要改变主函数中e的值
{
   //首先判断i值是否合理，若不合理，返回0
   if(i<1||i>L.length) return 0;//return是结束了整个函数，不再往下执行
   e=L.elem[i-1];
   return 1;
}

//顺序表的查找操作,查找元素e,返回位置序号
int LocateElem(SqList L,ElemType e)
{
    //首先判定查找(指定元素)操作的不合法性：无
    int i=0;
    for(;i<L->length;i++)
    {
        if(L.elem[i]==e)
        return i+1;
   }
   return 0;
}

//顺序表的插入(后移)操作,在第i个元素的位置(下标为i-1)，插入元素e
int ListInsert(SqList &L,int i,ElemType e);
{//用的是结构体指针变量，访问成员用箭头运算符还是用点 ?

    //先判断插入位置是否合法，在最后一个元素的后面插入也是合法的
   if(i<1||i>L.length+1) return 0;
   //还有存储空间已满否
   if(L.length==MAXSIZE)
return 0;
    int j;
for(j=L.length-1;j>=i-1;j--)
   {
       L.elem[j+1]=L.elem[j];
   }
    L.elem[i-1]=e;//第i个元素的位置(下标为i-1)
    L.length++;
    return 1;
}

int ListDelete(SqList &L,int i)
{
    //先看删除的位置是否合法
   if(i<1||i>L.length) return 0;//合法性判断
   int j;
   for(j=i-1;j<L.length;j++)
   {
      L.elem[j]=L.elem[j+1];
   }
   //别忘了顺序表长度的变化
L.length--;
    return 1;
}

链表

1.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？仅有尾指针的单循环链表

第一次测试

第一章 绪论

链表

第一章绪论