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

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

广东财经大学 2021 年数据结构考研真题考试年度：2021 年考试科目代码及名称：809-数据结构（自命题）适用专业：085400 电子信息［友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！］一、单项选择题（每小题 2 分，共 40 分） 1. 关于线性表的说法正确的是（）。 A.线性表的特点是每个元素都有一个前驱和一个后继元素 B.线性表是特征相同的 n（n≥0）个元素构成的有限序列 C.线性表采用顺序存储便于进行插入和删除操作 D.线性表采用链式存储便于进行随机查找操作 2. 表长为 n 的顺序存储的线性表，当在任何位置删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为（）。 A.(n-1)/2 B.n/2 C.(n+1)/2 D.n 3. 假设单链表结点结构为（data,next），删除指针 p 所指结点的后继结点 q 的语句序列是（）。 A.p->next=q->next; free(q); B.p->next=q; free(q); C.free(q);p->next=q->next; D.free(q);p->next=q; 4. 设有一个递归算法如下所示，计算 F(8)需要调用该递归函数的次数为（）。 int F(int n) { if(n<=3) return 1; else return F(n-2)+F(n-4)+1; } A.7 B.8 C.9 D.10 5. 若循环队列 Q 存储在数组 queue[0..n]中，front 是队首位置，rear 是队尾位置（初始 rear=front=0），则元素 e 入队的操作是（）。 A.Q.queue[Q.rear]=e; Q.rear=(Q.rear+1)%n; B.Q.queue[Q.rear]=e; Q.rear=(Q.rear+1)%(n+1); C.Q.rear=(Q.rear+1)%n; Q.queue[Q.rear]=e; D.Q.rear=(Q.rear+1)%(n+1); Q.queue[Q.rear]=e; 6. 关于串的叙述中不正确的是（）。

A.串是字符的有限序列 B.空串是由空格构成的串 C.串既可以采用顺序存储，也可以采用链式存储 D.模式匹配是串的一种重要运算 7. 按照从上至下、由左至右的顺序依次编号，深度为 7 的完全二叉树编号最大的叶结点编号是（）。 A.63 B.64 C.126 D.127 8. 已知完全二叉树的第 7 层有 20 个叶结点，则该二叉树最多有（）个结点。 A.83 B.147 C.214 D.215 9. 设 F 是一个森林，B 是由 F 变换得到的二叉树。若 F 中有 n 个非终端，则 B 中右指针域为空的结点有（）个。 A.n-1 B.n C.n+1 D.n+2 10. 由权值为 15,3,5,10 的四个叶结点构成的哈夫曼树的带权路径长度为（）。 A.46 B.59 C.66 D.88 11. 具有 n 个顶点的有向完全图用邻接表表示时，共有（）个弧结点。 A. n(n-1)/2 B.n(n-1) C.2n(n-1) D.n-1 12. 下面的（）算法适合构造一个稠密图的最小生成树。 A.Prim 算法 B.Kruskal 算法 C.Floy 算法 D.Dijkstra 算法 13. 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用（）查找法。 A.顺序查找 B.折半查找 C.分块查找 D.哈希查找 14. 对 50 个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。 A.4 B.5 C.6 D.7 15. 关于 B-树和 B+树的叙述不正确的是（）。 A.B-树和 B+树都是平衡的多叉树 B.B-树和 B+树都可用于文件的索引结构 C.B-树和 B+树都能有效支持顺序检索 D.B-树和 B+树都能有效支持随机检索 16. 假设散列表长度为 11，散列函数为 H(key)=key%7，冲突处理方法为开放地址法的二次探测再散列。已知表中已有记录的关键字为 32,17,9,27，现要将关键字为 45 的记录加入表

