数据结构-经典笔试题.docVIP

一、名词解释： 1. 数据结构——数据结构就是数据的组织形式，也可看成是包含数据结构的数据表，说明数据之间存在着一定的相互关系或约束。 2. 逻辑结构——我们把只表现元素之间逻辑关系，而不涉及它们在计算机中的表示，只是理论的、反映在纸面上的东西，这种抽象的数据结构称为逻辑结构。 3. 物理结构——抽象的数据结构在计算机内的表示，也就是映射在存储空间上的、具体的数据结构在计算机内表示，也就是映射在存储空间上的、具体的数据结构。 二、问答题： 简述“软件工程”的工程化的思想。 答：软件工程就是应用一些科学理论和工程上的技术来指导软件开发。 软件工程将研制软件的全过程分为六个阶段：问题说明，需求分析，系统设计，编写程序，测试工作，运行与维护。 软件工程的基本原则是：划分软件生命期，运行计划评审，编制软件文档。 说明对程序进行评价时，“时间”与“空间”之间的关系。 答：时间性和空间性是程序的效率问题。 时间效率决定于：源程序转换为目标程序的时间和目标程序执行的时间。时间效率与编译质量有关，与算法的简化程度有关，还与用户对语言的熟练程度有关，其中，算法的效率起主要作用。 空间效率一般指程序花费的内存空间的问题。 对于同等复杂程度的程序：一般时间效率越高的程序，占用的内存就越大，空间效率就越低；一般时间效率越低的程序，占用的内存就越小，空间效率就越高。两者具有一定的矛盾性。但是随着内存容量的不断增大，往往会牺牲空间性来提高时间性。 依照“软件工程”的思想，叙述软件生命周期的不同阶段及各阶段的主要工作内容。 答：在软件工程中，把从软件的计划开始，经历问题的说明（定义），需求分析，设计代码，测试与维护，直到软件报废为止的整个期间，称为软件的生命周期。在软件生命周期中，除了最后的运行与维护属于运行期，其它都称为开发期。 问题说明：对研究的问题进行完整而且适当的说明。 需求分析：根据问题说明，确定软件必须具有的功能。不是具体解决问题，而是明确必须“做什么”。 系统设计：将反映用户要求的逻辑模型转换为一个具体的设计方案，使用伪码来描述算法。 编写程序：将伪码转换为高级语言的形式。 测试工作：检查程序和系统的其他部分是否满足设计要求。 运行与维护：将验收后的软件交付用户使用，通过实际运行环境的检验，对不适应的部分进行修改和扩充。 拓扑排序中使用了那些数据结构——共使用了数组，链表，图和堆栈四种数据结构。 三、求二叉树的叶节点的个数： algorithm countleaf( Tree *t, int count ) { if( t != null ) { if( t-lchild == null t-rchild == null ) count++; coutleaf( t-lchild, count ); coutleaf( t-rchild, count ); } } 四、求二叉树深度的算法： algorithm depth( Tree *t ) { if( t == null ) return( 0 ); else { hl = depth( t-lchild ); hr = depth( t-rchild ); if( hl hr ) return( hl + 1 ); else return( hr + 1 ); } } 五、将二叉树的左右孩子交换的算法： algorithm swap( Tree *b ) //自顶向下的交换 { Tree *t; if( b == null ) return; else { t = b-lchild; b-lchild = b-rchild; b-rchild = t; swap( b-lchild ); swap( b-rchild ); } } 六、用两个栈模拟一个队列： algorithm 用两个栈模拟一个队列{ stack s1, s2; // 容量都为n。 void 元素入队{ int x; if( s1-top == n ) printf( 队列上溢 ); else push( s1, x ); } void 元素出队{ int x; s2-top = 0;