logo资料库

中科大软件学院复试资料.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.27M 资料格式：doc 举报 版权申诉
第1页 / 共40页
第2页 / 共40页
第3页 / 共40页
第4页 / 共40页
第5页 / 共40页
第6页 / 共40页
第7页 / 共40页
第8页 / 共40页
资料共40页，剩余部分请下载后查看
    软件工程复试总结
    一、数据库部分
    二、数据结构部分
    三、操作系统部分
    四、计算机网络部分
    五、计算机硬件部分
    六、程序语言、软件工程、编译原理
    软件工程复试总结 一、数据库部分 数据库绪论 1、简述三层模式、两级映射，分别有什么作用？ 模式（逻辑模式）：是数据库中全体数据的逻辑结构和特征的描述，是数据库系统模式 结构的中间层，即不涉及数据的物理存储细节，也与具体应用程序开发工具语言无关。 外模式（用户模式）：是用户能看见和使用的局部数据的逻辑结构和特征描述，是与某 一应用有关的数据的逻辑表示，是模式的子集，一个数据库可以有多个外模式。 内模式（存储模式）：数据物理结构和存储方式的描述，是数据在数据库内部的表示方 式，如存储方式是按照某个属性升序存储，什么索引等。 外模式模式映像：当模式发生改变，数据库管理员对外模式模式映像作相应改变，可使 外模式不变，从而应用程序不用修改。保证数据与程序的逻辑独立性。 模式内模式映像：当数据库的存储结构改变了，由数据库管理员对模式内模式映像作相 应改变，可以保持模式不变，从而应用程序也不必改变，保证了数据与程序的物理独立性。 三级模式使用户能逻辑地抽象地处理数据而不关心数据在计算机内具体表示方式与存 储方式，两级映像保证了数据库系统中的数据有较高的逻辑独立性和物理独立性。 2、说出至少三种数据库类型（层次，网状，关系）并简要解释了一下 层次模型：用树形结构来表示各类实体以及实体间的联系，有且只有一个节点没有双亲 节点（根节点），其他的都有且只有一个双亲节点。只能能直接表示的是一对多联系。 优点：效率高结构清晰，性能优于关系数据库，不低于网状。缺点：现实世界很多联系 都不是层次的，如节点间多对多联系，还有一个节点具有多个双亲的情况都不好表示。 网状模型：对于非层次关系的联系，用层次表示非树形结构是很不直接的，网状模型可 以很好的表示，它允许有一个以上的节点没有双亲，一个节点也可以有多个双亲，可以更直 接地描述现实世界。 优点：更直接描述现实世界，性能也较好，存取效率也较高。缺点：结构比较复杂不利 于掌握，用户编程还得了解系统结构细节，加重了编程的负担。 1
    关系模型：通常来看关系就是一张规范二维表，实体还是实体间的联系都用关系来表示， 对数据的检索和更新结果也是关系。 优点：概念单一，用户易懂易用，而且存取路径是对用户透明的，从而有更高的数据独 立性和安全性，也简化程序员的工作。缺点：查询效率往往不如格式化数据模型，为了提高 性能，增加开发 DBMS 难度。 关系数据库 3、简述关系与关系模式的区别。 关系实质是一张二维表，关系模式是对关系的描述，关系是关系模式在某一时刻的状态 或内容。 关系模式是静态的、稳定的，而关系是动态的，随时间不断变化的，因为关系操作不断 更新数据库中的数据。 通俗的说：关系是一张二维表，关系模式是表格的描述（表头），关系名是表名，元祖 是一行，属性是列，分量一条记录中的一个列值。 4、什么是关系数据库？关系和二维表有什么区别？ 关系数据库，是建立在关系数据库模型基础上的数据库，借助于集合代数等概念和方法 来处理数据库中的数据。 在关系模型中，数据结构表示为一个二维表，一个关系就是一个二维表（但不是任意一 个二维表都能表示一个关系。表中的第一行通常称为属性名，表中的每一个元组和属性都是 不可再分的，且元组的次序是无关紧要的。 5、关系的完整性（实体完整性、参照完整性、用户自定义）和数据库主键的约束性 实体完整性：关系的主码不能取空值，如果主码由若干属性组成都不能为空。实体以主 码作为唯一性标识。 参照完整性：一个关系中的外码，或者取空值（若属性组全为空），或者等于它参照的 那个关系的主码值。 用户自定义完整性：针对具体关系数据库的约束。 数据库语言 SQL 6、什么是 DDL、DML、DCL？（数据库语言有哪几种？） 数据定义语言（DDL）：Create、Drop、Alter 数据操纵语言（DML）：Insert、Update、Delete 数据控制语言（DCL）：Grant、Revoke 2
    数据查询语言：Select 7、什么是视图，有什么作用？在数据库哪层？ 视图：是从一个或几个基本表导出的表，是一个虚表，数据库只存放视图的定义，不存 放视图对应的数据，数据仍放在原来的基本表，基本表数据改变，通过视图查询也改变了， 作用：1、能够简化用户操作，使数据库看起来更简单，清晰，简化查询操作。2、更 安全，机密数据不出现在不应该看到这些数据的用户视图上。3、重构数据库时候，改变视 图不用修改程序，使数据具有逻辑独立性。 数据库设计 8、简述数据库设计的几个阶段 需求分析：详细调查现实世界要处理的对象，充分了解各种需求，在此基础确定新系统 的功能。 概念结构设计：经常采用自顶向下需求分析，自底向上概念结构设计。对需求分析收集 到的数据进行分类组织形成实体、实体的属性，确定实体之间联系，设计分 E-R 图。逐一 设计分 E-R 图，最后将所有分 E-R 图综合成一个系统的 E-R 图。 逻辑结构设计：一般来讲把 E-R 图向关系模型转换，一个实体型转换为一个关系模式。 一个一对一联系可以独立也可以和任意一端合并，一个一对多联系可以独立也可以和 N 端 对应的关系模式合并，一个多对多联系独立转换为一个关系模式。对数据模型规范化，还根 据具体需求设计相应的视图。 数据库物理设计：关系模式存取方法的选择，比如索引、聚簇、哈希等存储方式。还应 该确定数据库的存取结构，目前许多计算机有多个磁盘或磁盘阵列，因此可以将表和索引放 在不同的磁盘上，在查询时磁盘驱动器并行工作，可以提高物理 IO 读写效率，也可以将比 较大的表放在两个磁盘上，以加快存取速度。 数据库的实施与维护：比如备份与恢复等待。 9、什么是 E-R 图 E-R 图：实体-联系图，在概念结构设计中，对需求分析收集到的数据进行分类组织形 成实体、实体的属性，确定实体之间联系，设计 E-R 图。 10、分别解释 1NF、2NF、3NF、BCNF、4NF 范式：关系数据库中的关系是要满足一定要求的，满足不同程度的要求的为不同范式。 规范化：一个低一级范式关系模式通过模式分解可以转化为若干个高一级范式的关系模 式的集合。 1NF：满足最低要求的叫第一范式，每一个分量必须是一个不可分的数据项。 3
    2NF：消除关系中的部分函数依赖就称为第二范式，部分函数依赖就是非主属性不完全 依赖于码。 3NF：每一个非主属性既不部分依赖于码，也不传递依赖于码。 BCND：所有非主属性对每一个码都是完全函数依赖，没有任何属性完全依赖于非码的 任何属性，就是除了码外一定不能有决定因素。 数据库并发控制 11、什么是事物，并发控制是保证事物的？ 事物：是一系列的数据操作，这些操作要么全不做，要么全做，不可分割。运行过程中 发生某种故障不能继续执行，全部回滚到开始状态。 并发控制中多个用户存取数据库时候可能会产生多个事物同时存取同一个数据的情况， 不加控制就会破坏事物的一致性，为了保证事物的一致性所以进行并发控制。 12、ACID（事物的四个性质） A 原子性：要么都做，要么都不做。 C 一致性：如果运行中发生故障，必须回滚。不能让数据不一致。比如两人转钱，一半 坏了，不一致俩人都没有钱。 I 隔离性：一个事物不能被其他事物干扰。 D 持续性：事物一旦提交，他对数据库的改变就应该是永久的。接下来的操作和故障不 应该对刚才结果有任何影响。 13、数据库中锁有什么作用？什么是只读锁、什么是只写锁？ 一个事物对数据加锁可以保证事物的四个特性，加锁后其他事物不能更新此数据对象， 不会产生数据不一致性。 写锁（排他锁/ X 锁）：加写锁其他事物不能在对这个数据加任何类型锁，释放之前不能 读取和修改。 读锁（共享锁/ S 锁）：事物对数据加读锁，其他事物可以读但不可以修改，可以加读锁 不能加写锁。 14、什么是触发器，有什么作用？ 用户定义在关系表上的一类由事件驱动的特殊过程，一旦定义了，用户对表的增、删、 改操作均有数据库系统自动激活相应触发器 触发器可以分为语句触发器和行级触发器，触发器动作体是一个匿名 PL/SQL 过程块， 语句级触发器可以在语句执行前或后执行，而行级触发在触发器所影响的每一行触发一次。 4
    行触发器用户可以用 new 和 old 引用数据，语句级不能。 二、数据结构部分 线性表 15、单链表的就地逆置 将头结点摘下，然后从第一节点开始，头插法建立单链表，直到最后一个节点为止。 16、单链表可以用什么实现？ 指向结构体的指针实现，结构体中有两个成员，每个节点分为数据域和指针域，除了最 后一个节点，每个节点指针域都指向下一个节点的地址，最后一个节点指针域指向 NULL。 也可以用结构体数组模拟这种操作，数组中每个下标都对应一个数据元素和游标，游标 是下一个元素在数组中的下标，把未被使用的数组元素作为备用链表，下标为0的元素游标 存放备用链表第一个节点的下标。数组最后一个元素游标存放第一个有效数值元素的下标， 相当于头结点作用，游标为0表示指向为空。 栈和队列 17、实现一个队列的方法？为什么队列的顺序存储需要留一个空位？循环有什么好处？ 链式存储：把链表改装一下，加尾指针作为队列的尾部可以插入节点，头指针可以删除 节点，相当于出队。 顺序存储：正常的顺序存储想要利用空出的空间就必须移动元素，不移动还会浪费空间， 循环队列可以解决这个问题，把这段连续的地址空间，想象成逻辑上的环，所以只要有空闲 空间就能使用。 但是当 front 和 rear 指针相等的时候有两种情况，一种是满，一种是空，为了区分这种 情况，保留一个元素空间，我们假定当 rear+1与 front 相等队列就满了。而空的时候是 rear 等于 front。又因为是环也可能存在 rear>front 的情况，所以取模操作。 另外计算队列长度的时候，rear>front 队长为 rear-front，但当 rear
    19、什么是二叉排序树，简述它的查找过程，二叉排序树的时间复杂度，遍历后得到什么样 的序列？ 二叉排序树是一种二叉树，具有了一些独特性质，若左子树不为空，则左子树上所有节 点的值均小于它的根节点的值，右子树不为空，则右子树上所有节点的值均大于它的根节点 的值，而且它的左右子树也是二叉排序树。构造一个二叉排序树是为了提高动态查找中插入 和删除的速度。 查找过程：递归查找二叉排序树中是否存在要查关键字，若成功则指针指向该数据元素 的节点，返回成功，如果关键字小于树中这个节点，则去它左子树中继续查找，大于则去右 子树中查找。如果树中没有要查的关键字，则指针指向访问的上一个节点，以便于插入。 插入过程：如果当查找失败且指针 p 为空，则新建根节点，如果要插入的关键字小于 p 指向节点的数据，则插入到左孩子，否则右孩子。 删除过程：1叶节点直接删除2只有左或右子树删了接下面3左右子树都有的，找到要删 除的节点的直接前驱或后继，用这个节点替换要删除的节点，然后在删除这个节点。 二叉排序树，以链接的方式存储，有在执行插入或删除操作时候不用移动元素的优点， 插入删除性能较好，而查找的时间复杂度取决与二叉排序树的形状。中序遍历后得到升序系 列，所以也称为二叉排序树。 20、什么是平衡二叉树？ 为了解决二叉查找树，查找时间依赖于形状的问题，平衡二叉树就是在建立二叉排序树 的时候，对它做了一定的限制，使它保持平衡，使每一个节点的左子树和右子树的高度差至 多为1。 具体做法：找出距离插入节点最近且平衡因子绝对值大于一的节点，把它当为根的子树 叫做最小不平衡子树，进行相应旋转，使之平衡。 插入节点：LL 型，向右旋转。RR 型，向左旋转。RL 型，先右转，再左转。LR 型， 先左转，再右转。 21、什么是哈夫曼树？哈夫曼树的作用是什么？ 哈夫曼树：带权路径长度为从该节点到树根之间的路径长度与节点上权的乘积，带权路 径长度 WPL 最小的二叉树称作哈夫曼树。 构造过程：把带有权值的叶子节点按照从小到大的顺序排列成一个有序序列，取出前两 个最小权值的节点作为一个新节点的两个子节点，左孩子一般比右孩子小，新节点权值为两 个叶子的和，将新节点插入刚才有序序列适当位置，重新选出头两个最小的，重复上面过程。 哈夫曼编码：为了解决当年远距离电报的数据传输的最优化问题，发明了哈夫曼编码， 比如多英文文章传输，假设每个字母固定用一个二进制串表示，文章很长那传送的串会非常 长。但英文字母每个字母出现的频率是不一样的，所以可以根据字母频率设定权值，用哈夫 6
    曼树来规划它们，构造哈夫曼树以后，把左分支用0表示，右分支用1表示，然后从根到叶 子所经过的路径的数字用来编码，当双方约定好同样的哈夫曼树后，发送信息的时候能明显 减少串长度。 图的应用 22、什么是有环图，连通图，强连通图？ 连通图：无向图任意两点都是连通的，图中极大连通子图（极大子图还是连通的）成为 连通分量。 强连通图：有向图从 vi 到 vj 和从 vj 到 vi 都存在路径称为强连通图，有向图中极大连通 子图称作强连通分量。 连通图的生成树：是一个极小连通子图，含有图中全部 n 个顶点，但只有足以构成一 棵树的 n-1条边，少于是非连通图，多余必定构成环。 有向树：有向图中一顶点入度为0，其余入度为1 第一个顶点到最后一个顶点相同的路径称为环或回路。序列中顶点不重复出现的路径称 为简单路径，除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单 环。 23、图的存储方式有哪些简要叙述（邻接矩阵和邻接表）？ 邻接矩阵：将顶点和边分别存储，顶点用一维数组存储，边用二维数组。可以根据这个 二维数组获取图中的信息。比如判定两顶点是否有边，只需读取二维数组值。想知道某个顶 点的度就是将这一行的值相加。求他的临界点也只需遍历一行，值为1的就是。无向图的边 数组是对称的，有向图入度看列，出度看行。 邻接表：对于边数较少，顶点较多的图，如果还用邻接矩阵那是对空间的极大浪费，所 以用邻接表，顶点还是一维数组存储，此外数组每一个数据元素还存储指向第一个邻接点的 指针，以便于查找边的信息，图中每个顶点的所有邻接点构成一个链表。边表每个节点存储 这个顶点在顶点表中的下标，和一个指向下一个节点的指针。想知道某顶点的度，就查找这 个顶点的边中节点的个数，要判断是否存在边也只需遍历相应边表。但是对于有向图能得到 每个顶点出度，为了便于确定入度可以再建立一个逆邻接表。 24、什么是 DFS，遍历后形成什么？时间和空间复杂度多少？遍历节点顺序是否唯一？ DFS：图的深度优先遍历，是一种递归过程，是对树的先序遍历的推广，从某个顶点开 始访问，然后对尚未访问的邻接点出发，继续深度优先遍历，直到所有和初始顶点路径相通 的顶点都被访问到。对于非连通图，只需对它的连通分量分别进行 DFS。 BFS：图的广度优先遍历，类似于树的层序遍历，先初始化一辅助队列，从某个顶点开 始访问，访问节点后入队，队列不为空则队列元素出队列，然后判断当前出队列顶点邻接点 7
    是否访问过，没有则访问入队，重复这一过程。 25、什么是迪杰斯特拉算法？ 用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩 展，直到扩展到终点为止。并不是一下子就求出最短路径，而是一步步求他们之间顶点的最 短路径，在这个过程中都基于已经求出的最短路径的基础上。 26、什么是拓扑排序？什么图可以拓扑排序？ 这种用顶点表示活动，用弧来表示活动间的优先关系的有向图叫做顶点表示活动的网络 简称为 AOV 网。通常，在 AOV 网中，将所有活动排列成一个拓扑序列的过程叫做拓扑排 序，而且每个顶点出现且只出现一次，若顶点 a 在序列中排在顶点 b 前面，则在图中不存 在从顶点 b 到顶点 a 的路径。 (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它. (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边. (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止. 判定网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都 出现在它的拓扑有序序列中，则该 AOV 网中一定不存在环。 27、什么是普里姆算法？什么是克鲁斯卡尔算法？ 最小生成树：权值之和最小的那颗生成树称为最小生成树。 普里姆算法：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上” 的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有 n-1条边为止 克鲁斯卡尔：新建一个图 G，G 中拥有原图中相同的节点，但没有边，将原图中所有 的边按权值从小到大排序，从权值最小的边开始，如果这条边连接的两个节点于图 G 中不 在同一个连通分量中，则添加这条边到图 G 中，重复，直至图 G 中所有的节点都在同一个 连通分量中。 28、什么是关键路径？ 用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫 AOE 网。 在项目管理中，关键路径最长的那个路径，决定了整个项目的最短完成时间。把关键路 径上的活动成为关键活动，关键活动影响了整个工程的时间，即如果关键活动不能按时完成 的话，整个工程完成时间就会受到影响。 事件最早发生时间：从开始顶点到下一个顶点最长路径长度。它决定了它后面的活动的 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料