重庆邮电大学2020数据结构802真题.pdf-资料库

重庆邮电大学 2020 年攻读硕士学位研究生入学考试试题机密启用前重庆邮电大学 2020 年攻读硕士学位研究生入学考试试题科目名称：数据结构（A）科目代码： 802 考生注意事项 1、答题前，考生必须在答题纸指定位置上填写考生姓名、报考单位和考生编号。 2、所有答案必须写在答题纸上，写在其他地方无效 3、填（书）写必须使用黑色字迹钢笔、圆珠笔或签字笔。 4、考试结束，将答题纸和试题一并装入试卷袋中交回。 5、本试题满分 150 分，考试时间 3 小时。注：所有答案必须写在答题纸上，试卷上作答无效！第 1 页/共 9 页

重庆邮电大学 2020 年攻读硕士学位研究生入学考试试题一、选择题（本大题共 15 小题，每小题 2 分，共 30 分） 1. 设三个函数 f, g, h 分别为 f(n) = 1000n3+n2+1000, g(n) = 1000n3+5000n2, h(n)=n3/2+5000nlgn, 下列哪个关系不成立（）。 A． f(n) = O(g(n)) B. g(n) = O(f(n)) C． h(n) = O(n3/2) D. h(n) = O(nlgn) 2. 已知 P 结点是某双向链表的一个结点，在 P 结点后插入一个新结点 S 的语句序列是（）。 S->prior=P->prior; P->prior=S; S->next=P; P->prior->next=S; A. S->prior=P->prior; P->prior->next=S; P->prior=S; S->next=P; C. S->prior = P; S->next = P->next; P->next->prior = S; P->next = S; B. S->prior=P; S->next=P->next; P->next=S; P->next->prior=S; D. 3. 栈在（）中应用。 A. 递归调用 C. 表达式求值 D. A, B, C B. 子程序调用 4. 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为（）。 A. 1 和 5 B. 2 和 4 C. 4 和 2 5. 设完全二叉树的第 i=6 层有 24 个叶结点，则此树最多有 D. 5 和 1 注：所有答案必须写在答题纸上，试卷上作答无效！第 2 页/共 9 页

重庆邮电大学 2020 年攻读硕士学位研究生入学考试试题（）个结点。( i≥1) A. 55 B. 79 C. 81 6. 下列序列（）不是堆？ D. 127 A. 12, 35, 39, 57, 86, 48, 42, 73, 66, 100 B. 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 C. 06, 12, 20, 30, 52, 23, 42, 38, 103, 97, 66, 56 D. 05, 23, 20, 35, 28, 38, 29, 61, 56, 76, 40, 100 7. 将下图中二叉树按中序线索化，结点 f 的右指针和结点 g 的左指针分别指向结点（）。 A. d, e B. b, d C. d, b D. a, e 8. 在 Huffman 编码中，若编码长度只允许小于等于 5，则除了已对两个字符编码为 0 和 10 外，还可以最多对（）个字符编码。 A. 5 B. 6 C. 7 9. 设 G 是一个非连通无向图，有 28 条边，则该图的顶点数至少有（）个。 D. 8 A. 7 B. 8 C. 9 10. 对于一个有向图，若一个顶点的度为 k1, 出度为 k2,则对应逆邻接表中该顶点的入边表中的边结点数为（）。 D. 10 A. k1 B. k2 C. k1-k2 11. 在下图中所示的 AOE（Activity On Edge）网中，关键路径长度为（）。 D. k1+k2 A. 23 B. 22 C. 16 D. 13 注：所有答案必须写在答题纸上，试卷上作答无效！第 3 页/共 9 页 abgcdef

