2016年东北理工大学机械与电子工程学院数据结构(同等学力加试)复试笔试最后押题五套卷
● 摘要
一、选择题
1． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）
A.G 的邻接多重表需要n （n-l ）个边结点和n 个顶点结点 B.G 的连通分量个数最少 C.G 为连通图
D.G 所有顶点的度的总和为n （n-1） 答:A
【解析】A 项中G 的邻接多重表中需要n （n-l ）/2个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n-1，则n 个结点的度的总和为n （n-l ）。
2． 广义表
答:D
head 操作就是得到广义表中第一个的原子。【解析】
操作就是得到除第一个原子外剩下元
素构成的表。也就是toil 得到的元素需要在外层再加一个（ ）。
3． 给定二叉树如下图所示。设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树，若遍历后的节点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）
A.LRN B.NRL C.RLN
D.RNL
则式子
的值为（ ）。
图
答:D
【解析】对“二叉树”而言，一般有三条搜索路径； ①先上后下的按层次遍历；
②先左（子树）后右（子树）的遍历； ③先右（子树）后左（子树）的遍历；
其中第1种路径的搜索方式就是常见的层次遍历，第2种搜索路径方式包括常见的NLR 、中序遍历LNR 、后序遍历LRN , 第3种搜索路径方式则是不常使用的NRL 、RNL 、RLN 。本题考查的是第3种搜索路径方式的一种情况。根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D 。
4． 下面关于哈希（Hash ，杂凑）查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B. 除留余数法是所有哈希函数中最好的 C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可 答:C
【解析】若数据结构中存在关键字和K 值相等的记录，则必定在不需要进行比
较便可直接取得所查记录。在此，称这个对应关系f 为哈希（Hash ）函数，哈希函数的选择要视具体情况而定。
5． 若一个栈以向量
的存储位置上，由此，
存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。
答:C
【解析】题中初始栈顶指针top 为n+1, 而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。
6． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度 B. 为了能在二叉树中方便地进行插入与删除 C. 为了能方便地找到双亲 D. 使二叉树的遍历结果唯一 答:A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
7． 某网络的IP 地址空间为采用定长子网划分，子网掩码为则该网络的最大子网个数、每个子网内的最大可分配地址个数分别是（ ）。
A.32, 8 B.32, 6 C.8, 32
D.8, 30 答:B
【解析】子网号为5位，在CIDR 中可以表示
个子网，主机号为3位，除去全0和全1
的情况可以表示6个主机地址，答案为B 。
8． 设栈S 和队列Q 的初始状态均为空，元素a , b , c ，d ，e , f ，g 依次进入栈S 。若每个元素出栈 后立即进入队列Q ，且7个元素出队的顺序是b ，d ，c ，f , e , a ，g ，则栈S 的容量至少是（ ）。
A.1 B.2 C.3 D.4 答:C
【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序。在本题中，每个元素出栈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。
9． 哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。
A. 哈希函数 B. 除余法中的质数 C. 冲突处理
D. 哈希函数和冲突处理 答:D
【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
10．程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。
A. 逻辑设备名 B. 物理设备名 C. 主设备号 D. 从设备号 答:A
【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等。而操作