北京科技大学2002年招收攻读硕士学位研究生入学考试试题
考试科目：数据结构
适用专业：计算机应用技术 计算机软件与理论 系统工程 计算机系统结构
说明：统考生做一~七题，单考生做一、二、三、五、六、八、九题。全部试题答案请务必写在答卷纸上。
一、（20分）回答下列各题：
1.数据的逻辑结构在计算机存储器中的映象（或表示）通常有哪几种方法？
2.请简述算法的确定性之含义。
3.线性结构和树型结构的特点分别是什么？
4.设单链表中结点的数据域为 data，指针域为 next，指针 p 为表中某一结点的地址，请写出在 p 结点之前插入一 s 结点的C语言描述语句。
5.请简述在你所进行的算法设计中运用到栈和队列的两个例子。
6.设一棵三叉树中叶结点数为 n0，度为2、3的结点数分别为 n2、n3，试给出 n0 与 n2、n3 之间的关系。
7.构造无向连通网的最小生成树通常有哪两个典型的算法？
8.在含有 n(n>=0) 个关键字的 m 阶 B-树 上查找时，查找路径上最多涉及多少个结点？
9.请指出三个稳定的和三个不稳定的内排序方法。
10.检索一个ISAM文件是按哪三级索引顺序进行的？一个VSAM文件由哪三部分组成？
二、（10分）算法填空：
求 Huffman 树的带权路径长度（WPL）的算法如下，其中 ht 为树根结点的指针，S 为工作栈，Clearstack(S)、Push(S,p)、Pos(S) 和 Emptystack(S) 分别为置栈空、指针 p 进栈、出栈和判栈空的函数。请填写算法中下画线的空白之处，完成其功能。
三、（10分）
设某单位职工工资表 ST 由 "工资"、"扣除" 和 "实发金额" 三项组成，其中工资项包括 "基本工资"、"津贴" 和 "奖金"，扣除项包括 "水"、"电" 和 "煤气" 费用等。
1.请用广义表形式所描述的工资表 ST，并用 GetHead(ST) 和 GetTail(ST) 函数提取表中的奖金项；
2.用C语言描述广义表中的元素结构，并画出该工资表 ST 的存储结构。
四、（10分 此题统考生做）
设一棵二叉树 BT 如下：
1.请画出此二叉树 BT 的 "顺序" 及 "二叉链表" 式存储结构；
2.写出按 "先序"、"中序" 和 "后序" 方法遍历二叉树 BT 所得到的结果序列，并画出 BT 的一棵后序线索二叉树。
五、（15分）
设一个无向网 G 的邻接矩阵 A 如下：
1.请根据给定的邻接矩阵 A 画出网 G 的逻辑结构（G 中顶点用 v1~v8 表示）；
2.写出从顶点 v1 出发、按 "深度优先" 和 "广度优先" 搜索方法遍历网 G 所得到的顶点序列；
3.从顶点 v1 出发，按照求最小生成树的 Prim 算法，画出网 G 的一棵最小生成树。
六、（15分）
设记录的关键字（key）集合 K={26, 36, 41, 44, 15, 68, 12, 6, 51, 25}
1.以 K 为权值集合，构造一棵 Huffman 树；依次取 K 中各值，构造一棵二叉排序树；
2.设 Hash 表表长 m=16，选取 Hash 函数的方法为 H(key)=key%13，处理冲突的方法为 "二次探测再散列"，请依次取 K 中各值，构造出满足所给条件的 Hash 表结构；
3.设以 K 中第一个关键字（26）为枢轴，写出对 K 按 "快速排序" 方法排序时，第一趟排序结束时的结果，并将 K 调整成一个堆顶元素取最大值的堆。
七、（20分 此题统考生做）
算法设计：
1.设 L 为单向循环链表（不带头结点）第一结点的指针，结点编号分别为 1,2,...,n，从链表中编号为 k(1<=k<=n) 的结点开始计数，计到 m(1<=m<=n) 时的结点出列（删除），再从出列的下一结点从 1 开始计数，计到 m 时的结点又出列，...，依此类推，直到表中所有的结点都出列为止。请用C语言函数形式写出完成此任务的算法：Josephu(L, n, k, m)；
2.设有 n 个顶点的向图 G 已用邻接表结构存储，顶点表指针为 g ，且图中各顶点的入度已记录在顶点的 id 域中（即 g->data[ i ].id=第i(1<=i<=n)个顶点的入度）。请用C语言函数形式写出判断图G是否存在回路的算法：Top_cycle(g, n) （注：此算法中可调用栈操作的基本算法）。
八、（10分 此题单考生做）
设森林 F={T1, T2, T3} 如下：
1.若按 "孩子兄弟表示法" 存储此森林 F，请画出其存储结构；
2.写出按 "先序" 和 "中序" 方法遍历森林 F 所得到的结果序列。
九、（20分 此题单考生做）
算法设计：
1.设两个带头结点单链表的头指针分别为 A 和 B ，链表中结点的数据域为 data（设为整形），指针域为 next。请用C语言函数形式写出将表 A 和表 B 合并为一个单链表 L 的算法：Union(A, B, L)（注：若表A和表B中有数据值相同的结点，只保留其中一个）；
2.设记录的关键字集合 K={k1, k2,......,kn} 已存入整形数组 A[n] 中，请用C语言函数形式写出将数组 A[n] 调整成一个小根堆的算法：Creatheap(A[n])（注：若 K 中各值满足 ki<=k2i, ki<=k2i+1, i=1,2,......,n/2 时，将 K 视为一个小根堆）。
一、（20分）回答下列各题：
1.数据的逻辑结构在计算机存储器中的映象（或表示）通常有哪几种方法？
2.请简述算法的确定性之含义。
3.线性结构和树型结构的特点分别是什么？
4.设单链表中结点的数据域为 data，指针域为 next，指针 p 为表中某一结点的地址，请写出在 p 结点之前插入一 s 结点的C语言描述语句。
5.请简述在你所进行的算法设计中运用到栈和队列的两个例子。
6.设一棵三叉树中叶结点数为 n0，度为2、3的结点数分别为 n2、n3，试给出 n0 与 n2、n3 之间的关系。
7.构造无向连通网的最小生成树通常有哪两个典型的算法？
8.在含有 n(n>=0) 个关键字的 m 阶 B-树 上查找时，查找路径上最多涉及多少个结点？
9.请指出三个稳定的和三个不稳定的内排序方法。
10.检索一个ISAM文件是按哪三级索引顺序进行的？一个VSAM文件由哪三部分组成？
二、（10分）算法填空：
求 Huffman 树的带权路径长度（WPL）的算法如下，其中 ht 为树根结点的指针，S 为工作栈，Clearstack(S)、Push(S,p)、Pos(S) 和 Emptystack(S) 分别为置栈空、指针 p 进栈、出栈和判栈空的函数。请填写算法中下画线的空白之处，完成其功能。
三、（10分）
设某单位职工工资表 ST 由 "工资"、"扣除" 和 "实发金额" 三项组成，其中工资项包括 "基本工资"、"津贴" 和 "奖金"，扣除项包括 "水"、"电" 和 "煤气" 费用等。
1.请用广义表形式所描述的工资表 ST，并用 GetHead(ST) 和 GetTail(ST) 函数提取表中的奖金项；
2.用C语言描述广义表中的元素结构，并画出该工资表 ST 的存储结构。
温馨提示：答案为网友推荐，仅供参考