2013年秋季_数据结构_final(含答案)

1得分《数据结构》考试题（闭卷）A卷（电信系本科2012级2013年11月29日）姓名班级学号题号一二三总分题分403238110得分注：总分110分，不折算，超过100分按100分计一、回答下列问题(每题5分，共40分)1．二分查找应采用哪种存储结构，为什么？(lyg)解答：二分查找应采用顺序存储结构，链式存储结构不适合二分运算2．设一棵三叉树中有2个度为1的结点，2个度为2的结点，2个度为3的结点，计算该三叉树中有多少个度数为0的结点。(wb)解答：7个n1=2,n2=2,n3=3,求n0n=n0+n1+n2+n3n-1=2x1+2x2+2x3n0=13-2-2-2=7.3．在KMP算法中，已知模式串由比特串组成，若其next函数为012345612,请给出该模式串的可能值。(lyz)解答：可能的模式串：11111101x（1,0均可）012345612（next函数）可能的模式串：00000010x（1,0均可）012345612（next函数）4．对序列{33，44，21，8，19，123，46，78，11}进行快速排序和堆排序，请分别写出第一趟快速排序和第一趟堆排序后的结果(lyz)解答：若以33为基准，第一趟快排结果是：11,9,21,8,33,123,46,78,44以大根堆进行升序排序的第一趟堆排结果是：11,78,33,44,9,21,46,8,12325.已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H(K)=Kmod7（取余），若发生冲突采用线性探查法处理，即：Hi=(H(K)+di)mod7，di=1,2,…,6。（5分）（1）计算出每一个元素的散列地址并在下图中填写出散列表：0123456（2）求出在查找每一个元素概率相等情况下的平均查找长度。(lg)解答：（1）01234566336152240（2）ASL=6.15311216．设某二叉树的前序遍历序列和后序遍历序列正好相反，则该二叉树具有什么特征？(lwy)解答：树中没有度为2的节点，如果回答是单枝树，扣2分。7．对于一个n个节点的链表，现要删除其中某个节点，已知该节点的指针(头结点指针未知，不能使用)，如何利用该指针完成操作？(bx)解答：将待删除节点的后一个节点的数据信息全部复制到待删除节点里，然后删除待删除节点的后一个节点（常规的删除方法）。8．设有向图G的二元组形式表示为G=（D，R），D={1，2，3，4，5}，R={1,2，2,4，4,5，1,3，3,2，3,5}，试画出该图，并给出该图的一种拓扑排序序列：(wb)【解答】拓扑序列为：13245123453得分二、综合题（每题8分，共32分）1.已知二叉树的存储结构为二叉链表，阅读下面算法。(lwy)typedefstructnode{DateTypedata；Structnode*next；}ListNode，*LinkList；LinkListhead=NULL；VoidTreePro(BiTreeT){LinkLists；If(T){TreePro(T－lchild)；If((!T－lchild)&&(!T－rchild)){s=(ListNode*)malloc(sizeof(ListNode))；s－data=T－data；s－next=head；head=s；}TreePro(T－rchild);}}对于如图所示的二叉树（1）画出执行上述算法后所得结果；（2）说明该算法的功能。解答：（1）建立一个单链表head81381914（2）按二叉树中叶子结点数据自右至左链接成一个链表2．已知如图所示的带权图。(wb)(a)给出该图的邻接矩阵；(b)给出该图以节点1出发按照邻接矩阵进行广度优先搜索所得到的广度优先搜索序列；(c)画出最小生成树，并求出最小生成树上所有边的权值之和。【解答】58188129223819144a)邻接矩阵b)广度优先搜索序列：12453c)最小生成树如下图；边长权值之和=83.假设某符号集合包含8个字符号（E，H，L，O，S，T，U，V），它们各自出现的概率为（0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11）。试求其哈夫曼编码，画出哈夫曼树（按左子树权值小，右子树权值大建树，编码按左“0”右“1”）。并对输入序列11011100010011110011011100进行译码。(bx)答：Huffman树如下：编码结果如下：T：00H：10V：010S：111U：0110O：1100E：0111L：1101译码结果为：LOVEHUST123455得分4.杰克船长带领99名海盗在世界的尽头发现了一大批宝藏，足足有一百枚钢镚，为了分配这一大批宝藏，他们商定：由杰克船长开始依次提出分配方案，若剩余海盗（包括方案提出者在内）中有半数或半数以上海盗同意，则依照此方案分配，否则就干掉那名海盗。假设杰克船长和所有海盗足够聪明，那么请问杰克船长最多能够得到多少枚钢镚呢？并写出分配方案和递归过程。(bx)答：可由最后剩余3名海盗的情形递推至100名1）首先我们先从只剩下3个的情况来考虑，对最后那个人来说，若是不同意倒数第三个人的提议而把他杀掉则无论接下来那个人做如何分配那个人都不会死（包括他在内一共2人，并且他同意自己的提议）所以最后那个人什么都拿不到。从而对倒数第三个人来说只要他给最后一人一个金币，自己留99个那么最后一个人必定会同意（不然最后一个人会一个金币都拿不到）。2）再考虑4个人的情况，借用上面的讨论，若倒数第二个人不同意倒数第四个人的提议而把他杀掉，则他一个金币都拿不到（变成3个人的情况：9901）所以只要倒数第四个人的提议为：99010则相比之下倒数第二个人会同意这个提议。3）依次向上递推，则对于之前的人只要每隔一个人给一个金币就可以保证有半数或半数以上的人（包括他自己）同意，也就是说杰克船长可以拿到100-[(100-1)/2]下整=51个提议方案：（5101010101……010）答案为51枚，分配方案为510101……010三、算法设计题（共38分）1.(6分)已知一个带表头结点的单链表只给出了头指针list。在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值；否则，返回0。(wb)要求：（1）描述算法的设计思路和算法实现步骤。（2）利用伪C语言实现算法，关键之处给出注释。解答：(1)定义两个辅助指针p和q，初始时均指向头结点的下一个结点。p指针沿链表移动；当p指针移动到第k个元素时，q指针开始与p指针同步移动；当p指针移动到链表结尾时，q指针所指元素即为倒数第k个结点。以上过程仅对链表扫描一遍。(2)实现步骤(S1)置count=0,p和q指向首元结点；(S2)若p==NULL，转向(S5);(S3)若count==k,则q指向下一个结点；否则，置count=count+1;6(S4)置p指向下一个结点，转向(S2);(S5)若count==k,则查找成功，输出该结点的data域的值，返回1；否则，查找失败，返回0.(S6)算法结束。(3)代码intsearchk(LinkListlist,intk){LinkListp,q;intcount=0;p=q=listlink;while(p!=NULL){if(countk)count++;elseq=qlinkp=plink;}//whileif(countk)return(0);else{printf(“%d”,qdata);return(1);}}2．(8分)试编写一算法将升序的二叉排序树变为降序二叉排序树(lyz)解答：可采用递归和非递归算法1）递归算法Exchange(&T)While(T){Exchange(T-rchild,ex)Exchange(T-rchild,ex)}Exchange(p,ex)//交换p的左右孩子，ex为是否交换的标注{Ifp&!ex//p不空且左右没交换，则交换其左右孩子{q=p-lchildp-lchild=p-rchildp-rchild=q}ex=true}2）非递归算法在中序遍历过程中交换左右孩子即可73.(8分)给定如下的n*n的数字矩阵，每行从左到右是严格递增，每列的数据也是严格递增123356489现在要求设计一个算法，给定一个数k判断出k是否在这个矩阵中。描述算法并且给出时间复杂度（jhb）解：算法思想：沿着对角线查找，获得i,使得k位于a[i][i]与a[i+1][i+1]之间。k只可能存在于a[i][i]对应的右上角矩阵和a[i+1][i+1]对应的左下角矩阵。使用递归法继续查找即可。时间复杂度O(n)intsearchK(intint_arr[][],intn,intstartlow,intstartclm,intk){intlefttemp=0;intdowntemp=0;inti=0;while(int_arr[startlow+i][startclm+i]k||in)i++;if(i==n)return0;elseif(arr[i][i]==k)reuturn1;elsereturnsearchK(int_arr,n,startlow,startclm+i,k)+searchK(int_arr,n,startlow+i,startclm,k);}4．(8分)取值为[1，n-1]含n个元素的整数数组至少存在一个重复数，要求设计尽可能高效的算法，找出其中任意一个重复数，给出算法的时间、空间复杂度。（lwy）解答：intfind_dup(inta[],intn){intx,y;x=y=0;do{x=a[a[x]];//x一次走两步y=a[y];//y一次走一步}while(x!=y);//找到环中的一个点x=0;do{x=a[x];y=a[y];8}while(x!=y);//找到入口点returnx;}时间复杂度为o(n),空间复杂度为o(1)。如果设计的算法时间复杂度为o(nlogn),空间复杂度为o(n)，得3分。5.(8分)一个二叉树中任意两个节点间距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，兄弟节点间的距离是2.找出二叉树中距离最大的两个节点之间的距离值，并给出平均时间、空间复杂度。(bx+tc+lwy)答：算法思路：计算一个二叉树的最大距离有两个情况：情况A：路径经过左子树的最深节点，通过根节点，再到右子树的最深节点情况B：路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者首先计算经过根节点的最大路径距离，其实就是左右子树的深度和；然后分别计算左子树和右子树的最大距离，三者比较，最大值就是当前二叉树的最大距离了。MaxDist(bitreeT){If(T!=NULL)L=Depth(T-lchild)+Depth(T-rchild);Return(max(L,MaxDist(T-lchild),MaxDist(T-rchild);}应加上求深度的函数intDepth(Bitreep){ifp=NULLreturn(0);Elsereturn(1+max(Depth(p-lchild),Depth(p-rchild)));}平均时间复杂度为o(n2),空间复杂度为o(logn)。