809-数据结构--2023年广东财经大学硕士研究生入学考试试卷

2023年12月2日发(作者：时间同步出错)

-

广东财经大学硕士研究生入学考试试卷

考试年度：2023年

适用专业：085404计算机技术

考试科目代码及名称：809-数据结构

［友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效!］、

一、单选题（10题，每题1分，共10分）

1 .算法的时间复杂度取决于（）o

A.问题的规模 B.待处理数据的初态 C.计算机的配置 D.A和B

2 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A.单链表

C.双链表

B.仅有头指针的单循环链表

D.仅有尾指针的单循环链表

3 .设一个栈的输入序列是1,2,3,4,5,则下列序列中，（）是栈的合法输出序歹h

A.51234B.45132C.43125D.32154

4 .若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3,当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。

A.1和5 B.2和4 C.4和2 D.5和1

5 .下面关于串的的叙述中，（）是不正确的。

A.串是字符的有限序列

C.模式匹配是串的一种重要运算

存储

6 .设给定权值总数有n个，其哈夫曼树的结点总数为（）个。

A.不确定B.2n C.2n+l D.2n-l

B.空串是由空格构成的串

D.串既可以采用顺序存储，也可以采用链式

7 .具有k条边的无向图，对其邻接矩阵的对称性及非零元素的数量，下列说法正确的是（）。

A.不对称2k个B.对称2k个C.不对称k个D.对称k个

8 .对50个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。

A.3 B.4 C.5 D.6

9 .不能保证每趟排序至少能将一个元素放到其最终位置上的排序方法是（）。

A.插入排序 B.快速排序C.冒泡排序 D.堆排序

10 .下列几种排序方法中，（）是稳定的排序方法。

A.堆排序、冒泡排序

C.希尔排序、归并排序

B.快速排序、堆排序

D.归并排序、冒泡排序

二、简答题（5题，每题10分，共50分）

1 .以下是二叉链表存储结构的表示，s是初值为0的全局变量。假设已经用二叉链表实现了如图1所示的二叉树的存储，指针root指向其根结点。函数func（）的代码如图2所示: typedef struct BiTNode

{ int data;

struct BiTNodc *lchild, *rchild ;

)*BiTree;

int s=0;

〃二叉链表定义

〃全局变量s

int func(BiTree T)

