搜索
公共基础知识电科三班刘扬•数据结构与算法•软件工程基础•数据库设计基础•程序设计基础数据结构与算法•重点：栈，队列，二叉树，排序与查找•难点：主要集中在二叉树，考核形式包括给出前序，中序遍历，求后序遍历等问题，满二叉树和完全二叉树的结点问题栈限定在一端进行插入与删除的线性表；其允许插入与删除的一端称为栈顶；不允许插入与删除的另一端称为栈底；栈按照“先进后出”或“后进先出”组织数据。•栈的存储方式有顺序存储和链式存储•栈的基本运算：(1)入栈运算(2)退栈运算，删除元素(3)读栈顶元素栈顶栈的输入序列为1,2,3......，n-1，n，输出序列的第一个元素为n，则第i个元素为________A.n-i+1B.n-1C.iD.那个元素都无所谓A假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top执向栈顶元素，如果bottom=49，top=30（数组下标），则栈具有____________个元素（2009.3）元素个数为栈底元素下标—栈顶元素下标+120队列指允许在一端（队尾）进入插入；而在另一端（队头）进行删除的线性表；队列是“先进先出”或“后进后出”的线性表。队列运算包括：(1)入队运算(2)退队运算计算循环队列的元素个数：“尾指针减头指针”，若为负数，再加其容量即可某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有_____个元素。（2008.4）当frontrear时，循环队列中元素的个数为rear-front，当frontrear时，循环队列中元素的个数为（N-front+rear），其中N为循环队列的容量24•（根）节点，子树•叶子：没有后继节点（或终端节点）•分支节点：非叶子节点（或非终端节点）•树的度：树中各节点的度的最大值•节点的层次：根节点的层次为一，其他任何层数等于它的父节点的层数加一•树的深度：节点的最大层次值二叉树的特点：(1)非空二叉树只有一个根结点；(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点,深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。二叉树的性质1.在二叉树的第k层上，最多有2k-1(k≥1)个结点2.深度为m的二叉树最多有2m-1个结点；3.度为0的结点（即叶子结点）总是比度为2的结点多一个，即：n0=n2+14.具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分，具有n个结点的完全二叉树的深度为[log2n]+1深度为5的满二叉树有_____个叶子结点16215-具有88个节点的二叉树，其深度至少为____71][12288lognnlogn至少为个节点的二叉树，深度对于具有某二叉树有5个度为2的结点，则该二叉树中叶子结点的个数为______对于一个非空的二叉树，叶子结点个数＝度为2的结点个数+16二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历：（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。根左右左根右左右根如图，二叉树进行前序遍历的结果为______(2006.4)ABDYECFXZvoidpreorder(bnode*BT){if(BT=NULL)return;else{visit(BT)；if(BT-LC!=NULL)preorder(BT-LC);if(BT-RC!=NULL)preorder(BT-RC);}}查找技术二分法查找：设有序线性表的长度为n，被查找的元素为x，则二分法查找的方法如下：（1）将x与线性表的中间项比较（2）若x的值与中间项的值相等，则说明查到，查找结束（3）若x小于中间项的值，则在线性表的前半部分以相同的方法查找（4）若x大于中间项的值，则在线性表的后半部分以相同的方法查找顺序查找：从表中的的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符查到所要找的元素为止。负责就是表中没有要找的元素，查找不成功。二分法查找只适用于顺序存储线性表，对于无序线性表和线性表的链式存储结构只能用顺序查找有一个有序表{2,4,6,14,34,40,45,62,75,78,82,95，110}，当用二分法查找值为82的结点时，___次比较后能查找成功4intlow，high，mid；mid=(low+high)/2交换类排序法：(1)冒泡排序法，需要比较的次数为n(n-1)/2；(2)快速排序法。插入类排序法：(1)简单插入排序法，最坏情况需要n(n-1)/2次比较(2)希尔排序法，时间复杂度为O(n1.5)次比较。选择类排序法：(1)简单选择排序法,最坏情况需要n(n-1)/2次比较(2)堆排序法，时间复杂度为O（nlog2n）相比以上几种(除希尔排序法外)，堆排序法的时间复杂度最小。排序技术下列排序方法中，最坏情况下比较次数最少的是______（2007.4）A.冒泡排序B.简单选择排序C直接插入排序D.堆排序D软件工程基础•重点：软件工程与软件生命周期的概念，结构化设计方法中的软件设计原理、软件测试与软件调试的概念与方法软件工程概述•计算机软件是计算机系统中与硬件相互依存的一部分，包括程序、数据及相关文档的完整集合•软件按功能可以分为应用软件、系统软件和支撑软件（或工具软件）。例如教务管理系统属于应用软件，操作系统属于系统软件，汇编程序与编译程序属于支撑软件（或工具软件）。软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。简单的说就是使软件走向工程化。软件工程的核心思想是把软件产品看作是一个工程产品来处理。软件工程包括3个要素：方法、工具和过程。软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理。软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境。软件是指______(2007.9)A.程序B程序和文档C算法加数据结构D程序、数据及相关文档的完整集合D软件的生存周期一个软件从用户提出开发要求，到软件在使用中消退的全过程软件的生存周期分为三个阶段：制定计划、开发、运行的维护计划时期:主要任务是分析用户需求，分析软件系统所追求的目标，分析开发系统的可行性开发时期：包括设计和实现两个任务，其中设计包括需求分析和设计两个阶段，实现包括编程和测试两个阶段运行与维护软件的生命周期可分为多个阶段，一般分为定义阶段，开发阶段和维护阶段。编码和测试属于____开发阶段软件测试定义：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别。软件测试的目的：发现错误而执行程序的过程。软件测试方法：静态测试和动态测试。软件测试过程一般按4个步骤进行：单元测试、集成测试、验收测试（确认测试），系统测试软件测试程序设计分为静态分析和动态分析，其中_______是指不执行程序，而对程序文本进行检查，通过阅读和讨论，分析和发现程序中的错误。（2006.4）静态测试：指人工评审软件文档或程序，借以发现其中的错误。动态测试：基于计算机的测试，为了发现错误而执行程序的过程。静态分析动态测试的设计测试实例方法白盒测试法：根据程序的内部逻辑来设计的，主要用于软件的单元测试，主要方法有逻辑覆盖和基本路径测试等黑盒测试法：是对程序功能的测试，主要用于软件的确认测试，主要方法有等价类划分法、边界值分析法和错误推测法。软件测试分为黑盒测试和白盒测试，等价划分法属于_____测试。（2008.9）软件测试可分为黑盒测试和白盒测试，基本路径测试属于_______测试。（2009.3）黑盒白盒程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。程序调试的基本步骤：（1）错误定位；（2）修改设计和代码，以排除错误；（3）进行回归测试，防止引进新的错误。软件调试可分为静态调试和动态调试。主要调试方法有：（1）强行排错法（2）回溯法（3）原因排除法。程序的调试软件设计的基本原理软件设计的基本原理包括抽象，模块化，信息隐蔽和模块独立性模块独立性：是指软件系统中每个模块只涉及软件要求的具体子功能，它和软件系统中的其他模块的接口是简单的。例如，若一个模块只具有单一的功能且与其他模块没有太多的联系，那么称此模块具有模块独立性。模块的耦合性和内聚性是衡量软件模块独立性的两个定性指标耦合性是指模块间互相联系的紧密程度，内聚性是指一个模块内部各个元素间彼此结合的紧密程度。一个设计良好的软件系统应该具有高内聚、低耦合的特征耦合性和内聚性是对模块独立性度量的两个标准。下列叙述正确的是_______(2009.3)A)提高耦合性降低内聚性利于提高模块的独立性B)降低耦合性提高内聚性利于提高模块的独立性C)耦合性是指一个模块内部各个元素间彼此结合的紧密程度D)内聚性是指模块间互相联系的紧密程度B数据库设计基础•重点难点:数据库系统的基本概念，数据独立性，层次模型，关系模型以及E-R图的表示；此外还有笛卡尔积运算、数据库设计方法和步骤在数据库系统中需要对数据进行集中、统一的管理，已达到数据被多个应用程序共享的目标；数据库技术的的根本目标是解决数据的共享问题。数据库系统（DBS）是由数据库(DB)、数据库管理系统(DBMS)、数据库管理人员(人员)、系统平台之一——硬件平台(硬件)，系统平台之二——软件平台(软件)五个部分构成。数据库系统的核心是数据库（DB）数据库系统的基本概念数据库(DB)、数据库系统(DBS)、数据库管理系统(DBMS)之间的关系是____A.DB包含DBS和DBMSB.DBMS包含DB和DBSC.DBS包含DB和DBMSD.没有任何关系C数据库系统的基本特点：数据的集成性、数据的高共享性与低冗余性、数据独立性（物理独立性与逻辑独立性）、数据统一管理与控制。数据的独立性（物理独立性和逻辑独立性）物理独立性：指用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的。也就是说应用程序要处理的是数据的逻辑结构，这样即使当数据的物理存储结构改变了，应用程序也不变逻辑独立性：指用户的应用程序与数据库的逻辑结构是相互独立的，也就是说，数据的逻辑结构即使改变了，用户程序也可以不变。数据独立性分为逻辑独立性和物理独立性，当数据存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为______（2006.9）物理独立性数据库系统的三级模式：（1）概念模式：数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图；（2）外模式：也称子模式与用户模式。是用户的数据视图，也就是用户所见到的数据模式；（3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。在数据库系统中，用户所见的数据模式为_____（2006.9）A.概念模式B.外模式C.内模式D.物理模式B数据模型数据模型可以按照不同的应用层次分为三种类型•概念数据模型：E-R模型、拓展的E-R模型，面向对象模型以及谓词模型等•逻辑数据模型：层次模型，网状模型，关系模型和面向对象模型•物理数据模型E-R模型E-R模型是一种广泛使用的概念数据模型。该模型将现实世界的要求转化为实体、联系和属性等几个基本概念，以及他们之间的两种基本联系，并可以用一种直观图形表示出来。E-R模型的基本元素是实体、联系和属性实体：现实世界中的事物可以抽象为实体，实体是概念世界中的基本单位，它是客观存在的且又能相互区别的事物。属性：现实世界中事物均有一些特性，这些特性可以用属性来表示。属性刻画了实体的特征