公共基础知识真题总结(共9页)

1、公共(gnggng)基础(jch)知识(zh shi)真题总结（1）一个非空的数据结构如果满足以下两个条件：有且只有一个根节点；每一个节点最多有一个前件，也最多有一个后件，称为线性结构，称为线性表，可以采用顺序存储和链接存储，其中链式存储空间不连续。（2）双向链表节点有两个指针域，指向前一个节点的指针和指向后一个节点的指针，也是线性结构。（3）顺序存储结构中可能根节点不唯一，故可能不是线性结构；（4）栈是所有的插入与删除都限定在表的同一端进行的线性表；队列是指允许在一端进行插入，而在另一端进行删除的线性表。带链的湛与队列是线性结构。2. （1）循环队列是队列的一种顺序存储结构；（2）双向链表为

2、顺序存储结构，二叉树通常采用链式存储结构；（3）完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（4）有的非线性结构也可以采用顺序存储结构。3. (1) 一个非空的数据结构如果满足以下两个条件：有且只有一个根节点；每一个节点最多有一个前件，也最多有一个后件，称为线性结构。双向链表节点有两个指针域，指向前一个节点的指针和指向后一个节点的指针，也是线性结构; (2) 如果有两个节点的同一个指针域的值相等，说明一个节点有两个前件，属于非线性结构 (3) 非线性结构主要是指树形结构和网状结构，可以满足每个节点有两个指针域的条件 (4) 在链表中，如果有两个结点的同一个指针域的值相等，则该链

3、表一定是非线性结构。4. （1）数据结构(sh j ji u)中若有中间结点不满足只有一个前件或者后件条件(tiojin)，则不属于线性结构。 （2）没有根结点或没有叶子(y zi)结点的数据结构一定是非线性结构。5. （1）算法是指对解题方案的准确而完整的描述，简单的说，就是解决问题的操作步骤。算法不同于数学上的计算方法，强调实现，故算法强调动态的执行过程，不同于静态的计算公式；（2）算法的有穷性是指，算法中的操作步骤为有限个，且每个步骤都能在有限的时间内完成，即算法必须能在有限的步骤之后终止；（3）算法复杂度包括算法的时间复杂度和算法的空间复杂度。算法设计必须考虑执行算法所需的资源，即时间

4、与空间复杂度；（4）算法的优劣取决于算法复杂度，与程序的环境无关，当算法被编程实现之后，程序的运行受到计算机系统运行环境的限制。6. 线性链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间，所以一般要多于顺序存储结构。7. 顺序表具有以下两个基本特征：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在顺序表中，每个元素占有相同的存储单元。用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。8. （1）栈是先进后出的线性表；数据的插入和删除都在栈顶进行操作；栈

5、顶元素最后入栈却最先被删除，栈底元素最先入栈却最后被删除；在整个过程中，栈底指针不变，入栈与出栈操作均由栈顶指针的变化来操作；（2）队列是先进先出的线性表；（3）循环(xnhun)队列是线性结构(jigu)的线性表；其是队列(duli)的一种顺序存储结构；其有队头和队尾两个指针；在循环队列中只需要队头指针与队尾两个指针来共同反映对列中元素的动态变化情况。循环队列的队头指针与队尾指针都不是固定的，随着入队与出队操作要进行变化。因为是循环利用的队列结构所以对头指针有时可能大于队尾指针有时也可能小于队尾指针。（4）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。9. 栈是一种特殊的线性表，

6、它所有的插入与删除都限定在表的同一端进行。入栈运算即在栈顶位置插入一个新元素，退栈运算即是取出栈顶元素赋予指定变量。栈为空时，栈顶指针top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为top=m+1，当top=20时，元素依次存储在单元20：m中，个数为m-1910. 在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。在循环队列中进行出队、入队操作时，头尾指针仍要加，朝前移动。只不过当头尾指针指向向量上界时，其加操作的结果是指向向量的下界。由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时，头尾指针均相等。

