数据结构期末考试题(1)

命题人：葛建梅教研室主任（签字）：系主任签字：日期：2008年12月5日第1页共5页课程教研室软件使用专业计算机科学与技术（工、师）、软件工程年级07级班级学号考生姓名考试地点————————¤—————¤———————————装订线————————¤———————¤——————北华大学计算机科学技术学院2008-2009学年第一学期《数据结构》课程期末考试试卷（1）题号一二三四五六七八总分得分评卷人核分：一、填空题（每题2分，共14分）1.下面程序段的时间复杂度是________。for(i=1;in;i++)for(j=1;jn;j++)B[i][j]=35;2.顺序队列在实现时，通常将数组看成是一个首尾相连的环，这样做的目的是为避免产生_____________现象。判断一个循环队列队满的条件是__________________（设Q.front代表队头静态指针，Q.rear代表队尾静态指针，Maxsize代表该循环队列的空间大小）。3.在一个长度为n的顺序表中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动_________个元素。4．如果某二叉树的先序遍历序列为abcde，中序为badec，那么该二叉树的后序为________。5.一棵二叉树的第i(i≥1)层最多有_________________个结点；一棵深度为k的满二叉树共有_______________个非终端结点。6.已知一个有向图的邻接矩阵表示，计算第i个结点出度的方法是__________________。删除所有以第i个结点为弧头的弧的方法是__________________________。7.在各种查找方法中，平均查找长度与结点个数n无关的查法方法是______________。二、选择题（每小题2分，共16分）1.数据结构是一门研究非数值计算的程序设计问题中计算机的___①_____以及它们之间的___②_____和操作等的学科。①A．操作对象B．计算方法C.逻辑存储D．数据映像②A.结构B．关系C.运算D．算法2.一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是________。A．abcdeB．edcbaC．edabcD．cbade2.大题得分大题得分命题人：葛建梅教研室主任（签字）：系主任签字：日期：2008年12月5日第2页共5页课程教研室使用专业年级班级学号考生姓名考试地点————————¤—————¤—————————装订线————————¤———————¤—————————3.带头结点的单链表L为不空的判定条件是________。A.L－next=nullB.L=nullC.L!=nullD.L－next!=null4.判断下列叙述中哪个不正确A.将一棵树转换成二叉树后，根结点没有左子树；B.用二叉树的先序遍历和中序遍历可以导出后序遍历；C.一棵深度为K且有2K-1个结点的二叉树称为满二叉树D.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近.5．按二叉树的定义，具有3个结点的二叉树有_____种形态A.3B.4C.5D.66．在一个具有n个顶点的无向图中，要连通全部顶点至少需要________条边。A．nB．n+lC．n-1D．n／27．已知图G如下，求出该图的拓扑排序序列_________________。CBAGEDFHA．CABDEFGHB．ABCDEFGHC．ACBDEFGHD．ACBDFEHG8．在待排序的元素序列基本有序的前提下，效率最高的排序方法是________。A．插入排序B．选择排序C．快速排序D．归并排序三、分析解答（1至4小题每题6分，5至6小题每题8分，共40分）1．二维数组A的每个元素是由4个字符组成的串，行下标的范围从0~9，列下标的范围是从0~9，则存放A至少需要多少个字节，A的第3列和第7行共占多少个字节，若A按行优先方式存储，元素A[6][3]的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致。1题得分大题得分命题人：葛建梅教研室主任（签字）：系主任签字：日期：2008年12月5日第3页共5页课程教研室使用专业年级班级学号考生姓名考试地点————————¤—————¤—————————装订线————————¤———————¤————————2.已知一棵树如下图，请将此树转化为对应的二叉树，画出转化后的二叉树及二叉链表。ABFECADAG3.已知某系统在通信联络中出现的abcdef六种字符，其频率为（13，12，35，15，9，16），试构造一棵Huffman树，并写出每种字符的Huffman编码。4．已知关键字序列{503，17，512，908，897，275，170，653，426}，请给出采用希尔排序法（d1=4,d2=2,d3=1）对该序列作升序排列时的每一趟的结果。5.已知AOE网如下，按关键路径算法:（1）找出其关键路径。（2）计算：Ve(v5)、Vl(v3)（3）设V5,V7弧称为活动a,计算：e(a)和L(a)1211551256V1V2V6V4V7V5V3V81882024126．依据下列关键字序列{25，15，21，23，40，48，32，22}构成一棵二叉排序树。（1）请画出此二叉排序树。（2）若在二叉排序树中查找，则查找成功与查找不成功的平均查找长度分别是多少？2题得分3题得分4题得分5题得分6题得分命题人：葛建梅教研室主任（签字）：系主任签字：日期：2008年12月5日第4页共5页课程教研室使用专业年级班级学号考生姓名考试地点————————¤—————¤—————————装订线————————¤———————¤————————四、算法设计（每小题10分，共30分）1.某大学图书馆中有一批图书，按其价格从低到高的次序构成了一个单链表存于计算机中，链表的每个结点指出同样价格书的数量，现在要清理书库，将价格为C元的图书清出库，即从单链表中删除价格为C元的结点。单链表存储结构与按此存储结构的算法如下，请在空格上填写适当的语句，完成该算法。typedefstructLNode{floatcost;intnum;StructLNode*next;}LNode,*LinkList；voidDelbooks(LinkList&L,floatc){q=L;p=q-next;while(①&&p!=null){q=p;p=p-next;}if(p!=null){②;③;}}2.设二叉树采用二叉链表存储结构，PrintElement是对数据元素打印输出的应用函数。下面算法是用类C语言描述的，实现了按中序遍历二叉树T的递归算法，对每个数据元素调用函数PrintElement输出该结点的值。请在空格上填写适当的语句，完成该算法。typedefstructBiTNode{chardata;structBitNode*Lchild,*Rchild;}BitNode,*BiTree;大题得分1题得分2题得分命题人：葛建梅教研室主任（签字）：系主任签字：日期：2008年12月5日第5页共5页课程教研室使用专业年级班级学号考生姓名考试地点————————¤—————¤—————————装订线————————¤———————¤—————————StatusInOrderTraverse(BiTreeT){if(①){if(InOrderTraverse(T-Lchild))if(②)if(③)returnOK;returnERROR;}elsereturnOk;}StatusPrintElement(chare){④;returnOk;}3．假设图采用邻接表存储表示，设计一个广度优先遍历算法。图与队列的存储结构如下，请依据此存储结构用类C语言编写算法。#defineMAX_VERTEX_NUM20voidBFSTraverse(ALGraphG，Status(*Visit)(intv)){typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{Vertextypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;#defineMAXQSIZE100typedefstruct{int*base;intfront;intrear;}SqQueue;3题得分