2020 年广东财经大学数据结构考研真题考试年度：2020 年 考试科目代码及名称：809- 数据结构（自命题） 适用专业：085400 电子信息 ［友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！］一、 单项选择题（10 题，每题 2 分，共 20 分）1、 设 n 是描述问题规模的非负整数。下面的算法 1 是将一维数组 a 中的 n 个数逆序存放到原数组中，该算法的空间复杂度是________（要求用大 O 符号表示）。A．O(1) B．O(n) C．O(2n) D．O(n2)算法 1：for(i=0; iprior->next=p->next; p->next->prior=p->prior; B．p->next=p->next->next; p->next->prior=p; C．p->priort=p->next->next; p->next=p->prior->prior;D．p->prior-next=p; p->prior=p->prior->prior; 4、 最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是________。A. (rear+1)%n==front B. rear==front C．rear+1==front D. (rear-l)%n==front5、 若让元素 1，2，3，4，5 依次进栈，则出栈次序不可能出现在________种情况。A．5，4，3，2，1 B．4，3，1，2，5 C．2，1，5，4，3 D．2，3，5，4，16、 串“ababaabab”的 nextval 为_________。A．010104101 B．010102101 C．010100011 D．010101011 7、 二叉树是非线性数据结构，所以_________。A．它不能用顺序存储结构存储 B．它不能用链式存储结构存储 C．顺序存储结构和链式存储结构都能存储 D．顺序存储结构和链式存储结构都不能使用 8、 图 1 是一个有向无环图，其拓扑排序结果为________。A．v0、v1、v2、v4、v5、v3、v6 B．v1、v0、v3、v4、v5、v2、v6C．v1、v0、v3、v4、v5、v6、v2 D．v1、v0、v3、v4、v6、v2、v59、 在图 2 所示 AOE 网中，其关键路径长度为________。A．16 B．17 C．18 D．1910、 对一组数据(2，12,16,88,5,10)进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12,16,88,5,10第二趟排序结果：2,5,16,88,12,10第三趟排序结果：2,5,10,88,12,16 则采用的排序方法可能________。A．希尔排序 B. 快速排序 C. 简单选择排序 D. 直接插入排序二、 名词解释（10 题，每题 3 分，共 30 分）1、 数据结构2、 算法3、 算法的 5 个特性4、 算法的时间复杂度 O(1)5、 栈及其特点6、 递归函数7、 队列及其特点8、 串的模式匹配9、 二叉树的线索化10、 AOE 网三、 简答题（6 题，每题 10 分，共 60 分）1、 设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C（1） 画出这棵二叉树； （2）将这棵二叉树转换成对应的树（或森林）。2、 字符及其在报文中出现的频率如下表：字符CASTE频率38456利用 Huffman 树，为这些字符设计一组最优二进制编码，要求：（1）请在答题纸上绘出 Huffman 树，并且按 Huffman 编码规则在该树的每个分支上标上“0”或“1”。为了使答案唯一，请将 Huffman 树上每一层结点的权值按左小右大排列；（2）并在答题纸上自行绘制和填写下表；字符CASTEHuffman 编码（3）若接收到 1001100，这样一串 Huffman 编码，请写出其译码结果。（4）计算其 WPL 值。3、 已知无向图 G 的逻辑结构图如图 3 所示，试回答下述问题。（1）画出图 G 的邻接矩阵。（2）若从编号为１的顶点出发遍历该图，请画出其深度优先生成树和广度优先生成树。4、 针对图 4 所示的无向网：（1）按 Kruscal 算法生成最小生成树的过程，画出各步骤生成的中间图，并最终得出最小生成树；（2）求出最小生成树的代价。图 3图 45、 已知哈希函数为 H(k...
