数据结构软件工程数据库(2)有答案

(7) 软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于 A)定义阶段 B)开发阶段 C)维护阶段 D)上述三个阶段 (8) 软件详细设计产生的图如下： 该图是（ ）
A）N-S图 B）
PAD图
C）程序流程图
D）E-R图
（9）下面叙述中错误的是 A）软件测试的目的是发现错误并改正错误 B）对被调试的程序进行“错误定位”是程序调试的必要步骤 C）程序调试通常也称为Debug D）软件测试应严格执行测试计划，排除测试的随意性
栈：栈是只能在一端进行插入与删除运算的线性表。
入栈
入栈：5，3，7
Top 栈顶
7 3 5
Bottom 栈底不动
出栈：7，3，5
特点：先进后出
（通常用顺序结构存储也可以用链式存储）
入栈出栈都在栈顶。 栈底不动
（1）下列关于栈的叙述正确的是 A）栈按“先进先出”组织数据 B)栈按“先进后出”组织数据 C）只能在栈底插入数据 D）不能删除数据
数据库基础
数据库系统
VB VC++ 应用程序 PowerBuilder Delphi
数据库引挚 SQL命令 数据库管 理系统 数据库
ORACLE
ACCESS
FOXPRO
SQL SERVER
发出请求
SQL命令
IE
响应请求
HTM、ASP
数据
来自百度文库数据库
客户机
服务器
数据管理技术的三个发展阶段
• 人工管理阶段
数据结构
数据结构： 是指相互有关联的数据元素的集合。它用来反映 一个数据的内部构成，即一个数据由那些成分数据 构成，以什么方式构成，呈什么结构 分类： 逻辑结构:数据元素之间的逻辑关系，即人对数 据的理解，而进行抽象的模型 存储结构(物理结构)数据元素在计算机中的存储 方法，即计算机对数据的理解，逻辑结构在计算机 语言中的映射。(座位是物理结构，学号是逻辑结构)
二级考试基础辅导讲义
本 节 要 点
1. 2. 3. 4. 数据结构与算法 软件工程 数据库基础 程序设计基础
算法
算法：是指解题方案的准确而完整的描述 。 算法的基本特征： （1）可行性 （2）确定性 （3）有穷性 算法复杂度：主要包括时间复杂度和空间复杂度 （1）算法时间复杂度是指执行算法所需要的计算工作 量，可以用执行算法的过程中所需基本运算的执行 次数来度量。 （2）算法空间复杂度是指执行这个算法所需要的临时 工作单元数 。
--数据字典（DD) ：对数据流图中出现的被命名的图形元素的确切解释。
数据流图
报名单
考 生
成绩 准考证
考务处 理系统
试卷分析
试卷
成绩
阅卷站
加工
数据流
存储文件
外部实体
• 软件开发阶段
1、软件设计
“怎么做”
总体设计：抽象、模块化、信息隐蔽和模块独立性
详细设计
图形工具：程序流程图、N-S(方盒图)、PAD(问题分析图)、 HIPO（层次图+输入/处理/输出图） 表格工具：判定表 语言工具：PDL（伪码 ）
满二叉树： 共有2n-1个结点（n为深度）
A
二叉树的遍历
D B E
L在R之前
L R C
D
F
前序遍历： D→L→R 中序遍历： L→D→R 后序遍历： L→R→D
G
H
前序： ABCDEFGH
中序： CBDAGFHE
后序： CDBGHFEA
（1）某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度 为（假设根结点在第1层） A） 3 B） 4 C） 6 D） 7 （2）某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为 A)n+1 B)n-1 C)2n D)n/2
练习题： （1）下面描述中，不属于软件危机表现的是 A）软件过程不规范 B）软件开发生产率低 C）软件质量难以控制 D）软件成本不断提高 （2）软件生命周期是指 A）软件产品从提出、实现、使用维护到停止使用退役的过程 B）软件从需求分析、设计、实现到测试完成的过程 C）软件的开发过程 D）软件的运行维护过程 （3）在软件开发中，需求分析阶段产生的主要文档是 A）软件集成测试计划 B）软件详细设计说明书 C) 用户手册 D）软件需求规格说明书 （4）软件测试的目的是 A）评估软件可靠性 C）改正程序中的错误
B）发现并改正程序中的错误 D）发现程序中的错误
（5）软件(程序)调试的任务是 A)诊断和改正程序中的错误 C)发现并改正程序中的所有错误
B)尽可能多地发现程序中的错误 D)确定程序中错误的性质
(6) 数据流程图(DFD图)是 A)软件概要设计的工具 C)结构化方法的需求分析工具
B)软件详细设计的工具 D)面向对象方法的需求分析工具
（10）在软件开发中，需求分析阶段可以使用的工具是 A）N-S图 B）DFD图 C）PAD图（问题分析图） D）程序流程图
（11）软件是指 A)程序 C)算法加数据结构
B)程序和文档 D)程序、数据与相关文档的完整集合
（12）从工程管理角度，软件设计一般分为两步完成，它们是 A)概要设计与详细设计 B)数据设计与接口设计 C)软件结构设计与数据设计 D)过程设计与数据设计 （13）下列叙述中正确的是 A)软件测试的主要目的是发现程序中的错误 B)软件测试的主要目的是确定程序中错误的位置 C)为了提高软件测试的效率，最好由程序编制者自己来完成软件测试的工作 D)软件测试是证明软件没有错误
二叉树的基本性质：
性质1 在二叉树的第k层上，最多有 2k-1 个结点。 性质2 深度为m的二叉树最多有个2m-1 个结点。 性质3 在任意一棵二叉树中，度为0的结点个数 = 度为2的结点个数+1 设度为0的节点数a0，度为1的节点数a1，度为2的节点数a2，总节 点数n，则：
1）已知a0、a1，可求出n（已知a2、a1，也可求出n ）
若rear<front,则为 rear+队列容量-front
（1）设某循环队列的容量为50，头指针front=5（指向队头元素的前一位 置），尾指针rear=29（指向队尾元素），则该循环队列中共有 24 个元素。 （2）设某循环队列的容量为50，如果头指针front=45(指向队头元素的前 一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有 15 个元素。
树：是一种简单的非线性结构。
父结点
所有数据元素之间的关系 具有明显的层次特性。
子结点
叶子结点
结点的度 ：一个结点所拥有的后件的个数 （下级分叉） 树的度：所有结点中最大的度 树的深度 ：树的最大层次
二叉树：
1）非空二叉树只有一个根结点； 2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 3）二叉树的度可以为0、1或2。
（3）对于循环队列，下列叙述中正确的是（ ）。 A）队头指针是固定不变的 B）队头指针一定大于队尾指针 C）队头指针一定小于队尾指针 D）队头指针可以大于队尾指针，也可以小于队尾指针
（4）下列叙述中正确的是 A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构 B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况 C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况 D）循环队列中元素的个数是由队头指针和队尾指针共同决定
成本、质量、生产率
3,软件工程: 将工程化原则运用到软件开发过程
4.软件生命周期 软件定义、软件开发、软件运行维护三个阶段
可行性分析 软件定义 需求分析 总体设计
（概要设计）
软件生命周期 软件设计 详细设计 软件开发 软件编码
软件运行维护
软件测试
•软件定义阶段：提出问题（做什么）
可行性研究 ——可行性分析报告 需求分析——软件需求规格说明书 结构化分析方法工具： --数据流图（DFD）：以图形的方式描绘数据在系统中流动和处理的过程。
2、软件编码→编程（根据流程图编写程序）
静态测试
3、软件测试
动态测试
白盒：结构测试（编程人员测试） 黑盒：功能测试（不关心内部逻辑，达到用户目标）
测试步骤：单元测试、集成测试、确认测试、系统测试
软件测试的目的：尽可能地多发现程序中的错误
程序的调试 程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行，调试 程序应该由编制源程序的程序员来完成。 程序调试的基本步骤：（1）错误定位；（2）纠正错误；（3）回归测试。 注意与软件测试区分: 程序调试的任务是诊断和改正程序中的错误。 软件测试的目的：尽可能地多发现程序中的错误，不能也不可能证明程序 没有错误。
(链式)线性表 优点：修改效率高（插入、删除元素）
数据域 地址域
data next
head
左指针 数据域 右指针 head prev next
双向链表
循环链表
（1）下列叙述中正确的是 A）有一个以上根结点的数据结构不一定是非线性结构 B）只有一个根结点的数据结构不一定是线性结构 C）循环链表是非线性结构 D）双向链表是非线性结构 （2）下列叙述中正确的是 A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 D）上述三种说法都不对 （3）下列叙述中正确的是 A）顺序存储结构的存储一定是连续的， 链式存储结构的存储空间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表 D）链式存储结构比顺序存储结构节省存储空间
队列是指允许在一端（队尾）进入插入，而在另一 队列：
端（队头）进行删除的线性表。
front 头指针 rear
2 0 1 1
入队（增）：rear 移动
尾指针
出队（删）：front 移动
front
rear
5
3
7
循环队列：
rear front
front rear
循环队列元素个数: 若rear>front,则为 rear-front
（3）在深度为7的满二叉树中，叶子结点的个数为 A)32 B)31 C)64 D)63
（4）对下列二叉树进行前序遍历的结果是
A
B D Y E F Z C X
A)DYBEAFCZX
B)YDEBFZXCA
C)ABDYECFXZ
D)ABCDEFXYZ
软件工程基础
1,软件 =
程序
+ 数据 + 文档
2软件危机
2）已知n、a0，可求出a1、a2 3）已知n、a1，可求出a0、a2
如：二叉树中度为0的结点60个，度为1 的结点59个求总结点数
60+59+59=178
0 1 3 7 8 9 4 10 11 5 12 13 2 6 14 7 3 8 9 1 4
0 2 5 6
(a)满二叉树
(b)完全二叉树
满二叉树： 除最后一层外，每一层上的所有结点都有两个子结点。 完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后 一层上只缺少右边的若干结点。
（1）算法的时间复杂度是指（） A)算法的执行时间 B)算法所处理的数据量 C)算法程序中的语句或指令条数 D)算法在执行过程中所需要的基本运算次数 （2）算法的空间复杂度是指（ ）。 A）算法在执行过程中所需要的计算机存储空间 B）算法所处理的数据量 C）算法程序中的语句或指令条数 D）算法在执行过程中所需要的临时工作单元数 （3）算法的有穷性是指（） A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用
逻辑结构： 线性（线性表、栈、队列） 非线性（树、二叉树、图）
物理结构 顺序 链式 索引
如何区分线性和非线性？ 线性 一个数据节点只有一个前件和一个后件
非线性
一个数据节点有多个前件或多个后件
一种逻辑结构可通过多种物理结构来实现 （顺序）线性表 a b c d e f g h i
单链表
如：数组 方便查找（折半查找）
• 文件管理阶段 • 数据库系统阶段
１.人工管理阶段
• • • • • 时间：20世纪50年代中期以前 硬件：只有卡片、纸带、磁带等存储设备 软件：没有操作系统，没有进行数据管理的软件 应用：以科学计算为目的 特点： 数据１ 程序1
（2）一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是 A）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA
（3）下列叙述中正确的是 A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化 B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化 C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 D）上述三种说法都不对