《数据结构试卷2009A答案》由会员分享，可在线阅读，更多相关《数据结构试卷2009A答案（10页珍藏版）》请在金锄头文库上搜索。
1、 教研室主任签字： 第 1 页 共 10 页 哈尔滨工业大学（威海） 2008/2009 学年 春 季学期 数据结构 试题卷（ A） 答案 一、 单 择题（每 小题 2分，共 20分） 题号 1 2 3 4 5 6 7 8 9 10 答案 C C C A D D C A B D 二 、填空题（每 小题 2分，共 20分） 题号 答案 题号 答案 1 0,1,1,2,1,1,2,3,4,3 6 5 2 ABDEGCFH 7 v1v2v3v5v4v6v7 v1v2v6v3v4v7v5 3 2n-1 8 循环 4 q-next=q-next-next 9 51 5 2k-1 10 3 三 、应用题
2、（共 60 分） 1.有如下递归函数 fact(n),分析其时间复杂度。 (本题 4分 ) fact(int n) if (nnext-next; L-next-next=null; while(p!=NULL) q=p-next; p-next=L-next; L-next=p; p=q; 教研室主任签字： 第 3 页 共 10 页 3.已知一组关键字为（ 10， 24， 32， 17， 31， 30， 46， 47， 40， 63， 49），设哈希函数 H（ key） key%13。请写出用线性探测法处理冲突构造所得的哈希表。 (本题 4分 ) 答： 0 1 2 3 4 5 6 7 8 9
3、 10 11 12 49 40 17 31 32 30 46 47 10 24 63 4.已知二叉树中的结点类型 BinTreeNode 定义为： structBinTreeNode ElemType data; BinTreeNode*left， *right; 其中 data为结点值域， left和 right分别为指向左、右子女结点的指针域。下面函数的功能是返回二叉树 BT中值为 x的结点所在的层号，请 补全最内层 else所包含的内容 。 (本题 5分 ) Int NodeLevel(BinTreeNode * BT， ElemType X) if(BT=NULL)return 0;/
4、空树的层号为 0 else if(BT-data X) return 1;/根结点的层号为 1 else/向子树中查找 x结点 答： int cl NodeLevel(BT 一 left， X)； if(cl 1)return cl+1; int c2 NodeLevel(BT 一 right， X)； if (c2=1)returnc2 十 1 /若树中不存在 X 结点则返回 0 else return 0； 教研室主任签字： 第 4 页 共 10 页 5.下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的
5、n-1条公路 。 (本题 6 分 ) (1)画出所有可能的方案 (本题 3分 ) (2)描述 你 所选方案对应的 算法 概要 。 (本题 3分 ) 答： (1) v2 v4 v1 v5 v3 v6 16 21 11 14 33 6 19 18 6 5 教研室主任签字： 第 5 页 共 10 页 (2) 或 教研室主任签字： 第 6 页 共 10 页 6.设 A H 8个字符出现的概率为 :=0.10, 0.16, 0.01, 0.02, 0.29, 0.10, 0.07, 0.25。 设计最优二进制 编 码 （用 0,1 编码） （本题 7 分） (1)画出最优二叉树 （ 5分） (2)计算平
6、均码长。 （ 2分） 答： 最优二进制编码不惟一，但 WPL 惟一。 7.一棵二叉树的繁茂度 d 定义为各层结点数的最大值 w 与树的高0 1.00 0 0.45 0.55 0 0.20 0.25 0.26 0.29 0 0.10 0.10 0 0.03 0.07 A 0.10 0.16 0.01 0.02 A： 001 B: 101 C: 00000 D: 00001 E: 11 F: 100 G: 0001 H: 01 平均码长为： PiWi= =3（ 0.1 0.16 0.1） 5（ 0.01+0.02） +2（ 0.29+0.25） +4 0.07 =2.59 教研室主任签字： 第 7
7、 页 共 10 页 度 h的乘积。试写一算法，求二叉树的繁茂度。（本题 8分） 答： 法一： 要用层次遍历以及队列来处理，可以增设一个宽度计数器，在统计完每一层的结点个数之后 ,再从计数器中挑出最大值。 typedef struct BTNode node; int layer; /layer 是结点所在层数 BTNRecord, r ; int Width(Bitree T ) /求树宽 int count ; /增开 count 向量，存放各层对应的结点数 InitQueue(Q); /队列初始化， Q 的元素为 BTNRecord 类型 EnQueue(Q,T, 0); / 根 结 点
8、入 队 , 0 表示 count0 ，下标值 while(!QueueEmpty(Q) DeQueue(Q, r); /结点出队 countr.layer+; /出队时再把结 点对 应层 的计 数器加 if(r.node-lchild) EnQueue(Q,r.node-lchild, r.layer+1); if(r.node-rchild) EnQueue(Q,r.node-rchild, r.layer+1); /按层序入队时要随时标注结点所在层号 h=r.layer; /最后一个队列元素所在层就是树的高度 for(maxn=count0, i=1; h; i+) if(countima
9、xn) maxn=counti; /求出哪一层结点数最多 return (h*maxn) / Width 法二：若不用辅助数组，不用层数分量也可以，关键在于如何区别层与层。有两种方法： 一、通过比较指针判断是否到达新的一层的开始 ; 二、通过比较指针判断是否到达当前层的末尾 . 由于方法一对新的一层的开始点不易确定，比较次数要多于第二种，因此推荐第二种。 对任意种类的树都适用，二叉树类似可得。 算法如下： /- / TreeWidth 求树的宽度 / 不用辅助数组，不用层数分量 / 思路： / 1.以两个整型变量存宽度，一个表示当前层的节点数，一个表示当前已知最大宽度，当遍历完一层后立即判断两
10、者大小，保留大者。 / 2.通过比较指针判断是否到达本层的末尾，以确定层与层间的关系。 教研室主任签字： 第 8 页 共 10 页 /- int TreeWidth(TreeNode * T) int iMaxCount=0,iRecCount=0;/iRecCount 当前层的节点数 ,iMaxCount 当前已知最大宽度 TreeNode * pP=T,* pLastChild=T;/pP 指向当前节点 ,pFirstChild 指向本层最末节点 InitQueue(Q);/队列初始化， Q 的元素为 TreeNode*类型 EnQueue(Q,T);/根结点入队 while(!Queue
11、Empty(Q) DeQueue(Q,pP);/结点出队 iRecCount+;/出队时再把结点所在层的计数器加 1 if(hasChild(pP) EnQueue(Q,pP-Child);/有孩子则孩子入队 if(pP=pLastChild)/若到达本层的末尾 /先决定 iMaxCount，再重置 iRecCount /求繁茂度不能清零此变量。 iMaxCount=max(iMaxCount,iRecCount); iRecCount=0; QueueTail(Q,pLastChild); /读出队尾元素，注意不是出队 ! /既已到本层末尾，又已将其孩子入队 (若有的话 )，则队尾元素必为下
12、一层的最末元素 return iMaxCount; 8.欲将无序序列（ 24, 79, 13, 36, 70, 96, 12, 10, 36*, 49, 100, 27）中的关键码按升序重新排列 。 (本题 10分 ) (1)请写出快速排序第一趟排序的结果序列 ，以 24 为参照 。 （ 3分） (2)另外请 分别 画出堆排序（小根堆）的 无序堆 (完全二叉树 )和 初始堆。 （ 3分） (3) 用 C或 C+给出堆排序的筛选算法 (4分 ) 答：快速排序第一趟排序的结果序列为： 10， 12， 13， 24， 70， 96, 36, 79, 36*, 49, 100, 27 堆排序的初始堆如
13、下，注意要从排无序堆开始，从最后一个非终端结点开始，自下而上调整 ,而且要排成小根堆！ 初始堆序列为： 10， 24， 12， 79， 49， 27， 13， 36， 36*, 70, 100, 96 24 79 13 36 70 96 12 10 36*49 100 27 10 24 12 79 49 27 13 36 36*70 100 96 教研室主任签字： 第 9 页 共 10 页 无序堆 有序初始堆 SIFT(int i,int n,LIST A) int j; records temp; temp=Ai;j=2*i; while (jA2*r.key) swap(Ar,A2*r); r=last; else if(Ar.key)A2*r.ke
