2018年哈尔滨商业大学计算机与信息工程学院816数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 现有容量为10GB 的磁盘分区, 磁盘空间以簇(duster)为单位进行分配, 簇的大小为4KB , 若采用位图法管理该分区的空闲空间, 即用一位(bit)标识一个簇是否被分配, 则存放该位图所需簇的个数为（ ）
A.80 B.320 C.80K D.320K 【答案】A
【解析】磁盘的簇的个数为:
个
而一个簇的位示图能管理的簇的个数为:
所以需要簇的个数为
个
2． 对一组数据(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
【解析】题目中所给的三趟排序过程, 显然是使用起泡排序方法, 每趟排序时从前往后依次比较, 使大值“沉底”。希尔排序的基本思想是:先对序列进行“宏观调整”, 待序列中的记录“基本有序”时再进行直接插入排序。宏观调整的方法是:通过某种规则将大的待排序序列分割为若干小的待排序序列, 再依次对这些小的序列直接插入排序。宏观调整可以多次, 每次分割的序列数逐渐增多, 而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序列合并为
一个大的有序序列, 然后“逐趙归并”, 直至整个序列为有序为止。基数排序是分配排序的一种, 这类排序不是通过关键字比较, 而是通过“分配”和“收集”过程来实现排序的。本题中, 很容易看出大值逐渐“沉底”, 显然使用的是起泡排序法。
3． 当字符序列 作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ）。
A.4个 B.5个 C.3个 D.6个
图
【答案】C
【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t ，有两种结果
因此总共有3种结果。
4． 某时刻进程的资源使用情况如下表所示
和
，若首字符为，
则只有一种结果
此时的安全序列是（ ）。 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的 分配, 亦即找不到能够安全运行的序列, 因此此时是处于不安全状态, 所以不存在这样的安全序列。
5． 设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，a 11为第一元素，其存储地址为1，每个元素占一个地址空间，则a 85的地址为（ ）。
A.13 B.33 C.18 D.40
【答案】B
【解析】对于对称矩阵，
为了节省存储空间，为多个相同的元素只分配一个存储空
间。对于对称矩阵，元素下表之间的对应关系为:当i ＞＝j 时，k ＝i(i﹣l)/2＋j ﹣l ；当i ＜＝j 时，k ＝j(j﹣l)/2＋i ﹣l 。其中k 相当于地址空间的标号，i 为行号，j 为列号。因为第一个元素存储地址为1，所以最后计算的k 需要加1。所以a 85的存储位置为8*(8﹣1)/2＋5＝33。
6． 假设栈初始为空, 将中缀表达式当扫描到f 时, 栈中的元素依次是（ ）
A. B. C. D. 【答案】B
【解析】中缀表达式转后缀表达式遵循以下原则: (1)遇到操作数, 直接输出; (2)栈为空时, 遇到运算符, 入栈; (3)遇到左括号, 将其入栈;
(4)遇到右括号, 执行出栈操作, 并将出栈的元素输出, 直到弹出栈的是左括号, 左括号不输出; (5)遇到其他运算符符入栈;
(6)最终将栈中的元素依次出桟, 输出。
所以扫描到‟/‟, 入栈„描到‟+‟, 由于‟+‟优先级比‟/'低, 所以将‟/‟弹出, ‟+‟入栈; 扫描到‟*,, 优先级比‟+‟高, 入栈; 扫描到‟(„, 入栈; 扫描到‟一„, 将栈中优先级更高的‟*‟弹出, „一, 入栈; 扫描到‟*‟, 优先级比‟一„高, 入栈。所以扫描至“f 的时候, 栈中元素为:+(一*
转换为等价后缀表达式的过程中,
时, 弹出所有优先级大于或等于该运算符的栈顶元素, 然后将该运算