二级C公共基础部分讲座.doc

公共基础第一部分：数据结构与算法（约占10分）（理解）算法数据结构树与二叉树查找技术习题第二部分：程序设计基础（约占4分）（背）程序设计设计方法与风格结构化程序设计面向对象的程序设计习题第三部分：软件工程基础（约占8分）（背）软件工程的基本概念结构化分析方法结构化设计方法软件测试程序的调试习题第四部分：数据库设计基础（约占4分）（理解+背）数据库系统的基本概念数据模型关系代数数据库的设计与管理习题第一部分：数据结构与算法Main() Int i,sum;For(i=0;ifront时，容量是rear-font;(队列未满)当rearfront时，容量是m+(rear-font);(队列已满，并且已经返回)循环队列的运算1、 入队操作，在rear+1;2、 出队操作，在front+1线性表总结：在插入和删除时需要移动元素由于使用数组作为存储结构，所以空间不好扩展不便于对存储空间的动态分配故：对于大的线性数据结构和变动频繁的数据结构不适应使用线性存储结构链式结构线性表：存储方式：由两部分组成，一部分用来存储元素值，另一部分用来存储后一个（前一个）元素的位置。特点：存储数据元素之间的空间可以不连续；各节点之间的存储关系与元素的顺序可以不一致；可以顺序用结构存储，也可以使用链式结构结构存储头指针；最后一个节点的指针为null，当头指针为null是表示该表为空表单链表：只有next指针双向链表：有pre指针和next指针循环链表：删除和插入时都不需要移动元素习题：1、不属于线性结构的是：A、队列 B、线性表 C、二叉树 D、栈 2、数据的存储结构是指A、存储在外存的数据 B、数据所占的存储空间量C、数据在计算机中的顺序存储方式 D、数据的逻辑结构在计算机中的表示 3、下列关于栈描述错误的是：A、栈是先进后出的线性表 B、栈只是顺序存储的C、栈具有记忆作用 D、对栈的插入与删除不改变栈底指针 4、下列对于线性链表的描述正确的是A、存储空间不一定是连续的，且各个元素的顺序是任意的B、存储空间不一定是连续的，且前一个元素一定存储在后一个元素的前面C、存储空间必须是连续的，且前一个元素一定存储在后一个元素的前面D、存储空间必须是连续的，且各个元素的顺序是任意的 5、下列关于栈的描述正确的是：A、在栈中只能插入元素不能删除元素B、在栈中只能删除元素不能插入元素C、栈是特殊的线性表，只能在一端插入和删除元素D、栈是特殊的线性表，只能在一端插入元素，在另一端删除元素 6、下列叙述正确的是：A、一种逻辑结构只能有一种存储结构B、数据的逻辑结构属于线性结构，数据的存储结构属于非线性结构C、一个逻辑结构可以有多种存储结构，且不同的存储结构不影响程序的效率D、一个逻辑结构可以有多种存储结构，且不同的存储结构会影响程序的效率 7、按照后进先出的原则组织数据的是A、队列 B、栈 C、双向链表 D、二叉树 8、下列叙述正确的是A、线性链表是线性表的链式存储结构 B、栈和队列是非线性存储结构C、双向链表是非线性存储结构 D、只有根节点的二叉树是线性结构9、栈的运算特点是后进先出。元素a、b、c、d依次入栈，则不能得到的出栈序列是 （） 。A. a b c d B. c a b d C. d c b a D. b c d a 10、数据结构分为逻辑结构和存储结构，循环队列属于 11、数据的逻辑结构在计算机空间的存放形式称为数据的 12、按“先进后出”原则组织数据的是 13、数据结构分为线性结构和非线性结构，带链队列属于 三、 树和二叉树：树是非线性结构基本概念结点：若干个指向子树的分支结点的度：某结点拥有子结点的个数树的度：树中所有结点度的最大值叶子结点：度为0结点分支结点：度不为0的结点结点的层次（深度）：根为第一层，根的结点为第二层，依次类推树的深度：树中结点的最大层次称为树的深度二叉树：分支节点的度最多为2二叉树的基本性质：1、在二叉树的第k层上，最多有2k-1个节点2、在深度为m的二叉树中，最多有2m-1个结点3、在任意一棵二叉树中，度为0的节点的总比度为2的节点多一个4、具有n个结点的二叉树，其深度至少为log2n+1满二叉树和完全二叉树1、 满二叉树：除了最后一层，每一层都有两个结点2、 完全二叉树（左子树一直存在）注意：二叉树的存储结构中，除了可以将满二叉树和完全二叉树按层次顺序结构存储之外，其余均只能使用链式存储。二叉树的遍历：前序遍历：根，左，右中序遍历：左，根，右后序遍历：左，右，根习题：1、 在一棵二叉树上，第五层的结点最多有几个A、8 B、16 C、32 D、152、 某二叉树中度为2的结点有18个，度为0的结点有 3、 一棵二叉树第六层的结点最多有几个 4、 在深度为7 的满二叉树中，叶子结点有 个GDAECF5、 下图三种遍历的结果B四、 查找技术：顺序查找和二分查找二分查找：只有顺序存储的有序表才能使用二分查找运行效率：顺序查找：n,二分查找:log2n排序:习题：1、 长度为n的线性表，在最坏的情况下，下列各排序法对应的比较次数中正确的是A、冒泡排序为n/2 B、冒泡排序为n C、快速排序为n D、快速排序为(n(n-1)/22、 对长度为n的线性表进行顺序查找，在最坏的情况下需要比较多少次A、log2n B、n/2 C、n D、n+13、 数据结构中能够用二分法进行查找的是A、顺序存储结构的有