数据结构与算法题20091121 1100 [算法整理 ].doc

数据结构与算法笔试题2009/11/21 11:00 [算法整理 ] 第一章 数据结构与算法 一.算法的基本概念 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。 2.算法的基本要素：算法中对数据的运算和操作、算法的控制结构。 3.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。 4.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求 二.算法的复杂度 1.算法的时间复杂度：指执行算法所需要的计算工作量 2.算法的空间复杂度：执行这个算法所需要的内存空间 三.数据结构的定义 1.数据的逻辑结构：反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。 2.数据的存储结构：数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等存储结构。 四.数据结构的图形表示： 在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点。插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。 五.线性结构和非线性结构 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构和非线性结构。 线性结构：非空数据结构满足：有且只有一个根结点；每个结点最多有一个前件，最多只有一个后件。非线性结构：如果一个数据结构不是线性结构，称之为非线性结构。 常见的线性结构：线性表、栈、队列 六.线性表的定义 线 性表是n 个元素构成的有限序列（A1，A2，A3……）。表中的每一个数据元素，除了第一个以外，有且只有一个前件。除了最后一个以外有且只有一个后件。即线性表 是一个空表，或可以表示为（a1,a2,……an）, 其中ai I 1,2,……n 是属于数据对象的元素，通常也称其为线性表中的一个结点。 非空线性表有如下一些特征： （1）有且只有一个根结点a1,它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n 0时称为空表。 七.线性表的顺序存储结构 线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。 线性表的顺序存储结构具备如下两个基本特征： 1.线性表中的所有元素所占的存储空间是连续的； 2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 即线性表逻辑上相邻、物理也相邻，则已知第一个元素首地址和每个元素所占字节数，则可求出任一个元素首地址。 假设线性表的每个元素需占用K个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC ai+1 和第i个数据元素的存储位置LOC ai 之间满足下列关系: LOC ai+1 LOC ai +K LOC ai LOC a1 + i-1 *K ① 其中，LOC a1 是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。 因为在顺序存储结构中，每个数据元素地址可以通过公式①计算得到，所以线性表的顺序存储结构是随机存取的存储结构。 在线性表的顺序存储结构下，可以对线性表做以下运算： 插入、删除、查找、排序、分解、合并、复制、逆转 八.顺序表的插入运算 线性表的插入运算是指在表的第I个位置上，插入一个新结点x，使长度为n的线性表（a1,a2 …ai…an）变成长度为n+1的线性表 a1,a2…x,ai…an . 该算法的时间主要花费在循环的结点后移语句上，执行次数是n-I+1。 当I n+1,最好情况，时间复杂度o 1 当I 1, 最坏情况，时间复杂度o n 算法的平均时间复杂度为o n 九.顺序表的删除运算 线性表的删除运算是指在表的第I个位置上，删除一个新结点x，使长度为n的线性表（a1,a2 …ai…an）变成长度为n-1的线性表 a1,a2…ai-1,ai+1…an . 当I n,时间复杂度o 1 ,当I 1,时间复杂度o n ,平均时间复杂度为o n 十.栈及其基本运算 1. 什么是栈？ 栈实际上也是一个线性表，只不过是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶（TOP），另一端为 栈底（BOTTOM）。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后 才能被删除的元素。 假设栈S （a1,a2,a3,……an），则a1 称为栈底元素，an称为栈顶元素。栈中元素按a1,a2,a3……an的次序进栈，退栈