首页 > 其他分享 >信息学奥赛初赛天天练-85-NOIP2014普及组-基础题4-链表、随机存取、顺序存取、二分查找、二分比较、循环结构、图领奖

信息学奥赛初赛天天练-85-NOIP2014普及组-基础题4-链表、随机存取、顺序存取、二分查找、二分比较、循环结构、图领奖

时间:2024-09-07 17:24:29浏览次数:9  
标签:二分 初赛 链表 查找 格式 存取 节点

信息学奥赛初赛天天练-85-NOIP2014普及组-基础题4-链表、随机存取、顺序存取、二分查找、二分比较、循环结构、图领奖
PDF文档公众号回复关键字:20240907

1 NOIP 2014 普及组 基础题4

9 下列选项中不属于图像格式的是( )
A JPEG 格式
B TXT 格式
C GIF 格式
D PNG 格式

10 链表不具有的特点是( )

A 不必事先估计存储空间
B 可随机访问任一元素
C 插入删除不需要移动元素
D 所需空间与线性表长度成正比

18 设有 100 个数据元素,采用折半搜索时,最大比较次数为( )

A 6
B 7
C 8
D 10

19 若有如下程序段,其中 s,a,b,c均已定义为整型变量,且 a,c均已赋值,c>0。

s = a;   
for(b = 1; b <= c; b++)   s += 1;   

则与上述程序段功能等价的赋值语句是( )

A s = a + b
B s = a + c
C s = s + c
D s = b + c

20 计算机界的最高奖是( )
A 菲尔兹奖
B 诺贝尔奖
C 图灵奖
D 普利策奖

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) 二分查找

二分查找也叫二分搜索 (binary search),也叫折半查找 (half-interval search),是一种在有序数组中查找特定元素的搜索算法。

所以用二分查找的前提是数组必须是有序的,可以升序也可以降序

二分查找实现思路

以升序举例

即选择序列中间的数字和目标值进行比较

如果中间的数字小于目标值,说明包括中间数字在内的左半边区间的所有数字都小于目标值,可以全部排除。

如果中间的数字大于目标值,说明包括中间数字在内的右半边区间的所有数字都大于目标值,可以全部排除。

如果中间的数字等于目标值,则直接返回答案。

根据二分思想

2个数需要二分1

4个数需要二分2

8个数需要二分3

比较次数最多为3次,如果一个数n>5 且n<=8,需要比较3次,即log8=3

所以100个数比较,需要比较次数为:

⌈log100⌉=7 对log100向上取整

3 思路分析

9 下列选项中不属于图像格式的是( B )
A JPEG 格式
B TXT 格式
C GIF 格式
D PNG 格式

分析

A JPEG 格式 - 这是一种广泛使用的图像文件格式,JPEG 文件通常具有较好的压缩比,同时能保持图像质量。
B TXT 格式 - 这并非一种图像格式,而是纯文本文件的格式,不包含任何图像数据或格式信息。
C GIF 格式 - GIF(Graphics Interchange Format)也是一种常见的图像文件格式,支持动画和透明背景。
D PNG 格式 - PNG(Portable Network Graphics)是一种无损压缩的位图图像格式,支持透明背景和高色彩深度
所以选B

10 链表不具有的特点是( B )

A 不必事先估计存储空间
B 可随机访问任一元素
C 插入删除不需要移动元素
D 所需空间与线性表长度成正比

分析

链表插入和删除只需要变更指针,不需要移动元素
链表按节点指针链接,不需要像数组提前预估内存空间,占用空间随着节点增加长度相应正比例增加
链表只能顺序访问,不能随机访问

18 设有 100 个数据元素,采用折半搜索时,最大比较次数为( B )

A 6
B 7
C 8
D 10

分析

最近比较次数为
⌈log100⌉=7 对log100向上取整
所以选B

19 若有如下程序段,其中 s,a,b,c均已定义为整型变量,且 a,c均已赋值,c>0。

s = a;   
for(b = 1; b <= c; b++)   s += 1;   

则与上述程序段功能等价的赋值语句是( B )

A s = a + b
B s = a + c
C s = s + c
D s = b + c

分析

s=a ,s一开始赋值为a
如下循环从1开始一直累加到c,每次s加1
for (b = 1;b <= c; b++ )
	s = s + 1;
循环结束总共加了c次1,所以s累加了c
所以s=a+c

20 计算机界的最高奖是( C )
A 菲尔兹奖
B 诺贝尔奖
C 图灵奖
D 普利策奖

分析

