2022年暨南大学计算机830真题

news/2024/5/7 8:26:29/文章来源:https://blog.csdn.net/u014339447/article/details/127085953

学科、专业名称：网络空间安全

研究方向：网络空间安全083900

考试科目名称及代码：数据结构830

考生注意：所有答案必须写在答题纸(卷)上，写在本试题上一律不给分。

一、 单项选择题 (每题2分，共20分)

  1. 下列程序段的时间复杂度是 ( )。

    void func(int n){int i = 0,m = 0;while(m < n * n){i++:m=m+i;}
}

    A. O(n)

    B. O(logn)

    C. O(nlogn)

    D. O(n2)

  2. 设p指向一个非空双向链表中的某个结点，将一个q所指新结点插入到该双向链表中，使其成为p所指结点的前驱结点，能正确完成此要求的语句段是 ( )。

    A. q->next=p; q->prior=p->prior; p->prior=q; p->prior->next=q;

    B. p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;

    C. q->prior=p->prior; q->next=p; p->prior->next=q;p->prior=q;

    D. q->prior=p->next; q->next=p; p->prior->next=q; p->prior=q;

  3. 一个栈的入栈序列为1,2,3，···，n，其出栈序列是pi，p2，p3，···，Pn。若p1＝4，则p3可能取值的个数是多少？()

    A. n-3

    B. n-2

    C. n-1

    D. 无法确定

  4. 二维数组SA中，每个元素的长度为3个字节，行下标 i 从0到7，列下标 j 从0到9，从首地址SA开始连续存放在存储器内，且采用行优先顺序存储，元素A[4][5]的起始地址为 ( )。

    A. SA+141

    B. SA+111

    C. SA+135

    D. SA+165

  5. 一棵度为4的树 T 中，若有10个度为 4 的结点，20个度为 3 的结点，1个度为2的结点，12个度为1的结点，则树 T 的叶子结点个数是 ( )。

    A. 63

    B. 81

    C. 105

    D. 72

  6. 设森林 F 中有 4 棵树 T1，T2，T3，T4，其结点个数分别为 10、15、12、19，将森林 F 转换成一棵二叉树BT，BT 的根结点 R 为 T1 上的结点，则 R 的左子树上的结点个数是 ( )。

    A. 9

    B. 10

    C. 19

    D. 27

  7. 设哈夫曼编码的长度不超过4，若已对两个字符编码为 1 和 01，则最多还可对( )个字符编码。

    A. 2

    B. 3

    C. 4

    D. 7

  8. 下列四个序列中，哪一个是堆 ( )。

    A. 65,55,40,10,30,25,20,15

    B. 65,55,30,15,25,40,20,10

    C. 65,40,55,10,25,30,20,15

    D. 65,55,40,30,15,25,20,10

  9. 在含有33个结点的二叉排序树上，查找关键字为34的结点，以下 ( ) 是可能的关键字比较序列？

    A. 25,37,16,45,34

    B. 45,37,16,25,34

    C. 45,25,16,37,34

    D. 16,37,25,45,34

  10. 序列（5,3,12,9,4,2,10.6,8）是某排序方法第一趟后的结果，该排序算法可能是（）。

    A.冒泡排序

    B.堆排序

    C.归并排序

    D.简单选择排序

二、填空题（每空2分，共20分）

  1. 线性结构中元素之间存在一对一关系，树型结构中元素之间存 ( ) 关系，图型结构中元素之间存在 ( ) 关系。

  2. 高度为3的满二叉树B（设根结点为第一层），将其还原为森林T，其中包含根结点的那棵树中有 ( ) 个结点。

  3. 采用邻接矩阵的方法存储图时，查找图的某一条边的时间复杂度是 ( ) 。

  4. 已知序列（12,18,4,3,6,13,2,9,19,8），采用快速排序对该序列作升序排序的第一趟结果是 ( ) 。

  5. 设G为具有37条边的无向连通图，则G至少有 ( ) 个顶点,至多有 ( ) 个顶点。

  6. 含有n个顶点e条边的无向连通图，利用Prim算法生成最小生成树的时间复杂度为 ( ) 。

  7. 一棵二叉树的后序序列为CEFAKHGBD，中序序列为CAEFDKBGH，则先序序列为 ( ) 。

  8. 若使用二叉链表作为树的存储结构，在有n个结点的二叉链表中空链域的个数为 ( ) 。

