欢迎报考广东财经大学硕士研究生，祝你考试成功！（第1页共7页）广东财经大学硕士研究生入学考试试卷
考试年度：2019年
考试科目代码及名称：809-数据结构（自命题）
适用专业：085211工程硕士（计算机技术）
［友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！］一、单项选择题（10题，每题2分，共20分）1、设n是描述问题规模的非负整数，下面的程序片段的时间复杂度是________。i=2;while(i<=n)i=i*2;2
A．O(n)B．O(n)C．O(nlog2n)D．O(log2n)）。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．2B．3C．4D．64、设有一个递归算法如图1所示则计算fact(n)需要调用该函数的次数为________。A．n+1B．n-1intfact(intn){//n大于等于0if(n<=0)return1;elsereturnn*fact(n-1);}图1图2C．nD．n+25、对图2所示的带权有向图，若采用迪杰斯特拉(Dijkstra)算法求从原点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是________。A．f，d，eA．012345678999B．e，d，fB．012121111212C．d，e，fC．0123012322345D．f，e，dD．0112342234566、串“ababaaababaa”的next数组为________。7、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用________遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历8、下面关于B-和B+树的叙述中，不正确的是________。A．B-树和B+树都是平衡的多叉树B．B-树和B+树都可用于文件的索引结构C．B-树和B+树都能有效地支持顺序检索D．B-树和B+树都能有效地支持随机检索1欢迎报考广东财经大学硕士研究生，祝你考试成功！（第2页共7页）9、对一组数据(2，12,16,88,5,10)进行排序，若前三趟排序结果如下：第一趟排序结果：2,12,16,5,10,88第三趟排序结果：2,5,10,12,16,88则采用的排序方法可能________。A．希尔排序B.起泡排序A．v0、v1、v2、v4、v5、v3、v6B．v1、v0、v3、v4、v5、v2、v6C．v1、v0、v3、v4、v5、v6、v2D．v1、v0、v3、v4、v6、v2、v5图3二、填空题（10题，每题3分，共30分）1、算法的时间复杂度为O(1)，意味着算法的执行时间_____________________。2、图4所示算法，将一维数组a中的n个数逆序存放到原数组中，其空间复杂度是_____（要求用大O符号表示）。3、在调用图5所示递归过程时，如果从键盘输入的数据依次是：3，2，1，0。则屏幕上相应的显示数据依次是________。for(i=0;i
广东财经大学809数据结构2019-2020年考研真题
