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≠NP
B.英特尔公司收购计算机安全软件公司迈克菲(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 的最小
值是___________。