三. 判断题（每题2分，共20分，正确的选T，错误的选F）

  1. 数据的逻辑结构包括顺序结构和链式结构两种类型。 ( )

  2. 队列的链式存储结构和顺序存储结构相比，其中一个优点是节省了存储空间。 ( )

  3. 一棵二叉树的每个结点有且仅有一个前驱结点。 ( )

  4. 采用邻接表的方式存储一个图，结果可能是不唯一的。 ( )

  5. 在一个AOE网中，一个关键活动提前完成，另一个关键活动延期完成，那么整个工程有可能会按时完成。 ( )

  6. Dijkstra算法除了用来求一个带权有向图中两个顶点之间的最短路径之外，还可以用来判定图中是否存在回路。 ( )

  7. 在一个拓扑有序序列中，任意两个相继的结点之间在对应的图中都存在一条路径。 ( )

  8. 堆排序算法中，当待排记录初始序列已经为按关键字顺序有序时，其时间复杂度将从O（nlogn）蜕化到O（㎡），其中n为序列中元素的个数。 ( )

  9. 线索二叉树中一个结点的左线索指向的是该结点的双亲结点。 ( )

  10. 对大顶堆进行层次遍历可以得到一个有序序列。 ( )

四、简答题（共40分）

  1. 简述创建线索二叉树的目的，以及建立线索二叉树的思路。（4分）

  2. 给定关键字序列T＝（11,13,12,14,5,6,8,7,9,10），采用快速排序算法，以第一个元素为枢轴，对该序列由小到大排序，并写出具体排序过程，要求给出每趟排序后的中间结果。（3分）

  3. 对于给定11个数据元素的有序表T＝｛2,3,10,15,20,25,28,29,30,35,40｝采用折半查找，请回答以下问题。（本题共三小题，前两小题各2分，第三小题4分，共计8分）

    （1）若查找给定值为20的元素，将依次与表中哪些元素比较？

    （2）若查找给定值为26的元素，将依次与哪些元素比较？

    （3）假设查找表中每个元素的概率相同，求查找成功时的平均查找长度和查找不成功时的平均查找长度

  4. 设有一段正文由字符集｛A. B，C，D. E. F）组成，正文长度为100个字符，其中每个字符在正文中出现的次数分别为17,12,5,28,35,3。若采用Huffman编码对这段正文进行压缩存储，请完成如下问题。（本题共四小题，每小题各2分，共计8分）

    （1）根据上述背景，构造出Huffman树（规定权值较小的结点为左子树）。

    （2）给出每个字符的Huffiman编码。

    （3）若有某一段正文的二进制编码序列为01101010110011，请将它翻译成所对应的正文。

    （4）计算按Huffman 编码压缩存储这段正文共需要多少个字节。

  5. 已知一个有向网G的带权邻接矩阵如下所示，回答以下问题。（本题共两小题，第一小题2分，第二小题5分，共计7分）

    (1) 画出该带权有向图（假设顶点编号为VO，VI，V2，V3，V4，V5）.

    (2) 使用Dijkstra（迪杰斯特拉）算法求出从顶点VO到其余各顶点的最短路径，并写出过程。

  6. 已知一个无向图如下图2所示，分别用Prim和Kruskal 算法生成最小生成树，要求画出构造过程（设Prim算法以顶点V1为起点）。（10分）

