2017年郑州大学联合培养单位安阳师范学院944计算机学科专业基础综合之数据结构考研导师圈点必考题汇编目录 2017年郑州大学联合培养单位安阳师范学院944计算机学科专业基础综合（含数据结构、计算机组成原理、操作系统、计算机网络）专业硕士之数据结构考研导师圈点必考题汇编（一） . 2 2017年郑州大学联合培养单位安阳师范学院944计算机学科专业基础综合（含数据结构、计算机组成原理、操作系统、计算机网络）专业硕士之数据结构考研导师圈点必考题汇编（二） 19 2017年郑州大学联合培养单位安阳师范学院944计算机学科专业基础综合（含数据结构、计算机组成原理、操作系统、计算机网络）专业硕士之数据结构考研导师圈点必考题汇编（三） 32 2017年郑州大学联合培养单位安阳师范学院944计算机学科专业基础综合（含数据结构、计算机组成原理、操作系统、计算机网络）专业硕士之数据结构考研导师圈点必考题汇编（四） 44 2017年郑州大学联合培养单位安阳师范学院944计算机学科专业基础综合（含数据结构、计算机组成原理、操作系统、计算机网络）专业硕士之数据结构考研导师圈点必考题汇编（五） 58一、选择题1 一个TCP 连接总是以1KB 的最大段发送TCP 段，发送方有足够多的数据要发送。当拥塞窗口为16KB 时发生了超时，如果接下来的4个RTT （往返时间）时间内的TCP 段的传输都是成功的，那么当第4个RTT 时间内发送的所有TCP 段都得到肯定应答时，拥塞窗口大小是（ ）。A.7KBB.8KBC.9KBD.16KB【答案】C【解析】回顾TCP 流量控制和拥塞控制（慢启动）的知识点，从第一个MSS 开始，每次发送成功，拥塞窗口值翻倍，四次以后，应该为16, 但是由于拥塞阈值变为16/2=8, 故三次成功后为8, 以后为线性增长，故为8+1=9, 答案为C 。 2 对一组数据（2, 12, 16, 88, 5，10）进行排序，若前三趟排序结果如下：第一趟：2，12，16, 5，10，88第二趟：2，12，5，10，16, 88 第三趟：2，5，10，12，16, 88则采用的排序方法可能是（ ）。A. 起泡排序B. 希尔排序C. 归并排序D. 基数排序【答案】A【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次，待序列中的记录“基比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐増多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序，直至整个序列为有序为止。 基数排序是分配排列合并为一个大的有序序列，然后“逐趟归并”序的一种，这类排序不是通过关键字比较，而是通过“分配”和“收集”过程来实现排序的。 本，显然使用的是起泡排序法。 题中，很容易看出大值逐渐“沉底” 3 给定二叉树如下图所示。设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树，若遍历后的节点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）A.LRNB.NRLC.RLND.RNL 图【答案】D【解析】对“二叉树”而言，一般有三条搜索路径；先上后下的按层次遍历；先左（子树）后右（子树）的遍历；先右（子树）后左（子树）的遍历；其中第1种路径的搜索方式就是常见的层次遍历，第2种搜索路径方式包括常见的NLR 、中序遍历LNR 、后序遍历LRN , 第3种搜索路径方式则是不常使用的NRL 、RNL 、RLN 。本题考查的是第3种搜索路径方式的一种情况。根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D 。 4 在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。A. 机械特性B. 功能特性C. 过程特性D. 电气特性【答案】C 。【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边界点，即接插装置；电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制；功能特性：主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以 分析描述事件先后顺序的就是规程，也就是过程特性，答案是C 。 5 浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含2位符号位）。若有两个数则用浮点加法计算X+Y的最终结果是（ ）。A.001111100010B.001110100010C.010000010001D. 发生溢出【答案】D【解析】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点在对阶、规格化、判溢出这三步。X 和Y 的阶码不同，所以应该先对阶，对阶原则为：小阶向大阶看齐。因此将Y 对阶后得到：Y=然后将尾数相加，得到尾数之和为：34/32。因为这是两个同号数相加，尾数大于1，则需要右规，阶码加1。由于阶码的位数为5位，且含两位符号位，即阶码的表示范围在-8?+7之间。而阶码本身等于7, 再加1就等于8。因此，最终结果发生溢出。 6 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。 【答案】C【解析】因为该序列中的结点已经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为的时间复杂度为对于采用归并法，它是一种稳定的排序方法，它对于一般的快速排序法，序列越接近有序，所需要的比较次数越多， 此时的时间复杂度为 7 在无噪声情况下，若某通信链路的带宽为3kHz ，采用4个相位，每个相位具有4种振幅的QAM 调制技术，则该通信链路的最大数据传输速率是（ ）。A.12kbpsB.24kbpsC.48kbpsD.96kbps【答案】B【解析】首先要根据信道有无噪声来确定是否采用奈奎斯特定理。解题难点在于离散数值的确定，先确定调制技术的码元数，此处为4个相位乘以4种振幅，共16种，即该通信链路的最大数据传输速率=23（44）=64=24kbps。 8 下列有关浮点数加减运算的叙述中，正确的是（ ）。 对阶操作不会引起阶码上溢或下溢 右规和尾数舍入都可能引起价码上溢考研试题