郑州轻工业学院09-10学年第2学期数据结构试题(B卷)

1、请画出该二叉树，并写出其先序遍历序列（7分）20092010学年第二学期期末考试数据结构试题 B一、单项选择题（每道选择题只有一个正确答案；共15小题，每小题2分，共30分）1 数据结构是【】。A. 种数据类型B 数据的存储结构C 一组性质相同的数据元素的集合D.相互之间存在一种或多种特定关系的数据元素的集合2. 线性表采用链式存储时，结点的存储地址【】。A.必须是不连续的B. 连续与否均可 C 必须是连续的 D 和头结点的存储地址相连续3. 若线性表最常用的操作是存取第 i个元素及其前驱元素的值，则采用【】存储方式最节省时间。A单链表 B 双向链表 C 单循环链表 D 顺序表4. 设栈S和队

2、列Q的初始状态均为空，元素a,b,c,d,e,f,g 依次进入栈S。若每个元素出栈后立即进入队列Q且7个元素出队的顺序是b,d,c,f,e,a,g ，则栈S的容量至少是【 】。 A . 1 B . 2 C . 3 D . 45. 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓存区， 主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是【】。A 栈B 队列 C 树 D 图6排序算法的稳定性是指【】。A 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变B经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变C算法的排序性能与

3、被排序元素的数量关系不大D算法的排序性能与被排序元素的数量关系密切7 在下列排序方法中，【】的比较次数与记录的初始排列状态无关。A.直接插入排序 B.起泡排序 C.快速排序 D.简单选择排序&在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系【】。A.不一定相同B .都相同C.都不相同D .互为逆序9二维数组A89按行优先顺序存储，若数组元素A23的存储地址为1087,A47的存储地址为1153,则数组元素A67的存储地址为【】。A. 1207 B . 1209 C . 1211 D. 121310. 若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树

4、是【】。A .二叉排序树B .哈夫曼树C .堆D . AVL树11. 栈中元素的进出原则是【】。A.先进先出 B.后进先出C.栈空则进D.栈满则出12. 数组Q 20用来表示一个循环队列，f为当前队列头元素的位置，r为队尾元素的后一位置，若队列的长度和队头指针值分别为13和17,则当前尾指针的值为【】。A.8B . 9C . 10D. 1113. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是【】A.9B . 11 C. 15 D .不确定14. 一棵具有n个结点的完全二叉树的树高度（深度）是【】。A. Jogn +1 B . logn+1C . IljognD .

5、 logn-115. 引入二叉线索树的目的是【】。A加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删除C. 为了能方便的找到双亲D .使二叉树的遍历结果唯一二、应用题（共5题，共计50分）1. 已知一棵二叉树的中序遍历结果为GDHBAEC,后序遍历结果为 GHDBEIFCA3. 已知带权图的邻接表如下所示，其中边表结点的结构为:依此邻接表：（1）写出从顶点 C出发进行深度优先搜索的遍历序列；（2）写出从顶点 C出发进行广度度优先搜索的遍历序列；（3） 按照PRIM算法画出从顶点 C出发求最小生成树的过程。（15分）4. 已知某系统在通信联络中只可能出现8种字符（a, b, c

6、, d, e, f ,g, h），其概率分别为 0.05， 0.29，0.07，0.08，0.14，0.23，0.03，0.11，试画出对 应的编码Huffman树（请按照左子树根结点的权小于等于右子树根结点的权的 次序构造），求每种字符的 Huffman编码。（12分）5 .设哈希（Hash）表的地址范围为 017,哈希函数为：H （ K）= K MOD 16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49）造出Hash表，试回答下列问题：（11分）（1）画出哈希表的示意图；（2）若查找关键字6

7、3,需要依次与哪些关键字进行比较？（3）若查找关键字60,需要依次与哪些关键字比较？（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。四、编程题（每题 10分，共20分）1.设有一个单向循环链表结构，first是指向头结点的指针。（1 ）请编写一个算法，将此链表中数据最小的结点从链表中删除。（2）请分析你的算法的时间复杂度。2. 给出算法分别求出二叉树的叶结点、度数为1的结点、度数为2的结点的个数。一个处处像别人表明自己优秀的，恰恰证明了他（她）并不优秀，或者说缺什么，便炫耀什么。对生活饱有热情，满足与一些小确幸，也要经得起诱惑，耐得住寂寞，内心始终如孩童般的纯真。要知道，你走的

8、每一步，都是为了遇见更好的自己，都是为了不辜负所有的好年华。一个真实的人，一定也是个有担当的。不论身处何地，居于何种逆境，他（她）们都不会畏惧坎坷和暴风雨的袭击。因为知道活着的意义，就是真实的直面风浪。生而为人，我们可以失败，却不能败的没有风骨，甚至连挑战的资格都不敢有。人当如玉，无骨不去其身。生于尘，立于世，便该有一颗宽厚仁德之心，便有一份容天下之事的气度。一个真实的人，但是又不会过于执着。因为懂得，水至清则无鱼，人至察则无徒的道理。完美主义者最大的悲哀，就是活得不真实，不知道审时度势，适可而止。一扇窗，推开是艳阳天，关闭，也要安暖向阳。不烦不忧，该来的就用心珍惜，坦然以对；要走的就随它去，

9、无怨无悔。人活着，就是在修行，最大的乐趣，就是从痛苦中寻找快乐。以积极的状态，过好每一天，生活不完美，我们也要向美而生。一个真实的人，一定是懂爱的。时光的旅途中，大多数都是匆匆擦肩的过客。只有那么微乎其微的人，才可以相遇，结伴同行。而这样的结伴一定又是基于志趣相投，心性相近的品性。最好的爱，不是在于共富贵，而是可以共患难，就像一对翅膀，只有相互拥抱着才能飞翔。爱似琉璃，正是因为纯粹干净，不沾染俗世的美。懂爱的人，一定是真实的人。正是因为懂得真爱的不易，所以更是以真面目面对彼此，十指紧扣，甘愿与爱的人把世间各种风景都看透，无论风雨，安暖相伴。一个真实的人，定然是有着大智慧的。人生在世，什么都追求好，追求完美，虽然这是一种积极的思想，却会很累，不仅自己累，身