WindsorWu's Blog
首页 归档 分类 友链 关于 监测

数据结构期末复习

2024-12-07 笔记

数据结构.cpp

一、单选题

二、填空题

三、简答题

1. 栈与队列的存储及特点（入栈出栈、入队出队）

栈：表尾端为栈顶、表头为栈低、不含元素的空表为空栈、后进先出。

队列：允许插入的一端称为队尾、允许删除的一端称为队头、先进先出。

2. 单链表、双向链表、循环链表的插入、删除

单链表插入
1
2
3
4
s=new LNode;
s->data=’x’;
s->next=p->next;
p->next=s;
单链表删除
1
2
3
q=p->next;
p->next=q->next;
delete q;
双向链表插入
1
2
3
4
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
双向链表删除
1
2
3
p->prior->next=p->next;
p->next->prior=p->prior;
delete p;
循环链表插入
循环链表删除

3. 二叉树遍历（求先中后序序列及恢复二叉树）

P141 2（2）①

设一颗二叉树的先序序列为ABDFCEGH，中序序列为BFDAGEHC。

画出这棵二叉树

先序/后序确定根，中序确定左右

4. 一般树/森林与二叉树的转换

P141 2（2）③

设一颗二叉树的先序序列为ABDFCEGH，中序序列为BFDAGEHC。

将这棵二叉树转换成对应的树（或森林）

将树转换成二叉树的步骤是：
　　（1）加线。就是在所有兄弟结点之间（同一层同一双亲结点的结点间）加一条连线；
　　（2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；
　　（3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明，红色横线连起来的结点作为最左结点的右孩子。

将森林转换为二叉树的步骤是：
　　（1）先把每棵树转换为二叉树；
　　（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

二叉树转换为树是树转换为二叉树的逆过程，其步骤是：
　　（1）若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来；
　　（2）删除原二叉树中所有结点与其右孩子结点的连线；
　　（3）整理（1）和（2）两步得到的树，使之结构层次分明。

二叉树转换为森林比较简单，其步骤如下：

　　（1）先把每个结点与右孩子结点的连线删除，得到分离的二叉树；
　　（2）把分离后的每棵二叉树转换为树；
　　（3）整理第（2）步得到的树，使之规范，这样得到森林。

5. 哈夫曼树及哈夫曼编码/译码

P141 2（3）
设一个权集W={5，2，9，11，8，3， 7}，请画出相应的Huffman树,并计算它的带权路径长度WPL。

6. 图的两种存储：邻接表、邻接矩阵（注意区分图和网的表示方法差别）

P182 2（1）（2）

有向图：邻接表、邻接矩阵看指出（出度）

无向网：邻接表无向看成双向、邻接矩阵带权

7. 图的两种遍历：DFS和BFS

P183 2（3）

深度优先遍历DFS：主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…

广度优先遍历BFS：先遍历第一层(节点 1)，再遍历第二层(节点 2，3，4)，第三层(5，6，7，8)，第四层(9，10)

8. 最小生成树（prim算法、kruskal算法）

P182 2（2）（3）

普里姆算法（Prim算法）不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。

Kruskal算法在图中存在相同权值的边时也有效，不算顶点。

9. 折半查找及决策树

P224 2(1)

顺序存储、有序存放

10. 二叉排序树的构造、插入、删除

对于给定结点的数据集合D={1，11，5，8，3，10，7，13，9}
（1）依次取出D中各数据，构成一棵二叉排序树BT。
（2）求等概率情况下的平均查找长度ASL。
（3）画出在二叉排序树BT中删除“11”后的树的结构。

11. 散列表查找-冲突处理与表构造

Hi = (Hash(key) + di) mod m，（1 ≤ i ≤ m）

线性探测法

其中，m为散列表长度，di = i（i为1,2，…，m-1 线性序列）

二次探测法

增量序列di为12，-12，22，-22，…，q2 二次序列

12. 散列表查找-查找成功与失败的ASL

