资源描述：
《广东工业大学考试试卷 000复习样题答案 数据结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构复习样题答案一.单项选择题（共12分）1.B2.A3.A4.D5.C6.D7.B8.C二.填空题(共12分)9.数据对象、数据关系、基本操作10.从表中任一结点出发均可找到表中其他结点11.字符依次对应相同且长度相同12.3313.各结点均无左孩子14.n-115.在排序过程中需要访问外存16.散列三.解答题（共36分）JanFebMarAprJuneMayJulyAugSepOctNovDec成功的平均查找长度＝42/12ESCJSBSDISKSASFGS17．（5分）后序线索18.（10分）已知一个长度为12的表为（Jan，Feb，
2、Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）（1）试将表中元素依次插入到一棵初始为空的二叉排序树（字符串之间按字典顺序比较大小）。画出该二叉排序树，并求出等概率情况下查找成功的平均查找长度。（2）设哈希表长度为13，哈希函数H（k）=ëi/2û，其中i为关键字k中第一个字母在字母表中的序号（例如A和D的序号分别为1和4），用链地址法解决冲突。请画出通过依次插入表中元素所构造的散列表，并求出在等概率情况下查找成功的平均查找长度。0123456789101112MayAugSepNovDecFebJulyMa
3、rAprOctJuneJan成功的平均查找长度＝18/12-5-19.（5分）假设电文中仅由a到h共8个字母组成，字母在电文中出现的频度依次为7，19，2，6，32，3，21，10请画出由此构造的哈夫曼树（要求树中所有结点的左右孩子必须是左大右小），并写出这8个字母相应的哈夫曼编码。b1917c2d6e32f3a7h10g213833625113000000001111111字符哈夫曼码a111b010c01111d0110e00f01110g10h11020.（8分）若对序列（25，19，7，41，29，12，23，26）按升序排序，请分别给
4、出（1）步长为4的一趟希尔排序的结果；（2）初始大根堆。答：（1）（12，7，25，29，19，23，26，41）（2）（41，26，23，25，29，12，7，19）524319426138127721.（8分）对于右边的带权图G，请（1）画出G的邻接矩阵；（2）画出G的最小生成树。答：（1）（2）5243142327-5-四.算法题（共30分）22．（5分）函数f22定义如下，其中函数调用Insert(L,i,k)在顺序表L的第i位置插入k。voidf22(SqList&L,inti){if(i>0){f22(L,i-1);for(intk
5、=1;k<=i;k++)Insert(L,i,k);}}设有空顺序表L＝（），请写出调用递归函数f22(L,3)后（1）L的长度：6（2）L＝（1，2，3，2，1，1）23.（5分）算法f23(L)将带头结点的单链表L逆置。请在画线处填空。voidf23(LinkList&L){LinkListp=L->next;L->next=NULL;while(p){LinkLists=p->next;p->next=L->next;L->next=p;p=s;}}24.（5分）s是一个升序静态查找表，请简要说明函数调用f24(s,1,s.length,
6、k)的意义。intf24(SSTables,intlow,inthigh,KeyTypek){if(low>high)return0;intmid=(low+high)/2;if(k==s.elem[mid].key)returnmid;if(k>s.elem[mid].key)returnf24(s,mid+1,high,k);elsereturnf24(s,low,mid-1,k);}答：在s中递归折半查找k。-5-25．（5分）请对以下函数填空，实现求二叉树T中各结点的子孙总数，并填入结点的DescNum域中的算法。intf25(BiTr
7、eeT){if(!T)return-1;else{T->DescNum=f25(T->lchild)+f25(T->rchild)+2;returnT->DescNum;}}26．（5分）图的邻接矩阵表示和算法f26描述如下：#defineMaxNum5typedefstruct{charvexs[MaxNum];
intarcs[MaxNum][MaxNum];
intn,e;}MGraph;intf26(MGraphG,inti){intd=0;for(intj=0;j8、rcs[j][i])d++;}returnd;}已知一个图G的邻接矩阵如右所示，G.arcs=0011000100000111100011110(1)
