广东财经大学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]用于标记相关节点是否已被访问。作答时，给出必要的分析和说明，以及注释，可以使用伪代码描述算法。