P225 2（5）（6）

给定结点的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。设散列表的长度为13，散列函数为：H（K）=K Mod 13。试画出线性探测再散列解决冲突时所构造的散列表，并计算平均查找长度。

0 1 2 3 4 5 6 7 8 9 10 11 12
线性探测法查找成功

$$
\frac12(1+\frac1{1-α})
$$

线性探测法查找失败

$$
\frac12(1+\frac1{(1-α)^2})
$$

二次探测法查找成功

$$
-\frac1α\ln{(1-α)}
$$

二次探测法查找失败

$$
\frac1{(1-α)}
$$

13. 直接插入排序，冒泡排序，选择排序，快速排序思想

P263 2 (1)

直接插入排序，冒泡排序，简单选择排序，快速排序每一趟的过程。
已知序列{7，8，6，4，3，2，17，5，15}，请写出采用某种排序法对该序列作升序排序时每一趟的结果。

四、算法题

1. 二叉树（递归思想）

建立二叉树 和 二叉树的遍历算法
二叉树的二叉链表存储简单算法的实现（先序/中序/后序遍历二叉树）。
求结点个数，树深，复制二叉树，求叶片个数
教材p120-122，第5章ppt 46-49页

1
2
3
4
5
typedef  struct  BiTNode
{
char data;
 struct  BiTNode  *lchild , *rchild ;
}BiTNode, *BiTree;
先序遍历
1
2
3
4
5
6
7
8
9
10
void  Treeout(BiTree  T)
{
   //填入实现代码
	if (T) {
        cout << T->data;
        Treeout (T->lchild);
        Treeout (T->rchild);
    }

}
中序遍历
1
2
3
4
5
6
7
8
void InOrder(BiTree T)      //中序遍历
{
    if (T) {
        InOrder(T->lchild);
        cout << T->data;
        InOrder(T->rchild);
    }
}
后序遍历
1
2
3
4
5
6
7
8
void PostOrder(BiTree T)      //后序遍历
{
    if (T) {
        InOrder(T->lchild);
        InOrder(T->rchild);
        cout << T->data;
    }
}
结点的个数
1
2
3
4
int NodeCount(BiTree T) {
    if(T==NULL) return 0;
    else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
叶子结点的个数
1
2
3
4
5
6
7
8
9
10
void CountLeaf(BiTree T) {
    if(T==NULL) {
        return ;
    }
    if(T->lchild==NULL && T->rchild==NULL){
        num_0++;
    }
    CountLeaf(T->lchild);
    CountLeaf(T->rchild);
}
树的深度
1
2
3
4
5
6
7
8
9
10
int Depth(BiTree T) {
    int Tl=0,Tr=0;
    if(T==NULL) return 0;
    else{
        Tl=Depth(T->lchild);
        Tr=Depth(T->rchild);
        if(Tl>Tr) return (Tl+1);
        else return(Tr+1);
    }

交换左右子树
1
2
3
4
5
6
7
8
void swap(BiTree &T) {
    if(T==NULL) return;
    BTNode *temp=T->lchild;
    T->lchild=T->rchild;
    T->rchild=temp;
    swap(T->lchild);
    swap(T->rchild);
}

2. 排序算法（直接插入排序、冒泡排序、简单选择排序、快速排序）

P230-240

直接插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertSort(int r[],int n)
{
    int i,j,key;
    for(i=2;i<=n;i++){
        key=r[i];
        j=i-1;
        while(j>=1&&r[j]>key){
            r[j+1]=r[j];
            j--;
        }
        r[j+1]=key;
        show(r,n);
    }
冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void BubbleSort(int r[],int n)
{
    bool swapped;
    for(int i=1;i<n;i++){
        swapped=false;
        for(int j=n;j>i;j--){
            if(r[j-1]>r[j]){
                swap(r[j-1],r[j]);
                swapped=true;
            }
        }
        show(r,n);
        if(!swapped) break;
    }
}
简单选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void SelectSort(int R[],int n)
{
    for (int i = 1; i <= n - 1; i++)
    {
        int minIndex = i; 
        for (int j = i + 1; j <= n; j++)
        {
            if (R[j] < R[minIndex])
                minIndex = j;
        }
        if (minIndex != i)
        {
            int temp = R[i];
            R[i] = R[minIndex];
            R[minIndex] = temp;
        }
        show(R, n);
    }
}
快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int  QuilckSort(int R[10],int left,int right)
{
    int i,j;
    R[0] = R[left];
    i = left;
    j = right;
    while(i!=j)
    {      
        while(j>i&&R[j]>R[0])
            j--;
        R[i] = R[j];
        while(j>i&&R[i]<R[0])
            i++;
        R[j] = R[i];
    }
    R[i] = R[0];
    show(R,9);
    return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void RealQuickSort(int R[10],int left,int right)
{
    int mid;
    if(left >= right)
    {
        return;
    }
    else
    {
        mid=QuilckSort(R,left,right);
        RealQuickSort(R,left,mid-1);
        RealQuickSort(R,mid+1,right);
    }
}

3. 线性表的基本操作（顺序存储和链式存储）

P25-37

单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct Node
{
   int data;
   struct Node  *next;
 }LNode;
void Show(LNode *L)
{
//填入实现代码
LNode *current = L->next; // 跳过头结点
    while (current != NULL) {
        cout << current->data;
        current = current->next;
    }
}

4. 队列的进队和出队操作。（循环队列和链队列）

循环队列入队
1
2
3
4
5
6
Status EnQueue(SqQueue &Q, QElemType e) { //插入元素e为Q的新的队尾元素
    if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    return OK;  
}
循环队列出队
1
2
3
4
5
6
Status DeQueue(SqQueue &Q, QElemType &e) {//删除Q的队头元素，用e返回其值
    if(Q.front==Q.rear) return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXQSIZE;
    return OK;
}
链队列入队
1
2
3
4
5
6
7
8
9
Status EnQueue(LinkQueue &Q, QElemType e) { //插入元素e为Q的新的队尾元素
    QNode *p;
    p=new QNode;
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;
}
链队列出队
1
2
3
4
5
6
7
8
9
10
Status DeQueue(LinkQueue &Q, QElemType &e) {//删除Q的队头元素，用e返回其值
    QNode *p;
    if(Q.front==Q.rear) return ERROR;
    p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)   Q.rear=Q.front;
    delete p;
    return OK;
}

5. 栈的进栈和出栈操作（顺序存储和链式存储）

顺序栈的进栈
1
2
3
4
5
6
Status Push(SqStack &S, SElemType e) {
    if (S.top - S.base == S.stacksize)
        return ERROR;
    *(S.top++) = e;
    return OK;
}
顺序栈的出栈
1
2
3
4
5
6
Status Pop(SqStack &S, SElemType &e) {
    if (S.base == S.top)
        return ERROR;
    e = *(--S.top);
    return OK;
}
链栈的入栈
1
2
3
4
5
6
7
8
Status Push(LinkStack &S, SElemType e) {
    LinkStack p;
    p = new StackNode;
    p->data = e;
    p->next = S;
    S = p;
    return OK;
}
链栈的出栈
1
2
3
4
5
6
7
8
9
10
Status Pop(LinkStack &S, SElemType e) {
    LinkStack p;
    p = new StackNode;
    if(S==NULL) return ERROR;
    e=S->data;
    p=S;
    S=S->next;
    delete p;
    return OK;
}

本文作者：WindsorWu

本文链接： https://blog.nekolin.top/2024/12/07/DataStructureFE/

文章默认使用 CC BY-NC-SA 4.0 协议进行许可，使用时请注意遵守协议。

更新于 2024-12-10

# C/C++
上一篇
软件工程概论
下一篇
2023年暑假记录

评论

您所在的地区可能无法访问 Disqus 评论系统，请切换网络环境再尝试。