数据结构与算法分析模拟试题及答案5

模拟试题(五)

一、单项选择题(每小题 2 分,共20分)
(1)队列的特点是(   )。
A)先进后出 B)先进先出
C)任意位置进出 D)前面都不正确
(2)有n个记录的文件,如关键字位数为d,基数为r,则基数排序共要进行(   )遍分配与收集。
A)n B)d C)r D)n - d
(3)在二叉树结点的先序序列、中序序列和后序序列中,所有叶子结点的先后顺序(   )。
A)都不相同 B)完全相同
C)先序和中序相同,而与后序不同 D)中序和后序相同,而与先序不同
(4)限定在一端加入和删除元素的线性表称为(   )。
A)双向链表 B)单向链表 C)栈 D)队列
(5)若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是(   )。
A)起泡排序 B)插入排序 C)选择排序 D)二路归并排序
(6)设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树上的结点个数为n,森林F中第一棵树的结点个数是(   )。
A)m-n-1 B)n+1 C)m-n+1 D)m-n
(7)对于具有n个顶点的强连有向图,其弧条数的最小值为(   )。
A)n+1 B)n C)n-1 D)n-2
(8)下面关于广义表的叙述中,不正确的是(   )。
A)广义表可以是一个多层次的结构 B)广义表至少有一个元素
C)广义表可以被其他广义表所共享 D)广义表可以是一个递归表
(9)设二叉树根结点的层次为0,一棵深度(高度)为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点,下列关系式不正确的是(   )。
A)f>=c B)c>f C)f=2k+1-1 D)c>2k-1
(10)设一棵二叉树中没有度为1的结点,已知叶子结点数为n,此树的结点数为(   )。
A)2n+2 B)2n+1 C)2n D)2n-1
二、(每小题4分,共8分)
写出下列中缀表达式的后缀形式:
(1)3X/(Y-2)+1
(2)2+X*(Y+3)
三、(每小题4分,共8分)
试对如下图中的二叉树画出其:
在这里插入图片描述
(1)顺序存储表示;
(2)二叉链表存储表示的示意图。
四、(每小题4分,共8分)
判断以下序列是否是小根堆? 如果不是,将它调整为小根堆。
(1){ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }
(2){ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 }
五、(本题8分)
已知一个图的顶点集V和边集E分别为:
V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
按照普里姆算法从顶点1出发得到最小生成树,试写出在最小生成树中依次得到的各条边。
六、(每小题2分,共8分)
设有12个数据25,40,33,47,12,66,72,87,94,22,5,58,它们存储在散列表中,利用线性探测再散列处理冲突,取散列函数为H(key)=key % 13。
(1)顺次将各个数据散列到表中,并同时列出各元素的比较次数。
(2)计算查找成功的平均查找次数。
七、(第1小题2分,第2、3小题每小题3分,本题8分)
对于如下图所示的图G,邻接点按从小到大的次序。
在这里插入图片描述
(1)图G有几个连通分量?
(2)按深度优先搜索所得的树是什么?
(3)按深度优先搜索所得的顶点序列是什么?
八、(本题8分)
已知一棵树边为:
{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<C,B>,<G,L>,<G,K>,<A,G>,<A,F>,<A,H>,<C,A>}
试画出这棵树,并回答下列问题:
(1)哪个是根结点?
(2)哪些是叶子结点?
(3)树的深度是多少?
九、(本题9分)
给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)。写出用下列算法从小到大排序时第一趟结束时的序列。
(1)希尔排序(第一趟排序的增量为5)
(2)快速排序(选第一个记录为枢轴)
十、(本题15分)
编写复制一棵二叉树的非递归算法。

模拟试题(五)参考答案

