5、线性表、栈和队列是（线性）结构，可以在线性表的（任意）位置插入和删除元素，而栈只能在（栈顶）插入和删除元素；对于队列只能在（队尾）插入元素，在（队首）删除元素。
6、栈的插入和删除只能在栈的（栈顶）进行，队列的插入和删除分别在（两）端进行，进行插入的一端叫做（队尾），进行删除的一端叫做（队首）。
7、对于一个具有n个结点的二叉树，当它为一棵（完全）二叉树时具有最小高度，当它为一棵单支树时具有（最大）高度。
8、设无向图G的顶点数为n，图G最少有（n-1）条边，最多有（n（n-1）/2）
三、简答题：
1、假定有四个元素依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。
答：假设ABCD四元素依次进栈：
1)A进栈->B进栈->C进栈->D进栈->出栈->出栈->出栈->出栈 结果：D->C->B->A
2)A进栈->B进栈->C进栈->出栈->D进栈->出栈->出栈->出栈 结果：C->D->B->A
3)A进栈->B进栈->C进栈->出栈->出栈->D进栈->出栈->出栈 结果：C->B->D->A
4)A进栈->B进栈->C进栈->出栈->出栈->出栈->D进栈->出栈 结果：C->B->A->D
5)A进栈->B进栈->出栈->C进栈->D进栈->出栈->出栈->出栈 结果：B->D->C->A
6)A进栈->B进栈->出栈->出栈->C进栈->D进栈->出栈->出栈 结果：B->A->D->C
7)A进栈->B进栈->出栈->C进栈->出栈->D进栈->出栈->出栈 结果：B->C->D->A
A进栈->B进栈->出栈->出栈->C进栈->出栈->D进栈->出栈 结果：B->A->C->D
9)A进栈->出栈->B进栈->C进栈->D进栈->出栈->出栈->出栈 结果：A->D->C->B
10)A进栈->出栈->B进栈->C进栈->出栈->D进栈->出栈->出栈 结果：A->C->D->B
11)A进栈->出栈->B进栈->C进栈->出栈->出栈->D进栈->出栈 结果：A->C->B->D
12)A进栈->出栈->B进栈->出栈->C进栈->D进栈->出栈->出栈 结果：A->B->D->C
13)A进栈->出栈->B进栈->出栈->C进栈->出栈->D进栈->出栈 结果：A->B->C->D
2、二叉树与树之间有什么区别？一棵度为2的树与二叉树有什么区别？
答：二叉树的度最大为2，而树的度无此限制。
在二叉树中，一个结点的子树有左、右之分，不能互换位置。而度为2的树则无此限制。
3、写出对如图所示二叉树进行先序遍历、中序遍历、后序遍历时得到的顶点序列。
答：先序遍历序列：ABDEC 中序遍历序列：DEBAC 后序遍历序列：EDBCA
程序设计基础作业4
一、选择题与填空题
1、D 结构化程序流程图中一般包括三种基本结构，下述结构中哪一种不属于其基本结构（嵌套结构）
2、A 程序设计语言的选择是顺利实施编程的重要基础，评价语言的因素很多，而其重要的选择依据是（语言的应用领域）
3、B 在软件工程中，软件测试的目的是（发现软件错误）
4、E 软件危机是软件产业化过程中出现的一种现象，下述现象中，（软件需求难以满足、软件开发成本提高、软件开发进度难以控制、软件质量不易保证） 5、C 软件工程的出现主要是由于（软件危机的出现）
6、算法的四种基本操作是（逻辑运算、算术运算、数据比较、数据传送） 7、算法的控制结构给出了算法的执行框架，她决定了算法中各种操作的执行（次序）
8、算法的控制结构有三种基本形式：（顺序结构、选择结构、循环结构） 9、评价算法的综合性能最主要的是算法的（正确性）和（运行效果）
10、算法的隐匿性效率包括两方面，算法的（时间）复杂度和算法的（空间）复杂度。
11、结构化程序设计方法的主要技术是（自顶而下）和（逐步求精） 12、软件生命周期包括软件的（定义）、软件的（开发）和（使用与维护）软件3个部分。
13、软件定义时期主要包括（可行性分析）和（要求分析）两个阶段。
14、软件开发时期是具体设计和实现在前一时期定义的软件，它由（软件设计阶段、实现阶段、测试阶段）3个阶段组成。
15、软件工程的目标是可概括为生产具有（正确）性、（可用）性，以及（开销合宜）的产品。
16、常见的软件开发模型由（瀑布模型、快速原型法模型、螺旋模型）
二、简答题：
1、什么是算法？它有哪几个重要特性？简述三种算法的描述形式和
特点。
答：算法是用于求解某个特定问题的一些指令的集合。
算法的特性：1．有穷性2．确定性3．可行性4．输入性5．输出性
用自然语言描述的算法通俗易懂，而且容易掌握，但算法的表达与计算机的具体高级语言形式差距较大，通常是用于介绍求解问题的一般算法。
伪代码是一种介于自然语言与计算机语言之间的算法描述方法。它结构性较强，比较容易书写和理解，修改起来也相对方便。其特点是不拘泥于语言的语法结构，而着重以灵活的形式表现被描述对象。它利用自然语言的功能和若干基本控制结构来描述算法。
流程图也叫框图，它是是用各种几何图形、流程线及文字说明来描述计算过程的框图。用流程图描述算法的优点是：直观，设计者的思路表达得清楚易懂，便于检查修改。
2、结构化程序设计主要有哪些特征？
答：(1)一个程序按结构化程序设计方式构造时，一般地总是一个结构化程序，即由三种基本控制结构：顺序结构、选择结构和循环结构构成。 (2)有限制地使用goto语句。
(3)藉助于体现结构化程序设计思想的所谓结构化程序设计语言来书写结构化程序，并采用一定的书写格式以提高程序结构的清晰性，增进程序的易读性。
(4)强调程序设计过程中人的思维方式与规律，是一种自顶向下的程序设计策略，它通过一组规则、规律与特有的风格对程序设计细分和组织。
3、模块化程序设计有哪些优点和缺点？简述模块的设计准则是什么？
答：优点（1）模块化方法使程序的结构简明清晰 （2）模块化方法可以提高系统的可靠性。 （3）模块化方法加强了系统的可维护性。 （4）模块化方法能够提高系统的可重用性。 （5）模块化方法有利于软件工程管理。 缺点（1）编码前需要大量的额外工作
（2）模块化程序运行时需要较多的CPU时间 （3）模块化程序需要较多的存储空间。
4、什么是软件工程？软件工程的目标是什么？
答：软件工程是应用计算机科学、数学及管理科学等原理，开发软件的工程。 软件工程的目标可概括为“生产具有正确性、可用性以及开销合宜的产品”。
5、软件开发模型有哪两类？瀑布模型和速成原型法各有什么特点？
答：软件开发模型大体上可分为两种类型：
第一种是以软件需求完全确定为前提的瀑布模型。
第二种是在软件开发初始阶段只能提供基本需求时采用的渐进式开发模型，如原型模型、螺旋模型等。
瀑布模型的主要特点是：阶段间的顺序性和依赖性。开发过程是一个严格的下
导式过程，即前一阶段的输出是后一阶段的输入，每一阶段工作的完成需要确认，而确认过程是严格的追溯式过程，后一阶段出现了问题要通过前一阶段的重新确认来解决。因此，问题发现得越晚解决问题的代价就越高。
快速原型法的最大特点是快捷，且避免了许多由于不同理解而造成的错误。
程序设计基础形考作业答案
