2013年山东省信息学奥赛夏令营提高一DAY2栈和队列上机练习题目

信息学奥赛刷题题库全文共四篇示例，供读者参考第一篇示例：信息学奥赛是一项旨在培养学生计算机科学和信息技术能力的比赛，也是检验学生解决问题和创新能力的平台。

随着信息技术的不断发展，信息学奥赛越来越受到广大学生和教育者的重视。

为了帮助学生更好地备战信息学奥赛，提高其解决问题的能力，我们整理了一份信息学奥赛刷题题库。

1. 算法题：算法是信息学奥赛的核心内容，涉及到各种数据结构和算法的运用。

学生可以通过解决算法题，提高自己设计和分析算法的能力。

经典的算法题目包括最短路径算法、最小生成树算法、动态规划等。

2. 编程题：信息学奥赛的编程题目要求学生使用编程语言解决问题，考察他们的编程能力和思维逻辑。

编程题通常涉及到数据处理、排序算法、字符串处理等内容。

学生可以通过编程题目锻炼自己的编程技能，提高解决实际问题的能力。

4. 数据处理题：信息学奥赛中的数据处理题目要求学生处理大量数据并给出正确的输出，考察他们的数据处理和分析能力。

数据处理题目可以帮助学生提高数据处理技能和对数据结构的熟练运用。

以上是信息学奥赛刷题题库的一部分内容，希望通过这些题目的练习，学生可以提高自己的算法能力、编程水平和数学思维能力，为参加信息学奥赛做好充分准备。

祝愿所有参加信息学奥赛的学生取得优异的成绩！第二篇示例：信息学奥赛是一个旨在培养学生动手能力和创造力的比赛，其题目设计围绕计算机科学和算法问题展开。

参加信息学奥赛刷题是提高自己编程水平和解决问题能力的有效途径。

在刷题过程中，能够锻炼自己的逻辑思维能力、编程实践能力以及计算机科学基础知识。

为了帮助有志于参加信息学奥赛的同学练习和提高编程能力，我们准备了一份信息学奥赛刷题题库，涵盖了各种难度和类型的题目。

以下将为大家介绍这份题库的内容及其优势：一、题库特点：1.题目全面：题库包含了信息学奥赛的常见题目及其变形题，涉及到了各个知识点和算法的应用，能够帮助学生全面了解信息学奥赛的考察内容。

2.题目难度适中：题库中的题目根据难度进行了分类，从简单到困难，适合不同水平的参赛者，既可以作为初学者的入门练习，也可以作为有经验者的挑战。

历年全国青少年信息学奥赛选择题一、单项选择题(共10题,每题1.5分,共计15分。

每题有且仅有一个正确答案)。

第14届:2008年1.在以下各项中,()不是操作系统软件。

A.SolarisB.LinuxC.SybaseD.Windows VistaE.SymbianC是数据库系统2.微型计算机中,控制器的基本功能是()。

A.控制机器的各个部件协调工作B.实现算数运算与逻辑运算C.存储各种控制信息D.获取外部信息E.存放程序和数据3.设字符串S=“Olympic”,S的非空子串的数目是()。

A.29B.28C.16D.17E.71个字符的子串(7个):"o" "l" "y" "m" "p" "i" "c",2个字符(6个):"ol" "ly" "ym" "mp" "pi" "ic" .……7个字符(1个):olympic所以:共有7+6+5+4+3+2+1=284.完全二叉树有2*N-1的结点,则它的叶子结点数目是()。

A.N-1B.2*NC.ND.2N-1E.N/2最多只能在最下层缺少结点,并且缺少的结点都在最右边,即最下层的结点都集中在该层最左边,则称此二叉树为完全二叉树。

5.将数组{8,23,4,16,77,-5,53,100}中元素从大到小按顺序排序,每次可以交换任意两个元素,最少要交换()次。

A.4B.5C.6D.7E.86.设栈S的初始状态为空,元素a,b,c,d,e,f依次入栈,出栈顺序为b,d,c,f,e,a 那么栈容量至少应该是()。

A.6B.5C.4D.3E.27.与十进制数28.5625相等的四进制数是()A.123.21B.131.22C.130.22D.130.21E.130.20整数部分就不用说了,是130小数部分,0.5625×4=2.250.25×4=11所以是0.218.递归过程和函数调用时,处理参数和返回地址,通常使用一种称为()的数据结构。

2014年山东省信息学奥赛夏令营基础二班测试题每题时限1S 内存128MB1、高精度求积(multiply.pas/c/cpp)【问题描述】输入两个高精度正整数M和N（M和N均小于100位）。

