40.查找练习题(王道2023数据结构第7章)

试题1(王道7.2.4节综合练习5):

写出折半查找的递归算法。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>#define MAXSIZE 10
#define ElemType int
#define Status inttypedef struct{int data[MAXSIZE];  //存储空间的基地址int length;  //当前长度 
}SqList;void CreatList(SqList &L){  //建立线性表L.length = 6;L.data[0] = 2;L.data[1] = 3;L.data[2] = 5;L.data[3] = 7;L.data[4] = 9;L.data[5] = 11;
}int BinarySearch(SqList L,ElemType x,int low,int high){int mid = (low + high) / 2;if(low > high)return -1;else if(L.data[mid] == x)return mid;else if(L.data[mid] < x)BinarySearch(L, x, mid + 1, high);elseBinarySearch(L, x, low, mid - 1);
}int main(){SqList L;CreatList(L);printf("%d", BinarySearch(L, 7, 0, 5));
}

输出:

3

试题2(王道7.2.4节综合练习6):

线性表中各结点检索概率不等时,可用如下策略提高顺序检索的效率:若找到指定的结点,则将该结点与前驱结点(若存在)交换,使得经常被检索的结点尽量位于表的前端。试设计在顺序结构和链式结构的线性表上实现上述策略的顺序检索算法。

此题可以联系链表练习题的第20题:

【试题再现】试题20:设头指针为L的带有表头结点的非循环双向链表,其每个结点中除有prior(前驱指针),data(数据),next(后继指针)域外,还有一个访问频度域freq。在链表被启用前,其值均初始化为零。每当在连表中进行一次Locate(L,x)运算时,令元素值为x的结点中freq域的值增1,并使此链表中结点保持按访问频度非递增的顺序排列,同时最近访问的结点排在频度相同的结点的前面,以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法,该运算为函数过程,返回找到结点的地址,类型为指针型。

