南邮数据结构课后习题课ppt课件.ppt

习题课一 1 5确定下列各程序段的程序步 确定划线语句的执行次数 计算它们的渐近时间复杂度 习题一 第18页 1 i 1 k 0 do k k 10 i i while i n 1 答 划线语句的执行次数为n 1 O n 1 2 i 1 x 0 do x i 2 i while i n 划线语句的执行次数为 log2n O log2n 3 for inti 1 i n i for intj 1 j i j for intk 1 k j k x 划线语句的执行次数为n n 1 n 2 6 O n3 2 4 x n y 0 while x y 1 y 1 y 2 1利用线性表类LinearList提供的操作 涉及实现两个集合的交和差运算 划线语句的执行次数为 O 习题二 第37页 3 include include seqlist0 h include conio h templatevoidInterSection SeqList 2 1利用线性表类LinearList提供的操作 涉及实现两个集合的交和差运算 4 templatevoidDifference SeqList voidmain SeqListLA 10 LB 10 for inti 1 i 8 i LA Insert i i for i 1 i 3 i LB Insert i i 3 InterSection LA LB Difference LA LB 5 templatevoidSeqList Invert1 Ttemp for inti 0 i length i Find length temp 得到序列的最后一个元素Delete length Insert i temp 2 2 2 在类LinearList中增加一个成员函数 将顺序表逆置 实现该函数并分析算法的时间复杂度 利用类SeqList提供的操作直接实现 6 2 2 2 在类LinearList中增加一个成员函数 将顺序表逆置 实现该函数并分析算法的时间复杂度 不利用类SeqList提供的操作直接实现 templatevoidSeqList Invert Te for inti 0 i length 2 i e elements i elements i elements length 1 i elements length 1 i e O n 7 2 5在类SingleList中增加一个成员函数 将单链表逆置运算 直接实现该函数并分析其时间复杂度 templatevoidSingleList invert Node p first q first NULL while p q p link p link first first p p q 8 2 7单链表中结点按元素值递增链接 在类SingleList中增加一个成员函数 直接实现删除结点值在a至b之间的结点 a b templatevoidSingleList DeleteAb Ta Tb Node p first q first while p 思考结点a和b有没有删除掉 9 习题三 第50页 3 1设A B C D E五个元素依次进栈 进栈后可立即出栈 问能否得到下列序列 若能得到 则给出相应的push和pop序列 若不能 则说明理由 1 A B C D E2 A C E B D3 C A B D E4 E D C B A答 2 和3 不能 对2 中的E B D而言 E最先出栈则表明 此时B和D均在栈中 由于 B先于D进栈 所以应有D先出栈 同理3 也不能 1 能 push pop push pop push pop push pop push pop 4 能 push push push push push pop pop pop pop pop 10 3 2设计2个栈共享一个数组 画出示意图 定义一个足够大的栈空间 该空间的两端分别设为两个栈的栈底 用bottom1和bottom2指示 让两个栈的栈顶 用top1和top2指示 都向中间伸展 直到两个栈的栈顶相遇 才会发生溢出 栈空 两栈均空 top1 0且top2 n 1栈满 top1 top2 1 写出下列表达式的后缀表达式 a b c d ab cd b 2 4 a cb2 4a c 11 编程实现利用队列将栈中元素逆置的算法templatevoidinvertstack SeqStack 12 4 1给出三维数组元素A i j k 的存储地址loc A i j k 习题四 第68页 答 设有三维数组声明为A n1 n2 n3 每个元素占m个存储单元 则loc A i j k loc A 0 0 0 m i n2 n3 j n3 k 13 4 5给出下列稀疏矩阵的行优先和列优先顺序存储的三元组表 14 设计递归算法 对整数数组A n 求数组A的最大整数 求数组A中n个整数的平均值 求数组的最大值intMaximum inta intn if n 1 returna 0 数组只有一个元素时返回a 0 else if Maximum a n 1 a n 1 returna n 1 elsereturnMaximum a n 1 求数组的平均值floatAverage inta intn if n 1 returnfloat a 0 elsereturn Average a n 1 n 1 a n 1 n 习题五 第81页 15 5 2设计一个递归算法 实现对一个有序表的顺序搜索 templateintSeqList Search4 constT templateintSeqList Sch4 constT 16 5 3画出对长度为12的有序表进行对半查找的二叉判定树 并求等概率搜索时 成功搜索的平均搜索长度解 1二叉判定树如下 成功搜索的平均搜索长度由于第i层有2i个结点 故平均搜索长度为 ASL log2 n 1 P 77 17 习题六 第107页 6 2 2 对于三个结点A B和C 可分别组成多少不同的无序树 有序树和二叉树 答 1 无序树 9棵 2 有序树 12棵 3 二叉树 30棵 18 6 4求一棵二叉树的叶子结点个数 templateintBTree Leaves intcount 0 Leaf root count returncount templatevoidBTree Leaf BTNode t int 其中Leaves声明为public型 Leaf声明为private型 19 6 4设对一棵二叉树进行中序遍历和后序遍历的结果分别为 1 中序遍历BDCEAFHG 2 后序遍历DECBHGFA画出该二叉树 答 20 6 5写出图6 23的遍历结果 先序 ADEHFJGBCK中序 HEJFGDABKC后序 HJGFEDKCBA 6 6 6 设计算法 交换一棵二叉树中每个结点的左 右子树 templatevoidBTree Exch BTNode p if p BTNode q Exch p lchild p lchild Exch p rchild p rchild q 21 6 10将图题6 24中的树转换成二叉树 并将图6 23中的二叉树转换成森林 22 6 11给出对图6 24中的树的先序遍历和后序遍历的结果 答 先序 A D E F J G M B L H C K后序 J G F E D M H L K C B A 23 分别以下列数据为输入 构造最小堆 80 10 70 20 60 30 50 40 24 WPL