广东工业大学考试试卷000复习样题答案数据结构

《广东工业大学考试试卷000复习样题答案数据结构》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构复习样题答案一.单项选择题《共12分〉I.B2.A3.A4.D5.C6.D7.B8.C二.填空题（共12分）9.数据对象、数据关系、基本操作10.从表中任一结点出发均可找到表中其他结点II.字符依次对应相同且长度相同12.3313.各结点均无左孩子14.n-115.在排序过程中需要访问外存16.散列三.解答题（共36分〉18.（10分）已知一个长度为12的表为成功的平均査找长度=42/12（Jan,Feb,Mar,Apr,May,June，July,Aug,Sep,Oct,Nov,Dec）（1）试将表中元素依次插入到一棵初始为空的二叉排序树（字符串之间按字典顺序比较大小）。画

2、出该二叉排序树，并求出等概率情况下查找成功的平均查找长度。（2）设哈希表长度为13,哈希函数H（k）=Li/2」，其中i为关键字k中第一个字母在字母表中的序号（例如A和D的序号分别为1和4）,用链地址法解决冲突。请画出通过依次插入表中元素所构造的散列表，并求出在等概率情况下查找成功的平均查找长度。012345678910111219.(5分)假设电文中仅由a到h共8个字母组成，字母在电文中出现的频度依次为7,19,2,6,32,3,21,10请画出由此构造的哈夫曼树(要求树中所有结点的左右孩子必须是左大右小)，并写出这8个字母相应的哈夫曼编码。字符哈夫曼码a111b010c01111

3、d0110e00fOHIO810h11020.(8分)若对序列(25,19,7,41,29,12,23,26)按升序排序，请分别给出(1)步长为4的一趟希尔排序的结果；(2)初始大根堆。答：(1)(12,7,25,29,19,23,26,41)(2)(41,26,23,25,29,12,7,19)算法题（共30分〉22.（5分）函数f22定义如下，其中函数调用Insert（L,i,k）在顺序表L的第i位置插入kovoidf22(SqList&L,inti){if(i>0){f22(L,i-1);for(intk=l;k<=i;k++)Insert(L,i,k);}}设有空顺序表L=(

4、),请写出调用递归函数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=NULLwhile(p){LinkLists=p->nextp->next=L->next;L->next=p24.(5分)s是一个升序静态查找表，请简要说明函数调用f24(s,1,s.length,k)的意义。intf24(SSTables,intlow,inthigh,KeyTypek){if(low>high)return0;

5、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-l,k);答：在S中递归折半查找k。25.(5分)请对以下函数填空，实现求二叉树T中各结点的子孙总数，并填入结点的DescNum域中的算法。intf25(BiTreeT){if(!_T)return-1;else{T->DescNum=f25(T->lchild)+f25(T->rchild)+_2；returnT->DescNum;}26.

6、(5分)图的邻接矩阵表示和算法f26描述如下:#defineMaxNum5typedefstruct{charvexs[MaxNum];intarcs[MaxNum][MaxNum];intn,e;}MGraph;intf26(MGraphG,inti){intd=0;for(intj=0;j

7、义。答：求图G第i顶点的度。27.(10分)请设计实现删除单链表中值相同的多余结点的算法，先简述算法思想，然后写出算法的C语言描述。voidpurge(LListL){//删除链表中的“冗余”元素LLists,q,p=L->next;while(p){//p指向当前被考察的结点q=p;while(q->next)//考察q所指后继结点if(q->next->data!=p->data)q=q->next;else//修改指针并释放结点空间{s=q->nex