7、11.类型优点缺 点顺序表（1）可以随机存取表中的任意结点 （2）无需为表示结点间的逻辑关系额外增加存储空间（1）顺序表的插入和删除运算效率很低 （2）顺序表的存储空间不便于扩充 （3）顺序表不便于对存储空间的动态分配链表（1）在进行插入和删除运算时，只需要改变指针即可，不需要移动元素 （2）链表的存储空间易于扩充并且方便空间的动态分配需要额外的空间（指针域）来表示数据元素之间的逻辑关系，存储密度比顺序表低由表中可以看出(kn ch)链式存储插入与删除运算效率高。12一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。线性链表

8、中数据的插入和删除(shnch)都不需要移动表中的元素，只需改变结点的指针(zhzhn)域即可。13.（1）双向链表与树形结构的节点均可以包含两个指针域，但前者为线性结构后者为非线性结构；（2）双向链表含有指向前件和指向后件的两个指针；（3）线性链表，就是指线性表的链式存储结构，由于这种链表中，每个节点只有一个指针域，故又称为单链表；（4）二叉树为非线结构，叶子节点没有后件但是可以有指向前件的指针。14.（1）线性单链表就是指线性表的链式存储结构，这种结构只能从一个节点遍历到其后的所有节点。（2）在单链表的第一个节点前增加一个表头节点，队头指针指向表头节点，所以可以从任何一个节点开始直接遍历到

9、所有节点，最后一个节点的指针域的值由NULL改为指向表头节点，这样的链表称为循环链表，其是线性结构；双向链表是指链表节点含有指向前一个节点的指针和指向后一个节点的指针，所以可以从任何一个节点开始直接遍历到所有节点；二叉树链表中节点指针由父节点指向子节点，可以从根节点开始遍历到所有节点。15.（1）双向链表与二叉链表均是有两个指针域的链表；二叉树通常采用链式存储结构，完全二叉树结构的最佳存储方式是顺序存储方式，这也就是说明有的非线性结构可以采用顺序存储结构。(2)在单链表的第一个结点前增加一个表头结点，队头指针指向表头结点，最后一个结点的指针域的值由NULL改为指向表头结点，这样的链表称为循环链

10、表。循环队列是队列的一种顺序存储结构。循环链表与循环队列是两种存储结构；（3）双向链表结点有两个指针域，指向前一个结点的指针和指向后一个结点的指针，而带链的栈是单链表形式。是顺序存储结构。16.（1）带链的栈与队列是线性结构。（2）结点(ji din)中具有多个指针(zhzhn)域的链表称为多重链表（3）栈是支持(zhch)子程序调用的数据结构；（4）在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。对任何一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。二叉树共有845个结点，度为0的结点有45个，度为1的结点数为n1, 度为2的结点数为n2，则

11、845=45+n1+n2，且45= n2+1，则n1=75617. 一棵深度为K的满二叉树，整棵二叉树共有2K-1个节点；满二叉树在其第i层上有2i-1个节点。在满二叉树中，只有度为2和度为0的节点。深度为7的满二叉树，节点个数为27-1=127，第七层叶节点个数为27-1=64，则127-64=63。18. 在二叉树中，一个结点所拥有的后件个数称为该结点的度。完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。由定义可以知道，完全二叉树中度为1的结点个数为1或者0。若结点总数为偶数，则有1个度为1的结点；若结点总数为奇数，没有度为1的结点。18. 在树结

12、构中，定义一棵树的根结点所在的层次为，其他结点所在的层次等于它的父结点所在的层次加，树的最大层次称为树的深度。完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。深度为6的满二叉树，结点个数为26-1=63，则第7层共有125-63=62个叶子结点，分别挂在第6层的左边62个结点上，加上第6层的最后1个叶子结点，该完全二叉树共有63个叶子结点。19. 前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。前序遍历描述为：若二叉树为空

13、，则执行空操作。否则：访问根结点；前序遍历左子树；前序遍历右子树。20. 当有序线性表为顺序存储时才能用二分法查找(ch zho)。可以证明的是对于长度为n的有序线性表，在最坏情况下，二分法查找只需要(xyo)比较次，而顺序(shnx)查找需要比较n次。21. 二分法查找也称拆半查找，是一种高效的查找方法。能使用二分法查找的线性表必须满足两个条件：用顺序存储结构；线性表是有序表。22. “有序是特指元素按非递减排列，即从小到大排列，但允许相邻元素相等；有序表可以顺序存储也可以链式存储；有序表可以用链接存储方式存储在不连续的存储空间内。23. 冒泡排序只交换相邻元素，但不是每次移动都产生新的逆序