31.链表练习题(2)(王道2023数据结构2.3.7节16-25题)-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/qq_54708219/article/details/133151369顺序表实现:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>#define MAXSIZE 10
#define ElemType int
#define Status inttypedef struct{int data[MAXSIZE];  //存储空间的基地址int length;  //当前长度 
}SqList;void CreatList(SqList &L){  //建立线性表L.length = 6;L.data[0] = 2;L.data[1] = 3;L.data[2] = 5;L.data[3] = 7;L.data[4] = 9;L.data[5] = 11;
}void PrintList(SqList L){for (int i = 0; i < L.length;i++){printf("%d ", L.data[i]);}
}int Search(SqList &L,ElemType x){int t;for (int i = 0; i < L.length;i++){if(L.data[i] == x){t = L.data[i - 1];  //交换L.data[i - 1] = x;L.data[i] = t;return i;}	}return -1;
}int main(){SqList L;CreatList(L);PrintList(L);printf("\n");printf("%d\n", Search(L, 7));PrintList(L);
}

输出:

2 3 5 7 9 11 
3
2 3 7 5 9 11

链表实现:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>#define MAXSIZE 10
#define ElemType int
#define Status int//单链表的数据结构
typedef struct LNode
{ElemType data;struct LNode *next;
}LNode, *LinkList;//初始化
int InitList(LinkList &L)
{L = (LNode *)malloc(sizeof(LNode));L->next = NULL;return 1;
}//输出
void PrintList(LinkList L)
{printf("当前单链表的所有元素:");LNode *p;p = L->next;while (p != NULL){printf("[%d] ", p->data);p = p->next;}printf("\n");
}int Create(LinkList &L)
{int n, e;LNode *temp = L;//声明一个指针指向头结点,用于遍历链表   printf("请输入要输入元素的个数:");scanf("%d", &n);for (int i = 1; i <= n; i++){LNode *a = (LNode*)malloc(sizeof(LNode));printf("请输入第%d元素的值:", (i));scanf("%d", &e);a->data = e;temp->next = a;a->next = NULL;temp = temp->next;}return 1;
}int Search(LinkList L,ElemType x){LinkList p = L;LinkList q = L;LinkList r;int i = 0;while(p!=NULL){if(p->data != x){p = p->next;i = i + 1;}else{if(i > 1){for (int j = 1; j <= i - 2; j++){q = q->next;}  //q指向第i-2个元素r = q->next;  //r指向第i-1个元素q->next = p;q = p->next;  //q指向第i+1个元素p->next = r;r->next = q;}return i;}}return -1;
}int main(){LinkList L;InitList(L);Create(L);PrintList(L);printf("元素在链表第%d个位置\n", Search(L, 7));PrintList(L);
}

输出:

请输入要输入元素的个数:6
请输入第1元素的值:2
请输入第2元素的值:3
请输入第3元素的值:5
请输入第4元素的值:7
请输入第5元素的值:9
请输入第6元素的值:11
当前单链表的所有元素:[2] [3] [5] [7] [9] [11]
元素在链表第4个位置
当前单链表的所有元素:[2] [3] [7] [5] [9] [11]

试题3(王道7.3.4节综合练习6):

设计算法,判断给定的二叉树是否是二叉排序树。

看其中序遍历序列是否是递增有序的即可:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>#define MAXSIZE 10
#define ElemType int//二叉排序树的结构体定义
typedef struct BiTNode{ElemType data;  //数据域BiTNode *lchild;  //指向左子树根节点的指针BiTNode *rchild;  //指向右子树根节点的指针
}BiTNode, *BiTree;int BST_Insert(BiTree &T,ElemType k){  //构造一棵二叉排序树if(T==NULL){T = (BiTree)malloc(sizeof(BiTNode));T->data = k;T->lchild = NULL;T->rchild = NULL;return 1;}else if(k==T->data){return 0;}else if(k<T->data){return BST_Insert(T->lchild, k);}else{return BST_Insert(T->rchild, k);}
}int if_BST(BiTree T){int a[10];int i = 0;if (T!=NULL){if_BST(T->lchild);a[i] = T->data;i = i + 1;if_BST(T->rchild);}for (int j = 1; j <= i-1;j++){  //实际上a数组中元素是0到i-1if(a[j-1] >= a[j]){return 0;}}return 1;
}int main(){BiTree T=NULL;int a[5] = {4, 2, 1, 3, 5};  //以王道第10题做验证for (int i = 0; i <= 4;i++){BST_Insert(T, a[i]);}printf("%d",if_BST(T));return 0;
}

输出:

1

试题4(王道7.3.4节综合练习7):

设计算法求指定结点在给定二叉排序树的层次。

老问题了,直接上递归:

int levelofNode(BiTree T, ElemType x,int level){if(T==NULL)return -1;else{if(T->data==x)return level;else{if(T->data<x)return levelofNode(T->rchild, x, level + 1);elsereturn levelofNode(T->lchild, x, level + 1);}}
}int main(){BiTree T=NULL;int a[5] = {4, 2, 1, 3, 5};  //以王道第10题做验证for (int i = 0; i <= 4;i++){BST_Insert(T, a[i]);}printf("%d",levelofNode(T,3,1));return 0;
}

输出:

3

试题5(王道7.3.4节综合练习8):

利用二叉树的遍历思想编写一个判断二叉树是否是平衡二叉树的算法。

这里利用层次遍历每一个结点,检查平衡因子绝对值是否小于1。全部通过才返回True。

int Depth(BiTree T){if(T==NULL)return 0;else{return (Depth(T->lchild) >= Depth(T->rchild)) ? Depth(T->lchild) + 1 : Depth(T->rchild) + 1;}
}int abs(int x){return x >= 0 ? x : -x;
}bool ifBalanceTree(BiTree T){  //层次遍历每一个结点int balance = 0;Queue q;InitQueue(q);BiTree p = T;InsertQueue(q, p);while(!IsQueueEmpty(q)){p = DeleteQueue(q, p);balance = abs(Depth(p->lchild) - Depth(p->rchild));if(balance > 1)return false;if(p->lchild!=NULL)InsertQueue(q, p->lchild);if(p->rchild!=NULL)InsertQueue(q, p->rchild);}return true;
}int main(){BiTree T=NULL;int a[5] = {1, 2, 3, 4, 5};  //以王道第10题做验证for (int i = 0; i <= 4;i++){BST_Insert(T, a[i]);}printf("%d",ifBalanceTree(T));return 0;
}

输出:

1  //int a[5] = {4, 2, 1, 3, 5};
0  //int a[5] = {1, 2, 3, 4, 5};

试题6(王道7.3.4节综合练习9):

设计算法求给定二叉排序树最小和最大的关键字。

最小关键字在最左下,最大关键字在最右下,抓住这一点判断即可。此题不需要从头遍历把所有结点全部输出。

int maxvalue(BiTree T){  //求最大关键字BiTree p=T;while (p->rchild!=NULL){p = p->rchild;}return p->data;
}int main(){BiTree T=NULL;int a[5] = {4, 2, 1, 3, 5};  //以王道第10题做验证for (int i = 0; i <= 4;i++){BST_Insert(T, a[i]);}printf("%d",maxvalue(T));return 0;
}
int minvalue(BiTree T){  //求最小关键字BiTree p=T;while (p->lchild!=NULL){p = p->lchild;}return p->data;
}int main(){BiTree T=NULL;int a[5] = {4, 2, 1, 3, 5};  //以王道第10题做验证for (int i = 0; i <= 4;i++){BST_Insert(T, a[i]);}printf("%d",minvalue(T));return 0;
}

试题7(王道7.3.4节综合练习10):

设计一个算法,从大到小输出二叉排序树中所有值不小于k的关键字。

倒序访问:显然先访问右子树,然后根结点,最后左子树,然后检查并输出。

void printoverk(BiTree T,int k){  //求最小关键字if(T!=NULL){printoverk(T->rchild, k);if(T->data>k){printf("%d ", T->data);}printoverk(T->lchild, k);}
}int main(){BiTree T=NULL;int a[5] = {4, 2, 1, 3, 5};  //以王道第10题做验证for (int i = 0; i <= 4;i++){BST_Insert(T, a[i]);}printoverk(T, 2);return 0;
}

输出:

5 4 3

试题8(王道7.3.4节综合练习11):

编写一个递归算法,在一棵具有n个结点的二叉排序树上查找第k小的元素,并返回该结点的指针。要求算法的平均时间复杂度是O(log_2n),二叉排序树每个结点中除了data,lchild,rchild外,增设一个count成员,保存以该结点为根的子树的结点个数。

函数的参数有两个:二叉树指针T和查找第k个最小元素。

//求树的结点数(递归)
int Number_Node(BiTree T){if(T==NULL)return 0;else{return Number_Node(T->lchild) + Number_Node(T->rchild) + 1;}
}int BST_Insert(BiTree &T,ElemType k){  //构造一棵二叉排序树if(T==NULL){T = (BiTree)malloc(sizeof(BiTNode));T->data = k;T->lchild = NULL;T->rchild = NULL;return 1;}else if(k==T->data){return 0;}else if(k<T->data){return BST_Insert(T->lchild, k);}else{return BST_Insert(T->rchild, k);}
}void BST_Insertcount(BiTree &T){  //修改count的数值Queue q;InitQueue(q);BiTree p = T;InsertQueue(q, p);while(!IsQueueEmpty(q)){p = DeleteQueue(q, p);p->count = Number_Node(p);if(p->lchild!=NULL)InsertQueue(q, p->lchild);if(p->rchild!=NULL)InsertQueue(q, p->rchild);}
}BiTree SearchSmallk(BiTree T,int k){  //寻找第k小的元素if(k<1||k>T->count)  //k不合法,直接返回空return NULL;if(T->lchild == NULL){if(k == 1)return T;elsereturn SearchSmallk(T->rchild, k - 1);  //第k小的元素必在右子树}else{if(T->lchild->count == k-1)return T;else if(T->lchild->count < k-1)return SearchSmallk(T->rchild, k - T->lchild->count - 1);  //第k小的元素必在右子树elsereturn SearchSmallk(T->lchild, k);  //第k小的元素必在左子树}
}int main(){BiTree T=NULL;BiTree p;int a[5] = {4, 2, 1, 3, 5};  //以王道第10题做验证for (int i = 0; i <= 4;i++){BST_Insert(T, a[i]);}BST_Insertcount(T);p = SearchSmallk(T, 3);printf("%d", p->data);return 0;
}

输出:

3

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

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

相关文章

Python---break关键字对for...else结构的影响

for循环中添加else结构 循环可以和else配合使用&#xff0c; else下方缩进的代码指的是当循环正常结束之后要执行的代码。 强调&#xff1a; 循环 正常结束&#xff0c;else之后要执行的代码。 非正常结束&#xff0c;其else中的代码是不会执行的。&#xff08;如遇到br…

[计算机提升] Windows系统各种开机启动方式介绍

1.14 开机启动 在Windows系统中&#xff0c;开机启动是指开启电脑后&#xff0c;自动运行指定的程序或服务的技术。一些程序或服务需要在开机后自动启动&#xff0c;以便及时响应用户操作&#xff0c;比如防安防软件、即时通信工具、文件同步软件等。 同时&#xff0c;一些系统…

Power BI 实现日历图,在一张图中展示天、周、月数据变化规律

《数据可视化》这本书里介绍了一个时间可视化的案例&#xff08;如下图所示&#xff09;&#xff0c;以日历图的形式展示数据的变化&#xff0c;可以在一张图上同时观察到&#xff1a;&#xff08;1&#xff09;每一天的数据变化&#xff1b;&#xff08;2&#xff09;随周变化…

图纸管理制度 《五》

1、存档文件应由专人管理&#xff0c;其他人未征得管理人员同意&#xff0c;不得随意翻阅查看。 2、档案管理人员要认真贯彻执行公司相关制度&#xff0c;严禁泄露档案材料中的秘密。 彩虹图纸管理软件_图纸管理系统_图纸文档管理软件系统_彩虹EDM【官网】彩虹EDM图纸管理软件…

Unity C#中LuaTable、LuaArrayTable、LuaDictTable中数据的增删改查

LuaTable、LuaArrayTable、LuaDictTable中数据的增删改查 介绍Lua表lua表初始化lua移除引用lua中向表中添加数据lua中表中移除数据lua表中连接数据lua表中数据排序获取lua表长度获取表中最大值 UnityC#中LuaTableUnityC#中LuaArrayTable、LuaDictTable、LuaDictTable<K,V>…

【C程序设计】用心浇灌<C程序>

目录 数据类型 整数类型 实例 浮点类型 void 类型 类型转换 数据类型 在 C 语言中&#xff0c;数据类型指的是用于声明不同类型的变量或函数的一个广泛的系统。变量的类型决定了变量存储占用的空间&#xff0c;以及如何解释存储的位模式。 C 中的类型可分为以下几种&…

云计算与ai人工智能对高防cdn的发展

高防CDN&#xff08;Content Delivery Network&#xff09;作为网络安全领域的一项关键技术&#xff0c;致力于保护在线内容免受各种网络攻击&#xff0c;包括分布式拒绝服务攻击&#xff08;DDoS&#xff09;等。然而&#xff0c;随着人工智能&#xff08;AI&#xff09;和大数…

Redis快速上手篇七(集群-六台虚拟机)

Redis集群 主从复制的场景无法吗满足主机单点故障时需要引入集群配置 一般数据库要处理的读请求远大于写请求 &#xff0c;针对这种情况&#xff0c;我们优化数据库可以采用读写分离的策略。我们可以部 署一台主服务器主要用来处理写请求&#xff0c;部署多台从服务器 &#…

【luckfox】添加压力传感器hx711

文章目录 前言一、参考资料二、电路图三、驱动四、makefile——添加驱动五、dts——使能gpio5.1 参考5.2 改动1—— hx117节点5.3 改动2——引脚节点5.4 已经被定义的引脚5.5 gpio源码 六、改动总结——使能hx711七、验证驱动添加八、编写测试文件8.1 测试代码8.2 配置编译环境…

解决:谷歌浏览器访问http时,自动转https访问的问题

问题背景&#xff1a;某个系统网站&#xff0c;之前一直用https域名访问&#xff0c;现在改成http域名后&#xff0c;用http访问&#xff0c;谷歌浏览器会自动跳转到https。 解决方法&#xff1a; 在浏览器中输入网址&#xff1a;chrome://net-internals/#hsts -》 在“Delete…

Jmeter压测实战:Jmeter二次开发之自定义函数

​1 前言 Jmeter是Apache基金会下的一款应用场景非常广的压力测试工具&#xff0c;具备轻量、高扩展性、分布式等特性。Jmeter已支持实现随机数、计数器、时间戳、大小写转换、属性校验等多种函数&#xff0c;方便使用人员使用。如果在使用过程中存在和业务强耦合的常用功能函…

【广州华锐互动】VR公司工厂消防逃生演练带来沉浸式的互动体验

在工业生产过程中&#xff0c;安全问题始终是我们不能忽视的重要环节。特别是火灾事故&#xff0c;不仅会造成重大的经济损失&#xff0c;更会威胁到员工的生命安全。传统的消防安全训练方法&#xff0c;如讲座、实地演练等&#xff0c;虽然具有一定的效果&#xff0c;但是无法…

Matlab绘制散点的95%置信区间图

Matlab常绘制95%置信区间图&#xff0c;主要使用到patch函数。 如果直接使用散点进行拟合&#xff0c;在patch函数绘制95%置信区间时&#xff0c;会绘制的很乱&#xff0c;这个是由于patch函数所导致的&#xff0c;其实这个问题在 Matlab绘制95%置信区间图 中已经讲到过&#…

【教3妹学编程-java实战4】Map遍历删除元素的几种方法

插&#xff1a; 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。 坚持不懈&#xff0c;越努力越幸运&#xff0c;大家一起学习鸭~~~ 2哥 :3妹&#xff0c;今天是周末&#xff0c;又不用上…

51单片机复位电容计算与分析(附带Proteus电路图)

因为iC x (dU/dt).在上电瞬间&#xff0c;U从0变化到U,所以这一瞬间就是通的&#xff0c;然后这就是一个直流回路&#xff0c;因为电容C直流中是断路的&#xff0c;所以就不通了。 然后来分析一下这个电容的电压到底是能不能达到单片机需要的复位电压。 这是一个线性电容&…

基于springboot实现休闲娱乐代理售票平台系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现休闲娱乐代理售票平台系统演示 摘要 网络的广泛应用给生活带来了十分的便利。所以把休闲娱乐代理售票管理与现在网络相结合&#xff0c;利用java技术建设休闲娱乐代理售票系统&#xff0c;实现休闲娱乐代理售票的信息化。则对于进一步提高休闲娱乐代理售票管…

【黑产攻防道03】利用JS参数更新检测黑产的协议破解

任何业务在运营一段时间之后都会面临黑产大量的破解。验证码和各种爬虫的关系就像猫和老鼠一样, 会永远持续地进行博弈。极验根据十一年和黑产博弈对抗的经验&#xff0c;将黑产的破解方式分为三类&#xff1a; 1.通过识别出验证码图片答案实现批量破解验证&#xff0c;即图片…

SQL-正则表达式和约束

文章目录 主要内容一.正则表达式1.操作1代码如下&#xff08;示例&#xff09;: 2.操作2代码如下&#xff08;示例&#xff09;: 3.操作3代码如下&#xff08;示例&#xff09;: 4.操作4代码如下&#xff08;示例&#xff09;: 二.约束1.主键约束 2.自增长约束3.非空约束4.唯一…

CSDN学院 < 华为战略方法论进阶课 > 正式上线!

目录 你将收获 适用人群 课程内容 内容目录 CSDN学院 作者简介 你将收获 提升职场技能提升战略规划的能力实现多元化发展综合能力进阶 适用人群 主要适合公司中高层、创业者、产品经理、咨询顾问&#xff0c;以及致力于改变现状的学员。 课程内容 本期课程主要介绍华为…

网络原理的讲解

网络原理 重要性: 网络原理知识 1.工作中非常重要的理论知识,尤其是正在调试一些bug的时候. 2.面试中非常重要的考点. 3.学习中非常关键的难点. 网络原理这里,主要给大家介绍, TCP/IP协议 这里的关键协议. 按照这里的这四层,分别进行介绍(物理层不涉及) 应用层 是和程序猿打…