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

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

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

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/286930.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Debezium发布历史43

Debezium发布历史43

原文地址&#xff1a; https://debezium.io/blog/2018/12/05/automating-cache-invalidation-with-change-data-capture/ 欢迎关注留言&#xff0c;我是收集整理小能手&#xff0c;工具翻译&#xff0c;仅供参考&#xff0c;笔芯笔芯. 通过更改数据捕获自动使缓存失效 2018 年…
阅读更多...
以 RoCE+软件定义存储同时实现信创转型与架构升级

以 RoCE+软件定义存储同时实现信创转型与架构升级

目前&#xff0c;不少企业数据中心使用 FC 交换机和集中式 SAN 存储&#xff08;以下简称“FC-SAN 架构”&#xff09;&#xff0c;支持核心业务系统、数据库、AI/ML 等高性能业务场景。而在开展 IT 基础架构信创转型时&#xff0c;很多用户受限于国外交换机&#xff1a;FC 交换…
阅读更多...
20 太空漫游

20 太空漫游

效果演示 实现了一个太空漫游的动画效果&#xff0c;其中包括火箭、星星和月亮。当鼠标悬停在卡片上时&#xff0c;太阳和星星会变成黄色&#xff0c;火箭会变成飞机&#xff0c;月亮会变成小型的月亮。整个效果非常炫酷&#xff0c;可以让人想起科幻电影中的太空漫游。 Code &…
阅读更多...
SpringBoot—支付—支付宝

SpringBoot—支付—支付宝

一、流程 二、沙箱操作 1.用支付宝账号登录【开放控制平台】创建应用获取 appid 2.选择沙箱模拟环境 3.沙箱应用-》获取appid(一个appid绑定一个收款支付宝账户) 4.利用开发助手工具生成RSA2密钥 公钥&#xff1a;传给支付宝平台 私钥&#xff1a;配置代码中&#xff0c;…
阅读更多...
json解析本地数据，使用JSONObject和JsonUtility两种方法。

json解析本地数据，使用JSONObject和JsonUtility两种方法。

json解析丨网址、数据、其他信息 文章目录 json解析丨网址、数据、其他信息介绍一、文中使用了两种方法作为配置二、第一种准备2.代码块 二、第二种总结 介绍 本文可直接解析本地json信息的功能示例&#xff0c;使用JSONObject和JsonUtility两种方法。 一、文中使用了两种方法…
阅读更多...
[GKCTF 2020]ez三剑客-eztypecho

[GKCTF 2020]ez三剑客-eztypecho

[GKCTF 2020]ez三剑客-eztypecho 考点&#xff1a;Typecho反序列化漏洞 打开题目&#xff0c;发现是typecho的CMS 尝试跟着创建数据库发现不行&#xff0c;那么就搜搜此版本的相关信息发现存在反序列化漏洞 参考文章 跟着该文章分析来&#xff0c;首先找到install.php&#xf…
阅读更多...
Arduino开发实例-AD8232心率监测传感器驱动

Arduino开发实例-AD8232心率监测传感器驱动

AD8232心率监测传感器驱动 文章目录 AD8232心率监测传感器驱动1、AD8232介绍2、硬件准备及接线3、驱动实现1、AD8232介绍 AD8232 传感器可为您提供心电图或 ECG 信号监测。 分析这些信号可以提供有关心脏功能的有用信息，例如心跳率、心律和其他有关心脏状况的信息。 该模块可…
阅读更多...
word 常用功能记录

word 常用功能记录

word手册 多行文字对齐标题调整文字间距打钩方框插入三线表插入参考文献自动生成目录 多行文字对齐 标题调整文字间距 打钩方框 插入三线表 插入一个最基本的表格把整个表格设置为无框线设置上框线【实线1.5磅】设置下框线【实线1.5磅】选中第一行&#xff0c;设置下框线【实线…
阅读更多...
Mysql的基本用法（上）非常详细、快速上手

Mysql的基本用法（上）非常详细、快速上手

上篇结束了java基础&#xff0c;本篇主要对Mysql中的一些常用的方法进行了总结&#xff0c;主要对查询方法进行了讲解&#xff0c;包括重要的多表查询用到的内连接和外连接等&#xff0c;以下代码可以直接复制到可视化软件中&#xff0c;方便阅读以及练习&#xff1b; SELECT *…
阅读更多...
Springer Latex正文参考文献样式改为数字

Springer Latex正文参考文献样式改为数字

用过爱斯唯尔的latex&#xff0c;正文参考文献都是数字&#xff0c;第一次用Springer Latex的参考文献竟然是authoryear&#xff0c;如下&#xff1a; 将这种样式变回序号样式&#xff1a; &#xff08;1&#xff09;使用这个documentclass&#xff08;此为双栏&#xff09; …
阅读更多...
Mnist手写体数字数据集介绍与在Pytorch中使用

