2018年北京语言大学计算机软件与理论825数据结构与程序设计之数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 在有n 个顶点的有向图中，每个顶点的度最大可达_____。
【答案】2(n－1)
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。
2． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。
【答案】完全；只有一个叶结点的二叉树
3． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32, 则其伙伴块的起始地址为_____; 。
【答案】480+8=488，480－32=448
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:
根据上述公式起始地址就为488。
4． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
5． 已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_____。
【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
6．
给定一组数据以它构造一棵哈夫曼树，则树高为_____，带权路径长度WPL 的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树:
第 2 页，共 55 页
7． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增
量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; (10，7，-9，0，47，23，1，8，98，36)
8． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。
9． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】O(1)；O(n)
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
10．假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为。
11．二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
12．文件由_____组成；记录由_____组成。
【答案】记录；数据项
13．设二维数组A 的行和列的下标范围分别为[0:8]和[0:10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_____。
【答案】A[2][3]
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*i＋j ＋l ﹣l)*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。
第 3 页，共 55 页
14．如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
15．顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【答案】if(top!＝n)data[++top]＝x ；
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
二、判断题
16．倒排文件是对次关键字建立索引。（ ）
【答案】√
【解析】倒排文件是对每一个次关键字项建立次关键字索引(称为倒排表) ，将所有具有相同次关键字的记录的物理记录号都填入倒排表为此次关键字的表中。
17．对于有n 个结点的二叉树，其高度为log 2n 。（ ）
【答案】 ×
【解析】例如n 结点的单枝树，高度就为n 。
18．外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（ ）
【答案】×
【解析】外部排序方法:按可用内存大小，将外存上含n 个记录的文件分成若干长度为2的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串(run)。对这些归并段进行逐趟归并，使归并段(有序的子文件) 逐渐由小至大，直至得到整个有序文件为止。一般情况下，外部排序所需总的时间=内部排序(产生初始归并段) 所需的时间m*tIS+外存信息读写的时间
需的时间。
19．拓扑排序的有向图中，最多存在一条环路。（ ）
【答案】×
【解析】要进行拓扑排序，需要满足一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在顶点B 到顶点A 的路径。如果是一个有环图，则不能满足这个条件，所以拓扑排序的有向图中不能存在环路。
20．有向图中顶点V 度等于其邻接矩阵中第V 行中的1的个数。（ ）
【答案】×
【解析】有向图顶点V 的出度等于其邻接矩阵第V 行中的1的个数，而有向图中V 的度等
第 4 页，共 55 页 内部归并所