2020年广东财经大学数据结构考研真题.doc

发布时间：2022-09-15 发布人：admin 分类：说明书资料大小：0.37M 资料格式：doc 举报版权申诉

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

一、单项选择题（10题，每题2分，共20分）

二、名词解释（10题，每题3分，共30分）

三、简答题（6题，每题10分，共60分）

四、算法设计与编程(4题，每题10分，共40分)

1、已知顺序表的类型定义如下：

2、已知二叉链表的类型定义如下：

3、已知单链表的类型定义如下：

4、记录结构定义如下：

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==front

5、若让元素 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，1 6、串“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、v6 C．v1、v0、v3、v4、v5、v6、v2 D．v1、v0、v3、v4、v6、v2、v5 9、在图 2 所示 AOE 网中，其关键路径长度为________。 A．16 B．17 C．18 D．19 10、对一组数据(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、字符及其在报文中出现的频率如下表：字符频率 C 3 A 8 S 4 T 5 E 6 利用 Huffman 树，为这些字符设计一组最优二进制编码，要求：（1）请在答题纸上绘出 Huffman 树，并且按 Huffman 编码规则在该树的每个分支上标上“0” 或“1”。为了使答案唯一，请将 Huffman 树上每一层结点的权值按左小右大排列；（2）并在答题纸上自行绘制和填写下表；字符 C A S T E Huffman 编码（3）若接收到 1001100，这样一串 Huffman 编码，请写出其译码结果。（4）计算其 WPL 值。 3、已知无向图 G 的逻辑结构图如图 3 所示，试回答下述问题。（1）画出图 G 的邻接矩阵。（2）若从编号为１的顶点出发遍历该图，请画出其深度优先生成树和广度优先生成树。 4、针对图 4 所示的无向网：（1）按 Kruscal 算法生成最小生成树的过程，画出各步骤生成的中间图，并最终得出最小生成树；（2）求出最小生成树的代价。图 3 图 4 5、已知哈希函数为 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 应如何处理？ 6、已知一组关键值序列{503，87，512，61，908，170，897，275，653，462}，试采用堆排序法对该组序列进行降序排序，要求：（1）用二叉树的形式画出所建立的初始堆，（2）画出第一次输出堆元素后，经过筛选调整之后的堆。四、算法设计与编程(4 题，每题 10 分，共 40 分) 1、已知顺序表的类型定义如下： 2、已知二叉链表的类型定义如下： #define MaxSize <顺序表的容量> typedef struct BitNode { typedef struct { TElemType data; int *elem; // 存储空间基址 Struct BiTNode int length; // 当前表长 *lchild,*rchild; } SqList; }BiTNode, *BiTree; 设顺序表 L 中数据元素为整型，各个数据元已知二叉树 T 用二叉链表，试用递归素的值均不相同，试编写函数实现删除 L 中值最方法编写函数计算 T 中叶子结点的数目。小的数据元素。函数原型为：请用类 C 语言写出函数代码，并且加上 DeleteMin_Sq(LinkList &L) 适当注释，以增加可读性。请用类 C 语言写出函数代码，并且加上适当注释，以增加可读性。 3、已知单链表的类型定义如下： typedef struct LNode { ElemType data; //数据域 struct LNode *next;//指针域 }LNode, *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 语言写出函数代码，适当加上注释，以增加可读性。

分享到：

赞收藏

资料库

2020年广东财经大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料