广东财经大学-F-809数据结构【2019】考研真题
2023-06-20
999+
463.5KB
6 页
侵权投诉
欢迎报考广东财经大学硕士研究生，祝你考试成功！（第 1 页 共 6 页）
广东财经大学硕士研究生入学考试试卷
考试年度：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)需要调用该函数的次数为________。£
A．£n+1£££ ££ B．£n-1£££££ C． n£££££ 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+树的叙述中，不正确的是________。
A．B-树和 B+树都是平衡的多叉树 B．B-树和 B+树都可用于文件的索引结构
1
欢迎报考广东财经大学硕士研究生，祝你考试成功！（第 2 页 共 6 页）
C．B-树和 B+树都能有效地支持顺序检索 D．B-树和 B+树都能有效地支持随机检索
9、 对一组数据(2，12,16,88,5,10)进行排序，若前三趟排序结果如下：
第一趟排序结果：2,12,16,5,10,88 第二趟排序结果：2,12,5,10,16,88
第三趟排序结果：2,5,10,12,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。则屏幕上相应的显示数据
依次是________。
for(i=0; i<n/2; i++)
{ temp=a[i];
a[i]=a[n-(i+1)];
a[n-(i+1)]=temp;
}
图 4
void test(int &sum)
{ int x;
cin>>x;
if(x==0)sum=0;
else { test(sum);sum+=x;cout<<sum<<"，"; }
}
图 5
4、 一棵完全二叉树的第六层有 10 个叶子结点，则整个二叉树的结点总数为数至多为________。
5、 已知二叉树的二叉链表的类型定义如下：
typedef struct node{
TElemType data；//数据域
Struct node *lchild, *rchild；//指向左、右孩子的指针域
}BiTNode, *BiTree
有如下函数所描述的算法，它试图求出二叉树的结点总数，请写出下划线处应填写的语句（仅限一个语
句）。
int NodeCount( BiTree T )
{
if(T==NULL) return 0; // 如果是空树，则结点个数为 0，递归结束
else ___________________________________________;
//否则结点个数为左子树的结点个数+右子树的结点个数+1（根节点）
}
6、 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素 58，则它将依次与
表中________比较大小，查找结果是失败。
7、 在散列技术中，处理冲突的两种方法是_______法和___________法。
8、 串“ababaabab”的 nextval 为_______。
2
图3
摘要：
展开>>
收起<<
欢迎报考广东财经大学硕士研究生，祝你考试成功！（第1页共6页）广东财经大学硕士研究生入学考试试卷考试年度：2019年 考试科目代码及名称：809-数据结构（自命题）适用专业：085211工程硕士（计算机技术）［友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！］一、单项选择题（10题，每题2分，共20分）1、设n是描述问题规模的非负整数，下面的程序片段的时间复杂度是________。i=2;while(inext->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next->prior=p;...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
