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

《考研真题：广东财经大学2019年[数据结构]考试真题》由会员分享，可在线阅读，更多相关《考研真题：广东财经大学2019年[数据结构]考试真题（8页珍藏版）》请在金锄头文库上搜索。

1、考研真题：广东财经大学 2019 年数据结构考试真题考研真题：广东财经大学 2019 年数据结构考试真题一、单项选择题（10 题，每题 2 分，共 20 分）一、单项选择题（10 题，每题 2 分，共 20 分）1、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-next=p;p-prior=p-prior-prior;Dp-prior=p-next-next;p-next=p-prio

2、r-prior;3、3、设栈 S 和队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5 和 e6 依次进入栈 S，一个元素出栈后即进入 Q，若 6 个元素出队的序列是 e2、e4、e3、e6、e5 和 e1，则栈 S 的容量至少应该是_。A2 B3 C4 D 64、4、设有一个递归算法如图 1 所示则计算 fact(n)需要调用该函数的次数为_。A n+1 B n-1 C n D n+2int fact(int n)/n 大于等于 0 if(n=0)return 1;else return n*fact(n-1);图 1图 1图 2图 25、5、对图 2 所示的带权有向图，若采用迪杰

3、斯特拉(Dijkstra)算法求从原点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是_。Af，d，e Be，d，f Cd，e，f Df，e，d6、6、串“ababaaababaa”的 next 数组为_。A012345678999 B012121111212 C0123012322345 D0112342234567、7、对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用_遍历实现编号。A先序 B.中序 C

4、.后序 D.从根开始按层次遍历8、8、下面关于 B-和 B+树的叙述中，不正确的是_。AB-树和 B+树都是平衡的多叉树 BB-树和 B+树都可用于文件的索引结构CB-树和 B+树都能有效地支持顺序检索 DB-树和 B+树都能有效地支持随机检索9、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.基数排序10、10、图 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 分）二、填空题（10 题，每题 3 分，共 30 分）1、1、算法的时间复杂度为 O(1)，意味着算法的执行时间_。2、2、图 4 所示算法，将一维数组 a 中的 n 个数逆序存放到原数组中，其空间复杂度是_（要求用大 O 符号表示）。3、3、在调用图 5 所示递归过程时，如果从键盘输入的数据依次是：3，2，1，0。则屏幕上相应的显示数据依次是_。图图 3for(i=0;ix;i

6、f(x=0)sum=0;else test(sum);sum+=x;coutsum，;图 5图 54、4、一棵完全二叉树的第六层有 10 个叶子结点，则整个二叉树的结点总数为数至多为_。5、5、已知二叉树的二叉链表的类型定义如下：typedef struct nodeTElemType data；/数据域Struct node *lchild,*rchild；/指向左、右孩子的指针域BiTNode,*BiTree有如下函数所描述的算法，它试图求出二叉树的结点总数，请写出下划线处应填写的语句（仅限一个语句）。int NodeCount(BiTree T)if(T=NULL)return 0;/如

7、果是空树，则结点个数为 0，递归结束 else _;/否则结点个数为左子树的结点个数+右子树的结点个数+1（根节点）6、6、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素 58，则它将依次与表中_比较大小，查找结果是失败。7、7、在散列技术中，处理冲突的两种方法是_法和_法。8、8、串“ababaabab”的 nextval 为_。9、9、倘若键值相同的记录，排序前后相对次序总能保持不变，则称排序方法是_的。10、10、若一组记录的关键字是(46,79,56,38,40,84)，则利用快速排序的方法，以第一个关键字为枢轴得到的一趟快速排序结果为_。三

8、、综合应用题（6 题，每题 10 分，共 60 分）三、综合应用题（6 题，每题 10 分，共 60 分）1、1、设一棵二叉树的先序序列：A B D F C E G H，中序序列：B F D A G E H C(1)画出这棵二叉树。(2)画出这棵二叉树的后序线索树。(3)将这棵二叉树转换成对应的树(或森林)。2、2、假设用于通信的电文仅由 8 个字母组成，字母在电文中出现的概率分别为 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。(1)试为这 8 个字母设计赫夫曼(Huffman)编码。(2)从数学期望的角度计算各字符赫夫曼编码的平均长度；若这 8 个字母采用

9、二进制等长编码，各字符的平均编码长度至少是多大？(3)简述赫夫曼编码的特点以及它试图达到目标。3、3、已知无向图 G 的逻辑结构图如图 6 所示，试回答下述问题。(1)画出图 G 的邻接矩阵。(2)依据你画出的邻接矩阵，若从编号为的顶点出发遍历该图，请画出其深度优先生成树。(3)依据你画出的邻接矩阵，若从编号为的顶点出发遍历该图，请画出其广度优先生成树。(4)试说明深度优先遍历、广度优先遍历需要分别借助什么数据结构方可实现。图 6图 6图 7图 74、4、求图 7 所示的带权连通图 G 的最小生成树(MST)，请回答下列问题：(1)若使用克鲁斯卡尔(Kruskal)算法求图 G 的 MST，请

10、依次写出算法选出的边；(2)若使用普利姆(Prim)算法，从顶点 A 开始求图 G 的 MST，请依次写出算法选出的边；(3)图的 MST 唯一吗？(4)请说明在什么情况下带权连通图的 MST 才会唯一。5、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)现有第七个关键字

