公共基础知识点.docx

1、公共基础知识点1. .算法的基本特征: (1)可行性(2)确定性(3)有穷性(4)输入和输出（拥有足够的情报2.对数据对象的运算和操作 算术运算 逻辑运算 关系运算 数据传输3一个算法一般可以用顺序、选择、循环三种基本结构组合而成。4.一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需要的附加存储空间5.算法的时间复杂度是指算法执行过程中所需要的基本运算次数 算法的空间复杂度是指执行过程中所需要的存储空间6.算法分析的目的是算法分析的目的是算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 7.数据结构是一门研究数据组织、存储和运算的一般方

2、法的学科。8.A. 栈后进先出队列先进先出B. 顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有以下特点:1.随机存取。2.作插入或删除操作时，需移动大量元数。3.长度变化较大时，需按最大空间分配。4.表的容量难以扩充。C. 链式存储：顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有以下特点:每个节点都由两部分组成： 数据域和指针域。数据域存放元素本身的数据，指针域存放指针。数据元素之间逻辑上的联系由指针来体现。D. 链接存储结构特点：1.比顺序存储结构多用空间(存储密度小) (每个节点都由数据域和指针域组成)。2.逻辑上相邻的节点物理上不必相邻。3

3、.插入、删除灵活 (不必移动节点，只要改变节点中的指针)。4.非随机存取。9. 数据结构分为逻辑结构与存储结构，线性链表属于 存储结构 数据的存储结构是指数据的逻辑结构在计算机中的表示数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及数据的存储结构.数据处理的最小单位是数据项，数据的基本单位是 数据元素。10. 线性表的特点：1.线性表中所有元素的性质相同。2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继.第一个数据元素无前驱,最后一个数据元素无后继。3.数据元素在表中的位置只取决于它自身的序号。11. 线性表的顺序存储结构特点： 1

4、.线性表中数据元素类型一 致，只有数据域，存储空间利用率高。 2.所有元素所占的存储空间是连续的 3.各数据元素在存储空间中是按逻辑顺序依次存放的 4. 做插入、删除时需移动大量元素。 5. 空间估计不明时，按最大空间分配。12. 插入算法的分析: 假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：13. 删除算法的分析: 在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：14. 顺序存储方法是把逻辑上相邻的结点存储在物理位置 相邻 的存储单元中。15. 用链表表示线性表的优点是便于插入和删除操作 . 在

5、单链表中，增加头结点的目的是方便运算的实现 . 非空的循环单链表head的尾结点(由p所指向) ，满足p-next=head 循环链表的主要优点是从表中任一结点出发都能访问到整个链表 当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为上溢。16. 栈是限定仅在表尾进行插入或删除操作的线性表 队列:一种特殊的线性结构，限定只能在表的一端进行插入，在 表的另一端进行删除的线性表 。此种结构称为先进先出（FIFO）表。17. 如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是e2,e4,e3,e1 一些重要的程序语言(如C语言和Pascal语言) 允许过程

6、的递归调用。而实现递归调用中的存储分配通常用栈。 栈通常采用的两种存储结构是链表存储结构和数组 由两个栈共享一个存储空间的好处是节省存储空间，降低上溢发生的机率18.二叉树的基本性质:性质1:二叉树的第i层上至多有2 i-1（i 1）个结点。性质2: 深度为k的二叉树中至多含有2k-1个结点。性质：对任何一棵二叉树T，如果其终端结点数为n0,度 为2的结点数为n2,则n0=n2+1。性质：具有n个结点的完全二叉树的深度为 二叉链表: 结点包含三个域：数据域、左、右指针域。19. 链式存储结构 三叉链表 : 结点包含四个域：数据域、左、右、双亲指针域。 链式存储结构的特点： （1）操作便于实现

7、（2）结构复杂 20树是结点的集合，它的根结点数目是 有且只有1. 具有3个结点的二叉树有5种形态21. 各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有：待排序的记录个数；记录本身的大小；记录的键值分布情况等。 若待排序的记录个数n较小时，可采用简单排序方法。 若n 较大时，应采用快速排序或堆排序。 若待排序的记录已基本有序，可采用简单插入和起泡 排序。 22. 已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是 直接插入排序 在最坏情况下，堆排序需要比较的次数为 nlog2n最简单的交换排序方法是冒泡排序排序是计算机程序设计中的一种重要操作，常见的排

