哈工程考研课件题DS06答案

数据结构A卷答案一、单项选择题（每空1分，共20分）1、A2、C3、A4、A5、C6、A7、A8、D9、D10、C11、A12、A13、C14、D15、C16、D17、D18、B19、B20、A二、填空题（每空1分，共10分）1、D,Q,F,X,A,P,B,N,M,Y,C,W2、1,3,6,8,11,13,16,19（答对一半给0.5分）3、prim（或中文译文）4、695、(n+1)/2（或2log(n+1)-1）（或2logn）（或n/2+1）（或n/2）（或n-(2logn-1)）6、L-next-next==L（或L-prior-prior==L）或（L-prior==L-next）（意思正确即给满分）7、2k-2+18、1269、主关键字10、93或92三、判断题（每空1分，共10分）1、×2、×3、×4、×5、×6、×7、×8、√9、×10、×四、应用题（每空5分，共30分）1．tdeLRdetsugRLdgsetubja2．散列地址012345678910关键字3311312343827223．(1)一趟希尔排序:12,2,10,20,6,18,4,16,30,8,28(2)一趟快速排序：6,2,10,4,8,12,28,30,20,16,184．0.030.070.040.100.170.050.110.060.110.220.250.610.360.391.00C5C3C8C6C1C4C2C700011111110000LLbgsetuajdkRRbjsetuakdgrfLRbgjestaidukrc1:0110c2:10c3:0010c4:0111c5:000c6:010c7:11c8:00115．6．选边次序为（1，6），（2，3），（1，7），（2，4），（2，5），（1，2）。五、算法设计题（每题15分，共30分）1．[算法思想]对二叉树进行先序遍历。遍历过程中，当结点的左右孩子均为空时，叶子结点计数器值加1，当结点的左孩子或右孩子不为空时，非终端结点计数器值加1。voidCount(BiTreebt,int*n0,*n)//统计二叉树bt上叶子结点数n0和非叶子结点数n{if(bt){if(bt-lchild==null&&bt-rchild==null)*n0++；//叶子结点else*n++;//非叶结点Count(bt-lchild,&n0,&n);Count(bt-rchild,&n0,&n);FDBGHECANULL125643184128576}}//结束Count2．[题目分析]由于已给条件（a1xan），故应先将第一结点从链表上摘下来，再将其插入到链表中相应位置。由于是双向链表，不必象单链表那样必须知道插入结点的前驱。voidDInsert（DLinkedListdl）∥dl是无头结点的双向循环链表，自第二结点起递增有序。本算法将第一结点（a1xan）插入到链表中，使整个链表递增有序。{s=la；∥s暂存第一结点的指针p=la-next；p-prior=la-prior；p-prior-next=p；∥将第一结点从链表上摘下while（p-datax）p=p-next；∥查插入位置s-next=p；s-prior=p-prior；p-prior-next=s；p-prior=s；∥插入原第一结点s}∥算法结束。