资源描述
新祥旭考研辅导咨询 VX: 15201309109 或 QQ：31777153442020 年中国传媒大学 824 数据结构考研初试真题六、代码题（40 分）1.判断一棵树是二叉排序树，写出算法设计思想，写出代码，计算时间复杂度2.图的深度优先搜索遍历的非递归算法，写出算法设计思想和代码3.两个数组（a1.am）和（b1.bn）存储在线性表 A1m+n中，要求将两个数组位置互换，写出算法设计思想和代码五、应用题（4*5）1.给出一组数进行非递减排序，增量序列 d=5,3,1，写出希尔排序过程和结果2.给出一组数和装填因子，用线性探查法解决冲突，要求写出哈希函数，画出哈希表，计算等概率情况下的查找成功和失败情况下的平均查找长度3.给出中序遍历序列和后序遍历序列，要求画出二叉树，并写出先序遍历序列4.忘记了四、填空题（10*2）1.程序的性是指，对输入数据进行判断，避免对输入的错误数据进行计算后得出乱七八糟的结果2.三元组和可以用来存储特殊矩阵和稀疏矩阵3.给出一组数和排序过程，判断是什么排序4.计算下列代码的时间复杂度，代码大概是while（in） i=i*2；5.一个二维数组 m*n（m 和 n 是具体数字），按列优先存储在一维数组中，每个元素占两个字节，开始位置 1024，计算某个具体位置的元素的存储位置6.给出一组数，计算这组数构成的赫夫曼树的最短带权路径长度7.一维数组 Am,n存储在循环队列中，队列满的判断条件是新祥旭考研辅导咨询 VX: 15201309109 或 QQ：3177715344三、判断题（10*2）1.折半查找判定树是一棵完全二叉树2.一个关于大顶堆中元素大小的表述，具体忘记了二、多选题（10*2）1.以下时间复杂度相同的是A. 克鲁斯卡尔算法 B. 冒泡排序C. 迪杰斯特拉算法 D. 拓扑排序2.对 B-树的特性描述正确的是A. 叶子结点不在同一层B. 叶子结点有指针连接其他两个正确选项不记得了3.给出一组数的第二趟排序结果，可能是以下哪种排序4.给出进栈序列，以及第几个（具体第几忘记了）出栈的元素是 a，以下可能的出栈序列是5.以下排序算法，排序趟数与初始状态无关的是一、单选题（15*2）1.对一个有 n 个顶点，e 条边的无向图，删除某个顶点及其邻接边的时间复杂度是A. ne B. n+e C. n D. 不记得了2.第六层有 24 个叶子结点的完全二叉树最多有几个结点3.高度为 h 的完全二叉树只有度为 0 和 2 的结点，则这棵树有几个结点4.有 n 个分支节点的二叉树高度是5.一个只有尾指针 rear 的带头节点的单链表，删除第一个元素的算法是选项中给出具体的算法语句6.若一个链表只有四种操作：删除第一个结点，删除最后一个结点，在第一个结点前插入元素，在最后一个结点后插入元素，则最好用以下哪种链表储存A. 只有尾指针的带头节点的循环双链表新祥旭考研辅导咨询 VX: 15201309109 或 QQ：3177715344B. 只有尾指针的带头节点的循环单链表C. 只有头指针的循环单链表D. 只有尾指针的带头节点的非循环双链表7.一个 100*100 的三对角矩阵，按行优先存储在下标从 0 开始的一维数组中，A25,26 的存储位置是8.给出一组数是一个堆（题目没说但可判断是小顶堆），插入一个元素调整后得到的堆是9.对串的描述错误的是（具体选项忘记了，串在 2020 大纲里只涉及模式匹配，但还是考了串的基本概念）10.有 n 个顶点的图的最小生成树是指A. 有 n 个顶点的权值最小的连通子图B. 有 n-1 条边的权值最小的连通子图C. D 选项忘记了
展开阅读全文