2014数据结构习题集答案.pdf

数据结构 习题集答案 数据结构 习题集答案 黄橡丽 黄橡丽 2014 年 8 月 2014 年 8 月 第一章第一章 第五章第五章 参考答案参考答案 一 单选与填空一 单选与填空 1 n n 1 2 2 O n 3 常数阶常数阶 O n 4 C 5 A 6 C 7 D 8 A 9 O n 10 B 11 C 12 A 13 A 14 B 15 C 16 L next NULL 17 P prior next P next P next prior P prior 18 B 19 C 20 3 21 C 22 A 23 A 24 C 25 D 26 D 27 I have a dream ave 28 6 29 A 30 D 31 a b c 32 B 33 C 二 算法题二 算法题 1 程序的功能 对长度大于等于 2 的单链表 将首元结点插入到表尾 2 1 栈中的数据元素逆置 2 如果栈中存在元素 e 将其从栈中清除 3 程序的运行结果 1 chris 2 card 4 10 题答案 define OK 1 define ERROR 0 typedef int Status typedef struct LNode int data struct LNode next LNode LinkList 4 题答案 int Length LinkList L 求链表的长度 k 0 p L while p next p p next k return k Length 5 题答案 LNode Locate LinkList L Elemtype x 链表上的元素查找 返回指针 p L next while p return p Locate 6 题答案 Status ListDelete L LinkList j 0 while p next j if p next j i 1 return ERROR 删除位置不合理 q p next 临时保存被删结点的地址以备释放 p next q next 改变删除结点前驱结点的指针域 e q data 保存删除结点的数据域 free q 释放删除结点的空间 return OK ListDelete L 7 题答案 Status ListInsert L LinkList j 0 while p j 寻找第 i 1 个结点 if p j i 1 return ERROR i 大于表长 1 或者小于 1 s LinkList malloc sizeof LNode 生成新结点 s s data e 将结点 s 的数据域置为 e s next p next 将结点 s 插入 L 中 p next s return OK ListInsert L 8 题答案 void CreateList L LinkList L next NULL r L 尾指针 r 指向头结点 for i 0 idata 输入元素值 p next NULL r next p 插入到表尾 r p r 指向新的尾结点 CreateList L 9 题答案 Status Delete Between Linklist p L next while p q是最后一个不大于mink的元 素 p 是第一个大于 mink 的元素 if p return ERROR 如果没有比 mink 更大的元素 while p free p p q next return OK Delete Between 10 题答案 void MergeList L LinkList pb Lb next pc Lc La 用 La 的头结点作为 Lc 的头结点 while pa pc pa pa pa next else pc next pb pc pb pb pb next pc next pa pa pb 插入剩余段 free Lb 释放 Lb 的头结点 第六章第六章 参考答案 参考答案 一 单选与填空一 单选与填空 1 D 2 150 3 C 4 A 5 D 6 D 7 B 8 A 9 B 10 1 95 11 B 二 解答题二 解答题 1 1 先序遍历 GADEFBC 二叉树的形态见左下图 2 对应的树见右下图 2 1 画出该二叉树 2 画出对应的二叉树 a cb ed f g i h a kb c f l e h d g i j 3 1 二叉树 树形结构同 2 2 二 叉 树 的 后 序 后 继 线 索 树 3 二 叉 树 对 应 的 森 林 GJHDBEIFCA 4 1 哈夫曼树 三 算法题答案三 算法题答案 1 求位于先序序列中第k个位置的结点的值 e中存放结点的返回值 i 为计数器 Status PONodeK TElemType if i k e T data else PONodeK e i k T lchild PONodeK e i k T rchild a b c j d e f h g i 2 电文中六个字符的哈夫曼编码如下 A 01 B 000 C 111 D 110 E 10 F 001 a b j d e f h g i c 8 10 0 0 0 0 0 1 1 1 1 1 100 56 28 26 17 18 11 44 28 A E B F D C return OK 2 求二叉树中叶子结点的数目 Status POLeafNodeNum int POLeafNodeNum i T lchild POLeafNodeNum i T rchild return OK 3 按先序交换二叉树的左右子树 Status ExchangeBiTree BiTree if T p T lchild T lchild T rchild T rchild p ExchangeBiTree T lchild ExchangeBiTree T rchild return OK 4 求二叉树的深度 int Depth BiTree T int depthLeft depthRight depthval if T depthval 0 else depthLeft Depth T lchild depthRight Depth T rchild if depthLeft depthRight depthval 1 depthLeft else depthval 1 depthRight return depthval 第七章第七章 参考答案 参考答案 一 单选与填空一 单选与填空 1 B 2 C 3 D 4 B 5 C 6 D 7 n n 1 2 8 B 9 A 10 A 11 A 12 15 二 解答题二 解答题 1 2 1 无向图 2 邻接矩阵存储结构 3 广度优先生成树 3 1 2 3 B A F C D E 011010 100101 100100 011010 100101 010010 A B D C E F 6 5 3 5 6 6 4 4 表 1 各事件 顶点 的最早发生时间和最迟发生时间为 顶点 a b c d e f g h k ve 0 6 4 5 7 7 15 14 18 vl 0 6 6 8 7 10 16 14 18 表 2 各活动 弧 的最早开始时间和最迟开始时间为 弧 ab ac ad be ce df eg eh fh gk hk e 0 0 0 6 4 5 7 7 7 15 14 l 0 2 3 6 6 8 8 7 10 16 14 关键路径为 5 1 有向带权图的邻接矩阵为 3 深度优先生成树 0 10 602 30 40 1030 50 320 2 拓扑排序有两种可能结果 V1V2V3V4V6V5V7V8 和 V1V3V2 V4V6V5V7V8 V1 V2 V3 V4 V6 V5 V7 V8 4 注 斜粗体的部分为所求 从 V1 到各终点的距离和最短路径的求解过程 终点 i 1 i 2 i 3 i 4 i 5 i 6 i 7 V2 2 V3 3 3 V4 7 6 V5 13 13 12 V6 10 V7 15 V8 16 16 16 vj v2 v3 v4 v6 v5 v7 v8 第第九九章章 参考答案 参考答案 一 单选与填空一 单选与填空 1 4 2 B 3 B 4 C 5 B 6 D 7 B 8 C 9 D 二 解答题二 解答题 1 长度为 12 的有序表进行折半查找的判定树为 等概率查找成功时的平均查找长度为 1 1 2 2 4 3 5 4 12 37 12 2 6 3 9 1 4 7 11 2 5 8 10 6 12 3 成功 1 2 2 5 1 1 1 2 8 15 8 不成功 5 4 3 2 1 2 1 2 1 7 6 11 34 11 4 成功 ASLsucc 1 4 2 2 3 7 11 7 不成功 ASLnsucc 1 1 2 3 7 7 7 1 13 55 20 49 22 0 1 5 2 6 3 4 32 39 5 画表如下 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 查找 63 首先要与 H 63 63 16 15 号单元内容比较 即 63 vs 31 no 然后顺移 与 46 47 32 17 63 相比 一共比较了 6 次 查找 60 首先要与 H 60 60 16 12 号单元内容比较 但因为 12 号单元为空 应当有空标 记 所以应当只比较这一次即可 对于黑色数据元素 各比较 1 次 共 6 次 对红色元素则各不相同 要统计移位的位数 63 需要 6 次 49 需要 3 次 40 需要 2 次 46 需要 3 次 47 需要 3 次 所以 ASL 1 11 6 2 3 3 6 23 11 三 算法题答案三 算法题答案 typedef int KeyType typedef struct KeyType key char name 20 SElemType typedef struct SElemType elem MAXSIZE int length SSTable 1 int Search Seq SSTable ST KeyType key ST elem 0 key key for int i ST length ST elem i key key i return i Search Seq 2 int Search Bin SSTable ST KeyType key int high low mid low 1 high ST length while low high mid low high 2 if key ST elem mid key return mid else if key ST elem mid key high mid 1 else low mid 1 return 0 Search Bin 第十章第十章 参考答案 参考答案 一 单选与填空一 单选与填空 1 C 2 A 3 D 4 C 5 C 6 B 7 O n2 8 直接插入排序直接插入排序 二 解答题二 解答题 1 1 希尔排序 初始序列 37 65 56 8 76 3 89 34 21 46 d 5 3 65 34 8 46 37 89 56 21 76 d 3 3 46 21 8 56 34 76 65 37 89 d 1 3 8 21 34 37 46 56 65 76 89 2 快速排序 第一趟排序结果 3 堆排序 初始关键字的完全二叉树形式 初始建堆的结果 37 65 56 8 76 3 89 34 21 46 i j j 21 65 56 8 76 3 89 34 46 i i j 21 56 8 76 3 89 34 65 46 i j j 21 34 56 8 76 3 89 65 46 过程 i i j 21 34 8 76 3 89 56 65 46 i j j 21 34 3 8 76 89 56 65 46 i i j 21 34 3 8 76 89 56 65 46 i j j 21 34 3 8 37 76 89 56 65 46 第一次交换之后的结果 第一次交换之后重建堆的结果 2 1 直接插入排序 初始关键字 503 087 512 061 908 170 897 275 653 426 i 2 087 503 512 061 908 170 897 275 653 426 i 3 087 503 512 061 908 170 897 275 653 426 i 4 061 087 503 512 908 170 897 275 653 426 i 5 061 087 503 512 908 170 897 275 653 426 i 6 061 087 170 503 512 908 897 275 653 426 i 7 061 087 170 503 512 897 908 275 653 426 i 8 061 087 170 275 503 512 897 908 653 426 i 9 061 087 170 275 503 512 653 897 908 426 i 10 061 087 170 275 426 503 512 653 897 908 2 希尔排序 初始关键字 503 087 512 061 908 170 897 275 653 426 d1 5 170 087 275 061 426 503 897 512 653 908 d2 3 061 087 275 170 426 503 897 512 653 908 d3 1 061 087 170 275 426 503 512 653 897 908 3 二路归并 初始关键字 503 087 512 061 908 170 897 275 653 426 第一趟归并结果 087 503 061 512 170 908 275 897 426 653 第二趟归并结果 061 087 503 512 170 275 897 908 426 653 第三趟归并结果 061 087 170 275 503 512 897 908 426 653 第四趟归并结果 061 087 170 275 426 503 512 653 897 908