Mnist手写体数字数据集介绍与在Pytorch中使用

1.介绍 MNIST&#xff08;Modified National Institute of Standards and Technology&#xff09;数据集是一个广泛用于机器学习和计算机视觉研究的常用数据集之一。它由手写数字图像组成&#xff0c;包括0到9的数字&#xff0c;每张图像都是28x28像素的灰度图像&#xff0c;图…
阅读更多...
Unity游戏资源更新（AB包）

Unity游戏资源更新（AB包）

目录 前言&#xff1a; 一、什么是AssetBundle 二、AssetBudle的基本使用 1.AssetBundle打包 2.BuildAssetBundle BuildAssetBundleOptions BuildTarget 示例 3.AssetBundle的加载 LoadFromFile LoadFromMemory LoadFromMemoryAsync UnityWebRequestAsssetBundle 前…
阅读更多...
设计模式：单例模式

设计模式：单例模式

文章目录 1、概念2、实现方式1、懒汉式2、饿汉式3、双检锁/双重校验锁4、登记式/静态内部类5、枚举6、容器实现单例 1、概念 单例模式&#xff08;Singleton Pattern&#xff09;是 Java 中最简单的设计模式之一。这种类型的设计模式属于创建型模式&#xff0c;它提供了一种创…
阅读更多...
Linux引导过程与服务控制

Linux引导过程与服务控制

目录 一、操作系统引导过程 1. 过程图示 2. 步骤解析 2.1 bios 2.2 mbr 2.3 grup 2.4 加载内核文件 3. 过程总结 4. centos6和centos7启动区别 5. 小结 二、服务控制及切换运行级别 1. systemd核心概念 2. 运行级别 3. Systemd单元类型 4. 运行级别所对应的Syst…
阅读更多...
YOLOv8改进 | 检测头篇 | DynamicHead原论文一比一复现 （不同于网上版本，全网首发）

YOLOv8改进 | 检测头篇 | DynamicHead原论文一比一复现 （不同于网上版本，全网首发）

一、本文介绍 本文给大家带来的改进机制是DynamicHead(Dyhead)，这个检测头由微软提出的一种名为“动态头”的新型检测头，用于统一尺度感知、空间感知和任务感知。网络上关于该检测头我查了一些有一些魔改的版本，但是我觉得其已经改变了该检测头的本质，因为往往一些细节上才…
阅读更多...
【安卓的签名和权限】

【安卓的签名和权限】

Android 编译使用哪个key签名&#xff1f; 一看Android.mk 在我们内置某个apk的时候都会带有Android.mk&#xff0c;这里面就写明了该APK使用的是什么签名&#xff0c;如&#xff1a; LOCAL_CERTIFICATE : platform表明使用的是platform签名 LOCAL_CERTIFICATE : PRESIGNED…
阅读更多...
MPI并行程序设计 —— C 和 fortran 环境搭建 openmpi 示例程序

MPI并行程序设计 —— C 和 fortran 环境搭建 openmpi 示例程序

1.安装环境 wget https://download.open-mpi.org/release/open-mpi/v4.1/openmpi-4.1.6.tar.g tar zxf openmpi-4.1.6.tar.gz cd openmpi-4.1.6/ 其中 configure 选项 --prefix/.../ 需要使用绝对路径&#xff0c;例如&#xff1a; ./configure --prefix/home/hipper/ex_open…
阅读更多...
使用UDP和JSON在C#中高效发送结构体数据

使用UDP和JSON在C#中高效发送结构体数据

使用UDP和JSON在C#中高效发送结构体数据 引言 在许多网络编程场景中&#xff0c;我们经常需要在不同的应用程序或服务之间发送和接收数据。UDP&#xff08;用户数据报协议&#xff09;因其低延迟和少开销的特点&#xff0c;在需要快速数据传输的场景中非常有用。本文介绍了如何…
阅读更多...
VS 2022 控制台程序运行时不显示控制台

VS 2022 控制台程序运行时不显示控制台

Visual Studio 2022&#xff0c;C#控制台程序运行时不显示控制台。此外&#xff0c;C#程序修改运行时的程序名。 文章目录 不显示控制台修改运行时的程序名打包成.exe 文件 不显示控制台 1 选中需要项目&#xff0c;右击属性&#xff0c;选中常规。 2 将输出类型从控制台改为…
阅读更多...
介绍两本书《助推》与《耐力》

介绍两本书《助推》与《耐力》

冠历最后一年已经养成了没有冲突的情况下每天跑步、读书的习惯&#xff0c;今天突发奇想&#xff1a;是否重新挑战下每日写作。 ​ 今天介绍两本书。第一本是《助推》&#xff0c;这本书是由于真友 吾真本 的介绍开始读的。 一句话介绍这本书&#xff0c;那就是&#xff1a;如果…
阅读更多...
最新文章

Copyright @ 2022~2023