海南大学2010-2011数据结构B期末试卷

1 海南大学 2010 2011 学年度第 1 学期试卷 科目 科目 数据结构数据结构 试题试题 B B 姓名 学 号 学院 信息技术学院 专业班级 成绩登记表 由阅卷教师用红色笔填写 大题 号 一二三四五总分 得分 阅卷教师 201 年 月 日 一 一 选择题 共选择题 共 30 分 每小题分 每小题 2 分 分 1 在一个长度为 n 的单链表的第 i 0 inext NULL C head next head D head NULL 4 若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除进入表 中的最后一个元素 则采用 b 存储方式最节省运算时间和存储空间 A 单链表 B 仅有头指针的单循环链表 C 双向链表 D 有头尾指针的单循环链表 5 设有一个顺序栈 S 元素 a b c d e f 依次进栈 如果 6 个元素出栈的顺序 是 b d c f e a 则栈的容量至少应该是 b 得分评卷人 2 A 2 B 3 C 5 D 6 6 向一个栈顶指针为 top 的带头结点的非空的链栈中删除结点 则其操作步骤 是 c A top next s B s next top next top next s free s C C s top top top next free s D D s top next top top next free s 7 以下为平衡二叉排序树的查找算法 假设表长为N 则算法的时间复杂度为 d A O 1 B O N C O N N D O log2 N bitree search fsortree t key bitree t keytype key while t NULL if t data key return t if t data key t t lchild else t t rchild return NULL SEARCH FSORTTREE 8 在解决计算机主机与打印机间速度不匹配问题时通常设置一个打印数据缓冲 区 主机将要输出的数据依次写入该缓冲区 而打印机则从该缓冲区中取 出数据打印 该缓冲区应该是一个 d 结构 A 数组 B 线性表 C 堆栈 D 队列 9 一棵有 124 个叶结点的完全二叉树 最多有 a 个结点 A 247 B 248 C 249 D 251 10 一棵非空的二叉树的前序遍历序列和后序遍历序列正好相同 则该二叉树一 定满足 c A 所有的结点均无左孩子 B 所有的结点均无右孩子 C 只有一个孤立的结点 D 是任意一棵二叉树 11 已知字符A B C D的使用频率 权值 分别为22 7 9 27 对其进行 HUFFMAN编码 各字符对应的编码为 c A A 001 B 100 C 110 D 0 3 B A 100 B 101 C 0 D 11 C A 11 B 100 C 111 D 0 D A 100 B 1011 C 11 D 0 12 在具有 N 个顶点和 N 条边的无向图的邻接表存储中 邻接表中结点的总数为 A N B 2N C 3N D 4N 13 由同一关键字集合构造的各棵二叉排序树 A 其形态不一定相同 但平均查找长度相同 B 其形态不一定相同 平均查找长度也不一定相同 C 其形态均相同 但平均查找长度不一定相同 D 其形态均相同 平均查找长度也都相同 D 以上都不是 14 设有 1000 个基本有序序的元素 希望用最快的速度挑选出其中前 10 个最大的 元素 最后选用 a 排序法 A 冒泡排序 B 快速排序 C 直接插入排序 D 归并排序 15 对序列 15 9 7 8 20 1 4 进行排序 进行一趟排序后 数据的排 列变为 4 9 7 8 1 15 20 则采用的是 b 排序 A 选择排序 B 快速排序 C 希尔排序 D 冒泡排序 二 填空题 二 填空题 20 分 每空分 每空 2 分 分 16 栈的逻辑特点是 后进先出 队列的逻辑特点是 先进先出 17 将含 100 个结点的完全二叉树从根开始 每层从左到右依次对结点编号 根结点的编号为 1 则编号为 31 的结点的双亲的编号为 15 其右子 的编号为 63 18 设树 F 由 T1 T2 T3 三棵子树组成 与 F 对应的二叉树为 B 已知 T1 T2 T3 的结点数分别为 x y z 则该二叉树 B 的左子树中有 x 1 个结点 右子树 中有 y z 个结点 x 1 y z 19 设链队列的队头指针为 front 队尾指针为 rear 队列为空的条件是 得分评卷人 4 rear head 队列为满的条件是 rear 1 MAXSIZE head 20 在有向图中 以顶点 v 为终点的边的数目称为 v 的 21 堆是一个键值序列 k1 k2 kn 对 i 1 2 满足 ki k2i且 ki k2i 1 2i 1 n 三 应用题 共三 应用题 共 25 分 分 22 对下图所示的树 分别写出其先序和后序序列 并转换成对应的二叉树 5 分 先序 A B E C F G D H KI J 后序 E B F G C K H I J D A 得分评卷人 5 23 对下面给定的图用克鲁斯卡尔算法 从顶点 2 开始 求最小生成树 要求画 出最小生成树 并按构造过程给出边的序列 5 分 见图 1 克鲁斯卡尔算法 0 2 3 5 1 4 2 5 1 2 普利姆算法 2 0 2 5 5 3 2 1 1 4 图 1 24 设给定的排序码序列为 72 73 71 23 94 16 05 68 请写出快速 排序过程中每趟排序的结果 5 分 68 05 71 23 16 72 94 73 16 05 23 68 71 72 94 73 05 16 23 68 71 72 94 73 05 16 23 68 71 72 73 94 6 25 假定一个待存储的线性表为 22 41 53 46 30 13 1 6722 41 53 46 30 13 1 67 散列地址空间为 HT 8 散列函数为 H k key 8 若采用线性探查法处理冲突 请计算每个元 素的散列地址 5 分 画出最后得到的散列表 2 分 并求出平均查找长度 3 分 共 10 分 平均查找长度平均查找长度 ASL 1 8 3 1 6 3 2 1 1 2 19 8 四 算法测试 分 四 算法测试 分 26 代码如下 6 分 下面是在递增有序表 R n 中的下标在 low 到 high 范围内的区域查找键值 为 K 的元素的二分查找的递归算法 请在划线处填上适当的内容 有序表 R 进行二分查找递归算法 int halfsearch R low high k int low high k 在顺序表 R 上进行二分查找 k 为给定的关键字值 int rectype R int mid if low high return False 检索失败 else mid high low 2 设置查找的中间位置 mid switch k case R mid keyk return halfsearch R low mid 1 k break case R mid key k return mid break SWITCH 得分评卷人 0 1 2 3 4 5 6 7 8 比较次数比较次数 3 1 6 3 2 1 1 2 22 41 5346 30 13167 7 ELSE HALFSEARCH 见书上第 318 页 0 mid 1 hiht k low mid 1 k 27 设 h 是带表头结点的单链表的头指针 请设计一个逆置这个单链表的程序 即原链表为 a1 a2 a3 an 逆置后变为 an an 1 a2 a1 6 分 单链表结点结构为 typedef struct node int data link LNode 2 分 struct node void invert LNode h LNode s p p h link h link 2 分 0 h next NULL while p NULL s p p p link 2分 S next H next h link s 五 编写算法 五 编写算法 1 分 分 28 试编写算法 在一个循环单链表中删除结点 S 且要求函数返回该链表的 一个入口指针 假设表长大于 1 且表中即无头结点 也无头指针 函数原 型为 void delete xyz NODE S 分 解一 void delete xyz NODE S NODE f f s next while f next s 找到S点的前一结点 f f next f next s next free s 得分评卷人 8 解二 解一的问题是删除结点 s 后 没有再指向链表的指针了 NODE delete xyz NODE S NODE f f s next while f next s f f next f next s next free s return f 29 已知某二叉树BINTREE的结点结构如下 根结点的指针为T 试编写一算法 求该二叉树的深度 分 LchildLchild DataData RchildRchild 函数形式 参考 函数形式 参考 void BiTreeDepth BiTree T int level int int depth 0 void BiTreeDepth BiTree T int level int 9 BiTreeDepth T Lchild level 1 depth BiTreeDepth T Rchild level 1 depth if BiTreeDepth 算法 2 算法思路 用递归实现该算法 如果二叉树为空 则返回 0 如果二叉树只 有一个结点 根结点 返回 1 否则返回根结点的左分支的深度与右分支的深 度中较大者加 1 算法实现如下 int GetHeight BINTREE T int lh int rh if T null return 0 else if T LChild null else lh GetHeight T LChild rh GetHeight T RChild return lh rh lh rh lh rh lh rh 1 1 算法 3 非递归算法 按层遍历 用队列实现 参阅 P187 例 6 4 void leveltraverse Bitreenode T int Queue Q 队列 Q 定义的结点结构包含两个域 Q LINK 和 Q level 其中 Q LINK Bitreenode 型 记录入队的结点的指 针 地址 Q level int 型 记录该结点的深度 initqueue Q 初始化队列 p T 10 Enqueue Q p 1 根结点入队 对应 Q LINK p 和 Q level 1 while qu