20112012北京交通大学数据结构与算法期末考试参考答案

经典word整理文档，仅参考，双击此处可删除页眉页脚。本资料属于网络整理，如有侵权，请联系删除，谢谢！北京交通大学考试试题（A卷）课程名称:数据结构与算法2011-2012学年第一学期:张勇(请考生注意:（）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场)题号得分一总分阅卷人一、填空题（每空2分，共20分）1.在顺序表中访问任意一个元素的时间复杂度均为，因此顺序表也称为的数据结构。2．三维数组a[4][3][2](下标从0开始)，假设a[0][0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是。3.直接插入排序用监视哨的作用是。4.已知广义表Ls=(a,(b,c),(d,e)),运用head和tail函数取出Ls中的原子d的运算是。5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。被比较元素除外，还有。6.在AOV网中，顶点表示，边表示。7.有向图G可进行拓扑排序的判别条件是。8.若串‘ABCDEFGHIJK’,S2=‘451223’‘####’则执行Substring(S1,Strlength(S3),Index(S2,‘12’的结果是。二、选择题（每空2分，共20分）1.在下列存储形式中，哪一个不是树的存储形式？（）A．双亲表示法B．孩子链表表示法D．顺序存储表示法C．孩子兄弟表示法2.查找n个元素的有序表时，最有效的查找方法是（）。A．顺序查找．分块查找C．折半查找D．二叉查找3.将所示的s所指结点加到p所指结点之后，其语句应为（）。p╳s(A)s->next=p+1;p->next=s;(B)(*p).next=s;(*s).next=(*p).next;(C)s->next=p->next;p->next=s->next;(D)s->next=p->next;p->next=s;4.在有向图的邻接表存储结构中，顶点v在链表中出现的次数是（）。A.顶点v的度B.顶点v的出度C.顶点v的入度D.依附于顶点v的边数5.算法的时间复杂度为nlogn）、空间复杂度为O(1)的排序算法是（）。2A.堆排序B.快速排序C.归并排序D.直接选择a6.设矩阵A组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i≤j),在一维数组B中下标k的值是（）：aaaan,nnn,2Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+jＣ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j7.由一个长度为11况下，查找成功的平均查找长度是（）。A．29/11B.31/11C.33/11D.35/118.AVL树是一种平衡的二叉排序树，树中任一结点的（）。19.下列四种排序方法中，不稳定的方法是（）。A.直接插入排序B.冒泡排序C.归并排序D.堆排序10.设树的度为4，其中度为1,2,3,4的结点个数分别为4,2,,1,1,则T中的叶子数为）。（A．5B6C．7．8三、判断题（10分，每小题1分）1.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）2.数组不适合作任何二叉树的存储结构。（）3.广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。（）4.在含有n个结点的树中，边数只能是n-1条。（）5.）6.简单选择排序在最好情况下的时间复杂度为O(n)。（）7.在二叉排序树中插入一个新结点，总是插入到叶结点下面。（）8.采用线性探测处理冲突，当从哈希表中删除一个记录时，不应将该记录所在位置置空，因为这会影响以后的查找。（）9.有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序，其平均查找长度不同。（）10.广义表中原子个数即为广义表的长度。()四、应用题（24分）1.6分）将下列由三棵树组成的森林转换为二叉树。DEFGAHBCIJKL2．(6分给定下列图，完成以下问题（1）画出该图的邻接矩阵和邻接表（2）根据所画的邻接表，从顶点B出发，画出图的深度优先搜索树（3）根据普里姆（）算法，求它的最小生成树（不必写出全部过程，在生成树中标出边生成的次序即可）A355D6BC123E4F1G36分）输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题：（1）构造一棵二叉排序树，计算查找成功的平均查找长度；（2）依此二叉排序树，如何得到一个从大到小的有序序列；（3）画出在此二叉排序树中，删除“66”后的树结构.4.（6分）将序列{25,34,12,7,15,47,65,79，47+16中的关键字按升序重新排列，请写出（1）冒泡排序一趟扫描的结果（2）以第一个元素为分界点的快速排序一趟扫描的结果（3）堆排序所建的初始堆和第一趟排序结果。五、程序填空题（10分，每空1分）1.下列算法是建立单链表的算法，请填写适当的语句，完成该功能。typedefstructLnode{ElemTypestructLnode*next;}LNode,*LinkList;data;StatusCreatList_L(LinkList&L,intn){//正序输入n个元素的值,建立带表头结点的单链线性表LL=(LinkList)malloc(sizeof(LNode));if(!L)returnERROR;L->next=NULL;p=(1);for(i=0;i<n;i++){s=(LinkList)malloc(sizeof(LNode));if(!s)returnERROR;scanf(&s->data);(2)(3);;}p->next=NULL;returnOK;}//CreatList_L2.下列算法是经典模式匹配算法程序，请填写适当的语句，完成该功能。#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];//0号单元存放串长intIndex(SStringS,SStringT,intpos){if(pos>=1&&pos<=S[0]){i=pos;j=(4);while(i<=S[0]&&j<=T[0])if(S[i]==T[j]){++i;++j;}else{(5);(6);}if(j>T[0])returnelsereturn0;(7);}elsereturn0;}3.L,完成该功能。voidSelectSort(LinkListL){p=L;while(p){q=p;r=q->next;while(r){if((8)r=(9))q=r;;}tmp=q->data;q->data=p->data;p->data=tmp;p=(10);}}六、算法设计题（16分）1.（8分）已知一个带有头结点的单链表，假设该链表只给出了头指针。在不改变链表结构的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，则打印该结点的值，并返回1；否则，只返回0。链表结构定义为：typedefstructLnode{ElemTypedata;structLnode*next;}LNode,*LinkList;2、(8分)下题中任选一题（1）给定一棵赫夫曼树T，编写算法，求该赫夫曼树T的带权路径长度。赫夫曼树T采用如下定义的存储结构：typedefstructBiTNode{TElemTypedata;//此处data代表结点的权值structBiTNode*lchild,*rchild;}BiTNode,*BiTree;（2）假设一棵二叉树以二叉链表表示，元素值为整数，且元素值无重复，编写算法，打印以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。二叉树T采用如下定义的存储结构：typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;（3）设计一算法，要求将二叉树的叶结点按从左到右的顺序连成一个单链表，表头指针为head,二叉树按二叉链表方式存储，链接时用叶结点的右指针域来存放单链表指针，分析算法的时间、空间复杂度。假设二叉树T采用如下定义的存储结构：typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;一、填空题1.O(1)2.80随机存取3.防止数组下标越界4.Head【HeadTailTail（LS）】】】5.A[3]6.活动A[5]A[7]活动之间的先后关系7.该有向图无环8.DEF二、选择题1.D2.C3.D4.C5.A6.B7.C8.B9.D10.D三、判断题1.✕2.✕3.✕4.✓5.✕6.✕7.✕8.✓9.✕10.✕四、应用题1.ABGILJ2.(1)邻接矩阵：A5536B53C51D32E614F241G31邻接表：01234561000031264524534⋀G⋀(2)深度优先搜索树为：BDG(3)最小生成树：1ADGC26E4535F3.(1)二叉排序树如下：平均查找长度ASL=(1+2X2+4X3+3X4)/10=2.9(2)按照右子树根节点顺序(3)○(4)25、127、1534、47、65、47+、16791○16、15、127、2547、65、7947+、342○初始堆：79、47+、、34、16、4712、、25、153第一趟排序后：65、、47、34、16、1512、725、79（二叉树表示方法也可）五、程序填空题1.L2.p->next=s3.p=s4.15.i=i-j+26.j=17.ij+18.q->data>r->data9.r->next10.p->next六、算法设计题1.三种基本思路，（1）设一指针p指向链表的第1个结点，之后找到离p距离为k的结点（如果有的话），然后p与q同时移动，直到q指向链表尾部。（2）计算出单链表的长度，从而计算出要查找的节点在正向的位置，3K个节点。第一种思路可得满分，后两种扣2分。第二种方法参考代码：intSearch(LinkListL,intk){Lnode*p;intlength=0,i;if(!L||!L->next)return-1;p=L->next;while(p){length++;p=p->next;}if(length<k)return-1;p=L->next;for(i=0;i<length–k;i++){p=p->next;}printf(该元素为：%d\n,p->data);returnp->data;}2.(1)intHvalue(BiTreeT,inth){intlvalue,rvalue;if(!T)return0;if(T->lchild==NULL&&T->rchild==NULL)returnh*T->data;lvalue=Hvalue(T->lchild,h+1);rvalue=Hvalue(T->rchild,h+1);returnlvalue+rvalue;}(2)采用先序遍历方式遍历整棵树，设置标志位，标识是否找到所需节点，若找到，则打印其子树，同时后续监视是否已经返回，若返回则关闭标志，停止打印boolflag=false;intPrint(BiTreeT,intk){if(!T)return0;if(T->data==k)flag=true;if(flag)printf(%d,T->data);Print(T->lchild,k);Print(T->rchild,k);if(T->data==k)flag=false;}（3）采用先序遍历方式遍历整棵树，如果找到叶子结点，则将其