五、算法填空（共2小题，每空2分，共20分）

  1. 下面是先序遍历二叉树的非递归算法，请在空白处填上适当内容，使其成为一个完整算法。

    typedef struct BiTNode
{TElemType data;struct BiTNode *lchild, *rchild:
} BiTNode, *BiTree;
void PreOrderTraverse(BiTree T, Status (*Visit)(TElemType))
{BTNode *p;SqStack *st;InitStack(st);if (T != NULL){Push(st, T);while (______){______Visit(p->data);if (p->rchild != NULL)______if (______)______}}
}

  2. 给定一个带头结点的双向链表L，至少包含一个数据结点。以下代码为实现将L中所有结点按照数据值递增有序排列，排序算法为直接插入排序法，请将代码中空白处填写完整。

    typedef struct DiLNode{ElemType data;struct DiLNode *prior;struct DiLNode *next;} DilNode.*DiLinkList;void sort(DiLNode *&L){DiLNode *p, *pre.*q;p = L->next->next;L->next->next = NULL;while (p != NULL){q = p->next;pre = L;while (pre->next != NULL && pre->next->data < p->data)pre = pre->next;______if (pre->next != NULL)________________________}}

六、编写算法（共3小题，每小题10分，共30分）

  1. 设有一个长度为n的线性表L采用顺序存储结构存储。设计一个算法，以第一个元素为分界线（基准），将所有小于或等于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。要求算法的时间复杂度为O（n），且算法最多只能借助1个辅助变量。

  2. 设图G有n个顶点，按照如下提示设计一个算法，将G的邻接矩阵转换为对应的邻接表。G的邻接表存储类型定义如下：

    typedef struct Anode
{int adjvex;struct ANode *nextarc;InfoType weight;
} ArcNode;
typedef struct Vnode
{Vertex data;ArcNode *firstac;
} VNode;
typedef struct
{VNode adjlist[MAXV];int n, e;
} AdjGraph;

    G的邻接矩阵存储类型定义如下：

    typedef struct
{int no;InfoType info;
} VertexType;
typedef struct
{int edges[MAXV][MAXV];int n, e;VertexType vexs[MAXV];
} MatGraph:

  3. 一个公司在某地区有n个产品销售点，现打算在这个地区的某个销售点上建一个中心仓库，负责向该地区的各个销售点提供销售产品。由于运输线路和公交条件不同，向每个销售点运输一次产品的费用也不相同。若公司每天都会向每个运输点运输一次产品，试设计一个算法，以帮助公司解决应将中心仓库建立在哪个销售点上才能使运输费用达到最低的问题。

其他年份真题及答案：https://app2098.acapp.acwing.com.cn/

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

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

相关文章

[python刷题模板] 珂朵莉树 ODT （基于支持随机访问的跳表

[python刷题模板] 珂朵莉树 ODT （基于支持随机访问的跳表

[python刷题模板] 珂朵莉树 ODT &#xff08;基于支持随机访问的跳表&#xff09; 一、 算法&数据结构1. 描述2. 复杂度分析3. 常见应用4. 常用优化二、 模板代码0. 区间推平(lg)&#xff0c;单点询问(lg) CF292E. Copying Data1. 区间推平&#xff0c;区间询问最小值2. 区…
阅读更多...
Unity Lighting 面板的参数设置用途详细总结

Unity Lighting 面板的参数设置用途详细总结

一、Environment 环境光 二、Scene 1、如果选择生成LightMap 要关闭实时光&#xff0c;开启烘培光 lighting mode为Mixed时&#xff0c;lighting settings的Mixed Lighting可用于设置混合的方式&#xff1a;Baked Indirect mode提供最高质量的光照&#xff0c;其设置只牵扯间…
阅读更多...
windows环境下elasticsearch使用教程

windows环境下elasticsearch使用教程

windows环境下elasticsearch使用教程如下&#xff1a; 一、首先安装jdkElasticSearch是基于lucence开发的&#xff0c;lucence是apache开发的&#xff0c;因此ElasticSearch运行环境就需要java jdk支持。所以要先安装JAVA环境。由于ElasticSearch 5.x 往后依赖于JDK 1.8的&…
阅读更多...
HAPPE＋ER：一款让脑电研究人员“更快乐”的软件，可用于事件相关电位(ERP)分析的标准化预处理管道

HAPPE＋ER：一款让脑电研究人员“更快乐”的软件，可用于事件相关电位(ERP)分析的标准化预处理管道

