2018年全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构题库【历年

下载地址:http://free.100xuexi.com/Ebook/157116.html
目录                                                                                        封面
内容简介
目录
第1部分　历年真题
　2015年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
　2014年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
　2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
　2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
第2部分　章节题库
　第1章　绪　论
　第2章　线性表
　第3章　栈和队列
　第4章　树与二叉树
　第5章　图
　第6章　查　找
　第7章　排　序
第3部分　模拟试题
　全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合模拟试题及详解（一）
　全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合模拟试题及详解（二）

内容预览
第1部分　历年真题
2015年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合题目要求。请在答题卡上将所选项的字母涂黑。
1．已知程序如下：

程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（　　）。
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＝{0,v1>，0,v2>，0,v3>，1,v3>}，若从顶点v0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（　　）。
A．2
B．3
C．4
D．5
【答案】D查看答案
【解析】根据题意知，有向图的结构如图1所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可能得到的不同遍历序列分别是：①v0→v2→v1→v3；②v0→v2→v3→v1；③v0→v1→v3→v2；④v0→v3→v2→v1；⑤v0→v3→v1→v2。

图1 有向图
6．求如图2所示带权图的最小(代价)生成树时，可能是克鲁斯卡尔(Kruskal)算法第2次选中但不是普里姆(Prim)算法(从v4开始)第2次选中的边是（　　）。

图2带权图
A．（v1，v3）
B．（v1，v4）
C．（v2，v3）
D．（v3，v4）
【答案】C查看答案
【解析】Kruskal算法的核心思想是“归并边”，不断选取当前未被选取的权值最小的边。从v4开始，Kruskal算法选中的第一条边是（v1，v4），B选项错误。Kruskal算法第二次可能选中的边有（v1，v3），（v2，v3），（v3，v4）。Prim算法是“归并顶点”的算法，从v4开始，第一次选中的是（v1，v4），这样就已经有v1和v4两个顶点了，第二次选中的是与这两个顶点相连且权值最小的边，（v1，v3）和（v3，v4）都符合，只有（v2，v3）不可能是Prim算法第二次选中的边，所以选C项。
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≠t[j]）时，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，i=5（保持不变）。
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”，即-12510。
14．下列有关浮点数加减运算的叙述中，正确的是（　）。
Ⅰ．对阶操作不会引起阶码上溢或下溢
Ⅱ．右规和尾数舍入都可能引起阶码上溢
Ⅲ．左规时可能引起阶码下溢
Ⅳ．尾数溢出时结果不一定溢出
A．仅Ⅱ、Ⅲ
B．仅Ⅰ、Ⅱ、Ⅳ
C．仅Ⅰ、Ⅲ、Ⅳ
D．Ⅰ、Ⅱ、Ⅲ、Ⅳ
【答案】D查看答案
【解析】浮点数的加减运算步骤包括：①对阶，使两个操作数的小数点位置对齐，阶码小的尾数右移，可能产生溢出，但是阶码不会溢出；②尾数求和，将对阶后的尾数按定点数加（减）运算规则运算；③规格化，包括左规和右规，左规时阶码减少，可能出现阶码下溢，而右规时，阶码增加可能出现阶码上溢；④舍入，该过程可能需要右规调整，因此可能出现阶码上溢；⑤溢出判断，浮点数的溢出与否是由阶码的符号决定的，而不是由尾数溢出判断的，因此尾数溢出时结果不一定溢出。因此Ⅰ、Ⅱ、Ⅲ、Ⅳ均正确。
15．假定主存地址为32位，按字节编址，主存和Cache之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（Write Back）方式，则能存放4K字数据的Cache的总容量的位数至少是（　　）。
A．146K
B．147K
C．148K
D．158K
【答案】C查看答案
【解析】Cache和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个块和缓存块容量相同；主存中某块只能映象到Cache的一个特定的块中。本题中，Cache总共存放4K字数据，块大小为4个字，因此Cache被分为4K/4 ＝ 1K个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-4＝18 位。所以，Cache的每一行需要包含所存的数据4个字，每个字32位，18位标记位、一个有效位和一个一致性维护位（回写方式），因此总容量为：（4×32＋18＋1＋1）×1K ＝148K。
16．假定编译器将赋值语句“x＝x＋3；”转换为指令“add xaddr，3”，其中，xaddr是x对应的存储单元地址。若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB，且Cache使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（　）。
A．0
B．1
C．2
D．3
【答案】B查看答案
【解析】采用页式虚拟存储管理方式时，若页表全部放在内存中，则存取一个数据最少要访问两次内存：第一次是访问页表，得到所存取的数据或指令的物理地址；第二次根据该地址存取数据或指令。在配有TLB的页式虚拟存储管理方式中，如果给出的地址在TLB中，则直接根据该地址取数据或指令，仅需要一次访问内存。在本题中，读取xaddr可能并不需要访问内存而直接访问Cache。Cache使用直写方式时，计算完后需要将数据写回到内存中，因此完成整个指令功能至少需要访问主存1次。
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；把地址addr处的内存数据放入寄存器R0中
【答案】C查看答案
【解析】A项，除法操作出现除数为零的情况时，会产生内中断，CPU切换为内核态进行中断处理；B项，直接产生中断，会切换到内核态；D项，addr出现非法地址，会出现中断，进而切换到内核态。
25．下列选项中，会导致进程从执行态变为就绪态的事件是（　）。
A．执行P（wait）操作
B．申请内存失败
C．启动I/0设备
D．被高优先级进程抢占
【答案】D查看答案
【解析】D项，被高优先级进程抢占，进程会由执行态变为就绪态。ABC三项，程序由于缺少资源而由执行态转为阻塞态。
26．若系统S1采用死锁避免方法，S2采用死锁检测方法，下列叙述中正确的是（　）。
Ⅰ.S1会限制用户申请资源的顺序，而S2不会
Ⅱ.S1需要进程运行所需资源总量信息，而S2不需要
Ⅲ.S1不会给可能导致死锁的进程分配资源，而S2会
A．仅Ⅰ、Ⅱ
B．仅Ⅱ、Ⅲ
C．仅Ⅰ、Ⅲ
D．Ⅰ、Ⅱ、Ⅲ
【答案】B查看答案
【解析】死锁避免的策略是：必须知道将来的资源需求，以寻找可能的安全允许顺序，如果不存在安全序列就阻塞；死锁检测的策略是：只要允许就分配资源，它只定期检查死锁是否已经发生，如果发生就通过剥夺解除死锁。
27．系统为某进程分配了4个页框，该进程已访问的页号序列为2，0，2，9，3，4，2，8，2，4，8，4，5。若进程要访问的下一页的页号为7，依据LRU算法，应淘汰页的页号是（　　）。
A．2
B．3
C．4
D．8
【答案】A查看答案
【解析】LRU置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框，题中访问过程中页框的变化如下：

