2021年南京晓庄学院数据结构题库参考答案.docx
《2021年南京晓庄学院数据结构题库参考答案.docx》由会员分享,可在线阅读,更多相关《2021年南京晓庄学院数据结构题库参考答案.docx(39页珍藏版)》请在咨信网上搜索。
1、数据构造与算法习题册(课后某些参照答案)数据构造与算法课程组目录课后习题部分第一章 绪论1第二章 线性表3第三章 栈和队列5第四章 串8第五章 数组和广义表10第六章 树和二叉树13第七章 图16第九章 查找20第十章 排序23第一章 绪论一. 填空题1. 从逻辑关系上讲,数据构造类型重要分为 集合 、线性构造、树构造和 图构造。2. 数据存储构造重要有 顺序存储和 链式存储 两种基本办法,无论哪种存储构造,都要存储两方面内容:数据元素 和 数据元素之间关系 。3. 算法具备五个特性,分别是 有穷性 、拟定性、可行性、输入 、输出 。4. 算法设计规定中健壮性指是 算法在发生非法操作时可以作出
2、解决特性。二. 选取题1. 顺序存储构造中数据元素之间逻辑关系是由 C 表达,链接存储构造中数据元素之间逻辑关系是由 D 表达。A 线性构造 B 非线性构造 C 存储位置 D 指针2. 假设有如下遗产继承规则:丈夫和妻子可以互相继承遗产;子女可以继承爸爸或妈妈遗产;子女间不能互相继承。则表达该遗产继承关系最适当数据构造应当是 B 。A 树 B 图 C 线性表 D 集合3. 算法指是 A 。A 对特定问题求解环节一种描述,是指令有限序列。B 计算机程序 C 解决问题计算办法 D 数据解决三. 简答题1. 分析如下各程序段,并用大O记号表达其执行时间。(1) (2)i=1;k=0;i=1;k=0;
3、While(in-1)do k=k+10*i; k=k+10*i;i+; i+; while(inext =rear-next;rear-next =s;rear =s;;删除开始结点操作顺序为q=rear-next-next;rear-next-next=q-next;delete q;。 二. 选取题1.数据在计算机存储器内表达时物理地址与逻辑地址相似并且是持续,称之为: C A存储构造 B逻辑构造 C顺序存储构造 D链式存储构造2. 在n个结点顺序表中,算法时间复杂度是O(1)操作是: A A 访问第i个结点(1in)和求第i个结点直接前驱(2in) B 在第i个结点后插入一种新结点(1
4、in)C 删除第i个结点(1in) D 将n个结点从小到大排序3. 线性表L在 B 状况下合用于使用链式构造实现。A 需经常修改L中结点值 B 需不断对L进行删除插入C L中具有大量结点 D L中结点构造复杂4. 单链表存储密度 C A不不大于1 B等于1 C不大于1 D不能拟定三. 判断题1. 线性表逻辑顺序和存储顺序总是一致。 F 2. 线性表顺序存储构造优于链接存储构造。 F 3. 设p,q是指针,若p=q,则*p=*q。 F 4. 线性构造基本特性是:每个元素有且仅有一种直接前驱和一种直接后继。 F 四. 简答题1. 分析下列状况下,采用何种存储构造更好些。(1)若线性表总长度基本稳定
5、,且很少进行插入和删除操作,但规定以最迅速度存取线性表中元素。(2)如果n个线性表同步并存,并且在解决过程中各表长度会动态发生变化。(3)描述一种都市设计和规划。 应选用顺序存储构造。很少进行插入和删除操作,因此空间变化不大,且需要迅速存取,因此应选用顺序存储构造。 应选用链式存储构造。链表容易实现表容量扩充,适合表长度动态发生变化。 应选用链式存储构造。由于一种都市设计和规划涉及活动诸多,需要经常修改、扩充和删除各种信息,才干适应不断发展需要。而顺序表插入、删除效率低,故不适当。五. 算法设计1. 已知数组An中元素为整型,设计算法将其调节为左右两某些,左边所有元素为奇数,右边所有元素为偶数
6、,并规定算法时间复杂度为O(n)。2. 线性表存储在整型数组Aarrsize前elenum 个单元中,且递增有序。编写算法,将元素x插入到线性表恰当位置上,以保持线性表有序性,并且分析算法时间复杂度。int insert (datatype A,int *elenum,datatype x)/*设elenum为表最大下标*/if (*elenum=arrsize-1) return 0;/*表已满,无法插入*/else i=*elenum; while (i=0 & Aix)/*边找位置边移动*/Ai+1=Ai;i-; Ai+1=x;/*找到位置是插入位下一位*/ (*elenum)+;ret
7、urn 1;/*插入成功*/O(n)第三章 栈和队列一. 填空题1. 设有一种空栈,栈顶指针为1000H,既有输入序列为1. 2. 3. 4. 5, 通过push,push,pop,push,pop,push,push后,输出序列是 23 ,栈顶指针为 1003H 。2. 栈普通采用两种存储构造是 顺序栈 、链栈 ;其鉴定栈空条件分别是 TOP=-1 、 TOP=NULL ,鉴定栈满条件分别是 TOP=数组长度 、存储空间满 。3. 栈 可作为实现递归函数调用一种数据构造。4. 表达式a*(b+c)-d后缀表达式是 abc+*d- 。二. 选取题1. 若一种栈输入序列是1,2,3,n,输出序列
8、第一种元素是n,则第i个输出元素是 D 。A 不拟定 B n-i C n-i-1 D n-i+12. 设栈S和队列Q初始状态为空,元素e1. e2. e3. e4. e5. e6依次通过栈S,一种元素出栈后即进入队列Q,若6个元素出队顺序是e2. e4. e3. e6. e5. e1,则栈S容量至少应当是 C 。A 6 B 4 C 3 D 23. 一种栈入栈序列是1,2,3,4,5,则栈不也许输出序列是 C 。A 54321 B 45321 C 43512 D 12345 三. 判断题 1. 有n个元素依次进栈,则出栈序列有(n-1)/2种。 F 2. 栈可以作为实现过程调用一种数据构造。 T
9、 3. 在栈满状况下不能做进栈操作,否则将产生“上溢”。 T 4. 在循环队列中,front指向队头元素前一种位置,rear指向队尾元素位置,则队满条件是 front=rear。 F 四. 简答题1. 设有一种栈,元素进栈顺序为A,B,C,D,E,能否得到如下出栈序列,若能,请写出操作序列,若不能,请阐明因素。 C,E,A,B,D C,B,A,D,E不能,由于在C、E出栈后,A一定在栈中,并且在B下面,不也许先于B出栈可以,设为进栈操作,为入栈操作,则其操作序列为IIIOOOIOIO。2. 在操作序列push(1). push(2). pop. push(5). push(7). pop. p
10、ush(6)之后,栈顶元素和栈底元素分别是什么?(push(k)表达k入栈,pop表达栈顶元素出栈。)栈顶元素为6,栈底元素为1。3. 在操作序列EnQueue(1). EnQueue(3). DeQueue. EnQueue(5). EnQueue(7). DeQueue. EnQueue(9)之后,队头元素和队尾元素分别是什么?(EnQueue(k)表达整数k入队,DeQueue表达队头元素出队)。队头元素为5,队尾元素为9。4. 简述如下算法功能(栈元素类型SElemType为int)。 (1) status algo1(Stack S,int e) Stack T;int d;Init
11、Stack(T);while(!StackEmpty(S)Pop(S,d);if(d!=e) Push(T,d);while(!StackEmpty(T)Pop(T,d); Push(S,d); /S中如果存在e,则删除它。(2) void algo2(Queue &Q)Stack S; int d; InitStack(S);while(!QueueEmpty(Q)DeQueue(Q,d);Push(S,d);while(!StackEmpty(S)Pop(S,d);EnQueue(Q,d);/队列逆置五. 算法设计1. 试写一种鉴别表达式中开、闭括号与否配对浮现算法BOOL Bracket
12、Correspondency(char a)int i=0;Stack s;InitStack(s);ElemType x;while(ai)switch(ai)case (:Push(s,ai);break;case :Push(s,ai);break;case ):GetTop(s,x);if(x=()Pop(s,x);else return FALSE;break;case :GetTop(s,x);if(x=) Pop(s,x);else return FALSE;break;default:break;i+;if(s.size!=0) return FALSE;return TRUE
13、;2. 假设称正读和反读都相似字符序列为“回文”,例如,abba和abcba是回文,abcde和ababab则不是回文。试写一种算法鉴别读入一种以为结束符字符序列与否是“回文”。Status SymmetryString(char* p)Queue q;if(!InitQueue(q) return 0;Stack s;InitStack(s);ElemType e1,e2;while(*p)Push(s,*p);EnQueue(q,*p);p+;while(!StackEmpty(s)Pop(s,e1);DeQueue(q,e2);if(e1!=e2) return FALSE;return
14、 OK;第四章 串一. 填空题1. 不包括任何字符(长度为0)串 称为空串;由一种或各种空格(仅由空格符)构成串 称为空白串。2. 设S=“A;/document/Mary.doc”,则strlen(s)= 20 ,“/”字符定位位置为 3 。3. 若n为主串长,m为子串长,则串典型模式匹配算法最坏状况下需要比较字符总次数为 (n-m+1)*m 。二. 选取题1. 串是一种特殊线性表,其特殊性体当前: ( B )A可以顺序存储 B数据元素是一种字符 C可以链式存储 D数据元素可以是各种字符2. 设有两个串p和q,求q在p中初次浮现位置运算称作:( B ) A连接 B模式匹配 C求子串 D求串长
15、3. 设串s1=ABCDEFG,s2=PQRST,函数con(x,y)返回x和y串连接串,subs(s,i,j)返回串s从序号i开始j个字符构成子串,len(s)返回串s长度,则con(subs(s1,2,len(s2),subs(s1,len(s2),2)成果串是:( D ) A BCDEF B BCDEFG C BCPQRST D BCDEFEF4. 若串S=”software”,其子串数目是( B )。 A 8 B 37 C 36 D 9三. 计算题1. 设s=I AM A STUDENT,t=GOOD,q=WORKER,求:1)Replace(s,STUDENT,q) 2)Concat
16、(t,SubString(s,7,8)1、Replace(s,STUDENT,q)I AM A WORKER2、由于SubString(s,7,8) STUDENTConcat(t,SubString(s,7,8)GOOD STUDENT四. 算法设计1. 运用C库函数strlen,strcpy(或strncpy)写一种算法void StrDelete(char *S,int t,int m) ,删除串S中从位置i开始持续m个字符。若istrlen(S),则没有字符被删除;若i+mstrlen(S),则将S中从位置i开始直至末尾字符均被删去。提示:strlen是求串长(length)函数:in
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2021 南京 学院 数据结构 题库 参考答案
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【二***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【二***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。