C语言公共基本知识点.ppt

公共基础知识 算法 算法的概念 是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程。 算法的基本特征 确定性 有穷性 可行性 输入(=0个)，输出(=1个)。 算法 算法的三种基本控制结构 顺序结构 选择结构 循环结构 算法效率的度量—算法复杂度 时间复杂度：指执行算法所需要的计算工作量。 空间复杂度：指执行这个算法所需要的内存空间。 （2009-09-4）算法的空间复杂度是指（A ）。 A）算法在执行过程中所需要的计算机存储空间 B）算法所处理的数据量 C）算法程序中的语句或指令条数 D）算法在执行过程中所需要的临时工作单元数 （2008-04-5）算法的有穷性是指（A ）。 A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用 （2006-09-7）下列叙述中正确的是（ D ）。 A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对 （2005-09）算法复杂度主要包括时间复杂度和【空间】复杂度。 （2005-04）问题处理方案的正确而完整的描述称为【算法】。 数据结构 数据的逻辑结构 线性结构（链表、队列、堆栈） 非线性结构（树、图） 数据的存储结构(物理结构) 顺序存储：逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现 链式存储：不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的 线性结构 存在唯一的被称为“第一个”的数据元素 存在唯一的被称为“最后一个”的数据元素 除第一个外，每个元素只有一个前驱 除最后一个外，每个元素只有一个后继 线性表的顺序存储 线性表的链式存储---链表 栈 只允许在栈顶操作 先进后出 队列 队尾进，队首进 先进先出 （2005-04-1）数据的存储结构是指（ D ）。 A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示 （2005-04-5）下列对于线性链表的描述中正确的是（ A ） A）存储空间不一定是连续, 且各元素的存储顺序是任意的 B）存储空间不一定是连续, 且前件元素一定存储在后件元素的前面 C）存储空间必须连续, 且前件元素一定存储在后件元素的前面 D）存储空间必须连续, 且各元素的存储顺序是任意的 （2009-09-2）下列数据结构中,能够按照“先进后出”原则存取数据的是（B ）。 A）循环队列 B）栈 C）队列 D）二叉树 （2008-09）一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（B ）。 A）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA 树 二叉树 每一个结点最多有两棵子树 性质： 在二叉树的第k层上，最多有2k-1(k≥1)个结点； 深度为m的二叉树最多有2m-1个结点； 叶子结点总是比度为2的结点多一个 满二叉树 最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点,深度为m的满二叉树有2m-1个结点。 往年真题 （2006-04-7）在深度为7的满二叉树中，叶子结点的个数为（C ）。 A）32 B）31 C）64 D）63 （2009-03-3）某二叉树有5个度为2的结点,则该二叉树中的叶子结点数是（C ）。 A）10 B）8 C）6 D）4 （2007-09-8）一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（ A ） A）219 B）221 C）229 D）231 （2007-04）某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为（ A）。 A）n+1 B）n-1 C）2n D）n/2 二叉树的遍历 先序遍历 访问根结点 先序遍历左子树 先序遍历右子树 中序遍历 中序遍历左子树 访问根结点 中序遍历右子树 后序遍历 后序遍历左子树 后序遍历右子树 访问根结点 往年真题 （2007-04） A）DYBEAFCZX B）YDEBFZXCA C）ABDYECFX