资源描述：
《数据结构试卷2009a答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、哈尔滨工业大学（威海）2008/2009学年春季学期数据结构试题卷（A）答案一、单择题（每小题2分，共20分）题号12345678910答案CCCADDCABD二、填空题（每小题2分，共20分）题号答案题号答案10,1,1,2,1,1,2,3,4,365v1v2v3v5v4v6v72ABDEGCFH7v1v2v6v3v4v7v532n-18循环4q->next=q->next->next951k-152103三、应用题（共60分）1.有如下递归函数fact(n),分析其时间复杂度。(本题4分)fact(intn){if(n<=1)教研室主任签字：第1页共1
2、0页return1;elsereturn(n*fact(n-1));}答：设求n的阶乘需运行f(n)次。f(n)=f(n-1)+cf(n-1)=f(n-2)+c………….f(3)=f(2)+cf(2)=f(1)+cf(1)=2;f(n)=2+(n-1)c时间复杂度为O(n)2.写一算法，实现单链表的逆置，不需要辅助空间。(用C或C++描述)(本题6分)（1）存储结构（1分）（2）算法(5分)答：(带头结点的单链表)structcelltype{elementtypeelement;celltype*next;};typedefcelltype*LIST;t
3、ypedefcelltype*position;voidreverse(LISTL){positionp,q;p=L->next->next;L->next->next=null;while(p!=NULL){q=p->next;p->next=L->next;L->next=p;p=q;}}教研室主任签字：第2页共10页3.已知一组关键字为（10，24，32，17，31，30，46，47，40，63，49），设哈希函数H（key）＝key%13。请写出用线性探测法处理冲突构造所得的哈希表。(本题4分)答：0123456789101112494017313
4、23046471024634.已知二叉树中的结点类型BinTreeNode定义为：structBinTreeNode{ElemTypedata;BinTreeNode*left，*right};其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是返回二叉树BT中值为x的结点所在的层号，请补全最内层else所包含的内容。(本题5分)IntNodeLevel(BinTreeNode*BT，ElemTypeX){if(BT==NULL)return0;//空树的层号为0elseif(BT->data＝＝X)return1
5、;//根结点的层号为1else{//向子树中查找x结点}}答：intcl＝NodeLevel(BT一>left，X)；if(cl>＝1)returncl+1;intc2＝NodeLevel(BT一>right，X)；if(c2>=1)returnc2十1//若树中不存在X结点则返回0elsereturn0；教研室主任签字：第3页共10页5.下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路。(本题6分)(1)画出所有可能的方案(本题3分)(2)描述你所选方案对应
6、的算法概要。(本题3分)16v1v22111619v66v333145v518v4答：(1)教研室主任签字：第4页共10页(2)或教研室主任签字：第5页共10页6.设A～H8个字符出现的概率为:={0.10,0.16,0.01,0.02,0.29,0.10,0.07,0.25}。设计最优二进制编码（用0,1编码）（本题7分）(1)画出最优二叉树（5分）(2)计算平均码长。（2分）答：最优二进制编码不惟一，但WPL惟一。01.0000.450.5500.200.250.260.2900.100.1000.030.07A0.100.160.010.02A：0
7、01平均码长为：B:101ΣPiWi=C:00000=3×（0.1＋0.16＋0.1）D:00001＋5×（0.01+0.02）E:11+2×（0.29+0.25）F:100+4×0.07G:0001=2.59H:017.一棵二叉树的繁茂度d定义为各层结点数的最大值w与树的高教研室主任签字：第6页共10页度h的乘积。试写一算法，求二叉树的繁茂度。（本题8分）答：法一：要用层次遍历以及队列来处理，可以增设一个宽度计数器，在统计完每一层的结点个数之后,再从计数器中挑出最大值。typedefstruct{BTNodenode;intlayer;//layer是结
8、点所在层数}BTNRecord,r;intWidth(Bitree
