1、欢迎报考广东财经大学硕士研究生，祝你考试成功！（第 5 页 共 5 页）广东财经大学硕士研究生入学考试试卷考试年度：2019年 考试科目代码及名称：809-数据结构（自命题） 适用专业：085211 工程硕士（计算机技术）友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！一、 单项选择题（10题，每题2分，共20分）1、 设n是描述问题规模的非负整数，下面的程序片段的时间复杂度是_。i=2; while(inext-prior=p-prior; p-prior-next=p-next;Bp-next=p-next-next; p-next-prior=p;Cp-prior-ne
2、xt=p; p-prior=p-prior-prior;Dp-prior=p-next-next; p-next=p-prior-prior;3、 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是_。A2 B3 C4 D 64、 设有一个递归算法如图1所示则计算fact(n)需要调用该函数的次数为_。An+1 Bn-1 C n D n+2int fact(int n) /n大于等于0 if(n=0) return 1; else return n*fact(
3、n-1);图1图25、 对图2所示的带权有向图，若采用迪杰斯特拉(Dijkstra)算法求从原点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是_。Af，d，e Be，d，f Cd，e，f Df，e，d6、 串“ababaaababaa”的next数组为_。A012345678999 B012121111212 C0123012322345 D0112342234567、 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采
4、用_遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按层次遍历8、 下面关于B-和B+树的叙述中，不正确的是_。 AB-树和B+树都是平衡的多叉树 BB-树和B+树都可用于文件的索引结构CB-树和B+树都能有效地支持顺序检索 DB-树和B+树都能有效地支持随机检索9、 对一组数据(2，12,16,88,5,10)进行排序，若前三趟排序结果如下： 第一趟排序结果：2,12,16,5,10,88第二趟排序结果：2,12,5,10,16,88第三趟排序结果：2,5,10,12,16,88 则采用的排序方法可能_。A希尔排序 B. 起泡排序 C. 归并排序 D. 基数排序图310、 图3是
5、一个有向无环图，其拓扑排序结果为_。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、v5二、 填空题（10题，每题3分，共30分）1、 算法的时间复杂度为O(1)，意味着算法的执行时间_。2、 图4所示算法，将一维数组a中的n个数逆序存放到原数组中，其空间复杂度是_（要求用大O符号表示）。3、 在调用图5所示递归过程时，如果从键盘输入的数据依次是：3，2，1，0。则屏幕上相应的显示数据依次是_。for(i=0; ix;if(x=0)sum=0;else test(sum);s
6、um+=x;coutsum，; 图54、 一棵完全二叉树的第六层有10个叶子结点，则整个二叉树的结点总数为数至多为_。5、 已知二叉树的二叉链表的类型定义如下：typedef struct node TElemType data；/数据域 Struct node *lchild, *rchild；/指向左、右孩子的指针域BiTNode, *BiTree有如下函数所描述的算法，它试图求出二叉树的结点总数，请写出下划线处应填写的语句（仅限一个语句）。int NodeCount( BiTree T ) if(T=NULL) return 0; / 如果是空树，则结点个数为0，递归结束 else _;
7、 /否则结点个数为左子树的结点个数+右子树的结点个数+1（根节点） 6、 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中_比较大小，查找结果是失败。7、 在散列技术中，处理冲突的两种方法是_法和_法。8、 串“ababaabab”的nextval为_。9、 倘若键值相同的记录，排序前后相对次序总能保持不变，则称排序方法是_的。10、 若一组记录的关键字是(46,79, 56,38,40,84)，则利用快速排序的方法，以第一个关键字为枢轴得到的一趟快速排序结果为_。三、 综合应用题（6题，每题10分，共60分） 1、 设一棵二叉树
8、的先序序列： A B D F C E G H ，中序序列： B F D A G E H C(1)画出这棵二叉树。(2)画出这棵二叉树的后序线索树。(3)将这棵二叉树转换成对应的树(或森林)。2、 假设用于通信的电文仅由8个字母组成，字母在电文中出现的概率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。(1)试为这8个字母设计赫夫曼(Huffman)编码。(2)从数学期望的角度计算各字符赫夫曼编码的平均长度；若这8个字母采用二进制等长编码，各字符的平均编码长度至少是多大？(3)简述赫夫曼编码的特点以及它试图达到目标。3、 已知无向图G的逻辑结构图如图6所示，
9、试回答下述问题。(1)画出图G的邻接矩阵。(2)依据你画出的邻接矩阵，若从编号为的顶点出发遍历该图，请画出其深度优先生成树。(3)依据你画出的邻接矩阵，若从编号为的顶点出发遍历该图，请画出其广度优先生成树。(4)试说明深度优先遍历、广度优先遍历需要分别借助什么数据结构方可实现。图6图74、 求图7所示的带权连通图G的最小生成树(MST)，请回答下列问题：(1)若使用克鲁斯卡尔(Kruskal)算法求图G的MST，请依次写出算法选出的边；(2)若使用普利姆(Prim)算法，从顶点A开始求图G的MST，请依次写出算法选出的边；(3)图的MST唯一吗？(4)请说明在什么情况下带权连通图的MST才会唯
10、一。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，2
11、75，653，462，试采用堆排序法对该组序列进行降序排序，要求：(1) 对该组序列进行降序排序，建立的初始堆应为大根堆还是小根堆？(2) 用二叉树的形式画出所建立的初始堆；(3) 画出第一次输出堆元素后，经过筛选调整之后的堆。四、 算法设计与编程题（4题，每题10分，共40分）1、 已知顺序表的类型定义如下：#define MaxSize typedef struct ElemType *elem; / 存储空间基址 int length; / 当前表长 SqList;设顺序表L中的数据元素非递减有序，试编写函数实现将e插入L的适当位置，以保持线性表的有序性。函数原型为：bool Inser
12、tOrderList(SqList &L, ElemType e)请用类C 语言写出函数代码，并且加上适当注释，以增加可读性。2、 已知单链表的类型定义如下：typedef struct LNode ElemType data; /数据域struct LNode *next;/指针域LNode, *LinkList;有一个带头结点的单链表L，其结点的元素值按非递减的顺序排列，试编写函数，其功能是：审查单链表L，凡元素值相同的结点只保留其中一个，使得单链表L按元素值递增有序。函数原型为：void Delete(LinkList &L)请用类C 语言写出函数代码，并且加上适当注释，以增加可读性。3
13、、 已知图的邻接表存储表示，其类型定义如下：#define MVNum 100 /最大顶点数 typedef struct ArcNode /边结点 int adjvex; /该边所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条边的指针 OtherInfo info; /和边相关的信息 ArcNode; typedef struct VNode VerTexType data; /顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的边的指针 VNode, AdjListMVNum; /AdjList表示邻接表类型 typedef struct
14、 AdjList vertices; /邻接表 int vexnum, arcnum; /图的当前顶点数和边数 ALGraph;试基于图的深度优先搜索策略写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（ij）,是则返回1,否则返回0。算法函数原型为：int exist_path_DFS(ALGraph G,int i,int j)请用类C 语言写出函数代码，并且加上适当注释，以增加可读性。4、 已知记录的类型定义如下：typedef struct int key ; /关键字域 Infotype otherinfo; /其它域 RecordType;记录依顺序存储结构存放，其类型定义如下：#define MAXSIZE 100 /最大记录数 typedef struct RecordType rMAXSIZE +1; /0号单元不存记录 int length; SqList;编写算法，对依上述方式存储的关键字为整型值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：至多使用一个记录的辅助存储空间；算法的时间复杂度为O(n),n是表中记录的个数； 算法函数原型为：void Process(SqList L)请：(1)简述算法思路；(2)用类C 语言写出函数代码，并且加上适当注释，以增加可读性。5
