软件基础复习重点带答案文库

《软件基础复习重点带答案文库》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、ReviewListforSoftwaretechnologyBasics1、知道系统软件和应用软件的区别。系统软件是指为管理，控制和维护计算机及外设，以及捉供计算机与用户界面等软件系统软件以外的其他软件就是应用软件2、吋间复杂度的计算？知道吋间复杂度与空间复杂度往往是相互矛盾的。3、数据的存储结构有哪四种？P11-P12顺序储存结构链式储存结构索引储存结构散列储存结构4、线性数据结构冇哪些？非线性数据结构冇哪些？线性表，栈，队列，双队列，数组，串。二维数组，多维数组，广义表，树(二叉树等)，图。5

2、、知道循环链表和比非循环链表，可以做到从链表中任何一个节点出发，找到另外的其他任何节点。C语言实现双向链表的删除操作？P27(p->prior)・>next=p->next;(p->next)->prior=p->prior;6、栈和队列的特点？栈和队列用链表存储时分别叫什么？栈：后进先出队列：先进先出链栈链队列循环队列的入队列和出队列操作是如何用C语言实现的？P34-P35先判断是否上溢或下溢，对于循环队列上溢贞fornt==(rear+l)%MAXSIZE)下溢if(fint==rear)入队列

3、reai-(rear+1)%MAXSIZEqueue[rear]=x出队列front=(front+1)%MAXSIZEx=queue[front]采用保留一个空闲位置时，循环队列空和满的判断条件？空：rear==front满：front=(rear+1)%MAXSIZE7、稀疏矩阵的三元组表。P43—P44储存一个高阶系数矩阵时，其每一个非零元素可以用一个三元组(i,j,val)表示，i是彳亍号，j是列号，val是元素8、树的基本概念。知道霍夫曼树(HuffmanTree)可应用于信息通信中。结点

4、的度是指一个结点拥有的子树数目树的深度是指树的最大层次值森林是指M棵互不相交的树的集合二叉树的性质2、性质5。性质2：深度为K的二叉树的结点总数最多为2Ak-l性质5：略如何构造一个序列的二叉排序树？P81设K1是二叉排序树的根，将K（2〜n）与K（1〜n・l）比较，小就插入K（l-n-l）的左边，大就插入它右边怎么样遍历二叉排序树得到的是有序序列？中序遍历知道树（包括二叉树和非二叉树）均可以用二叉链表表示。P57链表中结点的两个指针域分别指向该结点的第一个孩了和下一个兄弟结点能够写出给定二叉树的先

5、序、中序、和后续遍历序列。P53以一棵二叉树说明其三种遍历顺序：9、图的基本概念。图G:V（G）是顶点的非空有限集合玖G）是边的有限集合有向图无向图子图带权图：图的边上冇一根相关联的数连通图：在无向图屮每一对顶点都有路径强连通图：在有向图屮每对顶点都存在V・>U和U・>V的路径图的邻接表唯一吗？不唯一有向图的邻接表能唯一画出该有向图知道构造图的最小生成树可以解决一些实际问题。会写有向图和无向图的邻接矩阵。P63用一维数组储存顶点用二维数组储存边的信息10、操作系统的四个基木特征？P103并行：同时存

6、在若干个止在运行的程序共享：系统的资源可被内存中多个并行执行的进程共同使用虚拟：通过分时使用的方式把物理上的唯一变成逻辑上的多个界步性：操作系统控制下的多个作业的运行顺序和时间是不确定的操作系统的基本功能？P99管理计算机系统屮的各种资源为用户提供良好的界面11、进程存在与否的唯一•标志是？P108PCB（进程控制块）12、四个杳找算法各口是如何实现的？顺序查找折半查找分块查找哈希查找只能适用于有序序列的是哪种杳找算法？折半查找Hash查找会产生冲突吗？能够根据给出的顺序查找算法写出改进的顺序查找算

7、法的C语言程序。会设置监视哨在数组尾增加一个1＜值While（A[i].key!=K）i++13、五个排序算法是什么？直接插入排序简单选择排序冒泡排序快速排序归并排序14、图的深度优先搜索和广度优先搜索遍历。P65（课本例题）自己看15、数据库里而常用数据模型冇哪些？P165目前最常用的是哪个？关系型数据库的标准语言是P187?层次模型网状模型关系模型面向对象模型关系模型SQL16、软件的瀑布模型。P249软件测试有哪两种方法？P277略白盒测试和黑盒测试