访问页号为7的页时，内存中存在的页的页号是：2、8、4和5，根据LRU定义应淘汰的是2。
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．文件系统用位图法表示磁盘空间的分配情况，位图存于磁盘的32～127号块中，每个盘块占1024个字节，盘块和块内字节均从0开始编号。假设要释放的盘块号为409612，则位图中要修改的位所在的盘块号和块内字节序号分别是（　　）。
A．81、1
B．81、2
C．82、1
D．82、2
【答案】C查看答案
【解析】位图中要修改的位所在的盘块号=起始块号＋└盘块号/（1024×8）┘=32＋└409612/（1024×8）┘=32＋50=82，块内字节号=└（盘块号%（1024×8））/8┘=1。
32．某硬盘有200个磁道(最外侧磁道号为0)，磁道访问请求序列为：130，42，180，15，199，当前磁头位于第58号磁道并从外侧向内侧移动。按照SCAN调度方法处理完上述请求后，磁头移过的磁道数是（　　）。
A．208
B．287
C．325
D．382
【答案】C查看答案
【解析】SCAN算法是在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。当前磁头位于第58号磁道并从外侧向内侧移动，所以先依次访问130、180和199，然后再返回从内侧向外侧移动，依次访问42和15，那么磁头需要移动的磁道数是（199-58）＋（199-15）=325。
33．通过POP3协议接收邮件时，使用的传输层服务类型是（　　）。
A．无连接不可靠的数据传输服务
B．无连接可靠的数据传输服务
C．有连接不可靠的数据传输服务
D．有连接可靠的数据传输服务
【答案】D查看答案
【解析】POP3协议是最简单的邮箱访问协议，当用户接收邮件时，POP3客户进程首先与邮件服务器的POP3服务器进程建立TCP连接，因此是一种有连接可靠的数据传输服务。
34．使用两种编码方案对比特流01100111进行编码的结果如图3所示，编码1和编码2分别是（　　）。

