二级选择题讲义

计算机二级选择题

不要害怕,不要直接放弃!

目标：至少15・20分

1、公共基础10分（不在于理解，在于掌握做题方法+适当的记忆）

数据结构与算法（5分）

程序设计基础（2分）

软件工程基础（2分）

数据库设计基础（1分）

2、计算机基础知识4分

3、Office6分

6设数据元素的集合D={1,2,3,4,5）,则满足下列关系R的数据结构中为线性结构的是

R=((1,2),⑶2),(5,1),(4,5)}

R={(1,3),(4,1),(3,2),(5,4))

R={(1,2),(2,4),(4,5),(2,3)}

R={(1,3),(2,4),(3,5),(1,2))

计算机二级公共基础

第一章数据结构与算法

一、算法

算法是指解题方案的准确而完整的迤述。算法不等于程序,也不等于计算方法。程序的编

制不可能优于算法的设计。

比如：旅游（先规划一再实施）

比如：在3,6,8,4,5里面找出最大数

编程完成问题：在一无序数据系列中找出最大数（n个数）:

算法：用第一个数和第二数比较，取较大数；

用这个较大数和下一个数比，取较大数;

经过以上步骤n步，获得最大数。

程序：

#include<stdio.h>

voidmain()

(

inta[4],i,m;

scanf("%d",&a[0]);

m=a[0];

for(i=l;i<4;i++)

(

scanf("%d",&a[i]);

if(a[i]>m)

m=a[i];

printf("Themaxnumberis%d",m);

)

2、算法的基本特征

(1)可行性。

(2)确定性。每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的

一条执行路径，即相同的输入只能得出相同的输出。

(3)有穷性。算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有

限个，二是每个步骤都能在有限时间内完成。

(4)拥有足够的情报。

3、算法复杂度主要包括时间复杂度和空间复杂度。两个之间没有直接联系。

(1)算法时间复杂度是指执行算法所需要的吐复建量，可以用执行算法的过程中所需

基本运算的执行次数来度量。

(2)算法空间复杂度是指执行这个算法所需要的内底空回。

4、设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。

基本运算包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

练习

【1】、算法的有穷性是指（）。

A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的

C）算法程序的长度是有限的D）算法只能被有限的用户使用

正确答案：A

【解析】：有穷性是指算法程序的运行时间是有限的。

【2】、算法的空间复杂度是指（）。

A）算法在执行过程中所需要的计算机存储空间

B）算法所处理的数据量

C）算法程序中的语句或指令条数

D）算法在执行过程中所需要的临时工作单元数

正确答案：A

【解析】：算法的空间复杂度是指算法在执行过程中所需要的内存空间。

[3]、下列关于算法叙述正确的是（）。

A）算法就是程序

B）设计算法时只需要考虑数据结构的设计

C）设计算法时只需要考虑结果的可靠性

D）以上三种说法都不对

正确答案：D

【解析】：算法是指解题方案的准确而完整的描述，算法不等于程序，也不等于计算方法，所以A错

误。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。

【4】、下列叙述中正确的是（）

A）一个算法的空间复杂度大，则其时间复杂度也必定大

B）一个算法的空间复杂度大，则其时间复杂度必定小

C）一个算法的时间复杂度大，则其空间复杂度必定小

D）算法的时间复杂度与空间复杂度没有直接关系

正确答案：D

【解析】：算法的空间复杂度是指算法在执行过程中所需要的内存空间，算法的时间复杂度，是指执

行算法所需要的计算工作量，两者之间并没有直接关系，答案为D。

[5]、下列叙述中正确的是（）

A）算法的效率只与问题的规模有关，而与数据的存储结构无关

B卜算法时间复杂度是指执行算法所需要的计算工作量

C）数据的逻辑结构与存储结构是一一对应的

D）算法的时间复杂度与空间复杂度一定相关

正确答案：B

【解析】：算法的效率与问题的规模和数据的存储结构都有关，A错误。算法的时间复杂度，是指执

行算法所需要的计算工作量，B正确。由于数据元素在计算机存储空间中的位置关系可能与逻辑关系

不同，因此数据的逻辑结构和存储结构不是一一对应的，C错误。算法的时间复杂度和空间复杂度没

有直接的联系，D错误。

难度提升:

■•下列叙述中正确的是

«

算法的时间复杂度与算法程序中的语句条数成正比10下列叙述中错误的是

®算法的时间复杂度与运行算法时特定的输入有关®对于各种特定的输入，算法的时间复杂度是固定不变的

算法的时间复杂度与算法程序编制者的水平有关算法的时间复杂度与使用的计算机系统无关

算法的时间复杂度与计算机的运行速度有关算法的时间复杂度与使用的程序设计语言无关

ID:56488算法的时间复杂度与实现算法过程中的具体细节无关

，如要查找的数据恰好是人

第1个元素，只需比较1次

；如要查找的数据是最后

一个元素，贝M个额据需要

比较n次。2

□标记

二、数据结构

1、数据结构的基本概念

a、数据：如声音、视频、文字、图像；学校的学生信息、公安部门的公民信息、银行的存款信息

b、数据结构：是指相互有关联的数据元素的集合。

c、数据结构研究三个方面的问题：

逻辑结构：就是各数据元素之间的前后件关系。可以理解为图纸上画出来的关系图（线性结构、非线性结构）

存储结构：各数据元素在计算机中的存储关系，即数据的存储结构。数据的存储结构有顺序、链式、索引等。

对各种数据结构进行的运算：直找、排序、删除、插入等

同一种逻辑结构的数据可以采用不同的存储结构，但影响数据处理效率。

春夏秋冬

按顺序在9个房间里面找到9颗龙珠，即可打开大宝藏。

一、顺序存储

•••••••••宝藏

12345678910

二、链式存储

123456789101112131415

数据域指针域

datanexta——aaA

Q）结点结构仆）一个非空的线性链表示意图

AT族TCI》I篇

三、索引学生信息登记表

班级名称学号姓名身份证号出生日期家庭住址

有一个索引表13级旅管1201301020001陶欣'5001234567890919281994/1/18重庆大足

13级旅管1201301020002刘灵'5109808765243512341995/7/12重庆梁平

13级旅管1201301020003常志明,4009875628191018281991/9/17湖北利川

13级旅管1201301020004蒋顺"5120192837464525491994/6/7湖北咸丰

13级旅管1201301020005张宇澄'5139817591747293081994/7;8重庆永川

13级旅管1201301020006赵小矛'4092716486234508121994/8/1重庆南川

13级旅管1201301020007惇二说下色限5151234567898765431993/6/1重庆垫江

13级旅管1201301020008白敏'5030548971239876511994/11/14重庆酉阳

13级旅管1201301020009杨婷婷'5059827465892097611994/10/13重庆黔江

13级旅管1201301020010税正芳'4149873645789012871995/4/1四川泸州

13级旅管1201301020011傅茂竹,4567891234987659321994/3/10重庆万盛

13级旅管1201301020012陈建英'5061239876543212111993/3/24重庆石柱

栈

三、数据结构（逻辑结构）分为两大类型：线性结构和非线性结构。

（1）线性结构（非空的数据结构）条件：

1）有且只有一个根鲤;（在数据结构中，没有前件的结点称为根结点。）

2）每一个结点最多有一个前件，也最多有一个后件。

常见的线性结构有线返和线性链表等。

（2）非线性结构：不满足线性结构条件的数据结构。

*：常见的非线性结构有树、二叉树和网等。

【1】、下列叙述中正确的是（）。

A）有一祁上根结点的数据结构不一定是非线性结构

B）只有一个根结点的数据结构不一定是线性结构

28下列叙述中正确的是

有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构

有且只有一个根结点的数据结构一定是线性结构

有且只有一个根结点的数据结构一定是非线性结构

每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构

四、线性表（逻辑结构）

1.1）有且只有一个根结点；2）每一个结点最多有一个前件，也最多有一个后件。

学生1学生2学生3学生4学生5

线性表可能是空表

2、存储方式：顺序存储方式和链式存储方式。

245,9,8

24598

线性表的顺序存储结构具有以下两个基本特点：

(1)线性表中所有元素的所占的存储空间是连续的；

(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

245,9,8

245

3、线性表的插入、删除，直找(直找某个数和查找最大数、最小数)运算

顺序存储、和链式存储

24598

结论：1、在插入删除操作里面，顺序存储要移动数据，链式存储不移动数据，链式存储

优于顺序存储，顺序存储插入、删除运算不方便。

2、在长度为n的线性表中，查找某个数最坏情况下需要查找n次；

3、在长度为n的线性表中，找到最大数（或者最小数）需要比较n-1次

■@下列关于线性链表的叙述中，正确的是

■o进行插入与删除时，不需要移动表中的元素

Io各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续

Ic各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致

下列叙述巾正确的是

线性表链式存储结构的存储空间一般要少于顺序存储结构

线性表链式存储结构与顺序存储结构的存储空间都是连续的

线性表链式存储结构的存储空间可以是连续的，也可以是不连续的

28下列叙述中正确的是

有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构

o有且只有一个根结点的数据结构一定是非线性结构

o有且只有一个根结点的数据结构一定是线性结构

o每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构

41下列叙述中正确的是

顺序存储结构能存储有序表，链式存储结构不能存储有序表

O链式存储结构比顺序存储结构节省存储空间

顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的

O顺序存储结构只针时线性结构，锌式存储结构只针时非线性结构

2线性表的长度为n。在最坏情况下，比较次数为n-l的算法是

®寻找最大项

O有序表的插入

O同时寻找最大项与最小项

O顺序查找

5在线性表的链式存储结构中，其存储空间一般是不连续的，并且

前件结点的存储序号小于后件结点的存储序号

@前件结点的存储序号可以小于也可以大于后件结点的存储序号

前件结点的存储序号大于后件结点的存储序号

答案:BID:56405

t解析】链式存储结构使人

得节点在内存中不受位置

的限制，结点存储号可以

是任意的，并且能够保证

逻辑上的线性关系。故前

□标记

五、栈

定义：栈是限定在一端进行插入与删除运算的线性表。（栈是线性结构）

在栈中，允许插入与删除的一端称为栈顶（top）---移动的，变化的，不允许插入与删除

的另一端称为栈底（bottom）（栈底固定不变）。栈是按照〃先进后出〃或“后进先出〃

的原则组织数据的。

正栈

1、把2,3,1,5,6,8入栈再出橇p6

2、空栈:top<bottom5

初始状态或者

top=-l04

3、满栈:top达到最大值

3

4、计算栈中元素个数：

2

Top-Bottom+1

<—Bottom1

大-小+1

0

【1】、下列关于栈的叙述正确的是（）。

A）栈按“先进先出"组织数据B）栈按“先进后出”组织数据

C）只能在栈底插入数据D）不能删除数据

正确答案：B

[2]、一个栈的初始状态为空。现将元素，2、3、4、5、A、B、C、D、E依次入栈，然后再依

次出栈，则元素出栈的顺序是（）。

A）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA

正确答案：B

【6】、下列关于栈叙述正确的是（）。

A）栈顶元素最先能被删除B）栈顶元素最后才能被删除

C）栈底元素永远不能被删除D）栈底元素最先被删除

正确答案：A

【7】、下列叙述中正确的是（）。

A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化

B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化

C)在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化

D)以上说法均不正确

