2023考研数据结构复习（三）线性表②

一些用来复习和提高的题，包括选择题、算法设计题等，不定期更新

注：代码为伪代码

目录

一、选择题

二、算法设计题

（1）在一个长度为 n 的顺序表中删除第 i 个元素时（1 <= i <= n）需前移（）个元素

A. n                                                                      B. i - 1

C. n - i                                                                  D. n - i + 1

答案：C

（2）在长度为n的非空线性表中实现插入操作，不是动态分配存储的情况下，i 的合法取值范围为（）

A. 1<= i <= n                                                       B. 1 <= i <= n + 1

C. 0 <= i <= n - 1                                                 D. 0 <= i <= n

答案：B

二、算法设计题

（1）LA，LB为两个集合A和B，现求一个集合A = A ∪ B（数据结构C语言版（严蔚敏）P20）

void union(List &La, List &Lb){
    La_len = ListLengh(La);
    Lb_len = ListLengh(Lb);          //获取长度
    for(i = 1; i <= Lb_length; i++){
        e = GetElem(Lb, i);       //获取Lb中的一个元素
        if(LocateElem(La ,e) == -1){     //判断La中是否有该元素，如果没有，则插入La中
            ListInsert(La, ++La_len, e);
        }
    }
}

（2）已知LA，LB中的数据元素按值非递减排列，合并LA，LB为一个新的线性表LC，且LC中的数据元素仍然非递减有序，如LA  =（3，5，8，11），LB  =（2，6，8，9，11，15，20），则LC  =（2，3，5，6，8，8，9，11，11，15，20）（数据结构C语言版（严蔚敏）P20）

void MergeList(List &La, List &Lb， List &Lc){
    initList(Lc);
    i = j = 1;
    k = 0;    //i指La，j指Lb，k指Lc
    La_length = ListLength(La);
    Lb_length = ListLength(Lb);
    while((i < La_length) && (j < Lb_length)){//La，Lb非空
        GetElem(La, i, ei);
        GetElem(La, j, ej);
        if(ei < ej){     //比较哪个大，谁小就将其插入线性表LC
            ListInsert(Lc, ++k, ei);
            i++;
        } else{
            ListInsert(Lc, ++k, ej);
            j++;
        }
    }
    while(i <= La_len){   //La还没插入完
        GetElem(La, i, ei);
        ListInsert(Lc, ++k, ei);
    }
    while(j <= Ln_len){    //Lb还没插入完
        GetElem(Lb, i, ej);
        ListInsert(Lc, ++k, ej);
    }
}

（3）实现顺序表插入算法（数据结构C语言版（严蔚敏）P24）

Status ListInsert_Sq(SqList &L, int i, ElemType e){
    if(i < 1 || i > L.length + 1) return ERROR;          //判断插入位置是否合法
    if(L.length >= L.MaxSize){     
        //判断顺序表是否满，此处动态分配，若不能动态分配，直接ERROR
        newbase = （ElemType*）realloc(L.data, 
                                      (L.MaxSize + LISTINCREASEMENT) * sizeof(LNode));
        //LISTINCREASEMENT是每次再分配内存时的大小增量，如一次再分配10个节点长度的内存
        if(!newbase) exit(OVERFLOW);                    //存储分配失败
        L.data= newbase;                                //分配新基址
        L.MaxSize += LISTINCREASEMENT;
        //return ERROR                                  //如果是静态存储分配的话
    }
    q = &(L.data[i-1]);                                 //获取插入位置
    for(p = &(L.data[L.length-1]); p >= q; --p){
        *(p + 1) = * p;                                 //插入位置及之后位置后移
    }
    *q = e;                                             //此处是地址
    ++L.length;
    return OK;
}

（4）实现顺序表删除算法，删除第i个元素（数据结构C语言版（严蔚敏）P24）

Status ListDelete_Sq(SqList &L, int i, ElemType &e){
    if((i < 1) || (i > L.length)) return ERROR   //删除位置合法
    p = &(L/elem[i-1]);  //p为被删除的元素的位置
    e = *p;
    q = L.elem + L.length -1;   // q为表尾元素的位置
    for(++p; p <= q; ++p){
        *(p - 1) = *p;
    }
    --L.length;
    return OK;
}

（5）从顺序表中删除具有最小值的元素（唯一），并由函数进行返回，空出的位置由最后一个元素填补，若顺序表为空，则提示错误并退出运行（王道2023数据结构 P18）

bool Del_Min(sqList & L, ElemType &e){
    if(L.length == 0){
        return false;
    }
    e = L.data[0]; //初始化最小值为顺序表第一个元素
    int pos = 0; //设置位置指针
    for(int i = 1; i < L.length; i++){
        if(L.data[i] < e){
            e = L.data[i];
            pos = i
        }
    }
    L.data[pos] = L.data[L.length-1]; 用最后一位填充
    L.length--; 减去长度,默认原有的最后一位元素不在顺序表中了，但实际物理存储中仍然在那个位置
    return true;
}

（6）逆置顺序表L，要求算法时间复杂度为O(1)（王道2023数据结构 P18）

void Reverse(SqList &L){
    ElemType temp;
    for(i = 0; i < L.length / 2; i++){
        temp = L.data[i];
        L.data[i] = L.data[L.length-i-1];
        L.data[L.length-i-1] = temp;
    }
}