【输入样例】multiply.in33【输出样例】multiply.out92、员工的薪水(salary.pas/c/cpp)描述：小羊凭借自己灵活的大脑和自己的努力进入了一家大公司，年终评估时，老板给每一个员工规定了下一年的薪水，可是这是一家大公司，员工数成千上万，老板无法从中快速得知某个员工的薪水在公司内的水平。

于是就把这个艰苦的任务交给了聪明的小羊，要求小羊把员工的薪水从小到大排序，你能帮小羊解决这个问题吗？输入格式输入文件的第一行包括员工数(1<=n<=100000)，第二行包括N个整数，用空格分开，代表每个员工的薪水。

输出格式输出文件只有一行，包括N个整数，从小到大排序的员工薪水。

样例salary.in6100 10 500 500 200 50salary.out10 50 100 200 500 5003、采药(medic.pas/c/cpp)【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。

为此，他想拜附近最有威望的医师为师。

医师为了判断他的资质，给他出了一个难题。

医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。

我会给你一段时间，在这段时间里，你可以采到一些草药。

如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。

”如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件medic.in的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。

接下来的M 行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

山东信息学夏令营提高二测试竞赛时间：2014 年7 月21 日上午8:30-11:30Jason Hsiao提交源程序必须加后缀：注意：最终测试时，编译命令将开启-O2优化。

警告：程序内严禁以任何形式调用system函数。

旅行【问题描述】如果说旅行是令人愉悦的话，对于强迫症患者可不一定如此。

Alice最近得到了一张旅行地图，其中详细标明了A市内的N个景点，共有M 条双向路连接着N个景点。

由于Alice的精力有限，她实在无法将N个景点全部游遍，于是只好算了一个数字K，她只想详细游览前K个景点。

受到强迫症的困扰，Alice特别害怕会在某个环上重复走来走去而导致可怕的事情发生，所以她希望在地图上删去一些边，使得编号不大于K的所有景点都不在环上。

【输入格式】从文件tour.in中读入数据。

输入的第一行是三个整数N,M,K。

接下来M行，每行有两个整数u,v描述一条无向边。

【输出格式】输出到文件tour.out中。

输出唯一一行，一个整数，表示最少删去的边数。

【样例输入】11 13 51 21 31 53 52 84 117 116 106 92 38 95 99 10【样例输出】3【评分标准】对于每个测试点，你的输出必须和标准输出一致得到全部分数，否则不得分。

【数据规模及约定】对于20%的数据,N≤100,M≤300.对于40%的数据,N≤1,000,M≤ 5,000.对于100%的数据,N≤1,000,000,M≤2,000,000,1≤K≤N.数据保证不存在重边。

注意读入数据很大，请采取高效的读入方式。

必要时可以使用读入优化。

魔法序列【问题描述】Bob最近得到了一个序列，最初他以为这个序列只是一个普通的序列，结果正当他研究区间[l,r]内的元素时，Cindy不知说了一句什么话，结果区间[l,r]的元素竟然全部被开了平方。

Bob对这个现象十分感兴趣，但他并不打算深究为什么会出现这种现象，而打算玩一玩这个魔法序列。

NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛（提高组）试题解析一、单选题（15*1.5）1、A，一个字节有8个bit，32位整型变量占用4个字节，故选A。

2、A，二进制11.01转为十进制，（11.01）2 = 1*2+1+0*0.5+1*0.25 = （3.25）10 。

3、B,老和尚给小和尚讲的故事里边有故事本身，递归是函数内部调用函数本身，故选B，递归。

4、D，香农信息论鼻祖。

5、A，一定是满二叉树时拥有2个字节点的节点数最多，最下一层会有2013-1023=990个节点，于是倒数第二层会有990/2=495个节点有2个字节点，从第1层到倒数第三层共有1023-2^9=511个节点，且这些节点都是用2个子节点的节点，所以共有495+511=1006个，选A。

6、B，要使图不联通，只要其中某一个节点不连通即可，所有顶点度最少是3，所以最少需要删除3条边，选B。

7、D，此题最开始一眼扫到的时候脑子进水，跟学生将选B，O（n），实际上不是，计算F1需要1次，计算F2需要一次，计算Fn需要计算F(n-1)的次数加上F （n-2）的次数，所以其实就是计算Fn次，于是答案选择D，至于这个Fn到底是多大，数学上可以计算，它等于O((（1+sqrt(5)）/2)^n).8、B，这个必须是B，没有什么好说的，中序遍历保证左边都是小于根的，右边都是大于根的，所以可以保证是一个有序序列。

9、D，A项6和17对11取余都是6发生冲突，B项10的平方和17的平方对11取余都是1发生冲突，C项6的两倍和17的两倍对11取余都是1发生冲突，D项分别为1，2，3，4，不冲突。

10、D，IPV6地址是128位的。

谢谢网友指正！11、C，二分为6个和6个的顶点，此时边最多，有36条边。

