当前位置: 首页 > news >正文

数据结构模拟题[五]

数据结构试卷(五)

一、选择题 (20 分)

1.数据的最小单位是( )。

(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2.设一组初始记录关键字序列为 (50 ,40, 95,20,15,70,60,45) ,则以增量 d=4 的一趟希尔排序结

束后前 4 条记录关键字为( )。

(A) 40 ,50,20,95 (B) 15 ,40,60, 20

(C) 15 ,20,40,45 (D) 45 ,40,15, 20

3.设一组初始记录关键字序列为 (25,50,15, 35,80,85,20,40,36,70),其中含有 5 个长度为 2 的

有序子表,则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为( )。

(A) 15 , 25,35,50, 20,40,80,85,36,70

(B) 15 ,25,35,50,80,20,85,40, 70,36

(C) 15,25,35,50,80,85,20,36, 40,70

(D) 15, 25,35,50, 80,20,36,40,70,85

4.函数 substr( “DATASTRUCTURE”, 5,9) 的返回值为( )。

(A) “STRUCTURE” (B) “DATA”

(C) “ASTRUCTUR” (D) “DATASTRUCTURE”

5.设一个有序的单链表中有 n 个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的

时间复杂度为( )。

(A) O(log 2n) (B) O(1) (C) O(n 2

) (D) O(n)

6.设一棵 m叉树中度数为 0 的结点数为 N0,度数为 1 的结点数为 Nl ,,, ,度数为 m的结点数为 Nm,则

N0=( )。

(A) N l +N2+,, +Nm (B) l+N 2+2N3+3N4+,, +(m-1)Nm

(C) N 2+2N3+3N4+,, +(m-1)Nm (D) 2N l +3N2+,, +(m+1)Nm

7.设有序表中有 1000 个元素,则用二分查找查找元素 X最多需要比较( )次。

(A) 25 (B) 10 (C) 7 (D) 1

8.设连通图 G 中的边集 E={(a ,b),(a,e),(a,c),(b, e), (e, d),(d,f) ,(f, c)},则从顶点 a 出发可

以得到一种深度优先遍历的顶点序列为( )。

(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb

9.设输入序列是 1、 2、3、,, 、 n,经过栈的作用后输出序列的第一个元素是 n,则输出序列中第 i 个

输出元素是( )。

(A) n-i (B) n-1-i (C) n+1-i (D) 不能确定

10 设一组初始记录关键字序列为 (45 ,80,55,40,42,85) ,则以第一个记录关键字 45 为基准而得到一

趟快速排序的结果是( )。

(A) 40 ,42,45,55,80,83 (B) 42 ,40,45, 80,85,88

(C) 42 ,40,45,55,80,85 (D) 42 ,40,45, 85,55,80

二、填空题 ( 共 20 分)

1. 设有一个顺序共享栈 S[0: n-1] ,其中第一个栈项指针 top1 的初值为 -1 ,第二个栈顶指针 top2 的初

值为 n,则判断共享栈满的条件是 ____________________。

2. 在图的邻接表中用顺序存储结构存储表头结点的优点是 ____________________。

3. 设有一个 n 阶的下三角矩阵 A,如果按照行的顺序将下三角矩阵中的元素(包括对角线上元素)存放

在 n(n+1) 个连续的存储单元中,则 A[i][j] 与 A[0][0] 之间有 _______个数据元素。

4. 栈的插入和删除只能在栈的栈顶进行,后进栈的元素必定先出栈,所以又把栈称为 __________表;队

列的插入和删除运算分别在队列的两端进行,先进队列的元素必定先出队列,所以又把队列称为

_________表。

5. 设一棵完全二叉树的顺序存储结构中存储数据元素为 ABCDEF,则该二叉树的前序遍历序列为

___________,中序遍历序列为 ___________,后序遍历序列为 ___________。

6. 设一棵完全二叉树有 128 个结点,则该完全二叉树的深度为 ________,有 __________个叶子结点。

7. 设有向图 G的存储结构用邻接矩阵 A 来表示,则 A 中第 i 行中所有非零元素个数之和等于顶点 i 的

________,第 i 列中所有非零元素个数之和等于顶点 i 的__________。

8. 设一组初始记录关键字序列 (k 1,k 2,,, , k n) 是堆,则对 i=1 ,2,, , n/2 而言满足的条件为

_______________________________ 。

9. 下面程序段的功能是实现冒泡排序算法,请在下划线处填上正确的语句。

void bubble(int r[n])

{

for(i=1;i<=n-1; i++)

{

for(exchange=0,j=0; j<_____________;j++)

if (r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}

if (exchange==0) return ;

}

}

10. 下面程序段的功能是实现二分查找算法,请在下划线处填上正确的语句。

struct record{int key; int others;};

int bisearch(struct record r[ ], int k)

{

int low=0,mid,high=n-1;

while(low<=high)

{

________________________________;

if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1;else low=mid+1;

}

return(0);

}

三、应用题 (32 分)

1. 设某棵二叉树的中序遍历序列为 DBEAC,前序遍历序列为 ABDEC,要求给出该二

叉树的的后序遍历序列。

2. 设无向图 G(如右图所示) ,给出该图的最小生成树上边的集合并计算最小生成

树各边上的权值之和。

3. 设一组初始记录关键字序列为 (15 ,17,18,22,35,51,60),要求计算出成功

查找时的平均查找长度。

4. 设散列表的长度为 8,散列函数 H(k)=k mod 7,初始记录关键字序列为 (25 ,31,8,27,13,68) ,要

求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。

四、算法设计题 (28 分)

1. 设计判断两个二叉树是否相同的算法。

2. 设计两个有序单链表的合并排序算法。

一、选择题

1.A 2.B 3.A 4.A 5.D

6.B 7.B 8.B 9.C 10. C

二、填空题

1. top1+1=top2

2. 可以随机访问到任一个顶点的简单链表

3. i(i+1)/2+j-1

4. FILO ,FIFO

5. ABDECF ,DBEAFC ,DEBFCA

6. 8,64

7. 出度,入度

8. ki<=k 2i && k i<=k 2i+1

9. n-i,r[j+1]=r[j]

10. mid=(low+high)/2 ,r[mid].key>k

三、应用题

1. DEBCA

2. E={(1,5),(5,2),(5,3),(3,4)},W=10

3. ASL=(1*1+2*2+3*4)/7=17/7

4. ASL1=7/6 ,ASL2=4/3

四、算法设计题

1. 设计判断两个二叉树是否相同的算法。

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));

}

