公共基础知识点.docx

公共基础知识点.docx

《公共基础知识点.docx》由会员分享，可在线阅读，更多相关《公共基础知识点.docx（10页珍藏版）》请在冰点文库上搜索。

公共基础知识点

1..算法的基本特征:

（1）可行性

（2）确定性

（3）有穷性

（4）输入和输出（拥有足够的情报

2.对数据对象的运算和操作

⏹算术运算

⏹逻辑运算

⏹关系运算

⏹数据传输

3一个算法一般可以用顺序、选择、循环三种基本结构组合而成。

4.一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需要的附加存储空间

5.算法的时间复杂度是指算法执行过程中所需要的基本运算次数

算法的空间复杂度是指执行过程中所需要的存储空间

6.算法分析的目的是算法分析的目的是算法的工作量大小和实现算法所需的存储单元多少分别称为算法的

7.数据结构是一门研究数据组织、存储和运算的一般方法的学科。

8.

A.②栈——后进先出

③队列——先进先出

B.顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有以下特点:

1.随机存取。

2.作插入或删除操作时，需移动大量元数。

3.长度变化较大时，需按最大空间分配。

4.表的容量难以扩充。

C.链式存储：

顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有以下特点:

每个节点都由两部分组成：

数据域和指针域。

数据域存放元素本身的数据，

指针域存放指针。

数据元素之间逻辑上的联系由指针来体现。

D.链接存储结构特点：

1.比顺序存储结构多用空间（存储密度小）

（每个节点都由数据域和指针域组成）。

2.逻辑上相邻的节点物理上不必相邻。

3.插入、删除灵活

（不必移动节点，只要改变节点中的指针）。

4.非随机存取。

9.数据结构分为逻辑结构与存储结构，线性链表属于存储结构

数据的存储结构是指数据的逻辑结构在计算机中的表示

数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及数据的存储结构.

数据处理的最小单位是数据项，数据的基本单位是数据元素。

10.线性表的特点：

1.线性表中所有元素的性质相同。

2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继.第一个数据元素无前驱,最后一个数据元素无后继。

3.数据元素在表中的位置只取决于它自身的序号。

11.线性表的顺序存储结构特点：

1.线性表中数据元素类型一致，只有数据域，存储空间利用率高。

2.所有元素所占的存储空间是连续的

3.各数据元素在存储空间中是按逻辑顺序依次存放的

4.做插入、删除时需移动大量元素。

5.空间估计不明时，按最大空间分配。

12.插入算法的分析:

假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：

13.删除算法的分析:

在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：

14.顺序存储方法是把逻辑上相邻的结点存储在物理位置相邻的存储单元中。

15.用链表表示线性表的优点是便于插入和删除操作.

在单链表中，增加头结点的目的是方便运算的实现.

非空的循环单链表head的尾结点（由p所指向），满足p->next=head

循环链表的主要优点是从表中任一结点出发都能访问到整个链表

当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。

这种情况称为上溢。

16..栈——是限定仅在表尾进行插入或删除操作的线性表

队列:

一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。

此种结构称为先进先出（FIFO）表。

17.如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是e2,e4,e3,e1

一些重要的程序语言（如C语言和Pascal语言）允许过程的递归调用。

而实现递归调用中的存储分配通常用栈。

栈通常采用的两种存储结构是链表存储结构和数组

由两个栈共享一个存储空间的好处是节省存储空间，降低上溢发生的机率

18..二叉树的基本性质:

性质1:

二叉树的第i层上至多有2i-1

（i1）个结点。

性质2:

深度为k的二叉树中至多含有2k-1

个结点。

性质３：

对任何一棵二叉树T，如果其终端结点数为n0,度

为2的结点数为n2,则n0=n2+1。

性质４：

具有n个结点的完全二叉树的深度为

二叉链表:

结点包含三个域：

数据域、左、右指针域。

19..

链式存储结构

三叉链表:

结点包含四个域：

数据域、左、右、双亲指针域。

链式存储结构的特点：

（1）操作便于实现

（2）结构复杂

20树是结点的集合，它的根结点数目是有且只有1.

具有3个结点的二叉树有5种形态

21.各种排序方法各有优缺点，故在不同情况下可作不同的选择。

通常需考虑的因素有：

待排序的记录个数；记录本身的大小；记录的键值分布情况等。

•若待排序的记录个数n较小时，可采用简单排序方法。

•若n较大时，应采用快速排序或堆排序。

