2016年长春师范大学计算机科学与技术学院数据结构(同等学力及跨学科加试)复试笔试最后押题五套卷
● 摘要
一、选择题
1． —
组记录的关键码为
准得到的一次划分结果为（ ）。
答:C
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为一次划分结束。
2． 以太网的MAC 协议提供的是（ ）。
A. 无连接不可靠服务 B. 无连接可靠服务 C. 有连接不可靠服务 D. 有连接可靠服务 答:A 。
【解析】考查以太网MAC 协议，考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简洁：①采用无连接的工作方式；②不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，即尽最大努力交付，差错的纠正由高层完成。
3． 若一个栈以向量
存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。
答:C
【解析】题中初始栈顶指针top 为n+1, 而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。
则利用快速排序的方法，以第一个记录为基
4． 循环队列元素数是（ ）。
存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的
答:A
【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。
和队尾
的概念，在队头进行出队操作，
如果为负则元
可能为正也可能为负，为正时元素个数=
素的个数=所以统一的公式就是
5． 某容量为256M 的存储器，由若干位的DRAM 芯片构成，该DRAM 芯片的地址引脚和数据引脚总数是：（ ）
A.19 B.22 C.30 D.36 答:A
【解析】DRAM 地址线复用，4M 为2的22次方，因此除2为11根，数据线8根。因此地址引脚和数据引脚总数为19根
6． 计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。
A. 可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 答:B
【解析】计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述，也就是解决问题的步骤序列。一个算法通常需要具备五大特性：有穷性；确定性；可执行性；输入一个算法有零个或多个输入；输出一个算法有零个或者多个输出。
7． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）。
A. B. C. D. 答:C
【解析】段内位移的最大值就是最大段长。段号长度占了8位，剩下32-8=24位是段内位移空间，因此最大段长为
B 。
字节 字节 字节 字节
8． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度 B. 为了能在二叉树中方便地进行插入与删除 C. 为了能方便地找到双亲 D. 使二叉树的遍历结果唯一 答:A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
9． 在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性 B. 功能特性 C. 过程特性 D. 电气特性 答:C 。
【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边界点，即接插装置；电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制；功能特性：主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以 分析描述事件先后顺序的就是规程，也就是过程特性，答案是C 。
10．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）
。
答:B
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：28比72小，不交换； 第二次比较：28比5大，交换，此时为第三次比较：16比28小，不交换； 第四次比较：32比28大，交换，此时为第五次比较：28比2大，交换，此时为第六次比较：28比12大，不交换； 第七次比较：28比60小，交换，此时为一次划分结束。
二、填空题