图3编码图
A．NRZ和曼彻斯特编码
B．NRZ和差分曼彻斯特编码
C．NRZI和曼彻斯特编码
D．NRZI和差分曼彻斯特编码
【答案】A查看答案
【解析】NRZ编码用高电平表示1，低电平表示0。NRZI编码用电平的一次翻转来表示1，与前一个电平相同的电平表示0。曼彻斯特编码是根据每一个码元中间的电平变化来编码的，用正的电压跳变表示1，用负的电压跳变表示0。差分曼彻斯特编码在信号位开始时改变信号极性，表示0，在信号位开始时不改变信号极性，表示1。
35．主机甲通过128 kbps卫星链路，采用滑动窗口协议向主机乙发送数据，链路单向传播延迟为250 ms，帧长为1000字节。不考虑确认帧的开销，为使链路利用率不小于80％，帧序号的比特数至少是（　　）。
A．3
B．4
C．7
D．8
【答案】B查看答案
【解析】一个帧的传输时延是1000B/128kbps=62.5ms。设可以连续发送n个帧，则有（n×62.5）/(n×62.5＋250)≥80%，解得n≥16=24，所以帧序号的比特数至少是4。
36．下列关于CSMA／CD协议的叙述中，错误的是（　　）。
A．边发送数据帧，边检测是否发生冲突
B．适用于无线网络，以实现无线链路共享
C．需要根据网络跨距和数据传输速率限定最小帧长
D．当信号传播延迟趋近0时，信道利用率趋近100％
【答案】B查看答案
【解析】CSMA／CD协议是用于有线网络的协议。
37．下列关于交换机的叙述中，正确的是（　　）。
A．以太网交换机本质上是一种多端口网桥
B．通过交换机互连的一组工作站构成一个冲突域
C．交换机每个端口所连网络构成一个独立的广播域
D．以太网交换机可实现采用不同网络层协议的网络互联
【答案】A查看答案
【解析】交换机实质上就是一个多端口网桥是数据链路层上的网络设备。B选项错，交换机能经济地将网络分成小的冲突域，为每个工作站提供更高的带宽。C选项错，路由器是用来构成广播域的设备。D选项错，交换机是数据链路层上的网络设备。
38．某路由器的路由表如表1所示：
表1路由表

若路由器收到一个目的地址为169.96.40.5的IP分组，则转发该IP分组的接口是（　　）。
A．S1
B．S2
C．S3
D．S4
【答案】C查看答案
【解析】由路由表知，该路由器使用的是CIDR，斜线后的数字即为网络前缀的长度。目的IP地址169.96.40.5与路由表中的前三项都能匹配，这时应该根据最长前缀匹配原则选择169.96.40.0/27的目的网络，所以选C。
39．主机甲和主机乙新建一个TCP连接，甲的拥塞控制初始阈值为32 KB，甲向乙始终以MSS=1 KB大小的段发送数据，并一直有数据发送；乙为该连接分配16 KB接收缓存，并对每个数据段进行确认，忽略段传输延迟。若乙收到的数据全部存入缓存，不被取走，则甲从连接建立成功时刻起，未发生超时的情况下，经过4个RTT后，甲的发送窗口是（　　）。
A．1 KB
B．8 KB
C．16 KB
D．32 KB
【答案】A查看答案
【解析】发送窗口=min{接收窗口，拥塞窗口}。乙收到的数据全部存入缓存，不被取走，则经过4个RTT后，接收窗口只剩下16-1-2-4-8=1KB缓存，所以甲的发送窗口为1 KB。
40．某浏览器发出的HTTP请求报文如下：


下列叙述中，错误的是（　　）。
A．该浏览器请求浏览index.html
B．index.html存放在www.test.edu.cn上
C．该浏览器请求使用持续连接
D．该浏览器曾经浏览过www.test.edu.cn
【答案】C查看答案
【解析】由Connection：Close知，该浏览器请求的是非连续连接方式，所以C选项错。
二、综合应用题：41～47小题，共70分。
41．（15分）用单链表保存m个整数，结点的结构为：

，且|data|≤n（n为正整数）。现要求设计一个时间复杂度尽可能高效地算法，对于链表中data绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。
例如，若给定的单链表head如下：

则删除结点后的head为：

要求：
（1）给出算法的基本思想。
（2）使用C或C＋＋语言，给出单链表结点的数据类型定义。
（3）根据设计思想，采用C或C＋＋语言描述算法，关键之处给出注释。
（4）说明你所设计算法的时间复杂度和空间复杂度。
答：（1）算法思想：
定义一个大小为n的布尔数组flag，初始时所有的元素都赋值为false，用来标识遍历过程中是否出现元素绝对值为flag的结点。然后遍历链表，遍历过程中，每一个当前结点data域的绝对值所对应的flag位：若为真，则删除该结点；若为假（false），则将flag位置为真（true）。
（2）结点的数据结构定义如下：

