《习题答案及练习》PPT课件.ppt

计算机软件基础 第三版 第二章习题答案及练习 a O n2 b O n c O n3 3 O n3 8 统计输入数中正数和负数的个数 输入0则结束 main intx num1 0 num2 0 printf inputnum scanf d 1 L P link 2 R data P data 9 对以下单链表分别执行下列各程序段 并画出结果示意图 3 R data P link data 4 P link link link data P data 5 T P while T NULL T data T data 2 T T link 6 T P while T link NULL T data T data 2 T T link 7 P JD malloc sizeof JD P data 10 R link P P link S P 10 8 T L T link P link free P 9 S link L 如果S link L则S所指向的结点为尾结点 12 c dcba13 d 9 5 7 314 a T T 1 15 bc 2 14图示 16 采用队列数据结构 要做的工作 开辟一个队列结构的线性表 设置一个队头指针和一个队尾指针 有报到的或完成任务的 就排在队尾 需要工人做工时 从队头选派工人 17 入栈序列是 1 2 3 出栈序列是 2 1 3 19 i i 1 2 j 28 有n个叶子结点的哈夫曼树 其结点总数为2n 1 23 n24 1 2i 125 CDBFGEA26 110027 8 26 A B C D E9 7 3 5 11C的编码是1100 21 voidchange NODE T NODE m if T NULL m T LT L T R T R m change T L change T R typedefstructnode Intdata Structnode L R NODE A C B D A C B D 试以二叉链表作为存储结构 将二叉树中所有结点的左右子树进行交换 34 O n 35 b a b36 散列37 块与块之间按关键字有序 39 构造哈希函数 解决冲突 n n 1 2直接插入排序 18 30 7 14 23 8 给出下列函数的递归和非递归算法F n n 1 n F n 1 intF intn intm if n 0 m 1 elsem n F n 1 return m 非递归函数 intF intn intf1 1 s 1 if n 0 return1 while s n f1 f1 s s s 1 return f1 intF intn intcj if n 0 n 1 cj 1 elsecj n F n 1 return cj F 4 n 4 cj 4 F 3 Return cj n 2 cj 2 F 1 Return cj n 3 cj 3 F 2 Return cj n 1 cj 1 Return cj 补充作业3程序的功能是什么 根据下面图示的递归执行过程 给出二叉树先序遍历算法的执行过程 intsearch NODE LB inte NODE p LB p while p data e 在链式线性表LB中查找值为e的数据元素的位置的函数 typedefstructnode intdata structnode next NODE 第二版p70 7 e intAA R e P R intn 1 while P data e p next NULL p p next n n 1 if p next NULL 关系运算符 逻辑运算符 错在哪 main intn 0 intm 0 floata scanf f 程序有问题吗 AA inta n 错在哪 AA intb n intb n main staticinta 7 AA a 7 a 0 b 0 top1 T1 B C A B C D E 初态 a top2 OS NS B A b OS A c NS OS T2 T1 A e NS OS T2 T3 f T3 A T1 NS OS C T1 A d NS OS T4 T4 T2 T3 NS h A B C D E T1 B C T1 D E T2 D E 错在哪 在电话系统中 基本的数据元素是 用户名 电话号码 电话系统的数据是大量的这类数据元素的集合 其中用户名是用汉语拼音代替 数据元素的排列是按拼音字母升序排列 只有这样 才能进行高效率查询 由于该系统中数据元素的数量事先很难确定 增加或撤消用户电话是常有的操作 问题 1 如果让你设计一个电话号码查询系统 你认为采用什么样的数据结构最好 为什么 2 该系统中都有哪些常用的操作 简述每种操作的基本思想 1 阅读程序并回答问题 1 程序执行了什么功能 2 针对右面的图 写出程序的运行结果 typedefstructBiTN