数据结构联考试卷1及答案

试卷一A－1共8页一、单项选择题(每小题2分，共30分)1．算法的时间复杂度表征的是()。A.算法的难易程度B.算法的可读性C.执行算法所消耗的存储空间D.执行算法所消耗的时间2．在一个单链表中，若p所指结点不是尾元结点，s指向已生成的新结点，则在p之后插入s所指结点的正确操作是（）。A.s-next=p-next;p=s;B.p-next=s-next;s-next=p;C.s-next=p-next;p-next=s;D.s-next=p;p-next=s;3．设循环队列的元素存放在一维数组A[0..40]中，队列非空时，front指示队首元素，rear指示队尾元素的后一个位置。如果队列中元素的个数为15，front的值为33，则rear应指向的位置是（）。A.A[6]B.A[16]C.A[7]D.A[17]4．除根结点之外，树上每个结点（）。A.可有一个孩子、任意多个双亲B.只有一个孩子、一个双亲C.可以有任意多个孩子、一个双亲D.可以有任意多个孩子、任意多个双亲5．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）。A.O(1)B.O(n)C.O(nlogn)D.O(n2)6．含有20个结点的二叉树中，度为0的结点数为8，则度为2的结点数为（）注意事项：1.考生将姓名、学号等信息写在试卷相应位置；2.必须使用蓝(黑)色钢笔或签字笔在规定位置答题；3.注意字迹清楚，保持卷面整洁。A－2共8页A.7B.8C.9D.107．可以惟一地转化为一棵树的二叉树的特点是（）A.根结点没有孩子B.根结点只有一个孩子C.根结点无左孩子D.根结点无右孩子8．若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历9．广义表A=(a,(b),(),(c,d,e,f))的长度为（）。A.3B.4C.5D.610．用某种排序方法对关键字序列(25，82，20，45，16，27，66，34，18)进行排序时，序列的变化情况如下：18，16，20，25，45，27，66，34，8216，18，20，25，34，27，45，66，8216，18，20，25，27，34，45，66，82则所采用的排序方法是（）。A.归并排序B.选择排序C.快速排序D.希尔排序11．如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（）。A.连通图B.强连通图C.有向完全图D.有向无环图12．在一个带权连通图G中，权值最小的便一定包含在G的（）。A.深度优先生成树中B.广度优先生成树中C.连通子图中D.最小生成树中13．静态链表中指针表示的是（）。A.数组下标B.内存地址C.下一元素地址D.起始地址A－3共8页14．在下述结论中，正确的是（）。○1只有一个结点的二叉树的度为0。○2二叉树的左右子树可任意交换。○3二叉树的度为2。○4深度为h的二叉树的结点个数小于等于深度相同的满二叉树。A.○1○2○3B.○1○2C.○3○4D.○1○415．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。A.先序B.中序C.后序D.层次二、填空题(每小题2分，共20分)1．数据的同一种逻辑结构，可以对应多种不同的。2.在循环双向链表中，删除最后一个结点，其算法的时间复杂度为。3.一个栈的输入序列为1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为。4.一个12阶对称矩阵A，采用行优先顺序存储压缩存储上三角元素，a00为第一个元素，其存储地址为100，每个元素占2个存储地址空间，则a45的地址为。5.在树结构中，没有后继的结点称为结点。6.有m个叶子结点的哈夫曼树所具有的结点数是。7.对于具有n个顶点、n-1条边的连通图G来说，采用存储结构较为节省存储空间。8.要完全避免散列所产生的“堆积”现象，通常采用解决冲突。9.顺序查找算法的查找成功的平均查找长度为。注意事项：1.考生将姓名、学号等信息写在试卷相应位置；2.必须使用蓝(黑)色钢笔或签字笔在规定位置答题；3.注意字迹清楚，保持卷面整洁。A－4共8页10.在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是。三、应用题（共34分）1．设完全二叉树的顺序存储结构中存储数据ABCDEF，要求：（1）给出该二叉树的二叉链表存储结构；（2分）（2）给出该二叉树的先序、中序和后序遍历序列。（6分）2.设一组初始记录关键字集合为(18，12，11，27，22，32，54，68)，散列表的长度为11，散列函数H(k)=kmod11，要求：（1）用线性探测法作为解决冲突的方法设计哈希表，在等概率的假设下计算查找成功时的平均查找长度和查找失败时的平均查找长度；（7分）（2）用链地址法作为解决冲突的方法设计哈希表，在等概率的假设下计算查找成功时的平均查找长度和查找失败时的平均查找长度。（7分）3.已知图G的邻接表如下所示。要求：（1）写出从顶点D出发的深度优先搜索遍历序列；（2分）（2）从顶点B出发的广度优先搜索遍历序列。（2分）4.给定一个关键字序列{22，17，30，41，35，5，12，20}，要求：（1）A－5共8页请写出快速排序第一趟的结果；（2分）（2）请写出堆排序时所建的初始大顶堆；（2分）（3）请写出归并排序的全过程。（4分）四、设计题（每小题8分，共16分）1.设计将两个不带头结点有序单链表的合并成一个不带头结点的有序单链表的算法。typedefstructNode{intdata;structnode*next;}Node,*LinkList;2．以二叉链表为存储结构，写出求二叉树深度的算法。注意事项：1.考生将姓名、学号等信息写在试卷相应位置；2.必须使用蓝(黑)色钢笔或签字笔在规定位置答题；3.注意字迹清楚，保持卷面整洁。A－6共8页数据结构联考试卷（1）参考答案一、单项选择题(每小题2分，共30分)123456789101112131415DCCCBADABCDDAD都对二、填空题(每小题2分，共20分)1.存储（物理）结构2.O(1)3.n–i+14.1865.叶子或终端6.2m–17.邻接表8.链地址法9.(1+n)/210.归并排序三、应用题（共34分）1840/11A－7共8页3.答：从顶点D出发的深度优先搜索遍历序列为：DECBA；(2’)从顶点B出发的广度优先搜索遍历序列为：BCAED。(2’)4.答：（1）第一趟快排结果为：20,17,12,5,22,35,41,30；(2’)（2）初始大顶堆为：41,35,30,20,22,5,12,17；(2’)（3）第一趟归并排序结果为：17,22,30,41,5,35,12,20第二趟归并排序结果为：17,22,30,41,5,12,20,35第三趟归并排序结果为：5,12,17,20,22,30,35,41(4’)四、设计题（每小题8分，共16分）1.voidMergeSequentLists(LinkListha,LinkListhb,LinkList*hc){Node*s=NULL;*hc=NULL;while(ha!=0&&hb!=0){if(ha-datahb-data){if(s==NULL){*hc=ha;s=ha;}else{s-next=ha;s=ha;}ha=ha-next;}else{if(s==NULL){*hc=hb;s=hb;}else{s-next=hb;s=hb;}hb=hb-next;}}//whileif(ha==NULL)s-next=hb;elses-next=ha;}2.intMax(inta,intb){1/11（1*4+2*2）=8/11注意事项：1.考生将姓名、学号等信息写在试卷相应位置；2.必须使用蓝(黑)色钢笔或签字笔在规定位置答题；3.注意字迹清楚，保持卷面整洁。A－8共8页if(ab)returna;returnb;}intGetBinaryTreeDepth(BL_BTreeBT_root){if(NULL==BT_root)return0;elsereturnMax(GetBinaryTreeDepth(BT_root-lchild),GetBinaryTreeDepth(BT_root-rchild))+1;}