重庆邮电大学 2020 年攻读硕士学位研究生入学考试试题 12. 如果一个有向图具有拓扑有序序列，并且顶点按拓扑有序序列编号，那么其邻接矩阵必定为（）。 A. 对称矩阵 C.上三角矩阵 B.三对角矩阵 D. 下三角矩阵 13. 已知一个长度为 18 的有序顺序表中，若采用折半查找法查找第 12 个元素，则比较次数是（）。 A. 3 B. 4 C. 5 D. 6 14. 如果将学校所有同学按照生日（不考虑年份，只考虑月、日）来排序，那么下列排序算法中排序速度最快的算法是（）。 A. 归并排序 C. 快速排序 B. 希尔排序 D. 基数排序 15. 下列（）不是 AVL 树（平衡二叉树）。 A B C D 二、选择题（本大题共 15 小题，每小题 2 分，共 30 分） 1. 考虑函数 f (n) = nlogn 和 g(n) = na，其中 a 是实数。在下列空白处填写合适的数学符号（比如>, ≥ , <, ≤ 等），使得下列函数关系成立。f = O(g) : 当 a 1； g = O( f ) : 当 a 1。 2. 表达式 a*b-c-d$e$f-g-h*i 中，运算符的优先级由高到低依次为 -, *, $，且均右结合，则相应的后缀式是。 3. 7 个元素 a、b、c、d、e、f 和 g 顺序入栈。在栈上做了 5 次弹出操作，每个出栈的元素被插入到一个队列中。从队列中删除 3 个元素并将其推回到栈中。现在，从栈中弹出一个元素，弹出的注：所有答案必须写在答题纸上，试卷上作答无效！第 4 页/共 9 页

重庆邮电大学 2020 年攻读硕士学位研究生入学考试试题这个元素是。 4. 设一个稀疏矩阵有 1000 行 850 列，其中有 1000 个非 0 数据元素。设每个整数值占 2B，数据元素值占 4B，则用三元组表存储该矩阵时所需字节数是。 5. 一棵二叉排序树（BST，binary search/sort tree ）的后序遍历序列是 15, 10, 23, 25, 20, 35, 42, 39, 30。请给出这棵树的前序遍历序列：。 6. 如果 T1 是由有序树 T 转换成的二叉树，那么 T 中结点的后根遍历顺序对应 T1 中结点的遍历。 7. 设一棵树中只有度为 0 和度为 3 的结点，则该树的第 i 层（i≥1）的结点个数最多为。 8. 在一个图中，所有顶点的度数之和等于图的边数的 _____________倍。 9. 一个有向图的邻接表存储如下图所示，现按深度优先搜索方式从顶点 F 出发执行一次遍历，则得到的顶点系列是_____________。 10. 设一个 n 个顶点的带权连通图有 n1/2logn 条边，则应该选用 _____________（从 Prim， Kruskal 中选择一个填空）算法求这个图的最小生成树，从而使计算时间较少。 11. 对于长度为 9 的有序顺序表，若采用折半查找，在相等查找概率情况下查找成功的平均查找长度为_____________，查找不成功的平均查找长度为_____________。 12. 将 10 个元素散列到大小可容 100000 个元素的散列表中， _____________产生冲突。（请在“一定会”、“一定不会”、“仍然可能会”这些术语中选择正确的进行填空） 13. 数组 A 中，每个元素 A 的长度为 3 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到 10，从首地址 1000 开始连续存放在存储器内，该数组按行优先存放时，元素 A[8][5]的起始地址为_____________。注：所有答案必须写在答题纸上，试卷上作答无效！第 5 页/共 9 页

重庆邮电大学 2020 年攻读硕士学位研究生入学考试试题 14. 如果有一个时间复杂度为 O(n2)的算法（比如冒泡排序、选择排序或插入排序等），在有 200 个元素的数组上运行需要耗时 3.2 毫秒。那么，在类似的有 40000 个元素的数组上运行，需要 _____________秒时间。 15. 顺序文件中，要存取第 i 个记录，必须先存取个记录。三、综合应用题（本大题共 6 小题，每小题 10 分，共 60 分） 1. 下面这段 C 代码，针对输入的简单算术表达式的后缀表达式，输出其计算结果。例如，输入 5 2 * 3 3 2 + * +，该程序输出 25。请给出缺失的 5 行代码。 #include #define EOF -1 void push (int); /* push the argument on the stack */ int pop (void); /* pop the top of the stack */ void flagError ( ); int main ( ) { int c, m, n, r; while ((c = getchar ( )) != EOF) { if (isdigit (c) ) （1） ; else if ((c == '+') || (c == '*')) { m = （2） ; n = （3） ; r = (c == '+') ? n + m : n*m; （4） ; } else if (c != ' ') flagError ( ); } printf("% c", （5） ); } 2. 一个二叉树 BT 有 10 个结点，BT 为指向树根结点的指针，其值为 6, Lchild, Rchild 分别为结点的左、右孩子指针域, data 为结点的数据域。各结点的存储结构如下表所示: 1 2 Lchild 0 0 Data J H 3 2 F 4 5 6 7 8 9 10 3 7 5 8 0 10 1 D B A C E G I 注：所有答案必须写在答题纸上，试卷上作答无效！第 6 页/共 9 页

