2018年北京师范大学数学科学学院805数据结构(C语言版)之数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】P ﹣＞next! ＝NULL
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
2． 实现字符串拷贝的函数strcpv 为:
(_____)
【答案】s++＝*t++或(*s++＝*t++)!＝'\0‟
3． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。
【答案】
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
4． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f(m，n) 为这种表示方式的数目。例f(5，3) ＝5, 有5种表示方式:3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1，1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
_____
_____；
}
_____；
}
，
_____)
②执行程序，f(6，4) ＝_____。 【答案】①1; 1; f(m, n ﹣1) ; n ②9
5．
给定一组数据WPL 的值为_____。
【答案】5；96
以它构造一棵哈夫曼树，则树高为_____，带权路径长度
【解析】每次找两个最小的权值构建哈夫曼树:
6． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
7． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
8． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是
。
9． 表达式23＋((12*3﹣2)/4＋34，5/7) ＋108/9的后缀表达式是_____。
【答案】
(表达式中的点(.)是数分隔符，如
是三个数)
10．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。
【答案】比较；移动
11．一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
12．如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为其中:
left 指向其左孩子，
【答案】
13．顺序栈用
存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
left 指向其前驱；，
right 指向其后继。
，
right 指向其右孩子，，
，
【答案】if(top!＝n)data[++top]＝x ；
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
14．应用prim 算法求解连通网络的最小生成树问题。
(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值
)
(2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在
图的顶点数，应由用户定义
用二维数组作为邻接矩阵表示
中