《软件技术基础》习题解答.docVIP

第二章 2.1 什么是数据结构？它对算法有什么影响？ 数据结构是指同一数据对象中各数据元素间存在的关系。 数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。 何谓算法？它与程序有何区别？ 广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。 和程序的区别：一个程序包括两个方面的内容： （1）对数据的描述，即数据结构。 （2）对操作的描述，即算法。 所以算法是程序的一个要素。 2.12试编写算法求已知单链表长度，并考虑表空的情况。 p = head i = 0 While(p!=nil) //表不为空 P-- next(p)//移动到下一个元素 i++ End(while) Return i //返回数据的个数2.14 已知一循环链表中数值已按递增有序排列现要插入一个新结点，并使插入一个新节点，并使插入后链表仍为有序序列 ←b; If(head=nil) then{ head←head;head←p;return; } If(bdata (head)) then {next(p)←head ;head←p;return; } q←head While(next(q)≠nil)and(bdata(next(q)))do q←head(q) If(next(q)≠nil)then{next(p)←next(q);next(q)←p; } Else{ next(q)←p;next(p)←nil; } return } 2.30 设一颗二叉树其中序和后序遍历为 中序：BDCEAFHG 后序：DECBHGFA 答案：ABCDEFHG 2.33．给定一组权值W={8,2,5,3,2,17,4},画出由此生成的哈夫曼树。 2.34.有一图如题图2.4所示： （2） V1作深度优先有哪些信誉好的足球投注网站: V1作广度优先有哪些信誉好的足球投注网站: 线性插入排序：41，62，13，84，35，96，57，39，79，61，15，83 第01趟：41，62，13，84，35，96，57，39，79，61，15，83 第02趟：13，41，62，84，35，96，57，39，79，61，15，83 第03趟：13，41，62，84，35，96，57，39，79，61，15，83 第04趟：13，35，41，62，84，96，57，39，79，61，15，83 第05趟：13，35，41，62，84，96，57，39，79，61，15，83 第06趟：13，35，41，57，62，84，96，39，79，61，15，83 第07趟：13，35，39，41，57，62，84，96，79，61，15，83 第08趟：13，35，39，41，57，62，79，84，96，61，15，83 第09趟：13，35，39，41，57，61，62，79，84，96，15，83 第10趟：13，15，35，39，41，57，61，62，79，84，96，83 第11趟：13，15，35，39，41，57，61，62，79，83，84，96 冒泡排序：41，62，13，84，35，96，57，39，79，61，15，83 第01趟：41，13，62，35，84，57，39，79，61，15，83，96 第02趟：13，41，35，62，57，39，79，61，15，83，84，96 第03趟：13，35，41，57，39，62，61，15，79，83，84，96 第04趟：13，35，41，39，57，61，15，62，79，83，84，96 第05趟：13，35，39，41，57，15，61，62，79，83，84，96 第06趟：13，35，39，41，15，57，61，62，79，83，84，96 第07趟：13，35，39，15，41，57，61，62，79，83，84，96 第08趟：13，35，15，39，41，57，61，62，79，83，84，96 第09趟：13，15，35，39，41，57，61，62，79，83，84，96 第10趟：13，15，35，39，41，57，61，62，79，83，84，96 第11趟：13，15，35，39，41，57，61，62，79，83，84，96 快速排序：41，62，13，84，35，96，57