浙江工业大学数据结构试卷

浙江工业大学2007~2008年《数据结构》试卷A第1页浙工大0708学年《数据结构》试卷A一、单选题.(20×1=20分)1．常用的算法时间复杂度中，按照复杂度优劣排列正确的是（）。A)O(1)≤O(log2n)≤O(n)≤O(n2)≤O(nlog2n)B)O(1)≤O(n)≤O(log2n)≤O(n2)≤O(nlog2n)C)O(1)≤O(log2n)≤O(n)≤O(nlog2n)≤O(n2)D)O(1)≤O(n)≤O(log2n)≤O(nlog2n)≤O(n2)2．线性表如果采用链式存储结构时，要求内存中可用存储单元的地址（）。A)必须是连续的B)部分地址必须是连续的C)一定是不连续的D)连续或不连续都可以3．用于解决图的点对之间的最短路径的算法是（）。A)图的深度优先遍历算法B)图的Dijkstra算法C)图的Warshall算法D)图的floyd算法4．以下的数据结构中，是线性结构的是（）。A)栈B)散列C)图D)优先队列5．以下满足队列特点是（）。A)后到先服务B)在相同的端点添加和删除元素C)在一端添加元素，在另一端删除元素D)先进后出6.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09}，则数据结构A是（）。A)线性结构B)树型结构C)链式结构D)图型结构7．根据二叉树的定义，3个结点的二叉树有几种形态（）。A)6B)5C)4D)38．下列应用中，需使用队列的是（）。A）实现递归算法B）实现树的层次遍历C）实现表达式计算D）实现深度优先搜索9．使用按照中序遍历二叉排序树，得到的遍历序列满足（）。A)乱序B)降序C)升序D)情况随机10．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。A)15，25，35，50，20，40，80，85，36，70B)15，25，35，50，80，20，85，40，70，36C)15，25，35，50，80，85，20，36，40，70浙江工业大学2007~2008年《数据结构》试卷A第2页D)15，25，35，50，80，20，36，40，70，8511．在以下的序列中，哪个是最小堆？（）A)29，53，56，72，34，67，86B)86，72，34，48，56，53，29C)29，33，50，72，48，92，133D)34，42，53，12，5，29，3312．散列表长m=15,散列函数hash(key)=key%13,表中已经有了4个结点,关键字分别是18,32,59,73,其余地址为空，如是采用开地址散列(线性探测法)处理冲突，那么关键字109的结点地址为（）。A)8B)9C)5D)413．采用牺牲元素法来构造循环队列时，长度为n的向量可以存放的元素个数为:（）。A)n-2B)n-1C)nD)n+114．如果对二叉树采用的遍历方式是右子树左子树根，那么左下图的二叉树相应的遍历序列为（）。15．将一棵有99个结点的完全二叉树按顺序编号，根结点的编号为0,那么编号为49的结点的右子结点的编号为（）。A)98B)99C)100D)不存在16．一个栈的入栈序列是a,b,c,d,下列出栈序列中不可能的出栈序是哪个？（）。A)abcdB)acbdC)dcbaD)cabd17．10000个结点要构造二叉树(树高从0层开始)，则最高的二叉树和最低的二叉树的树高为（）。A）5000,100B）10000,18C）5000,14D）99999,1418．如下图，从顶点1出发，按照广度优先规则遍历，可能得到的序列为（）。A)1352467B)142375C)1234576D)135467219．设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A）5B）6C）7D）820．已知有向图G=(V,E),如右图所示，G的可能的拓扑排序为（）。A)V1,V3,V4,V6,V2,V5,V7B)V1,V3,V5,V6,V4,V2,V7C)V1,V3,V4,V5,V2,V6,V7D)V1,V2,V5,V3,V4,V6,V7二、填空题(10×2=20分)1．对于声明：ListStackmyStack;有一些操作：myStack.push(‘A’);myStack.push(‘K’);myStack.push(‘D’);myStack.pop();myStack.push(‘H’);myStack.push(‘K’);51749A)9,7,5,4,1B)4,1,9,7,5C)7,9,5,4,1D)9,7,4,1,51273546v1v2v3v4v7v5v6浙江工业大学2007~2008年《数据结构》试卷A第3页myStack.pop();myStack.pop();myStack.push(‘D’);此时，栈内元素从栈底向栈顶依次为______________（1）__________________。2．一个二叉树的前序遍历结果为：ABDEHCFIGJ;中序遍历结果为：DBEHAIFCJG;请给出这个二叉树的后序便历序列_____________（2）_________________________。3．表达式f+(a+b)/(d-e)*2对应的后缀表达式是_____________（3）_________________________。4．求如下程序段的时间复杂度，复杂度采用大O表示。__（4）___。//假设n,data[]均有定义intlow=0;inthigh=n;while(lowhigh){intmid=(low+high)/2;if(data[mid]==value)cout”findthedataat:”mid;elseif(data[mid]value)low=mid+1;elsehigh=mid;}cout”can’tfindthedata,thelastsearching:”low;5．使用上题的策略对排序向量：170，275，426，503，509，512，612，653，677，703，765，897，908检索元素703，请问依次比较的元素为________________（5）_____________________________。6．假设有向量(Q,H,C,Y,P,A,M,S,R,D,F,X)，如果要将该向量调整成最大堆，则结果是_____________（6）__________________；如果要将该向量按字母升序排列，则采用选择排序的第二趟排序的结果是______________（7）____________；采用快速排序的第二趟排序的结果是________（8）_________________。7．有排序二叉树的原始图如下所示:在原始图上添加结点77后，该排序树变为_______（9）_____在原始图上删除结点112，该排序树变为____（10）_________三、算法分析与设计:（60分）1．将关键码序列为{C,B,X,W,U,V,Y}依次插入到一个空的AVL树中，画出每次插入完成后的AVL树（8分）2．已知带权图如图所示，请给出它的邻接矩阵表示形式。（5分）575011279134446013093（二叉树的原始图）DAECMGB8010155030100402090浙江工业大学2007~2008年《数据结构》试卷A第4页3．设待排序的关键码序列为最大堆{30，28，20，18，12，10，16，6，2}，试写出使用堆排序的前3趟结果。（6分）4.有9个关键码的开地址散列向量{32，13，49，55，22，39，20，97，56}，散列函数为取余运算（即%11，如关键码32的向量地址为32%11=10），散列表空间为11个单元。试分别完成按以上关键码顺序插入到线性开地址散列解决冲突的散列表之后的结果。（5分）5．设有无向图G，要求给出用普里姆算法构造最小生成树的全过程。（6分）6.对于下图，试模拟Dijkstra算法，给出从编号为A的顶点出发到其它各个结点的最短路径的过程。（10分）7．假设用于通讯的电文仅有6个字母abcdef组成，字母在电文中出现的频率分别为7，19，5，16，42，11。试为这6个字母设计哈夫曼编码。（8分）8.已知一个队列．．的模板类如下#definequeue_size1000templateclassTclassqueueVector{protected:Tdata[queue_size];//队列空间intnextSlot;//入队指示intnextUse;//出队指示public://构造和析构函数queueVector();queueVector(constqueueVectorT&other);Tdequeue();//出队动作voidenqueue(Tvalue);//入队动作};请完善这个这个队列。已知模板类的各个函数实现情况如下，请补充完整。AGBFEDC121025281618221424816浙江工业大学2007~2008年《数据结构》试卷A第5页templateclassTqueueVectorT::queueVector(){//初始化队列：设置队列相关属性初始值。nextSlot=0;nextUse=0;}templateclassTqueueVectorT::queueVector(constqueueVectorT&other){//拷贝构造函数，根据参数初始化队列对象本身。（4分）}templateclassTTqueueVectorT::dequeue(){//出队动作：若队列不空，则删除队列首元素，并返回该元素。（4分）}templateclassTvoidqueueVectorT::enqueue(Tvalue){//入队动作：若队列不满，则往队列末尾添加元素。（4分）}一、选择题（20分）1.C2.D3.D4.A5.C6.B,D7.B8.B9.C10.A11.C12.B13.B14.D15.D16.D17.D(送分)18.C19.A20.A二、填空题.（20分）1．（1）AKD注意：从栈底到栈顶，若写成DKA，得1分。2．（2）DHEBIFJGCA3．（3）fab+de-/2*+4．（4）O(log2n)5．（5）[6]612,[10]765,[8]677,[9]703或[6]612,[9]7036．（6）YSXRPCMHQDFA（7）ACHYPQMSRDFX（8）ADCFPHMQRSYX浙江工业大学2007~2008年《数据结构》试卷A第6页7．（9）（10）三、算法分析设计(60分)1．（8分）1分1分1分1分2分2分2．（5分）2边1分，共9边；对角线为0，1分；3．（6分）①2分②2分③2分4．（5分）32%11=1013%11=249%11=555%11=022%11=039%11=620%11=997%11=956%11=1ABCDEMA0∞∞80∞10B20050∞∞∞C∞∞0∞30100D∞90∞040∞E∞∞∞∞0∞M∞15∞∞∞057504411279609377134130575044130796093134CBCBXWCBXUWCBX右单旋UCBWXV右左双旋VUCWXYB3028182010161216222818201061216302818620102121630调整21862010281216302018616102812230调整21861610281220301812616102822030调整552213975649392032012345678910浙江工业大学2007~2008年《数据结构》试卷A第7页2个