ImageVerifierCode 换一换
格式:DOC , 页数:13 ,大小:113.50KB ,
资源ID:844623      下载积分:2000 积分
快捷下载
登录下载
邮箱/手机:
温馨提示:
如需开发票,请勿充值!快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝扫码支付 微信扫码支付   
注意:如需开发票,请勿充值!
验证码:   换一换

加入VIP,免费下载
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【http://www.mydoc123.com/d-844623.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文([考研类试卷]计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编7及答案与解析.doc)为本站会员(syndromehi216)主动上传,麦多课文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文库(发送邮件至master@mydoc123.com或直接QQ联系客服),我们立即给予删除!

[考研类试卷]计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编7及答案与解析.doc

1、计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编 7 及答案与解析一、综合题1 给出循环队列中元素个数的计算式(设队最大长度为 N,队首指针 FRONT,队尾指针 REAR)【西北大学 2000 二、7(5 分)】2 顺序队列一般应该组织成为环状队列的形式,而且一般队列头或尾其中之一应该特殊处理。例如,队列为 listarray0,n 一 1】,队列头指针为 front,队列尾指针为rear,则 listarrayrear表示下一个可以插入队列的位置。请解释其原因。【北京大学 1999 一、3(203 分) 】3 设一个双端队列,元素进入该队列的次序为 a,b,c ,d。求既不能由输入受

2、限的双端队列得到,又不能由输出受限的双端队列得到的输出序列。【中山大学1999 一、4(3 分) 】二、设计题4 设有两个栈 S1、S2 都采用顺序栈方式,并且共享一个存储区0maxsize 一1,为了尽量利用空间,减少溢出的可能,可采用栈顶相向,迎面增长的存储方式。试设计 S1、S2 有关入栈和出栈的操作算法。 【哈尔滨工业大学 2001 七(12 分)】5 设从键盘输入一整数的序列:a 1,a 2,a 3,a n,试编写算法实现:用栈结构存储输入的整数,当 ai一 1 时,将 at 进栈;当 ay=1 时,输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给出相应的信息。【南京航空航天大学

3、 1998 六(10 分)】6 设表达式以字符形式已存入数组 En中,# 为表达式的结束符,试写出判断表达式中括号(和)是否配对的 C 语言描述算法:EXYX(E) 。(注:算法中可调用栈操作的基本算法。)【北京科技大学 2001 九、1(10 分)】7 假设称正读和反读都相同的字符序列为“回文” ,例如, abcba是回文,abcde和ababab则不是回文。试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。【中国海洋大学 2007 八(15 分)】8 设计一个算法,判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中,每个结点有两个域:ch 和 link,

4、其中 ch 域为字符类型。9 设整数序列 a1,a 2, an,给出求解最大值的递归程序。【南京航空航天大学2000 六】10 线性表中元素存放在向量 A(1,n)中,元素是整型数。试写出递归算法求出 A 中的最大和最小元素。【北京邮电大学 1994 八(10 分)】11 已知求两个正整数 m 与 n 的最大公因子的过程用自然语言可以表述为反复执行如下动作:第一步:若 n 等于零,则返回 m;第二步:若 m 小于 n,则 m 与 n 相互交换;否则,保存 m,然后将 n 送 m,将保存的 m 除以 n 的余数送 n。(1)将上述过程用递归函数表达出来(设求 x 除以 y 的余数可以用 x MO

5、Dy 形式表示)。(2)写出求解该递归函数的非递归算法。【北京航空航天大学 2001 五(15 分)】12 已知 Ackermann 函数定义如下:(1)写出 Ack(2,1)的计算过程。(2)写出计算 Ack(m,n) 的非递归算法。【北京师范大学 2005 六、2(15 分)】【北京航空航天大学 1999 六(15 分)】13 设计算法以求解从集合1。n)中选取 k(kn)个元素的所有组合。例如,从集合14)中选取 2 个元素的所有组合的输出结果为: 1 2,1 3,1 4,2 3,2 4,3 4。【合肥工业大学 2000 五、5(8 分)】14 对于任意的无符号的十进制整数 m,写出将其

6、转换为十六进制整数的算法 (转换仅要求能够输出正确的十六进制的整数即可)。【兰州大学 2000 九(10 分)】15 已知递归函数 F(m)(其中 DIV 为整除):(1)写出求 F(m)的递归算法;(2)写出求 F(m)的非递归算法。【北京师范大学 2003 五、3(1 5 分)】16 试设计算法,n 为大于等于 0 的整数,利用堆栈设计下列函数的非递归算法。【天津大学 2006 二、2(7 分)】17 已知有 n 个元素存放在向量 S1.n中,其值各不相同,请写一递归算法,生成并输出 n 个元素的全排列。【中国科学技术大学 1992 十三(20 分)】【苏州大学2005 五(15 分) 】