2. 设计两个有序单链表的合并排序算法。

void mergelklist(lklist *ha,lklist *hb,lklist *&hc)

{

lklist *s=hc=0;

while(ha!=0 && hb!=0)

if(ha->data<hb->data){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;}

else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;}

if(ha==0) s->next=hb; else s->next=ha;

相关文章:

数据结构模拟题[五]

数据结构试卷&#xff08;五&#xff09; 一、选择题 (20 分) 1&#xff0e;数据的最小单位是&#xff08; &#xff09;。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 2&#xff0e;设一组初始记录关键字序列为 (50 &#xff0c;40&#xff0c; 95&#xff0c;20…...

IDEA切换窗口快捷键失效

问题描述&#xff1a; 在idea中&#xff0c;如果切换窗口的快捷键&#xff08;Alt Tab&#xff09;失效了&#xff0c;可以通过清除缓存的方式修复...

QT中使用图表之QChart绘制X轴为日期时间轴的折线图

显然X轴是日期时间轴的话&#xff0c;那么我们使用的轴类就得是QDateTimeAxis QChart中日期时间轴的精度是毫秒 因此图表里面的数据的x值需要是一个毫秒数&#xff0c;才能显示出来 --------------------------------------------------------------------------------------…...

【传知代码】短期电力负荷(论文复现)

&#x1f351;个人主页&#xff1a;Jupiter. &#x1f680; 所属专栏&#xff1a;传知代码 欢迎大家点赞收藏评论&#x1f60a; 目录 备注前言介绍问题背景复现&#xff1a;一. 多维特征提取的提取框架&#xff1a;二. 论文中进行性能测试的MultiTag2Vec-STLF模型&#xff1a;三…...

ubuntu20.04 加固方案-设置重复登录失败后锁定时间限制

一、编辑PAM配置文件 打开终端。 使用文本编辑器&#xff08;如vim&#xff09;编辑/etc/pam.d/common-auth文件。 sudo vim /etc/pam.d/common-auth 二、添加配置参数 在打开的配置文件中&#xff0c;添加或修改以下参数&#xff1a; auth required pam_tally2.so deny5 un…...

【综合算法学习】(第十三篇)

目录 解数独&#xff08;hard&#xff09; 题目解析 讲解算法原理 编写代码 单词搜索&#xff08;medium&#xff09; 题目解析 解析算法原理 编写代码 解数独&#xff08;hard&#xff09; 题目解析 1.题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09;…...

Web3 Key Talking #4|Sui有何不同?及其发展路线图

活动时间&#xff1a; 2024 年 10 月 31 日&#xff08;周四&#xff09;20:00–21:00&#xff08;UTC8&#xff09; 会议链接&#xff1a; 腾讯会议 会议 ID &#xff1a;429–339–777 主持&#xff1a;Sanzhisanzhichazi1 嘉宾&#xff1a;uvdwangtxxl&#xff0c;Sui …...

