下载文档原格式
信息学基础知识题库硬件1．微型计算机的问世是由于（C）的出现。
A. 中小规模集成电路B. 晶体管电路C. (超)大规模集成电路D. 电子管电路2．中央处理器（CPU）能访问的最大存储器容量取决于（A）。
A. 地址总线B. 数据总线C. 控制总线D. 实际内存容量3．微型计算机中，（C）的存储速度最快。
A. 高速缓存B. 外存储器C. 寄存器D. 内存储器4．在计算机硬件系统中，cache是（D）存储器。
A. 只读B. 可编程只读C. 可擦除可编程只读D. 高速缓冲5．若我们说一个微机的CPU是用的PII300，此处的300确切指的是（A）。
A. CPU的住时钟频率B. CPU产品的系列号C. 每秒执行300百万条指令D. 此种CPU允许的最大内存容量6．计算机主机是由CPU与（D）构成。
A. 控制器B. 输入输出设备C. 运算器D. 内存储器7．计算机系统总线上传送的信号有（B）。
A. 地址信号与控制信号B. 数据信号、控制信号与地址信号C. 控制信号与数据信号D. 数据信号与地址信号8．不同类型的存储器组成了多层次结构的存储器体系，按存储器速度又快到慢的排列是（C）。
A. 快存>辅存>主存B. 外存>主存>辅存C. 快存>主存>辅存D. 主存>辅存>外存9．微机内存储器的地址是按（C）编址的。
A. 二进制位B. 字长C. 字节D. 微处理器的型号10．在微机中，通用寄存器的位数是（D）。
A. 8位B. 16位C. 32位D. 计算机字长11．不同的计算机，其指令系统也不同，这主要取决于（C）。
A. 所用的操作系统B. 系统的总体结构C. 所用的CPUD. 所用的程序设计语言12．下列说法中，错误的是（BDE）A. 程序是指令的序列，它有三种结构：顺序、分支和循环B. 数据总线决定了中央处理器CPU所能访问的最大内存空间的大小C. 中央处理器CPU内部有寄存器组，用来存储数据D. 不同厂家生产的CPU所能处理的指令集是相同的E. 数据传输过程中可能会出错，奇偶校验法可以检测出数据中哪一位在传输中出了错误13．美籍匈牙利数学家冯·诺依曼对计算机科学发展所作出的贡献是（C）。
第20届中小学生计算机程序设计竞赛初赛试题学校姓名准考证号（说明：答案请写在答题卷上。
考试时间120分钟，满分120分）一、选择题(每小题2分，共40分)下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将正确选项写在答题卷相应位置上，答在试卷上不得分。
1、构成运算器需要多个部件，（）不是构成运算器的部件。
A、加法器B、累加器C、地址寄存器D、ALU(算术逻辑部件)2、在主存和CPU之间增加Cache的自的是（）。
A、增加内存容量B、为程序员编程提供方便C、解决CPU与内存间的速度匹配问题D、提高内存工作的可靠性3、操作系统功能不包括（）。
A、提供用户操作界面B、管理系统资源C、提供应用程序接口D、提供HTML4、系统软件是（）的软件。
A、向应用软件提供系统调用等服务B、与具体硬件逻辑功能无关C、在应用软件基础上开发D、并不具体提供人机界面5、关于计算机的使用和维护，下列叙述中错误的是（）。
A、计算机要经常使用，不要长期闲置不用B、在计算机附近应避免磁场干扰C、为了延长计算机的寿命，应避免频繁开关计算机D、为了省电，每次最好只打开一个程序窗口6、Windows“回收站”占用的是（）中的空间。
A、主存B、软盘C、光盘D、硬盘7、ASCII码是对（）实现编码的一种方法。
A、语音B、汉字C、图形图像D、字符8、程序设计语言的定义一般应包（）几个方面。
A、语法、语义和语句B、语法、语义和语用C、语义、语句和语用D、语法、语用和语句9、与十进制数254等值的二进制数是（）。
A、11111110B、11101111C、11111011D、1110111010、对于二维数组a[1..4，3..6]，设每个元素占两个存储单元，若以行为主序存储，则元素a[3，4]相对于数组空间起始地址的偏移量是（）。
A、12B、14C、16D、1811、在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的排序算法是（）。
第十七届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal语言两小时完成）●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分。
共计30分。
每题有且仅有一个正确选项。
）1．在二进制下，1100011 +（）= 1110000。
A．1011 B．1101 C．1010 D．11112．字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。
A．66 B．5A C．50 D．视具体的计算机而定3．右图是一棵二叉树，它的先序遍历是（）。
A．ABDEFC B．DBEFAC C．DFEBCA D．ABCDEF4．寄存器是（）的重要组成部分。
A．硬盘B．高速缓存C．内存D．中央处理器（CPU）5．广度优先搜索时，需要用到的数据结构是（）。
A．链表B．队列C．栈D．散列表6．在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）。
A．程序运行时理论上所占的内存空间B．程序运行时理论上所占的数组空间C．程序运行时理论上所占的硬盘空间D．程序源文件理论上所占的硬盘空间7．应用快速排序的分治思想，可以实现一个求第K大数的程序。
假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。
A．O(n2)B．O(n log n)C．O(n) D．O(1)8．为解决Web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。
A．微软 B．美国计算机协会（ACM） C．联台国教科文组织D．万维网联盟（W3C）9．体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。
每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。
这种站队的方法类似于（）算法。
A．快速排序B．插入排序C．冒泡排序D．归并排序10．1956年（）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain)，以表彰他们对半导体的研究和晶体管效应的发现。
广东省汕头市金山中学高一信息技术历年NOIP初赛试题12分区联赛初赛试题（高中组）竞赛用时： 2 小时一、基础题<1>．执行① C> DIR 命令后，屏幕上显示如下画面：FORMAT COM 12145SYS COM 4878PUC BAT 126XCOPY EXE 112164 File（s） 123456 bytes free接着又顺序执行了如下几条DOS命令：②C> DIR > DF.TXT③C> TYPE DF.TXT④C> DIR试问：执行命令③和④在屏幕上显示的结果是否与①相同？<2>．列举一个问题，使问题的解能对应相应的算法例如对算法X:=10;Y;=5;READ（M,N）;S:=X*M-Y*N;可列举出如下的问题：学生答题，答对一题可得10分，答错一题则要扣去 5 分，输入答对的题数（M）与答错的题数（N）,求最后得分（S）是多少？现有以下算法：K:=0;FOR I:=0 TO 10 DO K:=K +（50-I*5） DIV 2 + 1; 请列出一个相应的问题。
<3>.有标号为A、B、C D和1、2、3、4的8个球，每两个球装一盒，分装4盒。
标号为字母的球与标号为数字的球有着某种一一对应的关系（称为匹配）并已知如下条件：①匹配的两个球不能在一个盒子内；② 2 号匹配的球与 1 号球在一个盒子里；③ A 号和 2 号球在一个盒子里；④B匹配的球和C号球在一个盒子里；⑤3号匹配的球与A号匹配的球在一个盒子里；⑥4号是A或B号球的匹配球；⑦D号与1号或2号球匹配；请写出这四对球匹配的情况。
<4>.从入口（1）到出口（17）的可行路线图中，数字标号表示关卡：15 ) --------------- (16)——(17) 一13 )——(14 ) :9 )——(10 )——(11)⑹二、根据题目要求，补充完善以下伪代码程序： <1>.求出二个整形数组错位相加的最大面积。
第十五届全国青少年信息学奥林匹克联赛初赛试题（普及组 C语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一．单项选择题（共20题，每题分，共计30分。
每题有且仅有一个正确答案。
）1、关于图灵机下面的说法哪个是正确的：A)图灵机是世界上最早的电子计算机。
B)由于大量使用磁带操作，图灵机运行速度很慢。
C)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
D)图灵机只是一个理论上的计算模型。
2、关于计算机内存下面的说法哪个是正确的：A)随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。
B)1MB内存通常是指1024*1024字节大小的内存。
C)计算机内存严格说来包括主存（memor）、高速缓存（cache）和寄存器（regiter）三个部分。
D)一般内存中的数据即使在断电的情况下也能保留2个小时以上。
3、关于BIOS下面说法哪个是正确的：A)BIOS是计算机基本输入输出系统软件的简称。
B)BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。
C)BIOS一般由操作系统厂商来开发完成。
D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
4、关于C72 C175.175 C-1 C1 C ain{canf"%d%d",&a,&b;ain{int a[3],b[3];int i,,tmain{int n,an 50void getnetchar tr[]{int =trentr,i,,,temain{char a[man];int n;canf"% %d",a,&n;whien>0{getneta;n--;}ain{canf"%d",&n;for i=1;i#incudeint n,m,,an;int hah[5][5];void worint ,int ,int tot{int i,;if tot=={an;return;}do{whie hah[][]{;if ==m{;= ① ;}if ==nreturn;}for i=-1;i=0&&i=0&&=0&&i=0&&<m④ ;;if ==m{;=0;}if ==nreturn;}whie 1;}int main{canf"%d%d%d",&n,&m,&;an=0;memethah,0,ieofhah;⑤ ;rintf"%d\n",an;return 0;}。
NOIP2010初赛模拟试题（六）（普及 Pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效●●一．单项选择题（共20题,每题1.5分,共计30分。
每题有且仅有一个正确答案。
）1、.在所有由两个1和六个0组成的8位二进制整数（补码）中，最小的数是：（）A．-127B．-64 C．-128 D．-652、.在一棵二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序（）A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同3、下面有效的IP地址是：（）A．202.280.130.45 B．130.192.33.45C．192.256.130.45 D．280.192.33.4564、一台具有1024*768分辨率、可显示65 536种颜色的显示器，其显示适配器（显示卡）上显示存储器容量的配置为：（）A．512K B．1MB C．大于1.6MB，小于2MB D．2MB5、进行二分法查找，则线性表（）A．必须顺序方式存储B．必须以链接方式存储，且数据元素已按值排好序C．必须以链接方式存储D．必须以顺序方式存储，且数据元素已按值排好序6、机器语言是用（）编写的。
A．二进制码B．ASCII码C．十六进制码D．国标码7、一棵含有101个结点的完全二叉树存储在数组A[1..101]中,对1≤k≤101,若 A[k]是叶子结点,则k的最小值是：（）A．51 B．50 C．49 D．488、不同的计算机，其指令系统也不相同，这主要取决于（）A. 所用的操作系统B. 系统的总体结构C. 所用的CPUD. 所用的程序设计语言9、计算机主机是由CPU 与（）构成的。
A．控制器B。
输入、输出设备C．运算器D．内存储器10、计算机系统总线上传送的信号有（）。
A．地址信号与控制信号B．数据信号、控制信号与地址信号C．控制信号与数据信号D．数据信号与地址信号11、计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。
作者：钟野梓序今年Noip2010初赛刚结束，网上便铺天盖地地响起了“今年初赛好容易”“分数线一定很高，怎么办……”之类的声音。
确实，自2008年起，Noip初赛难度确有逐年下降的趋势，然而这并不是出题水平降低的缘故，相反，我认为这是中国计算机协会（下称CCF）对于N oip考核目的的审视和改变所导致的必然结果。
因此，我试图通过深入解析本届Noip初赛试囗题，来探寻这种变化下面深层的规律，从而令信息学竞赛选手能更好地备战往后数届的Noip初赛，让初赛不再成为一个问题。
由于条件所限，本文仅以Pascal语言的提高组试囗题作为对象进行分析，相对于普及组而言提高组试囗题一向具有较高的难度和较好的区分度，作为研究对象是个很好的选择；至于说语言的选择，仅是因为笔者个人选择原因。
一、概况本届题目在设置方面与往年相似，由选择题（普及组仅有单项选择题，提高组则有单项选择题与不定项选择题）、问题求解、阅读程序写结果及完善程序四大部分组成；但值得注意的是，今年提高组试囗题的分值设计与往年出现了较大的不同，除了选择题仍然是30分（15分单项+15分不定项），其余部分分值均发生了变化，其中问题求解由10分上升到15分，阅读程序由32分下降到28分，完善程序由28分下降到27分。
由于是第一年实行这种分值，目前暂时无法定言背后的含义，然而或许CCF在初赛更加重视选手的数学素质，而弱化了对于阅读程序能力的考察。
众所周知，阅读程序的能力并不能非常真实地反映选手的程序能力，并且纵观近几年的阅读程序题已没有了什么新意，这也可看做是一个“求新求变”的信号。
至于试囗题整体难度方面较上年有了明显下降，其中问题求解第一题可以看做是考察选手的语文水平，而阅读程序更是没有了以往的“死算”题（即给定若干常数，在程序中设置一系列运算过程，让选手进行阅读计算类型的题目），完善程序给定的源代码风格良好，第二题竟然还加上了注释，这不能不说就是一种降低难度的举动。
历年真题：2004年第十届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal 语言 二小时完成 ）●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●一、 单项选择题（共10题，每题1.5分，共计15分。
每题有且仅有一个正确答案.）。
1. 设全集I = {a, b, c, d, e, f, g}，集合A = {a, b, c}，B = {b, d, e}，C = {e, f,g}，那么集合)(~)(B C B A ⋂⋃-为（ ）。
A. {a, b, c, d}B. {a, b, d, e}C. {b, d, e}D. {b, c, d, e}E. {d, f, g} //注意顺序，没有难度了选a2. 由3个a ，5个b 和2个c 构成的所有字符串中，包含子串“abc ”的共有（ ）个。
A. 40320B. 39600C. 840D. 780E. 60//1abc,2a,4b,1c →8！/（2！*4！*1！*1！*1！）=840-2abc,3b,1a →6!/(2!*3!*1!)=60 选d3.某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。
已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。
假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（ ）。
A. 1, 2, 3, 4, 5B. 1, 2, 4, 5, 7C. 1, 3, 5, 4, 6D. 1, 3, 5, 6, 7E. 1, 3, 6, 5, 7//栈操作，显然是e4. 满二叉树的叶结点个数为N ，则它的结点总数为（ ）。
A. NB. 2 * NC. 2 * N – 1D. 2 * N + 1E. 2N– 1//需要知道满二叉树的概念，画图就可知道，选c5. 二叉树T ，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（ ）。
第十届全国青少年信息学奥林匹克联赛初赛试题（普及组 C 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一．选择一个正确答案代码（A/B/C/D/E）,填入每题的括号内 (每题1.5分, 共30分)1.美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献是（）。
A.提出理想计算机的数学模型，成为计算机科学的理论基础。
B.是世界上第一个编写计算机程序的人。
C.提出存储程序工作原理，并设计出第一台具有存储程序功能的计算机EDV AC。
D.采用集成电路作为计算机的主要功能部件。
E.指出计算机性能将以每两年翻一番的速度向前发展。
2.下列哪个不是CPU（中央处理单元）（）。
A. Intel ItaniumB. DDR SDRAMC. AMD Athlon64D. AMD OpteronE. IBM Power 53.下列网络上常用的名字缩写对应的中文解释错误的是（）。
A.WWW（World Wide Web）：万维网。
B.URL（Uniform Resource Locator）：统一资源定位器。
C.HTTP（Hypertext Transfer Protocol）：超文本传输协议。
D.FTP（File Transfer Protocol）：快速传输协议。
E.TCP（Transfer Control Protocol）：传输控制协议。
4.下面哪个部件对于个人桌面电脑的正常运行不是必需的（）。
A.CPUB. 图形卡（显卡）C. 光驱D. 主板E. 内存5.下列哪个软件属于操作系统软件（）。
A. Microsoft WordB. 金山词霸C. FoxmailD. WinRARE. Red Hat Linux6.下列哪个不是计算机的存储设备（）。
A. 文件管理器B. 内存C. 高速缓存D. 硬盘E. U盘7.下列说法中错误的是（）。
A.CPU的基本功能就是执行指令。
B.CPU访问内存的速度快于访问高速缓存的速度。
江苏省金湖中学08、09、10级信息学奥赛组NOIP2010初赛模拟练习(三)1、下面一段程序是用（）语言书写的。
int func1(int n){int i,sum=0;for(i=1;i<=n;i++)sum+=i*i;return sum;}A)FORTRAN B)PASCAL C)C D) PROLOG E)BASIC2、多媒体计算机是指()计算机。
A)专供家庭使用的B)装有CD-ROM的B)连接在网络上的高级D)具有处理文字、图形、声音、影像等信息的3、在WORD文档编辑中实现图文混合排版时,关于文本框的下列叙述正确的是()。
A)文本框中的图形没有办法和文档中输入文字叠加在一起,只能在文档的不同位置B)文本框中的图形不可以衬于文档中输入的文字的下方。
C)通过文本框,可以实现图形和文档中输入的文字的叠加,也可实现文字环绕。
D)将图形放入文本框后,文档中输入的文字不能环绕图形。
4、计算机软件保护法是用来保护软件()的。
A)编写权B)复制权C)使用权D)著作权5、64KB的存储器用十六进制表示，它的最大的地址码是()A)10000B)FFFF C)1FFFF D)EFFFF6、在外部设备中，绘图仪属于（）A.输入设备B.输出设备C.辅（外）存储器D.主（内）存储器7、某种计算机的内存容量是640K，这里的640K容量是指（）个字节A.640B.640*1000C.640*1024D.640*1024*10248、已知数组中A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。
试问：A（5，8）的起始地址为（）A.SA+141B.SA+180C.SA+222D.SA+2259、电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。
这些线段可分为两类；一类是两端的小鸟相同；另一类则是两端的小鸟不相同。
NOIP 2010 初赛试题（提高组 C++语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10题，每题1.5分，共计15分。
每题有且仅有一个正确选项。
）1．与16进制数A1.2等值的10进制数是（）。
A. 101.2B. 111.4C. 161.125D. 177.252．一个字节（byte）由（）个二进制位组成。
A. 8B. 16C. 32D. 以上都有可能3．以下逻辑表达式的值恒为真的是（）。
A. P∨(¬P∧Q)∨(¬P∧¬Q)B. Q∨(¬P∧Q)∨(P∧¬Q)C. P∨Q∨(P∧¬Q)∨(¬P∧Q)D. P∨¬Q∨(P∧¬Q)∨(¬P∧¬Q)4．Linux下可执行文件的默认扩展名为（）。
A. exeB. comC. dllD. 以上都不是5．如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（）也成立。
A. 100B. 144C. 164D. 1966．提出“存储程序”的计算机工作原理的是（）。
A. 克劳德·香农B. 戈登·摩尔C. 查尔斯·巴比奇D. 冯·诺依曼7．前缀表达式“+ 3 * 2 + 5 12”的值是（）。
A. 23B. 25C. 37D. 658．主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了（）。
A. 寄存器B. 高速缓存C. 闪存D. 外存9．完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。
假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的（）号位置。
A. 2kB. 2k+1C. k/2下取整D. (k+1)/2下取整10．以下竞赛活动中历史最悠久的是（）。
A. 全国青少年信息学奥林匹克联赛（NOIP）B. 全国青少年信息学奥林匹克竞赛（NOI）C. 国际信息学奥林匹克竞赛（IOI）D. 亚太地区信息学奥林匹克竞赛（APIO）二、不定项选择题（共10题，每题1.5分，共计15分。
每题有一个或多个正确选项。
多选或少选均不得分。
）1．元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。
如果第1个出栈的是R3，那么第5个出栈的可能是（）。
A. R1B. R2C. R4D. R52．Pascal语言、C语言和C++语言都属于（）。
A. 高级语言B. 自然语言C. 解释性语言D. 编译性语言3．原地排序是指在排序过程中（除了存储待排序元素以外的）辅助空间的大小与数据规模无关的排序算法。
以下属于原地排序的有（）。
A. 冒泡排序B. 插入排序C. 基数排序D. 选择排序4．在整数的补码表示法中，以下说法正确的是（）。
A. 只有负整数的编码最高位为1B. 在编码的位数确定后，所能表示的最小整数和最大整数的绝对值相同C. 整数0只有唯一的一个编码D. 两个用补码表示的数相加时，如果在最高位产生进位，则表示运算溢出5．一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（）。
A. 0B. 2C. 4D. 66．在下列HTML语句中，可以正确产生一个指向NOI官方网站的超链接的是（）。
A. <a url="">欢迎访问NOI网站</a>B. <a href="">欢迎访问NOI网站</a>C. <a></a>D. <a name="">欢迎访问NOI网站</a>7．关于拓扑排序，下面说法正确的是（）。
A. 所有连通的有向图都可以实现拓扑排序B. 对同一个图而言，拓扑排序的结果是唯一的C. 拓扑排序中入度为0的结点总会排在入度大于0的结点的前面D. 拓扑排序结果序列中的第一个结点一定是入度为0的点8．一个平面的法线是指与该平面垂直的直线。
过点(1,1,1)、(0,3,0)、(2,0,0)的平面的法线是（）。
A. 过点(1,1,1)、(2,3,3)的直线B. 过点(1,1,1)、(3,2,1)的直线C. 过点(0,3,0)、(-3,1,1)的直线D. 过点(2,0,0)、(5,2,1)的直线9．双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。
设p指向链表中的一个结点，它的左右结点均非空。
现要求删除结点p，则下面语句序列中正确的是（）。
A. p->rlink->llink = p->rlink;p->llink->rlink = p->llink; delete p;B. p->llink->rlink = p->rlink;p->rlink->llink = p->llink; delete p;C. p->rlink->llink = p->llink;p->rlink->llink->rlink = p->rlink; delete p;D. p->llink->rlink = p->rlink;p->llink->rlink->llink = p->llink; delete p;10．今年（2010年）发生的事件有（）。
A. 惠普实验室研究员Vinay Deolalikar自称证明了P≠NPB. 英特尔公司收购计算机安全软件公司迈克菲（McAfee）C. 苹果公司发布iPhone 4手机D. 微软公司发布Windows 7操作系统三、问题求解（共3题，每题5分，共计15分）1．LZW编码是一种自适应词典编码。
在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。
举例说明，考虑一个待编码的信息串："xyx yy yy xyx"。
初始词典只有3个条目，第一个为x，编码为1；第二个为y，编码为2；第三个为空格，编码为3；于是串"xyx"的编码为1-2-1（其中-为编码分隔符），加上后面的一个空格就是1-2-1-3。
但由于有了一个空格，我们就知道前面的"xyx"是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典里，编码为4，然后按照新的词典对后继信息进行编码，以此类推。
于是，最后得到编码：1-2-1-3-2-2-3-5-3-4。
我们可以看到，信息被压缩了。
压缩好的信息传递到接收方，接收方也只要根据基础词典就可以完成对该序列的完全恢复。
解码过程是编码过程的逆操作。
现在已知初始词典的3个条目如上述，接收端收到的编码信息为2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，则解码后的信息串是"_________"。
2．无向图G有7个顶点，若不存在由奇数条边构成的简单回路，则它至多有_________条边。
3．记T为一队列，初始时为空，现有n个总和不超过32的正整数依次入队。
如果无论这些数具体为何值，都能找到一种出队的方式，使得存在某个时刻队列T中的数之和恰好为9，那么n的最小值是_________。
四、阅读程序写结果（共4题，每题7分，共计28分）1．#include <iostream>using namespace std;int main() {const int SIZE = 10;int data[SIZE], i, j, cnt, n, m;cin>>n>>m;for(i = 1; i <= n; i++)cin>>data[i];for(i = 1; i <= n; i++) {cnt = 0;for(j = 1; j <= n; j++)if ((data[i] < data[j]) || (data[j] == data[i] && j < i))cnt++;if(cnt == m)cout<<data[i]<<endl;}return 0;}输入5 296 -8 0 16 87输出：_________2．#include <iostream>using namespace std;int main(){const int SIZE = 100;int na, nb, a[SIZE], b[SIZE], i, j, k;cin>>na;for (i = 1; i <= na; i++)cin>>a[i];cin>>nb;for (i = 1; i <= nb; i++)cin>>b[i];i = 1;j = 1;while ((i <= na) && (j <= nb)) {if (a[i] <= b[j]) {cout<<a[i]<<' ';i++;}else {cout<<b[j]<<' ';j++;}}if (i <= na)for (k = i; k <= na; k++)cout<<a[k]<<' ';if (j <= nb)for (k = j; k <= nb; k++) cout<<b[k]<<' ';return 0;}输入：51 3 5 7 942 6 10 14输出：_________3．#include <iostream>using namespace std;const int NUM = 5;int r(int n){int i;if (n <= NUM)return n;for (i = 1; i <= NUM; i++)if (r(n - i) < 0)return i;return -1;}int main(){int n;cin>>n;cout<<r(n)<<endl;return 0;}输入：16输出：_________4．#include <iostream>using namespace std;const int SIZE = 100;int n, m, r[SIZE];bool map[SIZE][SIZE], found;bool successful(){int i;for (i = 1; i <= n; i++)if (! map[r[i]][r[i % n + 1]]) return false;return true;}void swap(int *a, int *b){int t;t = *a;*a = *b;*b = t;}void perm(int left, int right){int i;if (found)return;if (left > right) {if (successful()) {for (i = 1; i <= n; i++) cout<<r[i]<<' ';found = true;}return;}for(i = left; i <= right; i++) { swap(r + left, r + i);perm(left + 1, right);swap(r + left, r + i);}}int main(){int x, y, i;cin>>n>>m;memset(map, false, sizeof(map)); for (i = 1; i <= m; i++) {cin>>x>>y;map[x][y] = true;map[y][x] = true;}for (i = 1; i <= n; i++)r[i] = i;found = false;perm(1, n);if (! found)cout<<"No solution!"<<endl; return 0;}输入：9 121 22 34 55 66 11 72 73 84 85 96 9输出：_________五、完善程序（第1空2分，其余10空，每空2.5分，共计27分）1．（过河问题）在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。
