1、 程序设计方法论方而，提出由顶向下法和自底向上法。使程序模块化，使 问题的复杂性和人的思维统一起来了。 岀现了软件生产管理。磁盘问世，操作系统发展，非数值计算应用发展，通信设备完善，网络发展，集成电路发展等使软件复朵性增加 产生软件危机，在此背景下发展了软件技术。第三阶段：自动程序设计阶段 特点：向集成化、一体化发 展。出现了软件开发环境。程序设计基本方法进一步改进。 硬 件关系：集成电路迅速发展以及高分辨率终端的出现，为个人计算机发展提供了条件，再加上人工智能、专家系统研究的发展，使程序设计进入成熟期。什么是多媒体计算机多媒体计算机包含那几项什么是多媒体计算机1“媒体”的概念分为两部分，其一
2、是信息存储的实体，其二是 表现信息形式的载体；2.多媒体计算机是以计算机为核心，可以综合处理数值计算、文木文件、图形图像、声音视频等多种信息的计算机系统。3.多媒体是20世纪90年代计算机发展的新领域，它是计算机技术与图形图像、动画、声音和视频等领域顶尖技术结合的产 物，它将人机交互的信息从单纯的视觉（文字、图形）扩大 到两个以上的媒体信息B：多媒体的基木要素：文木，图形，图像，动画，音频，视频，可以看出，它是电脑， 电视机，游戏机，录放机，传真机和电话机的综合体第二章常用数据结构及其运算什么是数据结构它对算法有什么影响数据结构是指同一数据对象中各数据元素间存在的关系。数据结构对算法的影响：算
3、法的实现必须借助程序设计语言中提 供的数据类型及其运算。一个算法的效率往往与数据的表达形 式有关，因此数据结构的选择对数据处理的效率起着至关重要 的作用。它是算法和程序设计的基木部分，它对程序的质量影 响很大。2.2何谓算法它与程序有何区别广义地说，为解决一个问题而采取的方法和步骤，就称为“算 法。计算机算法是通过计算机能执行的算法语言来表达的。 和程序的区别：一个程序包括两个方面的内容：（1） 对数据的描述，即数据结构。（2） 对操作的描述，即算法。所以算法是程序的一个要素。何谓频度，时间复杂度，空间复杂度说明其含义。频度：在某个算法中某个语句被重复执行的次数就是此语句的 频度。时间复杂度：
4、是用来估算一个算法的执行时间的量，以算法 中频度最大的语句来度量。空间复杂度：指在算法中所需的辅助空 间的单元，而不包折问题的原始数据占用的空间。试编写一个求多项式Pn =anxn +an-i xn l+aix+ao的值Pn（xo）的算 法，要求用乘法次数最少，并说明算法中主要语句的执行次数及整 个算法的时间复杂度。A=（ao, ai an）ala2a3a4a5a6a7a8a9alOallal2al3al4al58 9 换换换换换换 交交交対蠶 2 10 1119 8 7 4,5,6,7,8,9,4,n-3交换5,n-4交换6,n-5交换交交交如果是偶数个元素，则1,14交换交换2,13交换2
5、, n-1交换3,12交换3, n2交换4,11交换4, n-3交换5,10交换5, n-4交换6,9交换6, n-5交换7,8交换7, n-6交换8,7交换8, n-7交换停止！ ！ 小结：n个元素倒置的算法是, i = lwhile （in-i+l） ai与 an-i+l交换 i+end（while）试编写算法求已知单链表长度，并考虑表空的情况。p = headi = 0While（p!=nil）2.PrQhMcf aPyP；Pnext（p）（p）=EXP（q）:8. x*-COEF（p）+COEF（q）;（x0） then COEF（p）x;pgp next（pre）next（p）; R
6、ET（p） rwxt（pr;uq;qnext（q）;RET（u） （p）EXP（q）:13.u-next（q）;next（q）-p;next（pre）q;pre*-q;q-u（case）（while）（qOnil） then next（pre）*-qfront（hb）*-rrarT2=A*1Tl-B-D厂LEJD/T2TT2/1zqT3L_iFME：A C+T4cT-K*F nT5十TS-e*T4T6-T3T nstack2 stack 1 top2topibottom2bolloni topi Jm;top2l if （topl=top2） then 上.return3.while （top
7、ltop2） do4.if （x mod 2=0） thenRtop2x;top2top2+l5.else Rtopl-x;topl-topl+l （while）有一个二维数组Al:m ；5,假设A3,2地址为1110, A2, 3地址为1115, 若每个单元占一个空间，问Al,4的地址是多少答案：H20用三元组和带行辅助向量形式表示下列的稀疏矩阵：0 0 0 0 0 00 3 0 0 0m0 0 0 0 0 0 0 0 00000000W0S000000OOOOOO0OO0000000000000000H200M020000000000002000 &1S0 0 0 0 0 71 22CD3
8、4 3 6FOS 1 - e 7 7 BINVIVI 3 2h X 2 3 4 SFOS 1 4 7 IO 12行1列85-13926246-S-1-4-126 2 27（21230NUM 3 3将题图的一般树化为二叉树。 答案：设一颗完全二叉数有1000个结点，试问: 有多少个叶子结点500 有多少个度为2的结点499（3）有多少个结点只有非空左子树1设一颗二叉树其中序和后序遍历为 中序：BDCEAFHG 后序：DECBHGFA 答案：ABCDEFHG2. 31对二叉树写出如下算法：（1）复制一棵二叉树；（2）判断两棵二叉树是否相等；（3）计算二叉树的树叶；（4）计算二叉树的深度；解：1）
9、struct TreeElementType Element;Tree *left;Tree *right;int CountLeaf（Tree *T）static int count = 0;if （T != NULL）CountLeaf（T-left）;Cou nt Leaf （T-r igh t）;if （T-left = NULL & T-right = NULL） count+;return count;int Depth（Tree *T）int depthLeft, depthRight, depth;if （T = NULL）return -1;elsedepthLeft = D
10、epth（T-depthRight = Depth（T-right）;depth = 1 + （depthLeft depthRight depthLeft:depthRight）; return depth;给定一组元*17,2836,5430,27,94,15,21,83,40,画出由此生成的二叉排序树。给定一组权值W=82532J7,4，画出由此生成的哈夫曼树。有一图如题图所示：（1） 写出此图的邻接表与邻接矩阵；（2） 由给点VI作深度优先搜索和广度优先搜索;（3） 试说明上述搜索的用途。（1）01001001000000000000 70100000010000000000 0 1
11、0 1 0000000 1 00000000 0101000000001000000 70010100000000000000 /90001010000000100000 0000 1 0 1 00000000 1 000 70000010100000000000 00000001010000000100 01000000101000000000 000000000 1 0 1 000000 1 0 60 100000001010000000 00000000000101000001 6/0010000000010100000 00000 1 0000000 1 0 1 0000 000000
12、00000000101001 0000001000000010100 00000000100000001010 0000000001000000101 00000000000010010010VI作深度优先搜索: U VlO- Vl L Vl 3 T Vl 5- F/6-Vi F/s Vi p V20Vl作广度优先搜索：VVVVVVVVVtVVVhVVVV V13- 门 97 J/ 卩20（3）为了避免同一顶点被多次访问。有一又向图如题图所示：0 2 2 2 1 4 = FC FC Ft FC FC 度度度度度度 出出出出出出（1）写出每一结点的入度和出度各为多少;（2）写出上图的邻接矩阵和邻
13、接表。 解：VI:入度=3V2:入度=2V3:入度寸V4:V5:V6:入度=00 0 0 0 0 0-700100 010001 001010 700000 J 1 0 1 1 0.求题图中结点a到各结点之间最短路径。ab:ac:bd:d*e:b*de*f:eg: 8de8求题图中所示AOV网所有可能的拓扑顺序结果。拓扑排序:V7-V5-V2-V4-V6-V3-V1-V8题图所示AOE网，求：（1）每一事件最早开始时间和最晚开始时间；（2）该计划最早完成时间为多少。活动最早最迟开始时间al al2a2 al3a3 al4E1916202325LL-E10事件最早最迟开始时间VIV2V3V4V5
14、V6V7V9V10VE27VL某校97级同学举办运动会，报名同学学号为97438, 97102, 97528, 97136, 97338, 97250, 97407, 97239, 97227,97517, 97321, 97421, 97451, 97241, 97118, 97543, 97309画出进行分块査找的数据组织形式。971O2 |P7118Q725OS7227 |p72ai 卜297321| Q7436 |w?4O7 | 97421 | 974CL |9751797543加块971369725097338974S1画一棵对20个记录进行对分査找的判定树，并求等概率情况下的平均査
15、找长ASL=（l+2*2+3*4+4*8+5*5）/20=设有10个记录的关键字为ICKES, BARBER, ELYOT, KERN, FRENCE, LOWES, BENSDN, FONK, ERVIN, KNOX。构造a=10/13的哈希表，取关键字首字母表中的序号为哈希函数值，用 随机探测解决冲突，di=（d1+Rj） mod 13, Rj取自伪随机数列：3, 7, 1, 12, 10,。统计该表的平均査找长度ASL。11KNOXBARBERBENSDNELYOTFRENCEERVINICKESKERNLOWESFONKX对于给定的一组关键字 41,62）3,84,35,96,57,3
16、99,61）5,83。分别写出：插入排序.简单选择排序、堆排序、冒泡排序.快速排序、二叉树排序的排序过 程，并对各排序方法进行分析。排序，简单选择排序、堆排序.冒泡排序.快速排序、二叉树排序的排序过 程，并对排序方法进行分析。13 41 62 84 35, 96,57,39, 79,61,15,8313 35 41 62 84 96 57 39 79 61 15 8313 35 41 57 62 84 96 39 79 61 15 8313 35 39 41 57 62 84 96 79 61 15 8313 35 39 41 57 62 79 84 96 61 15 8313 35 39 4
17、1 57 61 62 79 84 96 15 8313 15 35 39 41 57 61 62 79 84 96 8313 15 35 39 41 57 61 62 79 83 84 96对于具有n个记录的文件，要进行n-1趟排序就地排序稳定的排序方法简单选择排序 41, 62, 13, 84, 35, 96, 57, 39, 79, 61, 15, 8341 62 13 84 35 96 57 39 79 61 15 8313 41 62 84 35 96 57 39 79 61 15 8313 15 41 62 84 35 96 57 39 79 61 8313 15 35 41 62
18、84 96 57 39 79 61 8313 15 35 39 41 62 84 96 57 79 61 8313 15 35 39 41 57 62 84 96 79 61 8313 15 35 39 41 57 61 62 84 96 79 83堆排序96, 84, 83, 79, 62, 61, 57, 41, 39, 35, 15, 13冒泡排序 41, 62, 13, 84, 35, 96, 57, 39, 79, 61, 15, 8341,13, 62, 35, 84, 57, 39, 79, 61, 15, 83, 9613, 41, 35, 62, 57, 39, 79, 61
19、, 15, 83, 84, 9613, 35, 41, 57, 39, 62, 61, 15, 79, 83, 84, 9613, 35, 41, 39, 57, 61, 15z 62, 79, 83, 84, 9613, 35, 39, 41, 57, 15, 61z 62, 79, 83, 84, 9613, 35, 39, 41, 15, 57, 61, 62, 79, 83, 84, 9613, 35, 39, 15, 41, 57, 61, 62, 79, 83, 84, 9613, 35, 15, 39, 41, 57, 61z 62, 79, 83, 84, 9613,15,35
20、, 39, 41, 57, 61z 62, 79, 83, 84, 9613,15,35, 39, 41, 57, 61, 62, 79, 83, 84, 96快速排序 41, 62, 13, 84, 35, 96, 57, 39, 79, 61, 15, 8313, 35, 39, 15, 41, 96, 57z 83, 79, 61, 84, 6213,15,35, 39, 41, 96, 57, 83, 79, 61, 84, 6213,15,35, 39, 41, 96, 57z 83, 79, 61, 84, 6213,15,35, 39, 41, 62, 57, 83, 79, 6
21、1, 84, 9613,15,35, 39, 41, 57, 61z 62, 79, 84, 83, 9613,15,35, 39, 41, 57, 61, 62, 79, 84, 83, 96二叉树排序二义树建立过程4141, 6213,41, 6213, 41, 62, 8413, 35, 41, 62, 8413, 35, 41, 62, 84, 9613, 35, 41, 57, 62, 84, 9613, 35, 39, 41, 57, 62, 84, 9613, 35, 39, 41, 57, 62, 79, 84, 9613, 35, 39, 41, 57, 61, 62z 79, 84, 9613,15,35, 39, 41, 57, 61, 62, 79, 84, 96排序方法最好时间平均时间最坏时间辅助空间稳定性直接插入O（n）O（n2）0（n2）0（1）稳定二分插入0（h）希尔O 25）不稳定冒泡0（n）OQ）快速O（nlgn）0（10）直接选择堆归并O（nlgti）基数O
