集 美 大 学 试 卷 纸 2011 — 2012 学年 第 二 学期 考 生 信 息 栏 学院 专业 班级 姓名 学号 构的分类表。 装 订 线 试课程名卷 数据结构 A卷 称 卷 别 适 用 考2、（共4分）给出下列图1的二叉树的静态链表存学院、诚毅学院 软件工程专业 试 闭卷 √ 储、顺序存储和二叉链表存储。 方开卷 □ 1091 1171 1172 专业、式 年级 备注 总分 题号 一 二 三 四 得 分 得分 阅卷人 图1 二叉树 图2 二叉树的二叉链表的静态链表 一、问答题（共22分) 解：二叉树的顺序存储如下： 二叉树的二叉链表存储如下： 1、（共4分）完善下面的数据的逻辑结构和物理结P1 P2
4、（共4分）ISAM (索引顺序存取方法文件)是二叉树的静态链表存储填入图2。 静态索引结构。典型的例子是对磁盘上的数据文件建立盘组、柱面、磁道三级地址的多级索引。ISAM 文件用柱面索引对各个柱面进行索引。一个柱面索3、（共4分）有一段报文： 引项保存该柱面上的最大关键码（最后一个记录）CAST CAST SAT AT A TASA 以及柱面开始地址指针。如果柱面太多，可以建立出现的字符有 C, A, S, T，各字符出现的频度刚柱面索引的分块索引，即主索引。主索引不太大，好是 一般常驻内存。请对图 的索引基本原理做说明。 W＝{ 2, 7, 4, 5 } 请给出①画出构造的Huffman树； ②给出每个字符的Huffman编码。 P3 P4 考 生 信 息 栏 学院 专业 班级 姓名 学号 装 订 线
考 生 信 息 栏 学院 专业 班级 姓名 学号 装 订 线
5、（共6分）完善下面的基数排序过程。 图3 ISAM (索引顺序存取方法文件)静态索引结构 P5 P6