资源描述：
《软件基础(要点整理).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途软件基础复习要点算法1数据结构的概念数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科2 算法设计基本方法列举法、归纳法、递推、递归、回溯法3算法分析算法的时间复杂度：是指执行算法所需要的计算工作量算法的控件复杂度:是指执行这个算法所需要的内存空间线性表1线性表的概念2线性表的顺序存储结构在计算机中用一组地址连续的存储单元一次存储线性表的各个数据元素，称作线性表的顺序存储结构3双向链表4双链表的(P点）后插入操作(书P29，原问是:双链表的前插入如图2－17)DOＵBＬEＩNSERT(dｌi
2、nｋlist ＊p,ｉnｔ x){dlｉnkｌｉst *ｓ；ﻩｓ ＝(dlｉnkｌiｓt*)ｍalloc(sizｅｏf( dlｉnklｉst));ﻩs-> data= ｘ；ﻩｓ－>ｐrior= p－>nｅxｔ;ﻩs -＞prior= p;ﻩｐ －＞next->ｐrior= ｓ ;ｐ-＞next =s ;}栈1栈的概念及基本运算个人收集整理勿做商业用途２栈的链式存储结构【听录原题】(选择题)ABCＤE进栈,不可能的出栈顺序是？包含下列序列则是错误的：ＣAB，DAB,DＡC,EAB，ＥAC,EAＤ,EBＣ，EBD，包括在这些序列中间加入其它的数都是错误的序列，如
3、CAdB,ＣＡeB等情况(大小更大 中）。队列1 循环队列【听录原题】(无法确定)1) 出栈：puｓhﻩ进栈：pｏp2）求元素个数：rear> ｆｒont ： reaｒ– frontｒｅar<ｆｒoｎｔ:reａr –ｆront＋ＭaｘＳize3) 实现:利用“模”运算入队：rｅar=（reａr+1)ﻩ fronｔ = ( front+１)题:循环队列用数组A[0，m-1]存放其元素值已知其头尾指针分别是fronｔ和reａｒ,则当前队列中的元素个数（A）A(rear– front+m )%mBreaｒ – fｒoｎt+１Creａr-frｏnt–1ﻩﻩＤ ｒｅ
4、ａr－ｆｒont树(40’）１二叉树的形状（P５8）１)二叉树第i层上的结点数最多为2ｉ－1(i>=1)２)深度为 ｋ的二叉树至多有 2k–1 个结点（k ＞＝ 1）3) 在任意一棵二叉树中，若终端结点的个数为ｎ0,度为2的结点个数n2,则n0= n2＋1。证明:因为二叉树中所有结点的度数均不大于２,所以结点总数（记为n)应等于0度结点数、1度结点数(记为n1）和2度结点数之和：ｎ=ｎ０+n１+n２2 二叉树的存储（P6０)顺序存储结构：把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中，结点在这个序列中的相互位置还能反映出结点之间的逻辑关系。题
5、：某二叉树结点采用顺序存储结构如下：(考试题目数据可能会少一些)eａｆ^ｄ^g^＾Ｃj＾^hi^^^^b1)画出该二叉树；个人收集整理勿做商业用途2) 将二叉树还原为森林;（1)（2)(3）（3)(４)（５）3 二叉树的遍历P6３4树和森林与二叉树的转换P６7５ 满二叉树的概念６完全二叉树７二叉树的遍历【听录原题】(填空题、判断题、选择题10’)8二叉树是树的一种，没什么区别９二叉树第ｉ层有多少个结点?２n－110 N个二叉树所有结点之和（套公式)11将一棵有100个结点的完全二叉树编号，则编号为4９的结点，它的双亲的编号为多少?(完全二叉树）(套公式)12
6、二叉排序树，求取平均查找长度(5’）1３画二叉树，树和森林与二叉树的转换(５’)图1拓扑排序ｐ9１ 1) [例6.4]图6-１７ 给出了一个AOV网求拓扑序列的过程。（P9３) 【听录原题】(选择题)图的采用邻接表存储的图的优先遍历类似于二叉树的什么遍历？先序遍历个人收集整理勿做商业用途查找1)图7-9（a)、图7-9(b）所示的树在查找成功时的平均查找长度为:(Ｐ1０８)(考试题目与此题类似，此题非考试原题) ASLa=(1+2 x2 + 3x3)/6＝ 2.3ﻩASＬb = (１+２＋3+4＋5＋6)/6=3．5（a)(ｂ)ﻩ(考题6、题７其中一题)题６
7、、对于给定结点的关键字集合{5，7，3，1，９，6，４,8,2，1０}。(P116)ﻩ１)试构造一棵二叉排序树ﻩ２） 求等概率情况下的平均查找长度ASL题7、对于给定关键字集合K=｛10，18,3,5，19,2，４,9，７，1５}。（Ｐ116)ﻩ1)试构造一棵二叉排序树2）求等概率情况下的平均查找长度ＡSL排序1归并排序p1２82希尔排序p12１3快速排序p124操作系统1分时系统的特征２进程与程序的主要区别1)、“进程”是操作系统的最基本、最重要的概念之一。但迄今为止对这一概念还没有一个确切的统一的描述。下面给出几种对进程的定义描述：1.进程是程序的一次执
8、行;２.进程是可以并行执行的计算；3.进程是一个程序
