数据结构答案习题课1-9ppt课件.ppt

第2章线性表 1 1 顺位序输入n个数据元素的值 建立带表头结点的单链表 1voidCreateList LinkList 2 1 顺位序输入n个数据元素的值 建立带表头结点的单链表 2voidCreateList LinkList 3 1 顺位序输入n个数据元素的值 建立带表头结点的单链表 同学实例1 请问程序正确吗 voidCreateList LinkList 4 1 顺位序输入n个数据元素的值 建立带表头结点的单链表 同学实例2 请问程序正确吗 voidCreateList LinkList 5 1 顺位序输入n个数据元素的值 建立带表头结点的单链表 同学实例3 请问程序正确吗 voidCreateList LinkList 6 2 有一个带头指针的单链表 写出在其值为x的结点之后插入m个结点的算法 1Statusinsertm LinkList 7 2 有一个带头指针的单链表 写出在其值为x的结点之后插入m个结点的算法 2Statusinsertm LinkList 插入到p之后 returnOK 8 2 有一个带头指针的单链表 写出在每个其值为x的结点之后插入m个结点的算法 3Statusinsertm LinkList returnOK 9 3 假设在长度大于1的单循环链表 既无头结点 也无头指针 S为指向链表中某个结点的指针 试设计删除结点S的直接前驱结点的算法 同学实例 请问程序正确吗 Statusdeleteprior CirLinkList 10 3 假设在长度大于1的单循环链表 既无头结点 也无头指针 S为指向链表中某个结点的指针 试设计删除结点S的直接前驱结点的算法 1voiddeleteprior LinkList 释放结点 11 3 假设在长度大于1的单循环链表 既无头结点 也无头指针 S为指向链表中某个结点的指针 试设计删除结点S的直接前驱结点的算法 2voiddeleteprior LinkList 12 4 设计实现在单链表中删除值相同的多余结点的算法 Statusdeletesame LinkList t从p后查找相同结点 13 第4章串 14 2 设单链表中存放着n个字符 试设计算法判断字符串是否中心对称 intString Linklist 15 第6章树和二叉树 16 1 试找出分别满足下面条件的所有二叉树 1 前序序列和中序序列相同空二叉树或仅有一个结点的二叉树或任一结点均无左子树的非空二叉树 2 中序序列和后序序列相同空二叉树或仅有一个结点的二叉树或任一结点均无右子树的非空二叉树 3 前序序列和后序序列相同空二叉树或仅有一个结点的二叉树 17 2 已知一棵二叉树的中序遍历序列为DBHEAFICG 后序遍历序列为DHEBIFGCA 试画出该二叉树 中序 DBHEAFICG后序 DHEBIFGCA 18 3 编程统计二叉树中的结点个数 intnum BiTree root intnum1 num2 if root NULL return 0 elseif root lchild NULL 19 4 已知W 2 3 4 7 8 9 试构造关于W的一棵哈夫曼树 并求WPL 9 7 8 2 3 4 WPL 7 2 8 2 9 2 4 3 2 4 3 4 14 16 18 12 8 12 80 9 5 18 15 33 20 5 把如图所示的树转化成二叉树 21 6 画出和下列二叉树相应的森林 22 第7章图 23 1 请画出下图从定点A出发的广度优先生成树和深度优先生成树 24 2 写出下图的拓扑序列 V2 V1 V3 V6 V5 V4V2 V3 V1 V6 V5 V4 25 3 找出下图从A到C的最短路径 26 A B D C A B D C A B D A B S E C D B Vj 17 A B D E 17 A B D E E 15 A B D D 17 A B D C 18 A C 18 A C C 10 A B B i 4 i 3 i 2 i 1 从A到各终点的权值和最短路径 终点 27 4 试利用带洛伊德算法 写出下图相应的带权邻接矩阵的变化 28 4 试利用带洛伊德算法 写出下图相应的带权邻接矩阵的变化 29 4 试利用带洛伊德算法 写出下图相应的带权邻接矩阵的变化 30 第9章查找 31 1 设计出在递增有序的数组A 1 n 中查找值为x的元素的二分查找算法 学生作业 intSearch Bin SSTableST keyTypex low 1 high ST length while low high mid low high 2 if x ST elem mid x returnmid elseif x ST elem mid x high mid 1 elselow mid 1 return0 Serch Bin 32 intBSearch DataTypeA KeyTypex intlow 0 high n 1 mid while lowA mid low mid 1 return 1 查找失败 1 设计出在递增有序的数组A 1 n 中查找值为x的元素的二分查找算法 33 2 已知哈希表地址空间为0 14 哈希函数为H k kmod13 采用线性探查法处理冲突 将下列各数依次存入该散列表中 240 29 345 189 100 20 21 35 3 208 78 99 45 350性探测法 Hi H key i MODmi 1 2 k k m 189 78 350 29 208 3 100 240 345 12612112144469 20 99 35 21 45 计算余数 240 6 29 3 345 7 189 7 100 9 20 7 21 8 35 9 3 3 208 0 78 0 99 8 45 6 350 12 34 3 对于给定结点的关键字的集合K 10 18 3 8 19 2 7 9 试构造一棵二叉排序树 10 3 18 2 19 8 7 9 35 4 已知长度为12的表如下 Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec 1 建立相应的二叉排序树 2 建立相应的平衡二叉树 36 Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec Apr Aug Dec Nov Feb Jan Sep May June July Oct Mar 37 Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec Jan Feb Mar Apr May June July Aug 38 Jan Aug Mar Apr May June July Feb Sep Oct Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec 39 Jan Aug Mar Apr May June July Feb Oct Sep Nov Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec 40 Jan Aug Mar Apr May Feb Oct Sep Nov Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec 41 Jan Aug Mar Apr May June July Feb Oct Sep Nov Dec Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec 42 已知长度为12的表如下 建立相应的4阶B 树 Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec Jan FebJan FebJanMar AprFebJanMar 43 已知长度为12的表如下 建立相应的4阶B 树 Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec 44 已知长度为12的表如下 建立相应的4阶B 树 Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec 45 5 对于下面3阶B 树依次执行下列操作 画出每步的操作结果1 插入3002 插入703 插入304 删除150 46 1 插入300 260 300 47 2 插