数据结构与算法期末练习题

邢大头
2023-12-19 20:27:39 569
算法 c语言数据结构期末
文章目录

        数据结构题库
单选题
略
函数题

顺序表的查找操作

int LocateElem(SqList L,ElemType e){
    int sign = 0;
    for(int i = 0; i < L.length; i++){
        if(L.elem[i] == e){
            sign = i + 1;
        }
    }
    return sign;
}


顺序表的插入操作

6-4 顺序表的有序插入操作int ListInsert(SqList &L,int i,ElemType e){
    if(i > L.length + 1 || i < 1 || L.length == MAXSIZE){
        return 0;
    }
    for(int index = L.length; index >= i; index--){
        L.elem[index] = L.elem[index - 1]; 
    }
    L.elem[i-1] = e;
    L.length++;
    return 1;
}


顺序表的删除操作

int ListDelete(SqList &L,int i){
    if(i < 1 || i > L.length){
        return 0;
    }
    for(int index = i-1; index < L.length; index++){
        L.elem[index] = L.elem[index+1];
    }
    L.length--;
    return 1;
}


顺序表的有序插入操作

int SqInsert(SqList &L,ElemType e){
    if(L.length == MAXSIZE){
        return 0;
    }
    int temp = 0;
    for(int index = 0; index < L.length; index++){
        if(e <= L.elem[index]){
            temp = index;
            break;
        }
        temp = L.length;
    }
    for(int index = L.length; index > temp; index--){
        L.elem[index] = L.elem[index-1];
    }
    L.elem[temp] = e;
    L.length++;
    return 1;
}


求顺序表最大值

int GetMax(SqList L){
    if(L.length == 0){
        return 0;
    }
    int max = L.elem[0];
    for(int i = 1; i < L.length; i++){
        if(max < L.elem[i]){
            max = L.elem[i];
        }
    }
    return max;
}


求顺序表最小值

int GetMin(SqList L){
    if(L.length == 0){
        return 0;
    }
    int min = L.elem[0];
    for(int i = 1; i < L.length; i++){
        if(min > L.elem[i]){
            min = L.elem[i];
        }
    }
    return min;
}


顺序表统计大于指定元素值个数

int GetGreater(SqList L, ElemType e){
    int count = 0;
    for(int index = 0; index < L.length; index++){
        if(L.elem[index] > e){
            count++;
        }
    }
    return count;
}


顺序表统计指定元素值个数

int GetCount(SqList L, ElemType e){
    int count = 0;
    for(int index = 0; index < L.length; index++){
        if(L.elem[index] == e){
            count++;
        }
    }
    return count;
}


顺序表统计小于指定元素值个数

int GetSmaller(SqList L, ElemType e){
    int count = 0;
    for(int index = 0; index < L.length; index++){
        if(L.elem[index] < e){
            count++;
        }
    }
    return count;
}


求单链表的表长

int Length ( LinkList L ){
    int length = 0;
    while(L->next != NULL){
        L = L->next;
        length++;
    }
    return length;
}


统计单链表元素出现次数

int GetCount ( LinkList L,ElemType e ){
    int count = 0;
    while(L->next != NULL){
        L = L->next;
        if(L->data == e){
            count++;
        }
    }
    return count;
}


单链表统计正数个数

int PositiveInt(LinkList L){
    int count = 0;
    while(L->next != NULL){
        L = L->next;
        if(L->data > 0){
            count++;
        }
    }
    return count;
}


单链表统计负数个数

int NegativeInt(LinkList L){
    int count = 0;
    while(L->next != NULL){
        L = L->next;
        if(L->data < 0){
            count++;
        }
    }
    return count;
}


单链表统计偶数个数

int EvenNumber(LinkList L){
    int count = 0;
    while(L->next != NULL){
        L = L->next;
        if(L->data % 2 == 0){
            count++;
        }
    }
    return count;
}


单链表统计奇数个数

int OddNumber(LinkList L){
    int count = 0;
    while(L->next != NULL){
        L = L->next;
        if(L->data % 2 != 0){
            count++;
        }
    }
    return count;
}


