【期末考试】数据结构大题

~~08|2.03|2|8

^^统计出没带头结点的单链表HL中结点的值等于给定值x的结点数。

int CountX(LNode *HL, ElemType x)
{
    int i = 0;
    LNode *p = HL;
    while (p != NULL)
    {
        if (P->data == x)
            i++;
        p = p->next;
    }
    return i;
}

简答：定义一个i变量来记录节点值等于x的节点个数，然后创建一个LNode类型的指针指向HL节点，当p不等于NULL的时候就继续循环，在循环体内判断当前节点值是否等于x，等于的话i++，反之p指向下一个节点。

~~08|2.03|2|8

^^统计出带头结点的单链表HL中结点的值等于给定值X的结点数。

int CountX(LNode *HL, ElemType x)
{
    int i = 0;
    LNode *p = HL->next;
    while (p != NULL)
    {
        if (P->data == x)
            i++;
        p = p->next;
    }
    return i;
}

简答：定义一个i变量来记录节点值等于x的节点个数，然后创建一个LNode类型的指针指向HL的下一个节点，当p不等于NULL的时候就继续循环，在循环体内判断当前节点值是否等于x，等于的话i++，反之p指向下一个节点。

~~08|2.03|2|8

^^计算出没带头结点的单链表HL中所有结点的值(结点元素类型为整型)之和。

int Sum(LNode *HL)
{
    int sum = 0;
    LNode *p = HL;
    while (p != NULL)
    {
        sum += p->data;
        p = p->next;
    }
    return sum;
}

简答：定义一个sum变量来记录节点值之和，然后创建一个LNode类型的指针指向HL节点，当p不等于NULL的时候就继续循环，在循环体让sum加上当前节点的值，然后p指向下一个节点。

~~08|2.03|2|8

^^计算出带头结点的单链表HL中所有结点的值(元素类型为整型)之和。

int Sum(LNode *HL)
{
    int sum = 0;
    LNode *p = HL->next;

    while (p != NULL)
    {
        sum += p->data;
        p = p->next;
    }

    return sum;
}

简答：定义一个sum变量来记录节点值之和，然后创建一个LNode类型的指针指向HL->next节点，当p不等于NULL的时候就继续循环，在循环体让sum加上当前节点的值，然后p指向下一个节点。

~~08|2.03|2|8

^^计算出没带头结点的单链表HL中所有结点的值(元素类型为整型)之平均值。

float Aver(LNode *HL)
{
    int sum = 0;
    float num = 0;
    LNode *p = HL;
    while (p != NULL)
    {
        sum += p->data;
        num++;
        p = p->next;
    }
    return (float)sum / num;
}

简答：定义一个sum变量来记录节点值之和，一个i变量记录节点个数，然后创建一个LNode类型的指针指向HL节点，当p不等于NULL的时候就继续循环，在循环体让sum加上当前节点的值并且i++，然后p指向下一个节点。

退出循环的时候，返回sum/num。

~~08|2.03|2|8

^^计算出带头结点的单链表HL中所有结点的值(元素类型为整型)之平均值。

float Aver(LNode *HL)
{
    int sum = 0;
    float num = 0;
    LNode *p = HL->next;
    while (p != NULL)
    {
        sum += p->data;
        num++;
        p = p->next;
    }
    return (float)sum / num;
}

简答：定义一个sum变量来记录节点值之和，一个i变量记录节点个数，然后创建一个LNode类型的指针指向HL->next节点，当p不等于NULL的时候就继续循环，在循环体让sum加上当前节点的值并且i++，然后p指向下一个节点。

退出循环的时候，返回sum/num。

~~08|6.03|2|8

^^设计先序遍历二叉树的算法。

typedef struct node
{
    datatype data;
    struct node *lchild, *rchild;
} bitree;

void Preorderbitree(bitree *bt)
{
     if(bt==NULL) return;
     printf("%d ",bt->data);
     Preorder(bt->lchild);
     Preorder(bt->rchild);
}

二叉树的前序遍历：中->左->右 记住，这个前、中、后都是相对于中间这个节点的。

简答：先判断当前节点是否为空，如果为空，直接返回，如果不为空，打印当前节点，然后递归左子树和右子树。

下图的前序遍历：A->B->D->E->C->F->G

下图的中序遍历：D->B->E->A->F->C->G

下图的后序遍历：D->E->B->F->G->C->A

~~08|6.03|2|8

^^设计中序遍历二叉树的算法。

typedef struct node
{
    datatype data;
    struct node *lchild, *rchild;
} bitree;

void Preorderbitree(bitree *bt)
{
     if(bt==NULL) return;
     Preorder(bt->lchild);
     printf("%d ",bt->data);
     Preorder(bt->rchild);
}

二叉树的中序遍历：左->中->右 记住，这个前、中、后都是相对于中间这个节点的。

简答：先判断当前节点是否为空，如果为空，直接返回，如果不为空，然后递归左子树，左子树遍历到头了返回上一层打印节点，然后递归右子树。

~~08|6.03|2|8

^^设计后序遍历二叉树的算法。

typedef struct node
{
    datatype data;
    struct node *lchild, *rchild;
} bitree;

void Preorderbitree(bitree *bt)
{
     if(bt==NULL) return;
     Preorder(bt->lchild);
     printf("%d ",bt->data);
     Preorder(bt->rchild);
}

二叉树的后序遍历：左->右->中 记住，这个前、中、后都是相对于中间这个节点的。

简答：先判断当前节点是否为空，如果为空，直接返回，如果不为空，然后递归左子树，左子树遍历到头了然后递归右子树，递归完了右子树就打印。

~~08|6.03|3|8

^^设计按层次遍历二叉树的算法。

typedef struct node
{
    datatype data;
    struct node *lchild, *rchild;
} bitree;

