2017年中北大学软件学院821数据结构与算法考研仿真模拟题
● 摘要
一、选择题
1． 若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组
中，则在B 中确定
的位置k 的关系为（ ）。
【答案】B
【解析】将n 阶对称矩阵存人一维数组中，一维数组的大小需为
中，当
时，i 与k 的关系为
对n 阶对称矩阵
A
以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组
2． 下面关于哈希（Hash ，杂凑）查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B. 除留余数法是所有哈希函数中最好的 C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可 【答案】C
【解析】若数据结构中存在关键字和K 值相等的记录，则必定在不需要进行比
较便可直接取得所查记录。在此，称这个对应关系f 为哈希（Hash ）函数，哈希函数的选择要视具体情况而定。
3． 对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。
A. 每次分区后，先处理较短的部分 B. 每次分区后，先处理较长的部分 C. 与算法每次分区后的处理顺序无关 D. 以上三者都不对 【答案】A
【解析】令递归函数为f ，第一次进行递归函数认为递归深度为1，以后从深度为n 的递归函数f 中再调用递归函数f ，此时深度为整个f 的最大深度为递归深度。
4． 设与某资源相关联的信号量初值为3, 当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）。
A.0、1
第 2 页，共 69 页
的存储位置上，由此，
B.1、0 C.1、2 D.2、0 【答案】B
【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。
5． 下列程常段的时间复杂度是（ ）
A. B. C. D.
【答案】C
而对于k ，每次循环都执行
所以循环次数为
【解析】外部循环的退出条件是内部循环的退出条件是
对于j ，每次循环都执行所以每次循环次数为n 次。所以此程序
段的时间复杂度为O 即选C 。
6． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希（Hash ）表 B. 广度优先搜索网 C. 前序（根）遍历二叉树 D. 深度优先搜索网 【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
7． 某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位，并且数据按边界对齐存储。某C 语言程序段如下：
若record 变量的首地址为则地址中内容及record.c 的地址分别为（ ）。 A. B. C.
第 3 页，共 69 页
D.
【答案】D 。
【解析】32位整数a 需要占4个字节，16位整数c 需要占2个字节，而字符数据b 占一个字节。a=273, 转换成十六进制是111H , 采用小端方式存放数据，地址0xC008中的内容为11H 。由于数据按边界对齐存储，地址
中存放a , 地址
中存放b , 地址
中空闲，
地址中存放c 。
8． 在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37 所在结点的左、右子结点中保存的关键字分别是（ ）。
A.13、48 B.24、48 C.24、53 D.24、90 【答案】C
【解析】题目中，插入48以后，树根结点的平衡因子由-1变为-2, 失去平衡。这属于RL （先右后左）型平衡旋转，需做两次（先右旋后左旋转）旋转操作。过程如下图所示：
显然，在调整后的新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是24, 53。
9． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法。
A. 分块 B. 顺序 C. 折半 D. 哈希 【答案】A
第 4 页，共 69 页
相关内容
相关标签