基本概念

4 . 一个算法应该是（ ）。

A. 程序
B. 问题求解步骤的描述
C. 要满足5个基本特性
D. A 和C

5.下面关千算法说法正确的是（ ） 。

A. 算法最终必须由计算机程序实现
B . 为解决某问题的算法同为该问题编写的程序含义是相同的
C . 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的

7. 下述（ ）与数据的存储结构无关。

A. 栈
B. 双向链表
C. 散列表
D. 线索树

11.连续存储设计时，存储单元的地址( )。

A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续

12. 以下属于逻辑结构的是( )。

A. 顺序表
B. 散列表
C. 有序表
D. 单链表

13.T(n)=1000，求O(n);

O(n)=1

14.如下函数mergesort(）执行的时间复杂度为多少？假设函数调用被写为mergesort(1,n) ，函数merge()的时间复杂度为O(n) 。

顺序表

见81行后

//库函数头文件包含
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//函数状态码定义
#define OK          1
#define OVERFLOW   -2
typedef int Status;
//顺序表的存储结构定义
#define LIST_INIT_SIZE  5   //初始化大小
#define LISTINCREMENT   1   //每次增加的大小
typedef int ElemType;  //假设线性表中的元素均为整型
typedef struct {
    ElemType *elem;   //存储空间基地址 //因为是malloc()得到的连续的地址空间，所以也可以当作是整个顺序表（数组）的地址
    int length;       //表中元素的个数
    int listsize;     //表容量大小
} SqList;    //顺序表类型定义
Status ListInsert_Sq(SqList &L, int pos, ElemType e);   //插入
Status ListDelete_Sq(SqList &L, int pos, ElemType &e);  //删除
int ListLocate_Sq(SqList L, ElemType e);    //定位
void ListPrint_Sq(SqList L);    //遍历打印
//结构初始化与销毁操作
Status InitList_Sq(SqList &L) {
    //初始化L为一个空的有序顺序表
    L.elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L.elem)exit(OVERFLOW);
    L.listsize = LIST_INIT_SIZE;
    L.length = 0;
    return OK;
}
int main() {
    SqList L;
    if (InitList_Sq(L) != OK) {
        printf("InitList_Sq: 初始化失败！！！\n");
        return -1;
    }
    for (int i = 1; i <= 100; ++i)
        ListInsert_Sq(L, i, i);
    int operationNumber;  //操作次数
    scanf("%d", &operationNumber);
    while (operationNumber != 0) {
        int operationType;  //操作种类
        scanf("%d", &operationType);
        if (operationType == 1) {  //增加操作
            int pos, elem;
            scanf("%d%d", &pos, &elem);
            ListInsert_Sq(L, pos, elem);
        } else if (operationType == 2) {  //删除操作
            int pos;
            ElemType elem;
            scanf("%d", &pos);
            ListDelete_Sq(L, pos, elem);
            printf("%d\n", elem);
        } else if (operationType == 3) {  //查找定位操作
            ElemType elem;
            scanf("%d", &elem);
            int pos = ListLocate_Sq(L, elem);
            if (pos >= 1 && pos <= L.length)
                printf("%d\n", pos);
            else
                printf("NOT FIND!\n");
        } else if (operationType == 4) {  //输出操作
            ListPrint_Sq(L);
        }
        operationNumber--;
    }
    return 0;
}
/* 请在这里填写答案 */
Status ListInsert_Sq(SqList &L, int pos, ElemType e) {
    L.length++;
    if (L.length >= L.listsize) {
        L.elem = (ElemType *) realloc(L.elem,
                                      sizeof(int) * (L.listsize + LISTINCREMENT));  //realloc()函数会重新分配连续空间然后复制原来空间中的元素
        L.listsize = L.listsize + LISTINCREMENT;
    }
    if (L.length == 1) {
        L.elem[0] = e;
    } else {
        for (int i = L.length; i >= pos; i--) {
            L.elem[i] = L.elem[i - 1];
        }
        L.elem[pos - 1] = e;
    }
}
Status ListDelete_Sq(SqList &L, int pos, ElemType &e) {  //pos-1==数组下标
    e = L.elem[pos - 1];
    for (int i = pos - 1; i < L.length; i++) {
        L.elem[i] = L.elem[i + 1];
    }
    L.length--;
}
int ListLocate_Sq(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i] == e) {
            return i + 1;
        }
    }
    return -1;
}
void ListPrint_Sq(SqList L) {
    for (int i = 0; i < L.length; i++) {
        if (i == 0) {
            printf("%d", L.elem[i]);
            continue;
        } else {
            printf(" %d", L.elem[i]);
        }
    }
    printf("\n");
}