中，则放入的位置是（）。 A.1 B.3 C.5 D.7 17. 从未排序序列中依次取出元素与已排序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的排序方法称为（）。 A.插入排序 B.冒泡排序 C.选择排序 D.归并排序 18. 快速排序法在（）情况下最有利于发挥其长处。 A.待排序数据量大 B.数据中含有多个相同的关键字 C.数据按关键字已基本有序 D.数据按关键字完全无序 19. 下列排序算法中，占用辅助空间最多的是（）。 A.希尔排序 B.快速排序 C.堆排序 D.归并排序 20. 下列排序方法中，其中（）是稳定的。 A.堆排序，冒泡排序 B.快速排序，堆排序 C.选择排序，归并排序 D.归并排序，冒泡排序二、填空题（每空 2 分，共 40 分） 1. 从逻辑结构上看，堆栈是操作受限的（）结构，遵循（）存取原则。 2. 图的主要存储结构有四种：（）、（）、十字链表和邻接多重表表示法。 3. 如果已知二叉树的（）和（）遍历序列，可以唯一确定该二叉树。 4. 平均查找长度 ASL 和数据元素个数无关的查找方法所使用的数据结构是（），在快速排序、归并排序和堆排序中，稳定的排序方法是（）排序。 5. 假设记录 R1 和 R2 的关键字相同且 R1 在 R2 的前面，如果排序后 R1 仍在 R2 的前面则称排序方法是（）的，一般情况下基于（）关键字比较的排序算法是稳定的。 6. 一棵高度为 5 的理想平衡树中，最少含有（）个结点，最多含有（）个结点。 7. 通过将树的（）存储方式转换为（）存储方式，可以利用已有的算法解决树的问题。 8. 已知一颗完全二叉树中共有 768 结点，则该树中共有（）个叶子结点。已知一棵度为 3 的树有 2 个度为 1 的结点，3 个度为 2 的结点，4 个度为 3 的结点，则该树中有（）个叶子结点。

9. G 是一个非连通无向图，共有 28 条边，则该图至少有（）个顶点。在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要（）条弧。 10. 对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示，则表头向量大小为（），邻接表的边结点个数为（）。三、分析计算题（每小题 10 分，共 40 分） 1.设一棵二叉树的中序序列是：BDEAFGCKH，后序序列是：EDBGFKHCA。（1）写出该二叉树的先序序列。（2）画出该二叉树的中序线索二叉树。（3）将这棵二叉树转换成树或森林。 2.图-1 所示是带权的无向网，图中顶点的存储顺序为图-2 所示，要求：（1）画出该无向网的邻接表。（2）按步骤画出根据克鲁斯卡尔算法构造最小生成树的过程(图中标明对应边的权值)。（3）计算最小生成树的权值。 3.假设 Bt 是元素值为字符的二叉链表，其数据结构的表示以及 test 函数的调用如图-3 所示，用图-4 所示的二叉链表 Bt 调用 test 函数。（1）简述 test 函数的功能。

（2）尽量按屏幕显示格式写出运行结果。（3）调用 test 的次数是多少？ 4.设待排序数据的关键字序列为{49,54,60,75,36,93,27}，回答以下问题：（1）写出创建大顶堆的一趟初始建堆的过程，要求写出中间步骤。（2）堆排序采用何种存储结构？是否稳定的排序方法？（3）如果要降序排列全部数据，需要创建大顶堆还是小顶堆？四、算法设计题（每小题 15 分，共 30 分） 1. 在一个非递减有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使链表中不再有重复元素，要求算法时间复杂度为 O(N)。例如：算法输入链表为（19，26，26，32，50，62，62，62，89），则输出为（19，26，32，50， 62，89）。作答时，给出必要的分析和说明，以及注释，用类 C 语言写出尽量完整的程序。 2. 用非递归的方式写出无向图的深度优先遍历算法（DFS）。其中图采用邻接矩阵存储，例如定义一个邻接矩阵 map[N][N]用于存储图，定义一个数组 visited[N]用于标记相关节点是否已被访问。作答时，给出必要的分析和说明，以及注释，可以使用伪代码描述算法。

资料库

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

相关推荐

考研

热门标签

最新资料