1、第 1 页 ，共 5 页 浙浙 江江 理理 工工 大大 学学 2012018 8 年硕士研究生招生考试初试试题年硕士研究生招生考试初试试题 考试科目：数据结构考试科目：数据结构 代码：代码：991991 （请考生在答题纸上答题，在此试题纸上答题无效）（请考生在答题纸上答题，在此试题纸上答题无效） 一、单选题：一、单选题：(每小题每小题 2 分，共分，共 30 分分) 1. 带头结点的单链表 simpleList 为空的判定条件是 。 A. simpleList = null B. simpleList-next = null C. simpleList-next = simpleList D.
2、 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. 前者长
3、度固定，后者长度可变 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. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_存储
4、方式最节省运算时间。 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 是一个对称矩阵，为了节省存储，将其下三角部
5、分按行序存放在一维数组 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 623074155648第 2 页 ，共 5 页 12. 对序列15，9，7，8，20，-1，4进行排序，进行一趟排序后，数据的排列变为4，9，-1，8，20，7
6、，15；则采用的是哪一种排序。 （ ） A快速排序 B冒泡排序 C希尔排序 D选择排序 13. 若需在2(log)On的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ） 。 A快速排序 B堆排序 C归并排序 D直接插入排序 14. 将序列8，9，10，4，5，6，20采用冒泡排序排成升序序列，需要进行（ ）趟（假设采用从前向后的扫描方式） 。 A3 B4 C5 D6 15. 将二个分别含有 n 个元素的有序表归并成一个有序表，最少的比较次数是（ ） 。 A2n-1 Bn C2n Dn-1 二、二、填空题：填空题：(每空每空 2 分，共分，共 20 分分) 1. 在循环双链
7、表的 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 页 ，共
8、 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
9、 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） 请
10、画出这棵二叉树； （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
11、 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） 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存
12、在路径，现有一种解决该问题的方法： 设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点； 选择离 u 最近且尚未在最短路径中的一个顶点 v，加入到最短路径中，修改当前顶点u=v； 重复步骤，直到 u 是目标顶点时为止。 请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。 （7 分） 3. 设有两个集合 A 和集合 B，回答如下问题： (1) 给出你所用的数据结构，若 A=1,2,3，给出存储 A 这个集合的示意图（5 分） ； (2) 按如下的函数声明，应用你的数据结构，给出 AB 程序（以下的函数声明中假定你的数据结构的类型名称为 T，注意实际的程序可能需要修改
13、该类型名称） （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, unsig
14、ned char *buf); 表示将 buf 内的数据写到地址为 addr 的 Cache 内，所以 addr 一定是 4096 的倍数； 处理器读硬盘数据的指令表示为函数为 void read(unsigned int cid, unsigned char * buf); 其功能为读簇号为 cid 的簇，读取的数据存放在 buf 中；在这个函数中，需要考虑 Cache 命中； Cache 中的数据有一定的淘汰机制，目前最多使用的是最久未访问淘汰机制，即 Cache 中的一个簇，如果未被使用的时间最长，在一次 Cache 未命中时，将其淘汰出 Cache，而用未命中的数据来代替；所以 rea
15、d 函数中，需要考虑 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 指定地址
