广东财经大学2019年研究生考研真题-809数据结构.doc
欢迎报考广东财经大学硕士研究生,祝你考试成功!(第 1 页 共 5 页)1广东财经大学硕士研究生入学考试试卷考试年度:2019 年 - - - - 考试科目代码及名称:809- -题- 适用专业:085211 -友情提醒:请在考点提供的专用答题纸上答题,答在本卷或草稿纸上无效!一、 单项选择题(10 题,每题 2 分,共 20 分)1、 设 n 是描述问题规模的非负整数,下面的程序片段的时间复杂度是_。i=2;while(inext->prior=p->prior; p->prior->next=p->next;Bp->next=p->next->next; p->next->prior=p;Cp->prior->next=p; p->prior=p->prior->prior;Dp->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 的容量至少应该是_。A2 B3 C4 D 64、 设有一个递归算法如图 1 所示则计算 fact(n)需要调用该函数的次数为_。 A n+1 B n-1 C n D n+2int fact(int n) /n 大于等于 0if(n>x;if(x=0)sum=0;else test(sum);sum+=x;couttypedef struct ElemType *elem; / 存储空间基址int length; / 当前表长 SqList;设顺序表 L 中的数据元素非递减有序,试编写函数实现将 e 插入 L 的适当位置,以保持线性表的有序性。函数原型为:bool InsertOrderList(SqList /数据域struct LNode *next;/指针域LNode, *LinkList;有一个带头结点的单链表 L,其结点的元素值按非递减的顺序排列,试编写函数,其功能是:审查单链表 L,凡元素值相同的结点只保留其中一个,使得单链表 L 按元素值递增有序。函数原型为:void Delete(LinkList /该边所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条边的指针 OtherInfo info; /和边相关的信息 ArcNode; typedef struct VNode VerTexType data; /顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的边的指针 VNode, AdjListMVNum; /AdjList 表示邻接表类型 typedef struct AdjList vertices; /邻接表 int vexnum, arcnum; /图的当前顶点数和边数 ALGraph;试基于图的深度优先搜索策略写一个算法,判别以邻接表方式存储的有向图中是否存在由顶点 vi 到顶点 vj 的路径(ij),是则返回 1,否则返回 0。算法函数原型为:int exist_path_DFS(ALGraph G,int i,int j)请用类 C 语言写出函数代码,并且加上适当注释,以增加可读性。4、 已知记录的类型定义如下:typedef structint key ; /关键字域Infotype otherinfo; /其它域 RecordType;记录依顺序存储结构存放,其类型定义如下:#define MAXSIZE 100 /最大记录数 typedef struct RecordType rMAXSIZE +1; /0 号单元不存记录int length; SqList;编写算法,对依上述方式存储的关键字为整型值的记录序列进行整理,以使所有关键字为负值的记录排在关键字为非负值的记录之前,要求:至多使用一个记录的辅助存储空间;算法的时间复杂度为 O(n),n 是表中记录的个数; 算法函数原型为:void Process(SqList L)请:(1)简述算法思路;(2)用类 C 语言写出函数代码,并且加上适当注释,以增加可读性。