数据结构-函数题

6-2.求二叉树的高度

本题要求给定二叉树的高度。

函数接口定义：

int GetHeight( BinTree BT );
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};

要求函数返回给定二叉树BT的高度值。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */
int GetHeight( BinTree BT );int main()
{BinTree BT = CreatBinTree();printf("%d\n", GetHeight(BT));return 0;
}
/* 你的代码将被嵌在这里 */

 

输出样例（对于图中给出的树）：

4

 求树的高度的代码 

/*分治思想求二叉树的高度
1.bt为空，则高度为0
2.bt非空，其高度应为其左右子树高度的最大值加1 
*/ 
int GetHeight( BinTree BT )
{int hl,hr,h;if(BT!=NULL){hl=GetHeight(BT->Left);hr=GetHeight(BT->Right);h=hl>hr?hl:hr;return h+1;} elsereturn 0;//若为空树 
}

R6-1 求采用邻接矩阵作为存储结构的无向图各顶点的度 

本题要求实现一个函数，输出无向图每个顶点的数据元素的值，以及每个顶点度的值。

函数接口定义：

void degree(MGraph G);

 G为采用邻接矩阵作为存储结构的无向图。

裁判测试程序样例：

#include <stdio.h>
#define MVNum 100                 //最大顶点数 
typedef struct{ char vexs[MVNum];           //存放顶点的一维数组 int arcs[MVNum][MVNum];     //邻接矩阵 int vexnum,arcnum;          //图的当前顶点数和边数 
}MGraph; 
void degree(MGraph G);
void CreatMGraph(MGraph *G);/* 创建图 */
int main()
{MGraph G;CreatMGraph(&G);degree(G);return 0;
}
void CreatMGraph(MGraph *G)
{int i,j,k;scanf("%d%d",&G->vexnum,&G->arcnum);getchar();for(i=0;i<G->vexnum;i++)scanf("%c",&G->vexs[i]);for(i=0;i<G->vexnum;i++)for(j=0;j<G->vexnum;j++)G->arcs[i][j]=0;for(k=0;k<G->arcnum;k++){  scanf("%d%d",&i,&j);     G->arcs[i][j]=1; G->arcs[j][i]=1; }
}/* 请在这里填写答案 */

输入样例：

例如无向图

无向图.png

第一行给出图的顶点数n和边数e。第二行给出n个字符，表示n个顶点的数据元素的值。后面是e行，给出每一条边的两个顶点编号。

4 5
ABCD
0 1
0 2
1 2
1 3
2 3

输出样例：

输出n个顶点的元素值，顶点的数据类型为字符型。以及各顶点的度值

A:2
B:3
C:3
D:2

 求各定点的度的代码