7、18 请利用两个栈 S1 和 S2 来模拟一个队列。已知栈的三个运算定义如下:PUSH(ST,x):元素 x 入 ST 栈;POP(ST x):ST 栈顶元素出栈,赋给变量x;Sempty(ST:判 ST 栈是否为空。那么如何利用栈的运算来实现该队列的三个运算:enqueue:插入一个元素入队列;dequeue :删除一个元素出队列;queue 一empty:判队列为空。( 请写明算法的思想及必要的注释。)【上海交通大学 1999 二(12 分)】【厦门大学 2005 六(15 分) 】19 设结点结构为(data,link),试用一个全局指针 p 和某种链接结构实现一个队列,画出示意图,并给

8、出入队 addq 和出队 deleteq 过程,要求它们的时间复杂性都是O(1)(不计 new 和 dispose 时间)。【东南大学 1996 二(10 分)】20 编程:假设以数组 Qm存放循环队列中的元素,同时以 rear 和 length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件,并写 出相应的初始化(initqueue)、插入(enqueue)和删除(dlqueue)元素的操作。【天津大学 2002 一、5(10 分)】20 如果允许在循环队列的两端都可以进行插入和删除操作。要求:21 写出循环队列的类型定义;22 写出“从队尾删除 ”

9、和“从队头插入”的算法。【北方交通大学 1994 三(12 分)】23 已知 Q 是一个非空队列,S 是一个空栈。仅用队列和栈的 ADT 函数和少量工作变量,使用Pascal 或 C 语言编写一个算法,将队列 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) ;

10、元素 value 进队deQueue(q:queue):datatype; 出队列,返回队头值isEmpty(q:queue) :boolean; 判队列空否 【清华大学 2000 六(12 分)】【华南理工大学 2005 二、7(4 分)】24 将 n 个队列顺序映射到数组 v1m中,每一队列在 v 中表示为一循环队列。试画出其示意图并写出对应这种表示的 addq 和 deleteq 过程。【东南大学 1993 二(20 分)】计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编 7 答案与解析一、综合题1 【正确答案】 循环队列中元素个数为(REARFRONT+N)N 。其中 FRONT

11、 是队首指针,指向队首元素的前一位置;REAR 是队尾指针,指向队尾元素;N 是队列最大长度。2 【正确答案】 循环队列解决了用向量表示队列所出现的“假溢出” 问题,但同时又出现了如何判断队列的满与空问题。例如:在队列长 10 的循环队列中,若假定队头指针 front 指向队头元素的前一位置,而队尾指针指向队尾元素,则ffon=3,rear=7 的情况下,连续出队 4 个元素,则 front=rear 为队空;如果连续入队 6 个元素,则 front=rear 为队满。如何判断这种情况下的队满与队空,一般采取牺牲一个单元的做法或设标记法。即假设 front=rear 为队空, 而(rear+1

12、)表长=front 为队满,或通过设标记 tag。若 tag=0,front=rear 则为队空;若 tag=1,因入队而使得 fron=rear,则为队满。本题中队列尾指针 rear,指向队尾元素的下一位置,listarrayrear表示下一个入队的元素。在这种情况下,我们可规定,队头指针 front 指向队首元素。当 front=rear 时为队空,当(rear+1)n=front 时为队满。出队操作(在队列不空情况下)队头指针是 front=(front+1)n。3 【正确答案】 对于输入序列 a,b,c ,d,无论是输入受限的双端队列,还是输出受限的双端队列,其输出序列中,以 a,b,

13、c 开头的序列都有 6 个,如以 a 开头的有:abcd,abdc,acbd,acdb,adbc,adcb。但以元素 d 开头的只能得到 4 种序列。输入受限的双端队列不能得到 dbac 和 dbca,输出受限的双端队列不能得到 dbca 和dacb。故两种受限的双端队列均不能得到 dbca 输出序列。二、设计题4 【正确答案】 两栈共享向量空间,将两栈栈底设在向量两端,初始时,左栈栈顶指针为一 1,右栈栈顶指针为 maxsize。两栈顶指针相邻时为栈满。两栈顶相向,迎面增长,栈顶指针指向栈顶元素。typede f structElemType stackmaxsize;栈空间int top2

