重庆邮电大学 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( Q>reari = Q>front_ ) return 0；Q>data_ = x；Q>reari = _ ;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(T>lchild)；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( x<r(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 页）