搜索
目录1、数据结构基础知识……………………22、动态规划………………………………173、分支限界………………………………194、分治策略………………………………215、排序算法………………………………286、贪心算法………………………………457、计算机基础知识练习题………………518、附录——基础知识练习题参考答案…781数据结构数据结构是计算机专业基础课程之一，是十分重要的核心课程。计算机的所有系统软件和应用软件都要用到各种类型的数据结构。要想更好地运用计算机来解决实际问题，仅仅学习计算机语言而缺乏数据结构知识是远远不够的，而打好“数据结构”这门课程的扎实基础，对于学习计算机机专业的其他课程都是十分重要的。随着计算机应用领域不断扩大，非数值计算问题占据了当今计算机应用的绝大多数，简单的数据类型已经远远不能满足需要，各数据元素之间的复杂联系已经不是普通数学方程所能表达的。因此，掌握好数据结构方面的知识，对于提高我们解决实际问题的能力将会有莫大的帮助。实际上一个好的程序无非是选择一个合适的数据结构和好的算法，而好的算法的选择很大程度上取决于描述实际问题的数据结构的选取。所以，学好数据结构，将是进一步提高我们程序设计的关键之一。所以通常我们在程序设计时，所遇到的首要问题就是：选择什么样的数据结构才合适呢？这个问题十分关键。下面我们就各种数据结构作一些引导。线性表数据表是最常用且比较简单的一种数据结构，它是由有限个元素组成的有序集合，每个元素由一个或多个数据项组成。线性表具有如下的结构特点：①均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据必定具有相同的数据类型和长度。②有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之间的相对位置是线性的，即存在唯一的“第一个”和“最后一个”的数据元素，除第一个和最后一个外，其他的元素前都只有一个数据元素(直接前趋)和后面只有一个数据元素(直接后继)。队列抽象数据类型队列的定义和栈相反，队列(Queue)是一种先进先出(FirstInFirstOut,缩写为FIFO)的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，2最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。假设队列为q=(a1,a2,...an),那么，a1是队头元素，an则是队尾元素。队列中的元素是按照a1,a2,...an的顺序进入的，推出队列也只能按照这个次序依次推出，也就是说，只有在a1,a2,...an-1都离开队列之后，an才能推出队列。如图所示：堆栈表达式求值表达式求值是程序设计语言编译中的一个最基本问题.它的实现是栈应用的一个典型例子.这里介绍一种简单直观,广为使用的算法,通常成为算符优先法.要把一个表达式翻译成正确求值的一个机器指令序列,或直接对表达式求值,首先要能够正确解释表达式.要对表达式求值,首先要了解算术四则运算的规则.即:1)先乘除,后加减;2)从左算到右;3)先括号内,后括号外.算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的.任何一个表达式都是由数,运算符和界限符组成的,我们称它们为单词.为了叙述的简洁,我们仅讨论简单算术表达式的求值问题.这种表达式只含加,减,乘,除等四种运算符.读者不难将它推广到一般的表达式上.我们把运算符和界限符统称为算符,它们构成的集合命名为OP.根据上述三条运算规则,在运算的每一步中,任意两个相继出现的算符θ1和θ2之间的优先关系3至多是下面三种关系之一;θ1θ2θ1的优先权低于θ2θ1=θ2θ1的优先权等于θ2θ1θ2θ1的优先权高于θ2表3.1定义了算符之间的这种优先关系.为实现算符优先算法,可以使用两个工作栈.一个称作OPTR,用以寄存运算符;另一个称作POND,用以寄存操作数或运算结果.算法的基本思想是:1)首先置操作数栈为空,表达式起始符#为运算栈的栈底元素;2)依此读入表达式中每个字符,若是操作数则进OPND栈,若是运算符,则和OPTR栈的栈顶运算符比较优先权后作相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为#).以下算法描述了这个求值过程.FUNCexp_reduce:operandfype;{算术表达式求值的算符优先算法.假定从终端输入的表达式无语法错误,以#作结束符.设OPTR和OPND分别为运算符栈和操作数栈，OP为运算符的集合}INISTACK(OPTR);PUSH(OPTR,'#');INISTACK(OPND);{栈初始化,并在运算符栈的栈底压入表达式左端的虚设字符'#'}read(w);{从终端接受一个字符}WHILENOT((w='#')AND(GETTOP(OPTR)='#'))DOIFwNOTINopTHENPUSH(OPND,w)ELSECASEprecde(GETTOP(OPTR),w)OF'':[PUSH(OPTR,w);read(w)];{栈顶元素优先权低}'=:[x:=POP(OPTR);read(w)];{脱括弧并接受下一字符}':[theta:=POP(OPTR);b:=POP(OPND);a:=POP(OPND);PUSH(OPND,operate(a,theta,b))]{退栈并将运算结果入栈}ENDC;RETURN(GETTOP(OPND))ENDF;{exp_reducde}算法中还调用了两个函数。其中precede是判定运算符栈的栈顶运算符θ1与读入的运算符θ2之间优先关系的函数；orerate为进行二元运算aθb的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算结果。4例3-2利用算法exp_reducde对算术表达式3*（7-2）求值，操作过程如下所示。递归过程及其实现栈的另一个重要应用是在程序设计语言中实现递归过程。一个直接调用自己或通过一系列的过程语句间接地调用自己的过程，称做递归过程。例如，PROCEDUREA;BEGIN···A;···END;过程A中的语句A直接调用了过程A本身，这叫做直接递归调用。又如：PROCEDUREB;PROCEDUREC;BEGINBEGIN······C;C;······END;END;在过程B中调用了过程C,而过程C又调用了过程B.这两个过程都通过另一个过程调用了它们自己,这就叫做间接调用。递归是程序设计中一个强有力的工具。其一,有很多数学函数是递归定义的,如大家熟悉的阶乘函数Fact(n)=1若n=1Fact(n)=n·Fact(n-1)若n12阶Fibonacci数列Fib(n)=0若n=0Fib(n)=1若n=1Fib(n)=Fib(n-1)+Fib(n-2)其它情形和Ackerman函数Ack(m,n)=n+1m=0Ack(m,n)=Ack(m-1,1)n=0Ack(m,n)=Ack(m-1,Ack(m,n-1))其它情形等;其二,有的数据结构,如二叉树,广义表等,由于结构本身固有的递归特性,则它们的操作可递归地描述;其三,还有一类问题,虽则问题本身没有明显的递归结构,但用递归求解比迭代求解更简单,如八皇后问题,Hanio塔问题等.树5.1树的结构定义和基本操作树(Tree)是n(n=0)个结点的有限集。在一棵非空树中：(1)有且仅有一个特定的称为根的结点;(2)当n1时其余结点可分为m(m0)个互不相交的有限集T1,T2...Tm,其中,每一个集5合本身又是一棵树,并且称为根的子树(subtree)例如,在图6.1中,(a)是只有一个根结点的树;(b)是有13个结点的树,其中A是根,其余结点分成三个互不相交的子树：树是一种数据结构:Tree=(D,R)其中：D是具有相同特性的数据元素的集合；若D只含一个数据元素,则R为空集,否则R是D上个二元关系的集合，即R={H}。H为如下描述二元关系：(1)在D中存在发唯一的称为根的数据元素,它在关系H下无前驱;(2)若D-{root}≠φ，则存在D-{root}的一个划分D1,D2,...Dm(m0),对任意一对j≠k(l=j,k=m)有Dj∩Dk=φ，且对任意的i(l=i=m)，唯一存在数据元素Xi∈Di，有∈H;(3)对应于D-{root}的划分，H-{,...,}有唯一的一个划分H1,H2,...，Hm(m0),对任意一对j≠k(l=j,K=m)有，Hj∩Hk=φ，且对任意的i(l=i=m)Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。树结构中的一些基本术语：结点的度：结点拥有的子树数。叶子（终端结点）：度为零的结点。非终端结点（分支结点）：度不为零的结点。树的度：树内各结点的度的最大值。树的基本操作：(1)INITIATE(T)初始化操作，置T为空树。(2)ROOT(T)\ROOT(X)求根函数。求数T的根或求结点x所在的树的根结点。若T是空树或X不在任何一棵树上，则函数值为“空”。(3)RARENT(T,x)求双亲函数。求树T中结点x的双亲结点。若结点x是树T的根结点或结点x不在T中，则函数值为“空”。(4)CHILD(T,x,i)求孩子结点函数。求数T中结点x的第i个孩子结点。若结点x是树T的叶子或无第i个孩子或结点x不在树T中，则函数值为“空”。(5)RIGHT_SINLING(T,x)求右兄弟函数。求树T中结点x右边的兄弟。若结点x是其双亲的最右边的孩子结点或结点x不在树T中，则函树值为“空”。(6)CRT_TREE(x,F)建树操作。生成一棵以X结点为根，以森F为子树森林的树。(7)INS_CHILD(y,i,x)插入子树操作。置以结点x为根的树为结点y的第i棵子树。若原树中无结点y或结点y的子树个数>i-1，则空操作。(8)DEL_CHILD(x,i)删除子树操作。删除结点x的第i棵子树。若无结点x或结点x的子树个数>i，则空操作。6(9)TRAVERSE(T)遍历操作。按某个次序依此访问树中各个结点，并使每个结点只被访问一次。(10)CLEAR(T)清除结构操作。将树T置为空树。5.2.1二叉树定义与基本操作二叉树(binarytree)是另一种树型结构，它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒.二叉树是一种数据结构:Binary_tree=(D,R)其中：D是具有相同特性的数据元素的集合;若D等于空,则R等于空称为空的二叉树;若D等于空则R是D上某个二元关系H的集合，即R={H}，且(1)D中存在唯一的称为根的元素r，它的关系H下无前驱;(2)若D-{r}不等于空，则D-{r}={Dl,Dr}，且Dl交Dr等于空;(3)若Dl不等于空,则在Dl中存在唯一的元素xl,〈r,xl〉属于H，且存在Dl上的关系Hl属于H；若Dr不等于空,则在Dr中存在唯一的元素xr,〈r,xr〉属于H,且存Dr上的关系Hr属于H；H={r,xl,＜r,xr＞,Hl,Hr};(4)(Dl,Hl)是一棵合本定义的二叉树，称为根r的左子树,(Dr,Hr)是一棵符合定义的二叉树，称为根的右子树。其中，图6.2是各种形态的二叉树.(1)为空二叉树(2)只有一个根结点的二叉树(3)右子树为空的二叉树(4)左子树为空的二叉树(5)完全二叉树二叉树的基本操作：(1)INITIATE(BT）初始化操作。置BT为空树。(2)ROOT(BT)\ROOT(x)求根函数。求二叉树BT的根结点或求结点x所在二叉树的根结点。若BT是空树或x不在任何二叉树上，则函数值为“空”。(3)PARENT(BT,x)求双亲函数。求二叉树BT中结点x的双亲结点。若结点x是二叉树BT的根结点或二叉树BT中无x结点，则函数值为“空”。(4)LCHILD(BT,x)和RC