2017年常州大学艺术学院858数据结构考研冲刺密押题
● 摘要
一、选择题
1． 在虚拟存储管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是（ ）。
A. 编辑
B. 编译
C. 链接
D. 装载
【答案】B
【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本，不涉及到任何与计算机运 行相关的事；编译是由编译程序将用户源代码编译成若干个目标模块，源地址编译成目标程序时，会形成逻辑地址；链接是由链接程序将编译后形成的一组目标模块，以及所需库函数链接，形成完整的装入模块；装入是由装入程序将装入模块装入内存。
2． 若下图为lOBaseT 网卡接收到的信号波形，则该比特串是（ ）
A.00110110
B.10101101
C.01010010
D.11000101
【答案】A
【解析】以太网采用曼彻斯特编码，其将一个码元分成两个相等的间隔，前一个间隔为高电平而后一个间隔为低电平表示1，反之则表示0。故根据波形图，可得答案为A 。
3． 图的BFS 生成树的树高比DFS 生成树的树高（ ）。
A. 小或相等 B. 小 C. 大或相等 D. 大
【答案】A
【解析】BFS 称作广度优先搜索，DFS 称作深度优先搜索。广度优先搜索类似与二叉树的层
序遍历算法，深度优先搜索类似于树的先序遍历。因为深度优先搜索算法遵循的策略是尽可能的“深”地搜索一个图。所以图的BFS 生成树的树高比DFS 生成树的树高小或者相等。
4． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。
A. 直接插入排序
B. 起泡排序
C. 简单选择排序
D. 快速排序
【答案】A
【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需趟排序，也即时间复杂度仍为而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时
；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即间复杂度为0（nlog2n ）
n-1趟，
比较的时间复杂度由 降至
5． 下列关于最小生成树的叙述中，正确的是（ ）。
I . 最小生成树的代价唯一 II. 所有权值最小的边一定会出现在所有的最小生成树中III. 使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树一定相同IV. 使用普里姆算法和克鲁斯卡尔（Kruskal ）算法得到的最小生成树总不相同
A. 仅I
B. 仅II
C. 仅 I 、III
D. 仅 II 、IV
【答案】A 。
【解析】当图中存在相同权值的边时，其最小生成树可能是不唯一的，但最小生成树的代价
所以说法I 正确。一定是相同的，从n 个顶点的连通图中选取n-1条权值最小的边可能构成回路，
所以说法II 错误。当某个顶点有权值相同的边，使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树并不一定相同，所以说法III 错误。当最小生成树不唯一时，使用普里姆算法和克鲁斯卡尔（Krnskal ）算法得到的最小生成树可能相同，也可能不同，所以说法IV 错误。由此可得出正确答案。
6． 已知一棵有2011个结点的树，其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。
A.115
B.116
C.1895
D.1896
【答案】D
【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点（因为一个非终端结点
，另外，树根结点转至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子）
换成二叉树后也没有右孩子。题目中树的总结点数是2011，叶结点个数是116, 则非终端结点个数是2011-116=1895, 则该树对应的二叉树中 无右孩子的结点个数是1895+1=1896。
7． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
【答案】A
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是 ，则有语句设其执行时间为T （n ）
8． 对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。
A. 顺序存储方式
B. 链式存储方式
C. 散列存储方式
D. 以上均可以
【答案】B
9． 有
A.
B.
C.
D. 个分支结点的满二叉树的深度是（ ）。
【答案】C
【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树，所以非分支的结点总数为1，所以满二叉树共有
10．设置当前工作目录的主要目的是（ ）。
A. 节省外存空间
B. 节省内存空间
C. 加快文件的检索速度
D. 加快文件的读/写速度
个结点，所以满二叉树的深度为