2017年中国科学技术大学软件学院834软件工程基础[专业硕士]之数据结构考研题库
● 摘要
目录
2017年中国科学技术大学软件学院834软件工程基础[专业硕士]之数据结构考研题库（一） . 2 2017年中国科学技术大学软件学院834软件工程基础[专业硕士]之数据结构考研题库（二）15 2017年中国科学技术大学软件学院834软件工程基础[专业硕士]之数据结构考研题库（三）26 2017年中国科学技术大学软件学院834软件工程基础[专业硕士]之数据结构考研题库（四）34 2017年中国科学技术大学软件学院834软件工程基础[专业硕士]之数据结构考研题库（五）44
第 1 页，共 56 页
一、选择题
1． 设有数组
数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内
的存储首地址为（ ）。
【答案】B
【解析】在计算中，可以考虑按照列存放时，址。比如
顺序存放时，它是第
在内存的位置，比较容易计算元素的首地
个元素，由于首地址为BA ，
所以它的存储首地址为
存首地址BA 开始顺序存放，当用以列为主存放时，元素
2． 下列四个序列中，哪一个是堆（ ）？
A.75，65，30，15，25，45，20，10 B.75，65，45，10，30，25，20，15 C.75，45，65，30，15，25，20，10 D.75，45，65，10，25，30，20，15
【答案】C
【解析】堆的定义： n 个关键字序列
且
且
称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
小根堆：满足第①种情况的堆； 大根堆：满足第②种情况的堆。 根据堆定义即可得出答案。
3． 设哈希表
长哈希函
数
再哈希法解决冲突，关键字为49的结点的地址是（ ）。
【答案】D
【解析】15，38，61，84用哈希函数为5，发生冲突，用二次探测再散列法解决冲突：
仍然发生冲突。
仍然发生冲突。
不再发生冲突。
第 2 页，共 56 页
表中已有4个结点
：其余地址为空，如用二次探测
计算后得地址：4，5，6，7。49计算后
4． 设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单个文件最大长度是（ ）。
A.33KB B.519KB C.1057KB D.16513KB 【答案】C
【解析】4个地址项为直接地址索引，其指向的数据块大小4×256B=lKB，一级间接地址索引可以索引256/4=64个直接地址索引，故2个一级间接地址索引指向的数据块大小为2×64×256B=32KB，二级间接地址索引为256/4×256/4=4096个直接地址索引，故1个二级间接地址索引指向的数据块大小为4096×256B=1024KB, 共计1KB+32KB+1024KB=1057KB。
5． 对一组数据（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
【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次，待序列中的记录“基比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐増多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序，直至整个序列为有序为止。 基数排序是分配排列合并为一个大的有序序列，然后“逐趟归并”
序的一种，这类排序不是通过关键字比较，而是通过“分配”和“收集”过程来实现排序的。 本，显然使用的是起泡排序法。 题中，很容易看出大值逐渐“沉底”
6． 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树 B. 哈夫曼树
C. D. 堆
第 3 页，共 56 页
树
【答案】D
【解析】堆的定义： n 个关键字序列（1）
（2）
且且
或
称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
满足第（1）种情况的堆，称为小顶堆；满足第（2）种情况的堆，称为大顶堆。 由堆的定义可知堆可以满足上述性质。
7． 某时刻进程的资源使用情况如下表所示
此时的安全序列是（ ）。 A.P1, P2, P3, P4 B.P1, P3, P2, P4 C.P1, P4, P3, P2 D 不存在 【答案】D
【解析】典型的死锁避免算法，银行家算法的应用。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下下表，可以看到，经过P1, P4的运行以后，可用资源是2, 2，1，而 P2, P3所需资源分别是1，3, 2和1，3，1。所以剩余资源已经不够P2或P3的分配，亦即找不到能够安全运行的序 列，因此此时是处于不安全状态，所以不存在这样的安全序列。
8． 若对如下的二叉树进行中序线索化，则结点x 的左、右线索指向的结点分别是（ ）
A.
B.
C.
D.
第 4 页，共 56 页