2017年南昌大学信息工程学院838数据结构[专业硕士]考研仿真模拟题
● 摘要
一、选择题
1． 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为2字节，逻辑地址结构为：
逻辑地址空间大小为（ ）。
A.64 B.128 C.256 D.512
【答案】B
【解析】地址空间分为逻辑地址空间和物理地址空间。页的大小为采用二级页表，
一页可存放要
个页面来保存页表项，故本题答案为B 。
字节，页表项大小为2B ，
字节，故最少需
’个页表项，本题中逻辑地址空间大小为
页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是
字节，页表项大小为
2． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n B. C. D. 【答案】C
【解析】每个结点（除根节点外）都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n-1。
3． 若下图为lOBaseT 网卡接收到的信号波形，则该比特串是（ ）
A.00110110 B.10101101 C.01010010 D.11000101 【答案】A
【解析】以太网采用曼彻斯特编码，其将一个码元分成两个相等的间隔，前一个间隔为高电平而后一个间隔为低电平表示1，反之则表示0。故根据波形图，可得答案为A 。
4． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表 C. 双链表
D. 仅有尾指针的单循环链表 【答案】D
【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。
5． 已知一棵有2011个结点的树，其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。
A.115 B.116 C.1895 D.1896 【答案】D
【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点（因为一个非终端结点，另外，树根结点转至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子）
换成二叉树后也没有右孩子。题目中树的总结点数是2011，叶结点个数是116, 则非终端结点个数是2011-116=1895, 则该树对应的二叉树中 无右孩子的结点个数是1895+1=1896。
6． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。
A. 直接插入排序 B. 起泡排序 C. 简单选择排序 D. 快速排序 【答案】A
【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，
要使其下沉到底部仍需
趟排序，也即时间复杂度仍为
而对
简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即间复杂度为0（nlog2n ）
n-1趟，
比较的时间复杂度由 降至
7． 下列关于RISC 的叙述中，错误的是（ ）。
A.RISC 普遍采用微程序控制器
B.RISC 大多数指令在一个时钟周期内完成
C.RISC 的内部通用寄存器数量相对CISC 多
D.RISC 的指令数、寻址方式和指令格式种类相对CISC 少 【答案】A
【解析】B 项、C 项、D 项都是RISC 的特点之一，所以它们都是正确的，只有A 项是CISC 的特点，因为RISC 的速度快，所以普遍采用硬布线控制器，而非微程序控制器。
8． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个 【答案】C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
9． 站点A 、B 、C 通过CDMA 共享链路，A 、B 、C 的码片序列（chipping sequence
）分别是
和
C 收到A 发送的数据是（ ）
A.000 B.101 C.110 D.111
【答案】B
【解析】用A 的码片与信息做内积运算
10．将一个的三对角矩阵，按行优先存入一维数组（即该元素下标
A.198 B.195 C.197
【答案】B
在B 数组中的位置K 为（ ）。
若C 从链路上收到的序列是
则
中，A 中元素
【解析】将对角矩阵存入
11．已知有向图G=（V ，E ），其中
三对角矩阵压缩地址计算公式如下：
G 的拓扑序列是
（ ）。
【答案】A