广东财经大学809数据结构2023年考研真题
2024-02-02
999+
757.89KB
4 页
侵权投诉
欢迎报考广东财经大学硕士研究生，祝你考试成功！（第 1 页 共 4 页）
1
广东财经大学硕士研究生入学考试试卷
考试年度：2023年 考试科目代码及名称：809-数据结构
适用专业：085404计算机技术
［友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！］、
一、单选题（10题，每题1分，共10分）
1. 算法的时间复杂度取决于（ ）。
A.问题的规模 B.待处理数据的初态 C.计算机的配置 D.A和B
2. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，
则采用（ ）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表
C．双链表 D．仅有尾指针的单循环链表
3. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，（ ）是栈的合法输出序列。
A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4
4. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
5. 下面关于串的的叙述中，（ ）是不正确的。
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式
存储6. 设给定权值总数有n个，其哈夫曼树的结点总数为( ) 个。
A．不确定 B．2n C．2n+1 D．2n-1
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. 堆排序、冒泡排序 B. 快速排序、堆排序
C.希尔排序、归并排序 D. 归并排序、冒泡排序
二、简答题（5题，每题10分，共50分）
1. 以下是二叉链表存储结构的表示，s是初值为0的全局变量。假设已经用二叉链表实
现了如图1所示的二叉树的存储，指针root 指向其根结点。函数func( )的代码如图2所示：
欢迎报考广东财经大学硕士研究生，祝你考试成功！（第 2 页 共 4 页）
2
根据以上描述回答问题：
（1）递归算法必须包括哪几个部分？ （2分）
（2）描述func( )函数的基本功能，并说明该函数的递归终止条件。（4分）
（3）执行语句printf(“\n%d\n”,func(root))后，按屏幕格式写出相应的输出结果。（4分）
2.设一棵二叉树的先序序列是：A B D E G C F H K，中序序列是：D B G E A C H F K。
（1）写出这棵二叉树的后序序列。 （3分）
（2）画出这棵二叉树的中序线索二叉树。 （3分）
（3）将这棵二叉树转换为对应的树（或森林）。 （4分）
3.假设图G如图3所示，顶点的存储顺序如图4所示：
根据上图的拓扑结构和顶点顺序，回答以下问题：
（1）画出该图的邻接表存储结构。 （4分）
（2）根据所画的邻接表，从顶点v1 开始按顶点存储顺序正向遍历，写出深度优先遍历
序列。 （3分）
（3）根据所画的邻接表，从顶点v6 开始按顶点存储顺序逆向遍历，写出广度优先遍历
序列。 （3分）
4. 假设散列表长度为11，散列函数为H(key)=key%7，现要将关键字值为{24，10 ，16 ，31 ，19 ，17}
的记录依次放入散列表中，请按要求回答问题：
（1）如果冲突处理方法为开放地址法，增量序列di=12，-12，22，-22，32，-32……，请
画出相应的散列表，并计算等概率下查找成功时的平均查找长度ASLsucc。 （5分）
（2）如果冲突处理方法为链地址法，请画出对应的散列表，并计算等概率下查找失败
图3 图G的拓扑结构
V1
V2
V3
V6
V4
V5
图2 函数func( )的代码
typedef struct BiTNode
{ int data ;
struct BiTNode *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);
else s+=T->data;
func(T->rchild);
return s;
}//if
}//func
图1 根为root 的二叉树
图2 函数function()的伪代码
摘要：
展开>>
收起<<
欢迎报考广东财经大学硕士研究生，祝你考试成功！（第1页共4页）1广东财经大学硕士研究生入学考试试卷考试年度：2023年 考试科目代码及名称：809-数据结构适用专业：085404计算机技术［友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！］、一、单选题（10题，每题1分，共10分）1.算法的时间复杂度取决于（）。A.问题的规模B.待处理数据的初态C.计算机的配置D.A和B2.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表3.设一个栈的输入序...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