正确答案：C

[8]、设栈的存储空间为s(l:50),初始状态为top=-l.经过一系列正常的入栈与退栈操作后,

top=30,则栈中元素个数为：

a:30b:19c:31d:20

技巧：本例中用top初始值来判断为一个正栈。

1、把2,3,1,5,6,8入栈再出栈

2、空栈：初始状态

<—Bottom

Top=m+1

3、满栈Top

4、计算栈中元素个数：

botton-Top+1

大-小+1

假设用一个长度为50的数组（数组元素的下标为。到49）作为栈的存储空间，栈底指

针bottom指向栈底元素，栈顶指针指向栈顶元素，如果bottom=49,top=30,则栈

中有（）个元素

综合举例：三、29、31

四、28、41、46、49

五、45、46、48

带链栈:

1、带链栈空的条件是：top=bottom=NULL,如果top=bottom且不为NULL,说

明有一个元素。

2、带链栈不会溢出（不会满栈）

五、40、49、53、54、55

小结：

1、先进后出FILO;

工、支持子程序调用；

[9]、支持子程序调用的数据结构是（）。

A）栈B）树C）队列D）二叉树

正确答案：A

2、具有记忆功能；

3、可以不用顺序存放数据；

4、只能够在top首部进行操作，bottom是绝对不动的;

