2014《数据结构》期末试卷I(A)试题

第1页共7页试卷编号:2-A天津理工大学考试试卷2013～2014学年度第二学期《数据结构与算法》期末考试试卷课程代码：0668016试卷编号：2-A命题日期：2014年6月6日答题时限：120分钟考试形式：闭卷笔试一、单项选择题（每小题1分，共15分）得分1.设栈S初始状态为空，元素e1，e2，e3，e4，e5，e6依此通过栈S，，若6个元素出栈的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（）A.6B.4C.3D.22.下面程序段的时间复杂性的量级为（）for(inti=1;im;i++)for(intj=1;jn;j*=2)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m*lg(n))3.当利用大小为n的数组存储一个循环队列时，该队列的最大长度为（）A.n-2B.nC.n-1D.n+14.在含n个顶点和e条边的有向简单图的邻接矩阵中,零元素的个数为（）A．eB．2eC．n2－eD．n2－2e5．一个具有511个结点的完全二叉树，其叶结点个数为（）A.127B.128C.129D.2566．设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，则森林F中第一棵树的结点个数是（）第2页共7页试卷编号:2-AA.m-nB.m-n-1C.n+1D.条件不足，无法确定7．若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（）A.顺序存储结构B.链式存储结构C.索引存储结构D.散列(哈希)存储结构8．在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则叶结点个数为（）A．4B．5C．6D．79．堆排序算法的最差时间复杂度是（）A.O(nlog2n)B.O(log2n)C.O(n)D.O(n2)10．在长度为n的顺序表中，删除第i个元素（1≤i≤n）需要依次前移几个元素（）A.n-iB.n-i+1C.n-i-1D.i11.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）A.abcdeB.edcbaC.decbaD.dceab12.一棵树高为h的完全2叉树至少包含的结点数为（）A.2h-1-1B.2h-1C.2h-1D.2h13.一个大顶堆，最小的单元一定为（）A.根节点B.叶子节点C.树的非叶子节点D.树的最底层节点14.十字链表结构比较适合存储那种数据（）A.三角矩阵B.对称矩阵C.稀疏矩阵D.稠密矩阵15.递归程序的特点有()A.运行速度快B.占用空间少C.易于程序表达D.难于分析效率第3页共7页试卷编号:2-A二、填空题（每空3分，共15分）得分1.从平均时间复杂度角度来衡量，按从好到差顺序排列下面算法（冒泡排序、快速排序、希尔排序）：(1)______________(2)______________(3)______________。2．设散列（哈希）函数为H(k)=k％13，散列表的地址空间从0到12，用线性探测法解决冲突，将关键字（22，78，205，40，16，35，104，46）依次存入该散列表中。在等概率下查找成功的平均查找长度ASL=_______________。3．一个图的邻接矩阵为0101001011000010，则该图共有______个顶点为______向图，共有______条边。4.已知一棵二叉树的先序遍历序列为：ABHFDECKG，中序遍历序列为：HBDFAEKCG，则后序遍历序列为：________________。5.高度为5且符合6阶B_树约束条件的树，至少包含________________个结点。三、问答题（共40分）得分1.(10分)按4、5、6、2、1、3的顺序依次添加节点，生成AVL树，画出各步骤中树的形态。第4页共7页试卷编号:2-A2.（10分）画出图G按PRIM算法，从节点1开始逐步生成最小生成树的过程3．（10分）节点{n1,n2,...,n8}按顺序赋予如下权值{5，25，3，6，10，11，36，4}.试构造一棵Huffman树。1432561547263658第5页共7页试卷编号:2-A4．（10分）对下列有向图，写出以顶点1为出发点对图进行深度优先搜索所得到的所有可能的访问序列。四、算法设计题（共30分）得分1．（10分）下面的算法是对顺序存储的有序表A进行折半查找的递归算法，其中low代表折半区间的下界，high代表折半区间的上界，K代表待查关键字,函数返回值为所查找单元在有序表中的序号。在画有横线的地方填写适当的内容intBinarySearch(intA[],intlow,inthigh,intK){if(low=high){intmid=_________________;if(K==A[mid].key)Return________________;elseif(___________________)returnBinarySearch(A,low,mid-1,K);1462543第6页共7页试卷编号:2-Aelse________________________________;}elsereturn-1;}2．（10分）已知有一个二叉排序树(BST)，节点数据结构如下：StructNode{intkey;//左、右儿子指针。空时为NULLNode*l_son;Node*r_son;}满足右子树key值均大于父节点key、大于左子树key值。试编程实现如下函数：////////////////////////////////////////////////////////函数名：CountNodesByCondition//功能：统计二叉树中key值大于给定阈值的节点数//参数：//1、Node*root：二叉树根节点指针//2、intcondition:阈值//返回值：//当root为NULL，返回0//否则，返回key大于阈值的结点数//////////////////////////////////////////////////////intCountNodesByCondition(Note*root,intcondition){第7页共7页试卷编号:2-A}3．（10分）带头节点链表，节点数据结构如下：StructNode{intkey;Node*next;}最后单元的next指针为NULL。试编程实现如下函数：////////////////////////////////////////////////////////函数名：DeleteElem//功能：删除单链表中key为给定值的所有单元(不负责释放内存)//参数：//1、Node*head：单链表头节点指针//2、intvalue：要删除的key值//////////////////////////////////////////////////////voidDeleteElem(Note*head,intvalue){}