2018年新疆大学信息科学与工程学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 2． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。 【答案】算法如下: //本算法将无符号十进制整数m 转换为十六进制整数 第 2 页，共 34 页 ，则编号 求各顶点的入度 本算法的递归描述如下: //本算法将无符号十进制整数m 转换为十六进制整数 3． 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。 【答案】算法如下: 在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回 确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情 况 返回第一邻接点， 4． 结点类型和存储结构如下: 试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。 【答案】算法如下: 对存储在数组R 中的记录进行排序 初始化 设R[0]作监视哨，Max 是该类型最大元 素 第 3 页，共 34 页 取第一个边结点 和中必有一个等于 i 初始假定第一个元素有序 前驱 第一个元素 査找第i 个元素的序号 将笫i 个元素链入静态链表 5． —个有向图G=(V，E) 的平方图 ，使得表示。 【答案】算法如下: 且 满足下述性质 : 当且仅当存在某个顶点 22 。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表 二、应用题 6． 一个ISAM 文件除了主索引外，还包括哪两级索引？ 【答案】ISAM 文件有三级索引:磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引——主索引。故还包括的两级索引是盘组和磁道。 7． 证明:置换选择排序法产生的初始归并段的长度至少为m(m是所用缓冲区的长度) 。 【答案】由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时(即初始归并段) ，缓冲区中m 个元素中除最小元素之外，其他m －1个元素均大于第一个选出的元素，即当以后读入元素均小于输出元素时，初始归并段中也至少能有原有的m 个元素。 第 4 页，共 34 页