重庆邮电大学 2020 年攻读硕士学位研究生入学考试试题 0 0 0 0 0 0 0 4 9 Rchild 0 请完成下列各题: （l）画出二叉树 BT 的逻辑结构; （2）写出按前序、中序、后序遍历该二叉树所得到的结点序列; （3）画出二叉树的后序线索树。 3. 当输入大小为 N 时，您为一个程序收集其相应的运行时间。下表记录了在不同的输入 N 情况下，该程序对应的运行时间。 N（输入大小） Time（运行时间） 125 1000 8000 64000 512000 0.03 sec 1.00 sec 32.00 sec 1024.00 sec 32768.00 sec 请给出以 N 作为输入的函数来估计该程序的运行时间(以秒为单位)。提示：logba=lga/lgb 4. 一个有向图 G 的带权邻接矩阵如下所示： V1 V2 V3 V4 V5 V1 V2 V3 V4 V5 0 ∞ ∞ 19 ∞ 16 0 ∞ ∞ 11 ∞ 13 0 15 ∞ ∞ ∞ 18 0 ∞ 21 ∞ 33 ∞ 0 请采用单源点最短路径算法 Dijkstra 求解图 G 中 V1 点到其他各点的最短路径，要求给出计算过程。 5. 设有关键字序列 12, 15, 23, 56, 35,48, 5, 86, 9, 68，哈希函数为 H（Key）= Key mod 11，哈希表的地址空间为 0~10，开始时哈希表为空，采用链地址法解决冲突，请画出依次插入关键字后的哈希表——同一链表中结点对应关键字从小到大有序。 6. 下表 1 中第 0 行是待排序序列的原始输入(365 401 851 229 963 842 794 176 538); 最后一行为排序后的序列（176 229 365 401 538 注：所有答案必须写在答题纸上，试卷上作答无效！第 7 页/共 9 页

重庆邮电大学 2020 年攻读硕士学位研究生入学考试试题 794 842 851 963）; 其他各行是 5 种排序算法得到的某个中间步骤的内容。表 2 列出了这 5 种排序算法。请按行序直接给出每行序列对应的排序算法的编号。每个数字只使用一次。表 1 行号排序算法序列第 0 行原始输入 365 401 851 229 963 842 794 176 538 第 1 行第 2 行第 3 行第 4 行第 5 行 365 401 851 229 963 842 794 176 538 365 401 229 851 963 794 842 176 538 365 401 794 176 538 963 842 851 229 176 229 365 851 963 842 794 401 538 176 229 851 401 963 842 794 365 538 第 6 行排好序的输出 176 229 365 401 538 794 842 851 963 表 2 算法编号算法名称算法编号算法名称 1 2 3 希尔排序(增量为 5,3,1) 快速排序直接选择排序 4 5 6 归并排序直接插入排序冒泡排序四、算法设计题（本大题共 2 小题，每小题 15 分，共 30 分） 1. 设以带头结点的双向循环链表表示的线性表为 L=(a1, a2, a3, ..., an)。试写一时间复杂度 O(n)的算法，将 L 改造为 L=(a1, a3, ..., an, ..., a4, a2)。要求：（1）描述算法的基本设计思想；（2）根据设计思想，采用 C 语言描述算法，关键之处给出注释。 2. ORDER 公司是一个专门为人们提供排序服务的公司，该公司的宗旨是：“秩序是最美丽的”。他们的工作是通过一系列移动，将某些物品按顺序摆好。他们的服务是通过工作量来计算的，即移动东西的次数。所以，在工作前必须先考察工作量，以便向用户提出收费价格。用户并不知道精确的移动次数，实质上，大多数人是凭感觉来认定这一列物品的混乱程度。根据 ORDER 公司的经验，人们一般是根据“逆序对”的数目多少来称呼这一序列的混乱程度。注：所有答案必须写在答题纸上，试卷上作答无效！第 8 页/共 9 页

资料库

重庆邮电大学2020数据结构802真题.pdf

相关推荐

行业

热门标签

最新资料