信息学奥赛初赛天天练-43-CSP-J2020基础题-链表、连通图、2进制转10进制、栈、队列、完全二叉树、哈希表应用

PDF文档公众号回复关键字:20240710
在这里插入图片描述

2020 CSP-J 选择题

单项选择题(共15题,每题2分,共计30分:每题有且仅有一个正确选项)

7.链表不具有的特点是()

A.可随机访问任一元素

B.不必事先估计存储空间

C.插入删除不需要移动元素

D.所需空间与线性表长度成正比

8.有 10 个顶点的无向图至少应该有( )条边才能确保是一个连通图

A.9

B.10

C.11

D.12

9.二进制数 1011 转换成十进制数是( )

A.11

B.10

C.13

D.12

11.下图中所使用的数据结构是( )

A.栈

B.队列

C.二叉树

D.哈希表

12.独根树的高度为 1。具有 61 个结点的完全二叉树的高度为( )

A.7

B.8

C.5

D.6

2 相关知识点

1) 链表

是一种常见的数据结构,它是由一系列节点(Node)组成,每个节点包含两部分:数据域和指针域。数据域用于存储数据,指针域用于存储下一个节点的地址。链表的第一个节点称为头节点(Head),最后一个节点称为尾节点(Tail),尾节点的指针域指向空(NULL)

链表占用空间大小,和链表的长度有关,没增加一个节点,增加一个数据节点和一个指针节点,存储空间和链表长度成正比

随机存取

随机存取(直接存取,Random Access)指的是当存储器中的数据被读取或写入时,所需要的时间与该数据所在的物理地址无关

顺序存取

顺序存取 (Sequential Access)是一种按记录的逻辑顺序进行读、写操作的存取方法,所需要的时间与该数据所在的物理地址有关。

顺序存取表现为:在存取第N个数据时,必须先访问前(N-1)个数据

#include<bits/stdc++.h>
using namespace std;
/*
  随机存取、顺序存取 
*/ 
int a[10]={0,1,2,3,4,5,6,7,8,9}; 
int main(){
	cout<<a[9]<<endl;//随机读取下标为9的元素 输出 9  

	for(int i=0;i<10;i++){//顺序存储 逐一读取 
		cout<<a[i]<<" ";		
	}
	return 0;
}

数组可以随机以及顺序存取,而链表只能顺序存取

内存分配

数组静态分配内存,定义时指定内存大小,链表动态分配内存,使用是指定内存大小

数组是一种线性表数据结构,有一组连续的内存空间,链表是通过指针将一组零散的内存块串联起来使用的数据结构,不需要一块连续的内存空间

链表的删除

链表通过指针建立起数据之间的联系,删除节点时,只需要改变对应的指针指向即可,不需要移动数组的元素

2) 连通图

连通性

如果任意两点间存在路径,此图具有连通性

无向图的连通性

任意两点是连通的,任意两点都可以形成通路

最小边数

n个节点的无向连通图最小边数为n-1条边

树为一种连通图,n个节点的树,边数为n-1

3) 2进制转10进制

按权展开,但要注意各个位的权,最低位(最右边)的权是0次方,权值为1

向左为2^1, 2^2, 2^3, 2^4, 2^5…

(11010110)2=1×2^7+1×2^6+0×2^5+1×2^4+0×2^3+1×2^2+1×2^1+0×2^0=(214)10

向右,小数部分,2^(-1), 2^(-2), 2^(-3), 2^(-4), 2^(-5)…

(1011.01)2=(1*2^3+1*2^1+1*2^0+1*2^(-2))=8+2+1+0.25=11.25

4) 数据结构

栈又名堆栈,是一种限定仅在表尾进行插入和删除操作的线性表,这一端称为栈顶,另一端称为栈底

栈中的数据元素遵守后进先出的原则

在这里插入图片描述

队列

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(head)进行删除操作,而在表的后端(tail)进行插入操作

队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头

队列可以理解成我们平时的排队,先进入的先出去

二叉树

每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒

例如下面是一棵二叉树

完全二叉树

除了最下层,其他每层都饱满,去除最后一层是一棵满二叉树,最下层的结点都集中在该层最左边的若干位置上

哈希表

哈希表(Hash Table)是一种通过键(key)直接访问存储在内存中的特定位置的值(value)的数据结构。它支持快速的查找、添加和删除操作,其平均时间复杂度为O(1)

哈希表的工作原理基于哈希函数,该函数将键映射到数组的索引位置,可以随机读取

3 思路分析

7.链表不具有的特点是( A )

A.可随机访问任一元素

B.不必事先估计存储空间

C.插入删除不需要移动元素

D.所需空间与线性表长度成正比

分析

链表只能顺序访问,不能随机访问

8.有 10 个顶点的无向图至少应该有( A )条边才能确保是一个连通图

