历届奥赛试题解析-初赛讲解(10)

省淳中信息学奥赛辅导 奥赛试题解析

（4）入栈操作（数列Q右移操作）：

①当direction= true即数列Q没有翻转时head、tail右移下一位head= head mod c+1、tail= tail mod c+1；

②当direction= false即数列Q翻转时head、tail右移下一位head=((head+c-2) mod c)+1、tail= (( tail +c-2) mod c)+1 （5）出栈操作（数列Q左移操作）：

（6）对列Q空的判断：head = tail；数列Q已满的判断：head的下一位= tail （7）入栈出栈流程：

46

省淳中信息学奥赛辅导 奥赛试题解析

【2.状态描述】

1. 数组s模拟一个栈，n为栈的元素个数

2. 数组q模拟一个循环队列，tail为队尾的下标，head为队头的下标，

（1）数据入栈先放入队列Q的Q[head]中，数的数量小于壳厚度C时是放在队列Q中。 （2）入栈数据数量超过壳厚度C时将队列Q中的Q[tail]移出放入栈S中。 （3）出栈在队列Q的Q[head]中

（4）direction：表示队列q有没有翻转； empty是否空 【3.算法设计】

1.初始状态：栈和队列Q初始化 n := 0; //栈S中元素数量

tail指向队列Q存放最老的数据，head指向队列Q存放最新的数据 empty := true; //初始队列q中没有任何数 direction := true; //初始队列q没翻转 2. 入栈，入栈数据位element procedure push; begin

1．如果队列Q满时先要要将队列Q中尾部数据入栈S，未满直接进入第2步 （1）栈S数据数量加1：inc(n);

（2）队列Q的尾部数据入栈：s[n]:=q[tail]; ; （3）调整队列Q的尾指针 tail := next(tail); 2. 入栈数据先放入队列Q的头部

（2）如果Q不空，说明q[head]有数据，head移至下一个：head := next(head); end;

依次入栈ABCD后队列Q状态

（1）如果队列Q为空，说明q[head]尚未数据，直接放入q[head]:= element;

再输入E后的状态,Tail处移入数组 S,

47

省淳中信息学奥赛辅导 奥赛试题解析

3. 出栈：操作在队列Q头部进行 procedure pop; //出栈 begin

1.如果队列Q中有数据

（1）输出head下标数据: writeln( q[head]);

（2）新的头部已经不在head处，要调整到head的上一位置：head := previous(head); 2. 如果栈数组S中有数据要移一个到队列Q尾部，

（1）队列Q的尾部已不在Tail处，要调整到它的上一位置：tail := previous(tail); （2）将数组S中移一个到Q的尾部：q[tail]:= s[n]; end; 上例输出E

4.队列操作（没有反向）

1. 下标k的下一位置：next:=k mod c+1

2. 下标k的上一位置：previous := ((k+c-2) mod c) + 1; 3. 队列满：next(head) = tail 4. 队列空：tail = head

48

省淳中信息学奥赛辅导 奥赛试题解析

17. 十七届（2011）试题

17.1 十七届普及组

一、单项选择题（共 20 题，每题 1.5 分，共计 30 分。每题有且仅有一个正确选项。） 1．在二进制下，1101001 + （ B ） = 1110110。 A、1011

B、1101

C、1010

D、1111

2．字符“0”的 ASCII 码为 48，则字符“9”的 ASCII 码为（ B ）。 A、39 B、57 C、120 D、视具体的计算机而定

3．一片容量为 8GB 的 SD 卡能存储大约（ C ）张大小为 2MB 的数码照片。 A、1600 B、2000 C、4000 D、16000

4．摩尔定律（Moore's law）是由英特尔创始人之一戈登?摩尔（Gordon Moore）提出来的。根据摩尔定律，在过去几十年以及在可预测的未来几年，单块集成电路的集成度大约每（ C ）个月翻一番。

A、1 B、6 C、18 D、36

5．无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图 G 有 7 个顶点，则它共有（ B ）条边。

A、7 B、21 C、42 D、49 6．寄存器是（ D ）的重要组成部分。

A、硬盘 B、高速缓存 C、内存 D、中央处理器（CPU）

7．如果根结点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度最少是（ C ）。

A、10 B、11 C、12 D、13 【分析】深度i的最多叶子2i-1 =2011,的i=12

8．体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ B ）算法。

A、快速排序 B、插入排序 C、冒泡排序 D、归并排序

【分析】(1)选择排序基本思想是：对一数组a[1..n]，对某一位置i选择一个数放入其中 (2) 插入排序基本思想是: 对一数组a[1..n]，a[1]——a[i-1]已经有序，对某一数a[i]，在1—i之间确定位置k插入

9. 一个正整数在二进制下有 100 位，则它在十六进制下有（ C ）位。

A、7 B、13 C、25 D、不能确定

10. 有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是（ C ）。

A、正确的，将文件放入回收站意味着彻底删除、无法恢复

B、不正确的，只有将回收站清空后，才意味着彻底删除、无法恢复

C、不正确的，即使将回收站清空，文件只是被标记为删除，仍可能通过恢复软件找回 D、不正确的，只要在硬盘上出现过的文件，永远不可能被彻底删除

49

省淳中信息学奥赛辅导 奥赛试题解析

11.广度优先搜索时，需要用到的数据结构是（ B ）。

A、链表 B、队列 C、栈 D、散列表 【分析】下图访问顺序：①②③④⑥⑦⑤

12.在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ A ）。

A、程序运行时理论上所占的内存空间 B、程序运行时理论上所占的数组空间 C、程序运行时理论上所占的硬盘空间 D、程序源文件理论上所占的硬盘空间

13. 在含有 n 个元素的双向链表中查询是否存在关键字为 k 的元素，最坏情况下运行的时间复杂度是（ C ）。

A、O(1) B、O(log n) C、O(n) D、O(n log n) 【分析】最坏情况是最后才找到k，共查找n次。

14.生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下不属于生物特征识别技术及其应用的是（ C ）。

15.现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由 4 个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为 700、600、300、 200。那么，“也”字的编码长度是（ C ）。

A、1 B、2 C、3 D、4 【分析】

50