2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研冲刺密押题
● 摘要
目录
2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研冲刺密押题（一）.... 2 2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研冲刺密押题（二）.. 17 2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研冲刺密押题（三）.. 34 2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研冲刺密押题（四）.. 50 2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研冲刺密押题（五）.. 65
第 1 页，共 78 页
一、填空题
1．
【答案】5
2． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
3． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
4． 建立索引文件的目的是_____。
【答案】提高查找速度
5． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
【答案】（1）（2）（3）
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
第 2 页，共 78 页
=_____
（4）（5）
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
6． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
7． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
8． 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。
【答案】
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，
所以
9． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
10．试利用下列栈和串的基本操作完成下述填空题。
initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；
置串
为空串；
第 3 页，共 78 页
length （st ） 返回串st 的长度；
判串 返回联接
empty （st ） 判串空函数
{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）
注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11
）（12）
第 4 页，共 78 页
是否相等的函数；
之后的串；
sub （S , i , 1） 返回S 中第i 个字符；
栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符
如ch 是运算符，则入操作符栈s 判栈8是否为空
若读出ch 是操作数且栈为空，则按出错处理
若ch 是操作数且栈非空，则形成部分中缀表达式
取栈顶操作符 操作符取出后，出栈
将pre 的最后一个字符（操作数）加入到中缀式exp 的最后