第十五届全国青少年信息学奥林匹克联赛初赛试题(pascal语言 提高.pdf

第十五届全国青少年信息学奥林匹克联赛初赛试题

（提高组Pascal语言二小时完成）

●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●

一．单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确答案。）

1、关于图灵机下面的说法哪个是正确的：

A)图灵机是世界上最早的电子计算机。

B)由于大量使用磁带操作，图灵机运行速度很慢。

C)图灵机只是一个理论上的计算模型。

D)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

2、关于BIOS下面的说法哪个是正确的：

A)BIOS是计算机基本输入输出系统软件的简称。

B)BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。

C)BIOS一般由操作系统厂商来开发完成。

D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

3、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII编码为：

A)48B)49C)50D)以上都不是

4、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。

其对应的十进制整数应该是：

A)19B)-19C)18D)-18

5、一个包含n个分支结点（非叶结点）的非空满k叉树，k=1，它的叶结点数目为：

A)nk+1B)nk-1C)(k+1)n-1D.(k-1)n+1

6.表达式a*(b+c)-d的后缀表达式是：

A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd

7、最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与

较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。

A)（00，01，10，11）

B)（0，1，00，11）

C)（0，10，110，111）

D)（1，01，000，001）

8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：

2

A)平均情况O(nlogn)，最坏情况O(n)

2

2

B)平均情况O(n)，最坏情况O(n)

C)平均情况O(n)，最坏情况O(nlogn)

2

NOIP2009初赛

提高组Pascal1

2

D)平均情况O(logn)，最坏情况O(n)

2

9、左图给出了一个加权无向图，从

顶点V开始用prim算法求最小生成

0

树。则依次加入最小生成树的顶点

集合的顶点序列为：

A)V0,V1,V2,V3,V5,V4

B)V0,V1,V5,V4,V3,V3

C)V1,V2,V3,V0,V5,V4

D)V1,V2,V3,V0,V4,V5

10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资

源，请问全国信息学奥林匹克官方网站的网址是：

A)B)

C)D)

二．不定项选择题（共10题，每题1.5分，共计15分。每题正确答案的个数不少于1。

多选或少选均不得分）。

1、关于CPU下面哪些说法是正确的：

A