Ⅰ 数据结构与算法教程的目 录
第1章绪论11.1预备知识11.1.1集合的笛卡儿积11.1.2二元关系21.1.3二元关系的基本性质和几种重要关系31.2什么是数据结构41.2.1从实际问题理解数据结构41.2.2数据结构所讨论的内容61.2.3如何表示数据结构91.3抽象数据类型101.3.1什么是抽象数据类型101.3.2抽象数据类型的定义与实现121.4算法与算法分析131.4.1什么是算法131.4.2算法描述151.4.3常用的算法设计方法161.4.4算法分析21习题24上机练习题26第2章线性表的顺序存储及其运算272.1线性表的概念272.1.1 什么是线性表272.1.2线性表的抽象数据类型292.2顺序表及其运算实现302.2.1线性表的顺序存储——顺序表302.2.2顺序表的基本运算312.2.3顺序表应用例——求子集362.3栈362.3.1什么是栈372.3.2栈的抽象数据类型392.3.3顺序栈及其运算392.4栈应用422.4.1栈在优先级处理中的应用422.4.2栈与分治法482.4.3栈与回溯法502.4.4栈与递归552.5队列632.5.1队列及其抽象数据类型632.5.2顺序队列及其运算642.5.3队列应用例68* 2.5.4优先队列722.6数组与特殊矩阵的表示742.6.1数组的顺序存储742.6.2规则矩阵的压缩存储76* 2.6.3稀疏矩阵的三列二维数组表示——三元组顺序表78习题81上机练习题82第3章链表833.1线性表的链式存储——线性链表833.1.1线性链表的结构特点833.1.2线性链表的运算843.2链式栈与链式队列913.2.1栈的链式存储——链式栈913.2.2队列的链式存储——链式队列953.3循环链表983.3.1循环链表的结构特点983.3.2循环链表的基本运算993.3.3链表应用例103*3.4多重链表1093.4.1多重链表结构1093.4.2双向链表110*3.5广义表1123.5.1什么是广义表1133.5.2广义表的存储表示1143.5.3广义表的基本运算116习题120上机练习题121第4章树与二叉树1224.1树的基本概念1224.1.1 什么是树1224.1.2树的性质1274.2二叉树1284.2.1什么是二叉树1284.2.2二叉树的基本性质1284.2.3二叉树的抽象数据类型1314.2.4二叉树的存储结构1314.2.5二叉树的遍历及其他运算133* 4.2.6线索二叉树1384.3二叉树应用1414.3.1表达式线性化1414.3.2最优二叉树1434.3.3二叉搜索树1484.3.4堆154* 4.3.5二叉树与减治法1604.4树的运算1634.4.1树的抽象数据类型1634.4.2树的存储结构1644.4.3树的遍历165* 4.4.4树的其他运算167* 4.5树与回溯法1704.5.1问题解的描述——解空间树1714.5.2回溯法的求解过程分析——遍历解空间树1724.5.3回溯法求解问题的形式化描述174* 4.6森林的遍历1764.6.1森林与二叉树的转换1764.6.2森林的遍历177习题178上机练习题179第5章图1805.1图的基本概念1805.1.1图的定义和概念1805.1.2图的抽象数据类型184*5.1.3欧拉路径1855.2图的存储结构1865.2.1图的邻接矩阵表示1865.2.2图的邻接表表示189*5.2.3图的其他表示方法1925.3图的遍历1955.3.1图的深度优先遍历1955.3.2图的广度优先遍历1975.3.3图遍历的应用198*5.3.4图的连通性200*5.4有向图与有向无环图2015.4.1有向图的连通性和传递闭包202*5.4.2有向无环图和拓扑排序204*5.4.3关键路径2075.5最小生成树2085.5.1图的生成树与最小生成树2095.5.2普里姆(Prim)算法2105.5.3克鲁斯卡尔(Kruskal)算法2135.5.4贪心算法2155.6最短路径问题2185.6.1单源最短路径2185.6.2全源最短路径2205.6.3动态规划算法2235.7图应用例——城市间公路交通网问题2275.7.1问题描述2275.7.2问题求解思路228习题228上机练习题230第6章查找2316.1线性查找表2316.1.1顺序查找2326.1.2折半查找232*6.1.3斐波那契查找2346.1.4线性查找表的性能比较2346.2二叉搜索树查找性能2356.3AVL树2366.3.1BST的旋转操作2376.3.2AVL树的插入和平衡化旋转238*6.3.3AVL树的删除240*6.3.4AVL树的性能2416.4B-树2426.4.1多路动态搜索树2426.4.2B-树的查找2436.4.3B-树的插入244*6.4.4B-树的删除2456.5散列方法2466.5.1散列技术2466.5.2散列函数2476.5.3冲突处理2506.5.4散列的删除2526.5.5散列的性能2526.6静态索引结构2536.6.1索引查找2536.6.2索引存储方式254*6.6.3索引文件结构2556.7模式匹配2586.7.1字符串及其ADT2586.7.2字符串的存储表示2596.7.3字符串的模式匹配及简单匹配算法2596.7.4字符串匹配的KMP算法260习题263上机练习题264第7章排序2657.1排序的概念及算法性能分析2657.2基本排序方法2667.2.1冒泡排序2677.2.2插入排序2687.2.3直接选择排序2727.2.4基本排序方法的比较2737.3快速排序2747.3.1快速排序的过程2747.3.2快速排序的性能分析2757.4归并排序2767.4.1二路归并2767.4.2自底向上的归并排序2767.4.3自顶向下的归并排序278*7.5锦标赛排序2797.6堆排序2807.6.1堆排序的思想2807.6.2堆排序的实现2827.7内排序方法分析283*7.7.1排序方法的下界2837.7.2内排序方法的比较2847.8线性时间复杂度的排序算法285*7.8.1计数排序2857.8.2基数排序2877.9外部排序2907.9.1外部排序方法290*7.9.2基于败者树的k路归并方法291*7.9.3排序——归并的改进292习题296上机练习题297实验指导298实验一顺序表及其应用299实验二求解迷宫问题301实验三简单算术表达式的处理302实验四求解简单背包问题303实验五链表及其应用304实验六实验室机时机位的管理305实验七实现Huffman编码307实验八文件管理的模拟309实验九求网络站点间的最短连接312实验十查找最高分与次高分314实验十一比赛日程安排与成绩统计316
Ⅱ 有没有人知道计算机二级vf的辅导教程 或者 学习材料 及计算机二级考试的步骤
计算机二级vf，是上午考笔试，下午考机试。下面是笔试的公共基础材料。此外，你笔试还需做一套试卷。 机试的题库，你把邮箱号给我，我给你发过去。希望能对你有所帮助。。。公共基础知识第一章 数据结构与算法 (P1—P38) 1.1 算法 1.1.1 算法的基本概念 (P1—P4) 所谓算法是指解题方案的准确完整的描述。 1. 算法的基本特征 (1)可行性(2)确定性(3)有穷性(4)拥有够的情报 2. 算法的基本要素 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。 (1) 算法中对数据的运算和操作 (插入、删除) (2) 算法的控制结构 一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。 1.1.2 算法复杂度(P4—P6) 算法的复杂度主要包括时间复杂度和空间复杂度。 1． 算法的时间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。 2. 算法的空间复杂度 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 1.2数据结构的基本概念 数据结构，主要研究和讨论以下三个方面的问题： ① 数据的逻辑结构； ② 数据的存储结构； ③ 对各种数据结构进行的运算。(插入、删除) 主要目的是为了提高数据处理的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，(时间复杂度)二是尽量节省在数据处理过程中所占用的计算机存储空间。(空间复杂度) 1.2.1什么是数据结构 (P6—P11) 1. 数据的逻辑结构 所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。 2. 数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称为数据的物理结构) 一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。 1.2.3线性结构与非线性结构 (P12) 一般将数据分为两大类型：线性结构与非线性结构。 线性结构又称线性表 如果一个数据结构不是线性结构，则称之为非线性结构。1.3线性表及其顺序存储结构 1.3.1线性表的基本概念 (P12—P13) 线性表是由n (n≥0)个数据元素a1，a2，…，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为。 (a1,a2,…,ai,…,an) 非空线性表有如下一些结构特征： ① 有且只有一个根结点a1，它无前件； ② 有且只有一个终结点an，它无后件； ③ 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 1.3.2线性表的顺序存储结构 (P13—P14) 在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。 线性表的顺序存储结构具有以下两个基本特点： ① 线性表中所有元素据所占的存储空间是连续的； ② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 假设线性表中的第一个数据元素的存储地址为ADR(a1)，每一个数据元素占K个字节，则线性表中第i 个元素ai在计算机存储空间中的存储地址为 ADR(a1)=ADR(a1)+(i-1)K 1.3.3顺序表的插入运算 (P14—P15) 在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的。 1.3.4顺序表的删除运算 (P15—P16) 在平均情况下，要在线性表中删除一个元素，需要移动表中表中一半的元素。因此，在线性表顺序存储的情况下，要删除一个元素，其效率也是很低的。 由线性表在存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单。但这种顺序存储的方式对于元素经常需要变动的大线性表就不太合适了，因为插入删除的效率比较低。1.4栈和队列 1.4.1栈及其基本运算 (P16—P18) 1.什么是栈 栈是限定在一端进行插入与删除的另一端称为栈底。即栈是按照“先进后出”(FILO)或“后进先出”(LIFO)的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。 2.栈的顺序存储及其运算(采用顺序存储结构的栈称为顺序栈) 栈的基本运算有三种：入栈、退栈与读栈顶元素。 (1) 入栈运算(2)退栈运算(3)读栈顶元素 1.4.2队列及其基本运算 (P18—P20) 1.什么是队列 队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针(rear)的指针指向队尾元素，一端称为排头(也称为队头)通常也用一个排头指针(front)指向排头元素的前一个位置。 队列双称为“先进先出”或“后进后出”的线性表。 3. 循环队列及其运算 在实际应用中，队列的顺序存储结构一般采用循环队列的形式。 所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。 1.5线性链表 1.5.1线性链表的基本概念 (P20—P23) 由于线性表的顺序存储结构存在以上这些缺点，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用下面要介绍的链式存储结构。 在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。 在链式存储结构中，存储数据结构的存储空间可以下连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 链式存储方式既可用于表示线性结构，也可以用于表示非线性结构。 1. 线性链表 线性表的链式存储结构称为线性链表。 2. 带链的栈 栈也是线性表，也可以采用链式存储结构。 3. 带链的队列 与栈类似，队列也是线性表，也可以采用链式存储结构。 1.5.2线性链表的基本运算 (P23—P25) 线性链表在插入过程中不发生数据元素移动的现象，只需改变有关结点的指针即可，从而提高了插入的效率。 从线性链表的删除过程可以看出，在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。 1.5.3循环链表及其基本运算 (P25—P26) 循环链表具有以下两个特点： (1) 在循环链表中增加了一个表头结点，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。 (2) 循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。 1. 6树与二叉树 1.6.1树的基本概念 (P26—P28) 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。 在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件个数称为该结点的度 在树中，所有结点中的最大的度称为树的度。 根结点在第1层。 树的最大层次称为树的深度。 1.6.2二叉树及其基本性质 (P28—P31) 1. 什么是二叉树 二叉树具有以下两个特点： ① 非空二叉树只有一个根结点； ② 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 2. 二叉树的基本性质 性质1在二叉树的第K层上，最多有2K-1(K≥1)个结点。 性质2深度为m的二叉树最多有2m-1个结点。 性质3在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。 3. 满二叉树与完全二叉树 (1)满二叉树 所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点，这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第K层上有2K-1个结点，且深度为m的满二叉树有2m-1个结点。 (2)完全二叉树 所谓完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边若干结点。 满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。 性质6设完全二叉树共有n个结点。从根结点开始，按层序用自然数1,2，…，n给结点进行编号，则对于编号为k(k=1,2,…,n)的结点有以下结论： ① 若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)。 ② 若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点。 ③ 若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。 1.6.3二叉树的存储结构 (P31—P32) 在计算机中，二叉树通常采用链式存储结构。 1.6.4二叉树的遍历 (P32—P33) 二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。 1. 前序遍历(DLR) 2. 中序遍历(LDR) 3. 后序遍历(LRD) 1.7查找技术 1.7.1顺序查找 (P33) 顺序查找又称顺序搜索。 对于大的线性表来说，顺序查找的效率是很低的。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找： (1) 线性表无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。 (2) 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 1.7.2二分法查找 (P33—P34) 二分法查找只适用于顺序存储的有序表。 显然，当有序线性表为顺序存储时都能采用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。1.8排充技术 1.8.1交换类排序法 (P34—P35) 1. 冒泡排序法 冒泡排序法是一种最简单的交换类排序方法。 假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为n(n-1)/2。 2. 快速排序法 快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。 1.8.2插入类排序法 (P35—P37) 1. 简单插入排序法 自以为插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。 在简单插入排序法中，这种排序方法的效率与冒泡排序法相同。在最坏情况下，证券交易插入排序需要n(n-1)/2次比较。 2. 希尔排序法 希尔排序法属于插入类排序，但它对简单插入排序做了较大的改进。 1.8.3选择类排序法 (P37—P38) 1. 简单选择排序法 从中选出最小的元素，将它交换到表的最前面。 简单选择排序法在最坏情况下需要比较n(n-2)/2次。 2. 堆排序法 堆排序法属于选择类的排序方法。 堆排序的方法对于规模较小的线性表并不合适，但对于较大规模的来说是很有效的。第2章 程序设计基础 (P40—P45)2.1程序设计方法与风格 程序设计的风格总体而言应该强调简单和清晰，程序必须是可以理解的。可以认为，著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。 源程序文档化应考虑如下几点： (1) 符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。 (2) 程序注释：正确的注释能够帮助读者理解程序。注释一般分为序言性注释和功能性注释。 (3) 视觉组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。 2.2结构化程序设计 2.2.1结构化程序设计的原则 (P41—P42) 结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句。 2.2.2结构化程序的基本结构与特点 (P42—P43) 1. 顺序结构 2. 选择结构：选择结构又称为分支结构。 3. 重复结构：重复结构又称为循环结构。 2.3面向对象的程序设计 今天面向对象方法已经发展成为主流的软件开发方法。 一些著名的面向对象语言(如C++、Java) 2.3.2面向对象方法的基本概念 (P45—P48) 1. 对象 对象是面向对象方法中最基本的概念。对象可以用来表示客观世界中的任何实体。 面向对象的程序设计方法中涉及的对象由一组表示其静态特征的属性和它可执行的一组操作组成。 (4) 封装性。 2. 类(Class)和实例(Instance) 将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共同方法方法的对象的集合。所以，类是对象的抽象，而一个对象则是其对应类的一个实例。 3. 消息 对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。消息是一个实例与另一个实例之间传递的信息。 4. 继承 继承是面向对象的方法的一个主要特征。 第3章 软件工程基础3.1软件工程基本概念 3.1.1软件定义与软件特点 (P50) 计算机软件是包括程序、数据及相关文档的完整集合。 可见软件由两部分组成：一是机器可执行和程序和数据；二是机器不可执行的，与软件开发、运行、维护、使用等有关的文档。 软件的特点： ① 软件是一种逻辑实体，而不是物理实体，具有抽象性。 ② 软件的生产与硬件不同，它没有明显的制作过程。 ③ 软件在运行、使用期间不存在磨损、老化问题。 ④ 软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题。 ⑤ 软件复杂性高，成本昂贵。 ⑥ 软件开发涉及诸多的社会因素。 3.1.2软件危机与软件工程 (P51—P52) 软件工程概念的出现源自软件危机。 20世纪60年代末以后，“软件危机”。所谓软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。 1968年在北大西洋公约组织会议(NATO会议)上，讨论摆脱软件危机的办法，软件工程作为一个概念首次被提出。 软件工程包括个要素，即方法、工具和过程。 3.1.3软件工程过程与软件生命周期 (P52—P53) 2.软件生命周期 通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。 3.1.4软件工程的目标与原则(P53—P54) 1. 软件工程的目标 软件工程内容主要包括：软件开发技术和软件工程管理。 3.1.5软件开发工具与软件开发环境 (P54) 1. 软件开发工具 (VB、VC++、VFP) 2. 软件开发环境 软件开发环境或称软件工程环境是全面支持软件开发全过程的软件工具集合。 计算机辅助软件工程(CASE) 3.2结构化分析方法 3.2.1需求分析与需求分析方法 (P53—P59) 1. 需求分析 (1) 需求分析阶段的工作 需求分析阶段的工作，可以概括为四个方面： ① 需求获取 ② 需求分析 ③ 编写需求规格说明书 ④ 需求评审 2. 需求分析方法 常见的需求分析方法有： ① 结构化分析方法。主要包括：面向数据流的结构化分析方法(SA)面向数据结构的Jackson方法(JSD)面向数据结构的结构化数据系统开发方法(DSSD) ② 面向对象的分析方法(OOA) 3.2.2结构化分析方法 (P55—P59) 2.结构化分析的常用工具 (1) 数据流图(DFD) (2) 数据字典(DD) 数据字典是结构化分析方法的核心。 (3) 判定树 (4) 判定表 3.2.3软件需求规格说明书 (P59—P60) 软件规格说明书(SRS)是需求分析阶段的最后成果，是软件开发中的重要文档。 软件需求规格说明书的作用是： ① 便于用户、开发人员进行理解和交流。 ② 反映出用户问题的结构，可以作为软件开发工作的基础和依据 ③ 作为确认测试和验收的依据。3.3结构化设计方法 3.3.1软件设计基本概念 (P60—P62) 1.软件设计的基础 软件设计分两步完成：概要设计和详细设计。 2.软件设计的基本原理 (1) 抽象 (2) 模块化 (3) 信息隐蔽 (4) 模块独立性 模块独立程度是评价设计好坏的重要度量标准。衡量软件的模块独立软件的模块独立性使用耦合性和内聚性两个定性的度量标准。 ① 内聚性：内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。 ② 耦合性：耦合性是模块间互相连接的紧密程度的度量。 耦合性与内聚性是模块独立性的两个定性标准，耦合与内聚是相互关联的。在程序结构中，各模块的内聚性越强，则耦合性越弱。一般较优秀的软件设计，应尽量做到高内聚，低耦合。 3.3.3详细设计 (P67—P71) 几种主要的工具： 1. 程序流程图(PFD) 2. N-S (盒图) 3. PAD图 PAD图是问题分析图(Problem Analysis Diagram)的英文缩写。 4. PDL 过程设计语言(PDL)也称为结构化的英语和伪码。3.4软件测试 软件测试的投入，通常其工作量、成本占软件开发总工作量、总成本的40%以上。 软件测试是保证软件质量的重要手段，其主要过程涵盖了整个软件生命期的过程。 3.4.1软件测试的目的 (P71) 关于软件测试的目的，软件测试是为了发现错误而执行程序的过程。 3.4.3软件测试技术与方法综述(P71—P77) 可以分为静态测试和动态测试方法。若按照功能划分可以分为白盒测试和黑盒测试方法。 1. 静态测试与动态测试 (1) 静态测试 静态测试可以由人工进行，充分发挥人的逻辑思维优势。 (2) 动态测试 静态测试不实际运行软件，主要通过人工进行。动态测试是基于计算机的测试，是为了发现错误而执行程序的过程。 2. 白盒测试 白盒测试方法也称结构测试或逻辑驱动测试。 3. 黑盒测试方法 黑盒测试方法也称功能测试或数据驱动测试。黑盒测试是对软件已经实现的功能是否满足需求进行测试和验证。黑盒测试完全不考虑程序内部和逻辑结构和内部特性。 3.4.4软件测试的实施(P77—P80) 软件测试是保证软件质量的重要手段。 软件测试过程一般按4个步骤进行， 1. 单元测试 单元测试是对软件设计的最小单位——模块(程序单元)进行正确性检验的测试。 2. 集成测试 集成测试是测试和组装软件的过程。 3. 确认测试 4. 系统测试 3.5程序的调试 3.5.1基本概念 (P80—P81) 程序调试的任务是诊断和改正程序中的错误。它与软件测试不同，软件测试是尽可能多地发现软件中的错误。 软件测试贯穿整个软件生命期，调试主要在开发阶段。 3.5.2软件调试方法 (P81—P82) 1. 强行排错法 2. 回溯法 3.原因排除法 第4章 数据库设计基础 (P84—P111) 4.1数据库系统的基本概念 4.1.1数据、数据库、数据库管理系统 (P84—P87) 1. 数据 数据(Data)实际上就是描述事物的符号记录。 2. 数据库 数据库(简称DB)是数据的集合。 3. 数据库管理系统 数据库管理系统(简称DBMS)它是一种软件。 数据库管理系统是数据库系统的核心。 目前流行的DBMS均为关系数据库系统，如微软的Visual FoxPro和Access等。 4. 数据库管理员(简称DBA) 5. 数据库系统 数据库系统(简称DBS)由如下几部分组成：数据库(数据)、数据库管理系统(软件)、数据库管理员(人员)、系统平台之一____硬件平台(硬件)、系统平台之二——软件平台(软件)这五个部分构成了一个以数据库为核心的完整的运行实体，称为数据库系统。 4.1.2数据库系统的发展 (P87—P88) 数据管理发展至今已经历了三个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。 1. 关系数据库系统阶段 4.1.3数据库系统的基本特点 (P88—P890) 数据库系统具有以下特点： 1. 数据的集成性 2. 数据的高共享性与低冗余性 3. 数据独立性 数据独立性是数据与程序间的互不依赖性，数据独立性一般分为物理独立性与逻辑独立性两级。 (1) 物理独立性：物理独立性即是数据的物理结构的改变，从而不致引起应用程序的变化。 (2) 逻辑独立性：数据库总体逻辑结构的改变，不需要相应修改应用程序，这就是数据 的逻辑独立性。 4. 数据统一管理与控制 4.1.4数据库系统的内部结构体系 (P89—P91) 1. 数据库系统的三级模式 (1) 概念模式。概念模式是数据库系统中全局数据逻辑结构的描述，是全体用户(应用)公共数据视图。 (2) 外模式。外模式也称子模式或用户模式。它是用户的数据视图。 (3) 内模式。内模式又称物理模式，它给出了数据库物理存储结构与物理存取方法。 2. 数据库系统的两级映射 (1) 概念模式到内模式的映射。 (2) 外模式到概念模式的映射。 4.2数据模型 4.2.1数据模型的基本概念 (P91) 数据模型按不同的应用层次分成三种类型，它们是概念数据模型、逻辑模型、物理数据模型， 概念模型有E-R模型、逻辑数据模型又称数据模型， 层次模型、网状模型、关系模型， 物理数据模型又称物理模型。 1.2.2 E-R模型 (P91—P95) 概念模型是E-R模型(或实体联系模型) 1.E-R模型的基本概念 (1)实体 现实世界中的事物可以抽象成为实体 (2)属性 现实世界均有一些特性，这些特性可以用属性来表示。属性刻画了实体的特征。 (3)联系 一对一的联系，简记为1：1。 一对多或多对一联系，简记为1：M(1：m)或M：1(m：1)。 多对多联系，简高为M：N或m:n。 3.E-R模型的图示法 在E-R图中用椭圆形表示属性。 在E-R图中用菱形表示联系。 4.2.3层次模型的基本结构是树形结构 (P95) 4.2.4网状模型 (P95—P96) 网状模型是一个不加任何条件限制的无向图。 4.2.5关系模型 (P96—P98) 1.关系的数据结构 关系模型采用二维表来表示。4.3关系代数 (4)查询 ① 投影运算 ② 选择运算 ③ 笛卡尔积运算 则关系R与S经笛卡尔积记为R×S。 3.关系代数中的扩充运算 (1)交运算 (还有并和差) 关系R与S经交运算后所得到的关系是由那些既在R内又在S内的有序组成，记为R∩S。 (2)除运算 如果将笛卡尔积运算看作乘运算的话，那么除运算就是它的运算。 T÷R=S或R/R=S 4.4数据库设计与管理 数据库设计是数据库应用核心。 4.4.1数据库设计概述 (P104) 整个数据库应用系统的开发成目标独立的若干阶段。它们是：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段。 4.4.2数据库设计的需求分析 (P104—P105) 4.4.3数据库概念设计 (画E-R图) (P105—P108) 4.4.4数据库的逻辑设计 (P108—P109) 1. 从E-R图向关系模式转换。 4.4.5数据库的物理设计 (P110)
Ⅲ pascal 教程
第一章 Pascal入门第一节 Pascal语言的特点 信息学奥林匹克竞赛是一项益智性的竞赛活动，核心是考查参赛选手的智力和使用计算机编程解题的能力。信息学奥林匹克竞赛要求参赛选手有如下能力：针对竞赛题目中的要求构建数学模型，构造出有效的算法和选用相应的数据结构，写出高级语言程序，上机调试通过。程序设计是信息学奥林匹克竞赛的基本功，因此，青少年参与竞赛活动的第一步是必须掌握一门高级语言及其程序设计方法。以纪念法国数学家而命名的Pascal语言是使用最广泛的计算机高级语言之一，被国际上公认为程序设计教学语言的典范。其主要特点有：严格的结构化形式；丰富完备的数据类型；运行效率高；查错能力强。正因为这些特点，Pascal语言可以被方便地用于描述各种数据结构和算法，编写出高质量的程序。尤其是对于青少年程序设计初学者，Pascal语言有利于顺利入门，有益于从一开始培养良好的程序设计风格和习惯，越来越多的各类学校都把Pascal语言作为程序设计教学的第一语言。IOI（国际奥林匹克信息学竞赛）把Pascal语言规定为二种程序设计语言之一，NOI(全国信息学奥林匹克竞赛)把Pascal语言定为唯一提倡的程序设计语言，NOIp（全国信息学奥林匹克联赛）把Pascal定为最主要的程序设计语言。 Pascal语言有多种版本，本教材采用的Turbo Pascal 7.0（或Borland Pacsal 7.0） 是目前PC机上使用最多的一种高效Pascal，是迄今为止DOS环境下的最高版本。Turbo Pascal 7.0 所需硬件环境是任意型号的PC机，并且仅需一台1.44M软盘驱动器(当然有其他条件更好)；最小软件系统包括Turbo.exe(集成环境)和Turbo.tpl(标准单元库)两个文件，如果包括Turbo.hlp(求助文件)则更有利于学习。Turbo Pascal 7.0可以工作在DOS操作系统或Windows操作系统环境下。 第二节 turbo Pascal 集成环境 Pascal语言是编译型程序语言，一般需经过编辑、编译、链接、运行几个步骤方可得到结果，这些步骤是一个反复的过程，这对于初学者来说很不方便。Turbo Pascal提供了一个称为集成环境的工作系统，它集编辑、编译、调试、运行等功能于一体，对初学者学习十分方便。在DOS提示符状态下，键入TURBO↙，即可进入Turbo Pascal 集成环境，这时的屏幕显示如图。按任意键就可进入Pascal编辑处理状态。在Windows环境下运行时，最好先建立一个快捷方式，并在“属性”设置中，选择“程序”中的“高级”选项，去除“MS-DOS方式”。以后你运行Turbo Pascal的时候，只要双击那个已建立的快捷方式就可以直接在Windows下运行Turbo Pascal。启动后的界面见图一。在屏幕顶行是主菜单，包括以下十项子菜单： File 文件 Edit 编辑 Search 搜索 Run 运行 Compile 编译 Debug 调试 Tools 工具 Option 选项 Window 窗口 Help 帮助用下述方法之一进入相应的子菜单：1、 用F10功能键进入主菜单，按“←”、“→”将光标移至子菜单处，回车。 2、用F10功能键进入主菜单，按子菜单命令的首字母F、E、S、R、C、D、T、O、W、H之一。3、 Alt-子菜单命令首字母(按Alt键的同时，按首字母)。 4、用鼠标直接操作。 进入子菜单后，会出现一个下拉式菜单，这时的子菜单又含有多项命令功能供选择。选择的方法是：按命令的首字母或按↑、↓键将光标移至命令处回车。有些命令还有多级子菜单供选择。 在有子菜单出现时，按ESC键可返回上级子菜单或主菜单。在任何时候均可按F10键进入主菜单。 屏幕底行提示了各热键(在当前状态下生效的键)对应的功能。例如按F1键可以进入帮助。 屏幕中除顶行和底行外的中间大部分窗口为编辑窗口，用于编辑显示程序文本。 第三节 一个Pascal程序实例 一、进入编辑状态 1．进入编辑状态 在主菜单中选择Edit项，就可进入编辑状态，这时光标位于编辑窗口的左上角。在编辑状态下，可按↑、↓、←、→键上下左右移动光标；按退格键删光标前字符，按DEL键删光标所指字符；按回车键换行。 2．编辑窗口的说明 在窗口的左上角的小方块是关闭按钮，用于关闭窗口，中间的NONAME000.PAS是当前编辑的文件名，右上角的“1”表示当前窗口是第一个窗口，其右边的上下箭头用于恢复窗口的大小。在整个窗口的右边和下边设有上下左右滚动条。二、编辑输入一个Pascal程序 例：要求在屏幕上输出一句话： Follow me to study Pascal!(跟我学Pascal!) 程序如下： Program myfirst; begin write('Follow me to study Pascal!'); readln end. 选择File\New命令，打开一个新窗口（原来有窗口则不需要上述操作）。在编辑状态下，输入上述程序。三、在集成环境内运行程序 我们选择Run\Run命令(在Run子菜单下选Run命令，以后同)，如果程序正确，系统将按编译、链接、运行的过程自动给出结果： Follow me to study Pascal! 然后按回车返回集成环境。如果上例中无readln语句，系统运行后迅速返回编辑状态，使输出结果看不清，但这时选择Debug\User screen 命令或Alt+F5又可回到输出屏幕，按任意键又返回编辑状态。 如果程序有错，将产生两种情况之一：1、 编译失败。返回编辑窗口，光标指在错误程序行，窗口顶部显示错误信息；2、 运行错误。屏幕输出显示： Run_time error <错误代码> at <错误发生地址> 这里按任意键返回编辑窗口，光标指在错误行，窗口顶部显示错误信息。四、保存文件 以当前文件名为名存盘，选择File\Save 命令，系统以当前文件名NONAME000.PAS为名存盘。 选择File/Save As to命令，系统将按指定的盘符、路径、文件名存盘，例如： C：MYFIRST.PAS。 五、检查存盘文件 1、退出Turbo Pascal返回Dos，用DOS命令DIR检查 选择File\Quit——完全退出，因系统所占的内存完全释放，无法再返回Pascal。 选择File\DOS shell——暂时退出，这时系统暂驻内存，在DOS状态下，可用DOS命令DIR检查文件的情况，键入Exit命令还可返回Pascal。 2、选择File\Open命令，选择或键入已存盘文件名即可将所指文件装入编辑窗口。 习 题 下列Pascal程序运行后由用户输入一个数，作为半径r，程序将计算出半径为r的园的面积。 Program Area_of_Circle; const pi=3.1416; var s,r:real; begin writeln('Please input radius: '); readln(r); s:=Pi*sqr(r); writeln('s=',s) end. 运行例子： Please input radius：(显示：请输入半径) 5 (用户输入5) s=7.8540000000E+01 (显示结果) 在Turbo Pascal集成环境下输入、运行并保存上述程序。
Ⅳ pascal递归结构是怎么样的
主要思想把阶数较高的某一个过程，转化为阶数较低相同类型的过程，称为递归算法。采用递归编写程序能使程序变得非常简单而清晰。递归的主要思想包括三个方面：a) 定义形式是递归定义的。b) 数据之间的关系（即数据结构）按递归定义。c) 问题本身没有明显的递归结构，但用递归求解比用迭代求解更简单。? 例题分析阶乘函数定义（n!）描述如下： fac(n)= 1 (当n＝0时);n×fac（n－1）(当n>0时),请编程实现从键盘输入n值，通过调用函数求f(n)的值.[参考程序]program digui1;var n:integer;function fac(n:integer):real;beginif n=0then fac:=1else fac:=n*fac(n-1) ;end;beginwrite(‘n=’);readln(n);writeln(‘fac(‘,n,’)=’,fac(n):6:2);end.小结采用递归算法来编程，程序结构清晰简洁，它能使一个蕴涵递归关系且结构复杂的程序简洁精练，增加可读性。但递归过程的实现决定了递归算法的效率往往很低，费时和费内存空间。在实际编程中，如果能使用递推法解决的，应考虑用递推法，其效率更高些。用递推法求解阶乘函数的思路是：先求fac(1)，再求fac(2)，…,直到求出fac(n)，参考程序如下:program digui2;var n:integer;function fac(n:integer):realll;var I:integer;m:real;beginm:=1;for I:=1 to n do m:=m*I;fac:=m;end;beginwrite(‘n=’);readln(n);writeln(‘fac(’,n,’)=’,fac(n):6:2);end.说实话 如果真的想理解好递归我建议把八皇后问题看透彻。 八皇后就是非常经典的递归加回朔 program eightqueens; var x:array[1..8] of integer; {当前8个皇后所摆的方案} a,b,c:array[-7..16] of boolean; {分别是列，对角线，反对角线} i:integer; procere print; {打印本次方案} var k:integer; begin for k:=1 to 8 do write(x[k]:4); writeln; end; procere try(i:integer); {使用回溯法递归求解，试遍所有的情况，是一种递归枚举} var j:integer; begin for j:=1 to 8 do if a[j] and b[i+j] and c[i-j] {若(i,j) 可放} then begin x[i]:=j; {则第i行就放在第j列} a[j]:=false; {做上相应位置不能放的标志} b[i+j]:=false; c[i-j]:=false; if i<8 then try(i+1){8个没放完，则继续放} else print; {放完去打印方案} a[j]:=true;{回溯回来后，撤去不能放的标志} b[i+j]:=true; c[i-j]:=true end end; begin for i:=-7 to 16 do{初始化为每个位置均可放} begin a[i]:=true; b[i]:=true; c[i]:=true end; try(1);{从第一行开始} end. 现在循环从 i=1 ,j:=1 to 8 do 开始 此时 计算机检测到 i=1 j=1 (简化为（1，1）)为空，占用该位置并令该位置对应的斜线和水平方向的位置为 false ，然后程序就开始去执行try（2），注意此时计算机在i=1 这层仅仅走了一个循环（j=1）就跳到了i=2 ，第2层里此时计算机从j：=1 to 8 do 又开始循环，排除 j=1，j=2 得到 （2，3）注意计算机第2层里也只是走了3（j=3）个循环然后又跳到了i=3 这层依次类推得到（3，5），（4，2）（5，4）而在i=6 这层里计算机从j：= 1 to 8 do 都没有找到合适的位置，此时注意在i=6 这层里计算机计算机将返回到i=5 这层里，（因为用了递归）并且释放（5，4）该位置，为什么要释放呢？因为原因很简单如果不释放的话 该位置对应的斜线和水平方向会对以后的几层造成影响，让计算机误认为false。此时的在i=5这层里 j=4没有循环结束,然后计算机又会从j=5到 8 开始去找合适的位置 ，如果找不到又会返回到上一层依次类推直到计算机找到一组解 输出，假设在（8，3）这个位置是计算机找到的一组解，此时计算机又会从j=4到8 开始循环，如果找不到 计算机就会返回上一层的即i=7这层接着上一次的跳出位置走完以后的循环，依次类推不断的返回，跳出， 求解，（即令前几个位置不变，从第8个位置变换，没有空位置的。接会返回上一层）最后返回到i=1这层里，注意此时在这层里也只是走了j=1个循环然后计算机就又开始从j= 2 去试着找….大家有没有算过求出所有的解要走过多少个循环？我想估计也不下1000个吧。其实整个过程就是一个重复的过程（即递归）倒着想在i=7 这层里的j=1 位置即（7，1） 计算机会去试从（8，1）到（8，8）这8 个位置，而在（7，2）也同样会去试这8 个位置 等等在（6，1）会试（7，1）到（7，8） 等。 这是正着考虑（1，1）这里计算机会试着从（2，1）到（2，8）这8个位置而在这8 个位置里并没有试完就有空位置 （2，3）此时计算机会在这个位置对下一层里开始试（3，1）..（3，8）依次类推，试不通的返回，接着走完上一层直到试完所有的位置！
Ⅳ 数据结构和计算机相关的问题
1.数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。2.栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。 栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。 栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。 栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。3.线性表是由n（n≥0）个数据元素（结点）a[0]，a[1]，a[2]…，a[n-1]组成的有限序列。4.队列的操作原则是先进先出5.并发进程间的关系：并发进程相互之间可能是 无关的 ，也可能是 交往的 .如果一个进程的执行不影响其他进程的执行，且与其他进程的进展情况无关，即它们是各自独立的，则这些并发进程相互之间是无关的。如果一个进程的执行依赖其他进程的执行，则这些并发进程之间是有交往的。6.算法设计的基本方法:列举法 枚举归纳法 递推法 递归法 减半递推技术 回溯法 数值法7.数据结构分为哪几大类:通常有下列四类基本的结构： ⑴集合结构。该结构的数据元素间的关系是“属于同一个集合”。 ⑵线性结构。该结构的数据元素之间存在着一对一的关系。 ⑶树型结构。该结构的数据元素之间存在着一对多的关系。 ⑷图形结构。该结构的数据元素之间存在着多对多的关系，也称网状结构。8.对于一个顺寻战来说,战空 战满的条件:栈空的条件是st->top=0,栈满的条件是st->top==maxlen9.N/210.进程死锁的4个表要条件（1） 互斥条件：一个资源每次只能被一个进程使用。（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。（3） 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。11.操作系统的典型类型 3个:批处理操作系统 分时操作系统实时操作系统12.进程的3中基本:就绪，阻塞，运行 13.算法的概念和特征:算法（Algorithm）是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。 一个算法应该具有以下五个重要的特征： 1、有穷性2、确切性3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 5、可行性14.数据结构的概念:数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。15.什么是数据的存储结构:存储结构是指一个数据集合在计算机内存里是怎么样存储的.或者说在内存里怎么给一群数据分配内存. 16.查找的概念以及典型的算法:给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置;否则查找失败，返回相关的指示信息。顺序查找 二分查找 分块查找 哈希表查找17.操作系统的功能:作业管理(Job Management)进程管理(Process Management)存储管理(Memory Management)设备管理(Device Management)文件管理(File Management)18.递归算法思路:一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。19.数据的逻辑结构:简单说,数据的逻辑结构就是数据之间关系,如顺序关系,隶属关系等.20.队列的概念:队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表21.进程的概念:进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥有系统资源，是一个动态的概念，是一个活动的实体。它不只是程序的代码，还包括当前的活动，通过程序计数器的值和处理寄存器的内容来表示。22.二叉树的先序、中序和后续:NLR：前序遍历(PreorderTraversal亦称(先序遍历))访问结点的操作发生在遍历其左右子树之前。② LNR：中序遍历(InorderTraversal)访问结点的操作发生在遍历其左右子树之中(间)。③ LRN：后序遍历(PostorderTraversal)访问结点的操作发生在遍历其左右子树之后。23.快速排序:快速排序对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
Ⅵ 考“软考”的软件设计师，该看什么书
要参加软件设计师的考试，务必购买两本书：《软件设计师教程》《教程》建议买教育部指定的教材，《软件设计师历年试题解析》。《解析》倒也无所谓，张友生老师的分析似乎更全面、更有针对性。另外还有《软件设计师大纲》，在复习过程中阶段性地查一查，梳理一下知识结构体系，可以查缺补漏。1、具体学习每门课程的方法(1)软件工程。软件工程是复习的重点，不但上午题当中占10左右，而且下午题里也有2道软件设计分析方面的题目，一定要熟练的掌握书本中说到的各种软件分析设计方法及有关的分析用图，对各种图的功能作用和制作方法(特别是各种图的组成元素)以及各种图之间的转换及联系(如果有的话)，UML面向对象的软件设计方法及面象过程的软件设计方法完全理解，软件测试要达到理解的程度，其它的内容只有去强记了，因为基本是都是上午题，而且每年的题都不定，但与CMM有关的一定会有。(2)数据库。数据库部分也很重要，上午有5分左右，下午至少有一道数据库的题目，而且也一定是考关系型数据库，E-R模式也要搞懂，可由它导出关系，一定要弄懂关系数据库的几个范式及关系的建立方法。因此，就要对关系数据库的基础概念非常清楚，如键的定义，函数依赖，范式的定义、作用及转换是建立关系的基础。数据的并发控制，要熟练掌握SQL常用的几个语句，最好是用笔将每个语句写上几遍，对语句的各种形式加深记忆，数据库的学习还是不太难的。因为考试不会考数据的物理存储及数据安全，感觉这方面的知识更难，交叉学科更多。(3)学习数据结构和算法。数据结构和算法是考试的重点内容，它的复习以普通的教材为主，对数组、链表、队列、栈、树及堆等基本的数据组织方式要非常熟悉(要做到看见算法就知道要用什么数据组织方式更高效)，排序、索引及图的各种算法要了然于心(算法的分析过程及代码要非常清楚)，算法的分析方法达到理解应用的水平。对C语言要非常熟练(要会应用C语言语句的一些技巧，如可以利用函数的返回值做为判定条件，在循环中对数组的处理可使用a[i++]来提高编写代码的效率，这类的小技巧只有通过大量的阅读代码才能提高)，如果是初学面向对象方面的高级语言，建议还是先学C++，感觉它更象一种语言规范，而Java是一种编程的工具并且由于它的跨平台特性所以它有很多自己独有的功能和特点，有时间一定要看一本C++语言的数据结构，它能使你更全面和深刻的理解类及对象的编程方法。算法的学习不是一朝一夕就能提高的，一定要静下心来学习一些经典算法，比如：穷举法、贪婪法、分治法、迭代法、递推法、递归法、回溯法;找一些有名的算法程序来分析，比如：背包问题、组合问题、斐波那契数列、马踏棋盘问题、货朗担问题、八皇后问题、迷宫问题、汉诺塔问题、约琴夫环问题等。有了这些算法思想在你的头脑中扎根后，当看到问题，就自然的想起用什么方法来求最优解了。(4)程序设计语言。程序设计语言包括C语言、编译原理和面向对象的程序设计语言(通常以C++为例)。编译原理一定会考词法分析，它是后面编译过程的基础。主要考的内容是NFA与DFA的转换、正规式与有穷自动机的转换等。文法分析有一年考过下午题，这科对初学者比较难，比较抽象，理论性也比较强，反正我是学了4个来月才学通一点，这课复习没什么技巧，听听希赛的“编译原理视频教程”，学起来更快一些。C语言要掌握好三种基本结构、数组、链表、结构体、共用体、参数传递、指针及指针数组、指针函数等等。面向对象的程序设计语言要对基本概念及初步应用要了解，考得不深。(5)面向对象方法学。面向对象方法学不但是上午的考试重点，也是下午的考试重点。上午平均有12分左右，而下午有30分，一道与UML图形有关的题目，一道面向对象程序设计的选做题。所以要好好掌握这一块。UML当中的类图、用例图、状态图、协作图要掌握好，考试中会常出现。(老师多次强调这个要学习的知识点，我通过做题，认为老师抓的很准。)(6)操作系统。操作系统没什么说得了，把它的几个功能模块搞清楚及相关的算法搞清楚就好了，如处理器的管理、存储管理、设备管理、文件管理及系统安全，其中我认为比较难理解的是PV操作(在并发进程中它的应用非常灵活)和中断(反正这个对我比较难)，一定要把相关内容所讲到的算法及分析过程搞懂。当然还要注意进程死锁的问题，段页式存储的问题。其它课程的复习就按考试大纲进行，把里面的概念搞清楚，因为它大部分都是上午题。2、看书与练习相结合“看书时要有目的性，带着任务走，;看后做题进行巩固，所以看了书以后，要找一两个相关的题来做一做。
Ⅶ 求排列生成算法（pascal）
选择排序法：PROCEDURE selectsort; VAR i,j,k,temp:integer; BEGIN FOR i:=1 to n-1 DO BEGIN k:=i; FOR j:=i+1 to n DO IF a[k]>a[j] THEN k:=j; IF k<>i THEN BEGIN temp:=a[k]; a[k]:=a[i]; a[i]:=temp; END; END; END; 快速排列法： procere qsort(L,R:longint); var i,j,mid,temp:longint; begin i:=L; j:=R; mid:=a[L+random(R-L+1)]; {随机选择一个数组中的数作为对比数} repeat while a[i]< mid do inc(i); {在左半部分寻找比中间数大的数} while mid< a[j] do dec(j); {在右半部分寻找比中间数小的数} if i< =j then {若找到一组与排序目标不一致的数对则交换它们} begin temp:=a[i]; a[i]):=a[j]; a[j]:=temp; inc(i);dec(j); {继续找} end; until i >j; if L< j then qsort(L,j); {若未到两个数的边界，则递归搜索左右区间} if i< R then qsort(i,R); end; 注意:主程序中必须加randomize语句。 摘自pascal教程
Ⅷ 2008年计算机等级考试二级教程公共基础知识
1) 算法的复杂度主要包括______复杂度和空间复杂度。答：时间(2) 数据的逻辑结构在计算机存储空间中的存放形式称为数据的______。答：模式#逻辑模式#概念模式(3) 若按功能划分，软件测试的方法通常分为白盒测试方法和______测试方法。答：黑盒(4) 如果一个工人可管理多个设施，而一个设施只被一个工人管理，则实体"工人"与实体"设备"之间存在______联系。答：一对多#1：N#1:n(5) 关系数据库管理系统能实现的专门关系运算包括选择、连接和______。答：投影(6) 在先左后右的原则下，根据访问根结点的次序，二*树的遍历可以分为三种：前序遍历、______遍历和后序遍历。答：中序(7) 结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、______和限制使用goto语句。答：模块化(8) 软件的调试方法主要有：强行排错法、______和原因排除法。答：回溯法(9) 数据库系统的三级模式分别为______模式、内部级模式与外部级模式。答：概念#概念级(10) 数据字典是各类数据描述的集合，它通常包括5个部分，即数据项、数据结构、数据流、______和处理过程。答：数据存储(11) 设一棵完全二*树共有500个结点，则在该二*树中有______个叶子结点。答：250(12) 在最坏情况下，冒泡排序的时间复杂度为______。答：n(n-1)/2#n*(n-1)/2#O(n(n-1)/2)#O(n*(n-1)/2)(13) 面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个______。答：实体(14) 软件的需求分析阶段的工作，可以概括为四个方面：______、需求分析、编写需求规格说明书和需求评审。答：需求获取(15) ______是数据库应用的核心。答：数据库设计16) 数据结构包括数据的______结构和数据的存储结构。答：逻辑(17) 软件工程研究的内容主要包括：______技术和软件工程管理。答：软件开发(18) 与结构化需求分析方法相对应的是______方法。答：结构化设计(19) 关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、______和自定义完整性。答：参照完整性(20) 数据模型按不同的应用层次分为三种类型，它们是______数据模型、逻辑数据模型和物理数据模型。答：概念(21) 栈的基本运算有三种：入栈、退栈和______。答：读栈顶元素#读栈顶的元素#读出栈顶元素(22) 在面向对象方法中，信息隐蔽是通过对象的______性来实现的。答：封装(23) 数据流的类型有______和事务型。答：变换型(24) 数据库系统中实现各种数据管理功能的核心软件称为______。答：数据库管理系统#DBMS(25) 关系模型的数据*纵即是建立在关系上的数据*纵，一般有______、增加、删除和修改四种*作。答：查询(26) 实现算法所需的存储单元多少和算法的工作量大小分别称为算法的 ______。答：空间复杂度和时间复杂度(27) 数据结构包括数据的逻辑结构、数据的 ______以及对数据的*作运算。答：存储结构(28) 一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的______。答：可重用性(29) 面向对象的模型中，最基本的概念是对象和 ______。答：类(30) 软件维护活动包括以下几类：改正性维护、适应性维护、______维护和预防性维护。答：完善性(31) 算法的基本特征是可行性、确定性、______和拥有足够的情报。答：有穷性(32) 顺序存储方法是把逻辑上相邻的结点存储在物理位置______的存储单元中。答：相邻(33) Jackson结构化程序设计方法是英国的M.Jackson提出的，它是一种面向______的设计方法。答：数据结构(34) 数据库设计分为以下6个设计阶段：需求分析阶段、______、逻辑设计阶段、物理设计阶段、实施阶段、运行和维护阶段。答：概念设计阶段#数据库概念设计阶段(35) 数据库保护分为：安全性控制 、______、并发性控制和数据的恢复。答：完整性控制(36) 测试的目的是暴露错误，评价程序的可*性；而______的目的是发现错误的位置并改正错误。答：调试(37) 在最坏情况下，堆排序需要比较的次数为______。答：O(nlog2n)(38) 若串s="Program"，则其子串的数目是______。答：29(39) 一个项目具有一个项目主管，一个项目主管可管理多个项目，则实体"项目主管"与实体"项目"的联系属于______的联系。答：1对多#1：N(40) 数据库管理系统常见的数据模型有层次模型、网状模型和______三种。答：关系模型 (1) 下面叙述正确的是______。(C)A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令（或语句）的条数C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对(2) 以下数据结构中不属于线性数据结构的是______。(C)A. 队列B. 线性表C. 二*树D. 栈(3) 在一棵二*树上第5层的结点数最多是______。(B)A. 8B. 16C. 32D. 15(4) 下面描述中，符合结构化程序设计风格的是______。(A)A. 使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑B. 模块只有一个入口，可以有多个出口C. 注重提高程序的执行效率D. 不使用goto语句(5) 下面概念中，不属于面向对象方法的是______。(D)A. 对象B. 继承C. 类D. 过程调用(6) 在结构化方法中，用数据流程图（DFD）作为描述工具的软件开发阶段是______。(B)A. 可行性分析B. 需求分析C. 详细设计D. 程序编码(7) 在软件开发中，下面任务不属于设计阶段的是______。(D)A. 数据结构设计B. 给出系统模块结构C. 定义模块算法D. 定义需求并建立系统模型(8) 数据库系统的核心是______。(B)A. 数据模型B. 数据库管理系统C. 软件工具D. 数据库(9) 下列叙述中正确的是______。(C)A. 数据库是一个独立的系统，不需要*作系统的支持B. 数据库设计是指设计数据库管理系统C. 数据库技术的根本目标是要解决数据共享的问题D. 数据库系统中，数据的物理结构必须与逻辑结构一致(10) 下列模式中，能够给出数据库物理存储结构与物理存取方法的是______。(A)A. 内模式B. 外模式C. 概念模式D. 逻辑模式(11) 算法的时间复杂度是指______。(C)A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数(12) 下列叙述中正确的是______。(A)A. 线性表是线性结构B. 栈与队列是非线性结构C. 线性链表是非线性结构D. 二*树是线性结构(13) 设一棵完全二*树共有699个结点，则在该二*树中的叶子结点数为______。(B)A. 349B. 350C. 255D. 351(14) 结构化程序设计主要强调的是______。(B)A. 程序的规模B. 程序的易读性C. 程序的执行效率D. 程序的可移植性(15) 在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是______。(D)A. 概要设计B. 详细设计C. 可行性分析D. 需求分析(16) 数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是______。(A)A. 控制流B. 加工C. 数据存储D. 源和潭(17) 软件需求分析阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书以及______。(B)A. 阶段性报告B. 需求评审C. 总结D. 都不正确(18) 下述关于数据库系统的叙述中正确的是______。(A)A. 数据库系统减少了数据冗余B. 数据库系统避免了一切冗余C. 数据库系统中数据的一致性是指数据类型的一致D. 数据库系统比文件系统能管理更多的数据(19) 关系表中的每一横行称为一个______。(A)A. 元组B. 字段C. 属性D. 码(20) 数据库设计包括两个方面的设计内容，它们是______。(A)A. 概念设计和逻辑设计B. 模式设计和内模式设计C. 内模式设计和物理设计D. 结构特性设计和行为特性设计 (21) 算法的空间复杂度是指______。(D)A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 算法执行过程中所需要的存储空间(22) 下列关于栈的叙述中正确的是______。(D)A. 在栈中只能插入数据B. 在栈中只能删除数据C. 栈是先进先出的线性表D. 栈是先进后出的线性表(23) 在深度为5的满二*树中，叶子结点的个数为______。(C)A. 32B. 31C. 16D. 15(24) 对建立良好的程序设计风格，下面描述正确的是______。(A)A. 程序应简单、清晰、可读性好B. 符号名的命名要符合语法C. 充分考虑程序的执行效率D. 程序的注释可有可无(25) 下面对对象概念描述错误的是______。(A)A. 任何对象都必须有继承性B. 对象是属性和方法的封装体C. 对象间的通讯*消息传递D. *作是对象的动态性属性26) 下面不属于软件工程的3个要素的是______。(D)A. 工具B. 过程C. 方法D. 环境(27) 程序流程图（PFD）中的箭头代表的是______。(B)A. 数据流B. 控制流C. 调用关系D. 组成关系(28) 在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是______。(A)A. 数据库系统B. 文件系统C. 人工管理D. 数据项管理(29) 用树形结构来表示实体之间联系的模型称为______。(B)A. 关系模型B. 层次模型C. 网状模型D. 数据模型(30) 关系数据库管理系统能实现的专门关系运算包括______。(B)A. 排序、索引、统计B. 选择、投影、连接C. 关联、更新、排序D. 显示、打印、制表(31) 算法一般都可以用哪几种控制结构组合而成______。(D)A. 循环、分支、递归B. 顺序、循环、嵌套C. 循环、递归、选择D. 顺序、选择、循环(32) 数据的存储结构是指______。(B)A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据(33) 设有下列二*树： 对此二*树中序遍历的结果为______。(B)A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA(34) 在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送______。(D)D. 消息A. 调用语句B. 命令C. 口令(35) 检查软件产品是否符合需求定义的过程称为______。(A)A. 确认测试B. 集成测试C. 验证测试D. 验收测试(36) 下列工具中属于需求分析常用工具的是______。(D)A. PADB. PFDC. N-SD. DFD(37) 下面不属于软件设计原则的是______。(C)A. 抽象B. 模块化C. 自底向上D. 信息隐蔽(38) 索引属于______。(B)A. 模式B. 内模式C. 外模式D. 概念模式(39) 在关系数据库中，用来表示实体之间联系的是______。(D)A. 树结构B. 网结构C. 线性表D. 二维表(40) 将E-R图转换到关系模式时，实体与联系都可以表示成______。(B)A. 属性 B. 关系C. 键D. 域(41) 在下列选项中，哪个不是一个算法一般应该具有的基本特征______。(C)A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报(42) 希尔排序法属于哪一种类型的排序法______。(B)A. 交换类排序法B. 插入类排序法C. 选择类排序法D. 建堆排序法(43) 下列关于队列的叙述中正确的是______。(C)A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表(44) 对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。(B)A. N+1B. NC. (N+1)/2D. N/2(45) 信息隐蔽的概念与下述哪一种概念直接相关______。(B)A. 软件结构定义B. 模块独立性C. 模块类型划分D. 模拟耦合度(46) 面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是______。(C)A. 模拟现实世界中不同事物之间的联系B. 强调模拟现实世界中的算法而不强调概念C. 使用现实世界的概念抽象地思考问题从而自然地解决问题D. 鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考(47) 在结构化方法中，软件功能分解属于下列软件开发中的阶段是______。(C)A. 详细设计B. 需求分析C. 总体设计D. 编程调试(48) 软件调试的目的是______。(B)A. 发现错误B. 改正错误C. 改善软件的性能D. 挖掘软件的潜能(49) 按条件f对关系R进行选择，其关系代数表达式为______。(C)A. R|X|RB. R|X|R fC. бf(R)D. ∏f(R)(50) 数据库概念设计的过程中，视图设计一般有三种设计次序，以下各项中不对的是______。(D)A. 自顶向下B. 由底向上C. 由内向外D. 由整体到局部(51) 在计算机中，算法是指______。(C)A. 查询方法B. 加工方法C. 解题方案的准确而完整的描述D. 排序方法(52) 栈和队列的共同点是______。(C)A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点(53) 已知二*树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是______。(A)A. cedbaB. acbedC. decabD. deabc(54) 在下列几种排序方法中，要求内存量最大的是______。(D)A. 插入排序B. 选择排序C. 快速排序D. 归并排序(55) 在设计程序时，应采纳的原则之一是______。(A)A. 程序结构应有助于读者理解B. 不限制goto语句的使用C. 减少或取消注解行D. 程序越短越好(56) 下列不属于软件调试技术的是______。(B)A. 强行排错法B. 集成测试法C. 回溯法D. 原因排除法(57) 下列叙述中，不属于软件需求规格说明书的作用的是______。(D)A. 便于用户、开发人员进行理解和交流B. 反映出用户问题的结构，可以作为软件开发工作的基础和依据C. 作为确认测试和验收的依据D. 便于开发人员进行需求分析(58) 在数据流图（DFD）中，带有名字的箭头表示______。(C) A. 控制程序的执行顺序B. 模块之间的调用关系C. 数据的流向D. 程序的组成成分(59) SQL语言又称为______。(C)A. 结构化定义语言B. 结构化控制语言C. 结构化查询语言D. 结构化*纵语言(60) 视图设计一般有3种设计次序，下列不属于视图设计的是______。(B)A. 自顶向下B. 由外向内C. 由内向外D. 自底向上(61) 数据结构中，与所使用的计算机无关的是数据的______。(C)A. 存储结构B. 物理结构C. 逻辑结构D. 物理和存储结构(62) 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是______。(D)A. ABCEDB. DBCEAC. CDABED. DCBEA(63) 线性表的顺序存储结构和线性表的链式存储结构分别是______。(B)A. 顺序存取的存储结构、顺序存取的存储结构B. 随机存取的存储结构、顺序存取的存储结构C. 随机存取的存储结构、随机存取的存储结构D. 任意存取的存储结构、任意存取的存储结构(64) 在单链表中，增加头结点的目的是______。(A)A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现(65) 软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计是指______。(B)A. 模块间的关系B. 系统结构部件转换成软件的过程描述C. 软件层次结构D. 软件开发过程(66) 为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，通常也把这种图称为______。(B)A. PAD图B. N-S图C. 结构图 D. 数据流图(67) 数据处理的最小单位是______。(C)A. 数据B. 数据元素C. 数据项D. 数据结构(68) 下列有关数据库的描述，正确的是______。(C)A. 数据库是一个DBF文件B. 数据库是一个关系C. 数据库是一个结构化的数据集合D. 数据库是一组文件(69) 单个用户使用的数据视图的描述称为______。(A)A. 外模式B. 概念模式C. 内模式D. 存储模式(70) 需求分析阶段的任务是确定______。(D)A. 软件开发方法B. 软件开发工具C. 软件开发费用D. 软件系统功能(71) 算法分析的目的是______。(D)A. 找出数据结构的合理性B. 找出算法中输入和输出之间的关系C. 分析算法的易懂性和可*性D. 分析算法的效率以求改进(72) n个顶点的强连通图的边数至少有______。(C)A. n-1B. n(n-1)C. nD. n+1(73) 已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是______。(B)A. 堆排序B. 直接插入排序C. 快速排序D. 直接选择排序(74) 用链表表示线性表的优点是______。(A)A. 便于插入和删除*作B. 数据元素的物理顺序与逻辑顺序相同C. 花费的存储空间较顺序存储少D. 便于随机存取(75) 下列不属于结构化分析的常用工具的是______。(D)A. 数据流图B. 数据字典C. 判定树D. PAD图(76) 软件开发的结构化生命周期方法将软件生命周期划分成______。(A)A. 定义、开发、运行维护B. 设计阶段、编程阶段、测试阶段C. 总体设计、详细设计、编程调试D. 需求分析、功能定义、系统设计(77) 在软件工程中，白箱测试法可用于测试程序的内部结构。此方法将程序看做是______。(C)A. 循环的集合B. 地址的集合C. 路径的集合D. 目标的集合(78) 在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有______。(D)A. 数据无冗余B. 数据可共享C. 专门的数据管理软件D. 特定的数据模型(79) 分布式数据库系统不具有的特点是______。(B)A. 分布式B. 数据冗余C. 数据分布性和逻辑整体性D. 位置透明性和复制透明性(80) 下列说法中，不属于数据模型所描述的内容的是______。(C)A. 数据结构B. 数据*作C. 数据查询D. 数据约束
Ⅸ 数据结构与算法教程的内容提要
本书可以作为大专院校数据结构课程的教材，也可以作为从事计算机应用开发的科技人员的参考书。本书以清华大学电子系数据结构讲义为蓝本，主要针对高等院校非计算机专业开设“数据结构”课程的需要而编写的。全书从应用的角度，重点介绍数据处理中常用的数据结构——线性表、树与二叉树、图，以及基本的数据处理技术——查找和排序方法，同时通过实例把回溯法、分治法、贪心法、动态规划法等常用的算法设计思想的应用融入其中，把数据结构的介绍和常用算法设计的讨论紧密结合，并且辅之以充足的练习题，从而使读者更具体、更深刻地理解各种常用的数据结构，及它们与算法之间的关系，以达到学以致用的目的。
