2017年南京航空航天大学541计算机综合基础之数据结构(C)语言版复试实战预测五套卷
● 摘要
一、应用题
1． 请阅读下列算法，回答问题。
问题一：这是什么类型的排序算法，该排序算法稳定吗？
问题二：设置|的作用是什么? 若将WHILE--DO 语句中判断条件改为该算法将会有什么变化，是否还能正确工作？
【答案】问题一：此为直接插入排序算法，该算法稳定。
问题二：
采用的作用是监视哨，免去每次检测文件是否到尾，提高了排序效率。 描述算法后，算法变为不稳定排序，但能正常工作。
为关键字，用 2． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：
造出哈希表，试回答下列问题：
（1）画出哈希表示意图；
（2）若查找关键字63，需要依次与哪些关键字比较？
（3）若查找关键字60，需要依次与哪些关键字比较？
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
【答案】（1）哈希表示意图如表所示：
表 哈希示意图
线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）
（2）查找关键字63时，由于
63比较。
第 2 页，共 35 页 所以需要依次与31，46，47，32，17，
（3）查找关键字60时，由于
（4） 哈希地址12内为空，查找失败。
3． （1）对于有向无环图，叙述求拓扑有序序列的步骤；
（2）对于图1，写出它的四个不同的拓扑有序序列。
图1
【答案】（1）对有向图，求拓扑序列步骤为：
1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。
2）在图中删除该顶点及所有以它为尾的弧。
3）重复1）和2）, 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。
（2）拓扑有序序列如图2:
图2 拓扑有序序列
4． 画出对算术表达式
表所示。
表 操作数栈和运算符找的变化过程 求值时操作数栈和运算符栈的变化过程。 求值，过程如【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式
第 3 页，共 35 页
5． 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树；
（2）若查找元素54，需依次与哪些元素比较？
（3）若查找元素90，需依次与哪些元素比较？
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
【答案】（1）判定树如图所示：
图 判定树
（2）若查找元素54，需依次和元素30、63、42、54比较，查找成功。 （3）若查找元素90，需依次和元素30、63、87、95比较，查找失败。 （4）
6． 下列广义表，可以唯一对应一棵二叉树的有？并归纳出唯一对应的条件。
第 4 页，共 35 页
相关内容
相关标签