软件工程全程班学长

1、 “找学长” 精品课主讲人：黄璜专业课 第13课时南京大学软件学院软件工程 “找学长” 精品课上一课讲了什么？上一课讲了什么？这一课要讲什么？这一课要讲什么？上一课讲了什么？1 “找学长” 精品课 PV操作复习复习这一课要讲什么？2 “找学长” 精品课 数据结构数据结构 “找学长” 精品课 第一章第一章 引论引论递归求n!求数组中的最大值求数组元素的平均值统计叶子结点个数交换左右子树 “找学长” 精品课 第二章第二章 算法分析算法分析1）分析某个语句的执行次数（频度）2）分析某个程序段执行的时间复杂度（用大O表示，要求写出推导过程）例. x = 0; y = 0; for (int i = 1

2、; i = n; i+) for (int j = 1; j = i; j+) for (int k = 1; k 0) if(x100) x -= 10; y-; else x+; 1100次 “找学长” 精品课 第三章第三章 表、栈和队列表、栈和队列表、栈和队列的（基本概念，顺序存储结构，链式存储结构，应用）例. 逆转链表（假设不带表头结点） public void inverse( ListNode f ) if ( f = = NULL ) return; ListNode p = f . link ; pr = NULL; while ( p ! = NULL ) f . link

3、= pr ; pr = f ; f = p ; p = p . link ; f . link = pr ; 中缀到后缀： (a+b)*(c-d)/2*e) ab+cd-2/e* “找学长” 精品课 第四章第四章 树树1.二叉树的定义、性质2.满二叉树与完全二叉树的概念3.二叉树的机内存储：数组表示（完全二叉树）、左-右拉链表示、cursor4.先序、中序、后序遍历（递归、非递归）5.层次遍历（用到队列）6.利用先序、中序可唯一构造一棵树；利用中序、后序可唯一构造一棵树（手绘）7.树的存储方式：广义表表示：a(b(f,g),c,d(h,i,j),e)；双亲表示法；左子女右兄弟表示法 “找学长”

4、 精品课非递归中序遍历 void Inorder(BinaryNode * t) StackBinaryNode* s(10); BinaryNode * p = t; for ( ; ; ) 1) while(p!=NULL) s.push(p); p = p-Left; 2) if (!s.IsEmpty( ) p = s.pop( ); cout element; p = p-Right; else return; “找学长” 精品课preorder:ABDCEGFHIinorder: DBAEGCHFIABCDEFIHG “找学长” 精品课abcdefghijabcdefghij “找

5、学长” 精品课8. 树的遍历：深度优先遍历，广度优先遍历先序次序遍历（先序）：访问树的根 ；按先序遍历根的第一棵子树，第二棵子树，等。后序次序遍历（后序）：按后序遍历根的第一棵子树，第二棵子树，等； 访问树的根。广度优先遍历9.线索树root “找学长” 精品课线索树机内如何存储 一个结点增加两个标记域： leftchild leftthread data rightthread rightchild 0 leftchild 指向左子女 leftThread = = 1 leftchild 指向前驱（某线性序列） 0 rightchild 指向右子女 rightThread = = 1 rig

6、htchild 指向后继 “找学长” 精品课10.霍夫曼树(Huffman Tree)给定权值 15, 03, 14, 02, 06, 09, 16, 17 , 构造相应的霍夫曼树，并计算它的带权外路径长度。思想：权大的外结点靠近根， 权小的远离根。 算法：对权值由小到大排序02,03,06,09,14,15,16,17外径长度:2*5+3*5+6*4+9*3+14*3+15*3+16*2+17*2=229 “找学长” 精品课1. Write a recursive method that returns the number of 1s in the binary representatio

7、n of N. Use the fact that is equal to the number of 1s in the representation of N/2, plus 1, if N is odd.分析：一个n位的二进制数中1的个数等于前n-1位中1的个数加上最后一位中1的个数。例如： count(1010) = count(101) + 0 count(101) = count(10) + 1 count(10) = count(1) + 0 count(1) = 1/递归终止 易知： 1) 一个n位二进制数N的前n-1位组成的二进制数为N/2，例如：101 = 1010/10，

8、10 = 101/10，1 = 10/10； 2) 一个n位二进制正数N的最后一位中1的个数等于N%2。所以：count(N) = count(N/2) + N%2 “找学长” 精品课2. Find the computational complexity of the following four loops:c.For (cnt3=0，i=1;i=n；i*2)for(j=1;j=n;j+)cnt3+;F(n)=2+(log2n+1)(n+(1+n) =O(nlog2n) “找学长” 精品课3.对于下列程序片段，给出运行时间分析（使用大O）1)sum=0;for(i=0; in; i+) f

9、or(j=0; ji*i; j+) for(k=0; kj; k+) sum+; 1022101*0102)1(1)(niniiijjkiinf)()(215101024nOiinini “找学长” 精品课 4. Swap two adjacent elements by adjusting only the links ( and not the data ) using: a. Singly linked lists. b. Doubly linked lists. “找学长” 精品课5. 编写一个非递归方法以O(N)的时间复杂度反转单链表做法1：用堆栈来保存链表的遍历，用pop倒序输出，每倒序输出一个就构造新链表的一个结点。做法2 ：在遍历的过程中碰到结点就先删除然后再插入相同的结点。或者不断的进行插入操作来构造新的链表。做法3 ：在原链表的上用指针操作来进行链表的扭转。 “找学长” 精品课6. 若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（ ） A：dcebfa