资源描述
第 1 页 ，共 5 页 浙 江 理 工 大 学 2018 年硕士研究生招生考试初试试题 考试科目：数据结构 代码： 991 （请考生在答题纸上答题，在此试题纸上答题无效） 一、单选题： (每小题 2 分，共 30 分 ) 1. 带头结点的单链表 simpleList 为空的判定条件是 。 A. simpleList = null B. simpleList-next = null C. simpleList-next = simpleList D. simpleList! = null 2. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_存储方式最节省运算时间。 A. 单链表 B. 仅有头结点的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表 3. 向一个栈顶指针为 top 的链栈中删除一个结点时， 用 X 保存被删结点的值，则执行_。 A.X = top; top = top-next; B. X = top-data; C. top = top-next; X = top-data; D. X = top-data; top = top-next; 4. 一维数组和线性表的区别是 _。 A. 前者长度固定，后者长度可变 B. 后者长度固定，前者长度可 变 C. 两者长度均固定 D. 两者长度均可变 5. 稀疏矩阵一般的压缩存储方法有两种，即 _。 A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表 6. 不带头结点的单链表 simpleList 为空的判定条件是 。 A. simpleList = null B. simpleList-next = null C. simpleList-next = simpleList D. simpleList! = null 7. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_存储方式最节省运算时间。 A. 单链表 B. 仅有头结点的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表 8. 向一个栈顶指针为 top 的链栈中插入一个 S 所指结点时，则执行 _。 A. top-next = S; B. S-next = top-next; top-next = S; C. S-next = top; top = S; D. S-next = top; top = top-next; 9. 采用邻接表 存储的图的深度优先遍历算法类似于二叉树的 _。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 10. 设矩阵 A 是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组 B1, n(n-1)/2中，对任一下三角部分中任一元素 aij(ij ),在一组数组 B 的 下标位置 K 的值是 _。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 11. 如右图所示的一棵二叉排序树其不成功的平均查找长度为_。 A. 21/7 B. 28/7 C. 15/6 D. 21/6 6230 7415 5648第 2 页 ，共 5 页 12. 对序列 15， 9， 7， 8， 20， -1， 4进行排序，进 行一趟排序后，数据的排列变为 4， 9， -1，8， 20， 7， 15；则采用的是哪一种排序。（ ） A 快速排序 B 冒泡排序 C 希尔排序 D 选择排序 13. 若需在 2(log )On的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。 A 快速排序 B 堆排序 C 归并排序 D 直接插入排序 14. 将序列 8， 9， 10， 4， 5， 6， 20采用冒泡排序排成升序序列，需 要进行（ ）趟（假设采用从前向后的扫描方式）。 A 3 B 4 C 5 D 6 15. 将二个分别含有 n 个元素的有序表归并成一个有序表，最少的比较次数是（ ）。 A 2n-1 B n C 2n D n-1 二、 填空题： (每空 2 分，共 20 分 ) 1. 在循环双链表的 P 所指结点之前插入 S 所指结点的操作如下： S-next = P; S-prior = ; P-prior-next = ; P-prior = S; 2. 分析以下程序段的时间复杂度为 _。 I=s = 0; While (snext; P-data = P-next-data; P-next = _; Free(Q); 5. 带头结 点的双循环链表 L 中只有一个元素结点的条件是 。 6. 区分循环队列的满与空，有两种方法，它们是 和 。 7. 具有 n 个顶点的无向连通图 G 中至少有 条边。 8. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用 比较好。 第 3 页 ，共 5 页 三、简答题： (每小题 10 分，共 20 分 ) 1. 设对角线矩阵 A= （行列下标 i, j 满足： 1i， j5）(1)若将矩阵 A 压缩存储到数组 S 中： 1 2 1 0 1 2 1 0 0 0 1 3 5 下标： 1 2 3 4 5 6 7 8 9 10 11 12 13 试求出 A 中已存储之元素的行列下标（ i, j）与 S 中元素的下标 K 之间的关系。 (2)若将 A 视为稀疏 矩 阵时，请画出其行逻辑链接顺序表。 2. 设二叉树 BTree 的存储结构如下： 1 2 3 4 5 6 7 8 9 10 left 0 0 2 3 7 5 8 0 10 1 data j h f d b a c e g i right 0 0 0 9 4 0 0 0 0 0 其中， BTree 为树根结点指针， left、 right 分别为结点的左、右孩子指针域，在这里使用结点编号作为指针域值， 0 表示指针域值为空； data 为结点的数据域。请完成如下问题： (1) 画出二叉树 BTree 的逻辑结构； (2) 写出按先序、中序和后序遍历二叉树 BTree 所得到的结点序列； (3) 画出二叉树 BTree 的后线索化树。 四、解答题： (共 80 分 ) 1. 已知一棵二叉 树的先序遍历序列为： ABDFGCE，中序遍历序列为： BFDGACE。 （ 1） 请画出这棵二叉树；（ 5分） （ 2） 若采用顺序存储结构存储该二叉树，其中 0号存储单元存储根节点，用 #表示二叉树中不存在的节点，填写以下数组来表示这棵二叉树。（ 5分） 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 （ 3） 若采用链式存储，节点的结构如下图（标志位为 0 时表示指针指向孩子节点，为 1 时表示指向前驱或后继），画出和这棵二叉树相对应的中序线序二叉树；（ 5分） lchild LTag data RTag rchild （ 4） 说说中序线索二叉树的优点。（ 5分） 1 2 0 0 0 1 0 1 0 0 0 2 1 0 0 0 0 0 0 1 0 0 0 3 5 第 4 页 ，共 5 页 2. 已知以二维数组表示的带权图 （权值非负，表示边连接的两顶点间的距离） 的邻接矩阵如下图所示。 A B C D E F G H A 4 3 B 4 8 1 9 C 3 8 6 5 D 1 6 7 6 2 10 E 9 7 3 F 6 3 2 G 2 2 6 H 5 10 6 （ 1） 画出和该邻接矩阵对应的图；（ 5分） （ 2） 分别画出自顶点 A出发遍历所得的深度优先树和广度优先树；（ 8分） （ 3） 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法： 设最短路径初始时仅包含初始顶点，令当前顶点 u为初始顶点； 选择离 u 最近且尚未在最短路径中的一个顶点 v，加入到最短路径中，修改当前顶点u=v； 重复步骤，直到 u是目标顶点时为止。 请问上述方法能否求得最短路径？若该方法可行，请 证明之；否则，请举例说明。（ 7分） 3. 设有两个集合 A和集合 B，回答如下问题： (1) 给出你所用的数据结构，若 A=1,2,3，给出存储 A这个集合的示意图（ 5 分）； (2) 按如下的函数声明，应用你的数据结构，给出 A B 程序（以下的函数声明中假定你的数据结构的类型名称为 T，注意实际的程序可能需要修改该类型名称）（ 5分）。 T * intersection(T *ha, T *hb); 4. 硬盘 Cache 是用于缓解内存和外存之间速度差的一种机制， Cache 硬件通常位于硬盘上，由一个专门的处理器来管 理。处理器要读取的数据，如果保存在 Cache中，则称为 Cache命中，否则就称为 Cache未命中，现在提供给你如下信息： 有一个硬盘， Cache 大小为 16M Bytes，以 4K Bytes 为一簇，硬盘上的数据也以 4K Bytes为一个簇，硬盘和 Cache中的数据每次读写都以 1个簇为单位，写 Cache的函数是 write(int addr, unsigned char *buf); 表示将 buf内的数据写到地址为 addr的 Cache 内，所以 addr一定是 4096 的倍数； 处理器读硬盘数据的指令表示为函数为 void read(unsigned int cid, unsigned char * buf); 其功能为读簇号为 cid的簇，读取的数据存放在 buf 中；在这个函数中，需要考虑 Cache命中； Cache中的数据有一定的淘汰机制，目前最多使用的是最久未访问淘汰机制，即 Cache中的一个簇，如果未被使用的时间最长，在一次 Cache未命中时，将其淘汰出 Cache，而用未命中的数据来代替；所以 read函数中，需要考虑 Cache未命中。 现在，本题需要你实现这个 read函数，你需要回答如下问题： 第 5 页 ，共 5 页 (1) 给出数据结构，能够用 于管理 Cache； (5分 ) (2) 结合 (1)，请你实现 read函数，注意：如果未命中，真正从硬盘中读取数据，请直接使用函数 readhd，声明如下： void readhd(unsigned int cid, unsigned char * buf); 该函数不需要你实现。（ 25 分） 提示： 你可以先写出你的程序思路，然后根据这个思路来写你的程序： 例如：如果读 cache命中，那么 ，否则 ；如果 cache满，那么 ，否则 readhd和 write的使用方式示例代码如下； void read(unsigned int cid, unsigned char * buf) readhd(cid,buf); / 读硬盘数据 write(addr,buf); / 写入 cache指定地址
展开阅读全文