2003级数据结构试卷a

《2003级数据结构试卷a》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、安徽大学2004-2005学年第2学期《数据结构》试卷年级专业姓名学号座位号大项一二三四总分阅卷人登分得分一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题干后的括号内。每小题2分，共20分）1．深度为k(k>2)的完全二叉树的最少的叶结点数是。A2k-2-1B2k-2C2k-1-1D2k-12.利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素35要进行元素间的比较。A4次B5次C7次D10次3．把如下树转换成二叉树时，结点C是结点。ADCBA.A的左孩子B.B的左孩子C.A的右孩子D.B的右孩子4．用一维数组

2、作为完全二叉树的存储结构，根据堆的定义，下面四个一维数组表示的序列中，为堆。A7565301525452010B7565451030252015C7545653015252010D7545651025302010第2页，共6页学生答题注意：勿超黑线两端；注意字迹工整。图表清晰。第1页，共6页学生答题注意：勿超黑线两端；注意字迹工整。图表清晰。5．下面的二叉树中，不是完全二叉树。ABCD6．用线性探测法查找哈希表，可能要探测多个哈希地址，这些位置上的关键字值A一定是同义词B一定都不是同义词C都相同D不一定都是同义词7.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，

3、至少要进行次探测。Ak-1次Bk次Ck+1次Dk(k+1)/2次8．用二分查找法在有序表中进行查找的过程可用一棵判定树来描述,如有序表中共有n个结点,则此判定树的高为。A．n-1B．C．+1D．n+19．用顺序查找法对具有n个结点的线性表查找一个结点所需的平均比较次数为。AO(n2)BO(n)CO(n)DO()10．下列排序算法中，可能出现如下情况：在最后一趟排序之前，所有元素均不在其最终位置上。A快速排序B冒泡排序C堆排序D插入排序得分二、填空题（每空2分，共24分）1．n个顶点的生成树有条边。2．n个结点二叉链表中的空链域个数是。3．对二叉排序树进行遍历，就可以得到排好序的顶点序列

4、。4．单链表的结点有两个域：数据域（data）和指针域（next）,一个带头结点的单链表H的第一个元素的结点的指针为。5．树的三种存储结构是、和。6．Head【Tail【Head【((a,b),(c,d))】】】=7．快速排序算法在平均时间复杂度为。8．一个“好”的算法要考虑以下标准：正确性、、、。得分三、应用题(每小题8分，共40分)1．已知散列表的地址空间为0-13，散列函数为H（K）=Kmod13,分别用（1）线性探查法；（2）链地址法处理冲突。将元素(24，35，46，70，78，44，55，111，90，113，43，41)依次插入到初值为空的散列表中，画出该表。第3页，共6

5、页学生答题注意：勿超黑线两端；注意字迹工整。图表清晰。第4页，共6页学生答题注意：勿超黑线两端；注意字迹工整。图表清晰。2．设F={T1，T2，T3}是森林（如下图所示），试画出所对应的二叉树。KJIHGFABCDE3．对下面数据表，写出采用快速排序的每一趟的结果。251122345447661100314120解：4．数据集{3，4，6，7，9，11，16，24，20}为叶结点的权值，构造一棵哈夫曼树，并给出每一个叶结点的编码。5．一个带权的无向图如下所示，求该图上一棵最小生成树。3124531152263得分四、算法题（每小题10分，共20分）1．二叉树以二叉链表存储，设计算法求二

6、叉树中度为2的结点的个数。解：第6页，共6页学生答题注意：勿超黑线两端；注意字迹工整。图表清晰。2.假设两个带头结点的链表head和list中的结点值都是整数，且按结点值的递增次序链接起来的链表。在各链表中，每个结点的值各不相同，但head和list可能有值相同的结点（表头结点除外）。编写算法将链表head合并到链表list中，使得合并后的链表是按结点值递增次序链接起来的带头结点的链表，且链表中各个结点的值各不相同。第5页，共6页学生答题注意：勿超黑线两端；注意字迹工整。图表清晰。《数据结构》试卷参考答案与评分标准一、单项选择（每小题2分，共20分）1．C2.C3.D4.A5.A6.B

7、7.C8.C9.C10．B二、填空题（每空2分，共24分）1.n-12.时间随问题规模的增长率3．中序遍历4．H^.next5.双亲表示法、孩子表示法、孩子兄弟表示6.2k-17.O(nlongn)8.可读性、健壮性、效率与低存储需求三、应用题(每小题9分，共36分)（1）线性探测法0123456789101112136528423057313398221001177（2）开散列表--链地址法65NULL042NULL1228NULL30NUL