•若待排序的记录已基本有序，可采用简单插入和起泡

排序。

22.已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是直接插入排序

在最坏情况下，堆排序需要比较的次数为nlog2n

最简单的交换排序方法是冒泡排序

排序是计算机程序设计中的一种重要操作，常见的排序方法有插入排序、交换排序和选择排序等。

要求内存量最大的是归并排序

在待排序的元素序列基本有序的前提下，效率最高的排序方法是冒泡排序

希尔排序属于插入排序

23.程序设计语言的基本成分是数据成分、运算成分、控制成分和传输成分

对象实现了数据和操作的结合，是指对数据和数据的操作进行封装

面向对象的模型中，最基本的概念是对象和属性、行为

子程序通常分为两类过程和函数，前者是命令的抽象，后者是为了求值。

源程序文档化要求程序应加注释。

注释一般分为序言性注释和功能性注释

24软件设计：

包括软件结构设计、数据设计、接口设计和过程设计

25结构化分析方法面向数据流的结构化方法（SA）

面向数据结构Jackson方法（JSD）

面向数据结构的结构化数据系统开发方法（DSSD）

26.软件测试:

静态测试

动态测试：

白盒测试（结构测试）

黑盒测试（功能测试）

27程序调试：

目的：

（１）找出原因和具体的位置．

（２）进行改正，排除错误

调试方法：

（静态、动态调试法）

强行排错法

回溯法

原因排除法（演绎、归纳、二分法）

28.为了提高测试的效率，应该在完成编码以后制定软件的测试计划

软件工程的3个要素:

工具`过程`方法

软件设计包括软件的结构、数据、接口和过程设计，其中软件的过程设计是指系统结构部件转换成软件的过程描述

属于数据流图合法图符的是加工,数据存储,源和流

软件设计原则的是抽象,模块化,信息隐蔽

软件工程的出现是由于软件危机的出现

软件工程研究的内容主要包括：

软件开发技术和软件工程管理。

软件设计模块化的目的是降低复杂性

软件维护活动包括以下几类：

改正性维护、适应性维护、完善性维护，维护和预防性维护。

29．数据库系统的三级模式

（1）概念模式设计者数据全局逻辑要求

（2）外模式反映了用户对数据的要求

3）内模式:

它反映了数据在计算机物理结构中的实际存储形式

30实体完整性规则：

若属性A是基本关系R的主属性，则属

性A不能取空值。

31专门的关系运算：

选择，投影，连接

32.数据库设计：

视图设计：

3种设计次序（自顶向下、由底向上、由内向外）

33数据库管理系统DBMS中用来定义模式、内模式和外模式的语言为DDL

应用数据库的主要目的是解决数据共享问题

在数据库设计中，将E-R图转换成关系数据模型的过程属于逻辑数据阶段

数据独立性最高的阶段是数据库系统，数据库系统减少了数据冗余。

数据库核心是数据库管理系统（DBMS）

索引属于内模式

分布式数据库系统具有的特点：

数据分布性和逻辑整体性，位置透明性和复制透明性，分布性

关系表中的每一横行称为一个元组

34数据库的故障恢复一般是由DBA完成的

数据模型所描述的内容的是数据操作，数据约束，数据结构

在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有特定的数据模型

数据库设计包括两个方面的设计内容，它们是结构特性设计和行为特性设计

相对于数据库系统，文件系统的主要缺陷有数据关联差、数据不一致性和冗余性

数据库系统的是数据库，数据库管理系统，数据库管理员

必须进行查询优化的是关系数据库

35用树形结构来表示实体之间联系的模型称为层次模型

按条件f对关系Ｒ进行选择，其关系运算表示式是σf（R）

数据库管理系统常见的数据模型有层次模型、网状模型和关系模型3种。

数据库设计分为以下6个设计阶段：

需求分析阶段、概念设计

、逻辑设计阶段、物理设计阶段、实施阶段、运行和维护阶段。

数据模型按不同应用层次分成3种类型，它们是概念数据模型、逻辑数据模型和物理数据模型

36关键字ASC和DESC分别表示升序和降序的含义。

数据库系统阶段的数据具有较高独立性，数据独立性包括物理独立性和逻辑独立性两个含义。

数据库保护分为：

安全性控制、完整性控制、并发性控制和数据的恢复。

由关系数据库系统支持的完整性约束是指实体完整性和参照完整性。

关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、参照完整性和自定义完整性。

Strcat（p1,p2）

Strcmp

联合体

。

。

。