軟件复习资料北京信息科技大学.docx

复习大纲数据结构部分：约占60% 操作系统部分：约占25％数据库部分： 约占15％题型：填空题（包括填空计算题），选择,判断, 程序分析, 简答题, 编程题. 数据结构部分：（约占60%）第一章：软件的概念第二章：算法的评价（算法效率的度量）时间复杂度空间复杂度.常见的几种时间复杂度有：O(1)，O(logn)，O(n)，O(nlogn)，O(n2)，O(n3)，O(2n)，这里，n表示问题的规模。线性表的顺序存储结构：线性表的插入，线性表的删除。线性表的链式存储结构单链表的插入单链表的删除动态建立单链表的算法理解循环链表和双向链表的插入和删除原理。理解栈和队列的含义。进栈算法出栈算法入队算法出队算法队空和队满的条件。第三章：理解： 树，森林，二叉树（平衡，满，完全二叉树等）的定义。掌握二叉树的性质，二叉树的顺序和链式存储结构。掌握二叉树的三种遍历算法。掌握树，森林与二叉树的转换掌握Huffman树（唯一的显示与通信相关的例子）。理解图的存储结构(邻接表，邻接矩阵)，和图的深度和广度遍历算法。能根据深度和广度遍历画出相应的生成树。第4章：查找和排序理解静态查找：顺序查找，折半查找，分块查找理解动态查找（查找允许插入和删除）：二叉排序树查找，Hash查找，会定量计算查找长度（书后习题）。理解Hash表冲突的处理排序理解上述的排序算法，并知道稳定的含义。（稳定的算法处处保持相对次序。而不稳定算法不是处处不保持相对次序。例如快速排序 不稳定 45 36 36*， 排序后为36* 36 45而 45 36 15 36* 排序后为15 36 36* 45（不改变相对次序）。操作系统：约占20%理解虚拟机， 操作系统的功能，操作系统的类型，操作系统的性质。理解进程和程序的区别。理解多道程序的概念。理解进程的性质和状态转换。会利用P,V原语实现简单的进程同步和互斥。理解进程的调度算法。理解死锁的概念，掌握解决死锁的方法。存储器管理：理解虚拟存储器的概念和静态，动态地址映射。理解分区管理的物理意义（固定，可变分区）。理解页式，段式，段页式管理的基本原理。【计算页式的物理地址？】掌握有关缺页率的计算。理解请求页式管理和抖动的概念。设备管理：对SPOOLING技术（虚拟设备的实现）有一定的认识。掌握磁盘调度算法。数据库部分：（15％）理解关系模型（码，元组，属性，关系，域等）理解三级模式及二层映象。主码，外码，参照关系，被参照关系。第七章．理解关系的性质。理解关系的完整性（实体和参照）了解用关系代数查询掌握用SQL语言查询（重点在查询）第8章1NF 2NF 3NFE-R模型与关系之间的转换课堂老师讲解例题1.折半.递归查找2.二叉树左右到子树交换（递归）3.冒泡排序（优化）插入排序4 5.链子（...........）构造一棵二叉排序树，并计算查找成功时的ASL码（平均参考函数 P74）6. 7.给定一个进程地址访问序列（...........）,页面大小为100，绘出页面访问序列（页面缩写从零开始），假设主存块m=2,采用FIFO/LPU，求页面失效率（P130）8.作业不要求全部调度，不要求连续存储空间9.选择题。关键字：固定，可变，不要求连续，可部分装入答案：页式度存10.用pv原理实现简单方案 .11.填空题：E-R模型三要素：实体，联系，属性12.多道程序需要设计中需要硬件支持的：通道，终端13.快捷排序（写出第一次排序后的排序情况，注，其他排序方式一样需要看）14二叉树排序.：给总结点，计算最小高度例：总结点为1000时，最大高度为1000，最小高度为....(见书上公式计算)完全二叉树，码二叉树深度公式：霍夫曼树叶子结点公式(2n-1)（详见书）如果用二叉链表表示，则二叉链有2n个空指针域15.判断题数据完整性包括实体完整性，参照完整性和、、、、、（对）利用二分法查找关键字可以有序可以无序（错，必须为有序）关系的性质......元组顺序可颠倒（对）16.填空题SQL语句中，外模对应视图，内模对应物理存储结构，模对应关系表17.编程题单链表和双向链表的互换（单 双向循环）18.主表长度为144，分12执表，每执表为12，确定块用顺序，求分块平均长度（用顺序查找，折半查找进行计算平均长度）19.用折半法查找关键字，求比较次数课后作业部分习题答案第一次第?2?章?4，7，?8第二次第?2?章?6，?10，?124?头指针，头结点，首元结点（第一个元素结点）头指针是指向链表中第一个结点（头结点或首元结点）的指针；在首元结点之前附设的一个结点称为头结点；首元结点是指链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示表示空表的链表的头指针为空。4---