安徽大学2007年度硕士研究生入学考试真题

1、安徽大学2007年度硕士研究生入学考试数据结构试卷D大项-一-二二三四总分阅卷人登分一、单项选择(在备选答案中选出一个正确答案，并将其号码填在题干后的括号内。每小题2分，共20分)1 深度为k的完全二叉数的最少结点数是 A 2 k-1B 2 k-1 C 2 k-1 - 1 D 2 k得分6 .用线性探测法查找哈希表，可能要探测多个哈希地址，这些位置上的关键字值 A 一定是同义词B 一定都不是同义词C 都相同D 不一定都是同义词2.利用逐点插入法建立序列(50, 72, 43, 85, 75, 20, 35, 45, 65, 30)对应的二叉排 序树以后，查找元素 35要进行元素间的比较。A 4

2、次 B 5次 C 7次 D 10次7. 一个队的输入序列是A4, 3, 2, 1 B1, 2, 3, 4,则队列的输出是序列是1, 2, 3, 4 C 3, 2, 4, 13 .把如下树转换成二叉树时，结点C是结点B的左孩子&利用逐点插入法建立序列(50 , 72 , 43 , 85 , 75 , 20 , 35 , 45 , 65 , 30)对应的二叉排序树以后，查找元素35要进行元素间的比较。A 4次 B 5次 C 7次 D 10次9 .用顺序查找法对具有n个结点的线性表查找一个结点所需的平均比较次数为A 0(n ) B O(nlog； ) C 0(n)D O (logn )C. A的右孩

3、子D. B的右孩子4.下列序列中， 是堆。A (100,80,55,60,50,40,58,35,20)C (100,80,55,58,50,40,60,35,20)B (100,80,55,60,50,40,35,58,20)D (100,70,55,60,50,40, 58, 35,20)10 .快速排序属于 A .插入排序B .交换排序C .选择排序D .合并排序、填空题(每空2分，共24分)得分第1页，共6页学生答题注意：勿超黑线两端；注意字迹工整。5.下面的二叉树中， 不是平衡二叉树。AB第2页,共6页学生答题注意：勿超黑线两端；注意字迹工整。1. n个顶点的生成树有 条边。2 有K

4、个叶子结点的哈夫曼树，其结点的总数为2.从空二叉排序树开始，依次将序列40, 35, 24, 10, 20, 50, 45, 70中关键字插入二叉排序树，用图表示出这个过程。3. Tail 【Head 【Tail 【(a, b ) , ( c , d )】=4.平衡二叉树的平衡因子为5.树的三种存储结构是6 .双向循环链表的结点结构为 所指结点为尾结点的条件是llinkdatarli nkOL中，指针p7 .堆排序算法在平均时间复杂度为8.将pascal语言的整型数组 A0.8,0.8按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A7,3的地址是。三、应用题(每小题9分，共36

5、分)得分1 .已知散列表的地址空间为0-13，散列函数为 H ( K) =Kmod 13,分别用(1)线性探查法；(2)链地址法处理冲突。将元素 (24, 35, 46, 70, 78, 44, 55 , 111, 90, 113, 43, 41)依次插入到初值为空的散列表中，画出该表。3 .对下面数据表，写出采用快速排序的每一趟的结果。(35213244155486711101324130 )解：4.数据集 4, 7, 9, 11, 16, 23, 30 为叶结点的权值，构造一棵哈夫曼树，并给出 每一个叶结点的编码。第3页，共6页学生答题注意：勿超黑线两端；注意字迹工整。第4页，共6页学生答

6、题注意：勿超黑线两端；注意字迹工整。1到其余各点的最短路径及长度（给出求解的过程）5求下列有向图中从点2.编写算法完成按递增次序打印给定的链表head中各结点的操作。打印的方法是每一次寻找链表中值最小的结点，打印该结点后，把它从链表中删除，重复次操作直到链表结束为 空为止。得分，设计算法求二叉树中所有结点四、算法题（每小题 10分，共20分）1.二叉树以二叉链表存储，每个结点只有一个整型数据域 的数据和。解：第5页，共6页学生答题注意：勿超黑线两端；注意字迹工整。第6页，共6页学生答题注意：勿超黑线两端；注意字迹工整。在家庭生活中，父亲有大格局，就是在家庭遭遇困难或变故时，不退缩，能够顶住压力

7、。对待家庭小的损失不斤斤计较，不浑浑噩噩混日子，积极对待生活，对于家庭发展有大致的规戈叽蒙田曾说： 作为一个父亲，最大的乐趣就在于：在其有生之年，能够根据自己走过的路来启发教育子女一个父亲胜过一百个老师，父亲是孩子在人生中接触的第一个男性形象，他肩负着帮助孩子正确认识世界，了解社会的重任。父亲在教育孩子过程中有大格局，孩子才能健康茁壮成长, 才能为家庭的兴旺积蓄后备力量。在教育孩子中，父亲的大格局体现在不给孩子贴标签，懂得孩子的品格比能力更重要。说到才女，不少人会想到民国时的合肥四姐妹”进而感叹合肥张家是个风水宝地。父亲的格局决定家庭的方向一个家庭的福气运道，不是凭空出现的，它是家庭成员共同努力得来的。家庭要想和谐兴旺，首先要走对方向，父亲的格局就决定着家庭的发展方向。曾国藩曾说： 谋大事者首重格局 ”心中格局的大小，决定了眼光是否长远，眼光是否长远又决定了事物的成败家庭的发展不是一个一蹴而就的过程，家庭需要经营，需要规划。由于社会分工的不同，父亲作为家庭中的男性，承担着家庭领导者的职能，是家庭权威”的代表。作为家庭列车的火车头，父亲的眼光要远，格