专升本数据结构试题

第1页（共5页）“专升本”考试《数据结构》试题成绩：一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填下列表格内，填在题干的括号内无效。每小题2分，共28分)题号1234567891011121314答案1.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是()的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子2.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(log2n)的是()A.堆排序B.冒泡排序C.直接选择排序D.快速排序3.下列排序算法中，()算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。A.堆排序B.冒泡排序C.快速排序D.希尔排序4.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是()A.23415B.54132C.23145D.154325.设循环队列中数组的下标范围是0～n-1，其头尾指针分别为f和r，则其元素个数为()A.r-fB.r-f+1C.(r-f)modn+1D.(r-f+n)modn6.数组A［５］［６］的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，５］的地址为()A.1140B.1145C.1120D.11257.求最短路径的DIJKSTRA算法的时间复杂度为()A.O(n)B.O(n+e)C.O(n2)D.O(n×e)8.对有18个元素的有序表作二分查找，则查找A［3］的比较序列的下标依次为()A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，39.快速排序算法在最好情况下的时间复杂度为()A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n)试卷编号第2页（共5页）10.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是()A.堆排序B.冒泡排序C.快速排序D.直接插入排序11.哈希查找的时间复杂度为（）。A.O(n)B.O(1)C.O(n2)D.O(nlog2n)12.队列操作的特点是()A.先进先出B.后进先出C.只能进行插入D.只能进行删除13.在完全二叉树中，就层序列号而言，结点i的左孩子如果存在，其编号为()。A.i/2B.2iC.2i-1D.2i+114.数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用()排序算法最节省时间。A.堆排序B.希尔排序C.快速排序D.直接选择排序二、判断题(判断下列各题，正确的在题后括号内打“√”，错的打“×”。每小题1分，共10分)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(其中n为G的顶点数)。()三、填空题(每空2分，共20分)1.在有n个叶子结点的哈夫曼树中，总结点数是_______。2.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定_______。3.已知数组A［１０］［１０］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，６］对应的地址是_______。第3页（共5页）4.在有n个结点的无向图中，其边数最多为_______。5.链接表中添加附加表头的目的是_______。6.对矩阵采用压缩存储是为了_______。7.带头结点的单循环链表L为空表的条件是_______。8.在单链表中，在指针p所指结点后面插入一个结点s时的语句序列是：_______。9.对广义表A=(x,((a,b),c,d))的运算head(head(tail(A)))的结果是______。10.判断链接栈S为空的条件是_______。四、简答题(每小题5分，共25分)1.求出下图的一棵最小生成树。2.简单叙述什么叫堆，并将下面的序列整理成一个小顶堆。(70，12，20，31，1，5，44，66，61，200，30，80，150，4，28)（只要最终结果）3.已知一棵二叉树的先序遍历序列是ABCDEFGHIJK，中序遍历序列是CDBGFEAHJIK，请构造出该二叉树。4．简述二分查找的思想及方法，其时间和空间复杂度各为多少？第4页（共5页）5．简述快速排序的思想及方法，并对其排序性能进行简单的分析。五、编程题(共17分)1.编程计算二叉树T的深度。(7分)。2.写出对整型数组r中下标1-n区域中的数据进行简单选择排序的算法。(10分)。