14、。简单插入排序的元素移动不会产生新的逆序。快速排序每一次交换移动都会产生新的逆序，因为当不会有新的逆序产生时，本轮比较结束。24. 结构化程序设计中，要注意尽量避免goto语句的使用.25. 对象之间进行通信的构造叫做消息。多态性是指同一个操作可以是不同对象的行为。对象不一定必须有继承性。封装性是指从外面看只能看到对象的外部特征，而不知道也无须知道数据的具体结构以及实现操作,是实现对象的数据和操作结合于统一体中。26. 类是具有共同属性、共同方法的对象的集合，是关于对象的抽象描述，反映属于该对象类型的所有对象的性质。对象具有的性质，类也具有。27. 整数类实例包括：十进制常量用09表示，不能以

15、0开头；八进制常量用07表示，必须用0开头；十六进制常量用09和AF(af)表示，必须以0 x或0X开头。28. 继承是面向对象的方法的一个主要特征，是使用已有的类的定义作为基础建立新类的定义技术(jsh)。广义的说，继承是指能够直接获得已有的性质和特征，而不必重复定义(dngy)它们，所以说继承(jchng)是指类之间共享属性和操作的机制。29. （1）软件测试的目的是为了发现错误而执行程序的过程，并不涉及改正错误；（2）程序调试的基本步骤有：错误定位、修改设计和代码，以排除错误、进行回归测试，防止引进新的错误。程序调试通常称为Debug，即排错。软件测试的基本准则有：所有测试都应追溯到需求

16、、严格执行测试计划，排除测试的随意性、充分注意测试中的群集现象、程序员应避免检查自己的程序、穷举测试不可能、妥善保存测试计划等文件。30. 软件危机主要表现在：软件需求的增长得不到满足；软件开发成本和进度无法控制；软件质量难以保证；软件不可维护或维护程度非常低；软件的成本不断提高；软件开发生产率的提高赶不上硬件的发展和应用需求的增长。31. 软件需求规格说明书是需求分析阶段的最后成果，是软件开发的重要文档之一。软件需求规格说明书有以下几个方面的作用。便于用户、开发人员进行理解和交流；反映出用户问题的结构，可以作为软件开发工作的基础和依据，；作为确认测试和验收的依据。32. 模块独立性是指每个模

17、块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。一般较优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性。耦合性是模块间互相连接的紧密程度的度量而内聚性是指一个模块内部各个元素间彼此结合的紧密程度。33. 系统(xtng)结构图是对软件系统结构的总体设计的图形显示。在需求分析阶段，已经从系统开发的角度(jiod)出发，把系统按功能逐次分割成层次结构，是在概要(giyo)设计阶段用到的。PAD图是在详细设计阶段用到的。程序流程图是对程序流程的图形表示，在详细设计过程中用到。数据流图(DFD图)是结构化分析方法中使用的工

18、具，它以图形的方式描绘数据在系统中流动和处理的过程，由于它只反映系统必须完成的逻辑功能，所以它是一种功能模型，是在可行性研究阶段用到的而非软件设计时用到。34. 黑盒测试是对软件已经实现的功能是否满足需求进行测试和验证，黑盒测试完全不考虑程序内部的逻辑结构和内部特性，只根据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明。其设计测试用例的主要根据是：程序外部功能。35. 数据独立性包括物理独立性和逻辑独立性，物理独立性指数据的物理结构的改变，不会影响数据库的逻辑结构，也不会引起应用程序的改动；逻辑独立性指数据库的总体逻辑结构的改变，不会导致相应的应用程序的改变。36. 数据模型按照不同的应用层次分为以下3种类型：概念数据模型，着重于对客观世界复杂事物的描述及对它们内在联系的刻画；逻辑数据模型，是面向数据库系统的模型，着重于在数据库系统一级的实现，其主要包括层次模型、网状模型、关系模型和面向对象模型；物理数据模型，是面向计算机物理实现的模型，此模型给出了数据模型在计算机上物理结构的表示，其主要包括数据结构、数据操作、数据约束。37. 关系模型实体间的联