2018年北京工业大学软件学院893软件工程学科专业基础之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
2． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。
【答案】
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
3． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增 量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; (10，7，-9，0，47，23，1，8，98，36)
4． 模式串
【答案】01122312
5．
给定一组数据WPL 的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树:
以它构造一棵哈夫曼树，则树高为_____，带权路径长度
的next 函数值序列为_____。
6． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4；2
7． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。
【答案】操作系统文件；数据库
8． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)
【答案】93
在B
【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。
9． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32, 则其伙伴块的起始地址为_____; 。
【答案】480+8=488，480－32=448
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:
根据上述公式起始地址就为488。 10． 假定查找有序表中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。
【答案】
表
平均查找次数为
11．在哈希函数
。
中，p 值最好取_____。
【解析】折半查找时每个的次数如表所示:
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
12．在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
二、单项选择题
13．若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1, 则该平衡二叉树的结点总数为（ ）。
A.12 B.20 C.32 D.33
【答案】B 。
【解析】本题的实际问题是, 具有6层结点的平衡二叉树含有最少的结点数是多少。深度为h 的平衡二叉树中含有的最少结点数, 有
由此可得
。对应的平衡二叉树如下图所示。
表示
14．已知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。
A.CBEFDA B.FEDCBA C.CBEDFA D. 不定
【答案】A
【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B 的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。
15．用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中结点，使j 沿链移动的操作为（ ）。
A.j ＝r[j].next B.j ＝j ＋l C.j ＝j ﹣＞next D.j ＝r[j]﹣＞next 【答案】A
【解析】因为是用数组存储，这里所说的工作指针j 相当于数组的下标，结点是存储一个值域和next 域，next 域就是存放下一个结点的下表，所以只要将next 域中的值赋给j 就可以实现j 沿链移动。
16．对矩阵压缩存储是为了（ ）。
A. 方便运算 B. 方便存储
相关内容
相关标签