2017年云南大学软件学院842数据结构与程序设计考研冲刺密押题

目录

2017年云南大学软件学院842数据结构与程序设计考研冲刺密押题（一） (2)

2017年云南大学软件学院842数据结构与程序设计考研冲刺密押题（二） (8)

2017年云南大学软件学院842数据结构与程序设计考研冲刺密押题（三） (14)

2017年云南大学软件学院842数据结构与程序设计考研冲刺密押题（四） (20)

2017年云南大学软件学院842数据结构与程序设计考研冲刺密押题（五） (25)

第1 页，共29 页

2017年云南大学软件学院842数据结构与程序设计考研冲刺密押题（一）

注意：①本试题所有答案应写在答题纸上，不必抄题，写清题号，写在试卷上不得分；

②答卷需用黑色笔（钢笔，签字笔，圆珠笔）书写，用铅笔、红色笔等其他颜色笔答题，

试题作废；

③答卷上不得做任何与答题无关的特殊符号或者标记，否则按零分处理；

④考试结束后试题随答题纸一起装入试题袋中交回。————————————————————————————————————————一、填空题

1．高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

2．有五个数据依次入栈：1，2,3,4,5。在各种出栈的序列中，以3,4先出栈的序列有_____。（3在4之前出栈）

【答案】3个

【解析】以3,4先出栈的序列有34521、34215、34251共3个。

3．模式串的next函数值序列为_____。

【答案】01122312

4．G是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

5．线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。

【答案】（n－1）/2

【解析】删除第一个元素需要移动n－i次，以此类推，删除最后一个元素需要移动0次。平均次数为

6．表达式的后缀表达式是_____。

【答案】

7．试利用下列栈和串的基本操作完成下述填空题。

initstack（S）置S为空找；

push（S,X）元素X入找；

第2 页，共29 页

第 3 页，共 29 页

pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；

置串为空串；

length （st ） 返回串st 的长度；

判串是否相等的函数；

返回联接

之后的串；

sub （S ,i ,1） 返回S 中第i 个字符；

empty （st ） 判串空函数

{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true ,否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）

注意：毎个空格只填一个语句。 【答案】（1）栈S 初始化为空栈 （2）串exp 初始化为空串 （3）判取出字符是否是操作符

（4）如ch 是运算符，则入操作符栈s （5）判栈8是否为空

（6）若读出ch 是操作数且栈为空，则按出错处理

（7）exp （8）若ch 是操作数且栈非空，则形成部分中缀表达式

（9）exp

第 4 页，共 29 页 （10）

取栈顶操作符 （11

）

操作符取出后，出栈 （12）将pre 的最后一个字符（操作数）加入到中缀式exp 的最后

8． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】

【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为

9． 在有n 个顶点的有向图中，每个顶点的度最大可达。

【答案】2（n-l ）

【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。

10．设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素

的存储地址为_____；若以列序为主序顺序存储，则元素的存储地址为_____。

【答案】9174；8788

【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，

则它的存储地址为

若以列序为主存储顺序，则它的存储地址为

11．对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间.复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。 【答案】

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

12．顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】

【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。

13．分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ）

，而快速排序算法需要比较的次数达到最大，时间复杂度为