2020中国传媒大学824数据结构真题回忆

Rachel_R

六、代码题（40分）
1.判断一棵树是二叉排序树，写出算法设计思想，写出代码，计算时间复杂度
2.图的深度优先搜索遍历的非递归算法，写出算法设计思想和代码
3.两个数组（a1...am）和（b1...bn）存储在线性表A[1…m+n]中，要求将两个数组位置互换，写出算法设计思想和代码

五、应用题（4*5）
1.给出一组数进行非递减排序，增量序列d=｛5,3,1｝，写出希尔排序过程和结果
2.给出一组数和装填因子，用线性探查法解决冲突，要求写出哈希函数，画出哈希表，计算等概率情况下的查找成功和失败情况下的平均查找长度
3.给出中序遍历序列和后序遍历序列，要求画出二叉树，并写出先序遍历序列
4.忘记了

四、填空题（10*2）
1.程序的＿＿性是指，对输入数据进行判断，避免对输入的错误数据进行计算后得出乱七八糟的结果
2.三元组和＿＿可以用来存储特殊矩阵和稀疏矩阵
3.给出一组数和排序过程，判断是什么排序
4.计算下列代码的时间复杂度，代码大概是
while（i＜n）  i=i*2；
5.一个二维数组m*n（m和n是具体数字），按列优先存储在一维数组中，每个元素占两个字节，开始位置1024，计算某个具体位置的元素的存储位置
6.给出一组数，计算这组数构成的赫夫曼树的最短带权路径长度
7.一维数组A[m,n]存储在循环队列中，队列满的判断条件是

三、判断题（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. 只有尾指针的带头节点的循环双链表
B. 只有尾指针的带头节点的循环单链表
C. 只有头指针的循环单链表
D. 只有尾指针的带头节点的非循环双链表
7.一个100*100的三对角矩阵，按行优先存储在下标从0开始的一维数组中，A25,26的存储位置是
8.给出一组数是一个堆（题目没说但可判断是小顶堆），插入一个元素调整后得到的堆是
9.对串的描述错误的是
（具体选项忘记了，串在2020大纲里只涉及模式匹配，但还是考了串的基本概念）
10.有n个顶点的图的最小生成树是指
A. 有n个顶点的权值最小的连通子图
B. 有n-1条边的权值最小的连通子图
C. D选项忘记了
来源: [url=forum.php?mod=viewthread&tid=9794842]2020中国传媒大学824数据结构真题回忆[/url]

来自Android客户端

浅黛微妆粉

可以辅导数据结构专业课吗

来自iPhone客户端

半半子

请问楼主有824历年真题吗