信息学奥赛初赛天天练-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