A.9

B.10

C.11

D.12

分析

无向连通图,需要每2个节点都可以连通,n个节点,需要n-1条边,所以选A

如下图4个结点,3条边是连通图,任意2个结点都是连通的

9.二进制数 1011 转换成十进制数是( A )

A.11

B.10

C.13

D.12

分析

/*
按权展开,最低位(最右边)的权是0次方,权值为1
向左为2^1, 2^2, 2^3, 2^4, 2^5......
*/
(1011)2=1*2^3+0*2^2+1*2^1+1*2^0=8+0+2+1=11

11.下图中所使用的数据结构是( A )

A.栈

B.队列

C.二叉树

D.哈希表

分析

栈的操作是后进先出,队列操作是先进先出

如图 A进 B 进 B 出 C 进 符合栈的操作

二叉树需要构造树,没有体现

哈希表需要对键进行哈希函数运算,没有体现

12.独根树的高度为 1。具有 61 个结点的完全二叉树的高度为( D )

A.7

B.8

C.5

D.6

分析

独根树的高度为1,一个节点时树的高度为1

完全二叉树的特点为:除最后一层,都是满的

满二叉树结点个数
    
高度 1  - 结点 1   -2^1-1
高度 2  - 结点 3   -2^2-1
高度 3  - 结点 7   -2^3-1
高度 4  - 结点 15  -2^4-1
高度 5  - 结点 31  -2^5-1
高度 6  - 结点 63  -2^6-1
61个结点,最后一层不满,所以高度为6,第6层不满
所以选D

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

关于前端数据库可视化库的选择,vue3+antd+g2plot录课计划

之前&#xff1a;antdv 现在&#xff1a;g2plot https://g2plot.antv.antgroup.com/manual/introduction 录课内容&#xff1a;快速入门 图表示例&#xff1a; 选择使用比较广泛的示例类型&#xff0c;录课顺序如下&#xff1a; 1、折线图2、面积图3、柱形图4、条形图5、饼…

SpringCloud代码实战

项目结构 实例实现功能:实现通过id查询用户的订单信息 OrderCommon&#xff1a;公共的一些模块类型&#xff0c;此处为一个user对象 Eureka-Service:配置Eureka的启动类&#xff0c;服务端 Order-Service:提供查询功能的服务端 Order-Client:查询的客户端 OrderCommon代码…

西安明德理工学院师生莅临泰迪智能科技开展参观见习活动

为进一步深化校企合作&#xff0c;落实高校应用型人才培养。7月8日&#xff0c;西安明德理工学院与广东泰迪智能科技股份有限公司联合开展学生企业见习活动。西安明德理工学院金融产业学院副院长刘敏、金融学专业负责人张莉萍、金融学专业教师曹艳飞、赵浚妤、泰迪智能科技董事…

软件架构之架构风格

软件架构之架构风格 9.3 软件架构风格9.3.1 软件架构风格分类9.3.2 数据流风格9.3.3 调用/返回风格9.3.4 独立构件风格9.3.5 虚拟机风格9.3.6 仓库风格 9.4 层次系统架构风格9.4.1 二层及三层 C/S 架构风格9.4.2 B/S 架构风格9.4.3 MVC 架构风格9.4.4 MVP 架构风格 9.5 面向服务…

【日常记录】【插件】js 获取浏览器信息、操作系统等相关信息

文章目录 1. 原生方式2. 插件的方式2.1 Bowser 的基本使用2.2 UAParser2.3 Platform.js 参考链接 1. 原生方式 原生方式可以通过 navigator.userAgent 来获取 需要写一个正则来匹配&#xff0c;获取相关的信息 2. 插件的方式 获取浏览器版本相关信息的库主要有以下几个 Bowser&…

01MFC建立单个文件类型——画线

文章目录 选择模式初始化文件作用解析各初始化文件解析类导向创建鼠标按键按下抬起操作函数添加一个变量记录起始位置注意事项代码实现效果图虚实/颜色线选择模式 初始化文件作用解析 运行: 各初始化文件解析 MFC(Microsoft Foundation Classes)是一个C++类库,用于在Win…

力扣 双指针基础