5、栈的存放数据的个数为：大-小+1；

六.队列（线性结构）

Front

普通队列

012345678

t

2,5,7,1,8

Rear

队列是指允许在一端（队尾）进行插入，而在另一端（队头）出仃恻除的线性表。

1、Rear指针指向队尾,front指针指向队头。

2、先进先出FIFO,或者是后进后出LILO

2,57,1,8入队出队

3、队列可以是顺序存储结构，也可以是链式存储结构。

4、右图18（队列-作业调度）

5、带链队列空的条件是：top=bottom=NULL,如果top=bottom且不为NULL,说

明有1个元素。

18下列与队列结构有关联的是

21下列叙述中正确的是

先到先服务的作业调度

@带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针多重循环的执行

带链队列的存储空间可以不连续，但队头指针必须小于队尾指针

数组元素的弓I用

带链队列的存储空间可以不连续，但队头指针必须大于队尾指针

函数的递归调用

-X循环队列

B、rear<front的时候,num=rear-front+n;（n为容量）

C、rear二front的时候，循环队列可能为满，可能为空

2、循环队列中的元素个数随队头指针与队尾指针的变化而动态变化

3、循环队列是队列的一种顺序存储结构。（循环队列不能使用链式存储结构，而一般的队

列是可以使用链式存储结构的）

