专升本数据结构试题

“专科升级”考试数据结构问题试卷编号成就：一、单项选择题(在四个备选答案的每一项中，选择一个正确答案，并将正确答案编号填入下表，填入括号内无效。每项得2分，共28分)标题号1234567891011121314回答1.如果二叉树的序列与二叉树的序列完全相同，那么二叉树必须是()的二叉树。A.空的或只有一个节点b。高度等于节点数C.任何节点都没有左子节点，任何节点都没有右子节点2.在下面的排序算法中，时间复杂度不受数据初始状态的影响，常数O(log2n)为()A.堆排序b .气泡排序C.直接选择排序d .快速排序3.在以下排序算法中，()算法可能有以下情况：当初始数据是有序的时，它花费的时间最多。A.堆排序b .气泡排序C.快速排序d. hill排序4.如果堆栈的输入序列是1 2 3 4 5，下面的序列不能是堆栈的输出序列()A.2 3 4 1 5B。5 4 1 3 2C.2 3 1 4 5D。1 5 4 3 25.将循环队列中数组的下标范围设置为0 n-1，头指针和尾指针分别为f和r，元素个数为()A.r-fB。1D皇家空军司令部。(r-f n) mod n6.阵列A的每个元件5 6占据5个单元，并且根据行优先级存储在起始地址为1000的连续存储单元中，那么元件A 5，5的地址是()A.1140B。公元1145年至1120年。11257.DIJKSTRA算法寻找最短路径的时间复杂度为()A.O(n)b . O(n . e)c . O(N2)d . O(ne)8.对于有18个元素的有序表，用于寻找3的比较序列的下标是()A.1，2，3B。9，5，2，3摄氏度9，5，3D。9，4，2，39.在最好的情况下，快速排序的时间复杂度是()A.O(n)b . O(nlog2n)c . O(N2)d . O(log2n)10.下面的排序算法，在一次行程后可能无法选择一个元素，其最终位置是()A.堆排序b .气泡排序C.快速排序d .直接插入排序11.哈希查找的时间复杂度是()。A.O(n)B. O(1) C. O(n2)D. O(nlog2n)12.队列操作的特征是()A.后进先出C.仅插入d .仅删除13.在一个完整的二叉树中，就层序号而言，如果节点I的左子节点存在，则其编号为()。A.我/2B。2i C. 2i-1D。2i 114.数据表A中有10，000个元素。如果只需要找到最大的10个元素，那么()排序算法是最省时的。A.堆分类b. hill分类c .快速分类d .直接选择分类第二，判断问题(判断下列每个问题，正确地在问题后的括号内打勾，并错误地打勾 。每项扣1分，共10分)1.给定不同的输入序列来建立二进制排序树，并且必须获得不同的二进制排序树。()2.由于Hill的最后一个序列与直接插入序列相同，前者必须比后者花费更多的时间。()3.当链队列排队时，前指针的值不会改变。()4.如果堆栈的输入序列是123n.并且它的输出序列的第一个元素是n，它的输出序列的每个元素ai必须满足AI=n-I 1 (I=1，2.n)。()5.二叉树中的叶节点是二叉树中没有左右子树的节点。()6.树中的叶节点数必须等于其对应二叉树中的叶节点数。()7.在用邻接矩阵表示有向图之后，顶点的度数等于邻接矩阵第一列中的元素数。()8.有向图的邻接表和逆邻接表中的节点数必须相同。()9.删除二进制排序树中的一个节点，然后再次插入它。一定会得到原始的二叉排序树。()10.如果图g的拓扑序列是唯一的，它的弧数必须是n-1(其中n是g的顶点数)。()三、填空(每空2分，共20分)1.在具有N个叶节点的霍夫曼树中，点的和是_ _ _ _ _ _。2.树T存储在二进制链表中。如果树T中的节点是叶节点，则二进制链表BT中的对应节点必须是_ _ _ _ _ _。3.众所周知，阵列A 10 10是一个对称矩阵，其中每个元素占据5个单元。现在，下三角形部分被存储在连续的存储单元中，其起始地址按行优先级顺序为1000，那么对应于元素a 5，6的地址是_ _ _ _ _ _。4.在有n个节点的无向图中，最大边数是_ _ _ _ _ _。5.向链接表中添加附加标题的目的是_ _ _ _ _ _。6.矩阵被压缩存储_ _ _ _ _ _。7.首节点的单循环链表L为空的条件是_ _ _ _ _ _。8.在单链表中，当指针P指向的节点后插入一个节点S时，语句的顺序是：_ _ .9.广义表A=(x，(A，b)，c，d)上的头(尾(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.简述二元搜索的思想和方法。它的时间和空间