|
一基础知识题 设将整数依次进栈但只要出栈时栈非空则可将出栈操作按任何次序夹入其中请回答下述问题 ()若入出栈次序为Push() Pop()Push()Push() Pop() Pop( )Push() Pop( )则出栈的数字序列为何(这里Push(i)表示i进栈Pop( )表示出栈)? () 能否得到出栈序列和?并说明为什么不能得到或者如何得到 ()请分析 的种排列中哪些序列是可以通过相应的入出栈操作得到的 链栈中为何不设置头结点? 循环队列的优点是什么? 如何判别它的空和满? 设长度为n的链队用单循环链表表示若设头指针则入队出队操作的时间为何? 若只设尾指针呢? 指出下述程序段的功能是什么? () void Demo(SeqStack *S){ int i; arr[] ; n= ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i= i< n; i++) Push(S arr[i]); } //Demo () SeqStack S S tmp; DataType x; //假设栈tmp和S已做过初始化 while ( ! StackEmpty (&S)) { x=Pop(&S) ; Push(&tmpx); } while ( ! StackEmpty (&tmp) ) { x=Pop( &tmp); Push( &Sx); Push( &S x); } () void Demo( SeqStack *S int m) { // 设DataType 为int 型 SeqStack T; int i; InitStack (&T); while (! StackEmpty( S)) if(( i=Pop(S)) !=m) Push( &Ti); while (! StackEmpty( &T)) { i=Pop(&T); Push(Si); } } ()void Demo( CirQueue *Q) { // 设DataType 为int 型 int x; SeqStack S; InitStack( &S); while (! QueueEmpty( Q )) {x=DeQueue( Q); Push( &Sx);} while (! StackEmpty( &s)) { x=Pop(&S); EnQueue( Qx );} }// Demo () CirQueue Q Q; // 设DataType 为int 型 int x i n= ; // 设Q已有内容 Q已初始化过 while ( ! QueueEmpty( &Q) ) { x=DeQueue( &Q ) ; EnQueue(&Q x); n++;} for (i=; i< n; i++) { x=DeQueue(&Q) ; EnQueue( &Q x) ; EnQueue( &Q x);} 二算法设计题 回文是指正读反读均相同的字符序列如abba和abdba均是回文但good不是回文试写一个算法判定给定的字符向量是否为回文(提示将一半字符入栈) 利用栈的基本操作写一个将栈S中所有结点均删去的算法void ClearStack( SeqStack *S)并说明S为何要作为指针参数? 利用栈的基本操作 写一个返回S中结点个数的算法 int StackSize( SeqStack S)并说明S为何不作为指针参数? 设计算法判断一个算术表达式的圆括号是否正确配对 (提示 对表达式进行扫描凡遇到(就进栈遇)就退掉栈顶的(表达式被扫描完毕栈应为空 一个双向栈S是在同一向量空间内实现的两个栈它们的栈底分别设在向量空间的两端 试为此双向栈设计初始化InitStack ( S ) 入栈Push( S i x) 和出栈Pop( S i )等算法 其中i为 或 用以表示栈号 Ackerman 函数定义如下请写出递归算法 ┌ n+ 当m=时 AKM ( m n ) = │ AKM( m ) 当m≠ n=时 └ AKM( m AKM( mn)) 当m≠ n ≠ 时 用第二种方法 即少用一个元素空间的方法来区别循环队列的队空和队满试为其设计置空队判队空判队满出队入队及取队头元素等六个基本操作的算法 假设以带头结点的循环链表表示队列并且只设一个指针指向队尾元素站点(注意不设头指针) 试编写相应的置空队判队空 入队和出队等算法 对于循环向量中的循环队列写出求队列长度的公式 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数试给出判别此循环队列的队满条件并写出相应的入队和出队算法要求出队时需返回队头元素 |