菲尔兹奖,数学
菲尔兹奖(Fields Medal),又译为菲尔茨奖,是依加拿大数学家约翰·查尔斯·菲尔兹(John Charles Fields)要求设立的国际性数学奖项,于1936年首次颁发。菲尔兹奖是数学领域的国际最高奖项之一
诺贝尔奖,物理、化学,医学等
诺贝尔奖是根据瑞典化学家阿尔弗雷德·诺贝尔的遗嘱于1901年设立并开始每年颁发的奖项,旨在表彰在物理学、化学、和平、生理学或医学、文学、经济学领域“对人类作出最大贡献”的科学家
图灵奖,计算机领域奖项
图灵奖是由美国计算机协会(ACM)颁发的年度奖项,旨在表彰在计算机科学领域具有持久和重大技术重要性贡献的个人。该奖项以英国数学家、逻辑学家艾伦·图灵的名字命名,他是计算机科学和人工智能的先驱,被誉为“计算机之父”
普利策奖,是新闻界奖
普利策奖,正式名称为普利策新闻奖,是根据美国报业巨头约瑟夫·普利策的遗愿于1917年设立的奖项,被誉为“新闻界的诺贝尔奖”。普利策奖是美国新闻界的一项最高荣誉奖,其影响力历久不衰
所以选C

标签:二分,初赛,链表,查找,格式,存取,节点
From: https://www.cnblogs.com/myeln/p/18401930

相关文章

  • 算法-二分查找
    二分查找是在一个有序的数组中查找目标值target,需要将target和数组中间元素做比较:1)如果target=mid,查找成功,返回mid的下标。2)如果target>mid,目标在数组右半部分,low=mid+13)target<mid,目标在数组左半部分,high=mid-1如下数组:1、首先,指定数组的左指针和右指针,根据公式mid......
  • Java-单向链表实现
    什么是链表?        链表是一种常见的数据结构,用于存储一系列元素。与数组不同,链表中的元素(节点)在内存中不必是连续的。每个节点包含数据部分和指向下一个节点的引用(指针)。链表的主要优点是插入和删除操作的时间复杂度为O(1),但访问特定元素的时间复杂度为O(n)。头节点......
  • 内核链表
    一、特性内核链表:双向循环有头链表组成:将链表的结点作为结构体成员存在,只放指向前驱结点和后继结点的指针offsetof获取结构体中的成员到结构体开头中的偏移量container_of通过偏移量获取结构体首地址但应用层不能使用上述两个宏,处理方法:将节点作为结构体第一个成员(结构......
  • 信息学奥赛初赛天天练-84-NOIP2014普及组-基础题3-总线、存储器、邮件协议、二叉树、
    信息学奥赛初赛天天练-84-NOIP2014普及组-基础题3-总线、存储器、邮件协议、二叉树、满二叉树、顶点的度、无向图、有向图PDF文档公众号回复关键字:202409061NOIP2014普及组基础题36CPU、存储器、I/O设备是通过()连接起来的A接口B总线C控制线D系统文......
  • 搜索算法之二分搜索详细解读(附带Java代码解读)
    1.基本概念二分搜索(BinarySearch)是一种高效的查找算法,用于在一个已排序的数组中查找特定元素。它通过逐步将搜索范围减少一半来实现搜索,从而比线性搜索更快。由于它利用了数组的有序性,能够在对数时间内完成搜索操作。2.工作原理二分搜索的基本思想是:初始化:设置两个指针......
  • LeetCode Hot100刷题记录-21. 合并两个有序链表
    题目描述:将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。需要知道的pre-knowledge:list1和list2起初可直接代表两个链表的头节点,无需用另外的变量比如current来表示头节点。思路:准备一个虚拟节点,指向合并完成新链表的h......
  • LeetCode Hot100刷题记录-206. 反转链表
    206.反转链表题目描述:给你单链表的头节点head,请你反转链表,并返回反转后的链表。这道题要用到两个指针,一个current指向当前节点,另一个prev指向当前节点的上一个节点。首先让current指向头节点head,prev指向head的前一个也就是null,这里要用next变量来暂时存储current的下一个......
  • 1.3二分算法
    算法理解二分用于解决答案具有单调性问题(经典最大值最小问题),是一个好的入手点,用一个log的复杂度,将求解答案转化成了判断答案是否合法实数域上的二分两种方法:确定精度eps,固定枚举次数,一般后者精度大于前者T1:二分最大值,注:如果有一个数本身就大于二分答案,则答案肯定错误,证明:考虑......
  • 链表算法题(下)
    在链表算法题(上)长中我们已经学习了一系列的链表算法题,那么在本篇中我们将继续来学习链表的算法题,接下来就继续来破解链表的算法题吧!1.相交链表160.相交链表-力扣(LeetCode)通过以上的题目的描述该算法题要我们实现的代码功能是判断两条链表是否相交,如果相较的话就返......
  • DP优化——wqs二分
    在看wqs二分前建议先去看另一篇博客——斜率优化,对凸包等知识点有所了解。介绍wqs二分最初由王钦石在他的2012年国家集训队论文中提出,也叫"带权二分",或者"dp凸优化",而从IOI2016的Aliens题目开始,这种方法开始逐步在竞赛圈中有了一定的地位。在国内我们一般称为「wqs二......