３、答:由于地址空间为１0,且从10０开始,故散列函数选为Ｈ（key）=key%７＋1０0。
用线性探测再散列解决冲突，ASLｓucc=27/10
4、答：成功查找平均比较查找长度为：(n+1）／n[log2（n+１）]－1. 作业题二参考答案: 一、单项选择题
１、C 2、Ｃ 3、B ４、C ５、D 6、C 7、C 8、B 9、A 10、Ｃ 二、填空题 1、2ｎ0—1 ２、6，２61 3、 ?ｌoｇ2ｋ?＋1 4、２5 ５、N—1
6、最优二叉树，最小得二叉树 7、根结点，各子树 三、应用题 １、
答:不唯一,型对即可
9 6 3 22 13 7 4 此树得带权路径长度WＰL ＝9＊1＋6*2＋4＊3+（1＋２)＊４=45
1 2 2、 答： （1）插入10? ??? ?? 10
（5）插入2? (6)插入５ ??（7）插入４ 2 3 10 2 3 5 10 2 6 6 3 5 2 6 （8) 10 5 3 4 6 10 6 6 （2） 插入6
10 ? （3) 插入3?
10 （4)
6 调整 3 10 调整 3、答：当关键字为3时,比较次数为4; 当关键字为８时，比较次数为1； 当关键字为１9时,查找不成功； 4、答：（2)略
（3)深度优先遍历序列：AＢCDE广度优先遍历序列:ABCED(4）关键路径A—－Ｂ（长１00） 作业题三参考答案: 一、单项选择题
1、Ｄ 2、B 3、Ａ 4、Ｃ 5、Ｄ ６、Ａ 7、B ８、Ｃ 9、B 10、D 二、填空题 １、２，３ 2、4 3、n—１ 4、e
５、相同类型数据，地址连续 ６、三元组顺序表，三元组 7、 矩阵转置 三、应用题 １、 答： ? ? ?
B E C A ? ? ? ?? ?? ??? ① 二叉链表 ? ? ② ∧ ?? ? ⑦ ∧ ?? ? ? ③ ∧ ⑥ ∧ ?(2?? ∧ ④ ∧ ⑤ ? ? ?
2、答： ∧ ⑧ ∧ ∧ ⑨ ∧ 3、 答:Pｒｉｍ算法构造最小生成树得步骤如２4题所示,为节省篇幅,这里仅用Krｕskal算法，构造最小生成树过程如下：（下图也可选（２，４)代替(3，4），（５,6）代替(1，5)）
D
即:
4、 答：由完全二叉树得定义可知，除最后一层外,其她各层得结点就是满得。设该完全二叉树有d层，则除最后一层外各层得结点个数分别为:1，2，4，８，16，32，…,即第i层得结点个数为2ｉ—１。这里第８层有8个结点，显然第８/层就是最后得一层,那么第7层得结点个数为27—１=64个,其中得４个结点有8个叶子结点,余下得为叶子结点，个数为64—4=6０,所以该完全二叉树得叶子结点个数为６0+８＝6８个。 ５、 答：对应得二叉树形式如图所示：
作业题四参考答案: 一、单项选择题
1、 A 2、 B 3、 D ４、 Ｂ6、Ｃ ７、C 8、Ｃ 9、B 10、D 二、填空题 1、 答：前一个位置
2、 答：数组元素，数组元素,维数 3、 答：邻阵矩阵,邻接表 4、 答:９，4
5、 答:[48 44］ 52 [64 8０ 91] 6、1，2 三。判断 1、 答：√ 2、 答：× 3、 答:× 4、 答:√ ５、 答:√ 四、应用题
1、 答:模式p得nexｔ函数值如下：
D
５、
2、 答：A共120个字节。
a４，5得起始地址为:1116.
按行优先存储时,a2，５得起始地址为：１068。 按列优先存储时,a2,5得起始地址为:1１08。
3、 答:(1）哈希函数H（key)＝（关键字各字符编码之与)MOD 7 （２）
4、 答：一趟快速排序：22，19，13,6,2４，38,43，32
初始大堆:４3，3８，32，２2,2４，6，13,19
二路并归:第一趟：19,２4，32，４3,６，38，13,22 第二趟：１9,24，32，43，6，１3，22,38
第三趟：６，13，１9，22,24,3２,38,43 堆排序辅助空间最少，最坏情况下快速排序时间复杂度最差。 作业题五参考答案： 一、单项选择题 1、 答：C ２、Ｄ ３、D
4、 答:C ５、 答：B ６、 答：A ７、 答:Ｄ 8、 答:Ｂ 9、 答：C 10、 答:A 二、填空题 1、1,n－1 2、６０ 3、2 4、快速排序 5、简单选择排序 6.数据,指针,数据，指针 三 判断 1、 答：√ 2、 答：× 3、 答:× 4、 答：√ ５、 答：× 四、应用题
1、 答：该十字链表有一个十字链表表头结点，ｍａｘ（ｍ,ｎ）个行列表头结点。另外,每个非零元素对应一个结点,即k个元素结点，所以共有maｘ(m，n）＋ｋ+1个结点。
2、 答:（1）最小生成树得定义略。(2)最小生成树有两棵。(限于篇幅，下面得生成树只给出顶点集合与边集合，边以三元组(Vｉ，Ｖj,Ｗ)形式）,其中Ｗ代表权值。V(G)={１,２，3，4，5｝ Ｅ1(G）={(4，5,2），(2，5，4），(２,3，５),（1,2，7)｝；Ｅ2(Ｇ)=｛（4，5,２)，（２，4，4),(2，３，5）,(１,2，7）｝ ３、 答：采用顺序查找法：文件中记录可以以任意持续存放。 采用折半查找法：文件中得记录必须按照关键字从小到大有序存放。
采用分块查找法：将文件分成若干个块，每一个快中得记录可以任意得存放,但块之间得必须按照关键字从小到大得次序存放，即前一块中得所有记录得关键字得值必须小于后一块得所有记录得关键字得字值。 4、 答:排序过程如下：
（1)［］８8,３３，22,5５，99，11，66 （２）［1１］，33，22,55，９9，88，66 (3）[11，22］,３3,55，99，８8，６6 (４）［１１，22，３３］，5５,99，88，66 （５)［１1,２2，33,55］,9９，88,66 （６)[１1,2２，33,55,66］，99，8８ （7)［１1,22,33,55，66,88］,99
数据结构专升本模拟题及参考答案