void Levelorder(bitree T)
{

    int front = 0, rear = 1;
    BinTNode *cq[Max], *p;
    cq[1] = T;
    while (front != rear)
    {
        front = (front + 1) % NodeNum;
        p = cq[front];
        printf("%c ", p->data);
        if (p->lchild != NULL)
        {
            rear = (rear + 1) % NodeNum;
            cq[rear] = p->lchild;
        }
        if (p->rchild != NULL)
        {
            rear = (rear + 1) % NodeNum;
            cq[rear] = p->rchild;
        }
    }
}

首先当根节点入队列，然后进入循环，循环结束条件为队列为空，进入循环之后，让队列出队，将出队的节点的左右节点加入队列当中，循环往复。

~~08|6.03|2|8

^^设计求二叉树叶子结点个数的算法。

typedef struct node
{
    datatype data;
    struct node *lchild, *rchild;
} bitree;

int CountLeaf(bitree *bt)
{
    int count;
    if (bt == NULL)
        return 0;

    if (bt->lchild == NULL && bt->rchild == NULL)
        return (1);

    count = CountLeaf(bt->lchild) + CountLeaf(bt->rchild);
    return count;
}

也可以利用前序遍历，找到一个节点的左右节点都是NULL的时候，count+1；

~~08|6.03|2|8

^^设计判断两个二叉树是否相同的算法。

typedef struct node
{
    datatype data;
    struct node *lchild, *rchild;
} bitree;

int Judgebitree(bitree *bt1, bitree *bt2)
{
    if (bt1 == 0 && bt2 == 0)
        return (1);
    else if (bt1 == 0 || bt2 == 0 || bt1->data != bt2->data)
        return (0);
    else
        return (judgebitree(bt1->lchild, bt2->lchild) * judgebitree(bt1->rchild, bt2->rchild));
}

记录前序遍历的结果，看结果是否相同

~~08|7.03|2|8

^^编写一个算法，求出邻接表表示的有向图中序号为numb的顶点的出度(注意：可用高级语言，伪代码、流程图作答，任何一种作答方式等效)。

int OutDegree(GraphL &gl, int numb)
{
    int OutDegree(GraphL &gl, int numb)
    int d = 0, i;
    vexnode *p gl.adjlist[numb];
    while (p != NULL)
    {
        d++;
        p = p->next;
    }
    return (d);
}

无向图的度：当前节点相连的边的个数

有向图的出度：以当前节点的箭头出去的个数，也就是当前节点是多少个箭头的末尾

有向图的入读：被多少个箭头指向的个数

有向图的度：出度的个数+入度的个数

有向图的出度，也就是当前节点指出去多少个箭头：

遍历以这个节点为头节点的链表，这个链表的长度也就是这个节点的出度。

~~08|7.03|2|8

^^编写一个算法，求出邻接表表示的有向图中序号为numb的顶点的入度(注意：可用高级语言，伪代码、流程图作答，任何一种作答方式等效)。

int InDegree(GraphL &gl, int numb)
{
    int InDegree(GraphL &gl, int numb)
    int d = 0, i;
    vexnode *p = gl.adjlist[numb];
    for (i = 0; i < gl.vexnum; i++)
    {
        p = gl.adjlist[i];
        while (p != NULL)
        {
            if (p->vertex = = numb)
                d++;
            p = p->next;
        }
    }
    return (d);
}

有向图的入度：也就是有多少个箭头指向这个节点。

遍历所有的链表，找到这个节点出现多少次，出现的次数就是当前节点的入度。

~~08|7.03|2|8

^^编写图的深度优先搜索算法(注意：可用高级语言，伪代码、流程图作答，任何一种作答方式等效)。

bool st[1024];

int dfs(int u)
{
    st[u]=true;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            dfs(j);
        }
    }
}

用一个st数组来记录当前节点是否被遍历过，false为没有遍历过，true为遍历过了。

依次遍历每一个链表，如果当前节点没有被遍历，那么递归搜索这个节点的链表，循环往复。

~~08|7.03|2|8

^^编写图的广度优先搜索算法(注意：可用高级语言，伪代码、流程图作答，任何一种作答方式等效)。

用一个st数组来记录当前节点是否被遍历过，false为没有遍历过，true为遍历过了。

一次遍历每一个链表的节点，如果当前节点没有被遍历，就输出，遍历过了就遍历下一个节点。

比如这个链表
1: 4->7->2->-1
2: 5->8->1->-1
3: 9->4->-1
4: 6->3->1->-1
5: 2->-1
6: 4->-1
7: 1->-1
8: 2->-1
9: 3->-1
深度优先:先从1开始，然后走到4，4没有被遍历过，跳到4号链表，6没有遍历过，跳到4号链表，但是4号已经遍历过了，所以回到6号链表，6号链表中4的下一个是-1表示NULL，6号链表继续回到上一层4号链表，然后继续走4号链表的3节点，然后跳到3号链表，循环往复

广度优先:一次遍历1、2、3、4、5、6、7、8、9号链表中的所有内容
一直走完1号链表才去2号链表

~~08|7.03|2|8

^^编写一个算法，求出邻接表表示的无向图中序号为numb的顶点的度(注意：可用高级语言，伪代码、流程图作答，任何一种作答方式等效)。

无向图的度就是当前节点有多少个边：

遍历所有的链表，找当前节点出现了多少次，出现的次数就是该节点的度

~~08|7.03|3|8

^^编写一个算法，求出邻接表表示的有向图中序号为numb的顶点的度(注意：可用高级语言，伪代码、流程图作答，任何一种作答方式等效)。

有向图的度就是当前节点的入度+出度

遍历所有的链表，找当前节点出现的次数+以该节点为头节点的链表的长度