重庆邮电大学 2019 年 攻读 硕士学位研究生入学考试试题 注：所有答案 必须写 在答题纸上 ， 试卷上作答无效 ！ 第 1 页 （ 共 8 页 ） 机密启用前 重 庆 邮 电 大 学 2019 年 攻读 硕士学位研究生入学考试试题 科目名称 ： 数据结构（ A） 科目代码 ： 802 考生注意事项 1、答题前，考生必须在答题纸 指 定位置上填写考生姓名、报考 单位和考生编号 。 2、 所有答案必须写在答题纸上，写在其他地方无效。 3、填（书）写必须使用 0.5mm 黑色签字笔 。 4、考试结束，将答题纸和试题一并 装入 试卷袋中交回。 5、本试题满分 150 分，考试时间 3 小时。 重庆邮电大学 2019 年 攻读 硕士学位研究生入学考试试题 注：所有答案 必须写 在答题纸上 ， 试卷上作答无效 ！ 第 2 页 （ 共 8 页 ） 一、 选择题（本 大题共 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. 5 3设有数组 Ai,j，数组的每个元素长度为 3 字节， i 的值为 1 到 8 ， j 的值 为 1 到 10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A5， 8的存储首地址为 ( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 4一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是 ( )。 A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5下述编码中哪一个不是前缀码（ ）。 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=n) B. A2i+1(2i+1= n) C. Ai/2 D. 无法确定 7假设一个有 n 个顶点和 e 条弧的有向图用邻接表表示 ,则删除与某个顶点 vi 相关的所有弧的时间复杂度是 ( )。 A. O(n) B. O(e) C. O(n+e) D. O(n*e) 重庆邮电大学 2019 年 攻读 硕士学位研究生入学考试试题 注：所有答案 必须写 在答题纸上 ， 试卷上作答无效 ！ 第 3 页 （ 共 8 页 ） 8串的长度是指（ ） 。 A.串中所含不同字母的个数 B串中所含字符的个数 C.串中所含不同字符的个数 D串中所含非空格字符的个数 9循环队列存储在数组 A0.m中，则入队时的操作为（ ）。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 10关键路径是事件结点网络中（ ）。 A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长回路 D. 最短回路 二、填空题（本大题共 15 小题 ， 每 空 2 分，共 40 分 ） 1中缀算式（ 3+4X） -2Y/3 对应的后缀算式为 _。 2在完全二叉树中，编号为 i 和 j 的两个结点处于同一层的条件是 _。 3构造 n 个结点的强连通图，至少有 _条弧 。 4设有一个空栈，栈顶指针为 1000H(十六进制 )，现有输入序列为 a， b， c， d， e经过 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，输出序列是 _， 而栈顶指针值是 _H。设栈为顺序栈，每个元素占 4 个字节。 5若串 S1= ABCDEFG , S2= 9898 ,S3= # ,S4= 012345 ,执行 concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),lengt h(S2)，其结果为 _。 6若一组记录的排序码为（ 46， 79， 56， 38， 40， 84），则利用堆排序的方法 建立的初始堆为 _。 7在有序表（ 12， 24， 36， 48， 60， 72， 84）中二分查找关键字 72 时所需进 行的关键字比较次数为 _。 8有向图的边集为 , , , , d, c), ，该图的一 重庆邮电大学 2019 年 攻读 硕士学位研究生入学考试试题 注：所有答案 必须写 在答题纸上 ， 试卷上作答无效 ！ 第 4 页 （ 共 8 页 ） 个拓扑排序为： _。 9当输入序列局部有 序或元素个数较小时，在快速排序、选择排序、插入排序、 归并排序、堆排序中，最佳的排序方法是 _ 。 10假设两个队列共享一个循环向量空间（参见右图），其类型 Queue2 定义如 下： typedef struct DateType 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 个记录的有序顺序表中进行折半查找，最大比较次数是 _。 重庆邮电大学 2019 年 攻读 硕士学位研究生入学考试试题 注：所有答案 必须写 在答题纸上 ， 试卷上作答无效 ！ 第 5 页 （ 共 8 页 ） 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) 重庆邮电大学 2019 年 攻读 硕士学位研究生入学考试试题 注：所有答案 必须写 在答题纸上 ， 试卷上作答无效 ！ 第 6 页 （ 共 8 页 ） 对于如下所示的二叉树 （ 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)请画出该二叉树 重庆邮电大学 2019 年 攻读 硕士学位研究生入学考试试题 注：所有答案 必须写 在答题纸上 ， 试卷上作答无效 ！ 第 7 页 （ 共 8 页 ） (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 的相互关系仍保持正确。 重庆邮电大学 2019 年 攻读 硕士学位研究生入学考试试题 注：所有答案 必须写 在答题纸上 ， 试卷上作答无效 ！ 第 8 页 （ 共 8 页 ） 2. 快速排序算法中，如何选取一个界值（又称为轴元素），影响着快速排 序的效 率，而且界值也并不一定是被排序序列中的一个元素。例如，我们可以用被排 序序列中所有元素的平均值作为界值。 用 C 语言编写算法实现以平均值为界值 的快速排序方法（注： 待排序数据存储在数组 R 中 , 数组最小下标 为 S，数组 最大下标为 T）。