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

一、选择题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=head D、head!=NULL5、若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3。当从队列中删除一个元素，再加入两个元素后，rear和 front 的值分别为【 B 】。A、1和5 B、2和4 C、4和2 D、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+113、下列排序算法中，【 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的结点，如果它有左孩子，则其左孩子结点的编号为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、链队列实际上是一个同时带有头指针和尾指针的单链表（1n），则队尾指针指向该链表的第 个元素。答案：n 8、在有n个叶子结点的哈夫曼树中，总的结点个数是 。答案：2n1 9、已知完全二叉树的第7层有8个结点，则该二叉树的叶子结点个数为 。答案：3610、将一棵完全有100个结点的二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为 。答案：98 11、已知某二叉树的中序序列和后序序列分别为47215836、74285631，则它的前序序列为 。答案：1247358613、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为 ，邻接表中所有结点的总数是 。答案：n，2e14、在有序表A120中，采用折半查找算法查找元素值等于A12的元素，所比较过的元素的下标依次为 。答案：10 15 1215、一组记录的输入顺序为(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）构造的哈夫曼树结构如下：0adfhgbe111111100000004515293918567118264430c（2）所有字符编码为：a=000，b=110，c=001，d=1000，e=01，f=111，g=101，h=1001 （3）经哈夫曼编码后上述报文的最终长度WPL为：WPL=43+53+92+24+34+63+73+83=1282、某二叉树的结点数值采用顺序存储结构，如下图所示，要求：（1）画出该二叉树的结构；（2）分别写出该二叉树的前序和中序遍历序列；（3）分别写出结点F的双亲结点、左孩子结点和右孩子结点。结点编号123456789101112131415161718192021结点数值ABCDEFGHJMN第2题图答案：（1）GFD3BAC0J0E0H0MN（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）构造的二叉排序树如下：33867210015480914028（2）上述二叉树的中序遍历序列即是该整数序列的一个有序序列：1，3，6，28，38，40，54，72，80，91，100（3）删除结点72后的二叉树结构为下面任意一种结构：338610015480914028或者3386100154809140284、对于如下图所示的森林，要求：（1）写出图（a）所示的第一棵树的先序遍历序列；（2）将这个森林转换为相应的二叉树。NJAPMLKBDC(a) (b) (c)第4题图HGFEI答案： （1）图（a）所示树的先序序列为：ABEFGHCDI（2）该森林对应的二叉树结构如下：FCEN GJKLABMDJPH5、对于如下所示的加权图，写出用Kruskal算法构造最小生成树的过程，11796821135493712AGEFCBD10H并画出最后得到的最小生成树。 第5题图答案：最小生成树的构造过程如下图所示：1AGEFCBDH21AGEFCBDH2143AGEFCBDH213AGEFCBDH21543AGEFCBDH216543AGEFCBDH6216543AGEFCBDH五、按照指定功能，通过填空完成下列算法 1、L是带头结点的链表的头指针，以e返回第i个元素Status GetElem_L (LinkList L,int i, ElemType &e) p = L-next; j = 1; while ( p!=NULL & jnext; +j;if ( p =NULL | ji ) return ERROR; e = p-data; return OK; / GetElem_L2、算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符、界限符集合。operandType EvaluateExpression( ) 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 : Pop ( OPTR, theta); Pop ( OPND, b); Pop(OPND, a); Push ( OPND, Operate(a, theta, b) ); break; /switch /whilereturn GetTop(OPND); /EvaluateExpression3、后序遍历递归算法void PostOrderTraverse ( BiTree T , Status ( * Visit ) ( ElemType e ) ) / 采用二叉链表存贮二叉树， visit( )是访问结点的函数 / 本算法后序遍历以T为根结点指针的二叉树 if ( T ) PostOrderTraverse ( T-lchild, Visit ); PostOrderTraverse ( T-rchild, Visit ); Visit ( T-data )； /PostOrderTraverse4、在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。int Search_Seq ( SSTable ST, KeyType key ) / ST.elem0.key = key; / “哨兵” for ( i=ST.length; !EQ(key, ST.elemi.Key); -i )； return i; / 若表中不存在待查元素, i=0 /Search_Seq六、给出下列程序的运行结果（一）给出下列算法的功能描述1、typedef struct nodedatatype data;struct node *link; *LinkList;int Algo(LinkList list)if(list=NULL)return 0;elsereturn 1+Algo(list-link);答案：计算由list所指的线性链表的长度。2、void Algo ( MGraph G, VertexType u ) k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) if ( j!=k ) closedge j = u, G.arcs k j .adj ; closedgek.lowcost = 0; for (i=0; iG.vexnum; +i) k = minimum(closedge); printf ( closedgek.adjvex, G.vexsk ); closedgek.lowcost = 0; for ( j=0; jG.vexnum; +j ) if ( G.arcskj.adj data); if(a-lchild!=NULL) EnQueue(&q,a-lchild); if(a-rchild!=NULL) EnQueue(&q,a-rchild); printf(n); 答案：层序遍历二叉树（二）给出下列程序的运行结果4、void main()Stack S;char x,y;InitStack(S);x=c; y=k;Push(S,x); Push(S,a); Push(S,y);Pop(S,x); Push(S,t); Push(S,x);Push(S,s);while(!StackEmpty(S)Pop(S,y); printf(y)