12、B，我的学生几乎全选A去了，因为之前讲题只介绍过ASCII码，但是看到统一二字也应该想到Uni...前缀啊。

13、D，64位非零浮点数强制转换成32位浮点数，两个数会有大小上的细微差别，但不会发生符号变化，因为有专门的符号位。

栈和队列是信息学竞赛中经常涉及的数据结构，它们在算法和程序设计中有着广泛的应用。

掌握栈和队列的基本原理和操作方法，对于参加信息学竞赛的同学来说是非常重要的。

本文将深入探讨栈和队列的相关知识点，帮助大家更好地理解和掌握这两种数据结构。

一、栈的定义与特点栈是一种先进后出（LIFO）的数据结构，它的特点是只允许在栈顶进行插入和删除操作。

栈可以用数组或链表来实现，常见的操作包括压栈（push）、出栈（pop）、获取栈顶元素（top）等。

栈的应用非常广泛，比如在计算机程序中，函数的调用和返回值的存储就是通过栈来实现的。

二、栈的基本操作1. 压栈（push）：将元素压入栈顶2. 出栈（pop）：将栈顶元素弹出3. 获取栈顶元素（top）：返回栈顶元素的值，但不把它从栈中移除4. 判空：判断栈是否为空5. 获取栈的大小：返回栈中元素的个数三、栈的应用1. 括号匹配：利用栈来检查表达式中的括号是否匹配2. 表达式求值：利用栈来实现中缀表达式转换为后缀表达式，并进行求值3. 迷宫求解：利用栈来实现迷宫的路径搜索4. 回溯算法：在深度优先搜索和递归算法中，通常会用到栈来保存状态信息四、队列的定义与特点队列是一种先进先出（FIFO）的数据结构，它的特点是只允许在队尾进行插入操作，在队首进行删除操作。

队列同样可以用数组或链表来实现，常见的操作包括入队（enqueue）、出队（dequeue）、获取队首元素（front）、获取队尾元素（rear）等。

队列在计算机领域也有着广泛的应用，比如线程池、消息队列等都可以用队列来实现。

五、队列的基本操作1. 入队（enqueue）：将元素插入到队列的末尾2. 出队（dequeue）：从队列的头部删除一个元素3. 获取队首元素（front）：返回队列的头部元素的值4. 获取队尾元素（rear）：返回队列的尾部元素的值5. 判空：判断队列是否为空6. 获取队列的大小：返回队列中元素的个数六、队列的应用1. 广度优先搜索算法（BFS）：在图的搜索中，通常会用队列来实现BFS算法2. 线程池：利用队列来实现任务的调度3. 消息队列：在分布式系统中，常常会用队列来进行消息的传递4. 最近最少使用（LRU）缓存算法：利用队列实现LRU缓存淘汰在信息学竞赛中，栈和队列的相关题目经常出现，并且有一定的难度。

信息学奥赛选拔试题
信息学奥赛选拔试题一般会包括基础题、提高题和综合题。

以下是一些可能的信息学奥赛选拔试题：
基础题：
1. 什么是信息学？请简要解释。

2. 什么是算法？请简要解释。

3. 什么是数据结构？请简要解释。

4. 请解释以下信息学术语：数组、链表、栈、队列。

5. 请写出一个简单的计算器程序，可以执行加、减、乘、除四个基本运算。

提高题：
1. 请设计一个程序，实现将一个整数列表按照升序排序。

2. 请设计一个程序，实现将一个字符串列表按照字典序排序。

3. 请写出一个程序，可以判断一个数是否为素数。

4. 请设计一个程序，实现将一个字符串转换为整数。

5. 请设计一个程序，实现将两个有序整数列表合并为一个有序整数列表。

综合题：
1. 请设计一个程序，实现求解以下数学表达式：max(a, b, c) + min(a, b, c) + avg(a, b,
c)。

其中，a、b、c为整数，函数avg计算a、b、c的平均值。

2. 请写出一个程序，可以判断一个字符串是否为回文串。

3. 请设计一个程序，实现求解以下数学表达式：sqrt(a^2 + b^2) + log(c * d)。

其中，
a、b、c、d为实数，函数sqrt计算平方根，函数log计算自然对数。

第1~10题为基础题，第11~20题为提高题，第21~33为综合题注：因为在本文档中需要用到一些特殊的数学符号（如：求和号、分数等），所以当您在百度文库中浏览时，一些数学符号可能会显示不出来，不过当您把本文档下载下来在本地浏览时，所有的符号即可全部都显示出来。

^_^基础题：【1 Prime Frequency】【问题描述】给出一个仅包含字母和数字（0-9, A-Z 以及a-z）的字符串，请您计算频率（字符出现的次数），并仅报告哪些字符的频率是素数。