导读 事件相关电位(ERP)设计是用脑电图(EEG)检测神经认知功能的常用方法。然而&#xff0c;传统的ERP数据预处理方法是手动编辑&#xff0c;这是一个主观且耗时的过程。最近创建了许多自动化通道&#xff0c;以满足EEG数据预处理的标准化、自动化和量化的需求&#xff1b;然而…
阅读更多...
知识经济时代的基石：知识协同

知识经济时代的基石：知识协同

管理学家彼得德鲁克&#xff08;1994&#xff09;指出&#xff1a;“企业管理的本质不在于技术与程序&#xff0c;而在于使知识有效。”在知识占主导地位的社会里&#xff0c;企业依靠知识进行创新的能力代表了企业在竞争中的优势&#xff0c;也是企业成功与否的标志。 世界变…
阅读更多...
C++——string的封装

C++——string的封装

参考string类完成my_string类 #include <iostream> #include<cstring> using namespace std; class my_string { private:char *str;int len; public://无参构造my_string(){len 15;str new char[len];cout<<"无参构造"<<endl;}//有参构造…
阅读更多...
IDEA通过原型（骨架）创建MavenJavaWeb项目

IDEA通过原型（骨架）创建MavenJavaWeb项目

IDEA通过原型&#xff08;骨架&#xff09;创建MavenJavaWeb项目 目录IDEA通过原型&#xff08;骨架&#xff09;创建MavenJavaWeb项目一、通过原型&#xff08;骨架&#xff09;创建MavenJavaWeb项目二、配置tomcat一、通过原型&#xff08;骨架&#xff09;创建MavenJavaWeb项…
阅读更多...
【PTA】输出学生成绩

【PTA】输出学生成绩

个人名片&#xff1a; 博主&#xff1a;酒徒ᝰ. 个人简介&#xff1a;沉醉在酒中&#xff0c;借着一股酒劲&#xff0c;去拼搏一个未来。 专栏&#xff1a;PTA习题及解析 介绍&#xff1a;记录了博主在pta学习练题 目录前言1.简介2.优点一、题目二、代码前言 1.简介 “PTA程序…
阅读更多...
【面试题】面试官： Vue如何实现权限管理？

【面试题】面试官： Vue如何实现权限管理？

我正在参加「掘金启航计划」 一、权限管理 权限管理就是让不同的用户只能访问自己权限内的资源&#xff0c;有以下几种 路由权限&#xff0c;用户登录后只能看到自己权限内的导航菜单&#xff0c;且只能访问自己权限内的路由地址视图权限&#xff0c;用户只能看到自己权限内…
阅读更多...
朗涛任命Juanita Zhang为中国大陆区总经理，Peggy Hon为中国香港区总经理

朗涛任命Juanita Zhang为中国大陆区总经理，Peggy Hon为中国香港区总经理

在迅速发展的消费环境中&#xff0c;带领才华横溢的多元创意团队&#xff0c;持续推动业务发展 &#xff08;中国上海&#xff0c;2022年9月27日&#xff09;近日&#xff0c;全球顶尖的品牌设计与咨询公司朗涛宣布重要人事任命&#xff0c;分别任命Juanita Zhang为中国大陆区总…
阅读更多...
Eureka注册不上或注册后IP不对(多网卡的坑)

Eureka注册不上或注册后IP不对(多网卡的坑)

Eureka注册不上或注册后IP不对&#xff08;多网卡的坑&#xff09; 一、问题发现 ​ 使用SpringCloud一套的微服务项目在开发测试环境都再正常不过了&#xff0c;到生产部署的时候启动服务就死活无法启动&#xff0c;去看启动日志发现&#xff0c;在获取配置中心配置时连接不…
阅读更多...
SpringBoot保姆级教程（二）SpringBoot入门

SpringBoot保姆级教程（二）SpringBoot入门

目录 一.通过官网搭建项目 二.通过IDEA脚手架搭建项目 三.SpringBoot项目结构 四.通过Maven搭建项目 五.编写Java代码 一.通过官网搭建项目 接下来我们搭建一个SpringBoot项目&#xff0c;并引入SpringMVC的功能&#xff0c; 首先我们可以通过官网搭建项目&#xff1a; 1 …
阅读更多...
MYSQL介绍——数据库的增删改及常用函数

