数据结构课后习题

第一章第一章 3 1 A 2 C 3 D 5 计算下列程序中 x x 1 的语句频度 for i 1 i n i for j 1 j i j for k 1 k j k x x 1 解答 x x 1 的语句频度为 T n 1 1 2 1 2 3 1 2 n n n 1 n 2 6 6 编写算法 求 一元多项式 pn x a0 a1x a2x2 anxn的值 pn x0 并确定算法中每一语句 的执行次数和整个算法的时间复杂度 要求时间复杂度尽可能小 规定算法中不能使用求 幂函数 注意 本题中的输入为 ai i 0 1 n x 和 n 输出为 Pn x0 算法的输入和输出采 用下列方法 1 通过参数表中的参数显式传递 2 通过全局变量隐式传递 讨论两种方法的优缺点 并在算法中以你认为较好的一种实 现输入输出 解答 1 通过参数表中的参数显式传递 优点 当没有调用函数时 不占用内存 调用结束后形参被释放 实参维持 函数通 用性强 移置性强 缺点 形参须与实参对应 且返回值数量有限 2 通过全局变量隐式传递 优点 减少实参与形参的个数 从而减少内存空间以及传递数据时的时间消耗 缺点 函数通用性降低 移植性差 算法如下 通过全局变量隐式传递参数 PolyValue int i n float x a p printf nn scanf f printf nx scanf f for i 0 i n i scanf f 执行次数 n 次 p a 0 for i 1 i n i p p a i x 执行次数 n 次 x x x printf f p 算法的时间复杂度 T n O n 通过参数表中的参数显式传递 float PolyValue float a float x int n float p s int i p x s a 0 for i 1 inext S B P next P next next C P next S next D S next P next E S next L F S next NULL G Q P H while P next Q P P next I while P next NULL P P next J P Q K P L L L S M L P 3 D 4 D 5 D 4 已知顺序表已知顺序表 L 递增有序 编写一个算法 将递增有序 编写一个算法 将 X 插入到线性表的适当位置上 以保持线插入到线性表的适当位置上 以保持线 性表的有序性 性表的有序性 void inserX Seqlist L Elemtype x int i i L length 1 while i 0 i L length 7 试分别以不同的存储结构实现线性表的就地逆值的算法 即在原表的存储空间中将线性试分别以不同的存储结构实现线性表的就地逆值的算法 即在原表的存储空间中将线性 表表 a1 a2 an 逆置为 逆置为 an an 1 a1 1 以顺序表作存储结构 设线性表存于 以顺序表作存储结构 设线性表存于 a 1 arrsize 的前的前 elenum 个分量中 个分量中 void reverseqlist Seqlist L int i int temp for i 0 ilength 2 i temp L elem i L elem i L elem L length i 1 L elem L length i 1 temp 2 以单链表作存储结构 以单链表作存储结构 void reverselinklist linklist head Linklist p q p head next head next NULL while p next NULL q p next p next head next head next p p q 11 将线性表将线性表 A a1 a2 am B b1 b2 bn 合并成线性表合并成线性表 C C a1 b1 am bm bm 1 bn mn 线性表线性表 A B C 以单链表作为存储结构 且以单链表作为存储结构 且 C 表利用表利用 A 表和表和 B 表中的结点空间构成 表中的结点空间构成 注意 单链表的长度值注意 单链表的长度值 m 和和 n 均未显式存储 均未显式存储 解答 算法如下 LinkList merge LinkList A LinkList B LinkList C Node pa qa pb qb p pa A next pa 表示 A 的当前结点 pb B next p A 利用利用 p 来指向新连接的表的表尾 初始值指向表来指向新连接的表的表尾 初始值指向表 A 的头结点的头结点 while pa NULL qb qb next p next pa 交替选择表 A 和表 B 中的结点连接到新链表中 p pa p next pb p pb pa qa pb qb if pa NULL p next pa A 的长度大于 B 的长度 if pb NULL p next pb B 的长度大于 A 的长度 C A Return C 第三章第三章 1 B 2 C 3 C 8 假设表达式由单字母变量和双目四则运算构成 试写一个算法 将一个通常书写形式且 书写正确的表达式转为逆波兰式 分析 算法的思想 所有的变量在逆波兰式中出现的先后顺序和在原表达式中出现的相算法的思想 所有的变量在逆波兰式中出现的先后顺序和在原表达式中出现的相 同 因此只需要设立一个同 因此只需要设立一个 栈栈 根据操作符的 根据操作符的 优先级优先级 调整它们在逆波兰式中出现的顺序 调整它们在逆波兰式中出现的顺序 include include define STACK INIT SIZE 100 define STACK INCREAMENT 10 typedef struct 栈 char base char top int stackSize Stack void initStack Stack stack stackSize STACK INIT SIZE void push Stack S top S stackSize S base S stackSize STACK INCREAMENT S top p void pop Stack return p stack top char getTop Stack stack 获得栈顶元素 if stack base stack top return NULL return stack top 1 bool isAlpha char p 判断是不是字母 return p a else while precede getTop stack p 0 q c push stack p p void main char str 100 char newStr 100 int i for i 0 ifront Q front if Q front Q front Q elememt Q rear x Q rear Q rear 1 MAXSIZE 设置队尾指针 Return TRUE 出队算法 int DeleteQueue SeqQueue Q QueueElementType x 删除队头元素 用 x 返回其值 if Q front Q rear x Q element Q front Q front Q front 1 MAXSIZE 重新设置队头指针 if Q front Q rear tag 0 队头元素出队后队列为空 重新设置标志域 Return TUUE 15 1 功能 将栈中元素倒置 2 功能 删除栈中的 e 元素 3 功能 将队列中的元素倒置 第四章第四章 1 设设 s I AM A STUDENT t GOOD q WORKER 给出下列操作的结果 给出下列操作的结果 解答 StrLength s 14 SubString sub1 s 1 7 sub1 I AM A SubString sub2 s 7 1 sub2 StrIndex s 4 A 6 StrReplace s STUDENT q s I AM A WORKER StrCat StrCat sub1 t StrCat sub2 q sub1 I AM A GOOD WORKER 4 叙述以下每对术语的区别 空串和空格串 串常量与串变量 主串和子串 串变量的名叙述以下每对术语的区别 空串和空格串 串常量与串变量 主串和子串 串变量的名 字和串变量的值 字和串变量的值 解答 不含任何字符的串称为空串 其长度为 0 仅含有空格字符的串称为空格串 其 长度为串中空格字符的个数 空格符可用来分割一般的字符 便于人们识别和阅读 但计 算串长时应包括这些空格符 空串在串处理中可作为任意串的子串 用引号 数据结构教学中通常用单引号 而 C 语言中用双引号 括起来的字符序列称为串 常量 串值可以变化的量称为串变量 串中任意个连续的字符组成的子序列被称为该串的子串 包含子串的串又被称为该子串的 主串 子串在主串中第一次出现的第一个字符的位置称子串在主串中的位置 串变量的与其它变量一样 要用名字引用其值 串变量的名字也是标识符 串变量的值可 以修改 5 已知 已知 s xyz t x z y 试利用联结 求子串和置换等基本运算 将 试利用联结 求子串和置换等基本运算 将 s 转化为转化为 t 答案 本题有多种解法 下面是其中的一种 1 s1 substr s 3 1 取出子串 y 2 s2 substr s 6 1 取出子串 3 s3 substr s 1 5 取出子串 xyz 4 s4 substr s 7 1 取出子串 5 s5 replace s3 3 1 s2 形成部分串 x z 6 s s5 s4 s1 形成串 t 即 x z y 解析 题中所给操作的含义如下 连接函数 将两个串连接成一个串 substr s i j 取子串函数 从串 s 的第 i 个字符开始 取连续 j 个字符形成子串 replace s1 i j s2 置换函数 用 s2 串替换 s1 串中从第 i 个字符开始的连续 j 个字符 8 编写下列算法 编写下列算法 1 将顺序串将顺序串 r 中所有值为中所有值为 ch1 的字符换成的字符换成 ch2 的字符 的字符 2 将顺序串将顺序串 r 中所有字符按照相反的次序仍存放在中所有字符按照相反的次序仍存放在 r 中 中 3 从顺序串从顺序串 r 中删除其值等于中删除其值等于 ch 的所有字符 的所有字符 4 从顺序串从顺序串 r1 中第中第 index 个字符起求出首次与串个字符起求出首次与串 r2 相同的子串的起始位置 相同的子串的起始位置 5 从顺序串从顺序串 r 中删除所有与串中删除所有与串 r1 相同的子串 相同的子串 解答 1 Void replace Str r char ch1 char ch2 将串 r 中所有值为 ch1 的字符换成 ch2 的字符 for int i 0 ilen i if r vec i ch1 r vec i ch2 return 2 Void converse str r 将串 r 中所有字符按照相反的次序存放在 r 中 for int i 0 ilen 2 i Char ch r vec i r vec i r vec r len 1 i r vec r len 1 i ch Return 3 Void delete str r char ch 从串 r 中删除其值等于 ch 的所有字符 int i 0 int len r len While ivec i ch for j i jvec j r vec j 1 len else i return 4 int position str r1 int index char r2 从串 r1 中第 index 个字符起求出首次与字符 r2 相同的子串的起始位置 if indexr len return ERROR int i index while r vec i r2 if i r len cout len r1 len return 0 for i 0 ilen r1 len j i for t 0 tch j r1 ch t break if t r1 len for j i j r1 lenlen j r ch j r ch j r1 len r len r1 len if t r1 len i return 1 课本119页8 1题 c课本119页8 2题 c课本119页8 3题 c课本119页8 4题 c 课本119页8 5题 c 第五章第五章 1 假设有假设有 6 行行 8 列的二维数组列的二维数组 A 每个元素占用 每个元素占用 6 个字节 存储器按字节编址 已知个字节 存储器按字节编址 已知 A 的的 基地址为基地址为 1000 计算 计算 1 数组 A 共占用多少字节 288 2 数组 A 的最后一个元素的地址 1282 3 按行存储时 元素 A36 的地址 1126 4 按列存储时 元素 A36 的地址 1192 3 设有一个上三角矩阵 A 将其上三角中的元素逐列压缩存储到一个 n n 1 2 的一维数组 C 下标从 1 开始 请给出计算上三角矩阵中任意元素 aij i j 在一维数 组 C 中位置的公 式 K n n i 2 i 1 2 j i 1 2n i 2 i 1 2 j i 1 i m A m 矩阵行数 C n A n 矩阵列数 C t 0 三元组表长度 k 0 l 0 while k t if temp 相加不为零 加入 C C data c t i A data k i C data c t j A data k j C data c t v temp k l if A data k i B data l i C data c t j A data k j C data c t v A data k v k if A data k i B data l i C data c t j B data l j C data c t v B data l v l while k t 将 A 中剩余三元组加入 C C data c t i A data k i C data c t j A data k j C data c t v A data k v k while l t 将 B 中剩余三元组加入 C C data c t i B data l i C data c t j B data l j C data c t v B data l v l 9 求下列广义表运算的结果 1 HEAD a b c d 2 TAIL a b c d 3 TAIL HEAD a b c d 4 HEAD TAIL HEAD a b c d 5 TAIL HEAD TAIL a b c d 解答 1 a b 2 c d 3 b 4 b 5 d 第六章第六章 6 1 分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态 解答 具有 3 个结点的树 具有 3 个结点的二叉树 6 4 假设一棵二叉树的先序排列为 EBADCFHGIKJ 中序序列为 ABCDEFGHIJK 请画出该二叉 树 6 5 已知二叉树有 50 个叶子结点 则该二叉树的总结点数至少应有多少个 解答 n0表示叶子结点数 n2表示度为 2 的结点数 则 n0 n2 1 所以 n2 n0 1 49 当二叉树中没有度为 1 的结点时 总结点数 n n0 n2 99 6 8 画出与下列已知序列对应的树 T 树的先根次序访问序列为 GFKDAIEBCHJ 树的后根次序访问序列为 DIAEKFCJHBG 解答 树的后根遍历相当于二叉树的中序遍历 先转换为二叉树 在根据左孩子右兄弟的规则转换为数 6 9 假设通讯的电文仅由 8 个字母组成 字母在电文中出现的频率分别为 0 07 0 19 0 02 0 06 0 32 0 03 0 21 0 10 请为这 8 个字母设计哈夫曼编码 解答 答案不唯一 构造哈夫曼树如下 哈夫曼编码为 I1 11111 I5 1100 I2 11110 I6 10 I3 1110 I7 01 I4