输入：输入的第一行给出一个整数T( 0<T<201)，表示测试用例个数。

后面的T行每行给出一个测试用例：一个字母-数字组成的字符串。

字符串的长度是小于2001的一个正整数。

输出：对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频率是素数的字符。

这些字符按字母升序排列。

所谓“字母升序”意谓按ASCII 值升序排列。

如果没有字符的频率是素数，输出“empty”（没有引号）。

注：试题来源：Bangladesh National Computer Programming Contest在线测试：UV A 10789提示先离线计算出[2‥2200]的素数筛u[]。

然后每输入一个测试串，以ASCLL码为下标统计各字符的频率p[]，并按照ASCLL码递增的顺序（0≤i≤299）输出频率为素数的字符（即u [p[i]]=1且ASCLL码值为i的字符）。

若没有频率为素数的字符，则输出失败信息。

【2 Twin Primes】【问题描述】双素数（Twin Primes）是形式为(p, p+2)，术语“双素数”由Paul Stäckel (1892-1919)给出，前几个双素数是(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)。

在本题中请你给出第S对双素数，其中S是输入中给出的整数。

2００9－20１3年NOIP初赛提高组C＋+语言试题2013第十九届全国青少年信息学奥林匹克联赛初赛提高组C++语言试题竞赛时间:20１3年１0月１3日14：30～16:30选手注意:试题纸共有12页，答题纸共有2页，满分100分。

请在答题纸上作答，写在试题纸上的一律无效。

不得使用任何电子设备（如计算器、手机、电子词典等)或查阅任何书籍资料。

一、单项选择题(共15题,每题1.５分,共计２2.5分;每题有且仅有一个正确选项）1．一个３2位整型变量占用（）个字节。

A.４ B.8 C.3２ D.１282．二进制数1１.０1在十进制下是(）。

A.3.２5 B.4.125 C．6.25 D.11.１253．下面的故事与（)算法有着异曲同工之妙。

从前有座山，山里有座庙,庙里有个老和尚在给小和尚讲故事:?从前有座山，山里有座庙,庙里有个老和尚在给小和尚讲故事:‘从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事.．．．’?Ａ.枚举 B．递归 C．贪心 D.分治４.１9４8年，()将热力学中的熵引入信息通信领域,标志着信息论研究的开端。

A.冯·诺伊曼(John von Neｕmaｎn）B.图灵(Ａlaｎ Tｕring)C.欧拉（Leonhaｒd Eｕleｒ)D.克劳德·香农(Clａude Shannｏn）5．已知一棵二叉树有201３个节点,则其中至多有(）个节点有２个子节点。

A．1006 B.１０07 C.1０23 Ｄ.10246.在一个无向图中,如果任意两点之间都存在路径相连，则称其为连通图。

右图是一个有5个顶点、８条边的连通图。

若要使它不再是连通图,至少要删去其中的（)条边。

A.2 Ｂ.3 Ｃ．4 Ｄ.57.斐波那契数列的定义如下:F１=1,F2=1,Fn＝Fｎ–１+Ｆn–２(ｎ≥3)。

如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为(）。

iｎt F(int n){if(n＜＝2)ｒeturn 1;elserｅtｕｒn F（n－１)+F(n-2)；｝)A.O(1) Ｂ.O（n) Ｃ．O(n2) D.O(Ｆｎ8．二叉查找树具有如下性质:每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。

2013年山东省信息学奥赛夏令营提高一树及其应用练习题目第一篇：2013年山东省信息学奥赛夏令营提高一树及其应用练习题目树及其应用上机练习题目1.FBI树(fbi)【问题描述】我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。

由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：（1）T的根结点为R，其类型与串S的类型相同；（2）若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R 的右子树T2。

现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。

【输入文件】输入文件fbi.in的第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2N的“01”串。

【输出文件】输出文件fbi.out包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。

【样例输入】10001011【样例输出】IBFBBBFIBFIIIFF【数据规模】对于40%的数据，N <= 2；对于全部的数据，N<= 10。

2.树的遍历(tree)【问题描述】我们都知道二叉树的后序遍历，即对于节点i，先访问它的左儿子，再访问它的右儿子，最后输出它本身。

我们对其稍加改动：对于节点i，先访问它的右儿子，再访问它的左儿子，最后输出它本身。

给你一棵有序的二叉树（亦即，每个节点的值严格大于它左子树的节点的值，严格小于它右子树的节点的值）的后序遍历，请你输出它的“右-左-中”遍历。

【输入】第一行是一个整数n，表示节点个数。

第二行有n个数，表示一个n个节点的有序的二叉树的后序遍历的数值。

【输出】输出文件仅包含一行，有n个整数，表示这个二叉树的“右-左-中”遍历。