（3）boolflag[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;
　 deletep;
　 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．（8分）已知有5个顶点的图G如图4所示。

图4图G
请回答下列问题。
（1）写出图G的邻接矩阵A（行、列下标从0开始）。
（2）求A2，矩阵A2中位于0行3列元素值的含义是什么？
（3）若已知具有n（n≥2）个顶点的邻接矩阵为B，则Bm（2≤m≤n）中非零元素的含义是什么？
答：（1）邻接矩阵为

（2）A2为：

0行3列的元素的含义是顶点0到顶点3之间是相通的，并且路径长度为2的路径有3条。
（3）Bm(2≤m≤n)中非零元素的含义是：假设此顶点位于i行j列，表示从i顶点到j顶点路径长度为m的路径的条数。
43．（13分）某16位计算机的主存按字节编址，存取单位为16位；采用16位定长指令字格式；CPU采用单总线结构，主要部分如图5所示。图中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。

图5 CPU示意图
请回答下列问题。
（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所控制的部件是一个三态门，用于控制移位器与总线之间数据通路的连接与断开。
（4）须连接到控制部件的输出端端口有①②③⑤⑧。
【解析】操作符命令，传输等都需要控制信号进行控制。
（5）⑥→⑨，⑦→④。
（6）数据宽度是16位，以字节编址，输入端是2是为了增加地址获取ALU的第二个操作数，也就是执行（PC）＋2操作。
44．（10分）题43中描述的计算机，其部分指令执行过程的控制信号如图6所示。

图6 部分指令的控制信号
该机指令格式如图7所示，支持寄存器直接和寄存器间接两种寻址方式，寻址方式位分别为0和1，通用寄存器R0～R3的编号分别为0、1、2和3。

图7 指令格式
请回答下列问题。
（1）该机的指令系统最多可定义多少条指令？
（2）假定inc、shl和sub指令的操作码分别为01H、02H和03H，则以下指令对应的机器代码各是什么？
①inc R1；R1＋1→R1
②shl R2，R1；（R1）7条指令。
（2）①0240H，②0488H，③06EAH
【解析】“inc R1；R1＋1→R1”中R1是直接寻址的单地址指令，代码是“0000001 001000000”，前面七位是操作码（01H），001是第一个操作数地址（R1）；
“shl R2，R1；（R1）32／212=220页。
(2)(210×4)／212(页目录所占页数)＋(220×4)／212(页表所占页数)=1025页。
(3)需要访问一个二级页表。因为虚拟地址01000000H和01112048H的最高10位的值都是4，访问的是同一个二级页表。
47．(9分)某网络拓扑如图8所示，其中路由器内网接口、DHCP服务器、WWW服务器与主机1均采用静态IP地址配置，相关地址信息见图中标注；主机2～主机N通过DHCP服务器动态获取IP地址等配置信息。

图8某网络拓扑图
请回答下列问题。
(1)DHCP服务器可为主机2～主机N动态分配IP地址的最大范围是什么?主机2使用DHCP协议获取IP地址的过程中，发送的封装DHCP Discover报文的IP分组的源IP地址和目的IP地址分别是什么?
(2)若主机2的ARP表为空，则该主机访问Internet时，发出的第一个以太网帧的目的MAC地址是什么?封装主机2发往Internet的IP分组的以太网帧的目的MAC地址是什么?
(3)若主机1的子网掩码和默认网关分别配置为255.255.255.0和111.123.15.2，则该主机是否能访问WWW服务器?是否能访问Internet?请说明理由。
答：(1)DHCP服务器可为主机2～主机N动态分配IP地址的最大范围是：111.123.15.5～111.123.15.254；主机2发送的封装DHCP Discover报文的IP分组的源IP地址和目的IP地址分别是0.0.0.0和255.255.255.255。
(2)主机2发出的第一个以太网帧的目的MAC地址是ff-ff-ff-ff-ff-ff；封装主机2发往Internet的IP分组的以太网帧的目的MAC地址是O0-a1-a1-a1-a1-a1。
　 (3)主机1能访问WWW服务器，但不能访问Internet。由于主机1的子网掩码配置正确而默认网关IP地址被错误地配置为111.123.15.2(正确IP地址是111.123.15.1)，所以主机1可以访问在同一个子网内的WWW服务器，但当主机1访问Internet时，主机1发出的IP分组会被路由到错误的默认网关(111.123.15.2)，从而无法到达目的主机。

下载地址:http://free.100xuexi.com/Ebook/157116.html