前缀表达式

void Prefix(BiTree T){
    if(T == NULL){
        return;
    }
    printf("%c ", T->data);
    Prefix(T->lchild);
    Prefix(T->rchild);
}


中缀表达式

void Infix(BiTree T){
    if(T == NULL){
        return;
    }
    Infix(T->lchild);
    printf("%c ", T->data);
    Infix(T->rchild);
}


后缀表达式

void Suffix(BiTree T){
    if(T == NULL){
        return;
    }
    Suffix(T->lchild);
    Suffix(T->rchild);
    printf("%c ", T->data);
}


单链表元素最大值以及结点数

void Count_max (LinkList L ){
    int maxNum = 0, count = 0;
    if(L == NULL || L->next == NULL){
        printf("%d %d", maxNum, count);
        return;
    }
    maxNum = L->next->data;
    while(L->next != NULL){
        L = L->next;
        count++;
        if(maxNum < L->data){
            maxNum = L->data;
        }
    }
    printf("%d %d", maxNum, count);
}


单链表元素最小值以及结点数

void Count_min (LinkList L ){
    int count = 0, minNum = 0;
    if(L->next == NULL){
        printf("%d %d", minNum, count);
        return;
    }
    minNum = L->next->data;
    while(L->next != NULL){
        L = L->next;
        count++;
        if(minNum > L->data){
            minNum = L->data;
        }
    }
    printf("%d %d", minNum, count);
}


中序输出运算式中的运算符，并返回运算符的个数

int count = 0;
int Infix_num(BiTree T){
    if(T == NULL){
        return;
    }
    Infix_num(T->lchild);
    if(T->data >= 33 && T->data <= 47){
        printf("%c ", T->data);
        count++;
    }
    Infix_num(T->rchild);
    return count;
}


统计二叉树叶子结点个数

int count = 0;
int LeafCount ( BiTree T){
    if(T == NULL){
        return;
    }
    if(T->lchild == NULL && T->rchild == NULL){
        count++;
    }
    LeafCount(T->lchild);
    LeafCount(T->rchild);
    return count;
}


统计二叉树度为1的结点个数

int count = 0;
int NodeCount ( BiTree T){
    if(T == NULL){
        return;
    }
    if((!T->lchild && T->rchild) || (T->lchild && !T->rchild)){
        count++;
    }
    NodeCount(T->lchild);
    NodeCount(T->rchild);
    return count;
}


统计二叉树度为2的结点个数

int count = 0;
int NodeCount ( BiTree T){
    if(T == NULL){
        return;
    }
    if(T->lchild != NULL && T->rchild != NULL){
        count++;
    }
    NodeCount(T->lchild);
    NodeCount(T->rchild);
    return count;
}

主观题

哈夫曼树的构建

假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.09，0.16，0.02，0.06，0.32，0.03，0.21，0.11。

试为这8个字母设计哈夫曼编码，请写出哈夫曼树的构建详细过程和编码；(4分）
设计另一种由二进制表示的等长编码方案；（2分）
对于上述实例，分析两种方案的编码长度，分析两种方案的优缺点（3分）


wpl = 21 * 2 + 32 * 2 + 9 * 3 + 11 * 3 + 16 * 3 + 6 * 4 + 2 * 5 + 3 * 5

二叉排序树的构造

已知一组数据元素为（18,3,34,25,12,29,15）

试从空树开始画出按元素排列顺序输入而生成的一棵二叉排序树；
计算查找概率相同情况下，查找成功的平均查找长度。


wpl = 1 * 1 + 2 * 2 + 2 * 3 + 2 * 4

哈希表的构造

已知哈希函数为：H(k)=k%11，表长为11，采用线性探测再散列解决冲突，对下列关键字序列{43,88,27,11,10,23}

构造哈希表；
求出等概率下查找成功时的平均查找长度。


wpl = 1 * 3 + 2 + 3 + 4
联系方式
文章目录