第十五届全国青少年信息学奥林匹克联赛初赛试题
（提高组C语言二小时完成）●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一．单项选择题（共10题，每题15分，共计15分。每题有且仅有一个正确答案。）1、关于图灵机下面的说法哪个是正确的：A图灵机是世界上最早的电子计算机。B由于大量使用磁带操作，图灵机运行速度很慢。C图灵机只是一个理论上的计算模型。D图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。2、关于BIOS下面的说法哪个是正确的：ABIOS是计算机基本输入输出系统软件的简称。BBIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。CBIOS一般由操作系统厂商来开发完成。DBIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。3、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII编码为：
fA48
B49
C50
D以上都不是
4、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1。其对应的十进制整数应该是：
A19
B19
C18
D18
5、一个包含
个分支结点（非叶结点）的非空满k叉树，k1，它的叶结点数目为：
A
k1
B
k1Ck1
1
Dk1
1
6表达式abcd的后缀表达式是：
AabcdBabcdCabcdDabcd
7、最优前缀编码，也称Huffma
编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。
A（00，01，10，11）
B（0，1，00，11）
C（0，10，110，111）
D（1，01，000，001）
8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：
A平均情况O
log2
，最坏情况O
2
fB平均情况O
，
最坏情况O
2
C平均情况O
，
最坏情况O
log2

D平均情况Olog2
，最坏情况O
2
9、左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为：AV0V1V2V3V5V4BV0V1V5V4V3V3CV1V2V3V0V5V4DV1V2V3V0V4V5
10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：
A
B
C
D
二．不定项选择题（共10题，每题15分，共计15分。每题正确答案的个数不少于1。多选或少选均不得分）。
1、关于CPU下面哪些说法是正确的：
ACPU全称为中央处理器（或中央处理单元）。
BCPU能直接运行机器语言。
fr