1、欢迎报考广东财经大学硕士研究生，祝你考试成功！（第 3 页 共 3 页）广东财经大学硕士研究生入学考试试卷考试年度：2020年 考试科目代码及名称：809-数据结构（自命题） 适用专业：085400电子信息友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！一、 单项选择题（10题，每题2分，共20分）1、 设n是描述问题规模的非负整数。下面的算法1是将一维数组a中的n个数逆序存放到原数组中，该算法的空间复杂度是_（要求用大O符号表示）。AO(1) BO(n) CO(2n) DO(n2)算法1：for(i=0; in; i+) bi=an-(i+1);for(i=0; in; i
2、+) ai=bi;图1图22、 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是_。A访问第i个结点（1=i=n）和求第i个结点的直接前驱B在第i个结点后插入一个新结点（1=i=n）C删除第i个结点（1=iprior-next=p-next; p-next-prior=p-prior; Bp-next=p-next-next; p-next-prior=p; Cp-priort=p-next-next; p-next=p-prior-prior;Dp-prior-next=p; p-prior=p-prior-prior; 4、 最大容量为n的循环队列，队尾指针是rear，队头是fro
3、nt，则队空的条件是_。A. (rear+1)%n=front B. rear=front Crear+1=front D. (rear-l)%n=front5、 若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在_种情况。A5，4，3，2，1 B4，3，1，2，5 C2，1，5，4，3 D2，3，5，4，16、 串“ababaabab”的nextval为_。A010104101 B010102101 C010100011 D010101011 7、 二叉树是非线性数据结构，所以_。A它不能用顺序存储结构存储 B它不能用链式存储结构存储 C顺序存储结构和链式存储结构都能存储 D顺序存储
4、结构和链式存储结构都不能使用 8、 图1是一个有向无环图，其拓扑排序结果为_。Av0、v1、v2、v4、v5、v3、v6 Bv1、v0、v3、v4、v5、v2、v6Cv1、v0、v3、v4、v5、v6、v2 Dv1、v0、v3、v4、v6、v2、v59、 在图2所示AOE网中，其关键路径长度为_。A16 B17 C18 D1910、 对一组数据(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. 快速
5、排序 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树，为这些字符设计一组最优二进
6、制编码，要求：（1）请在答题纸上绘出Huffman树，并且按Huffman编码规则在该树的每个分支上标上“0”或“1”。为了使答案唯一，请将Huffman树上每一层结点的权值按左小右大排列；（2）并在答题纸上自行绘制和填写下表；字符CASTEHuffman编码（3）若接收到1001100，这样一串Huffman编码，请写出其译码结果。（4）计算其WPL值。3、 已知无向图G的逻辑结构图如图3所示，试回答下述问题。（1）画出图G的邻接矩阵。（2）若从编号为的顶点出发遍历该图，请画出其深度优先生成树和广度优先生成树。4、 针对图4所示的无向网：（1）按Kruscal算法生成最小生成树的过程，画出各
7、步骤生成的中间图，并最终得出最小生成树；（2）求出最小生成树的代价。图3图45、 已知哈希函数为H(key)=key % 11，哈希表长度为13，用平方探测再散列处理冲突。表中已存放6个记录，它们的存储地址为：addr(22)=0、addr(12)=1、addr(24)=2、addr(32)=10、addr(54)=10冲突，调整至11、addr(59)=4；其余地址为空。（1） 写出存储地址计算式（H0？, Hi？）（2） 现有第七个关键字65，写出其存储地址计算过程（要求写出每一步的计算式和冲突处理）。（3） 若查找关键字65的记录，需依次与哪些关键字进行比较？（4） 若删除54应如何处理
8、？6、 已知一组关键值序列503，87，512，61，908，170，897，275，653，462，试采用堆排序法对该组序列进行降序排序，要求：（1） 用二叉树的形式画出所建立的初始堆，（2） 画出第一次输出堆元素后，经过筛选调整之后的堆。四、 算法设计与编程(4题，每题10分，共40分)1、 已知顺序表的类型定义如下：#define MaxSize typedef struct int *elem; / 存储空间基址 int length; / 当前表长 SqList;设顺序表L中数据元素为整型，各个数据元素的值均不相同，试编写函数实现删除L中值最小的数据元素。函数原型为：DeleteMi
9、n_Sq(LinkList &L)请用类C 语言写出函数代码，并且加上适当注释，以增加可读性。2、 已知二叉链表的类型定义如下：typedef struct BitNode TElemType data;Struct BiTNode *lchild,*rchild;BiTNode, *BiTree;已知二叉树 T用二叉链表，试用递归方法编写函数计算T中叶子结点的数目。请用类C 语言写出函数代码，并且加上适当注释，以增加可读性。3、 已知单链表的类型定义如下：typedef struct LNode ElemType data; /数据域struct LNode *next;/指针域LNode,
10、 *LinkList;设带头结点的单链表L，其数据元素非递减有序，试编写函数实现将数据元素e插入L的适当位置，以保持该链表的依然非递减有序。函数原型为：bool InsertOrderList(LinkList &L, ElemType e)请用类C 语言写出函数代码，并且加上适当注释，以增加可读性。4、 记录结构定义如下：typedef struct int key ; /关键字域 Infotype otherinfo; /其它域RecordType;记录依顺序存储结构存放，其类型定义如下：#define MAXSIZE 100 /最大记录数 typedef struct RecordType MAXSIZE +1; /0号单元不存记录 int length; SqList;依据冒泡排序思路，编写实现升序排序的函数，函数原型为：void BubbleSort (Sqlist &L)请用类C 语言写出函数代码，适当加上注释，以增加可读性。3
