综合练习一及答案

第 1 页 共 7 页 综合练习题一综合练习题一 一 判断题 正确打一 判断题 正确打 错误打 错误打 并改正 并改正 1 哈希文件是一种直接存取文件 2 线性结构的数据可以采用顺序存储 也可以采用链式存储 非线性结构的 数据只能采用链式存储 3 栈和队列逻辑都是线性结构 串逻辑上不是线性结构 4 从双向循环链表中任何一个结点出发 查找该结点的前驱和后继都很方便 5 对于无向连通图 从图中的任何一个顶点出发 都可以遍历图中的所有顶 点 6 序列 101 88 49 75 33 39 43 构成最大堆 7 二叉树的中序和后序遍历序列可以唯一确定一颗二叉树 8 在顺序表中进行顺序搜索时 若各元素的搜索概率不等 则各元素应按照 搜索概率的增序排列存放 则可得到最小的平均搜索长度 二 简答题二 简答题 1 将 n 阶对称矩阵按上三角压缩存储在一维数组 A 中 请分析 A 中应包含多 少个数据元素 需要推导过程 2 队列可以用循环单链表来实现 故可以只设置头指针或者只设置一个尾指针 请 问哪一个种方案更合适 请从算法的时间复杂度分析为什么 3 请简述顺序存储结构的优点和不足 三 分析题三 分析题 1 为了方便访问树中任何一个结点的孩子结点和双亲结点 设计应采用的存 储结构 并画出此树的存储示意图 e e c cb b d d a a f f 第 2 页 共 7 页 2 设哈希表为 HT 7 哈希函数为 H key key 7 按下列关键码序列 1 17 15 45 22 12 41 构造哈希表 1 画出采用链表法解决冲突的哈希表 2 计算等概率下搜索成功时的平均搜索长度 3 假设系统在某通信中只使用 6 种字符 其出现概率分别为 0 03 0 06 0 07 0 08 0 29 0 47 现需要对通信文本文件进行压缩 1 画出相应的 Huffman 树 约定左子树权值小于右子树 2 设计出每个字符的 Huffman 编码 左为 0 右为 1 3 简述译码的过程 4 待排序的关键码序列为 56 7 18 33 29 1 20 25 分别写出使用 下列排序方法第一趟排序后的结果 1 直接选择排序 2 二路归并排序 3 冒泡排序 4 直接插入排序 5 画出下网的所有最小生成树 b be ef f a a c c d d 7 71515 1515 2121 2 25 5 9 9 2020 1111 第 3 页 共 7 页 四 算法设计题四 算法设计题 1 阅读下面顺序表的算法 const int MaxListSize 200 设定表可容纳的元素最大个数 template class SeqList T data MaxListSize int size 当前表的大小 public void Insert const T template void SeqList Insert const T if cout 顺序表已满 exit 0 if pos 0 检查参数的合法性 cout pos i 数据移位 插入数据 size 表长增 1 1 补充完成算法 Insert 2 计算算法 Insert 的时间复杂度 3 若不需要考虑数据固有的顺序 如何使算法的效率达到 O 1 第 4 页 共 7 页 2 补充算法 完成链式堆栈的入栈操作 template class LinStack 定义链式堆栈类模板 StackNode top T 为栈中元素类型 top 指向栈顶 int size 栈当前大小 public void Push const T 入栈 template void LinStack Push const T 把新结点作栈顶 栈大小增加 1 第 5 页 共 7 页 综合练习题一综合练习题一参考答案参考答案 一 判断题 正确打一 判断题 正确打 错误打 错误打 并改正 并改正 1 2 非线性结构的数据可以采用顺序存储 也可以采用链式存 储 3 串逻辑上也是线性结构 4 5 6 7 8 按降序排列 二 简答题二 简答题 1 答 数据元素个数为 n n 1 2 1 n n 1 2 2 答 只设置一个尾指针更合适 只设置一个尾指针 出队列和入队列的时间 复杂度都是 O 1 只设置头指针 出队列时间复杂度是 O n 入队列的时间 复杂度是 O n 3 答 优点 设计简单 可随机存取数据元素 不足 存储容量需要预先确定 为保证数据的原有顺序 插入和删除数据需要移动数据元素 三 分析题三 分析题 1 答 应采用双亲孩子表示法 存储示意图 序号 data parent 0a 1 1b0 2c0 3d1 4e1 5f1 1 2 3 4 5 第 6 页 共 7 页 2 答 下标 data link 2 平均搜索长度 1 4 2 2 3 1 7 11 7 3 答 1 2 编码 0 47 0 0 29 11 0 07 1010 0 08 1011 0 03 1000 0 06 1001 3 译码为根结点到叶结点的匹配过程 0 11 2 317 4 512 641 45 2215 0 0 0 0 3 3 0 0 0 0 6 6 0 0 0 0 9 9 0 0 2 2 9 9 0 0 0 0 7 7 0 0 0 0 8 8 0 0 1 1 5 5 0 0 2424 0 0 5353 0 0 4 4 7 7 1 1 0000 第 7 页 共 7 页 4 答 1 1 7 18 33 29 56 20 25 2 7 56 18 33 1 29 20 25 3 7 18 33 29 1 20 25 56 4 7 56 18 33 29 1 20 25 5 答 1 四 算法设计题四 算法设计题 1 1 size MaxListSize p