2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研强化模拟题
● 摘要
目录
2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研强化模拟题（一）.... 2 2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研强化模拟题（二）.. 16 2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研强化模拟题（三）.. 31 2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研强化模拟题（四）.. 44 2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研强化模拟题（五）.. 57
一、填空题
1． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。
注：（1）图的顶点号从0开始计；
（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；
（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。
）
.
【答案】0; j; i; 0; indegree[i]=0; [vex][i]; k==l; indegree[i]=0
【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
2． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，
元素个数为
；
（“图有回路”）
一个元素时，此时堆的元素个数最少，元素个数为
3． 假定查找有序表中每个元素的概率相等，则进行折半查找时的平均查找长度为_____
【答案】37/12
【解析】折半查找时每个的次数如表所示：
表
平均查找次数为
4． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n
个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
（1）若
是边，则
的值等于_____，若
不是边，则
的值是一个比任
何边的权，矩阵的对角线元素全为0。
（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若
【答案】（1）
已包括进生成树，就把矩阵元素A （i ，j ）置成 边上的权值；都大的数；（2）1; 负值；（3）为负；边
（3）算法结束时，相邻矩阵中。
5． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
6． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。
【答案】2（N-1）
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。
7． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）
【答案】93
【解析】对于上三角矩阵，将代入得93。
8． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用
【答案】50; 4
9． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，
【答案】比较；移动
在B
10．完善算法：求KMP 算法.next 数组。
END ； 【答案】
二、选择题
11．假定主存地址为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（WriteBack ）方式，则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。
A.146k B.147K C.148K D.158K 【答案】B
【解析】Cache 和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个块和缓存块容量相同；主存中某块只能映象到Cache 的一个特定的块中。本题中，Cache 总共存放4K 字数据，块大小为4个字，因此cache 被分为4K/4 = 1K 个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-14= 18位。所以，Cache 的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容=147K。 量为：
12．对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是:（ ）
A.05，46，13，55，94，17，42 B.05，13，17，42，46，55.94 C.42，13，94，05，55，46，17 D.05，13，46，55，17，42，94
【答案】C
【解析】基数排序有两种：最低位优先和最高位优先。
最低位优先的过程
先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。
以r 为基数的最低位优先排序的过程 假设线性表由结点序列组成，
其中
构成，每个结点aj 的关键字由d 元组（k ，k... ，k ，k ）在排序过程中，使用r 个队列
排序过程就是