2019年重庆邮电大学考研802数据结构真题.docx
重庆邮电大学 2019 年攻读硕士学位研究生入学考试试题机密启用前重 庆 邮 电 大 学2019 年攻读硕士学位研究生入学考试试题科目名称: 数据结构(A)科目代码: 802考生注意事项1、答题前,考生必须在答题纸指定位置上填写考生姓名、报考单位和考生编号。2、所有答案必须写在答题纸上,写在其他地方无效。3、填(书)写必须使用 0.5mm 黑色签字笔。4、考试结束,将答题纸和试题一并装入试卷袋中交回。5、本试题满分 150 分,考试时间 3 小时。注:所有答案必须写在答题纸上,试卷上作答无效 ! 第 1 页 (共 8 页)重庆邮电大学 2019 年攻读硕士学位研究生入学考试试题一、 选择题(本大题共 10 小题,每小题 2 分,共 20 分)1对于双向循环链表,每个结点有两个指针域 next 和 prior,分别指向前驱和后继。在 p 指针所指向的结点之后插入 s 指针所指结点的操作应为( )。A. p-next = s; s-prior = p; p-next-prior = s; s-next = p-next;B. p-next = s; p-next-prior = s; s-prior = p; s-next = p-next;C. s-prior = p; s-next = p-next; p-next = s; p-next-prior = s;D. s-prior = p; s-next = p-next; p-next-prior = s; p-next = s;2由 abc,3 个结点可以构造出多少种不同的二叉树?( )A. 2 B. 3 C. 4 D. 53设有数组 Ai,j ,数组的每个元素长度为 3 字节,i 的值为 1 到 8 ,j 的值为1 到 10,数组从内存首地址 BA 开始顺序存放,当用以列为主存放时,元素 A5 ,8的存储首地址为( )。A. BA+141 B. BA+180 C. BA+222 D. BA+2254一个栈的输入序列为 1 2 3,则下列序列中不可能是栈的输出序列的是( )。A. 2 3 1 B. 3 2 1C. 3 1 2 D. 1 2 35下述编码中哪一个不是前缀码( )。A.(00,01,10,11) B.(0, 1,00,11)C.(0, 10,110,111) D.(1,01,000,001)6当一棵有 n 个结点的二叉树按层次从上到下,同层次从左到右将数据存放在一维数组 Al.n 中时,数组中第 i 个结点的左孩子为( )。A. A2i(2i=, , , , ,该图的一注:所有答案必须写在答题纸上,试卷上作答无效 ! 第 3 页 (共 8 页)重庆邮电大学 2019 年攻读硕士学位研究生入学考试试题个拓扑排序为:_。9当输入序列局部有序或元素个数较小时,在快速排序、选择排序、插入排序、归并排序、堆排序中,最佳的排序方法是_ 。10假设两个队列共享一个循环向量空间(参见右图),其类型 Queue2 定义如下:typedef structDateType dataMaxSize; int front2,rear2;Queue2;对于 i=0 或 1 ,fronti和 reari分别为第 i 个队列的头指针和尾指针。请对以下算法填空,实现第 i 个队列的入队操作。int EnQueue (Queue2 *Q, int i, DateType x)/若第 i 个队列不满,则元素 x 入队列,并返回 1;否则返回 0 if( i1 ) return 0;if( Qreari = Qfront_ ) return 0;Qdata_ = x;Qreari = _ ;return1;11高度为 8 的平衡二叉树的结点数至少有_个。12. 文件由_组成;记录由_组成。13对于一个具有 n 个结点的单链表,在已知的结点*p 后插入一个新结点的时间复杂度为_,在给定值为 x 的结点后插入一个新结点的时间复杂度为_。14. 在 n 个记录的有序顺序表中进行折半查找,最大比较次数是_。注:所有答案必须写在答题纸上,试卷上作答无效 ! 第 4 页 (共 8 页)重庆邮电大学 2019 年攻读硕士学位研究生入学考试试题15. 求从某源点到其余各顶点的 Dijkstra 算法在图的顶点数为 10,用邻接矩阵表示图时计算时间约为 10ms,则在图的顶点数为 40,计算时间约为 _ms。三、问答题(本大题共 6 小题,每小题 10 分,共 60 分)1一个线性表为 B=(12,23,45,57,20,03,78,31,15,36),设散列表为 HT0.12,散列函数为 H(key )= key % 13 并用线性探查法解决冲突,请画出散列表,并计算等概率情况下查找成功的平均查找长度。2已知二叉树的存储结构为二叉链表,阅读下面算法。typedef struct node DateType data; Struct node * next;ListNode;typedef ListNode * LinkList; LinkList Leafhead = NULL; Void Inorder (BinTree T) LinkList s;If(T)Inorder(Tlchild);If (!T lchild)注:所有答案必须写在答题纸上,试卷上作答无效 ! 第 5 页 (共 8 页)重庆邮电大学 2019 年攻读硕士学位研究生入学考试试题对于如下所示的二叉树(1)画出执行上述算法后所建立的结构(2)说明该算法的功能3. 假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列,称可以操作的序列为合法序列,否则称为非法序列。(1)下面所示的序列中哪些是合法的?A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO(2)通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。(假定被判定的操作序列已存入一维数组 char A 中, 若操作序列合法,返回 true,否则返回 false)。4. 已知一个连通图如下图所示,试给出图的邻接矩阵和邻接表存储示意图,若从顶点 v1 出发对该图进行遍历,分别给出一个按深度优先遍历和广度优先遍历的顶点序列.(1) 图的邻接矩阵(2) 邻接表存储示意图(3) 从 v1 开始的深度优先遍历的顶点序列(4) 分析在深度遍历过程中,分别使用邻接矩阵和邻接表存储的算法复杂度(5) 讨论在图遍历问题中,这两种存储方式的优劣5一棵二叉树的先序序列为 ABCDGEF,中序序列为 CBDGAFE 。(1)请画出该二叉树注:所有答案必须写在答题纸上,试卷上作答无效 ! 第 6 页 (共 8 页)重庆邮电大学 2019 年攻读硕士学位研究生入学考试试题(2)将二叉树转换为相应的森林6. 请阅读下列算法,回答问题sort(r, n)for (i=2; i=n; i+)x=r(i); r(0)=x; j=i-1; while( xr(j) )r(j+1)=r(j);j=j-1;r(j+1)=x;(1)这是什么类型的排序算法,该排序算法稳定吗?(2)设置 r(0)的作用是什么?(3)若将 while 语句中判断条件改为 x=r(j), 该算法将会有什么变化?(4)若将 while 语句中判断条件改为 x=r(j), 该算法是否还能正确工作?四、程序设计题(本大题共 2 小题,每小题 15 分,共 30 分)1. 设有大小不等的 n 个数据组, 其数据总量为 m,顺序存放在空间区 D 内,每个数据占一个存储单元,数据组的首地址由数组 S 给出,(如下图所示),试编写将新数据 x 插入到第 i 个数据组的末尾且属于第 i 个数据组的算法,插入后,空间区 D 和数组 S 的相互关系仍保持正确。注:所有答案必须写在答题纸上,试卷上作答无效 ! 第 7 页 (共 8 页)重庆邮电大学 2019 年攻读硕士学位研究生入学考试试题2. 快速排序算法中,如何选取一个界值(又称为轴元素),影响着快速排序的效率,而且界值也并不一定是被排序序列中的一个元素。例如,我们可以用被排序序列中所有元素的平均值作为界值。 用 C 语言编写算法实现以平均值为界值的快速排序方法(注:待排序数据存储在数组 R 中, 数组最小下标为 S,数组最大下标为 T)。注:所有答案必须写在答题纸上,试卷上作答无效 ! 第 8 页 (共 8 页)