天然博客

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

2023-12-19 20:27:39 562

文章目录

        

数据结构题库

单选题

函数题

  • 顺序表的查找操作
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。

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

topic001.PNG

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

  • 二叉排序树的构造

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

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

topic002.PNG

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

  • 哈希表的构造

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

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

wpl = 1 * 3 + 2 + 3 + 4

联系方式
文章目录