文档介绍：信息学奥赛初赛试卷试题
信息学奥赛初赛试卷试题
信息学奥赛初赛试卷试题
第十六届全国青少年信息学奥林匹克联赛初赛试题
（提升组Pascal 语言二小时达成）
●●所有试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●
一．单项指向链表中的一个结点，
他的左右结点均为非空。现要求删除结点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≠NP
B．英特尔企业收买计算机安全软件企业迈克菲(McAfee)
C．苹果企业公布iPhone 4 手机D．微软企业公布Windows 7 操作系统
三、问题求解
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 的最小值是___________。
四、阅读程序写结果
1. begin
const if a[i] <= b[j] then
size = 10; begin