计算机二级知识点(一) .pdf

计算机二级知识点（一）

选择题

1.队列元素个数公式：题型一：计算队列的元素个数：(尾－头＋

表长)%表长。

2.队列头指针为front，队列尾指针为rear，队列容量为M，则元

素个数为

|rear-front+M|%M,注意，这个%是求余运算。

设循环队列的存储空间为Q(1:40)，初始状态为front=rear=40，

现经过一系列入队与退队运算后，front=15，rear=15，又正常地退

出一个元素，则循环队列中的元素个数为(39)

Front与rear数值相等，元素不变仍为40(0或40，但该题排除

0)，40-1=39

3.栈元素个数公式：尾-头；S（1：60），初始状态top=61，一

系列出栈入栈后，top=1，

现在栈中元素个数为60

设栈的储存空间为S(1：50)，初始top1=51，经过出栈入栈，

top2=20，则栈中元素个数为：top1-top2=31

变式：……（1：:30），初始top=-1，最后top=30，则栈中元

素个数为30(原来-1+1=0个元素)

《

S(1：m)，初始状态top=m+1，则元素数为m-top+1=0

S(1：m)，初始状态top=-1，则元素数为top+1=0

某带链栈的初始状态为top=bottom=NULL,过一系列正常的入

栈与退栈操作后，

top=bottom=20时，该栈中的元素个数为1,即top指针和

bottom指针共同指向的那个节点中的元素。

不管是顺序栈还是带链的栈，操作过程中栈底指针都是动态变化

的

栈的顺序储存结构中，栈顶指针的动态变化决定栈中元素的个数

在循环队列中，队头指针和队尾指针的动态变化决定队列的长度

4.—

5.线性结构：有且只有一个根节点(有一个根节点的结构，或者只

有一个根节点和叶子节

点的结构不一定是线性结构)；每个节点最多一个唯一前件、后件；

有多个指针域的链表(多重链表)既可能是线性结构，也可能是非线

性结构。

线性结构和非线性结构都可以是空的数据结构

6.结构化程序的根本控制结构：顺序结构，选择结构，循环结构

结构化程序设计原则：自顶向下，逐步求精，模块化，限制使用

goto语句

强调程序的易读性

7.算法：复杂度：时间复杂度(计算工作量)和空间复杂度(内存空

间)；数据的储存结构影

响算法的效率；时间复杂度与运行算法时特定的输入有关

8.·

9.最坏情况下时间复杂度比较：二分查找法O(log2n)<堆排序

O(nlog2n)<希尔排序O<简单

选择排序，冒泡排序，快速排序n(n-1)/2

队列的顺序存储结构一般采用循环队列的形式，查找二分法只适

用于顺序存储的有序表

10.

11.软件：程序，数据和文档的集合

定义阶段任务：可行性研究初步项目计划，需求分析（解决软件

“做什么”的问题）

开发阶段任务：总体设计（解决软件“怎么做”），详细设计，

编码，测试

运行维护阶段：使用，维护，退役

软件测试步骤：单元测试，集成测试，验收或确认测试，系统测

试

,

软件测试用例：输入数据和预期输出结果

分类：应用软件(事务处理软件，财务管理软件)，系统软件(操作

系统，数据库管理系统，编译程序，汇编程序，网络软件等)，支撑软

件(分析工具软件，设计工具软件，编码工具软件，测试工具软件，计

划进度管理软件等)

软件设计建模工具：程序流程图，N-S图，PAD图，HIPO图

软件设计阶段产生的文档：概要设计说明书，详细设计说明书，

设计测试初稿

软件需求分析阶段的文档：需求规格说明书

12.类：是同属性对象的集合，是对象的抽象；

13.面向对象的基本特点：标识唯一性（对象唯一性），分类性，

多态性（同一操作可以是

不同