9下列叙述中正确的是

循环队列是队列的一种链式存储结构

循环队列是队列的一种顺序存储结构

O循环队列是非线性结构

循环队列是一种逻辑结构

练习：第一部分：4,9,12,18,21,42,44,48

第二部分:2,7,14,21,22,25,28,33,41,44

第三部分:10,14,16,22,24,35,39

第四部分：31,35

第五部分：8,13,16,44,50,51,70（由于软件升级，红色部分到第6部分去了。第

5部分的题库顺序发送了变化，请大家做第5部分和第6部分里面队列的题）

七树与二叉树（非线性结构）

一）树

1、树是一种简单的非线性结构，所有元素之间具有明显的层次特性。［1题】

2、在树结构中，没有前件的结点只有一个，称为树的根结点，简称树的根。

3、每一个结点可以有多个后件，称为该结点的子结点。

4、没有后件的结点称为叶子结点。叶子节点的度为0

5、在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的

度称为树的度。树的最大层次称为树的深度。

重点掌握的：根、叶子结点、度、

树的度、树的深度

*6、一棵树的结点数=结点个数*结点度数+1

।21设一棵度为3的树，其中度为2,1,0的结点数分别为3,1,6。该树中度为3的结点数为

.o1

O3

O不可能有这样的树

2

二）二叉树的特点：

1、非空二叉树只有一个根结点；

2、每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

e

EF

3、二叉树的基本性质：必考的题目

(1)在二叉树的第k层上，最多有21(kN1)个结点；

(2)深度为k的二叉树最多有2«<-1个结点；

(3)度为0的结点(即叶子结点)总是比度为2的结点多一个；【2题】

二叉树中二叉树节点的度只能为【、、题】

(4)n=n0+ni+n2(0,1,2)345

4、满二叉树

是指除最后一层外，每一层上的所有结点1有两个子结点，则k层上有个结

点深度为k的满二叉树有2k-1个结点。

5、完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只

缺少右边的若干结点。完全二叉树中度为1的结点数为。或者1个。【6、8题】

满二叉树I完全二叉树完全二叉树

非完全二叉树非完全二叉树

[1]、下列数据结构中，属于非线性结构的是（）O

A）循环队列B）带链队列C）二叉树D）带链栈

正确答案：C

【2】、某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（）。

A）10B）8C）6D）4

正确答案：c

【3】、一棵二叉树共有25个结点，其中5个是叶子结点，则度为工的结点数为（）

A）16B）10C）6D）4

正确答案：A

[4]、某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在

第1层）（）o

A）3B）4C）6D）7

正确答案：D

【5】、一棵二叉树中共有80个叶子结点与70个度为1的结点,则该二叉树中的总

结点数为()

A)219B)229C)230D)231

正确答案：B

【6】、深度为7的完全二叉树中共有125个结点则该完全二叉树中的叶子结点数为

()。

A)62B)63C)64D)65

正确答案：B

【解析】：深度为k的完全二叉树最多有2匕1个结点，第k层最多有2皿个结点。前6

