下载文档原格式
山东专升本（计算机）历年真题试卷汇编2(题后含答案及解析) 题型有：1. 填空题 2. 单选题 3. 多选题 4. 判断题填空题每空2分，共20分。
请将每一个空的正确答案写在答题卡上。
1．在计算机系统中扩展名为TXT的文件被称为______文件，可以用记事本打开。
正确答案：文本文件解析：在计算机系统中，扩展名为TXT的文件被称为文本文件，可以用记事本创建、编辑和打开。
2．在Windows操作系统中，用鼠标双击______，可以关闭该窗口。
正确答案：程序图标解析：标题栏的最左边是应用程序的程序图标(又称“控制图标”)，双击窗口的程序图标，可关闭该窗口。
关闭一个Windows XP窗口的操作有：①Alt+F4；②单击标题栏中的“×”按钮；③用鼠标双击程序图标；④在任务栏上右击该图标，选择关闭。
3．计算机中通常所说的总线包括地址总线、数据总线和______三种。
正确答案：控制总线4．在Windows XP中，要进入当前对象的帮助窗口，可以按______键。
正确答案：Fl解析：在Windows XP中，要进入当前对象的帮助窗口，可以按F1键。
5．地址码长度为二进制24位时，其寻址范围是______MB。
正确答案：16解析：有24位二进制数作为地址，则有224种地址组合，对应224个存储单元。
假设一个存储单元对应一个字节，则24位地址码的寻址范围是224Byte=24×20Byte=16 MB。
6．在计算机内，多媒体数据最终是以______形式存在的。
正确答案：二进制代码解析：由于计算机只能处理二进制数字信号，因此，在计算机内多媒体数据也是以二进制代码的形式存在的。
7．MPEG是一个通用的标准，适用于______的压缩。
正确答案：运动图像解析：MPEG压缩标准是由MPEG专家针对运动图像而设计的，MPEG标准包括MPEG视频、MPEG音频和MPEG系统三部分。
8．JPEG是一种图像压缩格式，其含义是______。
计算机专业基础综合操作系统（进程管理）历年真题试卷汇编2(总分：96.00，做题时间：90分钟)一、单项选择题(总题数：28，分数：56.00)1.单项选择题下列各题的备选答案中，只有一个是符合题意的。
__________________________________________________________________________________________2.下列几种关于进程的叙述，____最不符合操作系统对进程的理解。
【浙江大学2003年】A.进程是在多程序并行环境中的完整的程序√B.进程可以由程序、数据和进程控制块描述C.线程是一种特殊的进程D.进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位综合考查进程的相关概念。
进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位，不是完整程序，程序是在时间上按严格次序前后相继的操作序列，是一个静态的概念。
3.下面关于并发性的论述中，正确的是____。
【太原科技大学2006年】A.并发性是指若干个事件在同一时刻发生B.并发性是指若干个事件在不同时刻发生C.并发性是指若干个事件在同一时间间隔内发生√D.并发性是指若干个事件在不同时间间隔内发生考查并发性的定义，注意与并行性相区分。
并发性是指两个或多个事件在同一时间间隔内发生；并行性是指两个或多个事件在同一时刻发生。
4.并发进程指____。
【北京理工大学2002年】A.可平行执行的进程√B.可先后执行的进程C.可同时执行的进程D.不可中断的进程考查并发进程的定义。
并发进程是在同一时间段内运行。
从宏观上看，进程之间不是先后执行，而是平行执行；从微观上看，进程之间不是同时执行，而是按时间片轮转交替执行。
5.下面对进程的描述中，错误的是____。
A.进程是动态的集合B.进程有生命期C.进程是指令的集合√D.进程可以并发执行考查进程的概念。
6.一个进程释放了一台打印机后，有可能改变____的状态。
计算机专业基础综合计算机组成原理（输入／输出(I／O)系统）历年真题试卷汇编2(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：25，分数：50.00)1.计算机的外部设备是指____。
（分数：2.00）A.输入／输出设备B.外存储器C.输入／输出设备和外存储器√D.电源解析：解析：考查计算机外部设备的概念。
除主机以外的硬件装置统称为外部设备或外围设备，包括输入／输出设备和外存储器。
2.下列说法正确的是____。
（分数：2.00）A.计算机中一个汉字内码在主存中占用4BB.输出的字型码16×16点阵在缓冲存储区中占用32B √C.输出的字型码16×16点阵在缓冲存储区中占用16BD.以上说法都不对解析：解析：考查基本概念。
计算机中一个汉字内码在主存中占用2B，输出的字型码16×16点阵在缓冲存储区中占用(16×16／8)B=32B。
3.对于字符显示器，主机送给显示器的是打印字符的____。
【北京理工大学2002年】（分数：2.00）A.AscII码√B.列点阵码C.BCD码D.行点阵码解析：解析：考杏字符显示器。
当显示器刷新显示时，首先要从缓冲存储器中读出一个要显示的字符编码，即打印字符的ASCII码，然后以此编码为依据，到字符发生器读取该字符的第1行光点信息，然后通过并串转换电路，变成串行信息送到CRT显示。
对于字符显示器来说，生机送给显示器的是打印字符的ASCII 码，而从字符发生器中取出的是字符的行点阵码。
4.在打印机或显示器的字库中，存放着字符的____。
【北京理工大学2002年】（分数：2.00）A.二进制码B.ASCII码C.BCD码D.点阵编码√解析：解析：考查打印机和显示器的字符存放方式。
在打印机或显示器的字库中，存放着字符的点阵编码。
5.CRT的分辨率为1024×1024像素，像素的颜色数为256，则刷新存储器的容量为____。
计算机专业基础综合历年真题试卷汇编2(题后含答案及解析)题型有：1. 单项选择题 2. 综合应用题单项选择题1-40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
1．先序序列为a，b，c，d的不同二叉树的个数是_______。
A．13B．14C．15D．16正确答案：B解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。
因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列a，b，c，d为入栈次序，则出栈序列的个数为?”，对于n个不同元素进栈，出栈序列的个数为C2nn=14。
知识模块：数据结构2．假设栈初始为空，将中缀表达式a／b+(c*d-e*f)／g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是_______。
A．+(*-B．+(-*C．／+(*-*D．／+-*正确答案：B解析：将中缀表达式转换为后缀表达式的算法思想如下：从左向右开始扫描中缀表达式；遇到数字时，加入后缀表达式；遇到运算符时：a．若为‘(’，入栈；b．若为‘)’，则依次把栈中的的运算符加入后缀表达式中，直到出现‘(’，从栈中删除‘(’；c．若为除括号外的其他运算符，当其优先级高于除‘(’以外的栈顶运算符时，直接入栈。
否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。
当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。
知识模块：数据结构3．在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是_______。
A．41B．82C．113D．122正确答案：B解析：设树中度为i(i=0，1，2，3，4)的结点数分别为Ni，树中结点总数为N，则树中各结点的度之和等于N-1，即N=1+N1+2N2+3N3+4N4=N0+N1+N2+N3+N4，根据题设中的数据，即可得到N0=82，即树T的叶结点的个数是82。
单项选择题---为题目类型1.设元素集合为D＝{1，2，3，4，5，6}。
B＝(D，R)为线性结构则R 是( )。
（A）R＝{(6，1)，(5，6)，(1，3)，(2，4)，(3，2)}（B）R＝{(4，5)，(6，1)，(5，6)，(1，3)，(2，4)，(3，2)}（C）R＝{(6，1)，(5，6)，(1，3)，(3，4)，(3，2)}（D）R＝{(6，1)，(5，6)，(2，3)，(2，4)，(3，2)}2.对长度为8 的数组进行快速排序，最多需要的比较次数为( )。
（A）8（B）8（C） 6（D） 43.树的度为3，共有31 个结点，但没有度为1 和2 的结点。
则该树中度为3 的结点数为( )。
（A）1（B）9（C）0（D）不可能有这样的树4.设栈与队列初始状态为空。
将元素A、B、C、D、E、F、G、H 依次轮流入栈和入队，然后依次轮流出栈和退队，则输出序列为( )。
（A）A，B，C，D，H，G，F，E（B）B，G，D，E，F，C，H，A（C）D，C，B，A，E，F，G，H（D）G，B，E，D，C，F，A，H5.数据字典的作用是( )。
（A）定义流程图中各个成分的具体含义（B）定义数据流图中各个成分的具体含义（C）定义系统结构图中各个成分的具体含义（D）定义功能结构图中各个成分的具体含义6.黑盒测试技术依据的是( )。
（A）软件功能的描述（B）程序的逻辑结构（C）程序的物理结构（D）软件行为的描述7.下面描述错误的是( )。
（A）对象一定有标识（B）对象一定有属性和方法(或操作)（C）对象具有封装性（D）不同对象的同一属性一定有相同的属性值8.关系数据模型的3 个组成部分中不包括( )。
（A）数据操作（B）数据结构（C）并发控制（D）完整性规则9.学校规定一个年级的所有班配备一名辅导员，则实体班级与实体辅导员之间的联系是( )。
（A）多对多（B）多对一（C）一对多（D）一对一10.定义学生选修课程的关系模式如下：SC(S#，Sn，C#，Cn，T#，G，Cr)(其属性分别为学号、姓名、课程号、课程名、授课老师号、成绩、学分)并且一门课程可由多个教师教授，则该关系的键是( )。
计算机专业基础综合计算机网络（网络层）历年真题试卷汇编2(总分：132.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.一个校园网中的4个部门都已经建立了自己的以太网，所有计算机使用的操作系统都相同，现在需要将这些部门的局域网互联起来，而且每个部门使用不同的网络地址(即每个部门一个子网)，应当选择的互联设备是____。
（分数：2.00）A.第2层交换机B.集线器C.路由器√D.网桥解析：解析：考查异构网络互联。
能够互联不同网络地址的应该是网络层设备，第2层交换机和网桥是数据链路层设备，集线器是物理层设备，只有路由器是网络层设备，因此选C。
2.需要将一个局域网分为多个IP子网时，应当选用的网络互联设备是____。
（分数：2.00）A.中继器或集线器B.网桥C.路由器√D.网关解析：解析：考查网络互联。
解决划分子网问题需要的也是网络层设备，中继器是物理层设备，而网关是在传输层上以实现网络互联，是最复杂的网络互联设备，仅用于两个高层协议不同的网络互联。
网关既可以用于广域网互联，也可以用于局域网互联。
网关是一种充当转换重任的计算机系统或设备，在使用不同的通信协议、数据格式或语言，甚至体系结构完全不同的两种系统之间，网关是一个翻译器。
3.在计算机网络中，能将异种网络互联起来，实现不同网络协议相互转换的网络互联设备是____。
【中南大学2007年】（分数：2.00）A.局域网交换机B.集线器C.路由器D.网关√解析：解析：考查异构网络互联。
关4.在OSI中，完成整个网络系统内连接工作，为上一层提供整个网络范围内两个终端用户之间数据传输通路工作的是____。
【华中科技大学2001年】（分数：2.00）A.物理层B.数据链路层C.网络层√D.运输层解析：解析：考查网络层的功能。
网络层的主要功能有：异构网络互联、路由选择与转发、拥塞控制、网络管理等。
为上一层提供整个网络范围内两个终端用户之间数据传输通路的工作即路由选择，因此选C。
计算机专业基础综合计算机网络（网络层）历年真题试卷汇编2（总分:132.00，做题时间：90分钟）一、单项选择题（总题数：27,分数：54.00）1.一个校园网中的4个部门都巳经建立了自己的以太网，所有计算机使用的操作系统都相同，现在需要将这些部门的局域网互联起来，而且每个部门使用不同的网络地址（即每个部门一个子网），应当选择的互联设备是。
（分数：2.00）A.第2层交换机B.集线器C.路由器VD.网桥解析：解析：考查异构网络互联。
能够互联不同网络地址的应该是网络层设备，第2层交换机和网桥是数据链路层设备，集线器是物理层设备，只有路由器是网络层设备，因此选C。
2.需要将一个局域网分为多个IP子网时，应当选用的网络互联设备是。
（分数：2.00）A.中继器或集线器B.网桥C.路由器VD.网关解析：解析：考查网络互联。
解决划分子网问题需要的也是网络层设备，中继器是物理层设备，而网关是在传输层上以实现网络互联，是最复杂的网络互联设备，仅用于两个高层协议不同的网络互联。
网关既可以用于广域网互联，也可以用于局域网互联。
网关是一种充当转换重任的计算机系统或设备，在使用不同的通信协议、数据格式或语言，甚至体系结构完全不同的两种系统之间，网关是一个翻译器。
3.在计算机网络中，能将异种网络互联起来，实现不同网络协议相互转换的网络互联设备是。
【中南大学2007年】（分数：2.00）A.局域网交换机B.集线器C.路由器D.网关V解析：解析：考查异构网络互联。
关4.在OSI中，完成整个网络系统内连接工作，为上一层提供整个网络范围内两个终端用户之间数据传输通路工作的是。
【华中科技大学2001年】（分数：2.00）A.物理层B.数据链路层C.网络层VD.运输层解析：解析：考查网络层的功能。
网络层的主要功能有：异构网络互联、路由选择与转发、拥塞控制、网络管理等。
为上一层提供整个网络范围内两个终端用户之间数据传输通路的工作即路由选择，因此选C。
全国计算机二级考试历年真题（整理）第一篇：全国计算机二级考试历年真题(整理)05年试卷一、选择题（（1）~（35）每小题2分，共70分下列各题A）、B）、C）、D）四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上，答在试卷上不得分。
（1）数据的存储结构是指（）。
A．存储在外存中的数据B．数据所占的存储空间量C．数据在计算机中的顺序存储方式 D．数据的逻辑结构在计算机中的表示（2）下列关于栈的描述中错误的是（）。
A．栈是先进后出的线性表 B．栈只能顺序存储 C．栈具有记忆作用D．对栈的插入与删除操作中，不需要改变栈底指针（3）对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（）。
A．冒泡排序为n/2 B．冒泡排序为n C．快速排序为n D．快速排序为n(n-1)/2（4）对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）。
A．log2n B．n/2 C．n D．n+1（5）下列对于线性链表的描述中正确的是（）。
A．存储空间不一定是连续，且各元素的存储顺序是任意的B．存储空间不一定是连续，且前件元素一定存储在后件元素的前面C．存储空间必须连续，且前件元素一定存储在后件元素的前面D．存储空间必须连续，且各元素的存储顺序是任意的（6）下列对于软件测试的描述中正确的是（）。
A．软件测试的目的是证明程序是否正确B．软件测试的目的是使程序运行结果正确C．软件测试的目的是尽可能多地发现程序中的错误D．软件测试的目的是使程序符合结构化原则（7）为了使模块尽可能独立，要求（）。
A．模块的内聚程度要尽量高，且各模块间的耦合程度要尽量强B．模块的内聚程度要尽量高，且各模块间的耦合程度要尽量弱C．模块的内聚程度要尽量低，且各模块间的耦合程度要尽量弱D．模块的内聚程度要尽量低，且各模块间的耦合程度要尽量强（8）下列描述中正确的是（）。
A．程序就是软件B．软件开发不受计算机系统的限制C．软件既是逻辑实体，又是物理实体D．软件是程序、数据与相关文档的集合（9）数据独立性是数据库技术的重要特点之一。
计算机专业基础综合计算机组成原理（输入／输出(I／O)系统）历年真题试卷汇编2(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：25，分数：50.00)1.计算机的外部设备是指____。
A.输入／输出设备B.外存储器C.输入／输出设备和外存储器√D.电源考查计算机外部设备的概念。
除主机以外的硬件装置统称为外部设备或外围设备，包括输入／输出设备和外存储器。
2.下列说法正确的是____。
A.计算机中一个汉字内码在主存中占用4BB.输出的字型码16×16点阵在缓冲存储区中占用32B √C.输出的字型码16×16点阵在缓冲存储区中占用16BD.以上说法都不对考查基本概念。
计算机中一个汉字内码在主存中占用2B，输出的字型码16×16点阵在缓冲存储区中占用(16×16／8)B=32B。
3.对于字符显示器，主机送给显示器的是打印字符的____。
【北京理工大学2002年】A.AscII码√B.列点阵码C.BCD码D.行点阵码考杏字符显示器。
当显示器刷新显示时，首先要从缓冲存储器中读出一个要显示的字符编码，即打印字符的ASCII码，然后以此编码为依据，到字符发生器读取该字符的第1行光点信息，然后通过并串转换电路，变成串行信息送到CRT显示。
对于字符显示器来说，生机送给显示器的是打印字符的ASCII码，而从字符发生器中取出的是字符的行点阵码。
4.在打印机或显示器的字库中，存放着字符的____。
【北京理工大学2002年】A.二进制码B.ASCII码C.BCD码D.点阵编码√考查打印机和显示器的字符存放方式。
在打印机或显示器的字库中，存放着字符的点阵编码。
5.CRT的分辨率为1024×1024像素，像素的颜色数为256，则刷新存储器的容量为____。
【大连理工大学2005年】A.256MBB.1MB √C.256KBD.32MB考查刷新存储器容量的计算。
刷新存储器的容量为1024×1024×8bit=1MB。
计算机专业基础综合计算机组成原理（数据的表示和运算）历年真题试卷汇编2(总分：102.00，做题时间：90分钟)一、单项选择题(总题数：37，分数：86.00)1.下列数中最大的是____。
【中南大学1998年】A.(1100lOl0)2B.(102)8C.(E9)16 √D.(121)3考查进位计数制及其相互转换。
本题将B、C选项改写为二进制表示，可更快找到最大数。
2.下列数中最小的是____。
【北京邮电大学2002年】A.(101001)2B.(52)8C.(101001)BcD √D.(233)16考查进位计数制及其相互转换。
C选项补齐为00101001，即为十进制数29，为最小数。
3.把十进制数172转换为八进制数和十六进制数分别是____。
【中南大学1998年】A.(543)，(AC)B.(543)，(AB)C.(254)，(AC) √D.(253)，(AC)考查不同进位计数制之间的转换。
十进制数172表示成二进制为10101100。
转换为八进制时，从最低位每3位对应一位八进制，则得(254)。
转换为十六进制时，从最低位每4位对应一位十六进制，则得(AC)。
4.下列____种说法有误差。
【华中师范大学1997年】A.任何二进制整数都可用十进制表示B.任何二进制小数都可用十进制表示C.任何十进制整数都可用二进制表示D.任何十进制小数都可用二进制表示√考查二进制与十进制的转换。
计算机中，小数的表示是离散的，并不是所有十进制小数都可用二进制表示。
5.下列____是不合法的BCD码。
【哈尔滨工程大学2003年】A.1111001B.11010110 √C.100D.10000101考查BCD码。
BCD码中，1010～1111为冗余编码，故B选项为不合法的BcD码。
6.余3编码是____。
【华中科技大学2002年】A.字符编码B.有权编码C.无权编码√D.汉字编码考查余3码。
余3码是一种无权码，是在8421码的基础上加上(0011) 2形成的，因每个数都多余“3”，故称余3码。
计算机专业基础综合历年真题试卷汇编2(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：16，分数：32.00)1.单项选择题1-40小题。
下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
（分数：2.00）__________________________________________________________________________________________解析：2.若无向图G=(V，E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是_______。
（分数：2.00）A.6B.15C.16 √D.21解析：解析：要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通，首先需要G的任意6个结点构成完全连通子图G1，需n(n-1)／2=6×(6-1)／2=15条边，然后再添一条边将第7个结点与G1连接起来，共需16条边。
3.下列关于图的叙述中，正确的是_______。
Ⅰ．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路（分数：2.00）A.仅ⅡB.仅Ⅰ、ⅡC.仅Ⅲ√D.仅Ⅰ、Ⅲ解析：解析：第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，故Ⅰ错误；稀疏图是边比较少的情况，此时用邻接矩阵的空间复杂度为O(n 2)，必将浪费大量的空间，而邻接表的空间复杂度为O(n+e)，应该选用邻接表，故Ⅱ错误。
存在回路的有向图不存在拓扑序列，若拓扑排序输出结束后所余下的顶点都有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在回路，故Ⅲ正确。
4.设图的邻接矩阵A如下所示。
各顶点的度依次是_______（分数：2.00）A.1，2，1，2B.2，2，1，1C.3，4，2，3 √D.4，4，2，2解析：解析：邻接矩阵A为非对称矩阵，说明图是有向图，度为入度加出度之和。
各顶点的度是矩阵中此结点对应的行(对应出度)和列(对应入度)的非零元素之和。
5.对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是_______。
（分数：2.00）A.O(n)B.O(e)C.O(n+e) √D.O(n*e)解析：解析：广度优先遍历需要借助队列实现。
邻接表的结构包括：顶点表；边表(有向图为出边表)。
当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次(顶点表遍历)，故时间复杂度为O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次(出边表遍历)，故时间复杂度为O(e)，算法总的时间复杂度为O(n+e)。
6.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是_______。
（分数：2.00）A.b，c，a，b，d，e，g，fB.e，a，f，g，b，h，c，dC.d，b，c，a，h，e，f，gD.a，b，c，d，h，e，f，g √解析：解析：只要掌握DFS和BFS的遍历过程，便能轻易解决。
逐个代入，手工模拟，选项D是深度优先7.设有向图G=(V，E)，顶点集V={V 0，V 1，V 2，V 3 )，边集E={＜v 0，v 1＞，＜v 0，v 2＞，＜v 0，v 3＞，＜v 1，v 3＞}。
若从顶点V 0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是_______。
（分数：2.00）A.2B.3C.4D.5 √解析：解析：画出该有向图图形如下：5种可能：＜v 0，v 1，v 3，v 2＞，＜v 0，v 2，v 3，v 1＞，＜v 2，v 0，v 3＞，＜v 0，v 3，v 2，v 1＞，＜v 0，v 3，v 1，v 2＞，选D。
8.下列关于最小生成树的叙述中，正确的是_______。
Ⅰ．最小生成树的代价唯一Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中Ⅲ．使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同Ⅳ．使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树总不相同（分数：2.00）A.仅Ⅰ√B.仅ⅡC.仅Ⅰ、ⅢD.仅Ⅱ、Ⅳ解析：解析：对于Ⅰ，最小生成树的树形可能不唯一(这是因为可能存在权值相同的边)，但是代价一定是唯一的，Ⅰ正确。
对于Ⅱ，如果权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，Ⅱ错误。
对于Ⅲ，设N个结点构成环，N-1条边权值相等，则从不同的顶点开始普里姆算法会得到N-1中不同的最小生成树，Ⅲ错误。
对于N，当最小生成树唯一时(各边的权值不同)，普里姆算法和克鲁斯卡尔算法得到的最小生成树相同，Ⅳ错误。
9.求下面带权图的最小(代价)生成树时，可能是克鲁斯卡(Kruskal)算法第2次选中但不是普里姆(Prim)算法(从V4开始)第2次选中的边是_______（分数：2.00）A.(V 1，V 3 )B.(V 1，V 4 )C.(V 2，V 3 ) √D.(V 3，V 4 )解析：解析：从V 4开始，Kruskal算法选中的第一条边一定是权值最小的(V 1，V 4 )，B错误。
由于V 1和V 4已经可达，第二条边含有V 1和V 4的权值为8的一定符合Prim算法，排除A、D。
10.对如下有向带权图，若采用迪杰斯特拉(Dijkstra)算法求从源点a到其他各项点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是_______（分数：2.00）A.d，e，fB.e，d，fC.f，d，e √D.f，e，d解析：解析：从a f，d，e。
11.对下图进行拓扑排序，可以得到不同拓扑序列的个数是_______（分数：2.00）A.4B.3 √C.2D.1解析：解析：3个不同的拓扑序列，分别为：abced、abecd、aebcd。
12.若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是_______。
（分数：2.00）A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一√D.无法确定是否存在解析：解析：对角线以下元素均为零，表明只有顶点i到顶点j(i＜j)可能有边，而顶点j到顶点i一定没有边，即有向图是一个无环图，因此一定存在拓扑序列。
对于拓扑序列是否唯一，试举一例：设有向图，则存在两个拓扑序列，因此该图存在可能不唯一的拓扑序列。
结论：对于任一有向图，如果它的邻接矩阵中对角线以下(或以上)的元素均为零，则存在拓扑序列(可能不唯一)。
反正，若图存在拓扑序列，却不一定能满足邻接矩阵中主对角线以下的元素均为零，但是可以通过适当地调整结点编号，使其邻接矩阵满足前述性质。
13.对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是()。
（分数：2.00）A.3，1，2，4，5，6B.3，1，2，4，6，5C.3，1，4，2，5，6D.3，1，4，2，6，5 √解析：解析：按照拓扑排序的算法，每次都选择入度为0的结点从图中删去，此图中一开始只有结点3的入度为0；删掉结点3后，只有结点1的入度为0；删掉结点1后，只有结点4的入度为0；删掉结点4后，结点2和结点6的入度都为0，此时选择删去不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为3，1，4，2，6，5和3，1，4，6，2，5，选D14.下列AOE网表示一项包含8个活动的工程。
通过同时加快若干活动的进度可以缩短整个工程的工期。
下列选项中，加快其进度就可以缩短工程工期的是_______（分数：2.00）A.c和eB.d和cC.f和d √D.f和h解析：解析：找出AOE网的全部关键路径为(b、d、c、g)、(b、d、e、h)和(b、f、h)。
根据定义，只有关键路径上的活动时间同时减少时，才能缩短工期，即正确选项中的两条路径必须涵盖在所有关键路径之中。
利用关键路径算法可求出图中的关键路径共有三条：(b、d、c、g)、(b、d、e、h)和(b、f、h)。
由此可知，选项A和B中并不能包含(b、f、h)这条路径，选项c中，并不能包含(b、d、c、g)和(b、d、e、h)这两条路径，只有C包含了所有的关键路径，因此只有加快f和d的进度才能缩短工期。
15.已知一个长度为16的顺序表L，其元素按关键字有序排列。
若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多的是_______。
（分数：2.00）A.4B.5 √C.6D.7解析：解析：折半查找法在查找成功时进行的关键字比较次数最多为log 2n」+1，即判定树的高度；折半查找法在查找不成功时进行的关键字比较次数最多为log 2 n」+1。
题中n=16，因此最多比较log 2 16」+1=5次。
也可以画出草图求解。
16.下列选项中，不能构成折半查找中关键字比较序列的是_______。
（分数：2.00）A.500，200，450，180 √B.500，450，200，180C.180，500，200，450D.180，200，500，450解析：解析：画出查找路径图，因为折半查找的判定树是一棵二叉排序树，看其是否满足二叉排序树的要很显然，选项A的查找路径不满足。
二、综合应用题(总题数：7，分数：28.00)17.综合应用题41-47小题。
__________________________________________________________________________________________ 解析：18.已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)要求：1)写出图G的邻接矩阵A。
2)画出有向带权图G。
（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：1)由题得图G的邻接矩阵A如下图所示。
2)根据上面的邻接矩阵，画出有向带权图G)解析：已知含有5个顶点的图G 6.00）(1).写出图G的邻接矩阵A(行、列下标从0开始)。
（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：图G的邻接矩阵A)解析：解析：考查图的邻接矩阵的性质。
(2).求A 2，矩阵A 2中位于0行3列元素值的含义是什么?（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：A 2如下：0行3列的元素值3表示从顶点0到顶点3之间长度为2的路径共有3条。