void degree(MGraph G)
{int i,j;for(i=0;i<G.vexnum;i++){int du=0;for(j=0;j<G.vexnum;j++){if(G.arcs[i][j]==1)//如果G.arcs[i][j]!=0,du++; {du++;}}printf("%c:%d\n",G.vexs[i],du);} 
}

 R6-1 求链式表的表长

本题要求实现一个函数，求链式表的表长。

函数接口定义：

int Length( List L );

L是给定单链表，函数Length要返回链式表的长度。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {ElementType Data;PtrToLNode Next;
};
typedef PtrToLNode List;List Read(); /* 细节在此不表 */int Length( List L );int main()
{List L = Read();printf("%d\n", Length(L));return 0;
}/* 你的代码将被嵌在这里 */

输入样例：

1 3 4 5 2 -1

输出样例：

5

 求表长代码

int Length( List L )
{LNode *p;p=L->Next;int len=0;while(p!=NULL){p=p->Next;len++;}return len;
}

 R6-2 求二叉树的深度

本题要求实现一个函数，可返回二叉树的深度。

函数接口定义：
int Depth(BiTree T);

T是二叉树树根指针，函数Depth返回二叉树的深度，若树为空，返回0。

裁判测试程序样例：


#include <stdio.h>
#include <stdlib.h>typedef char ElemType;
typedef struct BiTNode
{ElemType data;struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;BiTree Create();/* 细节在此不表 */int Depth(BiTree T);int main()
{BiTree T = Create();printf("%d\n", Depth(T));return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

输入为由字母和'#'组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据：

AB#DF##G##C##

输出样例（对于图中给出的树）：

二叉树.png

4

 代码：


int Depth(BiTree T)
{int hl=0,hr=0,h;if(T){hl=Depth(T->lchild);hr=Depth(T->rchild);h=hl>hr?hl:hr;//其高度为左右子树高度的最大值+1 return h+1;}elsereturn 0;
}

 R6-2 顺序表的查找操作

本题要求实现一个函数，要求从顺序表中查找指定元素，并返回第一个查找成功的元素在表中的位置序号，若查找失败，则返回0；

函数接口定义：

int LocateElem(SqList L,ElemType e);

 其中SqList结构定义如下：

typedef struct{ElemType *elem;int length;}SqList;```### 裁判测试程序样例：
```c++
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
typedef int ElemType;
typedef struct{ElemType *elem;int length;}SqList;
void InitList(SqList &L);/*细节在此不表*/
int LocateElem(SqList L,ElemType e);int main()
{SqList L;InitList(L);ElemType e;int p;scanf("%d",&e);p=LocateElem(L,e);printf("The position of %d in SequenceList L is %d.",e,p);return 0;
}/* 请在这里填写答案 */

输入格式：

输入数据有1行，首先给出以-1结束的顺序表元素值（不超过100个，-1不属于顺序表元素），然后是待查找的元素值。所有数据之间用空格分隔。

输入样例：

2 6 4 9 13 -1 2

输出样例：

The position of 2 in SequenceList L is 1.

代码： 

int LocateElem(SqList L,ElemType e)
{int i;for(i=0;i<L.length;i++){if(L.elem[i]==e)//L.elem[i] {return i+1;}} return 0;
}

 R6-1 二叉树叶结点计数

实现一个函数，返回二叉树bt中叶结点的数量。

题目保证二叉树中所有元素均为整数。

裁判测试程序样例：

#include "stdio.h"
#include "stdlib.h"
struct BinTree{int data;struct BinTree *left;struct BinTree *right;
};
struct BinTree* createNode(int item){ //创建结点/* 函数实现细节省略*/
}
struct BinTree* findNode(struct BinTree *bt, int item){ //查找结点/*  函数实现细节省略*/
}
int insert(struct BinTree *bt, int parent, int dir,  int item){ //插入结点/*   实现细节仅供参考 */struct BinTree *tmp;tmp = findNode(bt, parent);if(!tmp) return 0;if(dir == 0){if(tmp->left) return 0;tmp->left = createNode(item);if(tmp->left == NULL) return 0;} else{if(tmp->right) return 0;tmp->right = createNode(item);if(tmp->right == NULL) return 0;}return 1;
}
struct BinTree* createBinTree(){ //创建二叉树/*  实现细节仅供参考 */int total, data;scanf("%d", &total);if(total == 0) return NULL;scanf("%d", &data);struct BinTree *bt;bt = createNode(data);if(!bt) return NULL;int parent, dir;for(int i=1; i<total; i++){scanf("%d%d%d", &parent, &dir, &data);insert(bt, parent, dir, data);}return bt;
}
int countLeaves(struct BinTree *bt);
int main(){struct BinTree *bt1, *bt2;bt1 = createBinTree();bt2 = createBinTree();printf("%d\n",countLeaves(bt1));printf("%d\n",countLeaves(bt2));return 0;
}/* 你提交的代码将被嵌入在这儿 */

输入样例：

tree.png

对于图片中的两棵二叉树以及样例测试程序的输入方式：

3
30
30 0 10
30 1 25
4
30
30 0 10
30 1 25
25 0 20

输出样例：

对于样例测试程序的输出方式：

2
2

 代码：

/*统计二叉树中叶子结点的数目并没,有次序要求，
可以用三种遍历中的任意一种来完成.
一、后序遍历统计 
叶子结点：既没有左孩子，又没有右孩子 
*/ 
int countLeaves(struct BinTree *bt)
{int cnt=0;if(bt!=NULL){countLeaves(bt->leftt);countLeaves(bt->right);if(bt->left==NULL&&bt->right==NULL){cnt++;}} return cnt;
}
/*
方法二：采用分治方法，如果二叉树为空树，返回0，
如果二叉树只有一个结点 ，返回1
否则为左右子树叶子结点的和 
*/
int countLeaves(struct BinTree *bt)
{int count=0;if(bt==NULL)return 0;else if(bt->left==NULL && bt->right==NULL)return count+1;else{count=countLeaves(bt->left)+countLeaves(bt->right);return count;}
}

 R6-1 按值查找单链表

本题要求实现一个函数，Locate_LinkList(LinkList L, datatype x)函数是在带头结点单链表中查找值为x的结点。函数须返回找到结点的指针,没有找到返回空。

函数接口定义：

LNode *Locate_LinkList(LinkList L, datatype x);

其中 L 和 x 都是用户传入的参数。 L 是单链表的头指针； x 是需要查找的值。函数须返回找到结点的指针,没有找到返回空。

裁判测试程序样例：

在这里给出函数被调用进行测试的例子。例如：
#define FLAG  -1
#include <stdio.h>
#include <malloc.h>
typedef int datatype;
typedef struct node
{datatype data;struct node *next;
}LNode, *LinkList;LinkList Creat_LinkList();/*这里忽略函数的实现*/LNode *Locate_LinkList(LinkList L, datatype x);int main()
{LinkList L;LNode *p=NULL;int x;    L = Creat_LinkList();if(L == NULL){ printf("L=NULL,error!"); return 0;  }scanf("%d",&x);if(p=Locate_LinkList(L,x)) printf("%d",p->data);else printf("NOT");return 0;
}/* 请在这里填写答案 */

输入样例：

在这里给出一组输入。例如：

1 2 3 4 5 6 7 8 9 10 -1
8

输出样例：

在这里给出相应的输出。例如：

8

代码：

LNode *Locate_LinkList(LinkList L, datatype x)
{LNode *p;p=L->next;while(p!=NULL&&p->data!=x)//当它不为空并这个数据值不等于x {p=p->next;//则找下一个 }return p;//返回找到该节点的指针 
}

 R6-1 二叉树的遍历

本题要求给定二叉树的4种遍历。

函数接口定义：

void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );

 要求4个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );int main()
{BinTree BT = CreatBinTree();printf("Inorder:");    InorderTraversal(BT);    printf("\n");printf("Preorder:");   PreorderTraversal(BT);   printf("\n");printf("Postorder:");  PostorderTraversal(BT);  printf("\n");printf("Levelorder:"); LevelorderTraversal(BT); printf("\n");return 0;
}
/* 你的代码将被嵌在这里 */

输出样例（对于图中给出的树）：

Inorder: D B E F A G H C I
Preorder: A B D F E C G H I
Postorder: D E F B H G I C A
Levelorder: A B C D F G I E H

 

void InorderTraversal( BinTree BT )//中序遍历 (左 根 右)
{if(BT!=NULL){InorderTraversal(BT->Left);printf(" %c",BT->Data);InorderTraversal(BT->Right);} 
}
void PreorderTraversal( BinTree BT )//前序遍历 （根 左 右） 
{if(BT!=NULL){printf(" %c",BT->Data);PreorderTraversal(BT->Left);PreorderTraversal(BT->Right); } 
}
void PostorderTraversal( BinTree BT )//后序遍历 (左 右 根)
{if(BT!=NULL){PostorderTraversal(BT->Left);PostorderTraversal(BT->Right);printf(" %c",BT->Data);}
}
void LevelorderTraversal( BinTree BT )//层序遍历 
{BinTree a[11000];a[0]=BT;int len=1;if(!BT){return;}while(1){if(len==0)return ;int pos=0;BinTree b[11000];for(int i=0;i<len;i++){if(a[i]!=NULL)printf(" %c",a[i]->Data);if(a[i]->Left!=NULL)b[pos++]=a[i]->Left;if(a[i]->Right!=NULL)b[pos++]=a[i]->Right; }len=pos;for(i=0;i<len;i++)a[i]=b[i];}
}

 

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

C++学习笔记——string类和new函数

C++学习笔记——string类和new函数

目录 string类 1.功能增强 1.1 子字符串提取 1.2 字符串拼接 1.3 大小写转换 1.4 字符串比较 2.性能优化 3.使用示例 下面是一个简单的使用示例&#xff0c;展示了如何使用改进后的String类&#xff1a; NEW函数 2.1NEW函数的基本用法 2.2NEW函数的注意事项 2.3避…
阅读更多...
linux系统基础知识-基础IO

linux系统基础知识-基础IO

IO 概念引入位图的概念IO的系统调用函数openwriteread()close简单使用样例&#xff1a; 文件描述符fd默认文件流stdin/stdout/stderr文件描述符的分配规则 重定向的概念输出重定向输入重定向追加重定向dup2()系统调用总结 文件缓冲区深入理解缓冲区的概念输出缓冲区部分代码解释…
阅读更多...
Linux网络配置与抓包工具介绍

Linux网络配置与抓包工具介绍

目录 一、配置命令 1. ifconfig 1.1 概述信息解析 1.2 常用格式 2. ip 2.1 ip link 数据链路层 2.2 ip addr 网络层 2.3 路由 3. hostname 3.1 临时修改主机名 3.2 永久修改主机名 4. route 5. netstat 6. ss 7. ping 8. traceroute 9. nslookup 10. 永久修…
阅读更多...
UI5与后端的文件交互（一）

UI5与后端的文件交互（一）

文章目录 前言一、RAP的开发1. 创建表格2. 创建CDS Entity3. 创建BDEF4. 创建implementation class5. 创建Service Definition和Binding6. 测试API 二、创建UI5 Project1. 使用Basic模板创建2. 创建View3. 测试页面及绑定的oData数据是否正确4. 创建Controller5. 导入外部包&am…
阅读更多...
计算机体系结构期末复习流程大纲

计算机体系结构期末复习流程大纲

1.存储器和cache 存储器的容量、速度与价格之间的要求是相互矛盾的&#xff0c;速度越快&#xff0c;没bit位价格越高&#xff0c;容量越大&#xff0c;速度越慢&#xff0c;目前主存一般有DRAM构成。 处理器CPU访问存储器的指标&#xff1a; 延迟时间&#xff08;Latency&am…
阅读更多...
【算法】算法设计与分析 期末复习总结

【算法】算法设计与分析 期末复习总结

第一章 算法概述 时间复杂度比大小&#xff0c;用代入法&#xff0c;代入2即可。求渐进表达式&#xff0c;就是求极限&#xff0c;以极限为O的括号&#xff1b;O是指上界&#xff0c;Ω是指下界&#xff0c;θ是指上下界相等&#xff0c;在这里&#xff0c;可以这样理解&#…
阅读更多...
Influxdb2修改管理员密码

Influxdb2修改管理员密码

通过恢复管理员令牌来重置InfluxDB2管理员的密码 1.找到数据库的配置文件 一般为config.json 2.配置文件的的blod文件配置 3.在这个混合文本和二进制json文件中搜索已知的用户名或token之类的字符串。 例如&#xff1a; "id":"0bd73badf2941000","…
阅读更多...
WEB 3D技术 three.js 线框几何体

WEB 3D技术 three.js 线框几何体

本文 我们说一下 线框几何体 想将一个几何体 以线框形式展现 threeJS中 有两种类可以实现 第一种 WireframeGeometry 这种几何体 其实就类似于 将材质中的 wireframe 开启 这种方法 之前我们也用过 还有一种 就是 EdgesGeometry 边缘几何体 我们先将代码写成这样 import .…
阅读更多...
关于kthread_stop的疑问（linux3.16）

关于kthread_stop的疑问（linux3.16）

线程一旦启动起来后&#xff0c;会一直运行&#xff0c;除非该线程主动调用do_exit函数&#xff0c;或者其他的进程调用kthread_stop函数&#xff0c;结束线程的运行。 之前找销毁内核线程的接口时&#xff0c;发现了kthread_stop这个接口。网上说这个函数能够销毁一个内核线程…
阅读更多...
Java中的IO流

Java中的IO流

在Java中&#xff0c;I/O&#xff08;输入/输出&#xff09;流用于处理与输入和输出相关的操作。Java的I/O流按照数据处理的不同方式分为两大类&#xff1a;字节流和字符流。每个类别又分为输入流和输出流。以下是Java中常用的I/O流及其继承关系&#xff1a; 字节流&#xff0…
阅读更多...
批量剪辑方法：掌握视频剪辑技巧，按指定时长轻松分割视频

批量剪辑方法：掌握视频剪辑技巧，按指定时长轻松分割视频

在视频制作和编辑过程中&#xff0c;经常要批量处理和剪辑大量的视频片段。学会批量剪辑方法可以提高工作效率&#xff0c;还可以使视频编辑更加准确和高效。下面来看下云炫AI智剪如何按指定时长轻松分割视频的批量剪辑方法。 分割后的视频文件效果&#xff0c;已分割分段的视…
阅读更多...
业界首款PCIe 4.0/5.0多通道融合接口SSD技术解读

业界首款PCIe 4.0/5.0多通道融合接口SSD技术解读

之前小编写过一篇文章劝大家不要碰PCIe 5.0 SSD&#xff0c;详细内容&#xff0c;可以再回顾下&#xff1a; 扩展阅读&#xff1a;当下最好不要入坑PCIe 5.0 SSD 如果想要进一步了解PCIe 6.0&#xff0c;欢迎点击阅读&#xff1a; 浅析PCIe 6.0功能更新与实现的挑战 PCIe 6.…
阅读更多...
云卷云舒：【实战篇】云主机/虚拟机迁移

云卷云舒：【实战篇】云主机/虚拟机迁移

1. 简介 用户原有业务通过不同版本型号、不同操作系统的主机承载&#xff0c;形式上包括物理服务器、虚拟机、公有云主机等。随着业务不断扩张&#xff0c;需要将其业务云化转型&#xff0c;必须保证上云过程数据完整&#xff0c;业务平滑过度。 如果将所有业务系统都重新部署…
阅读更多...
教你如何将本地虚拟机变成服务器，供其它电脑访问

教你如何将本地虚拟机变成服务器，供其它电脑访问

场景&#xff1a;最近在做数据仓库的作业&#xff0c;需要团队协作&#xff0c;买不起阿里云服务器&#xff0c;所以想到能不能将我本地机上的虚拟机变成服务器&#xff0c;供其它同学的电脑访问。在虚拟机上安装hadoop和hive&#xff0c;然后同学机子上安装kettle进行连接。最…
阅读更多...
Java 反射(一)

Java 反射(一)

反射 1.反射的介绍 1.反射机制允话程序在执行期间借助于Refelction API取得任何类的信息&#xff08;比如成员变量&#xff0c;构造器&#xff0c;成员方法等&#xff09;并能操作对象的属性及方法&#xff0c;反射在设计模式和框架底层都会用到 2.加载完类之后&#xff0c;在…
阅读更多...
可狱可囚的爬虫系列课程 08：新闻数据爬取实战

可狱可囚的爬虫系列课程 08：新闻数据爬取实战

前言 本篇文章中我带大家针对前面所学 Requests 和 BeautifulSoup4 进行一个实操检验。 相信大家平时或多或少都有看新闻的习惯&#xff0c;那么我们今天所要爬取的网站便是新闻类型的&#xff1a;中国新闻网&#xff0c;我们先来使用爬虫爬取一些具有明显规则或规律的信息&am…
阅读更多...
【Redis-04】Redis命令在客户端与服务器之间的执行流程

【Redis-04】Redis命令在客户端与服务器之间的执行流程

Redis本质上是一个数据结构服务器&#xff0c;支持键值对类型存储的内存管理系统&#xff0c;可以用作数据库、缓存和消息中间件&#xff0c;在我日常的开发中&#xff0c;基本上使用redis作为缓存中间件。 在Redis中有两个重要的角色&#xff0c;一个是服务器server&#xff0…
阅读更多...
Adding Conditional Control to Text-to-Image Diffusion Models——【论文笔记】

Adding Conditional Control to Text-to-Image Diffusion Models——【论文笔记】

本文发表于ICCV2023 论文地址&#xff1a;ICCV 2023 Open Access Repository (thecvf.com) 官方实现代码&#xff1a;lllyasviel/ControlNet: Let us control diffusion models! (github.com) Abstract 论文提出了一种神经网络架构ControlNet,可以将空间条件控制添加到大型…
阅读更多...
性能分析与调优: Linux 监测工具的数据来源

性能分析与调优: Linux 监测工具的数据来源

目录 一、实验 1.环境 2. proc目录 3. sys目录 4.netlink 5.tracepoint 6.kprobes 7. uprobes 二、问题 1.systemd如何查看启动时间 2.CentOS与Ubuntu如何安装bpftrace 3.snap有哪些常用的命令 4.snap如何安装store 5.如何列出使用bpftrace的OpenJDK USDT探针 一…
阅读更多...
显示管理磁盘分区 fdisk

显示管理磁盘分区 fdisk

显示管理磁盘分区 fdisk fdisk是用于检查一个磁盘上分区信息最通用的命令。 fdisk可以显示分区信息及一些细节信息&#xff0c;比如文件系统类型等。 设备的名称通常是/dev/sda、/dev/sdb 等。 对于以前的设备有可能还存在设备名为 /dev/hd* (IDE)的设备&#xff0c;这个设…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023