层总共结点数=2A6-1=63,这里总共有125个，所以第7层有125-63=62个。

另外，第6层32个。所以叶子结点数二第6层叶子结点(第7层62个结点需要31

个结点发出左右子树，只有一个结点没有左右孩子)+第7层叶子结点(该层所有结点

为叶子结点)=1+62=63

【7】、下列叙述中正确的是（）。

A）结点中具有两个指针域的链表一短三叉藤

B）结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构

C）二叉树只能采用链式存储结构

D）循环链表是非线性结构

正确答案：B

【8】、一棵完全二叉树共有360个节点，则在该二叉树中度为1的结点个数为：

a）181b）0c）180d）l

正确答案：d

习题

一部分:16、22、26、35、49

二部分:1、11、16、32、40、46、48

三部分：4、7、13、17、20

四部分:21、40五部分:1、2、7、49六部分:23

=）二叉树的遍历

1、二叉树存储结构一般采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行

顺序存储。

2、二叉树的遍历：（一般画个图要你把顺序写出来）

（1）前序遍历（根左右），首先访问根结点，然后遍历左子树，最后遍历右子树；

（2）中序遍历（左根右），首先遍历左子树，然后访问根结点，最后遍历右子树；

（3）后序遍历（左右根）首先遍历左子树，然后访问遍历右子树，最后访问根结点。

前序：123

中序:213

后续：231

[1].对下列二叉树进行前序遍历的结果为（）

A)DYBEAFCZXB)YDEBFZXCAC)ABDYECFXZD)ABCDEFXYZ

练习：第三部分：44、45、46

前序：ABDYECFXZ

中序：DYBEAFCZX

后续：YDEBFZXCA

3、通过其中两个遍历，推导出另外一个遍历

方法：找根然后分左右

步骤：a、前序后序确认根;（前序中第一个节点是根，后续中最后一个节

点是根）

B.中序确认左右；（确定根后，用中序确定左右树）

3设某二叉树的前序序列为ABC,中序序列为CBA,则该二叉树的后序序列为

BCA

CAB

CBA

ABC

6设某二叉树的后序序列为CBA,中序序列为ABC,则该二叉树的前序序列为

ABC

CBA

BCA

CAB

19某二叉树的前序序列为ABCDEFG,中序序列为DCBAEFG,则该二叉树的深度（根结点在第1层）为

O3

O5

O4

O2

«

某二叉树的前序序列为ABCDEFG,中序序列为DCBAEFG,则该二叉树的后序序列为

DCBGFEA

DCBEFGA

BCDGFEA

EFGDCBA

30）设二叉树的后序序列与中序序列均为ABCDEFGH,则该二叉树的前序序列为

DCBAHGFE

HGFEDCBA

ABCDEFGH

EFGHABCD

ABCDHGFE

某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH。该完全二叉树的前序序列为

ABCDEFGH

ABDHECFG

HDEBFGCA

HDBEAFCG

练习:二部分:3、6、19、23、29、42、50

三部分：1、30、34、43、44、45、46

四部分：1、11、12、13-18.32、36、47

六部分:9、12、17、19

八、数据结构补遗

1、线性表

数

士

构

据

设\

B-RRJ其

口-Z

{bcef}

，JJ