class Solution {public void moveZeroes(int[] nums) {int l 0;//慢指针但先走for (int r 0; r < nums.length; r) {//快指针&#xff0c;遍历次数if (nums[r] 0) continue;//l比r先到&#xff0c;在此处定住l&#xff0c;r继续移动int t nums[l];nums[l] nums[r];num…

今天小编强烈推荐几款国产APP!

AI视频生成&#xff1a;小说文案智能分镜智能识别角色和场景批量Ai绘图自动配音添加音乐一键合成视频https://aitools.jurilu.com/ 今天小编强烈推荐几款国产APP,算得上是国产之光。如果能帮助到大家&#xff0c;别忘了给小编点点赞加关注哟&#xff01;更多精彩还在后面。 一、…

节点流与处理流:深入解析Java中的IO流

节点流与处理流&#xff1a;深入解析Java中的IO流 1、节点流&#xff08;Node Stream&#xff09;1.1 定义1.2 好处1.3 示例 2、处理流&#xff08;Processing Stream&#xff09;2.1 定义2.2 好处2.3 创建特征2.4 示例 3、总结 &#x1f496;The Begin&#x1f496;点点关注&…

关于string的‘\0‘与string,vector构造特点,反迭代器与迭代器类等的讨论

目录 问题一&#xff1a;关于string的\0问题讨论 问题二&#xff1a;C标准库中的string内存是分配在堆上面吗&#xff1f; 问题三&#xff1a;string与vector的capacity大小设计的特点 问题四&#xff1a;string的流提取问题 问题五&#xff1a;迭代器失效 问题六&#xf…

05_Shell索引数组

05_Shell索引数组 数组定义 #!/bin/basharr(1 2 3 "www.baidu.com")获取数组元素 #!/bin/basharr(1 2 3 "www.baidu.com")#通过下表获取元素 下标从1开始 ${arr[1]}#获取数组所有元素 ${arr[*]} 或者 ${arr[]}#获取数组长度 ${#arr[*]} 或者 ${#arr[*]}#获…

LeetCode(2)合并链表、环形链表的约瑟夫问题、链表分割

一、合并链表 . - 力扣&#xff08;LeetCode&#xff09; 题目描述&#xff1a; /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct …

选择最佳工具:评估8款顶级App界面设计软件

在如今的数字化时代&#xff0c;设计师也离不开各种界面设计软件来辅助自己的设计工作。在各种界面设计软件的帮助下&#xff0c;设计师们能够更好、更快地完成自己的设计工作。而今天本文要为大家推荐的这 8 款界面设计软件&#xff0c;分别是国产APP界面设计软件、Figma、Ske…

【数据库】Redis主从复制、哨兵模式、集群

目录 一、Redis的主从复制 1.1 主从复制的架构 1.2 主从复制的作用 1.3 注意事项 1.4 主从复制用到的命令 1.5 主从复制流程 1.6 主从复制实现 1.7 结束主从复制 1.8 主从复制优化配置 二、哨兵模式 2.1 哨兵模式原理 2.2 哨兵的三个定时任务 2.3 哨兵的结构 2.4 哨…

校园外卖系统带万字文档在线外卖管理系统java项目java课程设计java毕业设计

文章目录 校园外卖系统一、项目演示二、项目介绍三、万字项目文档四、部分功能截图五、部分代码展示六、底部获取项目源码带万字文档&#xff08;9.9&#xffe5;带走&#xff09; 校园外卖系统 一、项目演示 校园外卖服务系统 二、项目介绍 语言&#xff1a;java 数据库&…

ARM功耗管理标准接口之ACPI

安全之安全(security)博客目录导读 思考&#xff1a;功耗管理有哪些标准接口&#xff1f;ACPI&PSCI&SCMI&#xff1f; Advanced Configuration and Power Interface Power State Coordination Interface System Control and Management Interface ACPI可以被理解为一…

2023年高教杯数学建模2023B题解析(仅从代码角度出发)

前言 最近博主正在和队友准备九月的数学建模,在做往年的题目&#xff0c;博主主要是负责数据处理&#xff0c;运算以及可视化&#xff0c;这里分享一下自己部分的工作,相关题目以及下面所涉及的代码后续我会作为资源上传 问题求解 第一题 第一题的思路主要如下&#xff1a;…

单链表--续(C语言详细版)

2.6 在指定位置之前插入数据 // 在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); 分为两种情况&#xff1a;1. 插入的数据在链表中间&#xff1b;2. 插入的数据在链表的前面。 // 在指定位置之前插入数据 void SLTInsert(SLTNode** …

TISAX认证是什么?

TISAX认证是一种针对汽车行业数据安全和隐私保护的评估认证&#xff0c;其全称在不同资料中有所差异&#xff0c;但普遍认可的是它作为汽车行业信息安全评估体系的重要性。以下是对TISAX认证的详细解读&#xff1a; 一、背景和目的 随着汽车技术的不断发展&#xff0c;汽车数…

MySQL—统计函数和数学函数以及GROUP BY配合HAVING

合计/统计函数 count -- 演示 mysql 的统计函数的使用 -- 统计一个班级共有多少学生&#xff1f; SELECT COUNT(*) FROM student -- 统计数学成绩大于 90 的学生有多少个&#xff1f; SELECT COUNT(*) FROM student WHERE math > 90 -- 统计总分大于 250 的人数有多少&…