浙江省高等教育自学考试数据结构试题及解析历年试卷及解析

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯精选自学考料介绍⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯浙江省2018年1月高等教育自学考试数据构造试题课程代码：02331一、单项选择题(在每题的四个备选 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每题2分，共38分)1.某二叉树的先序序列和后序序列正好同样，则该二叉树必定是()的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子2.以下排序算法中，时间复杂度不受数据初始状态影响，恒为O(logn)的是()2A.堆排序B.冒泡排序C.直接选择排序D.快速排序3.以下排序算法中，()算法可能会出现下边状况：初始数占有序时，花销的时间反而最多。A.堆排序B.冒泡排序C.快速排序D.SHELL排序4.一个栈的输入序列为12345，则以下序列中不行能是栈的输出序列的是()A.23415B.54132C.23145D.154325.设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为()A.r-fB.r-f+1C.(r-f)modn+1D.(r-f+n)modn6.若某链 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 最常用的操作是在最后一个结点以后插入一个结点和删除最后一个结点，则采纳()储存方式最节约时间。A.单链表B.双链表C.带头结点的双循环链表D.单循环链表7.在有n个结点的二叉链表中，值为非空的链域的个数为()A.n-1B.2n-1C.n+1D.2n+18.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为()A.0B.1C.2D.不确立9.数组A［５］［６］的每个元素占5个单元，将其按行优先次序储存在初步地址为1000的连续的内存单元中，则元素A［５，５］的地址为()A.1140B.1145C.1120D.112510.求最短路径的DIJKSTRA算法的时间复杂度为()A.O(n)B.O(n+e)C.O(n2)D.O(n×e)11.对有18个元素的有序表作二分查找，则查找A［3］的比较序列的下标挨次为()A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，312.快速排序算法在最好状况下的时间复杂度为()1⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯精选自学考料介绍⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n)13.以下排序算法中，某一趟束后未必能出一个元素放在其最地址上的是()A.堆排序B.冒泡排序C.快速排序D.直接插入排序14.二叉在索化后，仍不可以有效求解的是()先序索二叉中求先序后B.中序索二叉中求中序后C.中序索二叉中求中序前D.后序索二叉中求后序后15.DFS算法的复度()A.O(n)B.O(n3)C.O(n2)D.O(n+e)16.列操作的原是()A.先先出B.后先出C.只好行插入D.只好行除17.有64个点的完整二叉的深度()(根的次1)。A.8B.7C.6D.518.在均衡二叉中插入一个点后造成了不均衡，最低的不均衡点A，并已知A的左孩子的均衡因子-1，右孩子的均衡因子0，作()型整以使其均衡。A.LLB.LRC.RLD.RR19.数据表A中有10000个元素，假如要求求出此中最大的10个元素，采纳()排序算法最省。A.堆排序B.希排序C.快速排序D.直接排序二、判断(判断以下各，正确的在后括号内打“√”，的打“×”。每小1分，共分)1.出不一样的入序列建筑二叉排序，必定获取不一样的二叉排序。()2.因为希排序的最后一趟与直接插入排序程同样，所以前者必定比后者花的多。()3.在列作出操作，不会改front指的。()4.若一个的入序列123⋯n，其出序列的第一个元素n，其出序列的每个元素ai必定足ai=n-i+1(i=1,2...,n)()5.二叉中的叶子点就是二叉中没有左右子的点。()6.一棵中的叶子点数必定等于与其的二叉中的叶子点数。()7.有向用接矩表示后，点i的人度等于接矩中第i列的元素个数。()8.有向的接表和逆接表中的点数必定同样。()9.除二叉排序中一个点，再重新插入上去，必定能获取本来的二叉排序。()10.G的拓扑序列独一，其弧数必n-1(此中nG的点数)。()三、填空(每空2分，共20分)1.在有n个叶子点的哈夫曼中，点数是_______。2.一棵T采纳二叉表存，假如T中某点叶子点，在二叉表BT中所2⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯精选自学考料介绍⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯的结点必定_______。3.已知数组A［１０］［１０］为对称矩阵，此中每个元素占5个单元。现将其下三角部分按行优先次序储存在初步地址为1000的连续的内存单元中，则元素A［５，６］对应的地址是_______。4.在有n个结点的无向图中，其边数最多为_______。5.拿出广义表A=(x,(a,b,c,d))中原子x的函数是_______。6.对矩阵采纳压缩储存是为了_______。7.带头结点的双循环链表L为空表的条件是_______。8.在双链表中，在指针P所指结点前面插入一个结点S∧时的语句序列是：S->next=P;S->prior=P->prior;P->prior=S;_______；9.对广义表A=(x,((a,b),c,d))的运算head(head(tail(A)))的结果是______。10.判断线索二叉树中某结点指针P所指结点有左孩子的条件是_______。四、简答题(每题5分，共15分)1.求出以下图的一棵最小生成树。2.将下边次序表建成一个小头堆。(70，12，20，31，1，5，44，66，61，200，30，80，150，4，28)3.已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造出该二叉树。五、综合应用题(共17分)1.已知一树的双亲表示法以下，此中各兄弟结点是挨次出现的，画出该树及对应的二叉树。(满分7分)。123456789101112131415dataABCDEFGHIJKLMNOparent0111223344566782.计算二叉树的深度的算法。(10分)3⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯精选自学考料介绍⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯浙江省2018年1月高等教育自学考试数据构造试题参照答案课程代码：02331一、单项选择题(每题2分，共38分)1.A2.B3.C4.B5.D6.C7.A8.B9.A10.C11.D12.B13.D14.D15.C16.A17.B18.A19.C二、判断题(每题1分，共10分)1.√2.×3√4.√5.×6.×7.√8.×9.×10.×三、填空题(每空2分，共20分)n-1左右子树空1225n(n-1)/2head(A)节约空间7.L->next=L->prior或L->next=LS->prior->next=S(a)P->ltag=1四、简答题(每题5分，共15分)1.最小生成树：2.小头堆：112431305206661200708015044283.二叉树：4⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯精选自学考料介绍⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯五、综合应用题(共17分)1.从丛林变换为二叉树：(7分)2.计算二叉树的深度的算法：(10分)intdepth(tree*T){if(!T)return0;elsereturn1+max(depth(T->Lchild),depth(->Rchild));}5