专业课

尾递归和单向递归的消除不需要借用栈单向递归和尾递归可直接用迭代实现其非递归过程其他情形必须借助栈实现非递归过程。证明：若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i<j<k,使Pj<Pk<Pi。 i<j 若Pi<Pj 说明小的先于大的数出栈，那么也就是Pi出栈在Pj入栈前...

...

双端队列： 两端都可以插入和删除，但实际应用中通常是输出受限的双端对列和输入受限的双端队列 输入受限的双端队列指的是：一端可以输入输出另一端只能输出不能输入 输出受限的双端队列指的是：一端可以输入输出另一端只能输入不能输出求从迷宫入口到出口的一条最短路径 要用到队列，因为队列可以用在广度优先中，队列中的元素表示离中心点依次越来越远。 所以第一次找到出口肯定是半径最短的。...

中缀表达式转化成后缀表达式算法void trans-post(char E[n] ,char B[n]) //中、后缀表达式转换//{ //E[n]是中缀表达式、B[n]是后缀表达式存储的空间 int i=0,j=0; char x; stype S; Clearstack(S); Push(S,‘#’)；//‘#’入栈// do { x=E[i++] ; //扫描当前表达式分量// if...

中缀表达式直接求值算法：OPNDType EvalueExpression(){ //OPTR 和OPND分别为运算符栈和操作数栈 InitStack(OPTR);Push(OPTR,’#’); InitStack(OPND);c=getchar(); While(c!=’＃’|| GetTop(OPTR)!=’#’) { If(!IN(c,OP) ) //如果是操作数，直接入操作数栈 { pus...

何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。2.基于时间的考虑。若线性表的操作主要是进行查找，很少...

Exp=a*b+(c-d/e)*f若 Exp=a*b+(c-d/e)*f 　则它的前缀式为： +*ab*-c/def 中缀式为： a*b+c-d/e*f 后缀式为： ab*cde/-fx+　综合比较它们之间的关系可得下列结论：1.三式中的 “操作数之间的相对次序相同”;(二叉树的三种访问次序中，叶子的相对访问次序是相同的)2.三式中的 “运算符之间的的相对次序不同”;3.中缀式丢失了括弧信息，致使...

循环链表是一种首尾相接的链表。也就是终端结点的指针域不是指向NULL空而是指向开始结点(也可设置一个头结点)，形成一个环。采用循环链表在实用中多采用尾指针表示单循环链表。这样做的好处是查找头指针和尾指针的时间都是O(1)，不用遍历整个链表了。判别链表终止的条件也不同于单链表，它是以指针是否等于某一指定指针如头指针或尾指针来确定。...

设计算法的要求（追求的目标）正确性、可读性、健壮性、效率与低存储量需求算法原地工作：当空间复杂度为O(1)时，称算法为就地工作（原地工作）。多型数据类型：是指其值的成分不确定的数据类型。从抽象数据类型的角度看，具有相同的数学抽象特性，故称之为　多型数据类型。数据结构是一门研究什么内容的学科？研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等学科对于一个数据结构，一般包括哪三个...

增长率由小至大的顺序排列下列各函数： 2^100, (2/3)^n，(3/2)^n， n^n , , n! ，2^n ，lgn ,n^lgn, n^(3/2)◇ 分析如下：2^100 是常数阶； (2/3)^n和 (3/2)^n是指数阶,其中前者是随n的增大而减小的； n^n是指数方阶； √n 是方根阶, n! 就是n(n-1)(n-2)... 就相当于n次方阶；2^n 是指数阶，lgn是对数阶 ...