2018年北京师范大学研究生院珠海分院879程序设计与数据结构[专业硕士]考研强化五套模拟题
● 摘要
一、填空题
1． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
2． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)
【答案】93
【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。
3． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。
【答案】选择；完全二叉树；；O(1)；满足堆的性质
4． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。
5． 建立索引文件的目的是_____。
【答案】提高查找速度
6． 已知有序表为(12，18，24，35，47，50，62，83，90，115，134) 当用二分法查找90时，需次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2; 4; 3
【解析】二分法查找元素次数列表
第 2 页，共 47 页 在B
查找100是找到115就停止了。
7． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ; ；2；k
8． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
(1)若是边，则的值等于_____，若不是边，则A(i, j) 的值是一个比任何
置边的权_____，矩阵的对角线元素全为0。 (2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素
成_____，若
【答案】(1)已包括进生成树，就把矩阵元素置成_____。 (3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。 边上的权值；都大的数；(2)1; 负值；(3)为负；边
9． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
10．如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
序查找效率一样为
11．
【答案】5
12．在下面的程序段中，对X 的赋值语句的时间复杂度为_____ (表示为n 的函数) 。
第 3 页，共 47 页
。 ＝_____ 【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺
【答案】1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋…＋n) ＝n(n＋1)(n＋2)/6，即O(n)
【解析】当i ＝l 时，赋值语句就被执行了一次。当i ＝2时，赋值语句被执行了1＋2次。当i ＝3时，赋值语句被执行了1＋2＋3次。...... 可以推出赋值语句总共被执行了1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋... ＋n) ＝n(n＋1)(n＋2)/6次。
二、判断题
13．对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（ ）
【答案】√
【解析】形状不同的两个二叉排序树(关键字集合相同) ，在中序遍历下是输出排好序的序列，所以顺序是一致的。
14．如果数据元素保持有序，则查找时就可以采用折半查找方法。（ ）
【答案】×
【解析】采用折半查找的条件是数据元素有序且存储方式为顺序存储，对于常见的链式存储，在进行查找时主要依靠指针来操作。
15．若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。（ ）
【答案】×
【解析】堆中某个节点的值总是不大于或不小于其父节点的值，这个并不是二叉排序树的性质。
16． 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）
【答案】 ×
【解析】数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。
17．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第k ﹣1层具有的最多结点数为余下的
【答案】 √
【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为k ﹣1层全满时，此时从根结点到第k ﹣1层具有最大的结点数为
18． 若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（ ）
【答案】√
【解析】因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所
第 4 页，共 47 页
个结点在第k 层的任一位置上。（ ）