MYSQL介绍——数据库的增删改及常用函数

数据操作语言——INSERT语句 Insert 语句可以向数据库中插入数据&#xff0c;可以是一条数据&#xff0c;也可以是多条数据&#xff0c;它有以下语法形式&#xff1a; 下面给出一个插入语法的示例&#xff1a; INSERT INTO t_dept(deptno,dname,loc) VALUES(50,司法部,济南)…
阅读更多...
（附源码）springboot篮球场地预约系统 毕业设计 345655

（附源码）springboot篮球场地预约系统 毕业设计 345655

蓝球场地预约系统的设计与实现 摘 要 传统的场地预约需要客户亲自到场地所在位置或指定地点进行&#xff0c;由于预约记录多是认为完成&#xff0c;易于出现错误和漏洞&#xff0c;管理效率低&#xff0c;特别是场地繁杂时&#xff0c;传统的预约方式已经完全不能满足要求。 远…
阅读更多...
一文读懂 Handler 消息处理机制（源码实战）

一文读懂 Handler 消息处理机制（源码实战）

Android 异步消息处理机制解析 Android 中的异步消息处理主要由四个部分组成&#xff0c;Message、Handler、MessageQueue、Looper 但是当我们提到 Android 异步处理机制的时候&#xff0c;我们首先会想到 Handler&#xff0c;而大多数Android 初学者对于 Handler 的作用仅局…
阅读更多...
医院患者挂号app(IDEA,SpringBoot,SSM,MySQL)+全套视频教程

医院患者挂号app(IDEA,SpringBoot,SSM,MySQL)+全套视频教程

【项目功能介绍】 本系统包含后台管理和前端app双端系统&#xff0c;后台管理的功能包含: 登录, 退出, 修改管理员信息(基本信息与头像),资源管理, 角色管理&#xff0c;资源权限分配, 数据字典管理&#xff0c;用户管理,医院管理, 医生管理; app端功能包含医生与患者二种角色…
阅读更多...
CNN中添加HOG特征的pytorch实现——基于Alexnet

CNN中添加HOG特征的pytorch实现——基于Alexnet

CNN中添加HOG特征的pytorch实现——基于Alexnet 几天前花了差不多两天时间基本实现了这个需求&#xff0c;经历了从一开始的毫无头绪&#xff0c;到最后对CNN模型 (加载数据集和数据流向) 和HOG特征有了更进一步的理解&#xff0c;实现需求之后又杂七杂八的看了一些相关的文章…
阅读更多...
DolphinScheduler 进阶（资源中心）

DolphinScheduler 进阶（资源中心）

文章目录内置参数引用依赖资源内置参数 DolphinScheduler 提供了一些时间相关的系统参数&#xff0c;方便定时调度使用。 1&#xff09;基础内置参数 变量名参数说明system.biz.date${system.biz.date}定时时间前一天&#xff0c;格式为 yyyyMMddsystem.biz.curdate${system…
阅读更多...
资深腾讯架构师耗时2个月整理的Redis全套学习笔记，涵盖所有核心知识点

资深腾讯架构师耗时2个月整理的Redis全套学习笔记，涵盖所有核心知识点

Redis 是一个开源、基于内存、使用 C 语言编写的 key-value 数据库&#xff0c;并提供了多种语言的 API。它的数据结构十分丰富&#xff0c;基础数据类型包括&#xff1a;string&#xff08;字符串&#xff09;、list&#xff08;列表&#xff0c;双向链表&#xff09;、hash&a…
阅读更多...
18【命令设计模式】

18【命令设计模式】

文章目录十八、命令设计模式18.1 命令设计模式简介18.1.1 命令设计模式概述18.1.2 命令设计模式的UML类图18.2 命令设计模式的实现18.3 命令设计模式的优缺点十八、命令设计模式 18.1 命令设计模式简介 18.1.1 命令设计模式概述 命令设计模式&#xff08;Command Pattern&am…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业