2018年北京市培养单位动物研究所862计算机软件基础之数据结构考研核心题库
● 摘要
一、算法设计题
1． 设有顺序放置的n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。
【答案】算法如下:
r 为含有n 个元素的线性表，元素是具有红、白和蓝色的砾石，用顺序存储结构存储
本算法对其排序，使所有红色栎石在前，白色居中，蓝色在最后
当前元素是红色
当前元素是白色
当前元素是蓝色
2． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。
【答案】算法如下:
在二叉树t 中査找结点值等于x 的结
点
结束
统计以t 为根结点的子树的叶结点数
n0
. 叶结点
输出并计数
结束
第 2 页，共 34 页
:
3． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N
的二叉树的存储结构。
和
分别指示结点i 的左儿子和右儿子，
，使
) 表示i 的左(右) 儿子为空。试写一个
存放结点i 的父亲；然后再写一个判别结点u 是否
算法，由L 和R 建立一个一维数组为结点V 的后代的算法。
【答案】算法如下:
和
是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组
T 数组初始化
若结点i 的左子女是则结点L 的
双亲是结点
i
若结点i 的右子女是R , 则R 的
双亲是
i
判断U 是否是V 的后代
4． —个有向图G=(V，E) 的平方图
，使得表示。
【答案】算法如下:
5． 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15) 用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？
【答案】算法如下:
第 3 页，共 34 页
本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代
满足下述性质
:
当且仅当存在某个顶点
且
22
。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表
关键字
链指针
用链地址法解决冲突，构造哈希表，哈希函数用
初始化
输入n(本例中n=9)
个关键字按题意x 互不相同
4等插入结点链入同义词表
构造的哈希表如图所示:
图构造的哈希表
查找成功时的平均查找长度
。
二、应用题
6． 设某文件经内排序后得到100个初始归并段(初始顺串) ，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？
【答案】设归并路数为k ，归并趟数为s ，则即最少5-路归并可以完成排序。
，因
，且k 为整数，故k=5，
第 4 页，共 34 页