【分析】选择A
加入的边依次为v0v1、v1v2、v1v3（或v2v3）、v1v5、v3v4。
10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：
A）http://www.noi.com/
B）http://www.noi.org/
C）http://www.noi.cn/
D）http://www.xinxixue.com/ 【分析】选择C 官网
二.不定项选择题（共10题，每题1.5分，共计15分，每题正确答案的个数不少于1。多选或少选均不得分）。
1、关于CPU下面哪些说法是正确的：
A）CPU全称为中央处理器（或中央处理单元）。
B）CPU能直接运行机器语言。
C）CPU最早是由Intel公司发明的。
D）同样主频下，32位的CPU比16位的CPU运行速度快一倍。
【分析】选择AB
C项中，Intel最早发明的是微处理器，而CPU之前就由电子管、晶体管实现着呢 D项中，位数只能说明处理的字长，所在的系统硬件指令不同，速度很难说谁快。
2、关于计算机内存下面的说法哪些是正确的：
A）随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。
B）一般的个人计算机在同一时刻只能存/取一个特定的内存单元。
C）计算机内存严格来说包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。
D）1MB内存通常是指1024*1024字节大小的内存。
【分析】选择BD 一般是对字节的一个单元串行操作。1MB=1024KB=1024*1024B
A中RAM不是位置随机，而是随时访问，所谓“随机存取”，指的是当存储器中的消息被读取或写入时，所需要的时间与这段信息所在的位置无关。 C中高速缓存和寄存器的物理实现是集成在CPU中，这两部分不属于冯诺依曼体系中的五大部分的任意一个部分。
3、关于操作系统下面说法哪些是正确的：
A.多任务操作系统专用于多核心或多个CPU架构的计算机系统的管理。
B.在操作系统的管理下，一个完整的程序在运行过程中可以被部分存放在内存中。
C.分时系统让多个用户可以共享一台主机的运算能力，为保证每个用户都得到及时的响应通常会采用时间片轮转调度的策略。
D.为了方便上层应用程序的开发，操作系统都是免费开源的。
【分析】选择BC
A多任务系统可以是单个CPU构架的，普通的PC都是多任务的。 D操作系统不是都免费开源
4、关于计算机网络，下面的说法哪些是正确的：
A）网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。
B）新一代互联网使用的IPv6标准是IPv5标准的升级与补充。
C）TCP/IP是互联网的基础协议簇，包含有TCP和IP等网络与传输层的通讯协议。 D）互联网上每一台入网主机通常都需要使用一个唯一的IP地址，否则就必须注册一个固定的域名来标明其地址。
【分析】选择C
A网络协议分层不是为了兼容，而是根据网络分层模型来的。
B新的IPv6是IPv4的升级。
D即使注册了域名也要有IP地址的。
5、关于HTML下面哪些说法是正确的：
A）HTML全称超文本标记语言，实现了文本、图形、声音、乃至视频信息的统一编码。
B）HTML不单包含有网页内容信息的描述，同时也包含对网页格式信息的定义。
C）网页上的超链接只能指向外部的网络资源，本网站网页间的联系通过设置标签来实现。 D）点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符（URL）请求网络资源或者网络服务。
【分析】选择BD
A没有都统一编码
C本网站页面也可以用超链接，就是绝对路径。也可以用相对路径。
6、若3个顶点的无权图G的邻接矩阵用数组存储为{{0，1，1}{1，0，1}{0，1，0}}，假定在具体存储中顶点依次为：v1，v2，v3 关于该图，下面的说法哪些是正确的：
A）该图是有向图。
B）该图是强联通的。
C）该图所有顶点的入度之和减所有顶点的出度之和等于1。
D）从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。
【分析】选择ABD
可以画出这个有向图，矩阵存储的时候，矩阵为非对称，故为有向图。 C入度之和等于出度之和。
7、在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每个结点都以next字段的指针指向下一个节点。假定其中已经有了2个以上的结点。下面
哪些说法是正确的：
A）如果p指向一个待插入的新结点，在头部插入一个元素的语句序列为：
p^.next:=clist^.next;clist^.next:=p;
B）如果p指向一个待插入的新结点，在尾部插入一个元素的语句序列为：
p^.next:=clist;clist^.next:=p;
C）在头部删除一个结点的语句序列为：
p:=clist^.next;clist^.next:=clist^.next^.next;dispose(p);
D）在尾部删除一个结点的语句序列为：
p:=clist;clist:=clist^.next;dispose(p);
【分析】选择AC
B应为p^.next:=clist^.next;clist^.next:=p; D中要循环找到尾指针的上一个元素才能进行删除
8、散列表的地址区间为0-10，散列函数为H(K)=K mod 11。采用开地址法的线性探查法处理冲突，并将关键字序列26，25，72，38，8，18，59存储到散列表中，这些元素存入散列表的顺序并不确定。假定之前散列表为空，则元素59存放在散列表中的可能地址有：
A）5 B）7 C）9 D）10
【分析】选择ABCD 哈希函数的冲突避免
计算各个的散列值26 25 72 38 8 18 59
5 4 6 5 8 7 4 这样就可能5的顺序：25、59??
7的顺序：25、26、38、59??
9的顺序：25、26、38、18、59?? 10的顺序：??59
上面的顺序不是唯一的。
9、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪些排序算法是稳定的：
A）插入排序 B）基数排序 C）归并排序 D）冒泡排序
【分析】选择ABCD
在编程实现的时候，只要控制好边界都是可以达到稳定排序的。
10、在参加NOI系列竞赛过程中，下面哪些行为是被严格禁止的：
A）携带书写工具，手表和不具有通讯功能的电子词典进入赛场。
B）在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。
C）通过互联网搜索取得解题思路。
D）在提交的程序中启动多个进程以提高程序的执行效率。
【分析】选择BCD
都算是违反纪律的。A有时候是可以的。这里考的是NOI，不是NOIP。 三.问题求解（共2题，每空5分，共计10分）
1.拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若
【分析】432
用排列组合即可，先确定12346的顺序，然后将7插入内部有两个位置可选，然后将5插入时候，可以有6个位置选择。最后，放89的时候，考虑两种情况，89在一起，有8个位置选；89不在一起，8个位置选2个。 C(2,1)×C(6,1)×[C(8,1)+C(8,2)]=2×6×(8+28)=432
2、某个国家的钱币面值有1，7，7^2，7^3共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通______张钱币。
【分析】35
10015化成7进制数是41125，正常是4×7+1=29张7^3面额的，1张7^2面额，2张7面额的，5张1面额的。
因为可以无限且找零，并要求最少流通数量。这样就把7进制上大于等于4的数a，用找零7-a的方法代替，这样就能达到最少。
这里29、1、2、5中只有5是大于4的，所以用一张大额的，并7-5找零的方法计算。这样，总数29+1+2+(1+7-5)=35张。