作者：圣才学习网
出版社：圣才教育
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
谢希仁《计算机网络》（第5版）配套题库【名校考研真题＋课后习题＋章节题库＋模拟试题】试读：
第一部分 名校考研真题
2015年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合题目要求。请在答题卡上将所选项的字母涂黑。
1．已知程序如下：
int S（int n）
{
return （n<＝0） ? 0 : s（n-1）+n;
}
void main（）
{
cout< } 程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（ ）。 A．main（）->S（1）->S（0） B．S（0）->S（1）->main（） C．main（）->S（0）->S（1） D．S（1）->S（0）->main（）【答案】A【解析】函数S（int n）是一个递归函数：①当实际参数小于等于零时则返回0，并终止递归；②当实际参数大于零时则递归调用S（n-1），并将S（n-1）的结果加上n作为返回值。程序从main（）函数开始，首先调用main（）函数；在main（）函数中调用S（1）函数时，将main（）函数的上下文保存到栈中，并进入函数S（1）；由于函数S（1）的实际参数大于零，需要调用S（0），故将S（1）函数的上下文保存到栈中，进入S（0）；在S（0）中，实际参数小于等于零，递归终止。 2．先序序列为a，b，c，d的不同二叉树的个数是（ ）。 A．13 B．14 C．15 D．16【答案】B【解析】二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。本题中，结点a为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bcd为右子树；②b为左子树，cd为右子树；③bc为左子树，d为右子树；④bcd为左子树，右子树为空。然后将左右子树继续分解，如第①种情况的右子树先序遍历（bcd）可能有：a．左子树为空，右子树为cd；b．左子树为c，右子树为d；c．左子树为cd，右子树为空。按照这种方法继续分解左右子树，直到不能再分解为止，可得第①和④种情况各包含5种不同情况，第②和③种情况各包含2种情况，因此总共有14种不同的二叉树。 3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是（ ）。 A．24，10，5和24，10，7 B．24，10，5和24，12，7 C．24，10，10和24，14，11 D．24，10，5和24，14，6【答案】D【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中，第二个被访问的两个结点的权值要么相等，要么和为根节点的权值，故B项错误。同理，通过第三个被访问的节点排除A项。C项，由两条路径可推出三个叶子节点的权值分别是：3、10和11，而根据哈夫曼树的定义可知，权值为3的节点应该和权值为10的结点结合，故C项错误。D项，反推出有四个叶子节点，权值分别为：5、5、6和8，满足哈夫曼树的条件。 4．现在有一颗无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。 A．根节点的度一定为2 B．树中最小元素一定是叶节点 C．最后插入的元素一定是叶节点 D．树中最大元素一定是无左子树【答案】D【解析】二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：①中序遍历左子树；②访问根节点；③中序遍历右子树”。A项错误，当树中仅有一个或者两个结点时，根节点的度就可能不为2；B项错误，树中最小元素是中序遍历时最后访问的节点，当没有右子树时，最后访问的节点是根节点；C项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间节点；D项正确，由中序遍历的特点可知，左子树的值大于根节点，所以最大元素一定没有左子树。 5．设有向图G＝（V，E），顶点集V＝{V0，V1，V2，V3}，边集E＝{ A．2 B．3 C．4 D．5【答案】D【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可能得到的不同遍历序列分别是：①V0→V2→V1→V3；②V0→V2→V3→V1；③V0→V1→V3→V2；④V0→V3→V2→V1；⑤V0→V3→V1→V2。 6．暂缺 7．下列选项中，不能构成折半查找中关键字比较序列的是（ ）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450【答案】A【解析】折半查找的过程是：先确定待查找记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足：对每一个关键字，其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A项错误，第三次比较的关键字为450，说明待查关键字位于200～450间，所以第四次比较时不会遇到关键字180。 8．已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s[i]!＝t[i]）时，i＝j＝5，则下次开始匹配时，i和j的值分别是（ ）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2【答案】C【解析】模式匹配（KMP）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为S）的指针（i）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t）向右“滑动”尽可能远的一段距离后，继续进行比较。模式串“滑动”的距离是由模式串（t）本身决定的，即t的子串t[0…j-1]中前缀串和后缀串相等的最长长度。本题中第一次失配i＝5，字串为“abaab”，其相等且最长的前后缀为“ab”，一次下一个j＝2。 9．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。 A．直接插入排序 B．起泡排序 C．基数排序 D．快速排序【答案】C【解析】C项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n（n-1）/2次（n为元素个数）。 10．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是（ ）。 A．1 B．2 C．3 D．4【答案】C【解析】堆排序中，依次输出堆顶的最小值，然后重新调整堆，如此反复执行，便得到一个有序序列。本题中，删除堆顶元素8后将最后一个元素12置于堆顶，然后调整堆：首先与15比较，12小于15，所以不用交换；然后与10比较，因为10小于12，所以交换10和12的位置；调整后12再与16比较，12小于16，调整堆过程结束。因此12共与15、10、16进行了三次比较。 11．希尔排序的组内排序采用的是（ ）。 A．直接插入排序 B．折半插入排序 C．快速排序 D．归并排序【答案】A【解析】希尔排序基本思想是：先将整个待排元素序列按某个增量分割成若干个子序列，在子序列内进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。 12．计算机硬件能够直接执行的是（ ）。 Ⅰ．机器语言程序 Ⅱ.汇编语言程序 Ⅲ.硬件描述语言程序 A．仅Ⅰ B．仅Ⅰ Ⅱ C．仅Ⅰ Ⅲ D．ⅠⅡ Ⅲ【答案】A【解析】机器语言是计算机唯一可以直接执行的语言。汇编语言属于低级语言，但其源程必须要翻译成目标程序成为机器语言程序后才能被直接执行。硬件描述语言是电子系统硬件行为描述、结构描述、数据流描述的语言。 13．由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（ ）。 A．-126 B．-125 C．-32 D．-3【答案】B【解析】能表示的最小整数一定是负数，符号位占用1个“1”；负数的补码和原码的转化是：原码符号位不变，数值部分按位取反，末位加“1”。因此最小的整数的补码是“10000011”，原码为“11111101”，即-125。10 14．下列有关浮点数加减运算的叙述中，正确的是（ ）。 Ⅰ．对阶操作不会引起阶码上溢或下溢 Ⅱ．右规和尾数舍入都可能引起阶码上溢 Ⅲ．左规时可能引起阶码下溢 Ⅳ．尾数溢出时结果不一定溢出 A．仅Ⅱ Ⅲ B．仅ⅠⅡ Ⅳ C．仅ⅠⅢ Ⅳ D．ⅠⅡ Ⅲ Ⅳ【答案】D【解析】浮点数的加减运算步骤包括：①对阶，使两个操作数的小数点位置对齐，阶码小的尾数右移，可能产生溢出，但是阶码不会溢出；②尾数求和，将对阶后的尾数按定点数加（减）运算规则运算；③规格化，包括左规和右规，左规时阶码减少，可能出现阶码下溢，而右规时，阶码增加可能出现阶码上溢；④舍入，该过程可能需要右规调整，因此可能出现阶码上溢；⑤溢出判断，浮点数的溢出与否是由阶码的符号决定的，而不是由尾数溢出判断的，因此尾数溢出时结果不一定溢出。因此ⅠⅡ Ⅲ Ⅳ均正确。 15．假定主存地址为32位，按字节编址，主存和Cache之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（Write Back）方式，则能存放4K字数据的Cache的总容量的位数至少是（ ）。 A．146k B．147K C．148K D．158K【答案】B【解析】Cache和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个块和缓存块容量相同；主存中某块只能映象到Cache的一个特定的块中。本题中，Cache总共存放4K字数据，块大小为4个字，因此cache被分为4K/4 ＝ 1K个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-14＝18 位。所以，Cache的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容量为：（4*32 + 18 + 1）*1K ＝ 147K。 16．假定编译器将赋值语句“x＝x+3；”转换为指令”add xaddt，3”，其中xaddt是x对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB，且Cache使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（ ）。 A．0 B．1 C．2 D．3【答案】C【解析】采用页式虚拟存储管理方式时，若页表全部放在内存中，则存取一个数据最少要访问两次内存：第一次是访问页表，得到所存取的数据或指令的物理地址；第二次根据该地址存取数据或指令。在配有TLB的页式虚拟管理方式中，如果给出的地址在TLB中，则直接根据该地址取数据或指令，仅需要一次访问内存。Cache使用直写方式时，计算完需要将数据写回到内存中，因此完成整个指令功能至少需要访问主存2次。 17．下列存储器中，在工作期间需要周期性刷新的是（ ）。 A．SRAM B．SDRAM C．ROM D．FLASH【答案】B【解析】动态随机存储器（DRAM）是利用存储元电路中栅极电容上的电荷来存储信息的，电容上的电荷一般只能维持1～2ms，因此即使电源不掉电，信息也会自动消失。为此，每隔一定时间必须刷新。 18．某计算机使用4体交叉存储器，假定在存储器总线上出现的主存地址（十进制）序列为8005，8006，8007，8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲突的地址对是（ ）。 A．8004、8008 B．8002、8007 C．8001、8008 D．8000、8004【答案】D【解析】交叉存储器，又称低位交叉编址，即低位地址为体号，高位地址为体内地址。本题中，主存地址对应的体号分别是：1，2，3，4，1，2，3，4，4。地址为8004和8000都是存取的四号储存器，可能导致8004存储还未完成而又存取8000地址，因此可能发生缓存冲突。 19．下列有关总线定时的叙述中，错误的是（ ）。 A．异步通信方式中，全互锁协议最慢 B．异步通信方式中，非互锁协议的可靠性最差 C．同步通信方式中，同步时钟信号可由多设备提供 D．半同步通信方式中，握手信号的采样由同步时钟控制【答案】C【解析】A项正确，异步通信方式中，全互锁协议最慢，主从模块都需要等待确认后才能撤销其信号；B项正确，异步通信方式中，非互锁协议没有相互确认机制，因此可靠性最差；C项错误，同步通信要遵循统一的时钟信号，不能由多设备提供；D项正确，半同步通信方式中，握手信号的采样由同步时钟控制。 20．若磁盘转速为7200转/分，平均寻道时间为8ms，每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是（ ）。 A．8.1ms B．12.2ms C．16.3ms D．20.5ms【答案】B【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms，平均等待时间与磁盘转速有关，为[60s/7200]*0.5 ≈4.165ms。磁盘的存取一个扇区的时间为60s/（7200 * 1000） ≈ 0.0083ms。因此总的时间为：8 + 4.165 + 0.0083 ＝ 12.1733ms。 21．在采用中断I/O方式控制打印输出的情况下，CPU和打印控制接口中的I/O端口之间交换的信息不可能是（ ）。 A．打印字符 B．主存地址 C．设备状态 D．控制命令【答案】B【解析】I/O接口的功能包括：①选址功能；②传送命令功能；③传送数据功能；④反映I/O设备工作状态功能。A项为数据，C项为设备状态，D项为命令。B项，主存地址在中断方式控制下是不需要的，因此，它不可能是CPU和打印控制接口中的I/O端口之间交换的信息。 22．内部异常（内中断）可分为故障（fault）、陷阱（trap）和终止（abort）三类。下列有关内部异常的叙述中，错误的（ ）。 A．内部异常的产生与当前执行指令相关 B．内部异常的检测由CPU内部逻辑实现 C．内部异常的响应发生在指令执行过程中 D．内部异常处理后返回到发生异常的指令继续执行【答案】D【解析】内中断分为：①由软中断指令启动的中断；②在一定条件下由CPU自身启动的中断。D项错误，如突然掉电引发的内中断经处理后不会继续执行。 23．处理外部中断时，应该由操作系统保存的是（ ）。 A．程序计数器（PC）的内容 B．通用寄存器的内容 C．快表（TLB）的内容 D．Cache中的内容【答案】B【解析】外部中断处理过程首先要保护现场，使得中断处理完后能够恢复程序的状态继续执行。保护现场有两个含义：①由中断隐指令保存程序的断点（程序计数器）；②由中断服务程序保存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。 24．假定下列指令已装入指令寄存器。则执行时不可能导致CPU从用户态变为内核态（系统态）的是（ ）。 A．DIV R0，R1；（R0）/（R1）→R0 B．INT n；产生软中断 C．NOT R0；寄存器R0的内容取非 D．MOV R0，addr；把地址处的内存数据放入寄存器R0中【答案】C【解析】A项，除法操作出现除数为零的情况时，会产生内中断，CPU切换为内核态进行中断处理；B项，直接产生中断，会切换到内核态；D项，addr出现非法地址，会出现中断，进而切换到内核态。 25．下列选项中会导致进程从执行态变为就绪态的事件是（ ）。 A．执行P（wait）操作 B．申请内存失败 C．启动I/0设备 D．被高优先级进程抢占【答案】D【解析】D项，被高优先级进程抢占，进程会由执行态变为就绪态。ABC三项，程序由于缺少资源而由执行态转为阻塞态。 26．若系统S1采用死锁避免方法，S2采用死锁检测方法，下列叙述中正确的是（ ）。 Ⅰ.S1会限制用户申请资源的顺序 Ⅱ.S1需要进行所需资源总量信息，而S2不需要 Ⅲ.S1不会给可能导致死锁的进程分配资源，S2会 A．仅Ⅰ Ⅱ B．仅Ⅱ Ⅲ C．仅Ⅰ Ⅲ D．Ⅰ Ⅱ Ⅲ【答案】C【解析】死锁避免的策略是：必须知道将来的资源需求，以寻找可能的安全允许顺序，如果不存在安全序列就阻塞；死锁检测的策略是：只要允许就分配资源，它指定期检查死锁是否已经发生，如果发生就通过剥夺解除死锁。两种方式都需要所需资源的总量信息，但S1是用于在分配资源时判断是否会导致死锁，而S2是用于检测是否出现死锁。 27．系统为某进程分配了4个页框，该进程已访问的页号序列为2，0，2，9，3，4，2，8，2，3，8，4，5，若进程要访问的下一页的页号为7，依据LRU算法，应淘汰页的页号是（ ）。 A．2 B．3 C．4 D．8【答案】B【解析】LRU置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框，题中访问过程中页框的变化如下： 序列： 2 0 2 9 3 4 2 8 2 3 8 4 5 页框： 2 2 0 0 0 2 9 3 3 4 4 2 3 0 2 2 2 9 3 4 4 8 2 3 8 9 9 3 4 2 8 2 3 8 4 3 4 2 8 2 3 8 4 5 淘汰： 0 9 2 访问页号为7的页时，内存中存在的页的页号是：3、8、4和5，根据LRU定义应淘汰的是3。 28．在系统内存中设置磁盘缓冲区的主要目的是（ ）。 A．减少磁盘I/O次数 B．减少平均寻道时间 C．提高磁盘数据可靠性 D．实现设备无关性【答案】A【解析】访问磁盘的开销远远大于访问内存的开销。磁盘缓冲区便是利用主存中的存储空间，来暂存从磁盘中读出（或写入）的信息，频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。 29．在文件的索引节点中存放直接索引指针10个，一级二级索引指针各1个，磁盘块大小为1KB。每个索引指针占4个字节。若某个文件的索引节点已在内存中，到把该文件的偏移量（按字节编址）为1234和307400处所在的磁盘块读入内存。需访问的磁盘块个数分别是（ ）。 A．1，2 B．1，3 C．2，3 D．2，4【答案】B【解析】文件的索引结点的直接索引指针有10个，因此直接索引的偏移量范围是0～2559，一级索引的偏移量范围是2560～65791，二级索引访问的偏移量范围是65792～45183907。偏移量1234可以通过直接索引得到在磁盘块的地址，因此需要一次访问，307400需要通过二级索引查找其在磁盘的位置，需要分别访问存放二级索引的两个索引块以及对应的数据块。 30．在请求分页系统中，页面分配策略与页面置换策略不能组合使用的是（ ）。 A．可变分配，全局置换 B．可变分配，局部置换 C．固定分配，全局置换 D．固定分配，局部置换【答案】C【解析】分配和置换策略有下面三个组合：①固定分配、局部置换；②可变分配、全局置换；③可变分配、局部置换。固定分配是指基于进程的类型（交互型或批处理型等），或根据程序员、程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间都不再改变，采用该策略时，如果进程在运行中发现缺页，则只能从该进程在内存的n个页面中选出一个页换出，然后再调入一页，才能保证分配给该进程的内存空间不变，因此不能有固定分配，全局置换组合。 31～40．暂缺 二、综合应用题：41～47小题，共70分。 41．（9分）用单链表保存m个整数，节点的结构为（data，link），且|data|＜n（n为正整数）。现要求设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。 例如若给定的单链表head如下 删除节点后的head为 要求（1）给出算法的基本思想（2）使用c或c++语言，给出单链表节点的数据类型定义。（3）根据设计思想，采用c或c++语言描述算法，关键之处给出注释。（4）说明所涉及算法的时间复杂度和空间复杂度。 答：（1）算法思想： 定义一个大小为n的布尔数组flag，初始时所有的元素都赋值为false，用来标识遍历过程中是否出现元素绝对值为flag的节点。然后遍历链表，遍历过程中，每一个当前结点data域的绝对值所对应的flag位：若为真，则删除该结点；若为假（false），则将flag位置为真（true）。（2）节点的数据结构定义如下：（3）bool flag[n]； //全局数组标志节点的绝对值是否出现过 Node * deleteABSEnqualNode（Node * head） { memset（flag, false, sizeof（flag））; Node *pre ＝ head; Node *p ＝ head->next; while（ p !＝ NULL ）{ if（ flag[ abs（p->data） ] ）{ //如果此绝对值已经在节点值的绝对值中出现过则删除该节点 pre->next ＝ p->next; delete p; p ＝ pre->next; } else {//否则，将flag中对应的位置置为true，并将指针指向下一个元素 flag[ abs（p->data） ] ＝ true; p ＝ p->next; } } return head; }（4）只遍历一次链表，所以时间复杂度为O（m）（m为单链表中元素的个数），申请大小为n的数组，所以空间复杂度为O（n）（n为节点绝对值的最大值）。 42．（11分）已知有5个顶点的图G如下图所示 请回答下列问题（1）写出图G的邻接矩阵A（行、列下标从0开始）。22（2）求A，矩阵A中位于0行3列元素值的含义是什么？m（3）若已知具有n（n>＝2）个顶点的邻接矩阵为B，则B（2<＝m<＝n）非零元素的含义是什么？ 答：（1）邻接矩阵为2（2）A为： 0行3列的元素的含义是顶点0到顶点3间是相通的，并且路径长度为2的路径有2条。m（3）B中非零元素的含义是：假设此顶点位于i行j列，表示从i结点到j结点路径长度为m的路径的条数。。 43．（12分）某16位计算机主存按字节编码。存取单位为16位；采用16位定长指令格式；CPU采用单总线结构，主要部分如下图所示。图中R0～R3为通用寄存器；T为暂存器；SR为移位寄存器，可实现直送（mov）、左移一位（left）、右移一位（right）3种操作，控制信号为Srop，SR的输出信号Srout控制；ALU可实现直送A（mova）、A加B（add）、A减B（sub）、A与B（and）、A或B（or）、非A（not）、A加1（inc）7种操作，控制信号为ALUop。 请回答下列问题。（1）图中哪些寄存器是程序员可见的？为何要设置暂存器T？（2）控制信号ALUop和SRop的位数至少各是多少？（3）控制信号Srout所控制部件的名称或作用是什么？（4）端点①～⑨中，哪些端点须连接到控制部件的输出端？（5）为完善单总线数据通路，需要在端点①～⑨中相应的端点之间添加必要的连线。写出连线的起点和终点，以正确表示数据的流动方向。（6）为什么二路选择器MUX的一个输入端是2？ 答：（1）图中程序员可见的寄存器有通用寄存器R0～R3和程序计数器PC；当执行算术或逻辑操作时，由于ALU本身是没有内部存储功能的组合电路，因此如要执行加法运算，被相加的两个数必须在ALU的两个输入端同时有效，因此设置暂存器T用于暂存数据总线发送的数据。【解析】程序员可见的寄存器包括：程序计数器、通用寄存器和状态寄存器。其他的IR、MAR和MDR等是CPU的内部工作寄存器，对程序员不可见。（2）ALUop和SRop的位数分别为3，2。【解析】ALU中共有7种命令，用三位即可区别表示，SR共有三种命令二位二进制即可表示。（3）Srout所控制的部件是状态字寄存器，用来存放ALU及CPU的指令状态。（4）须连接到控制部件的输出端端点有①②③⑤⑧。【解析】操作符命令，传输等都需要控制信号进行控制。（5）⑥→⑨，⑦→④。（6）数据宽度是16位，以字节编址，输入端是2是为了增加地址获取ALU的第二个操作数。 44．（10分）题43中描述的计算机，其部分指令执行过程的控制信号如如题44图a所示。题44图a部分指令控制信号 该机指令格式如题44图b所示，支持寄存器直接和寄存器间接两种寻址方式，寻址方式位分别为0和1，通用寄存器R0～R3的编号分别为0、1、2和3。题44图b指令格式 请回答下列问题。（1）该机的指令系统最多可定义多少条指令？（2）假定inc、shl和sub指令的操作码分别为01H、02H和03H，则以下指令对应的机器代码各是什么？ ①inc R1；R1+1→R1 ②shl R2，R1；（R1）<<1→R2 ③sub R3，（R1），R2；（（R1））–（R2）→R3（3）假定寄存器X的输入和输出控制信号分别为Xin和Xout，其值为1表示有效，为0表示无效（例如，PCout＝1表示PC内容送总线）；存储器控制信号为MEMop，用于控制存储器的读（read）和写（write）操作。写出题44图a中标号①⑧处的控制信号或控制信号的取值。（4）指令“sub R1，R3，（R2）”和“inc R1”的执行阶段至少各需要多少个时钟周期？ 答：（1）128【解析】支持两种寻址方式，使用1位标识，四个寄存器，使用2位标识，因此对于每一个操作数需要3位，每条指令三个操作数，一条指7令总共16位，因此剩余7位，所以可以定义2条指令。（2）①0240H，②0464H，③06EEH【解析】“inc R1；”中R1是直接寻址的单地址指令，代码是“0000001 001 000 000”，前面七位是操作码（01H），001是第一个操作数地址（R1）；“shl R2，R1；（R1）<<1→R2”中R1是间接寻址，R2是直接寻址，代码是“0000010 010 101 000”，前面七位是操作码（02H），010是第一个操作数地址（R2），101是第二个操作数地址；“sub R3，（R1），R2；（（R1））–（R2）→R3”中R1和R2是间接寻址，R3是直接寻址，代码是“000011 011 101 110”，前面七位是操作码（03H），011是第一个操作数地址（R3），101是第二个操作数地址，110是第三个操作数地址。（3）①0，②mov，③mova，④left，⑤read，⑥sub，⑦mov，⑧Srout。（4）至少各需要8和1个时钟周期。【解析】在一个时钟周期内CPU仅完成一个动作。 sub R1，R3，（R2）；（R3）–（（R2））→R1执行周期的微操作序列是： T0：R3→MAR T1：M（MAR）→MDR T2：MDR→R3 T3：R2→MAR T4：M（MAR）→MDR T5：MDR→MAR T6：M（MAR）→MDR T7：R3+MDR→R1 所以至少需要8个时钟周期。 inc R1；R1+1→R1执行周期的微操作序列是： T0：R1+1→R1 所以至少需要1个时钟周期。 45．（15分）有A、B两人通过信箱进行辩论，每人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中，设A的信箱最多放M个邮件，B的信箱最多放N个邮件。初始时A的信箱中有x个邮件（0< x < M），B中有y个（0 < y < N）。辩论者每取出一个邮件，邮件数减1.。 A、B两人操作过程： Code Begin A{ While（ TRUE ）{ 从A的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入B的信箱； } } B{ While（ TRUE ）{ 从B的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入A的信箱； } } Code End 当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。 当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。 请添加必要的信号量和P、V（或wait signed）操作，以实现上述过程的同步，要求写出完整过程，并说明信号量的含义和初值。 答：首先定义两个互斥信号量：mutexA和mutexB，初始时为1，分别用来实现对A的邮箱和B的邮箱的互斥使用；然后针对A的邮箱再定义两个信号量emptyA和fullA，初值分别为 M – x和x，分别表示信箱中仍能存放信的数量和已经存放的信的数量，同理设置emptyB和fullB，初值为N – y和 y。 初始代码： Semaphore mutexA ＝ 1， mutexB ＝ 1； Semaphore emptyA ＝ M – x，fullA ＝ x； Semaphore emptyB ＝ N – y,，fullB ＝ y； 通信代码： Code Begin A｛ while（ TRUE ） { P（ fullA ）; P（ mutexA ）; 从A的信箱中取出一个邮件； V（ mutexA ）; V（ emptyA ）; 回答问题并提出一个新问题； P（emptyB）; P（ mutexB ）; 将新邮件放入B的信箱； V（ mutexB ）; V（ fullB ）; } } B{ While（ TRUE ）{ P（ fullB ）; P（ mutexB ）; 从B的信箱中取出一个邮件； V（ mutexB ）; V（ emptyB ）; 回答问题并提出一个新问题； P（ emptyA ）; P（ mutexA ）; 将新邮件放入A的信箱； V（ mutexA ）; V（ fullA ）; } } Code End 46～47．暂缺 2014年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是符合题目要求的。
1．下列程常段的时间复杂度是（ ）
count＝0;
for（k＝1;k<＝n; k*2）
for（j＝1;j<＝n;j+1）
count++;
A．O（logn） 2
B．O（n）
C．O（nlogn） 22
D．O（n）【答案】C【解析】外部循环的退出条件是k>n，而对于k，每次循环都执行k＝k*2,所以循环次数为logn；内部循环的退出条件是j>n,对于j，每次循2环都执行j＝j+1，所以每次循环次数为n次。所以此程序段的时间复杂度为O（nlogn），即选C。2
2．假设栈初始为空，将中缀表达式转换为等价后缀表达式的过程中，当扫描到f时，栈中的元素依次是（ ）
A．
B．
C．
D．【答案】B【解析】中缀表达式转后缀表达式遵循以下原则：（1）遇到操作数，直接输出；（2）栈为空时，遇到运算符，入栈；（3）遇到左括号，将其入栈；（4）遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，
左括号不输出；（5）遇到其他运算符'+''-''*''/'时，弹出所有优先级大于或等于该运算符的栈顶
元素，然后将该运算符入栈；（6）最终将栈中的元素依次出栈，输出。
所以扫描到’/’，入栈‘描到’+’,由于’+’优先级比’/’低，所以将’/’弹出，’+’入栈；扫描到’*’,优先级比’+’高，入栈；扫描到’（‘,入栈;扫描到’-‘,将栈中优先级更高的’*’弹出，‘-’ 入栈;扫描到’*’,优先级比’-‘高，入栈。所以扫描到f的时候，栈中元素为：
3．循环两列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（ ）
A．队空：end1＝＝end2； 队满：end1＝＝（end2+1）modM
B．队空：end1＝＝end2; 队满：end2＝＝（end1+1）mod（M-1）
C．队空：end2＝＝（end1+1）modM ; 队满：end1＝＝（end2+1）modM
D．队空：end1＝＝（end2+1）modM; 队满：end2＝＝（end1+1）mod（M-1）【答案】A【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。
4．若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是（ ）
A．e,c
B．e,a
C．d,c
D．b,a【答案】D【解析】此二叉树的中序遍历序列为：debxac,由于节点x左右孩子都为空，所有进行中序线索化时，它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b和直接后继结点a，所以选D
5．将森林F转换为对应的二叉树T，F中叶结点的个数等于（ ）
A．T中叶结点的个数
B．T中度为1的结点个数
C．T中左孩子指针为空的结点个数
D．T中右孩子指针为空的结点个数【答案】C【解析】森林转化为对应的二叉树是‘孩子-兄弟’存储的，即左孩子指针指向当前节点的孩子节点，右孩子指针指向当前节点的兄弟节点，所以在T中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C
6．5个字符有如下4种编码方案，不是前缀编码的是（ ）
A．01,0000,0001,001,1
B．011,000,001,010,1
C．000,001,010,011,100
D．0,100,110,1110,1100【答案】D【解析】在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支表示字符‘0’，右分支表示字符‘1’，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。D选项中，编码110是编码1100的前缀，故不符合前缀编码的定义。
7．对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（ ）
A．3,1,2,4,5,6
B．3,1,2,4,6,5
C．3,1,4,2,5,6
D．3,1,4,2,6,5【答案】D【解析】拓扑排序方法如下:（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它；（2）从图中删去该顶点,并且删去从该顶点发出的全部有向边；（3）重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止。
对于此有向图进行拓扑排序所有序列为：3,1,4,6,2,5和3,1,4,2,6,5。所以选D
8．用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（ ）
A．存储效率
B．数列函数
C．装填（装载）因子
D．平均查找长度【答案】D【解析】哈希方法冲突会使在查找冲突的关键字时，还要根据冲突处理办法多次比较关键字，则直接影响了平均查找长度。
9．在一棵具有15个关键字的4阶B树中，含关键字的结点数最多是（ ）
A．5
B．6
C．10
D．15【答案】D【解析】m阶B树非根结点含关键字个数┌m/2┐ - 1 <＝ j <＝ m – 1。
4阶B树非根结点含关键字1～3个，所以要使关键字结点数量最多，那么每个结点只有一个关键字，一共有15个关键字那么最多有15个含有关键字的结点
10．用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）可能是（ ）
A．2
B．3
C．4
D．5【答案】B【解析】对于A，增量为2，那么9,4,7,20,15是一组，而它们是无序的，所以A错误
对于C，增量为4，那么9,7,15是一组，而它们是无序的，所以C错误
对于D，增量为5，那么9,8是一组，降序，1,20是一组，而它们是升序，所以D也错误。对于B，分为3组：9,13,20；1,7,23；4,8,15都是升序有序，所以B正确
11．下列选项中，不可能是快速排序第2趟排序结果的是（ ）
A．2,3,5,4,6,7,9
B．2,7,5,6,4,3,9
C．3,2,5,4,7,6,9
D．4,2,3,5,7,6,9【答案】C【解析】对于快速排序，每一趟都会使一个元素位于有序时的位置，而有序序列为2,3,4,5,6,7,9，与C进行对比，只有9位于它有序的时候的位置，显然不是第二趟快速排序的结果
12．程序P在机器M上的执行时间是20秒，编译优化后，P执行的指令数减少到原来的70%，而CPI增加到原来的1.2倍，则P在M上的执行时间是（ ）
A．8.4秒
B．11.7秒
C．14秒
D．16.8秒【答案】D【解析】20*0.7*1.2 ＝ 16.8
13．若x＝103,y＝-25,则下列表达式采用8位定点补码运算实现时，会发生溢出的是（ ）
A．x+y
B．-x+y
C．x-y
D．-x-y【答案】C【解析】8位定点补码能表示的数的范围为：-128～127
A结果为78，B结果为-128，D结果为-78都在此范围内，只有C结果128超过了8位定点补码能表示的数的范围，会发生溢出
14.float型整数据常用IEEE754单精度浮点格式表示，假设两个float型变量x和y分别在32为寄存器f和f中，若（f）＝CC900000H, 121（f）＝B0C00000H,则x和y之间的关系为：（ ）2
A．x B．x C．x>y且符号相同 D．x>y且符号不同【答案】A【解析】两个数对应的IEEE754的标准形式为；浮点数S阶码尾数1001 f11001 0000 0000 0000 0000 000010010110 f21100 0000 0000 0000 0000 00000001 将IEEE754单精度形式的二进制转化为浮点数公式为V＝（-1）^s*2^（E-Bias）*M 由于f1，f2的符号位都是1，所以f1，f2符号相同，而阶码上f1>f2，所以f1>f2，所以f1的绝对值比f2大，而他们都是负数，所以f1 15．某容量为256M的存储器，由若干4M*8位的DRAM芯片构成，该DRAM芯片的地址引脚和数据引脚总数是：（ ） A．19 B．22 C．30 D．36【答案】A【解析】DRAM地址线复用，4M为2的22次方，因此除2为11根，数据线8根。因此地址引脚和数据引脚总数为19根 16．采用指令Cache与数据Cache分离的主要目的是（ ） A．减低Cache的缺失损失 B．提高Cache的命中率 C．减低CPU平均访问时间 D．减少指令流水线资源冲突【答案】D【解析】指令流水线不会断流，预取过来的都是指令 17．某计算机有16个通用寄存器，采用32位定长指令字操作码字段（含寻址方式位）为8位，Store指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式，若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store指令中偏移量的取值范围是（ ） A．-32768～+32767 B．-32767～+32768 C．-65536～+65535 D．-65535～+65536【答案】A4，【解析】寄存器个数16＝2偏移量有32-8-4-4＝16位 指令编址方式如下所示：操作码源地址寄存器目的地址基址寄存器偏移量84416 16位补码取值范围为-32768～+32767，所以偏移量取值范围为-32768～+32767 18．某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微程序，各指令对应的微程序平均由4条微指令组成，采用断定法（下址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是：（ ） A．5 B．6 C．8 D．9【答案】C78【解析】32*4+2＝130，2＝128<130<2＝256，所以至少需要8位才能表示完130个地址。 19．某同步总线采用数据线和地址线复用方式。其中地址数据线有8根，总线时钟频率为66MHZ，每个时钟同期传送两次数据。（上升沿和下降沿各传送一次数据）该总线的最大数据传输率是（总线带宽）：（ ） A．132MB/S B．264MB/S C．528MB/S D．1056MB/S【答案】C【解析】总线带宽＝总线工作频率×（总线宽度/8），由于地址线与数据线复用，所以在两次数据传输过程中总线上数据一共传输了8次，那么总线带宽为66*8＝528，所以选C 20．一次总线事物中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元格读出或写入的个数，这种总线事务方式称为（ ） A．并行传输 B．串行传输 C．突发 D．同步【答案】C【解析】猝发数据传输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式 21．下列有关I/O接口的叙述中错误的是：（ ） A．状态端口和控制端口可以合用同一寄存器 B．I/O接口中CPU可访问寄存器，称为I/O端口 C．采用独立编址方式时，I/O端口地址和主存地址可能相同 D．采用统一编址方式时，CPU不能用访存指令访问I/O端口【答案】D【解析】采用统一编码方式，存储器和I/O端口共用统一的地址空间，不需要专用的I/O指令，任何对存储器数据进行操作的指令都可用于I/O端口的数据操作。所以D错误 22．某设备中断请求的相应和处理时间为100ns，每400ns发出一次中断请求，中断相应所容许的最长延迟时间为50ns，则在该设备持续工作过程中CPU用于该设备的I/O时间占整个CPU时间百分比至少是（ ） A．12.5% B．25% C．37.5% D．50%【答案】B【解析】每400ns响应一次中断并且用100ns进行处理，所以该设备的I/O时间占用CPU时间百分比为100/400＝25%,中断响应容许的延迟时间对此没有影响，属于干扰条件。 23．下列调整中，不可能导致饥饿现象的是（ ） A．时间片转移 B．静态优先及调度 C．非抢占式作业优先 D．抢占式短作业优先 【答案】A【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU使用时间，不会产生饥饿的现象，其余三个都会产生饥饿。 24．某系统有n台互斥使用的同类设备，3个并发进程需要3,4,5台设备，可确保系统不发生死锁的设备数n最小为（ ） A．9 B．10 C．11 D．12【答案】B【解析】2+3+4+1 ＝ 10 25．下列指令中，不能在用户态执行的是（ ） A．trap指令 B．跳转指令 C．后栈指令 D．关中断指令【答案】D【解析】关中断指令必须在和心态才能执行，trap指令可以在用户态下执行，执行了就转到和心态，跳转与退栈指令都是可以在用户态下执行的指令。 26．一个进程的读磁区操作完成后，操作系统针对该进程必做的是（ ） A．修改进程状态为就绪态 B．降低进程优先级 C．进程分配用户内存空间 D．增加进程的时间片大小【答案】A【解析】进程等待的I/O操作完成便会从等待状态转移到就绪状态。 27．现有容量为10GB的磁盘分区，磁盘空间以簇（cluster）为单位进行分配，簇的大小为4KB，若采用位图法管理该分区的空闲空间，即用一位（bit）标识一个簇是否被分配，则存放该位图所需簇的个数为（ ） A．80 B．320 C．80K D．320K 【答案】A20【解析】磁盘的簇的个数为：10GB/4KB＝2.5*2个 而一个簇的位示图能管理的簇的个数为：4KB*8＝32K20 所以需要簇的个数为2.5*2/32K ＝ 80个 28．下列措施中，能加快虚实地址转换的是1增大快表（TLB）2让页表常驻内存3增大交换区（ ） A．仅1 B．仅2 C．仅1,2 D．仅2,3【答案】C【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使cpu不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响 29．在一个文件被用户进程首次打开的过程中，操作系统需做的是（ ） A．将文件内容读到内存中 B．将文件控制块读到内存中 C．修改文件控制块中的读写权限 D．将文件的数据缓冲区首指针返回给用户进程【答案】B【解析】概念 30．在页式存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是（ ） Ⅰ．LRU算法 Ⅱ．FIFO算法 Ⅲ．OPT算法 A．仅Ⅱ B．仅ⅠⅡ C．仅ⅠⅢ D．仅Ⅱ Ⅲ【答案】A【解析】Belady现象只有FIFO算法才会出现 31．下列关于管道（Pipe）通信的叙述中，正确的是（ ） A．一个管道可实现双向数据传输 B．管道的容量仅受磁盘容量大小限制 C．进程对管道进行读操作和写操作都可以被阻塞 D．一个管道只能有一个读写进程或一个写进程对其操作【答案】C【解析】只有写进程才能对管道写入数据，读进程对管道进行读取数据，只能半双工通信，即某一时刻只能单向传输。管道为空，则读操作被堵塞，而如果有写操作对管道进行写的话那就要堵塞了。那么C正确 32．下列选项中，属于多级页表优点的是（ ） A．加快地址变换速度 B．减少缺页中断次数 C．减少页表项所占字节数 D．减少页表所占的连续内存空间【答案】D【解析】多级页表避免了把所有的页表一直保存在内存中 33．在OSI参考模型中，直接为会话层提供服务的是（ ） A．应用层 B．表示层 C．传输层 D．网络层【答案】C【解析】OSI参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。 34．某以太网拓扑及交换机当前转发表如下图所示，主机00-e1-d5-00-23-a1向主机00-e1-d5-00-23-c1发送1个数据帧，主机00-e1-d5-00-23-c1收到该帧后，向主机00-e1-d5-00-23-a1发送一个确认帧，交换机对这两个帧的转发端口分别是（ ） A．和 B．和 C．和 D．和目的地址端口00-e1-2d5-00-23-b1【答案】B【解析】第一次交换机没有00-e1-d5-00-23-c1的信息，只能选择从其他端口全部发送，同时记录这个数据报源MAC地址的信息00-e1-d5-00-23-a1,确认帧发送时已经有00-e1-d5-00-23-a1的信息了所以只用从1端口转发。 35．下列因素中，不会影响信道数据传输速率的是（ ） A．信噪比 B．频率宽带 C．调制速率 D．信号传播速度【答案】D【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。 36．主机甲与主机乙之间使用后退N帧协议（GBN）传输数据，甲的发送窗口尺寸为1000，数据帧长为1000字节，信道宽带为100Mbps，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间的单向传播延迟是50ms，则甲可以达到的最大平均数据传输速率约为（ ） A．10 Mbps B．20 Mbps C．80 Mbps D．100 Mbps【答案】C【解析】1000B*1000/（50*2ms）＝10MB＝80Mbps. 37．站点A、B、C通过CDMA共享链路，A、B、C的码片序列（chipping sequence）分别是（1,1,1,1）、（1，-1,1，-1）和（1，1,-1，-1），若C从链路上收到的序列是（2,0,2,0,0，-2,0，-2,0,2,0,2），则C收到A发送的数据是（ ） A．000 B．101 C．110 D．111【答案】B【解析】用A的码片与信息做内积运算 38．主机甲和乙已建立了TCP连接，甲始终以MSS＝1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB的确认段。若甲在t时刻发生超时时拥塞窗口为8KB，则从t时刻起，不再发生超时的情况下，经过10个RTT后，甲的发送窗口是（ ） A．10KB B．12KB C．14KB D．15KB【答案】A【解析】发送窗口是接受窗口和拥塞窗口的最小值，这里接收窗口总是10KB。拥塞窗口到那个时候是大于10KB的，取最小值。 39．下列关于UDP协议的叙述中，正确的是（ ） Ⅰ 提供无连接服务 Ⅱ 提供复用/分用服务 Ⅲ 通过差错校验，保障可靠数据传输 A．仅Ⅰ B．仅Ⅰ、Ⅱ C．仅Ⅱ、Ⅲ D．Ⅰ、Ⅱ、Ⅲ【答案】B【解析】UDP无连接创建，提供多路复用服务。虽然有差错检验，但是不能保证可靠数据传输，所以Ⅲ错误。 40．使用浏览器访问某大学Web网站主页时，不可能使用的协议是（ ） A．PPP B．ARP C．UDP D．SMTP【答案】D
试读结束[说明：试读内容隐藏了图片]