公共的基础课件.pptVIP

* * * 二级考试基础辅导讲义 数据结构与算法 数据库基础 软件工程 面向对象的程序设计 本 节 要 点 数据结构 数据结构： 是指相互有关联的数据元素的集合。 数据结构包括： 数据的逻辑结构 数据的存储结构 逻辑结构： 线性（线性表、栈、队列） 非线性（树、二叉树、图） 存储结构 顺序 链式 如何区分线性和非线性？ 线性 一个数据节点只有一个前件和一个后件 非线性 一个数据节点有多个前件或多个后件 一种逻辑结构可通过多种逻辑结构来实现 （顺序）线性表 (链式)线性表 a b c d e f g h i data next 地址域 数据域 head 单链表 prev next head 左指针 数据域 右指针 双向链表 循环链表 （1）下列叙述中正确的是 　　A）有一个以上根结点的数据结构不一定是非线性结构 　　B）只有一个根结点的数据结构不一定是线性结构 　　C）循环链表是非线性结构 D）双向链表是非线性结构 （2）下列叙述中正确的是　　A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的　　B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构　　C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构　　D）上述三种说法都不对 （3）下列叙述中正确的是 A）顺序存储结构存储空间一定是连续的，链式存储结构存储空间不一定是连续 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表 D）链式存储结构比顺序存储结构节省存储空间 7 3 5 入栈 Top 栈顶 Bottom 栈底不动 入栈：5，3，7 出栈：7，3，5 特点：先进后出 （通常用顺序结构存储也可以用链式存储） 入栈出栈都在栈顶。栈底不动 栈：栈是只能在一端进行插入与删除运算的线性表。 （1）下列关于栈的叙述正确的是 A）栈按“先进先出”组织数据 B) 栈按“先进后出”组织数据 C）只能在栈底插入数据? D）不能删除数据 （2）一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是 A）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA （3）下列叙述中正确的是　　A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化　　B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化　　C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 D）上述三种说法都不对　 2 0 1 1 front 入队（增）：rear 移动 出队（删）：front 移动 5 3 7 队列： 头指针 尾指针 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。 rear front rear 循环队列元素个数: 若rearfront,则为 rear-front 若rearfront,则为 rear+队列容量-front 循环队列： a c b d rear front 5 4 3 2 1 9 7 8 6 设某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有? ?个元素。 设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有 个元素。 24 15 3、对于循环队列，下列叙述中正确的是（ ）。 A）队头指针是固定不变的 B）队头指针一定大于队尾指针 C）队头指针一定小于队尾指针 D）队头指针可以大于队尾指针，也可以小于队尾指针 4、下列叙述中正确的是 A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构 B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况 C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况 D）循环队列中元素的个数是由队头指针和队尾指针共同决定 树： 是一种简单的非线性结构。 所有数据元素之间的关系具有明显的层次特性。 结点的度 ：一个结点所拥有的后件的个数 树的度： 所有结点中最大的度 树的深度 ：树的最大层次 叶子结点 父结点 子结点 二叉树： 1）非空二叉树只