公共基础知识部分.ppt

《公共基础知识部分.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、公共基础知识部分一、数据结构与算法二、程序设计基础三、软件工程基础四、数据库设计基础一、数据结构与算法1、数据的存储结构是指（）A、存储在外存中的数据B、数据所占的存储空间量C、数据在计算机中的顺序存储方式D、数据的逻辑结构在计算机中的表示分析:数据的存储结构:数据的逻辑结构在计算机存储空间中的存放形式。也称为物理结构。数据的逻辑结构：反映数据元素之间关系的数据元素集合（数据对象）的表示。包括：元素的信息、数据元素之间的前后件关系。结构：集合、线性结构、树形结构、图形结构四种。一种逻辑结构的数据可以表示成多种存储结构：顺序、链式、索引等。2、下列关于栈的描述中错误的是（）

2、A、栈是先进后出的线性表B、栈只能顺序存储C、栈具有记忆作用D、对栈的插入与删除操作中，不需要改变栈底指针分析：栈：特殊的线性表。限定只在一端进行插入与删除的线性表，这一端称为栈顶，另一端称为栈底。栈是按照“先进后出”或“后进先出”的原则组织数据的。栈具有记忆作用。3、对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（）A、冒泡排序为n/2B、冒泡排序为nC、快速排序为nD、快速排序为n(n-1)/2分析：冒泡排序和快速排序在最坏的情况下，需要比较n(n-1)/2次。4、对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）A、log

3、2nB、n/2C、nD、n+1分析：1、查找可分为：顺序查找和二分查找两种。2、对于长度为n的有序线性表，在最坏情况下，顺序查找需要比较n次，而二分查找只需要log2n次。5、下列对于线性链表的描述正确的是（）A、存储空间不一定连续，且各元素的存储顺序是任意的B、存储空间不一定连续，且前件元素一定存储在后件元素的前面C、存储空间必须连续，且前件元素一定存储在后件元素的前面D、存储空间必须连续，且各元素的存储顺序是任意的分析：1、线性链表：就是线性表的链式存储。存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确

4、定的。2、线性表的顺序存储：用一组地址连续的存储单元依次存储线性表的数据元素。缺点：插入删除时移动大量元素；有“上溢”情况；空间不便于动态分配。6、某二叉树中度为2的结点有18个，则该二叉树中有（）个叶子结点。分析：1、二叉树的定义二叉树只有一个根结点，每个结点最多只有两棵树（左子树、右子树）。2、二叉树的性质：性质1：在二叉树的第k层上至多有2k-1个结点（k>=1）;性质2：深度为m的二叉树至多有2k-1个结点。性质3：对任意一棵二叉树，度为0的结点数总比度为2的结点数多1。性质4：具有n个结点的完全二叉树深度至少为[log2n]+1。7、下列数据结构中，能用二分法进

5、行查找的是（）A、顺序存储的有序线性表B、线性链表C、二叉链表D、有序线性链表分析：二分查找只适用于顺序存储的有序表。8、下列关于栈的描述正确的是（）A、在栈中只能插入元素而不能删除元素B、在栈中只能删除元素而不能插入元素C、栈是特殊的线性表，只能在一端插入或删除D、栈是特殊的线性表，只能在一端插入元素，而字另一端删除元素9、下列叙述中正确的是（）A、一个逻辑数据结构只能有一种存储结构B、数据的逻辑结构属于线性结构，存储结构属于非线性结构C、一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D、一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据

6、处理的效率10、算法复杂度主要包括时间复杂度和（）复杂度。分析:1、算法的复杂度主要包括时间复杂度和空间复杂度.2、算法的时间复杂度：指执行算法所需要的计算工作量；3、算法的空间复杂度：指执行这个算法所需要的内存空间；4、算法的时间复杂度与空间复杂度并不相关。5、一棵二叉树第六层(根结点为第一层)的结点数最多为（）个。6、数据结构分为逻辑结构和存储结构，循环队列属于（）结构。11、按照”后进先出”原则组织数据的数据结构是（）A、队列B、栈C、双向链表D、二叉树12、下列叙述中正确的是（）A、线性链表是线性表的链式存储结构B、栈与队列是非线性结构C、双向链表是非线性结构D、

7、只有根结点的二叉树是线性结构分析：1、栈、队列和双向链表都是线性结构，而二叉树是非线性结构。2、线性结构和非线性结构是从数据的逻辑结构角度而言，与该数据结构中有多少个元素没有关系，即使是空二叉树也是非线性结构的。13、对如下二叉树进行后序遍历的结果为（）A、ABCDEFB、DBEAFCC、ABDECFD、DEBFCA分析：二叉树的遍历：就是按某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。1.前序遍历（根-左-右）2.中序遍历（左-根-右）3.后序遍历（左-右-根）ABCDEF14、在深度为7的满二叉树中,叶子结