班级:学号:姓名:装订线第1页共6页第2页共6页一、单项选择题(每空1分,共15分)1.算法的时间复杂度取决于。A.问题的规模B.待处理数据的初态C.A和B2.链表不具有的特点是。A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比3.在双向链表存储结构中,删除p所指的结点时须修改指针。A.p-prior-next=p-next;p-next-prior=p-prior;B.p-prior=p-prior-prior;p-prior-next=p;C.p-next-prior=p;p-next=p-next-next;D.p-next=p-prior-next;p-prior=p-next-next;4.输入序列为ABC,可以变为CBA时,经过的栈操作为。A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop5.设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是。A.6B.4C.3D.26.设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主序存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为。A.13B.33C.18D.407.广义表运算式GetTail(((a,b),(c,d)))的操作结果是。A.(c,d)B.c,dC.((c,d))D.d8.对n个元素的表做顺序查找时,若查找每个元素的概率相同,则查找成功的平均查找长度为。A.(n+1)/2B.n/2C.nD.((1+n)×n)/29.设有一表示算术表达式的二叉树,它所表示的算术表达式是。A.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C.(A*B+C)/(D*E+(F-G))D.A*B+C/D*E+F-G10.一棵树高为K的完全二叉树至少有个结点。A.2k–1B.2k-1–1C.2k-1D.2k11.若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置,利用遍历方法最合适。A.先序B.中序C.后序D.按层次12.下面结构中最适于表示稀疏无向图的是。A.邻接矩阵B.逆邻接表C.邻接多重表D.十字链表13.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应作型调整以使其平衡。哈尔滨工程大学试卷考试科目:数据结构A卷题号一二三四五总分分数评卷人装订线第3页共6页第4页共6页A.LLB.LRC.RLD.RR14.数据序列(2,1,4,9,8,10,6,20)只能是下列排序算法中的的两趟排序后的结果。A.快速排序B.冒泡排序C.选择排序D.插入排序15.对下列关键字序列用快速排序法进行排序时,速度最快的情形是。A.{21,25,5,17,9,23,30}B.{25,23,30,17,21,5,9}C.{21,9,17,30,25,23,5}D.{5,9,17,21,23,25,30}二、填空题(每空1分,共10分)1.线性表L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是。2.设有二维数组A[0..9,0..19],其每个元素占两个字节,第一个元素的存储地址为100,若按列优先顺序存储,则元素A[6,6]存储地址为_______。3.当广义表中的每个元素都是原子时,广义表便成了_______。4.在完全二叉树中,编号为i和j的两个结点处于同一层的条件是_______。5.一棵树T中,包括一个度为1的结点,两个度为2的结点,三个度为3的结点,四个度为4的结点和若干叶子结点,则T的叶结点数为_______。6.已知一无向图G=(V,E),其中V={a,b,c,d,e},E={(a,b),(a,d),(a,c),(d,c),(b,e)},现用某一种图遍历方法从顶点a开始遍历图,得到的序列为abecd,则采用的是_______遍历方法。7.己知有序表为(12,18,24,35,47,50,62,83,90,115,134),当用折半查找法查找100时,需_______次才能确定不成功。8.在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是______。9.分别采用堆排序、快速排序、冒泡排序和归并排序,对初态为有序的表,则最省时间的是______算法。10.不受待排序初始序列的影响,时间复杂度为O(n2)的排序算法是______。三、判断题(每空1分,共10分)1.顺序存储方式的优点是存储密度大,且插入、删除运算效率高。()2.线性表的特点是每个元素都有一个前驱和一个后继。()3.循环队列也存在空间溢出问题。()4.一个稀疏矩阵Am*n采用三元组形式表示,若把三元组中有关行下标与列下标的值互换,并把m和n的值互换,则就完成了Am*n的转置运算。()5.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。()6.用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中结点个数有关,而与图的边数无关。()7.在任意一棵非空二叉排序树中,删除某结点后又将其插入,则所得二排序叉树与原二排序叉树相同。()8.在初始数据表已经有序时,快速排序算法的时间复杂度为O(nlog2n)。()9.堆排序是稳定的排序方法。()10.在任何情况下,归并排序都比直接插入排序快。()四、应用题(每题7分,共35分)1.采用哈希函数H(k)=3*kMOD13,并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22、41、53、46、30、13、1、67、51,(1)构造哈希表(画示意图);(2)求等概率下成功的平均查找长度。2.一棵二叉树的先序、中序序列如下,请构造出该二叉树,并进行后序线索化。先序序列:ABDHIMEJCFKLG中序序列:HDIMBJEAKFLCG3.给出一组关键字{29,18,25,47,58,12,51,10},写出堆排序的过程(包括初始建大顶堆、堆顶每取下一个元素后堆调整)。班级:学号:姓名:装订线第5页共6页第6页共6页4.给定一组权值2、3、5、7、11、13、17、19、23、29、31、37、41,试画出哈夫曼树。5.用克鲁斯卡尔算法构造下图的一棵最小生成树,并给出选边顺序。五、算法设计题(每题15分,共30分)1.有一个带头结点的单链表,头指针为head,它的数据域的类型为整型,而且按自小到大的顺序排列,编写一个算法insertx_list(linklist*head,intx),在该链表中插入值为x的元素,使该链表仍然有序。2.请设计一个算法,要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表,表头指针为head。二叉树按二叉链表方式存储,链接时用叶子结点的右指针域来存放单链表指针。