8、序方法有插入排序、交换排序 和选择排序等。 要求内存量最大的是 归并排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是 冒泡排序希尔排序属于 插入排序23. 程序设计语言的基本成分是数据成分、运算成分、控制成分和 传输成分 对象实现了数据和操作的结合，是指对数据和数据的操作进行 封装 面向对象的模型中，最基本的概念是对象和 属性、行为 子程序通常分为两类过程和函数，前者是命令的抽象，后者是为了求值。 源程序文档化要求程序应加注释。注释一般分为序言性注释和功能性注释 24软件设计：包括软件结构设计、数据设计、接口设计和过程设计25结构化分析方法 面向数据流的结构化方法(SA) 面向数据

9、结构Jackson方法(JSD) 面向数据结构的结构化数据系统开发方法(DSSD) 26. 软件测试:静态测试动态测试：白盒测试（结构测试） 黑盒测试（功能测试）27程序调试：目的：（）找出原因和具体的位置 （）进行改正，排除错误 调试方法：（静态、动态调试法） 强行排错法 回溯法 原因排除法（演绎、归纳、二分法）28. 为了提高测试的效率，应该在完成编码以后制定软件的测试计划 软件工程的3个要素: 工具 过程 方法软件设计包括软件的结构、数据、接口和过程设计，其中软件的过程设计是指 系统结构部件转换成软件的过程描述属于数据流图合法图符的是 加工, 数据存储 ,源和流 软件设计原则的是抽象,模

10、块化, 信息隐蔽 软件工程的出现是由于 软件危机的出现 软件工程研究的内容主要包括：软件开发技术和软件工程管理。 软件设计模块化的目的是 降低复杂性软件维护活动包括以下几类：改正性维护、适应性维护、完善性维护 ，维护和预防性维护。29数据库系统的三级模式 （1）概念模式 设计者数据全局逻辑要求(2)外模式反映了用户对数据的要求 3）内模式 :它反映了数据在计算机物理结构中的实际存储形式 30实体完整性规则：若属性A是基本关系R的主属性，则属 性A不能取空值。 31专门的关系运算： 选择，投影，连接 32.数据库设计：视图设计：3种设计次序（自顶向下、由底向上、由内向外） 33数据库管理系统DB

11、MS中用来定义模式、内模式和外模式的语言为 DDL应用数据库的主要目的是 解决数据共享问题在数据库设计中，将E-R图转换成关系数据模型的过程属于逻辑数据阶段数据独立性最高的阶段是 数据库系统，数据库系统减少了数据冗余。数据库核心是数据库管理系统（DBMS）索引属于内模式分布式数据库系统具有的特点：数据分布性和逻辑整体性，位置透明性和复制透明性 ，分布性 关系表中的每一横行称为一个 元组34数据库的故障恢复一般是由 DBA完成的数据模型所描述的内容的是 数据操作，数据约束，数据结构在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有 特定的数据模型数据库设计包括两个方面的设计

12、内容，它们是结构特性设计和行为特性设计 相对于数据库系统，文件系统的主要缺陷有数据关联差、数据不一致性和 冗余性数据库系统的是 数据库，数据库管理系统，数据库管理员必须进行查询优化的是 关系数据库35用树形结构来表示实体之间联系的模型称为 层次模型按条件f对关系进行选择，其关系运算表示式是f(R) 数据库管理系统常见的数据模型有层次模型、网状模型和关系模型3种。 数据库设计分为以下6个设计阶段：需求分析阶段、概念设计、逻辑设计阶段、物理设计阶段、实施阶段、运行和维护阶段。 数据模型按不同应用层次分成3种类型，它们是概念数据模型、逻辑数据模型和物理数据模型36关键字ASC和DESC分别表示升序和降序的含义。 数据库系统阶段的数据具有较高独立性，数据独立性包括物理独立性和逻辑独立性两个含义。 数据库保护分为：安全性控制 、完整性控制、并发性控制和数据的恢复。 由关系数据库系统支持的完整性约束是指实体完整性和参照完整性。 关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、参照完整性和自定义完整性。 Strcat(p1,p2)Strcmp联合体。 。