华中科技大学《834计算机专业基础综合(数据结构、计算机网络）》历年考研真题汇编.pdf

目录834计算机专业基础综合（数据结构、计算机网络）研究生入学考试大纲第一部分华中科技大学834计算机基础综合历年考研真题2017年华中科技大学834计算机专业基础综合（数据结构、计算机网络）考研真题及详解2018年华中科技大学834计算机专业基础综合（数据结构、计算机网络）考研真题（回忆版）第二部分计算机全国联考历年考研真题2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2011年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2014年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2015年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2016年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及参考答案2017年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及参考答案2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及参考答案834计算机专业基础综合（数据结构、计算机网络）研究生入学考试大纲数据结构部分（占60%）【考试范围】线性表（包括队列、堆栈等特殊线性表）的基本逻辑结构特征理解与应用；线性表（包括队列、堆栈等特殊线性表）的物理存贮结构；特殊矩阵的存贮及应用；树、图等非线性结构的基本逻辑结构特征理解与应用；树、图等非线性结构的物理存贮结构。排序与查找算法；一些算法的设计与时间复杂度分析。【具体内容】一、绪论1引言2什么是数据结构3相关基本概念和术语4算法的基本特征5算法分析相关概念二、线性表1线性表的概念，线性表的抽象数据类型，基本操作2线性表的顺序存储结构：静态分配，动态分配3顺序表的插入删除算法，移动元素次数分析4顺序存储结构的优缺点，引出单链表的结构类型定义5单链表的算法：生成先进先出单链表，后进先出单链表6单链表的算法：生成不带表头的递增有序单链表，生成带表头的递增有序单链表7单链表的算法：在指定位置插入一个新结点；删除指定值的结点；在指定位置删除一个结点；8单链表的合并：两个递增有序的单链表合并成一个递增有序的单链表9循环链表的概念，双向循环链表的概念，插入和删除结点10 多项式的链表表示，算法思想三、栈和队列1栈的相关概念与特性2顺序栈的基本操作3链式栈的基本操作4栈的应用5队列的相关概念6链式队列的基本操作7顺序队列的基本操作四、数组1抽象数据类型数组的说明2数组的物理结构3特殊矩阵的压缩存储：对称矩阵与三对角矩阵的压缩存储4稀疏矩阵的压缩存储：三元组顺序表与十字链表5稀疏矩阵的运算（转置算法）6广义表的概念：概念、物理结构、递归算法五、树与二叉树1树的有关概念2二叉树的定义与性质3二叉树的存储结构4二叉树的遍历5二叉树遍历的应用6树的存储结构7树与二叉树的相互转换8树与森林的遍历9哈夫曼树10 哈夫曼算法六、图1图的定义及术语2图的物理存贮结构：邻接矩阵、邻接表、十字链表和邻接多重表3图的遍历：深度优先搜索遍历与广度优先搜索遍历4图的连通性问题：DFS与BFS生成树、强连通分量的求解，最小生成树5有向无环图及应用：拓扑排序、关键路径6最短路径：迪杰斯特拉算法、弗洛伊德算法七、查找1查找问题概述2顺序查找法3折半查找法4分块查找法5二叉排序树查找法6平衡二叉排序树查找法7B树查找法和B树查找法8键树查找法9哈希查找法八、排序1查找问题概述、插入排序法2交换排序法3选择排序法4归并排序法5基数排序法计算机网络部分（占40%）【考试范围】重点考查计算机网络的构成和计算机网络核心的两种数据交换方法、计算机网络的层次化体系结构、计算机网络的性能度量指标、四种主流的因特网应用的工作原理（万维网/电子邮件/域名解析/P2P）、数据可靠传输的基本原理和方法、数据传输中流量控制和拥塞控制的基本原理和方法、计算机网络中的三种设备标识方式（域名/IP地址/MAC地址）及其映射关系、端口的概念和TCP/UDP的工作原理、IP协议和路由协议、共享信道的协调方法和以太网的工作原理、无线局域网的构成和基本工作原理等内容。【具体内容】一、计算机网络和因特网1计算机网络的构成和功能2因特网的接入方式3因特网核心的数据交换方式4计算机网络的层次模型及相关概念5OSI/RM模型和TCP/IP模型二、应用层1应用层协议的原理及网络应用模型2Web应用和HTTP协议3因特网中的电子邮件4域名服务DNS5P2P文件共享三、运输层1运输层的工作原理和提供的服务2多路复用与多路分解3UDP协议和TCP协议的报文结构和工作机制4可靠数据传输的基本原理及其在TCP协议中的应用5拥塞控制的基本原理及其在TCP协议中的应用6流量控制的基本原理及其在TCP协议中的应用四、网络层1网络层的工作原理及其提供的服务2虚电路和数据报网络的工作原理及对比3路由器的构成和工作原理4IP地址的分类、子网划分和CIDR的工作原理5IPv4分组结构及转发机制6NAT协议的工作原理和应用场景7ARP、DHCP和ICMP协议8选路算法：RIP、OSPF和BGP-49IP组播的概念和IP组播地址10 IPv6地址、数据报格式和邻居发现协议五、数据链路层和以太网1数据链路层的工作原理及其提供的服务2差错检测和纠错技术3多址访问协议的分类和工作原理4链路层的编址方式5以太网6集线器和交换机的工作原理7点对点协议PPP8虚拟局域网六、无线网络和移动网络1无线网络的概念、组成、分类和工作原理2无线链路和网络特征3802.11无线局域网的工作原理4无线局域网中的多址访问协议5移动IP第一部分华中科技大学834计算机基础综合历年考研真题2017年华中科技大学834计算机专业基础综合（数据结构、计算机网络）考研真题及详解2018年华中科技大学834计算机专业基础综合（数据结构、计算机网络）考研真题（回忆版）数据结构部分一、选择题（共10道，一个2分，共20分）1数据结构的逻辑结构分类是哪两种？2给定一颗完全二叉树的结点数，求其中的叶节点个数3一个有n个结点的图构成一个邻接矩阵几乘几的矩阵410暂缺二、简答题（共5道题，前四个15分，最后一个10分，今年没有编程题，也就是都是算法和推演，不用写代码，都是根据要求写结果和原理）1给了8个左右的数字的一个集合，比如75，63，43，要求一次读取一个，输出成一个二叉排序树，写出结果，并且求等概率情况下的平均查找长度。2给了一个包含有ABCDEFGH这几个点的二叉树的先序和中序排列，要求画出原二叉树。3一个指令集合I1，I2，I3，对应给出了每个指令对应的发生概率大小0.03，0.03，0.15，0.15，0.3，0.4（这个数字印象比较深基本差不多），让求出用此集合构成的哈夫曼树。求出他们的一个组织，并且求出每个指令的哈夫曼编码。4给出了一个由ABCDEFGHLM点组成的的无向带权图，让求出最小生成树（这里题干没有写用哪种算法）。5给定了一个树，转化成对应的二叉树，大概有8个点左右。计算机网络部分一、选择题（共10道，一个1分，共10分）1IPV4和IPV6的特征对比，选出一个错误的2TCP拥塞控制中慢开始算法的特征，选出一个错误的310暂缺二、填空题（共10道，一个1分，共10分）1IEEE802.11用的协议是_2CDMA2000采用的编码方式是_3移动IP的基本工作过程（给了其中3个步骤，填另一个）4信道划分的三种方式（给了其中2个，填另一个）510暂缺三、简答题（共7道，共40分）1主机A向主机B先后发两个报文，给出了每个报文的字节数，然后分别问了第一个先到的情况下和第二个报文先到的情况下各自的确认号，源，目的。2题目给了两个通信设备之间的RTT，L是要发送的信息的长度，S和R分别代表（忘了。），也是两问，分别求在4L/RS/R2L/R（第一个条件这里有个两个不等号隔开的三个地方有个地方是RTT的，记不清给到哪里了）和S/R4L/R两种情况下一端从开始发送信息开始到完全接收到并收到确认所用的总时间3左边给出一个路由表，有A到G总共7个表项，右边给出了6个IP地址，根据路由表求每个地址对应的下一跳4求一个带权图的从A到各个点的最短路径，画出来是一个表格（可以参考严蔚敏数据结构第七章图的应用举的例子，形式基本没区别）5给了一个网络的带权图（6个点左右），和其中两个个点的路由表，比如给了B和E的，让求另外三个点（比如A，D，F）的路由表，其中一个是固定路由，另外两个RIP路由。6分6一个路由器转发报文 第NS/R时刻有N个分组到达，一个报文最大是S，传输速率是R，求任一分组的平均等待时延？4分7（7分）暂缺第二部分计算机全国联考历年考研真题2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解一、单项选择题：140小题，每小题2分，共80分。下列每题给出的四个选项中。只有一个选项是最符合题目要求的。1为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A栈B队列C树D图B【答案】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。栈和队列是操作受限的线性表，栈具有先进后出的特性而队列具有先进先出的特性。由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数【解析】据缓冲区具有先进先出性，则它的逻辑结构应该是队列。2设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是（）。A1B2C3D4C【答案】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序。在本题中，每个元素出栈S后立即进入队列Q，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序。根据出栈顺序可以分析各个元素进出栈的过程：第一个出栈元素为b，表明栈内还有元素a，b出栈前的深度为2；第二个出栈元素为d，栈内元素为a和c，d出栈前的深度为3；c出栈后，剩余元素为a，c出栈前的深度为2；f出栈后，剩余元素为a和e，f出栈前的深度为3；e出栈后，剩余元素为a，e出栈前的深度为2；a出栈后，无剩余元素，a出栈前的深度为1；g出栈后，无剩余元素，g出栈前的深度为1。所以栈容量至少是3。【解析】3给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是（）。ALRNBNRLCRLNDRNLD【答案】对“二叉树”而言，一般有三条搜索路径：【解析】先上后下的按层次遍历；先左（子树）后右（子树）的遍历；先右（子树）后左（子树）的遍历。其中第1种搜索路径方式就是常见的层次遍历，第2种搜索路径方式包括常见的先序遍历NLR、中序遍历LNR、后序遍历LRN，第3种搜索路径方式则是不常使用的NRL、RNL、RLN。本题考查的是第3种搜索路径方式的一种情况。根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D。4下列二叉排序树中，满足平衡二叉树定义的是（）。B【答案】平衡二叉树是指左右子树高度差（平衡因子）的绝对值不超过1的二叉树。A项中根结点的平衡因子是2；B项中每个结点的平衡因子的绝对值均不超过1；C项中根结点的平衡因子是2；D项中根结点的平衡因子是3。【解析】5已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。A39B52C111D119C【答案】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层。题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度。根据题意，一棵完全二叉树的第6层（设根为第1层）有8个叶结点，可知此二叉树的高度是6或7。题目中求二叉树的结【解析】点数最多的情况，因此此完全二叉树的高度为7。由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是26163。又根据二叉树的性质1可知，题目中二叉树的第6层结点数是2532个结点，已知有8个叶子结点，那么其余32824个结点均为分支结点，这些结点在第7层上最多有48个子结点（即叶子结点）。所以此二叉树的结点数最多可达261（258）2111。6将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（）。父子关系兄弟关系u的父结点与v的父结点是兄弟关系A只有B和C和D、和B【答案】首先，在二叉树中，若结点u是结点v的父结点的父结点，那么u和v的关系有如下4种情况：【解析】接下来，根据森林与二叉树的转换规则，将这4种情况还原成森林中结点的关系。其中：情况（1），在原来的森林中u是v的父结点的父结点；情况（2），在森林中u是v的父结点；情况（3），在森林中u是v的父结点的兄弟；情况（4），在森林中u与v是兄弟关系。由此可知，题目中的、是正确的。7下列关于无向连通图特性的叙述中，正确的是（）。所有的顶点的度之和为偶数边数大于顶点个数减1至少有一个顶点的度为1A只有B只有C和D和A【答案】在图中，顶点的度TD（Vi）之和与边的数目满足关系式：【解析】其中，n为图的总结点数，e为总边数。因此，项正确。对于、项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。（1）（2）8下列叙述中，不符合m阶B树定义要求的是（）。A根结点最多有m棵子树B所有叶结点都在同一层上C各结点内关键字均升序或降序排列D叶结点之间通过指针链接D【答案】B树就是指B-树。根据B-树的定义，m阶B-树中每个结点最多有m个分支，因此，根结点最多有m棵子树，A项正确；B-树中所有叶结点都在最底层，位于同一层，B项正确；结点内各关键字互不相等且有序排列，C项正确。但是，所有叶子结点之间通过指针链接，是B树的定义，而B-树中没有。因此，D项是错误的。【解析】9已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。A3，5，12，8，28，20，15，22，19B3，5，12，19，20，15，22，8，28C3，8，12，5，20，15，22，28，19D3，12，5，8，28，20，15，22，19A【答案】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。【解析】10 若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）。A起泡排序B插入排序C选择排序D二路归并排序B【答案】经过两趟排序后，A项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B项插入排序的结果是前三个数有序即可；C项选择排序结果是两个最小的元素在最前面按顺序排好；D项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B项正确。【解析】11 冯诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是（）。A指令操作码的译码结果B指令和数据的寻址方式C指令周期的不同阶段D指令和数据所在的存储单元C【答案】在冯诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段（分析取数阶段、执行阶段）取出的是数据。所以，CPU区分指令和数据的依据是指令周期的不同阶段。【解析】12 一个C语言程序在一台32位机器上运行。程序中定义了3个变量x、Y和z，其中x和z为int型，Y为short型。当x127，Y9时，执行赋值语句zxY后，x、Y和z的值分别是（）。Ax0000 007FH，YFFFF FFF9H，z0000 0076HBx0000 007FH，YFFFF FFF9H，zFFFF 0076HCx0000 007FH，YFFFF FFF7H，zFFFF 0076HDx0000 007FH，YFFFF FFF7H，z0000 0076HD【答案】当两个不同长度的数据，要想通过算术运算得到正确的结果，必须将短字长数据转换成长字长数据，这被称为“符号扩展”。例如，x和z为int型，数据长32位，Y为short型，数据长16位，因此首先应将y转换成32位的数据，然后再进行加法运算。运算采用补码的形式，而x的补码是0000 007FH，Y的补码是FFFF FFF7H，所以xY00000076H。【解析】13 浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含2位符号位）。若有两个数X2729/32，Y255/8，则用浮点加法计算XY的最终结果是（）。A0011 1110 0010B0011 1010 0010C0100 0001 0001D发生溢出D【答案】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点在对阶、规格化、判溢出这三步。X和的阶码不同，所以应该先对阶，对阶原则为：小阶向大阶看齐。因此将Y对阶后得到：Y275/32，然后将尾数相加，得到尾数之和为：34/32。因为这是两个同号数相加，尾数大于1，则需要右规，阶码加1。由于阶码的位数为5位，且含两位符号位，即阶码的表示范围在87之间。而阶码本身等于7，再加1就等于8。因此，最终结果发生溢出。【解析】14 某计算机的Cache共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是（）。A0B2C4D6C【答案】首先根据主存地址计算所在的主存块号，然后根据组相联【解析】映射的映射关系KI mod Q（K代表Cache的组号，I代表主存的块号，Q代表Cache的组数）来计算Cache的组号。由于每个主存块大小为32字节，按字节编址，那么主存129号单元所在的主存块号是4，Cache共有16块，采用2路组相联映射方式（即每组2块），故Cache有8组，按照上面的公式可以计算得到Cache的组号4 mod 84。15 某计算机主存容量为64 KB，其中ROM区为4 KB，其余为RAM区，按字节编址。现要用2 K8位的ROM芯片和4 K4位的RAM芯片来设计该存储器，则需要上述规格的ROM芯片数和RAM芯片数分别是（）。A1、15B2、15C1、30D2、30D【答案】主存储器包括RAM和ROM两部分，由于ROM区为4KB，则RAM区为60KB。存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种。选用2K8位的ROM芯片，只需采用2片芯片进行字扩展便可得到4KB的ROM区；选用4K4位的RAM芯片，需采用（60）/4*2片芯片进行字和位同时扩展便可得60KB的RAM区。【解析】16 某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第1字节为操作码字段，第2字节为相对位移量字段。假定取指令时，每取一个字节PC自动加1。若某转移指令所在主存地址为2000H，相对位移量字段的内容为06H，则该转移指令成功转移后的目标地址是（）。A2006HB2007HC2008HD2009HC【答案】相对寻址方式的有效地址EA（PC）D，其中PC为程序计数器，D为相对偏移量。主存按字节编址，取指令时，每取一个字节PC值自动加1。由于转移指令由两个字节组成，取出这条转移指令之后的PC值自动加2，为2002H，故转移的目标地址为2002H06H2008H。【解析】17 下列关于RISC的叙述中，错误的是（）。ARISC普遍采用微程序控制器BRISC大多数指令在一个时钟周期内完成CRISC的内部通用寄存器数量相对CISC多DRISC的指令数、寻址方式和指令格式种类相对CISC少A【答案】B项、C项、D项都是RISC的特点之一，所以它们都是正确的，只有A项是CISC的特点，因为RISC的速度快，所以普遍采用硬布线控制器，而非微程序控制器。【解析】18 某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为90ns、80ns、70ns和60ns，则该计算机的CPU时钟周期至少是（）。A90nsB80nsC70nsD60nsA【答案】对于各功能段执行时间不同的指令流水线，计算机的CPU时钟周期应当以最长的功能段执行时间为准。【解析】19 相对于微程序控制器，硬布线控制器的特点是（）。A指令执行速度慢，指令功能的修改和扩展容易B指令执行速度慢，指令功能的修改和扩展难C指令执行速度快，指令功能的修改和扩展容易D指令执行速度快，指令功能的修改和扩展难D【答案】在同样的半导体工艺条件下，硬布线（组合逻辑）控制器的速度比微程序控制器的速度快。这是因为硬布线控制器的速度主要取决于逻辑电路的延迟，而微程序控制器增加了一级控制存储器，执行的每条微指令都要从控制存储器中读取，影响了速度。由于硬布线控制器一旦设计完成就很难改变，所以指令功能的修改和扩展难。因此，硬布【解析】线控制器的特点是指令执行速度快，指令功能的修改和扩展难。20 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz，则总线带宽是（）。A10MB/sB20MB/sC40MB/sD80MB/sB【答案】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送。总线时钟频率为10MHz，时钟周期为0.1s，总线周期占用2个时钟周期，为0.2s。一个总线周期中并行传输4字节信息，则总线带宽是4B0.2s 20MB/s。【解析】21 假设某计算机的存储系统由Cache和主存组成。某程序执行过程中访存1000次，其中访问Cache缺失（未命中）50次，则Cache的命中率是（）。A5%B9.5%C50%D95%D【答案】Cache的命中率HN1/（N1N2），其中N1为访问Cache的次数，N2为访存主存的次数，程序总访存次数为N1N2，程序访存次数减去失效次数就是访问Cache的次数N1，。所以根据公式可得：H（100050）/100095%。【解析】22 下列选项中，能引起外部中断的事件是（）。A键盘输入B除数为0C浮点运算下溢D访存缺页A【答案】所谓外部中断是指由外部事件引起的中断，在这4个选项中，只有键盘输入是真正由外部事件引起的中断。【解析】23 单处理机系统中，可并行的是（）。进程与进程处理机与设备处理机与通道设备与设备A、和B、和C、和D、和D【答案】注意区分并发和并行。在单处理机系统中，进程只能并发。微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的。通道是独立于CPU控制的输入/输出的设备，处理机与通道两者是可以并行。显然，设备和设备之间也是可以并行的。【解析】24 下列进程调度算法中，综合考虑进程等待时间和执行时间的是（）。A时间片轮转调度算法B短进程优先调度算法C先来先服务调度算法D高响应比优先调度算法D【答案】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间。最高响应比优先调度算法是最先执行响应比最高的进程（响应比1等待时间/估计运行时间）。该算法综合了先来先服务（FCFS）和短作业优先（SJF）算法，FCFS只考虑每个作业的等待时间，而未考虑执行时间的长短。SJF只考虑执行时间的长短，而未考虑等待时间的长短，HRRN算法则同时考虑执行时间和等待时间。【解析】25 某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K最小值是（）。A2B3C4D5C【答案】死锁的抽屉原理一般描述是：将5个苹果放进4个抽屉，那么，必然有1个抽屉中至少有2个苹果。计算机系统的资源分配充分体现了这一原理。考察进程运行的特点，只要有一个进程能够运行，则运行结束后必然会归还资源，其余的进程也就会得到满足从而可以执行（这里考虑的资源主要是可重用的资源，不可重用的资源会消失，就不可用上述方法分析）。所以最少需要4个进程竞争使用，每个进程占用2台打印机，此时会产生死锁。【解析】26 分区分配内存管理方式的主要保护措施是（）。A界地址保护B程序代码保护C数据保护D栈保护A【答案】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可【解析】越界，因此需要进行界地址保护。通常的界地址保护方法采用软硬件结合的方法。考生要注意本题与虚拟存储方法的区别。27 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（）。A28字节B216字节C224字节D232字节C【答案】段内位移的最大值就是最大段长。段号长度占了8位，剩下32824位是段内位移空间，因此最大段长为224B。【解析】28 下列文件物理结构中，适合随机访问且易于文件扩展的是（）。A连续结构B索引结构C链式结构且磁盘块定长D链式结构且磁盘块变长B【答案】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问。链式结构的优点是文件易于扩展，缺点是不易随机访问。【解析】索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展。29 假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求，序列为35，45，12，68，110，180，170，195，采用SCAN调度（电梯调度）算法得到的磁道访问序列是（）。A110，170，180，195，68，45，35，12B110，68，45，35，12，170，180，195C110，170，180，195，12，35，45，68D12，31，45，68，110，170，180，195A【答案】SCAN算法类似电梯工作原理，即朝一个固定方向前进，经过的磁道有访问请求则马上服务，直至到达一端顶点，再掉头往回移动以服务经过的磁道，并这样在两端之间往返。因此，当磁头从105道向序号增加的方向移动时，便会服务所有大于105的磁道号（从小到大的顺序）；往回返时又会按照从大到小的顺序进行服务。注意与循环扫描算法的区别，所以SCAN算法的访问序列是：110，170，180，195，68，45，35，12。【解析】30 文件系统中，文件访问控制信息存储的合理位置是（）。A文件控制块B文件分配表C用户口令表D系统注册表A【答案】文件控制块是文件存在的标志，文件的相关信息（基本信息、存取控制信息以及使用信息）都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息。【解析】31 设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2，再建立F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是（）。A0、1B1、1C1、2D2、1B【答案】为了使文件实现共享，通常在使用该形式文件系统的文件索引节点中设置一个链接计数字段，用来表示链接到本文件的用户目录项的数目（引用计数值），这是共享的一种方法。当新文件建立时，一般默认引用计数值为1。硬链接可以看作是已存在文件的另一个名字，新文件和被链接文件指向同一个节点，引用计数值加1。当删除被链接文件时，只是把引用计数值减1，直到引用计数值为0时，才能真正删除文件。软链接又叫符号链接，在新文件中只包含了被链接文件的路径名，新文件和被链接文件指向不同的节点。建立软链接文件时，文件的【解析】引用计数值不会增加。在这种方式下，当被链接文件删除时，新文件仍然是存在的，只不过是不能通过新文件的路径访问被链接文件而已。因此，在本题中，当建立F2时，F1和F2的引用计数值都为1。当再建立F3时，F1和F3的引用计数值就都变成了2。当后来删除F1时，F3的引用计数值为211。F2的引用计数值仍然保持不变，所以F2和F3的引用计数值分别是：1，1。32 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（）。A逻辑设备名B物理设备名C主设备号D从设备号A【答案】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等。而操作系统内部管理设备使用的是设备编号。【解析】33 在OSI参考模型中，自下而上第一个提供端到端服务的层次是（）。A数据链路层B传输层C会话层D应用层B【答案】题目中指明了这一层能够实现端到端传输，也就是端系统到端系统的传输，数据链路层主要负责传输路径上相邻结点间的数据交付，这些结点包括了交换机和路由器等数据通信设备，这些设备不能被称为端系统，因此数据链路层不满足题意。题目中指明了这一层能够实现传输，会话层只是在两个应用进程之间建立会话而已，应用层只是提供应用进程之间通信的规范，都不涉及传输。所以本题答案应该是B项。在OSI模型中网络层提供的是主机到主机的通信服务。【解析】34 在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是（）。A12 kbpsB24 kbpsC48 kbpsD96 kbpsB【答案】首先要根据信道有无噪声来确定是否采用奈奎斯特定理。解题难点在于离散数值的确定，先确定调制技术的码元数，此处为4个相位乘以4种振幅，共16种，即该通信链路的最大数据传输速率23log 2（44）6424kbps。【解析】35 数据链路层采用后退N帧（GBN）协议，发送方已经发送了编号为07的帧。当计时器超时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（）。A2B3C4D5C【答案】后退N帧协议，即GO-BACKN策略的基本原理是，当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧；或者当发送方发送了N个帧后，若发现该N帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就不得不重新发送出错帧及其后的N帧。本题收到3号帧的确认，说明0，1，2，3号帧已经收到，丢失的是4，5，6，7号帧，共4帧。因此答案为C项。【解析】36 以太网交换机进行转发决策时使用的PDU地址是（）。A目的物理地址B目的IP地址C源物理地址D源IP地址A【答案】交换机会监测发送到每个端口的数据帧，通过数据帧中的有关信息（源结点的MAC地址、目的结点的MAC地址），就会得到与每个端口所连接结点的MAC地址，并在交换机的内部建立一个“端口-MAC地址”映射表。建立映射表后，当某个端口接收到数据帧后，交换机会读取出该帧中的目的结点的MAC地址，并通过“端口-MAC地址”的对应关系，迅速将数据帧转发到相应的端口，注意这里的交换机工作在数据链路层，因此关于IP地址的选项是不对的，因此答案为A。【解析】37 在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps，电缆中的信号传播速度是200000km/s。若最小数据帧长度减少800bit，则最远的两个站点之间的距离至少需要（）。A增加160mB增加80mC减少160mD减少80mD【答案】以太网采用CSMA/CD访问协议，在发送的同时要进行冲突检测，这就要求在能检测出冲突的最大时间内数据包不能够发送完毕，否则冲突检测不能有效地工作。所以，当发送的数据包太短时必须进行填充。最小帧长度碰撞窗口大小报文发送速率，本题最小数据帧长度减少800b，那么碰撞的窗口也要减少，因此距离也要减少，从而（8002108）/（1109）160m，由于时间延时存在两倍的关系，因此减少的距离为80m。【解析】38 主机甲和主机乙间已建立一个TCP连接，主机甲向主机乙发送了两个连续的TCP段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是（）。A500B700C800D1000D【答案】TCP使用滑动窗口流控协议，窗口大小的单位是字节，本题中分别包含300字节和500字节的有效载荷，第一个段的序列号为200，那么确认序列号为2003005001000。【解析】39 一个TCP连接总是以1KB的最大段发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时，如果接下来的4个RTT（往返时间）时间内的TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是（）。A7KBB8KBC9KBD16KBC【答案】回顾TCP流量控制和拥塞控制（慢启动）的知识点，从第一个MSS开始，每次发送成功，拥塞窗口值翻倍，四次以后，应该为16，但是由于拥塞阈值变为16/28，故三次成功后为8，以后为线性增长，故为819，答案为C。【解析】40 FTP客户和服务器间传递FTP命令时，使用的连接是（）。A建立在TCP之上的控制连接B建立在TCP之上的数据连接C建立在UDP之上的控制连接D建立在UDP之上的数据连接A【答案】对于FTP，为了保证可靠性，选择TCP。FTP应用需要建立两条TCP连接：一条为控制连接，另一条为数据连接。FTP服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII形式表示的。【解析】二、综合应用题：4147小题。共70分。41（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点；选择离最近且尚未在最短路径中的顶点，加入到最短路径中，修改当前顶点；重复步骤，直到是目标顶点时为止。请问上述方法能否求得最短路径？若该方法可行，请证明之；否则请举例说明。解：题目中方法不一定能（或不能）求得最短路径。举例说明：图（a）中，假设初始顶点1到目标顶点4之间有一条边，权值x2。显然图（a）中这顶点1和顶点4之间的最短路径长度为2。若按照题目中给定的方法找到的路径为初始顶点1经过中间结点2、3到目标顶点4，即初始顶点123一目标顶点4，所经过的边的权值分别为y11、y21、y31。显然，y1y2y33大于2。因此按照题目中给定的方法所求得的路径并不是这两个顶点之间的最短路径。图（b）中，假设初始顶点为1、目标顶点为4，欲求从顶点1到顶点4之间的最短路径。显然，按照题目中给定的方法无法求出顶点1到顶点4的路径，而事实上顶点1到顶点4的最短路径为1到4。42（15分）已知一个带有表头结点的单链表，结点结构为，假设该链表只给出了头指针1ist。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：（1）描述算法的基本设计思想；（2）描述算法的详细实现步骤；（3）根据设计思想和实现步骤，采用程序设计语言描述算