14、;top 为两个栈顶指针stk;入栈操作的核心语句段如下:if(Stop1 一 Stopo=1)coutx; 从键盘读入整数序列if(x!=一 1) 读入的整数不等于一 1 时入栈if(top=maxsize 一 1)coutch); break:case):if(StackEmpty(8)StackGetTop(s)!=()coutMaxValue(a,n 一 1)maxn=an; else maxn=MaxValue(a,n 一 1);10 【正确答案】 只是结果要最大和最小元素,现给出完整函数。void MinMaxValue(int A,int n,int stop1=t; retur

15、n(stop0); 算法结束 由于是尾递归,可以不使用栈,其非递归算法如下: int gcd(int m,n) 求正整数 m 和 rl 的最大公因子 if(mn)t=m;m=n;n=t;) 若 mrl,则 m 和n 互换 while(n!=0)t=tn;tll=n;n=七n; reLurn(m); 算法结束12 【正确答案】 int Ack(int m,n)if(m=0)return(n+1);else if(m!=0&n=0)return(Ack(m-1,1);else return(Ack(m-1,Ack(m,m 一 1);算法结束Ack(2,1)的计算过程:Ack(2,1)=Ack(1,

16、Ack(2,0) 因 m0 而得=Ack(1,Ack(1,1) 因 m0,n0,n=0 而得=Ack(1,Ack(0,2) 因 m=0 而得=Ack(1,3) 因 m=0 而得=Ack(0,Ack(1,2) 因 m0 而得=Ack(0,Ack(0,Ack(1 ,1) 因 m0 而得=Ack(0,Ack(0,Ack(0 ,Ack(1,0) 因 m0 而得=Ack(0,Ack(0,Ack(0 ,Ack(0,1) 因 mnext=p 一next;P 一next=s; 将 S 结点链入队尾p=s; P 指向新队尾出队的核心语句段如下:if(p-next=p) coutnext 一next;p-next

17、-next=s-next; s 指向队头元素,出队coutdatanext ; 空队列delete(s); 回收空间20 【正确答案】 循环队列的定义:typedef structElemType Qm;int rear,length;)SeQueue;rear 指向队尾元素,length 为元素数(1)设 cq 是 SeQueue 类型变量,当 cqlength=0 时队空,当 cq1ength=m 时队满。(2)SeQueue initqueue(SeQueue cq) cq 为循环队列,本算法进行队列初始化cqrear=0;cq 1ength=0; return cq;(3)SeQueu

18、e enqueue(SeQueue cq,ElemType x)入队算法,元素 x 入队if(cq1ength=m)return(0); 队满else fcqrear=(cq rear+1)m; 计算插入元素位置cqQcq rear=x; 将元素 x 入队列cq1ength+ ; 修改队列长度return(cq);) 算法结束(4)ElemType dlqueue(SeQueue cq) 出队算法,且返回出队元素if(cq1ength=0)return(0); 队空else(int front=(cqrearcq1ength+1+m)m; 出队元素位置cq1ength- 一; 修改队列长度re

19、turn(cqQfront); 返回队头元素 else) 算法结束21 【正确答案】 用一维数组 v0M-1实现循环队列,其中 M 是队列长度。设队头指针 front 和队尾指针 rear,约定 front 指向队头元素的前一位置,rear 指向队尾元素。定义 front=rear 时为队空,(rear+1)m=front 为队满。约定队头端入队向下标小的方向发展,队尾端入队向下标大的方向发展。(1)从队尾删除元素的核心语句段如下:if(Qfront=Qrear) Gout“队列空”end1;exit(0);)Qrear=(Q rear 一 1+M)M; 修改队尾指针return(Q data

20、(Qrear+1+M)M); 返回出队元素22 【正确答案】 从队头插入元素 X 的核心语句段如下:if(Qrear=(Qfront 一 1+M)M) cout“ 队满 ”endl; exit(0);)QdataQ front=x; x 入队列Qfront=(Qfront 一 1+M)M; 修改队头指针23 【正确答案】 根据队列先进先出和栈后进先出的性质,先将非空队列中的元素出队,并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈,依次插入初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素,最后退栈的元素(出队时第一个元素)成了最后入队的元素,从而实现了原队

21、列的逆置。核心语句段如下:makempty(s); 置空栈while(!isEmpty(Q) 队列 Q 中元素出队value=deQueue(Q);push(s ,value) ; 将出队元素压入栈中while(!isEmpty(s) 栈中元素退栈value=pop(s); enQueue(Q,value);) 将出栈元素入队列 Q24 【正确答案】 设数组下标从 0 开始,即数组 v0m 一 1。设每个循环队列长度(容量 )为 L,则循环队列的个数为 n=mL为了指示每个循环队列的队头和队尾,设如下结构类型: typedef structint f,r;)scq; scq qn; (1)初始化的核心语句: for(i=1;in)coutn)fprintf C 队列号错误n”) ;exit(0);) if(qir=qif) cout 第i 个循环队列从下标(i1)L 开始,到 iL 一 1 为止。设每个循环队列均用牺牲一个单元的办法来判断队满,即为(gir+1)L+(i-1)*L=qif 时,判定为队满。

copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1