北京理工大学2013级数据结构B试题(B卷)_答案

1一、选择题1、所谓算法是指【B】。A、计算机程序B、求解特定问题的计算方法C、欧几里德算法D、求解特定问题的指令的有限序列2、在一个单链表中，若p所指结点不是表尾结点，在p之后插入s所指结点，则执行【B】。A、s-next=p;p-next=s;B、s-next=p-next;p-next=s;C、s-next=p-next;p=s;C、p-next=s;s-next=p;3、若已知一个栈的入栈序列是1，2，3，，n，其输出序列为P1,P2,P3,,Pn，若P1=n，则Pi为【C】。A、iB、n=iC、n-i+1D、不确定4、不带头结点的单链表head为空的判定条件是【A】。A、head==NULLB、head-next==NULLC、head-next==headD、head!=NULL5、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为【B】。A、1和5B、2和4C、4和2D、5和16、一棵有124个叶子结点的完全二叉树，最多有【A】结点。A、247B、124C、248D、1257、按照二叉树的定义，具有3个结点的二叉树有【C】种。A、3B、4C、5D、68、在一个有向图中，所有顶点的入度之和是所有顶点的出度之和的【B】倍。A、1/2B、1C、2D、49、对线性表进行二分查找时，要求线性表必须【C】。A、以顺序方式存储B、以链式方式存储C、以顺序方式存储，且结点关键字有序排列。D、以链式方式存储，且结点关键字有序排列。10、若一颗二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足【B】。A、所有结点均无孩子B、所有结点均无右孩子C、只有一个叶子结点D、是一颗满二叉树11、一个有n个结点的图，最多有【D】个连通分量。A、0B、1C、n-1D、n12、一棵树有n个结点，在该树的二叉链表存储表示中，空链域（即空指针域）的个数为【C】。A、n-1B、2n-1C、n+1D、2n+1213、下列排序算法中，【A】排序算法不能保证在每趟排序中将一个元素放到其最终位置上。A、直接排序B、冒泡排序C、简单排序D、快速排序14、在一颗度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则其叶子结点个数为【C】。A、4B、5C、6D、715、在一个包含n个顶点e条边的有向图的邻接矩阵中，零元素的个数为【C】。A、eB、2eC、n2-eD、n2-2e16、一个栈的入栈序列是1，2，3，4，则栈不可能输出的序列是【C】。A、4321B、1432C、4312D、123417、为了将遍历结果还原为惟一的二叉树，应当知道的遍历条件是【D】。A）先序遍历和后序遍历B）先序遍历和层次遍历C）中序遍历和层次遍历D）中序遍历和后序遍历18、二叉排序树是【B】。A、每一分支结点的度均为2的二叉树B、中序遍历得到一升序序列的二叉树C、按从左到右顺序编号的二叉树D、每一分支结点的值均小于左子树上所有结点的值，又大于右子树上所有结点的值19、在有向图的邻接表存储结构中，顶点v的下标在链表中出现的次数是【B】。A）顶点v的度B）顶点v的出度C）顶点v的入度D）依附于顶点v的边数20、一个有n个顶点的有向图最多有【B】条边。A、nB、n(n-1)C、2nD、n(n-1)/2二、判断对错【x】1、顺序存储方式结构只能用于线性结构，不能用于非线性结构【x】2、算法的优劣与描述算法的语言有关。【】3、在线性链表中，只能顺序存取元素，不能直接存取元素。【】4、二叉树就是度小于等于2的有序树。【x】5、若一个结点是某二叉树子树的前序遍历序列的最后一个结点，则它也必是该子树的中序遍历序列的最后一个结点。【x】6、对于一棵含有n个结点的树，将其结点按从上到下且从左至右按1至n进行编号，则对其任意一个编号为i的结点，如果它有左孩子，则其左孩子结点3的编号为2i。【】7、在完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。【】8、具有n个顶点的强连通图至少有n条弧。【x】9、由树转换得到的二叉树，其根结点没有左子树。【】10、在二叉排序树中，最大值结点和最小值结点一定是叶子结点。三、填空题1、向量的第一个元素的存储地址是200，每个元素的长度是3，那么第6个元素的存储地址是。答案：2153、在一个带头结点的单链表中，p所指结点既不是首元结点，也不是尾元结点，删除p结点的直接后继结点的语句序列是、。答案：q=p-next,p-next=p-next-next,free(q)4、从堆栈中删除一个数据元素，即出栈的操作过程是、。答案：栈顶指针减1，取出数据元素5、从循环队列删除数据元素时，需要判满队列是否已经空了，判断条件是：。答案：rear==front7、链队列实际上是一个同时带有头指针和尾指针的单链表（1…n），则队尾指针指向该链表的第个元素。答案：n8、在有n个叶子结点的哈夫曼树中，总的结点个数是。答案：2n－19、已知完全二叉树的第7层有8个结点，则该二叉树的叶子结点个数为。答案：3610、将一棵完全有100个结点的二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为。答案：9811、已知某二叉树的中序序列和后序序列分别为47215836、74285631，则它的前序序列为。4答案：1247358613、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为，邻接表中所有结点的总数是。答案：n，2e14、在有序表A[1…20]中，采用折半查找算法查找元素值等于A[12]的元素，所比较过的元素的下标依次为。答案：10151215、一组记录的输入顺序为(25,38,65,90,72,14)，则利用堆排序方法建立的初始“大顶堆”为。答案：90,72,65,38,25,14四、简答题1、有一份电文中共使用8个字符：a、b、c、d、e、f、g、h，它们出现的频度分别为：4、7、5、2、9、8、6、3，试设计一个编码使该段电文的总长度为最短。要求：（1）构造出哈夫曼树（要求所有左子树根结点的权值小于等于右子树根结点的权值）；（2）求出每个字符的哈夫曼编码；（3）计算经哈夫曼编码后上述报文的最终长度。答案：（1）构造的哈夫曼树结构如下：（2）所有字符编码为：a=000，b=110，c=001，d=1000，e=01，f=111，g=101，h=10010adfhgbe111111100000004515293918567118264430c5（3）经哈夫曼编码后上述报文的最终长度WPL为：WPL=4×3+5×3+9×2+2×4+3×4+6×3+7×3+8×3=1282、某二叉树的结点数值采用顺序存储结构，如下图所示，要求：（1）画出该二叉树的结构；（2）分别写出该二叉树的前序和中序遍历序列；（3）分别写出结点F的双亲结点、左孩子结点和右孩子结点。结点编号123456789101112131415161718192021结点数值ABCDEFGHJMN第2题图答案：（1）（2）前序序列：ABDFMNGCEHJ中序序列：BMFNDGACHEJ（3）结点F的左孩子结点为M，右孩子结点为N，双亲结点位D。3、输入一个正整数序列{40,28,6,72,100,3,54,1,80,91,38}，要求：（1）依次读取上述整数序列中的数据，构造一个二叉排序树；（2）如何根据此二叉树求得上述整数序列的一个有序序列？并写出该有序序列；（3）画出在此二叉树中删除结点“72”后得到的二叉树结构。答案：（1）构造的二叉排序树如下：GFD3BAC0J0E0H0MN6（2）上述二叉树的中序遍历序列即是该整数序列的一个有序序列：1，3，6，28，38，40，54，72，80，91，100（3）删除结点72后的二叉树结构为下面任意一种结构：或者3386100154809140283386721001548091402874、对于如下图所示的森林，要求：（1）写出图（a）所示的第一棵树的先序遍历序列；（2）将这个森林转换为相应的二叉树。答案：（1）图（a）所示树的先序序列为：ABEFGHCDI（2）该森林对应的二叉树结构如下：338610015480914028ACIDBEFGHJNKLMP(a)(b)(c)第4题图85、对于如下所示的加权图，写出用Kruskal算法构造最小生成树的过程，并画出最后得到的最小生成树。第5题图答案：最小生成树的构造过程如下图所示：FCENGJKLABMDJPH11796821135493712AGEFCBD10H1AGEFCBDH92143AGEFCBDH21543AGEFCBDH213AGEFCBDH21AGEFCBDH10五、按照指定功能，通过填空完成下列算法1、L是带头结点的链表的头指针，以e返回第i个元素StatusGetElem_L(LinkListL,inti,ElemType&e){p=L-next;j=1;while(p!=NULL&&ji){p=p-next;++j;}216543AGEFCBDH6216543AGEFCBDH11if(p==NULL||ji)returnERROR;e=p-data;returnOK;}//GetElem_L2、算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符、界限符集合。operandTypeEvaluateExpression(){InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();while(c!=‘#’||GetTop(OPTR)!=‘#’){if(!In(c,OP)){Push(OPND,c);c=getchar();}elseswitch(Precede(GetTop(OPTR),c){case:Push(OPTR,c);c=getchar();break;case=:Pop(OPTR,x);c=getchar();break;case:Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression123、后序遍历递归算法voidPostOrderTraverse(BiTreeT,Status(*Visit)(ElemTypee)){//采用二叉链表存贮二叉树，visit()是访问结点的函数//本算法后序遍历以T为根结点指针的二叉树if(T){PostOrderTraverse(T-lchild,Visit);PostOrderTraverse(T-rchild,Visit);Visit(T-data)；}}//PostOrderTraverse4、在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。intSearch_Seq(SSTableST,KeyTypekey){//ST.elem[0].key=key;//“哨兵”for(i=ST.length;!EQ(key,ST.elem[i].Key);--i)；returni;//若表中不存在待查元素,i=0}//Search_Seq六、给出下列程序的运行结果（一）给出下列算法的功能描述1、typedefstructnode{datatypedata;structnode*link;}*LinkList;intAlgo(LinkListlist){if(list==NULL)return0;elsereturn1+Algo(list-link);}答案：计算由list所指的线性链表的长度。132、voidAlgo(MGraphG,VertexTypeu){k=L