(

if (T)

(func(T->lchild);

if (T->data%2!=0)

printf("%d∖tπ,T->data+10);

el s+=,F>dala;

func(T->rchild);

retum s;

)∕∕if

)∕∕func

图1根为root的二叉树 图2函数function()的伪代码

根据以上描述回答问题：

(1)递归算法必须包括哪几个部分？ (2分)

(2)描述func()函数的基本功能，并说明该函数的递归终止条件。(4分)

(3)执行语句Printf("∖n%d∖n”,func(root))B,按屏幕格式写出相应的输出结果。(4分)

2 .设一棵二叉树的先序序列是：ABDEGCFHK,中序序列是：DBGEACHFKo

(1)写出这棵二叉树的后序序列。(3分)

(2)画出这棵二叉树的中序线索二叉树。(3分)

(3)将这棵二叉树转换为对应的树(或森林)。(4分)

3 .假设图G如图3所示，顶点的存储顺序如图4所示:

vl v2 v3 v4 v5 v6

图4顶点的存储顺序

根据上图的拓扑结构和顶点顺序，回答以下问题：

(1)画出该图的邻接表存储结构。(4分)

(2)根据所画的邻接表，从顶点Vl开始按顶点存储顺序正向遍历，写出深度优先遍历序列。(3分)

(3)根据所画的邻接表，从顶点v6开始按顶点存储顺序逆向遍历，写出广度优先遍历序列。(3分)

4 .假设散列表长度为11,散列函数为H(key)=key%7,现要将关键字值为(24,10,16,31,19,17｝的记录依次放入散列表中，请按要求回答问题：

(1)如果冲突处理方法为开放地址法,增量序列4=亿」2,22,W32,0……，请画出相应的散列表，并计算等概率下查找成功时的平均查找长度ASLsucco(5分)

(2)如果冲突处理方法为链地址法，请画出对应的散列表，并计算等概率下查找失败时的平均查找长度ASLunsucc<.（5分） 5 .假设待排序元素的关键字序列为｛78,55,86,45,60,100,70,98,35）,试回答以下问题：

（1）写出第一趟快速排序的执行过程，要求写出原始序列，之后每移动一次元素写出一行。（5分）

（2）快速排序在什么情况下达到最佳时间性能？写出最佳情况下的时间凝杂度。（2分）

（3）为避免最坏情况的出现可采取什么优化措施？写出其基本思想。（3分）

三、综合分析题（3题，每题30分，共90分）

1.假设某班的班长创建如下图所示的班级通讯录，包括学号、姓名和电话号码三项内容并按学号递增顺序排列，对通讯录的日常管理包括存储、查询和编辑（增删改）。

Number（in型） Name（char型） Telephone（int型）

220501

220502

220503

220504

张三

李四

王五

赵六

185****2222

185****4444

185****6666

185****8888

如果你是班长，需要编程实现对通讯录的日常管理，试回答以下问题：

（1）你认为该通讯录在内存中处理时应采用何种存储结构？请说明理由。（4分）

（2）根据你所采用的存储结构，写出记录的结构定义和通讯录的存储表示。（6分）

（3）假如有同学要转学离开班级，设计算法Delete（）实现下述功能：根据给定的姓名值查找该同学，如果找到则将该记录从通讯录中删除，未找到则给出“该同学不在本班！”的提示信息。（10分）

（4）假如有新同学要插班进来，设计算法InSert（）实现下述功能：根据给定的学号查找是否存在对应的记录，如果未找到则将该记录插入相应位置依然保持按学号递增有序，找到则用新记录替换原记录。（10分）

温馨提示：算法首选用类C或其他语言的伪代码描述，也可用自然语言或流程图描述。

6 .某省的六个地级市（用符号A、B、C、D、E、F表示）之间计划修建可双向行驶的高速公路，从而实现任意两个城市之间的连通。根据地质结构和经费预算列出可能修建的高速路段以及预计费用（单立：亿元）如下表所示：

城市1 城市2 预计费用（亿元）

5

2

4

7

3

5

8

3

6

1

A

A

A

B

B

C

C

C

D

E

B

C

D

C

E

D

E

F

F

F

现在要解决的问题是如何以最少的建设费用、修建最少的高速路段以连通任意两个城TtJo如果让你设计施工方案，请根据以上信息回答问题： （1）你认为用什么数据结构描述该问题？请根据上表信息画出拓扑结构图并标出权值。（3分）

（2）写出你打算采用的存储结构表示，并设计Create（）算法创建基于该存储结构之上的相应数据结构。（12分）

（3）你认为可以用什么算法解决该问题？请说明你选择该算法的理由，然后按步骤画出该算法的执行过程。

路的总费用是多少？

（12分）

（3分）

（4）假如每个路段的预计费用即为最终的实际费用，那么建成连通这六个地级市的高速公温馨提示：算法首选用类C或其他语言的伪代码描述，也可用自然语言或流程图描述。

7 .某班的期末考试结束了，班主任要计算全班同学的语文、数学、英语的三科总分，然后按照总分（Score）的降序排列并准备奖励排名前10的同学，要求排序不改变总分相同的同学原来的排列顺序（比如：张三排在赵六的前面且总分相同，排序后仍保持张三排在赵六的前面）。假设如下所示的成绩表采用顺序存储结构，如果班主任委托你完成该项任务，请回答以下问题：

No

1

2

3

4

.......

Name

张三

李四

王五

赵六

...

Chine

78.5

85.0

96.5

82.5

......

Maths

95.0

90.5

93.0

87.0

......

English

86.5

80.5

89.5

90.5

......

Score

260.0

256.0

279.0

260.0

......

（1）请写出该成绩表的顺序存储结构的表示。（3分）

（2）要满足排序要求，你认为应采取什么排序方法？请说明理由。（3分）

（3）根据你定义的存储结构，设计算法SCOreSOrt（）实现如下功能：假设每位同学的单科成绩已经录入，先求出三科成绩的相加和SCOre,再根据你选择的排序方法按照SCOre的非递增顺序排序。（12分）

（4）在按总分排序后的成绩表中按给定的总分进行检索，你认为用什么查找方法效率较高，请说明理由。设计算法SearCh（）实现按总分检索的功能，如果找到则返回该记录全部信息，未找到则给出“未找到相应记录”的提示信息。（12分）

温馨提示：算法首选用类C或其他语言的伪代码描述，也可用自然语言或流程图描述。

-