2019年广东财经大学数据结构考研真题.doc-资料库

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

2019 年广东财经大学数据结构考研真题考试年度：2019 年考试科目代码及名称：809-数据结构（自命题）适用专业：085211 工程硕士（计算机技术）［友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！］一、单项选择题（10 题，每题 2 分，共 20 分） 1、设 n 是描述问题规模的非负整数，下面的程序片段的时间复杂度是________。 i=2; while(i<=n) i=i*2; A．O(n2) B．O(n) C．O(nlog 2 n) D．O(log 2 n) 2、在双向链表存储结构中，删除 p 所指的结点时须修改指针（）。 A．p->next->prior=p->prior; p->prior->next=p->next; B．p->next=p->next->next; p->next->prior=p; C．p->prior->next=p; p->prior=p->prior->prior; D．p->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 的容量至少应该是________。 A．2 B．3 C．4 D． 6 4、设有一个递归算法如图 1 所示则计算 fact(n)需要调用该函数的次数为________。 B． n-1 C． n A． n+1 D． n+2 int fact(int n) { //n 大于等于 0 if(n<=0) return 1; else return n*fact(n-1); } 图 1 图 2 5、对图 2 所示的带权有向图，若采用迪杰斯特拉(Dijkstra)算法求从原点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是________。 A．f，d，e B．e，d，f C．d，e，f D．f， e，d 6、串“ababaaababaa”的 next 数组为________。 A．012345678999 B．012121111212 C．0123012322345 D．011234223456 7、对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用________遍历实现

编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 8、下面关于 B-和 B+树的叙述中，不正确的是________。 B．B-树和 B+树都可用于文件的索引结构 A．B-树和 B+树都是平衡的多叉树 C．B-树和 B+树都能有效地支持顺序检索 D．B-树和 B+树都能有效地支持随机检索 9、对一组数据(2，12,16,88,5,10)进行排序，若前三趟排序结果如下：第一趟排序结果：2,12,16,5,10,88 第三趟排序结果：2,5,10,12,16,88 则采用的排序方法可能________。第二趟排序结果：2,12,5,10,16,88 A．希尔排序 B. 起泡排序 C. 归并排序 D. 基数排序 10、图 3 是一个有向无环图，其拓扑排序结果为________。 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 二、填空题（10 题，每题 3 分，共 30 分） 1、算法的时间复杂度为 O(1)，意味着算法的执行时间_____________________。 2、图 4 所示算法，将一维数组 a 中的 n 个数逆序存放到原数组中，其空间复杂度是_____ （要求用大 O 符号表示）。 3、在调用图 5 所示递归过程时，如果从键盘输入的数据依次是：3，2，1，0。则屏幕上相应的显示数据依次是________。图 3 for(i=0; i>x; if(x==0)sum=0; else { test(sum);sum+=x;cout<

//否则结点个数为左子树的结点个数+右子树的结点个数+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、设一棵二叉树的先序序列： 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 所示，试回答下述问题。 (1)画出图 G 的邻接矩阵。 (2)依据你画出的邻接矩阵，若从编号为１的顶点出发遍历该图，请画出其深度优先生成树。 (3)依据你画出的邻接矩阵，若从编号为１的顶点出发遍历该图，请画出其广度优先生成树。 (4)试说明深度优先遍历、广度优先遍历需要分别借助什么数据结构方可实现。图 6 图 7 4、求图 7 所示的带权连通图 G 的最小生成树(MST)，请回答下列问题： (1)若使用克鲁斯卡尔(Kruskal)算法求图 G 的 MST，请依次写出算法选出的边； (2)若使用普利姆(Prim)算法，从顶点 A 开始求图 G 的 MST，请依次写出算法选出的边； (3)图Ｇ的 MST 唯一吗？ (4)请说明在什么情况下带权连通图的 MST 才会唯一。 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) 用二叉树的形式画出所建立的初始堆； (3) 画出第一次输出堆元素后，经过筛选调整之后的堆。四、算法设计与编程题（4 题，每题 10 分，共 40 分） 1、已知顺序表的类型定义如下： 2、已知单链表的类型定义如下： #define MaxSize typedef struct { <顺序表的容量> typedef struct LNode { ElemType *elem; // 存储空间基址 length; // 当前表长 int } SqList; 设顺序表 L 中的数据元素非递减有序，试编写函数实现将 e 插入 L 的适当位置，以保持线性表的有序性。函数原型为： bool InsertOrderList(SqList &L, ElemType e) ElemType data; struct LNode *next;//指针域 //数据域 }LNode, *LinkList; 有一个带头结点的单链表 L，其结点的元素值按非递减的顺序排列，试编写函数，其功能是：审查单链表 L，凡元素值相同的结点只保留其中一个，使得单链表 L 按元素值递增有序。函数原型为：void Delete(LinkList &L) 请用类 C 语言写出函数代码，并且加上请用类 C 语言写出函数代码，并且加上适适当注释，以增加可读性。当注释，以增加可读性。 3、已知图的邻接表存储表示，其类型定义如下： #define MVNum 100 typedef struct ArcNode{ //最大顶点数 //边结点 //该边所指向的顶点的位置 int adjvex; struct ArcNode *nextarc;//指向下一条边的指针 OtherInfo info; //和边相关的信息 }ArcNode; typedef struct VNode{ VerTexType data; ArcNode *firstarc; }VNode, AdjList[MVNum]; typedef struct{ //顶点信息 //指向第一条依附该顶点的边的指针 //AdjList 表示邻接表类型 AdjList vertices; int vexnum, arcnum; //邻接表 //图的当前顶点数和边数 }ALGraph;

试基于图的深度优先搜索策略写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点 vi 到顶点 vj 的路径（i≠j）,是则返回 1,否则返回 0。算法函数原型为：int exist_path_DFS(ALGraph G,int i,int j) 请用类 C 语言写出函数代码，并且加上适当注释，以增加可读性。 4、已知记录的类型定义如下： typedef struct{ int key ; Infotype otherinfo; //其它 //关键字域记录依顺序存储结构存放，其类型定义如下： #define MAXSIZE 100 //最大记录数 typedef struct{ RecordType r[MAXSIZE +1]; //0 号单元不存记域 } RecordType; 录 int length; } SqList; 编写算法，对依上述方式存储的关键字为整型值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：①至多使用一个记录的辅助存储空间； ② 算法的时间复杂度为 O(n),n 是表中记录的个数； ③ 算法函数原型为： void Process(SqList L) 请：(1)简述算法思路；(2)用类 C 语言写出函数代码，并且加上适当注释，以增加可读性。

资料库

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

相关推荐

考研

热门标签

最新资料