软件基础(要点整理)

《软件基础(要点整理)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、软件基础复习要点算法1数据结构的概念数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科2算法设计基本方法列举法、归纳法、递推、递归、回溯法3算法分析算法的时间复杂度：是指执行算法所需要的计算工作暈算法的控件复杂度：是指执行这个算法所需要的内存空间线性表1线性表的概念2线性表的顺序存储结构在计算机屮用一组地址连续的存储单元一次存储线性表的各个数据元索•，称作线性表的顺序存储结构3双向链表4双链表的（P点）后插入操作（I5P29,原问是：双琏表的前插入如图2-17）«—

2、>xDOUBLEINSERT(dlinklist*p,intx){dlinklist*s;s=(dlinklist*)malloc(sizeof(dlinklist));sdata=x;s->prior=p->next;s->prior=p;p->next・>prior=s;p->next=s;)栈1栈的概念及基本运算2栈的链式存储结构【听录原题】（选择题）ABCDE进栈，不可能的出栈顺序是？包含下列序列则是错误的：CAB,DAB,DAC,EAB,EAC,EAD,EBC,EBD,包括在这些序列中间加入其它的数

3、都是错误的序列，如CAdB,CAeB等情况（大小更大中）。队列1循环队列【听录原题】（无法确泄）1）出栈：push进栈：pop2）求元素个数：rear>front:rear-frontrear

4、・front一1Drear・front树（40，）1二叉树的形状（P58）1）二叉树第i层上的结点数最多为2<1（i>=l）2）深度为k的二义树至多有2k-l个结点（k>=l）3）在任意一棵二叉树中，若终端结点的个数为n。，度为2的结点个数n2,则n0=n2+lo证明：因为二叉树中所有结点的度数均不人于2,所以结点总数（记为n）应等于0度结点数、1度结点数（记为山）和2度结点数之和：n=n（）+n1+n22二叉树的存储（P60）顺序存储结构：把二叉树的所冇结点按照一定的线性次序存储到一片连续的存储单元中，结点

5、在这个序列中的相互位置还能反映出结点之间的逻辑关系。题：某二义树结点采川顺序存储结构如下：（考试题口数据町能会少一些）eafAdAgAAcJAAh•1AAAAb1）画出该二叉树;cd2）将二叉树还原为森林;d3二叉树的遍历P634树和森林与二叉树的转换P675满二叉树的概念6完全二叉树7二叉树的遍历【听录原题】（填空题、判断题、选择题10J8二叉树是树的一种，没什么区别9二叉树第i层有多少个结点？2n-l10N个二叉树所有结点之和（套公式）11将一棵有100个结点的完全二叉树编号，则编号为49的结点，它的双亲

6、的编号为多少？（完全二叉树）（套公式）12二叉排序树，求取平均查找长度（5，）13画二叉树，树和森林与二叉树的转换（5J图1拓扑排序p911）［例6.4］图6-17给出了一个AOV网求拓扑序列的过程。（P93）【听录原题】（选择题）图的采用邻接表存储的图的优先遍历类似于二叉树的什么遍历？先序遍历查找1）图7-9（a）、图7-9（b）所示的树在查找成功时的平均查找长度为：（P108）（考试题目与此题类似，此题非考试原题）ASLa=(l+2x2+3x3)/6=2.3ASLb=(1+2+3+4+5+6)/6=3.5

7、(a)（考题6、题7其中一题）题6、对于给定结点的关键字集合｛5,7,3,1,9,6,4,8,2,1（）｝。（P116）1）试构造一棵二叉排序树2）求等概率情况下的平均查找长度ASL题7、对于给定关键字集合K二｛10,18,3,5,19,2,4,9,7,15｝。（P116）1）试构造一棵二叉排序树2）求等概率情况下的平均査找长度ASL排序1归并排序P1282希尔排序pl213快速排序p!24操作系统1分时系统的特征2进程与程序的主要区别1）、“进程”是操作系统的最基本、最重要的概念之一。但迄今为止对这一概念还

8、没有一个确切的统一的描述。下面给出儿种对进程的定义描述：1.进程是程序的一次执行；2.进程是可以并行执行的计算；3.进程是一个程序与其使用的数据在处理机上顺序执行时发牛的活动；4.进程是程序在一个数据集合上的运行过程。它是系统进行资源分配和调度的一个独立单位。2）、进程的特征：动态性：是程序的一次执行；并发性：进程是可以并发执行；独立性：是系统进行资源分配和调度的一个独立单位；异步性：进程间的相互制