11、 65，写出其存储地址计算过程（要求写出每一步的计算式和冲突处理）。(3)若查找关键字 65 的记录，需依次与哪些关键字进行比较？(4)若删除 54 应如何处理？6、6、已知一组关键值序列503，87，512，61，908，170，897，275，653，462，试采用堆排序法对该组序列进行降序排序，要求：(1)对该组序列进行降序排序，建立的初始堆应为大根堆还是小根堆？(2)用二叉树的形式画出所建立的初始堆；(3)画出第一次输出堆元素后，经过筛选调整之后的堆。四、算法设计与编程题（4 题，每题 10 分，共 40 分）四、算法设计与编程题（4 题，每题 10 分，共 40 分）1、已知顺序表的

12、类型定义如下：1、已知顺序表的类型定义如下：#define MaxSize typedef struct ElemType*elem;/存储空间基址 int length;/当前表长 SqList;设顺序表 L 中的数据元素非递减有序，试编写函数实现将 e 插入 L 的适当位置，以保持线性表的有序性。函数原型为：bool InsertOrderList(SqList&L,ElemType e)请用类 C 语言写出函数代码，并且加上适当注释，以增加可读性。2、已知单链表的类型定义如下：2、已知单链表的类型定义如下：typedef struct LNode ElemType data;/数据域st

13、ruct LNode*next;/指针域LNode,*LinkList;有一个带头结点的单链表 L，其结点的元素值按非递减的顺序排列，试编写函数，其功能是：审查单链表 L，凡元素值相同的结点只保留其中一个，使得单链表 L 按元素值递增有序。函数原型为：void Delete(LinkList&L)请用类 C 语言写出函数代码，并且加上适当注释，以增加可读性。3、已知图的邻接表存储表示，其类型定义如下：3、已知图的邻接表存储表示，其类型定义如下：#define MVNum 100 /最大顶点数 typedef struct ArcNode /边结点 int adjvex;/该边所指向的顶点的位置

14、 struct ArcNode*nextarc;/指向下一条边的指针 OtherInfo info;/和边相关的信息 ArcNode;typedef struct VNode VerTexType data;/顶点信息 ArcNode*firstarc;/指向第一条依附该顶点的边的指针 VNode,AdjListMVNum;/AdjList 表示邻接表类型 typedef struct AdjList vertices;/邻接表 int vexnum,arcnum;/图的当前顶点数和边数 ALGraph;试基于图的深度优先搜索策略写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点vi 到

15、顶点 vj 的路径（ij）,是则返回 1,否则返回 0。算法函数原型为：int exist_path_DFS(ALGraph G,int i,int j)请用类 C 语言写出函数代码，并且加上适当注释，以增加可读性。4、已知记录的类型定义如下：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 语言写出函数代码，并且加上适当注释，以增加可读性。