DM={d,bVX

a,MgI

Z(a,/

该,d,d)

士

数(e,e)

(f据

a)构¥

口/

线性结构

非线性结构

循环链表

循环队列

3、堆

Z131下列各序列中不是堆的是

答案:BID:56380O(91,85,53,36,47,30,24,12)

大根雄，所有节点的值大A(47,91,53,85,30,12,24,36)

于或等于左右子结点的值O

；小根堆，所有节点的值

小于或等于左右子结点的O(91,85,53,47,36,30,24,12)

值。v

(91,85,53,47,30,12,24,36)

□标记

下列叙述中错误的是（）。

。向量是线性结构

O非空线性结构中只有一个结点没有前件

O非空线性结构巾只有一个结点没有后件

⑥只有一个根结点和一个叶子结点的结构必定是线性结构

1）下列数据结构中，不能采用顺序存储结构的是（）。

⑥非完全二叉树

。堆栈

。队列

练习：三部分：18

九1、查找技术

1、顺序查找的使用情况：

长度为n的线性表，找出一个数据，最坏的情况为比较n次。

长度为n的线性表，找出一个最大（最小）数据，最差的情况为比较n-1次。

2、二分法查找只适用于顺隹僮的有序表：5,8,10,26,34,76

二分查找：对于长度为n的有序线性表，最坏情况只需比较log2n次。

4在长度为97的顺序有序表中作二分查找，最多需要的比较次数为（）。

06

096

048

07

十、排序技术

1、排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。

2、冒泡排序、快速排序、简单插入排序、选择排序，最坏情况下需要比较

n（n」）/2次

希尔排序法，最坏情况需要0（n15）次比较。

堆排序法，最坏情况需要O(nlog2n)次比较。

3、排序最坏情况下时间复杂度最小(排序的次数)的是堆排序。

n(n-1)/2>n15>nlog2n

4、已经学习的算法时间复杂度关系

n(n-1)/2>n15>nlog2n>n>n-l>log2n

【工】、对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为()

A)9B)10C)45D)90

【2】、对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-l)/2的排序方法

是()

A)快速排序B)冒泡排序C)简单插入排序"""D)堆排序

正确答案：D

【3】、堆排序最坏情况下的时间复杂度为()。

15

A)0(n)B)O(nlog2n)C)O(n(n-l)/2)D)O(log2n)

正确答案：B

【4】、对长度为n的线性表排序,在最坏情况下,比较次数不是n(n-l)/2的排序方

法是()。

A)快速排序B)冒泡排序C)直接插入排序"""D)堆排序

正确答案：D

【5】、下列排序方法中，最坏情况下比较次数最少的是()。

A)冒泡排序B)简单选择排序"""C)直接插入排序"""D)堆排序

Q）在希尔排序法中，每经过一次数据交换后（）。

15设表的长度为n。在下列结构所时应的算法中，最坏情况下时间复杂度最低的是

o只能消除一个逆序

循环链表中寻找最大项

。能消除多个逆序

O堆排序

。不会产生新的逆序

有序链表查找

。消除的逆序个数一定比新产生的逆序个数多

希尔排序

正确答案：B

答疑；在希尔排序过程中，虽然对于每一个子表采用的仍是插入排序

排序过程的性能。故答案为B。

38下列算法中，最坏情况下时间复杂度最低的是

■®有序表的对分查找

Io堆排序

Io寻找最大项

Io顺序查找

练习：

一部分:8、23、27、32、43

二部分：10

三部分:15、33、42、48、49、50

四部分：3、4、5、22、25

五部分:9、10、11、12、13、14、17（不要求X18（不要求X19

六部分:1、2、5、7、15,18、29、33、38

第二章程序设计基础

一、程序设计设计方法和风格

1、注释分序言性注释和功能性注释；

2、语句结构清晰第一、效率第二；程序一定要求具有易读性，可读性较好。

3、程序设计方法有两种：结构化程序设计和面向对象程序设计。

二、结构化程序设计

结构化程序设计方法的四条原则是：考试重点都要背下来

1.自顶向下；

2.逐步求精；

3.模块化；

4.限制使用goto语句。

结构化程序的基本结构和特点：

(1)顺序结构

(2)选择结构：又称分支结构

(3)循环结构(重复结构)

三、面向对象的程序设计

1、对象由对象名、属性和操作(方法)三部分组成。

属性即对象所包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。

2、面向对象基本概念：

•对象

•类和实例：类是指具有共同属性、共同方法的对象的集合。类是对象的抽象，

对象是对应类的一个实例。

•消息：消息是一个实例与另一个实例之间传递的信息。

•继承：继承是指能够直接获得已有的性质和特征，而不必重复定义他们。类之

间共享属性和操作的机制。

•多态性：多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的

现象

3、对象的基本特点：

(1)标识惟一性；

(2)分类性；

(3)多态性；

(4)封装性；

(5)模块独立性好。

4、面向对象方法的优点：

(1)与人类习惯的思维方法一致；

(2)稳定性好；

(3)可重用性好；

(4)易于开发大型软件产品；

(5)可维护性好。

【1】、在面向对象方法中，不属于〃对象〃基本特点的是（）。

A）一致性B）分类性C）多态性D）标识唯一性

正确答案：A

