考研真题:广东财经大学2020年[数据结构]考试真题

2024年1月12日发(作者：教科网)

考研真题：广东财经大学2020年[数据结构]考试真题一、单项选择题（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; i

b[i]=a[n-(i+1)];for(i=0; i

a[i]=b[i];图1图22、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是________。A．访问第i个结点（1<=i<=n）和求第i个结点的直接前驱B．在第i个结点后插入一个新结点（1<=i<=n）C．删除第i个结点（1<=i<=n）D．将n个结点从小到大排序3、在双向链表中，删除结点p的操作是________。A．p->prior->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、数据结构4、算法的时间复杂度O(1)7、队列及其特点10、AOE网2、算法5、栈及其特点8、串的模式匹配3、算法的5个特性6、递归函数9、二叉树的线索化三、简答题（6题，每题10分，共60分）1、设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C（1）画出这棵二叉树； （2）将这棵二叉树转换成对应的树（或森林）。2、字符及其在报文中出现的频率如下表：

字符频率C3A8S4T5E6利用Huffman树，为这些字符设计一组最优二进制编码，要求：（1）请在答题纸上绘出Huffman树，并且按Huffman编码规则在该树的每个分支上标上“0”或“1”。为了使答案唯一，请将Huffman树上每一层结点的权值按左小右大排列；（2）并在答题纸上自行绘制和填写下表；字符Huffman码（3）若接收到1001100，这样一串Huffman编码，请写出其译码结果。（4）计算其WPL值。编CASTE3、已知无向图G的逻辑结构图如图3所示，试回答下述问题。（1）画出图G的邻接矩阵。（2）若从编号为１的顶点出发遍历该图，请画出其深度优先生成树和广度优先生成树。4、针对图4所示的无向网：（1）按Kruscal算法生成最小生成树的过程，画出各步骤生成的中间图，并最终得出最小生成树；（2）求出最小生成树的代价。图4图35、已知哈希函数为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、已知顺序表的类型定义如下：#define MaxSize <顺序表的容量>typedef struct {

int *elem; // 存储空间基址int length; // 当前表长2、已知二叉链表的类型定义如下：typedef struct BitNode {TElemType data;Struct BiTNode *lchild,*rchild;}BiTNode, *BiTree;已知二叉树 T用二叉链表，试用递归方法} SqList;设顺序表L中数据元素为整型，各个数据元素的编写函数计算T中叶子结点的数目。请用值均不相同，试编写函数实现删除L中值最小的类C 语言写出函数代码，并且加上适当数据元素。函数原型为：DeleteMin_Sq(LinkList 注释，以增加可读性。&L)请用类C 语言写出函数代码，并且加上适当注释，以增加可读性。3、已知单链表的类型定义如下：typedef struct LNode {

ElemType data; //数据域struct LNode *next;//指针域}LNode, *LinkList;设带头结点的单链表L，其数据元素非递减有序，试编写函数实现将数据元素e插入L的适当位置，以保持该链表的依然非递减有序。函数原型为：bool InrtOrderList(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 语言写出函数代码，适当加上注释，以增加可读性。