一、单项选择题(每小题 2 分,共20分)
(1)B (2)B (3)B (4)C (5)B
(6)D (7)B (8)B (9)B (10)D
二、(每小题4分,共8分)
(1)3 X * Y 2 - / 1 +
(2)2 X Y 3 + * +
三、(每小题4分,共8分)
(1)二叉树的顺序存储表示如下所示:
在这里插入图片描述
(2)二叉树的二叉链表存储表示的示意图如下图所示:
在这里插入图片描述
四、(每小题4分,共8分)
(1)不是小根堆。调整为:{12,24,33,65,33,56,48,92,86,70}
(2)是小根堆。
五、(本题8分)
普里姆算法从顶点1出发得到最小生成树为:
(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20
六、(每小题2分,共8分)
(1)取散列函数为H(key)=key % 13。
(2)顺次将各个数据散列到表中,并同时列出各元素的比较次数如下表所示。
在这里插入图片描述
(4)计算查找成功的平均查找次数=(1×7+2×3+3×2)/12=19/12。
七、(第1小题2分,第2、3小题每小题3分,本题8分)
(1)图G有2个连通分量。
(2)按深度优先搜索所得的树如下图所示:
在这里插入图片描述
(3)按深度优先搜索所得的顶点序列:ABHFGCDE
八、(本题8分)
(1)树,如下图所示:
在这里插入图片描述
(2)C是根结点。
(3)F,K,L,H,D,M,N是叶子结点。
(3)深度是5。
九、(本题9分)
(1)(12,2,10,20,6,18,4,16,30,8,28)
(2)(6,2,10,4,8,12,28,30,20,16,18)
十、(本题15分)
将算法实现函数声明为二叉树类的友元函数,可采用层次遍历的方式进行复制,将已复制的结点进入一个队列中即可。
具体算法实现如下:

// 文件路径名:exam5\alg.h
template
void CopyBitree(BinaryTree *fromBtPtr, BinaryTree *&toBtPtr)
// 操作结果: 复制二叉树fromBt到toBt的非递归算法
{
if (toBtPtr != NULL) delete toBtPtr; // 释放toBtPtr
if (fromBtPtr->Empty())
{ // 空二叉树
toBtPtr = NULL; // 空二叉树
}
else
{ // 非空二叉树
LinkQueue<BinTreeNode *> fromQ, toQ; // 队列
BinTreeNode *fromPtr, *toPtr, *fromRoot, *toRoot;
fromRoot =(BinTreeNode *) fromBtPtr->GetRoot(); // 取出fromBtPtr的根
toRoot = new BinTreeNode(fromRoot->data); // 复制根结点
fromQ.InQueue(fromRoot); toQ.InQueue(toRoot); // 入队
while (!fromQ.Empty())
{ // fromQ非空
fromQ.OutQueue(fromPtr); // 出队
toQ.OutQueue(toPtr); // 出队
if (fromPtr->leftChild != NULL)
{ // 左子树非空
toPtr->leftChild = new BinTreeNode(fromPtr->leftChild->data);
// 复制fromPtr左孩子
fromQ.InQueue(fromPtr->leftChild); toQ.InQueue(toPtr->leftChild); // 入队
}
if (fromPtr->rightChild != NULL)
{ // 右子树非空
toPtr->rightChild = new BinTreeNode(fromPtr->rightChild->data);
// 复制fromPtr左孩子
fromQ.InQueue(fromPtr->rightChild); toQ.InQueue(toPtr->rightChild); // 入队
}
}
toBtPtr = new BinaryTree(toRoot); // 生成toBtPtr
}
}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

集群聊天服务器(9)一对一聊天功能

目录 一对一聊天离线消息服务器异常处理 一对一聊天 先新添一个消息码 在业务层增加该业务 没有绑定事件处理器的话消息会派发不出去 聊天其实是服务器做一个中转 现在同时登录两个账号 收到了聊天信息 再回复一下 离线消息 声明中提供接口和方法 张三对离线的李…

jedis基础入门

jedis采用key&#xff0c;value的形式保存数据&#xff0c;使用nosql sql和nosql的区别 一&#xff1a;入门案例 导入依赖 <dependencies><dependency><groupId>redis.clients</groupId><artifactId>jedis</artifactId><version>…

QWen2.5学习

配置环境 pip install transformers 记得更新一下&#xff1a;typing_extensions pip install --upgrade typing_extensions 安装modelscope modelscope/modelscope: ModelScope: bring the notion of Model-as-a-Service to life. 下载这个仓库的代码上传到服务器解压 推…

足球青训俱乐部管理后台系统(程序+数据库+报告)

基于SpringBoot的足球青训俱乐部管理后台系统&#xff0c;系统包含两种角色&#xff1a;管理员、用户,系统分为前台和后台两大模块 编程语言&#xff1a;Java 数据库&#xff1a;MySQL 项目管理工具&#xff1a;Maven 前端技术&#xff1a;Vue 后端技术&#xff1a;SpringBoot…

MoneyPrinterTurbo - AI自动生成高清短视频

MoneyPrinterTurbo是一款基于AI大模型的开源软件&#xff0c;旨在通过一键操作帮助用户自动生成高清短视频。只需提供一个视频 主题或 **关键词** &#xff0c;就可以全自动生成视频文案、视频素材、视频字幕、视频背景音乐&#xff0c;然后合成一个高清的短视频。 ​ ​ 主要…

Cross-Inlining Binary Function Similarity Detection

注&#xff1a;在阅读该论文时顺便参考了作者团队的分享视频&#xff1a;【ICSE 2024论文预讲会-第二期-下午-哔哩哔哩】 https://b23.tv/XUVAPy3 在这个视频的末尾最后一个 一.introducion 计算下面两个函数的相似度&#xff1a; 查询函数&#xff1a;脆弱函数&#xff0c;重…

C++:哈希拓展-位图

目录 一.问题导入 二.什么是位图? 2.1如何确定目标数在哪个比特位? 2.2如何存放高低位 2.3位图模拟代码实现 2.3.1如何标记一个数 2.3.2如何重置标记 2.3.3如何检查一个数是否被标记 整体代码实现 标准库的Bitset 库中的bitset的缺陷 简单应用 一.问题导入 这道…

GCP : Memcache backed by Cloud Datastore

Memcache backed by Cloud Datastore 的用途主要体现在以下几个方面&#xff1a; 提高性能和可扩展性&#xff1a; Memcache 是一个高性能的分布式内存对象缓存系统&#xff0c;通常用于缓存数据库查询等操作&#xff0c;以减轻数据库负载&#xff0c;加快动态Web应用的响应速度…

【Python】问题解决:yaml文件加载得到字符串而不是字典

问题描述 最近需要使用python处理yaml文件&#xff0c;但使用过程中发现只能输出字符串的格式&#xff0c;而不是想要的字典格式。 基本使用 在python中想要读写yaml文件&#xff0c;可以安装使用第三方包pyyaml来实现&#xff0c;首先安装一下&#xff1a; pip install pyya…

时钟之Canvas+JS版

写在前面 上一篇介绍使用CSSJS方式实现&#xff0c;但元素太过单一。此篇将以HTML5的canvas标签结合JS来实现。 HTML代码 <canvas id"clock" width"300" height"300"></canvas> JS代码 var canvas null; var ctx null; var int…

shell脚本_创建执行与变量的定义与使用

PS:前言本章节讲解使用的系统为linux2024.1&#xff0c;基于Debian的Linux发行版。 一、什么是shell脚本&#xff1f; 1. 定义&#xff1a; 2. 主要特点&#xff1a; 3. shell脚本的基本结构 4. Shebang 二、创建执行 1.脚本的创建 2. 脚本的执行 2.1.chmod 2.2. 使用…

CSP/信奥赛C++语法基础刷题训练(11):洛谷P5743:猴子吃桃

CSP/信奥赛C语法基础刷题训练&#xff08;11&#xff09;&#xff1a;洛谷P5743&#xff1a;猴子吃桃 题目描述 一只小猴买了若干个桃子。第一天他刚好吃了这些桃子的一半&#xff0c;又贪嘴多吃了一个&#xff1b;接下来的每一天它都会吃剩余的桃子的一半外加一个。第 n n n…

C++11(四)---可变参数模板

文章目录 可变参数模板 可变参数模板 参数包代表多个类型和参数 // Args是一个模板参数包&#xff0c;args是一个函数形参参数包 // 声明一个参数包Args...args&#xff0c;这个参数包中可以包含0到任意个模板参数。 template <class ...Args> void ShowList(Args... arg…

【qt】控件1

1.控件使能&#xff08;enabled&#xff09; QPushbutton*stnew QPushbutton(this);//定义一个按钮 st->setEnabled(false);//按钮设置不能使用当设置该控件不能使用的话&#xff0c;对应控件的子控件也不能使用 通过isEnabled()函数可以查看对应控件状态 演示&#xff1…

昇思MindSpore第二课---Transformer

1. Transformer的概念 Transformer是一种基于注意力机制结构的神经网络&#xff0c;其主要的作用就是用于处理机器翻译、语言建模以及文本生成等自然语言的处理。 比如人类在做一篇阅读理解的时候&#xff0c;我们的注意力可能主要集中在我们所阅读的这一行内容。而机器也是如此…

【Go】-bufio库解读

目录 Reader和Writer接口 bufio.Reader/Writer 小结 其他函数-Peek、fill Reader小结 Writer Scanner结构体 缓冲区对于网络数据读写的重要性 Reader和Writer接口 在net/http包生成的Conn 接口的实例中有两个方法叫做Read和Write接口 type Conn interface {Read(b []b…

mac 0S中虚拟机分辨率高怎么办

在VMware Fusion安装的Windows虚拟机有时候会遇到下图的问题&#xff0c;分辨率很高、桌面和任务栏的图标都很小&#xff0c;没办法正常使用。 解决方法&#xff1a; 点击工具栏中的扳手图标&#xff0c;打开设置。 打开系统设置中的“显示器”。 取消勾选“使用Retina全分辨率…

找不到d3dx9_43.dll怎么解决,d3dx9_43.dll缺失的七种解决方法

​在计算机游戏领域&#xff0c;遇到“找不到d3dx9_43.dll”错误信息是一个相当普遍的现象。这一问题不仅影响玩家的游戏体验&#xff0c;还可能导致游戏无法启动或运行不稳定。本文旨在深入解析这一问题的原因&#xff0c;并提供有效的解决方法&#xff0c;帮助广大游戏玩家轻…

论文《基于现实迷宫地形的电脑鼠设计》深度分析(四)——现实迷宫算法

论文概述 《基于现实迷宫地形的电脑鼠设计 》是由吴润强、庹忠曜、刘文杰、项璟晨、孙科学等人于2023年发表的一篇优秀期刊论文。其针对现阶段电脑鼠计算量庞大且不适用于现实迷宫地形的问题&#xff0c;特基于超声波测距与传统迷宫算法原理&#xff0c;设计出一款可在现实…

ARM(安谋) China处理器

0 Preface/Foreword 0.1 参考博客 Cortex-M23/M33与STAR-MC1星辰处理器 ARM China&#xff0c;2018年4月established&#xff0c;独立运行。 1 处理器类型 1.1 周易AIPU 1.2 STAR-MC1&#xff08;星辰处理器&#xff09; STAT-MC1&#xff0c;主要为满足AIOT应用性能、功…