数据结构-经典笔试题

《数据结构-经典笔试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软件技术基础一、名词解释：1.数据结构——数据结构就是数据的组织形式，也可看成是包含数据结构的数据表，说明数据之间存在着一定的相互关系或约束。2.逻辑结构——我们把只表现元素之间逻辑关系，而不涉及它们在计算机中的表示，只是理论的、反映在纸面上的东西，这种抽象的数据结构称为逻辑结构。3.物理结构——抽象的数据结构在计算机内的表示，也就是映射在存储空间上的、具体的数据结构在计算机内表示，也就是映射在存储空间上的、具体的数据结构。二、问答题：1.简述“软件工程”的工程化的思想。答：软件工程就是应用一些科学理论和工程上的技术来指导软件开发。软件工程将研制软件的全过程分为六个阶段：问题说明，

2、需求分析，系统设计，编写程序，测试工作，运行与维护。软件工程的基本原则是：划分软件生命期，运行计划评审，编制软件文档。2.说明对程序进行评价时，“时间”与“空间”之间的关系。答：时间性和空间性是程序的效率问题。时间效率决定于：源程序转换为目标程序的时间和目标程序执行的时间。时间效率与编译质量有关，与算法的简化程度有关，还与用户对语言的熟练程度有关，其中，算法的效率起主要作用。空间效率一般指程序花费的内存空间的问题。对于同等复杂程度的程序：一般时间效率越高的程序，占用的内存就越大，空间效率就越低；一般时间效率越低的程序，占用的内存就越小，空间效率就越高。两者具有一定的矛盾性。但是随着

3、内存容量的不断增大，往往会牺牲空间性来提高时间性。3.依照“软件工程”的思想，叙述软件生命周期的不同阶段及各阶段的主要工作内容。答：在软件工程中，把从软件的计划开始，经历问题的说明（定义），需求分析，设计代码，测试与维护，直到软件报废为止的整个期间，称为软件的生命周期。在软件生命周期中，除了最后的运行与维护属于运行期，其它都称为开发期。1）问题说明：对研究的问题进行完整而且适当的说明。2）需求分析：根据问题说明，确定软件必须具有的功能。不是具体解决问题，而是明确必须“做什么”。3）系统设计：将反映用户要求的逻辑模型转换为一个具体的设计方案，使用伪码来描述算法。4）编写程序：将伪码转

4、换为高级语言的形式。5）测试工作：检查程序和系统的其他部分是否满足设计要求。6）运行与维护：将验收后的软件交付用户使用，通过实际运行环境的检验，对不适应的部分进行修改和扩充。4.拓扑排序中使用了那些数据结构——共使用了数组，链表，图和堆栈四种数据结构。三、求二叉树的叶节点的个数：algorithmcountleaf(Tree*t,intcount){if(t!=null){if(t->lchild==null&&t->rchild==null)count++;coutleaf(t->lchild,count);10软件技术基础coutleaf(t->rchild,count);}}

5、四、求二叉树深度的算法：algorithmdepth(Tree*t){if(t==null)return(0);else{hl=depth(t->lchild);hr=depth(t->rchild);if(hl>hr)return(hl+1);elsereturn(hr+1);}}五、将二叉树的左右孩子交换的算法：algorithmswap(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

6、);}}六、用两个栈模拟一个队列：algorithm用两个栈模拟一个队列{stacks1,s2;//容量都为n。void元素入队{intx;10软件技术基础if(s1->top==n)printf("队列上溢");elsepush(s1,x);}void元素出队{intx;s2->top=0;while(!Empty(s1))push(s2,pop(s1));pop(s2,x);while(!Empty(s2))push(s1,pop(s2));}void判断队列是否为空{if(isEmpty(s1))return(1);elsereturn(0);}}七、邻接表的排序：对给定的数

7、组A[1:n]，假定每个元素是由形式age->link的记录组成，其中age域表示年龄，link域指向由name->link组成的链表，该链表记录了同龄人的姓名。要求设计算法，使A[1]链表中的年龄小于A[2]链表中的年龄，A[2]链表中的年龄小于A[3]链表中的年龄……algorithm邻接表的排序{for(i=1;iageage)pos=j;if(pos!=i){