【2】、面向对象方法中，继承是指（）。

A）一组对象所具有的相似性质B）一个对象具有另一个对象的性质

C）各对象之间的共同性质D）类之间共享属性和操作的机制

正确答案：D

【3】、下列选项中属于面向对象设计方法主要特征的是（）。

A）继承B）自顶向下C）模块化D）逐步求精

正确答案：A

【4】、下面对对象概念描述正确的是（）

A）对象间的通信靠消息传递B）对象是名字和方法的封装体

C）任何对象必须有继承性D）对象的多态性是指一个对象有多个操作

正确答案：A

【5】、面向对象方法中，实现对象的数据和操作结合于统一体中的是（）。

A）结合B）封装C）隐藏D）抽象

正确答案：B

【6】、定义无符号整数类为Ulnt,下面可以作为类UInt的实例化值的是（）。

A）-369B）369C）0.369D）整数集合{1,234,5}

正确答案：B

练习：

一部分:12,18,30

二部分:1,21,47,48,49,50,

三部分:1,2,4—13,16,22,23,36,37

四部分：3,6,7,12,18,22,32,36,37,40,43,46,51,52,53,54,55,56,57,58

第三章软件工程基础

一、软件工程基本概念

1、软件工程是用工程、科学和数学的原则和方法研制，维护计算机软件的有关技术及管理方法。

软件是包括程序、数据及相关文档的完整集合。

2、软件的特点包括：

(1)软件是一种逻辑实体；

(2)软件的生产与硬件不同，它没有明显的制作过程；

(3)软件在运行、使用期间不存在磨损、老化问题；

(4)软件的开发、运行对计算机系统具有依赖性，

(5)软件复杂性高，成本昂贵；

(6)软件开发涉及诸多的社会因素。

3、软件按功能分为应用软件、系统软件、支撑软件(或工具软件)。【5】

11数据库管理系统是系统软件。

21教务处管理系统是应用软件。(学生、财务)

4、软件危机主要表现在成本、质量、生产率等问题。

软件危机主要表现在：

1）软件需求的增长得不到满足。用户对系统不满意的情况经常发生。

2）软件开发成本和进度无法控制。开发成本超出预算，开发周期大大超过规定日期的情况经常发生。

3）软件质量难以保证。

4）软件不可维护或维护程度非常低。

5）软件的成本不断提高。

6）软件开发生产率的提高跟不上硬件的发展和应用需求的增长。

5、软件工程包括3个要素：方法、工具、过程。

方法：完成软件工程项目的技术手段。

工具：支持软件的开发、管理、文档生成。

过程：支持软件开发的各个环节的控制、管理。

6、软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程。[9、10]

软件生命周期三个阶段:软件定义.软件开发、运行维护，软件生命周期中所花费最多的阶段是软

件运行维护阶。

1）软件定义阶段：包括可行性分析和需求分析。

a.需求分析

*：需求分析的主要任务就是解决"做什么”的问题。

*：需求分析方法有：结构化需求分析方法.面向对象的分析方法。

*：需求分析一般分为需求获取、需求分析、编写需求规格说明书【3、13、17,20]和需

求评审四个步骤进行。

b、结构化需求分析方法

常用工具：1）数据流图（DFD）;2）数据字典（DD）;3）判定树；4）判定表。DD

为了解释DFD[4]

*：数据字典的作用是对数据流图中出现的被命名的图形元素的确切解释。

登录系统

客户

加工数据流存储文件源、潭

2）软件开发阶段:

软件设计：分为概要设计（总体设计）和详细设计两个部分。

软件实现：编写程序。软件设计中模块划分应遵循的准则高内聚，低耦合。［2、7］（大内高手）

软件测试：测试各部分发现错误。

a、软件概要设计（总体设计）

a）基本任务是：宽度:"整体控制密度7最大模炭数面前为袤东7

（1）设计软件系统结构（总结构）；扇入：调用一个给定模块的模块个数。

（2）数据结构及数据库设计；扇出：一个模块直接调用的其他模块数。

原子模块：树中位于叶子结点的模块。

（3）编写概要设计文档；

（4）概要设计文档评审。深度为4

b）相关概念：宽度为6

F的扇入为2

深度［HL宽度、扇入、扇出D的扇出为3

原子模块：树中位于叶子结点的模块。原子模块为5

