下载文档原格式
![复赛noip2010提高组题解[新版]](https://img.taocdn.com/s1/m/7b1ee1c3b8f3f90f76c66137ee06eff9aef84965.png)
1.translate（20分）简单模拟。
开一个1000的队列，时刻保持队列长度不大于M，每次接受翻译请求时，先在队列中查找，查找失败则将单词加入队列。
查找使用Hash则为O(N)，直接扫描O(MN)，都在可接受范围内。
考试时只打了20分，原因至今不明，告诫大家对于水题不要多想，就像这道题最好不开hash，因为一个系统的可靠度是该系统所有子系统可靠度之积，程序越复杂越可能出错。
4.tortoise（50分）基础动规。
可以从题目背景中抽象出这样的问题：有一四维立方体（这里的立方体棱长不必相等，每一维对应一种卡片，每维的棱长对应该种卡片个数），每走一格（即使用一张卡片）的收益是当前位置坐标的函数。
求从(0,0,0,0)走到(a1,a2,a3,a4)最大收益。
故有方程f[x,y,z,t]=max{f[x-1,y,z,t], f[x,y-1,z,t], f[x,y,z-1,t], f[x,y,z,t-1]} + w[1 + x + y*2 + z*3 + t*4]目标状态： f[a1,a2,a3,a4]O(b^4)的代价，数据保证b<=40,完全满足要求5.prison（70分）问题可以重新描述为：寻找最小的冲突值c，使得存在一种方案，将原图分为两部分，并去掉这两部分之间的所有边后，余下的边权都不大于c。
对于这个问题我们可以二分查找c，并判定其可行性。
判定可行性的方法至今没想好。
考试的时候我是用并查集，将所有与u相连并与u之间边权大于c的点（设为点集Zu）必然不与u在同一集合中，枚举所有的u，每次将Zu合并成为一个集合，若存在某点u和Zu某个点处于同一个集合中，则c不可行，反之则可行。
但这种方法貌似存在bug，能拿70分。
如果把并查集合并查找的时间代价看作常数，则这种做法的时间代价为O(elogK),e是边数，K为最大的冲突值。
6.flow（100分）先用floodfill预处理出上方的每个格子能覆盖到下方的格子，构造一个布尔矩阵，行下标表示最上方的某个点，列下标表示最下方的某个点，矩阵对应点的值表示相应两个点的覆盖关系。
第十六届全国青少年信息学奥林匹克联赛初赛试题（ 提高组 C++ 语言 两小时完成 ）• • 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ••、单项选择题 （共 10 题，每题 1.5 分，共计 15 分。
每题有且仅有一个正确选项。
）1．与十六进制数 A1.2 等值的十进制数是（ )A ． 101.2B ． 111.4C ． 161.125D ． 177.25&主存储器的存取速度比中央处理器 （CPU ）的工作速度慢的多，从而使得后者的效率受到影响。
而根据局部性原理，CPU 所访问的存储单元通常都趋于一个较小的连续区域中。
于是，为了提高系统 整体的执行效率，在 CPU 中引入了（ ）。
A ．寄存器B ．高速缓存C ．闪存D ．外存9．完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序 结构的数组中。
假定根结点存放在数组的 1 号位置上，则第 k 号结点的父结点如果存在的话，应当 存放在数组中的（ ）号位置。
A ．2kB ．2k+1C ．k/2 下取整D ．（k+1）/22．一个字节（ byte ）由（ ）个二进制组成。
A ．8B ．16上都有可能3．以下逻辑表达式的值恒为真的是（ ）。
A . P V （n P A Q ）V （n P 心 Q ）BC . P V Q V （ P A n Q ）V （n P A Q ）D 4 ． Linux 下可执行文件的默认扩展名是 （ ） 。
A.exe B. com都不是C ．32 D .以Q V( n P A Q )V (P A n Q )P V n Q V( P A n Q V (n P A n Q)C. dllD.以上5 ．如果在某个进制下等式 7*7=41 成立，那么在该进制下等式 12*12= （ A. 100B. 144C. 164 ）也成立。
D. 1966 ．提出“存储程序”的计算机工作原理的是（A. 克劳德 ?香农B. 戈登?摩尔）。
NOIP提高组初赛历年试题及答案选择题篇单项选择题（共10-15题，每题1.5分，共计15-22.5分。
每题有且仅有一个正确选项。
）注：答案在末尾NOIP2011-1.在二进制下，1011001+（）=1100110。
同普及组NOIP2011-1 A.1011 B.1101 C.1010 D.1111NOIP2011-2.字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。
A.66B.5AC.50D.视具体的计算机而定NOIP2011-3.下图是一棵二叉树，它的先序遍历是（）。
A.ABDEFCB.DBEFACC.DFEBCAD.ABCDEFNOIP2011-4.寄存器是（）的重要组成部分。
同普及组NOIP2011-6A.硬盘B.高速缓存C.内存D.中央处理器（CPU）NOIP2011-5.广度优先搜索时，需要用到的数据结构是（）。
同普及组NOIP2011-11A.链表B.队列C.栈D.散列表NOIP2011-6.在使用高级语言编写程序时，一般提到的“空间复杂度”中的空间是指（）。
同普及组NOIP2011-12A.程序运行时理论上所占的内存空间B.程序运行时理论上所占的数组空间C.程序运行时理论上所占的硬盘空间D.程序源文件理论上所占的硬盘空间NOIP2011-7.应用快速排序的分治思想，可以实现一个求第K大数的程序。
假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。
A.O(n2) B.O(n log n) C.O(n) D.O(1)NOIP2011-8.为解决web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。
A.微软B.美国计算机协会（ACM）C.联合国教科文组织D.万维网联盟（W3C）NOIP2011-9.体育课的铃声响了，同学们都陆续的奔向操场，按老师的要求从高到低站成一排。
2009 第十五届全国青少年信息学奥林匹克联赛初赛试题提高组 C++ 语言 二小时完成 ）全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效． 单项选择题 （共 10 题，每题分，共计 15 分。
每题有且仅有一个正确答 案。
）1、关于图灵机下面的说法哪个是正确的：图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作 用。
2、关于BIOS 下面的说法哪个是正确的:BIOS 里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的 驱动程序。
BIOS 能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
3、已知大写字母A 的ASCII 编码为65（十进制），则大写字母J 的 十六进制ASCII 编码为:4、在字长为 16位的系统环境下，一个 16位带符号整数的二进制补码为 101。
其对应的十进制整数应该是:n 个分支结点（非叶结点）的非空满 k 叉树，k>=1，它的叶结点数 B) nk-1 C) (k+1)n-1 D. (k-1)n+16. 表达式 a*（b+c ）-d 的后缀表达式是:A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd7、最优前缀编码，也称 Huffman 编码。
这种编码组合的特点是对于较频繁使用 的元素给与较短的唯一编码，以提高通讯的效率。
下面编码组合哪一组不是 合法的前缀编码。
A ）（00， 01， 10， 11）A) 图灵机是世界上最早的电子计算机。
B) 由于大量使用磁带操作，图灵机运行速度很慢。
C) 图灵机只是一个理论上的计算模型。
D) A) BIOS 是计算机基本输入输出系统软件的简称。
B) C) BIOS 一般由操作系统厂商来开发完成。
D) A) 48 B) 49 C) 50 D)以上都不是 A) 19 B) -19 C) 18 D) -185、一个包含目为:A) nk + 1B ） （0，1，00，11）C ）（0，10，110，111）D ）（1，01，000，001）8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：9、右图给出了一个加权无向图， 从顶点 V 0 开始用 prim 算法求最 小生成树。
作者：钟野梓序今年Noip2010初赛刚结束，网上便铺天盖地地响起了“今年初赛好容易”“分数线一定很高，怎么办……”之类的声音。
确实，自2008年起，Noip初赛难度确有逐年下降的趋势，然而这并不是出题水平降低的缘故，相反，我认为这是中国计算机协会（下称CCF）对于N oip考核目的的审视和改变所导致的必然结果。
因此，我试图通过深入解析本届Noip初赛试囗题，来探寻这种变化下面深层的规律，从而令信息学竞赛选手能更好地备战往后数届的Noip初赛，让初赛不再成为一个问题。
由于条件所限，本文仅以Pascal语言的提高组试囗题作为对象进行分析，相对于普及组而言提高组试囗题一向具有较高的难度和较好的区分度，作为研究对象是个很好的选择；至于说语言的选择，仅是因为笔者个人选择原因。
一、概况本届题目在设置方面与往年相似，由选择题（普及组仅有单项选择题，提高组则有单项选择题与不定项选择题）、问题求解、阅读程序写结果及完善程序四大部分组成；但值得注意的是，今年提高组试囗题的分值设计与往年出现了较大的不同，除了选择题仍然是30分（15分单项+15分不定项），其余部分分值均发生了变化，其中问题求解由10分上升到15分，阅读程序由32分下降到28分，完善程序由28分下降到27分。
由于是第一年实行这种分值，目前暂时无法定言背后的含义，然而或许CCF在初赛更加重视选手的数学素质，而弱化了对于阅读程序能力的考察。
众所周知，阅读程序的能力并不能非常真实地反映选手的程序能力，并且纵观近几年的阅读程序题已没有了什么新意，这也可看做是一个“求新求变”的信号。
至于试囗题整体难度方面较上年有了明显下降，其中问题求解第一题可以看做是考察选手的语文水平，而阅读程序更是没有了以往的“死算”题（即给定若干常数，在程序中设置一系列运算过程，让选手进行阅读计算类型的题目），完善程序给定的源代码风格良好，第二题竟然还加上了注释，这不能不说就是一种降低难度的举动。
NOIP提高组初赛历年试题及答案阅读题篇阅读程序写结果（共4 题，每题8 分，共计32 分）阅读程序的最好方法并非是依次从头到尾。
程序不像迷语，我们无法从末尾几页找到答案，也不像一本引人入胜的书籍，只需直接翻到褶皱最多的那几页，我们就能找到最精彩的片断。
因此我们在阅读程序时，最好逐一考察研究每一段代码，搞清楚每一段代码的来龙去脉，理解每一段代码在程序中所起的作用，进而形成一个虚拟的程序结构，并以此为基础来进行阅读。
1、分层读：高层入手，逐层深入，正确理解程序。
2、写注解：固化、总结、提炼已有的理解成果。
3、先模拟：根据代码顺序跟踪变量，模拟运算。
4、找规律：先模拟几次循环后，找出背后的规律。
5、看功能：从代码结构和运算结果判断程序功能。
6、猜算法：有时不知道算法，通过结构和函数猜一猜。
7、换方法：了解程序本质后，换一个熟悉的方法试试。
对大多数人来说，写程序是令人开心的一件事情，读别人的程序却很痛苦，很恐惧，宁愿自己重写一遍。
其实读到好的程序，就像读一篇美文，令人心旷神怡，豁然开朗，因为这背后是一个人的思维，甚至整个人生。
阅读别人的程序不仅可以巩固自己的知识，启发自己的思维，提升自己的修养，让你收获满满，其实，这也是在学习、在竞赛、在工作中的最重要、最常用的基本功。
如果说写程序是把自己的思维转化为代码，读程序就是把代码转化为你理解的别人的思维。
当你阅读程序时有强烈的代入感，像演员一样，真正进入到编剧的精神世界，面部表情也随之日渐丰富起来。
祝贺你！你通关了！总之，看得多，码得多，拼得多，你就考得多……NOIP2011-1．#include <iostream>#include <cstring> using namespace std; const int SIZE = 100; int main(){int n,i,sum,x,a[SIZE]; cin>>n;memset(a,0,sizeof(a)); for(i=1;i<=n;i++){ cin>>x;a[x]++;}i=0;sum=0;while(sum<(n/2+1)){ i++;sum+=a[i];}cout<<i<<endl; return 0;}输入：4 5 6 6 4 3 3 2 3 2 1一步步模拟，注意输出的是sum超出循环条件时的i值（中位数），而不是sum，也不是a[x]输出：3NOIP2011-2．#include <iostream>using namespace std;int n;void f2(int x,int y);void f1(int x,int y){if(x<n)f2(y,x+y);void f2(int x,int y){cout<<x<<' ';f1(y,x+y);}int main(){cin>>n;f1(0,1);return 0;}输入：30此为简单的递归题，依次输出f2(x,y)中的x值，注意边界条件时f1(x,y)的x>=30咦！这不是隔一个输出一个的Fibonacci吗？输出：1 2 5 13 34NOIP2011-3．#include <iostream>using namespace std;const int V=100;int n,m,ans,e[V][V];bool visited[V];void dfs(int x,intlen){int i;visited[x]= true;if(len>ans)ans=len;for(i=1;i<=n;i++)if( (!visited[i]) &&(e[x][i]!=-1) ) dfs(i,len+e[x][i]);visited[x]=false;}int main(){int i,j,a,b,c;cin>>n>>m;for(i=1;i<=n;i++)for(j=1;j<=m;j++)e[i][j]=-1;for(i=1;i<=m;i++) {cin>>a>>b>>c; e[a][b]=c;e[b][a]=c;}for(i=1;i<=n;i++) visited[i]=false; ans=0;for(i=1;i<=n;i++) dfs(i,0);cout<<ans<<endl; return 0;}输入：4 61 2 102 3 203 4 304 1 401 3 502 4 60一看就知这是深搜算法（DFS），输入是个四个顶点的无向图（邻接矩阵如下）：如len>ans，则ans=len，可以说明这是个在图中用DFS找最长的路径的程序。
NOIP2010第十六届初赛试题及答案(普及组Pascal)NOIP2010第十六届初赛试题及答案(普及组Pascal) PDF格式第十六届全国青少年信息学奥林匹克联赛初赛试题（普及组 Pascal 语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一. 单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确答案。
）1.2E＋03表示（）。
A.2.03B.5C.8D.20002.一个字节（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.exeC.dllD.以是都不是5.如果树根算是第1层，那么一棵n层的二叉树最多有（）结点。
A.2n-1B.2nC.2n+1D.2n+16.提出“存储程序”的计算机工作原理的是（）。
A.克劳德·香农B.戈登·摩尔C.查尔斯·巴比奇D.冯·诺依曼7.设X、Y、Z分别代表三进制下的一位数字，若等式XY＋ZX＝XYX在三进制下成立，那么同样在三进制下，等式XY×ZX＝（）也成立。
A.YXZB.ZXYC.XYZD.XZY9.前缀表达式“＋3×2＋5 12”的值是（）。
A.23B.25C.37D.6510.主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了（）。
A.寄存器B.高速缓存C.闪存D.外存11.一个字长为8位的整数的补码是11111001,则它的原码是（）。
NOIP2010提高组初赛（答案+选择题题目+个人分析)一、单项选择题1.与16进制数A1.2等值的10进制数是（）A.101.2B.111.4C.161.125D.177.25C A1.2=10*16^1+1*16^0+1*16^(-1) 公式A=10B=11C=12D=13E=14F=15A=10*16^1=160 1=1*16^0=1 0.2=1*16^(-1)=1/8=0.125Y*X^Z+y*x^z+y*x^z+.......... Y题中式子每一位数X进制数Z第几位数例如上式A是第2位数所以2次方必考的进制运算没什么可说的=。
=2.一个字节（byte）由（）个二进制组成。
A.8B.16C.32D.以上都有可能A字节8个字16个双字32个常识问题：数据存储是以“字节”（Byte）为单位，数据传输是以“位”（bit）为单位，一个位就代表一个0或1（即二进制），每8个位（bit）组成一个字节（Byte）。
8bit=1Byte3.以下逻辑表达式的值恒为真的是（）。
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)A不太懂表示方法："∨"表示"或"，"∧"表示"与"."┐"表示"非"."= =" 表示＂等价＂.１和０表示＂真＂和＂假＂(还有一种表示,"+"表示"或", "·"表示"与")4.Linux下可执行文件的默认扩展名是( )。
A. exe windows执行程序B. Com windows可执行文件C. Dll动态链接库D. 以上都不是DLinux和Windows不同，Linux一般可执行文件都没有扩展名；Linux不根据拓展名判断文件类型而是根据文件内容判断；因此Linux下扩展名的作用只是帮助以识别文件的，对Linux本身并没有什么用=。
CCFNOIP2010全国青少年信息学奥林匹克联赛初赛试题第⼗六届全国青少年信息学奥林匹克联赛初赛试题试题及答案NOIP2010（Pascal提⾼组）⼀、单项选择题1.与16进制数 A1.2等值的10进制数是（）A.101.2B.111.4C.161.125D.177.25解：此题考查的知识点是进制转换。
把⼀个M进制的数转换为⼗进制数的⽅法是：⽤这个M进制数的第N 位（从⼩数点出发从左往右依次为第1位，第2位，第3位……，从⼩数点出发从右往左依次为第-1位，第-2位，第-3位……）乘以M的N-1次⽅，然后累计求和。
⼗六进制中⽤A,B,C,D,E,F分别表⽰10，11，12，13，14，15.（A1.2）16=10*161+1*160+2*16-1=(161.125)10故选答案C.2.⼀个字节（byte）由（）个⼆进制组成。
A.8B.16C.32D.以上都有可能解：此题要求考⽣掌握计算机存储单元⽅⾯的相关知识。
计算机中的信息都是以⽂件形式被保存和管理的；所有的信息在计算机中都要转化为⼆进制数。
计算机最基本的存储单元是字节Byte，最⼩单位是⼆进制位bit。
1个字节占8个⼆进制位；⽐字节⼤的存储单位还有KB,MB,GB,TB,它们的换算关系是：1KB=1024B,1MB=1024KB,1GB=1024MB,1TB=1024GB.计算机有⼀个重要的性能参数：字长，指的就是CPU⼀次能处理的⼆进制信息串的长度，⼀个汉字按GB2312-80规划转化为⼆进制信息串后长16位（2个字节），⼀个英⽂字母或数字按ASCII码规则转化为⼆进制信息串后长8位（1个字节）。
故选答案A.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)解：此题考查逻辑运算⽅⾯的知识。
⽤逻辑运算符连接起来的表达式称为逻辑表达式。
第十六届全国青少年信息学奥林匹克联赛初赛试题（提高组 C++语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10题，每题1.5分，共计15分。
每题有且仅有一个正确选项。
）1．与十六进制数 A1.2等值的十进制数是（）A．101.2 B．111.4 C．161.125 D．177.252．一个字节（byte）由（）个二进制组成。
A．8 B．16 C．32 D．以上都有可能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. 6 58．主存储器的存取速度比中央处理器(CPU)的工作速度慢的多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了( )。
A．寄存器 B．高速缓存 C．闪存 D．外存9．完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。
假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（）号位置。
A．2k B．2k+1 C．k/2下取整 D．(k+1)/210．以下竞赛活动中历史最悠久的是（）。
A．全国青少年信息学奥林匹克联赛（NOIP）B．全国青少年信息学奥林匹克竞赛（NOI）C．国际信息学奥林匹克竞赛（IOI）D．亚太地区信息学奥林匹克竞赛（APIO）二、不定项选择题（共10题，每题1.5分，共计15分。
每题正确答案的个数不少于1。
多选或少选均不得分）。
1．元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。
如果第1个出栈的是R3，那么第5个出栈的可能是( )。
A．R1 B．R2 C．R4 D．R52．Pascal语言，C语言和C++语言都属于( )。
A．高级语言 B．自然语言C．解释性语言 D．编译性语言3．原地排序是指在排序过程中(除了存储待排序元素以外的)辅助空间的大小与数据规模无关的排序算法。
以下属于原地排序的有( )。
A．冒泡排序 B．插入排序 C．基数排序 D．选择排序4．在整数的补码表示法中，以下说法正确的是（）。
A．只有负整数的编码最高位为1B．在编码的位数确定后，所能表示的最小整数和最大整数的绝对值相同C．整数0只有一个唯一的编码D．两个用补码表示的数相加时，如果在最高位产生进位，则表示运算溢出5．一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（）。
A．0 B．2 C．4 D． 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->link = p->llink; delete p;10．今年(2010年)发生的事件有（）。
A．惠普实验室研究员Vinay Deolalikar 自称证明了P≠NPB．英特尔公司收购计算机安全软件公司迈克菲(McAfee)C．苹果公司发布iPhone 4手机D．微软公司发布Windows 7 操作系统三．问题求解（共2题，每空5分，共计10分）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题，每题8分，共计32分）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 0;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>#include<cstring>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 33 44 55 66 11 72 73 84 85 96 9输出：_________五．完善程序 (第1题，每空2分，第2题，每空3分，共28分)1．(过河问题) 在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入N(2<=N<1000)和这N个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸.例如,有3个人甲、乙、丙,他们单独过桥的时间分别为1、2、4,则总共最少需要的时间为7.具体方法是:甲、乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲、丙在一起过桥到河的左岸,总时间为2+1+4=7.#include<iostream>#include<cstring>using namespace std;const int SIZE=100;const int INFINITY = 10000;const bool LEFT=true;const bool RIGHT =false;const bool LEFT_TO_RIGHT=true;const bool RIGHT_TO_LEFT=false;int n,hour[SIZE];bool pos[SIZE];int max(int a,int b){if(a>b)return a;elsereturn b;}int go(bool stage){int i,j,num,tmp,ans;if(stage==RIGHT_TO_LEFT){num=0;ans=0;for(i=1;i<=n;i++)if(pos[i]==RIGHT){num++;if( hour[i]>ans)ans=hour[i];}if( ① )return ans;ans=INFINITY;for(i=1;i<=n-1;i++)if(pos[i]==RIGHT)for(j=i+1;j<=n;j++)if(pos[j]==RIGHT){pos[i]=LEFT;pos[j]=LEFT;tmp=max(hour[i],hour[j])+ ②; if(tmp<ans)ans=tmp;pos[i]=RIGHT;pos[j]=RIGHT;}return ans;}if(stage==LEFT_TO_RIGHT){ans=INFINITY;for(i=1;i<=n;i++)if( ③ ){pos[i]=RIGHT;tmp=④;if(tmp<ans)ans=tmp;⑤;}return ans;}return 0;}int main(){int i;cin>>n;for(i=1;i<=n;i++){cin>>hour[i];pos[i]=RIGHT;}cout<<go[RIGHT_TO_LEFT)<<endl;return 0;}2.（烽火传递）烽火台又称烽燧，是重要的军事防御设施，一般建在险要处或交通要道上。
