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

2024-01-03 06:43:58

~~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的顶点的度(注意:可用高级语言,伪代码、流程图作答,任何一种作答方式等效)。

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

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

文章来源:https://blog.csdn.net/2301_79516932/article/details/135352835
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。