最大扇入、最大扇出

b、详细设计：是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工

具表示算法和数据结构的细节。

常见的过程设计工具有：考试重点

1、程序流程图、N-S（方盒图）、PAD（问题分析图）和HIPO（层次图+输入/处理/输出图工

表格工具（判定表1语言工具PDL（伪码）[8、15]

程序流程图是考试重点，其中——-箭头表示控制流【1】，菱形表示逻辑条件。

c、软件测试

软件测试的目的：发现错误。【6】

软件测试方法：静态测试和动态测试。

静态测试：不实际运行软件，主要通过人工进行。

动态测试：是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法。

白盒主要方法：1、逻辑覆盖测试2、基本路径测试3、语句覆盖，在程序内部进行，白盒是可以看

见的。

黑盒主要方法[14]:1等价类划分法、2边界值分析法、3错误推测法、4因果图。

软件测试过程一般按4个步骤进行（要背先后顺序）：【19】

单元测试、集成测试、验收测试（确认测试）和系统测试。

3.5程序的调试[12]

程序调试的任务是诊断（发现）和改正程序中的错误，debug

程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。

动态调试是辅助静态调试。

调试方法有：（1）强行排错法；（2）回溯法；（3）原因排除法。

最后13、16、18

[1]、程序流程图中带有箭头的线段表示的是（）O

A）图元关系B）数据流C）控制流D）调用关系

正确答案：c

【解析工在数据流图中，用标有名字的箭头表示数据流。在程序流程图中，用标有名字的箭头表示控制流。所以选择C。

【2】、软件设计中模块划分应遵循的准则是（）。

A）低内聚低耦合B）高内聚低耦合C）低内聚高耦合D）高内聚高耦合

正确答案：B

[3]、在软件开发中，需求分析阶段产生的主要文档是（）。

A）可行性分析报告B）软件需求规格说明书

C）概要设计说明书D）集成测试计划

正确答案：B

[4]、在软件开发中，需求分析阶段可以使用的工具是（）o

A）N-S图B）DFD图C）PAD图D）程序流程图

正确答案：B

【5】、软件按功能可以分为：应用软件、系统软件和支撑软件（或工具软件）。下面属于应用软件的是（）。

A）编译程序B）操作系统C）教务管理系统~D）汇编程序

正确答案：C

[6]、下面叙述中错误的是（）

A）软件测试的目的是发现错误并改正错误

B）对被调试的程序进行“错误定位"是程序调试的必要步骤

C）程序调试通常也称为Debug

D）软件测试应严格执行测试计划，排除测试的随意性

正确答案：A

[7]、耦合性和内聚性是对模块独立性度量的两个标准。下列叙述中正确的是（）o

A）提高耦合性降低内聚性有利于提高模块的独立性

B）降低耦合性提高内聚性有利于提高模块的独立性

C）耦合性是指一个模块内部各个元素间彼此结合的紧密程度

D）内聚性是指模块间互相连接的紧密程度

正确答案：B

【8】、软件详细设计生产的图如下：

该图是（）

A）N-S图B）PAD图C）程序流程图D）E-R图

正确答案：C

【9】、软件生命周期是指（）。

A）软件产品从提出、实现、使用维护到停止使用退役的过程

B）软件从需求分析、设计、实现到测试完成的过程

C）软件的开发过程

D）软件的运行维护过程

正确答案：A

[10]、软件生命周期中的活动不包括（）。

A）市场调研B）需求分析C）软件测试D）软件维护

正确答案：A

[11]、某系统总体结构图如下图所示：

该系统总体结构图的深度是（）。

A）7B）6C）3D）2

正确答案：c

[12]、程序调试的任务是（）。

A）设计测试用例"B）验证程序的正确性

C）发现程序中的错误D）诊断和改正程序中的错误

正确答案：D

、下面不属于需求分析阶段任务的是（

[13]）o

A）确定软件系统的功能需求B）确定软件系统的性能需求

C）需求规格说明书评审D）制定软件集成测试计划

正确答案：D

【14】、在黑盒测试方法中，设计测试用例的主要根据是（）o

A）程序内部逻辑B）程序外部功能C）程序数据结构D）程序流程图

正确答案：B

[15]、在软件设计中不使用的工具是（）。

A）系统结构图