数据结构习题.doc
《数据结构习题.doc》由会员分享,可在线阅读,更多相关《数据结构习题.doc(25页珍藏版)》请在咨信网上搜索。
1、第1章 概论一、选择题1. 要求同一逻辑结构的所有数据元素具有相同的特性,这意味着( B )A、数据元素具有同一的特点。B、不仅数据元素包含的数据项的个数要相同,而且对应数据项的类型要一致。C、每个数据元素都一样。D、数据元素所包含的数据项的个数要相等。2. 数据结构是一门研究非数值计算的程序设计问题中计算机的( (c) )以及它们之间的( B )和运算的学科。(1)A、操作对象 B、计算方法 C、逻辑存储 D、数据映象(2)A、结构 B、关系 C、运算 D、算法3. 数据结构被形式的定义为(D,R),其中D是( (B) )的有限集合,R是D上( (D) )的有限集合。(1)A、算法 B、数据
2、元素 C、数据操作 D、逻辑结构(2)A、操作 B、映象 C、存储 D、关系4. 在数据结构中,从逻辑上可以把数据结构分为( C )A、动态结构和静态结构 B、紧凑结构和非紧凑结构C、线性结构和非线性结构 D、内部结构和外部结构5. 线性-表的顺序存储结构是一种( A )的存储结构。A、随机存取 B、顺序存取 C、索引存取 D、Hash存取6. 算法分析的目的是( C )A、找出数据结构的合理性 B、研究算法中的输入和输出的关系C、分析算法的效率以求改进 D、分析算法的易懂性和文档性7. 计算机算法指的是( (C) )。它必需具备输入、输出和( (B) )等五个特征。(1) A、计算方法 B、
3、排序方法 C、解决某一问题的有限运算序列 D、调度方法(2) A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性8. 线性表若采用链表存储结构时,要求内存中可用存储单元的地址( D)A、必须是连续的 B、部分地址必须是连续的C、一定是不连续的 D、连续不连续都可以9. 在以下的叙述中,正确的是(B )A、线性表的线性存储结构优于链式存储结构B、二维数组是它的每个数据元素为一个线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出10. 根据数据元素之间关系的不同特性,以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下
4、解释错误的是 ( A )A、集合中任何两个结点之间都有逻辑关系但组织形式松散B、线性结构中结点按逻辑关系依次排列形成一条锁链C、树形结构具有分支、层次特性,其形态有点像自然界中的树D、图状结构中的各个结点按逻辑关系互相缠绕,任何两个结点都可以邻接11. 以下说法正确的是( D )A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合二、判断题1. 数据元素是数据的最小单位。02. 数据结构是带有结构的数据元素的集合。13. 数据结构,数据元素,数据项在计算机中的映象分别称为存储结构,结点,数据域。14. 数据项是数据的
5、基本单位。05. 数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要建立的。16. 数据的物理结构是数据在计算机中实际的存储形式。17. 算法和程序没有区别,所以在数据结构中二者是通用的。08. 顺序存储结构属于静态结构,链式存储结构属于动态结构。0三、填空题1. 所谓数据的逻辑结构指的是数据元素之间的 _逻辑关系_。2. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合,它包括三方面的内容数据的逻辑结构、数据的存储结构、对数据施加的操作。3. 数据的逻辑结构包括 集合 、 线性结构 、 树形结构 和图状构图 四种类型。4. 在线性结构中,开始结点_没有_前驱结点,其余每个结
6、点有且只有_1_个结点。5. 在树形结构中,树根结点只有_1_,其余每个结点有且只有_1_前驱结点;叶子结点没有_后继_结点,其余每个结点的后继结点可以_任意个_。6. 在图形结构中,每个结点的前驱结点和后继结点可以有_任意个_。7. 算法的五个重要特性是_有穷性_、_确定性_、_可行性_、_输入_、_输出_。8. 下列程序段的时间复杂度是_。for (i=1;i=n;i+) Aij=0;9. 下列程序段的时间复杂度是_。s=0;for(i=1;i=n;i+) for(j=1;j=n;j+) s=s+Bij;sum=s;10. 存储结构是逻辑结构的_物理_实现。11. 从数据结构的观点看,通常
7、所说的数据应分成三个不同的层次,即_数据_、_数据元素_和_数据项_。12. 根据需要,数据元素又被称为_结点_、_记录_、_元素_或_顶点_。13. 通常,存储结点之间可以有_顺序存储、链式存储、索引存储、散列存储_、_、_、_四种关联方式,称为四种基本存储方式。14. 通常从_正确性、可读性、健壮性、高效性_、_、_、_等几方面评价算法的(包括程序)的质量。15. 一个算法的时空性能是指该算法的_时间复杂度_和_空间复杂度_,前者是算法包含的_计算量_,后者是算法需要的_存储量_。16. 在一般情况下,一个算法的时间复杂性是_问题规模_的函数。17. 常见时间复杂性的量级有:常数阶O(_1
8、_)、对数阶O(_)、线性阶O ( _n_)、平方阶O(_)、和指数阶O(_)。通常认为,具有指数阶量级的算法是_不可行_的。18. 数据结构的基本任务是数据结构的_设计_和_实现_。19. 数据对象是性质相同的 数据元素 的集合。20. 抽象数据类型是指一个 数学模型 以及定义在该模型上的一组操作。四、应用题1. 分析下列程序段的时间复杂度。i=1;WHILE(i=n)i=i*2;2. 叙述算法定义及其重要特性。3. 简述下列术语:数据,数据元素,数据结构,数据对象。4. 逻辑结构与存储结构是什么关系?5. 将数量级,n,n2,n3,nlog2n,log2n,2n,n!,按增长率进行排列。6
9、. 设有数据逻辑结构为:D=k1,k2,k3,k9R=,画出这个逻辑结构的图示,并确定相对于关系R,哪些结点是开始结点,哪些结点是终端结点?7. 设有如图1.1所示的逻辑结构图,给出它的逻辑结构,并说出它是什么类型的逻辑结构。k1k5k8k2k3k6k4k7图1.18. 分析下列程序的时间复杂度(设n为正整数) (1) int rec(int n) if(n=1) return(1); else return(n*rec(n-1); (2) x=91;y=100;while(y0) if(x10) y-;(3) i=1;j=0; while(i+jj) j+; else i+;(4) x=n;
10、y=0; while(x=(y+1)*(y+1) y+;9. 设n为正数。试确定下列各程序段中前置以记号的语句的频度:(1)i=1;k=0;while(i=n-1)k+=10*i; i+;(2) k=0; for(i=1;i=n;i+) for(j=i;jnext=NULL C、head-next=head D、head!=NULL10. 非空循环单链表head的尾结点*p满足( C )A、p-next=NULL B、p=NULL C、p-next=head D、p=head 11. 在循环双链表的*p结点之后插入*s结点的操作是( D )A、p-next=s; s-prior=p; p-ne
11、xt-prior=s; s-next=p-next;B、p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;C、s-prior=p; s-next=p-next;p-next:=s; p-next-prior=s; D、s-prior =p; snext=pnext; pnext-prior =s;p-next=s; 12. 在一个单链表中,已知*q结点是*p结点的前驱结点,若在*q和*p之间插入结点*s,则执行( C )A、s-next=p-next; p-next=s;B、p-next=s-next; s-next=p;C、q-next=s
12、; s-next=p;D、p-next=s; s-next=q;13. 在一个单链表中,若*p结点不是最后结点,在*p之后插入结点*s,则执行( B )A、s-next=p; p-next=s;B、s-next=p-next; p-next=s;C、s-next= p-next; p=s;D、p-next=s; s-next=p;14. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用( A )存储方式最节省时间。A、顺序表 B、单链表 C、双链表 D、单循环链表15. 设rear是指向非空带头结点的循环单链表的尾指针,则删除表中第一元素的操作可表示为(D )A、p=re
13、ar; rear=rear-next; free(p)B、rear=rear-next; free(rear);C、rear=rear-next-next; free(rear); D、p=rear-next-next; rear-next-next=p-next; free(p);16. 在一个单链表中,若删除*p结点的后继结点,则执行( A )A、q=pnext; pnext=qnext; free(q);B、p=p-next; p-next= p-next-next;free(p);C、p-next= p-next;free(p-next);D、p= p-next-next;free(p
14、-next);17. 设指针P指向双链表的某一结点,则双链表结构的对称性可用( C )式来刻画A、p-prior-next=p-next-nextB、p-prior-prior=p-next-priorC、p-prior-next=p-next-priorD、p-next-next=p-prior-prior18. 在循环链表中,将头指针改设为尾指针rear后,其头结点和尾结点的存储位置分别是 ( B )A、rear和rear-next-nextB、rear-next 和rearC、rear-next-next和rearD、rear和rear-next19. 循环链表主要优点是( D )A、不
15、再需要头指针了B、已知某个结点的位置后,能够容易找到它的直接前趋C、在进行插入、删除运算时,能更好地保证链表不断开D、从表中任一结点出发都能扫描到整个链表20. 在线性表的下列存储结构中,读取元素花费时间最少的是( D )A、单链表 B、双链表 C、循环链表 D、顺序表二、判断题1. 顺序存储的线性表可以随机存取。A2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价,因为平均每次操作只有近一半的元素需要移动。B3. 线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此是属于同一数据对象。A4. 在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上不一定相邻
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整 word 数据结构 习题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。