内容发布更新时间 : 2024/12/25 1:56:05星期一 下面是文章的全部内容请认真阅读。
五、算法设计题
1. 设线性表存于A[1..size]的前num各分量中,且递增有序。请设计一个算法,将x插入到线性表的适当位置上,以保持线性表的有序性,并在设计前说明设计思想,最后说明所设计算法的时间复杂度。
2.试分别以顺序表和单链表作存储结构,各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法,在原表的存储空间内将线性表(a1,a2,.. .,an)逆置为(an,.. .,a2,a1)。
3.试编写在无头结点的单链表上实现线性表基本运算LOCATE(L,X)、INSERT(L,X,i)和DELETE(L,i)的算法,并和在带头结点的单链表上实现相的算法进行比较。
4.将线性表A=(a1,a2,……am), B=(b1,b2,……bn)合并成线性表C, C=(a1,b1,……am,bm,bm+1,…….bn) 当m<=n时,或 C=(a1,b1, ……an,bn,an+1,……am)当m>n时,线性表A、B、C以单链表作为存储结构,且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。
5. 已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为0(n)、空间复杂度为0(1)的算法,该算法删除线性表中所有值为item的数据元素。(O(1)表示算法的辅助空间为常量)。
6.假设在长度大于1的循环链表中,既无头结点也无头指针。s为指向链表中某个结点的指针,试编写算法删除结点*s的前趋结点。
7.已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写算法,构造三个循环链表,使每个循环链表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。
8.约瑟夫环问题
约瑟夫问题的一种描述为:编号1,2,…,n的n个人按顺时针方向围坐一圈,每个人持有一个密码(正整数)。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。试设计一个程序,求出出列顺序。利用单向循环链表作为存储结构模拟此过程,按照出列顺序打印出各人的编号。
例如m的初值为20;n=7,7个人的密码依次是:3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5。
9
习题三 栈和队列
一 单项选择题
1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。
①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2
2.若已知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,...,pn,若p1=3,则p2为( )。
A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6,5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列?( )
A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是 ( )
A.2 B. 3 C. 5 D.6
5. 若栈采用顺序存储方式存储,现两栈共享空间V[1..m],top[i]代表第i个栈( i =1,2)栈顶,栈1的底在v[1],栈2的底在V[m],则栈满的条件是( )。
A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后,i值为:( )
int f(int x)
{ return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));
A.2 B. 4 C. 8 D. 无限递归
7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时,对象栈和算符栈为( ),其中^为乘幂 。
A. 3,2,4,1,1;(*^(+*- B. 3,2,8;(*^- C. 3,2,4,2,2;(*^(- D. 3,2,8;(*^(- 8. 用链接方式存储的队列,在进行删除运算时( )。
A. 仅修改头指针 B. 仅修改尾指针
C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
9. 递归过程或函数调用时,处理参数及返回地址,要用一种称为( )的数据结构。
A.队列 B.多维数组 C.栈 D. 线性表
10.设C语言数组Data[m+1]作为循环队列SQ的存储空间, front为队头指针,rear为队尾指针,则执行出队操作的语句为 ( )
A.front=front+1 B. front=(front+1)% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( )
A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front
10
D.sq.rear ==sq.front
12. 栈和队列的共同点是( )。
A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点
二、填空题
1.栈是_______的线性表,其运算遵循_______的原则。
2. 一个栈的输入序列是:1,2,3则不可能的栈输出序列是_______。
3.用S表示入栈操作,X表示出栈操作,若元素入栈的顺序为1234,为了得到1342出栈顺序,相应的S和X的操作串为_______。
4. 循环队列的引入,目的是为了克服_______。 5.队列是限制插入只能在表的一端,而删除在表的另一端进行的线性表,其特点是_______。
6. 已知链队列的头尾指针分别是f和r,则将值x入队的操作序列是_______。
7.表达式求值是_______应用的一个典型例子。
8.循环队列用数组A[0..m-1]存放其元素值,已知其头尾指针分别是front和rear ,则当前队列的元素个数是_______。
9. 以下运算实现在链栈上的初始化,请在________________处用请适当句子予以填充。
Void InitStacl(LstackTp *ls){ ________________;}
10.` 以下运算实现在链栈上的进栈,请在处用请适当句子予以填充。
Void Push(LStackTp *ls,DataType x)
{ LstackTp *p;p=malloc(sizeof(LstackTp)); ________________; p->next=ls;
________________; }
11.以下运算实现在链栈上的退栈,请在________________处用请适当句子予以填充。
Int Pop(LstackTp *ls,DataType *x) {LstackTp *p; if(ls!=NULL) { p=ls;
*x=________________; ls=ls->next;
________________; return(1);
11
}else return(0); }
12. 以下运算实现在链队上的入队列,请在________________处用适当句子予以填充。
Void EnQueue(QueptrTp *lq,DataType x) { LqueueTp *p;
p=(LqueueTp *)malloc(sizeof(LqueueTp)); ________________=x; p->next=NULL;
(lq->rear)->next=________________; ________________;
}
三、应用题
1.给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满?
2. 画出对算术表达式A-B*C/D-E↑F求值时操作数栈和运算符栈的变化过程。
3. 将两个栈存入数组V[1..m]应如何安排最好?这时栈空、栈满的条件是什么?
4. 怎样判定循环队列的空和满?
四、算法设计题
1.借助栈(可用栈的基本运算)来实现单链表的逆置运算。
2. 设表达式以字符形式已存入数组E[n]中,‘#’为表达式的结束符,试写出判断表达式中括号(‘(’和‘)’)是否配对的C语言描述算法:EXYX(E); (注:算法中可调用栈操作的基本算法。)
3. 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。 (1)下面所示的序列中哪些是合法的?
A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO
(2)通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返
回true,否则返回false(假定被判定的操作序列已存入一维数组中)。
4. 设有两个栈S1,S2都采用顺序栈方式,并且共享一个存储区[O..maxsize-1],为了尽量利用空间,减少溢出的可能,可采用栈顶相向,迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。
5. 请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下:PUSH(ST,x):元素x入ST栈;POP(ST,x):ST栈顶元素出栈,赋给变量x;Sempty(ST):判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算:enqueue:插入一个元素入队列; dequeue:删除一个元素出队列;queue_empty:判队列为空。(请写明算法的思想及必要的注释)
12
6. 要求循环队列不损失一个空间全部都能得到利用,设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满,请编写与此相应的入队与出队算法。
7. 已知Q是一个非空队列,S是一个空栈。仅用队列和栈的ADT函数和少量工作变量,编写一个算法,将队列Q中的所有元素逆置。栈的ADT函数有:
makeEmpty(s:stack); 置空栈
push(s:stack;value:datatype); 新元素value进栈 pop(s:stack):datatype; 出栈,返回栈顶值 isEmpty(s:stack):Boolean; 判栈空否 队列的 ADT函数有:
enqueue(q:queue:value:datatype); deQueue(q:queue):datatype; isEmpty(q:queue):boolean; 元素value进队 出队列,返回队头值 判队列空否
13