Axios 请求超时设置无效的问题及解决方案

文章目录 Axios 请求超时设置无效的问题及解决方案1. 引言2. 理解 Axios 的超时机制2.1 Axios 超时的工作原理2.2 超时错误的处理 3. Axios 请求超时设置无效的常见原因3.1 配置错误或遗漏3.2 超时发生在建立连接之前3.3 使用了不支持的传输协议3.4 代理服务器或中间件干扰3.5 …...

数据结构+算法

一、数据结构 1、线性结构 数组&#xff1a; 访问&#xff1a;O(1)访问特定位置的元素&#xff1b;插入&#xff1a;O(n)最坏的情况发生在插入发生在数组的首部并需要移动所有元素时&#xff1b;删除&#xff1a;O(n)最坏的情况发生在删除数组的开头发生并需要移动第一元素后…...

利用ExcelJS封装一个excel表格的导出

ExcelJS 操作和写入Excel 文件。 直接上代码&#xff0c;js部分&#xff1a; exportFn.js import ExcelJS from exceljs; import { saveAs } from file-saver;export function exportExcleUtils(tHeader, filterVal, listData, fileName) {//设置工作簿属性const workbook ne…...

AI 原生时代,更要上云:百度智能云云原生创新实践

本文整理自百度云智峰会 2024 —— 云原生论坛的同名演讲。 我今天分享的主题&#xff0c;是谈谈在云计算和 AI 技术快速发展和深入落地的背景下&#xff0c;百度智能云在云原生的基础设施产品和技术层面做的一些创新实践。 毋庸置疑&#xff0c;过去十几年云计算和 AI 技术是…...

C语言程序编译运行

程序功能&#xff1a;使用 printf() 输出 “Hello, World!”。 C语言源程序&#xff1a; #include <stdio.h> int main() {// printf() 中字符串需要引号printf("Hello, World!");return 0; }编译过程&#xff1a; vim hello.c gcc hello.c -o hello ./hell…...

视频点播系统扩展示例

更多的前端页面&#xff08;如视频详情页、用户注册页等&#xff09;。更复杂的业务逻辑&#xff08;如视频评论、搜索功能等&#xff09;。安全性和权限管理&#xff08;如用户角色管理、权限控制等&#xff09;。其他技术细节&#xff08;如文件上传、分页查询等&#xff09;…...

echo $? —— Linux 中的退出状态码详解

在 Linux 系统中&#xff0c;echo $? 是一个非常重要的命令&#xff0c;用于显示上一条命令的退出状态码。这个小小的符号组合可以帮助我们判断命令是否成功执行&#xff0c;同时也为编写自动化脚本提供了基础支持。本文将详细介绍 echo $? 的用法及其在实际开发中的应用。 …...

heic格式转化jpg最简单方法?快来学习这几种简单的转换方法!

heic格式转化jpg最简单方法&#xff1f;在当今的数字图像处理领域&#xff0c;HEIC格式以其卓越的压缩效率和高质量图像表现&#xff0c;正逐渐崭露头角并受到业界的深切关注&#xff0c;HEIC格式凭借先进的压缩技术&#xff0c;成功地在保持图像清晰度的同时&#xff0c;大幅度…...

力扣(leetcode)每日一题 3259 超级饮料的最大强化能量|动态规划

3259. 超级饮料的最大强化能量 题干 来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB&#xff0c;数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。 你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而…...

Webserver(2.7)内存映射

目录 内存映射内存映射相关系统调用内存映射的注意事项如果对mmap的返回值(ptr)做操作&#xff0c;释放内存&#xff08;munmap&#xff09;是否能够成功&#xff1f;如果open时O_RDONLY&#xff0c;mmap时prot参数指定PROT_READ | PROT_WRITE会怎样&#xff1f;如果文件偏移量…...

vue3父子组件传值,子组件暴漏方法

1.父传子 defineProps 父组件直接通过属性绑定的方式给子组件绑定数据&#xff0c;子组件通过defineProps接收函数接收 其中v-model是完成事件绑定和事件监听的语法糖。v-model算是v-bind和v-on的简洁写法&#xff0c;等价于 <c-input ref"inputRef" :modelValue…...

Linux_04 Linux常用命令——tar

一、命令格式 tar [选项] [归档文件] [要处理的文件或目录]1、选项 c创建归档文件x解压缩归档文件z使用gzipj使用bzip2v处理过程显示信息f指定归档文件名称 2、归档文件-可指定目录及文件名 /home/wang.tar.gz 3、要处理的文件或目录 /home/study1/wang 二、常见命令 t…...

Java项目实战II基于Java+Spring Boot+MySQL的编程训练系统(源码+数据库+文档)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 在当今数字…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...