数据结构习题集.docx
《数据结构习题集.docx》由会员分享,可在线阅读,更多相关《数据结构习题集.docx(29页珍藏版)》请在咨信网上搜索。
1、1 绪论一、选择题:1、下列算法的时间复杂度是( ) for(i=0;in;i+ +) ci=i; AO(1) BO(n) CO(log2n) DO(nlog2n)2、数据在计算机存储器内表示时,根据结点的关键字直接计算出该结点的存储地址,这种方法称为( ) A索引存储方法 B顺序存储方法 C链式存储方法 D散列存储方法 解析: 数据结构在计算机中的表示(映像)称为数据的物理(存储)结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法:顺序映象和非顺序映象,并由此得到两种不同的存储结构:顺序存储结构和链式存储结构。顺序存储方法:它是把逻辑上相邻的结点存储在物理位置相邻
2、的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现,由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法,通常借助于程序设计语言中的数组来实现。链式存储方法:它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构,链式存储结构通常借助于程序设计语言中的指针类型来实现。索引存储方法:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。散列存储方法:就是根据结点的关键字直接计算出该结点的存储地址。数据结构中,逻辑上(逻辑结构:数据元素之间的逻辑关系)可以把数据结构分成线性结构和非线性结构。线性结构的
3、顺序存储结构是一种随机存取的存储结构,线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。3、以下哪一个术语与数据的存储结构无关?( )。A.顺序表 B.链表C.散列表 D.队列4、算法在发生非法操作时可以做出处理的特性称为( )。A正确性B易读性C健壮性D高效性5、逻辑结构是指数据元素的( )。A关联方式 B存储方式C结构D数据项6、研究数据结构就是研究( )。A数据的逻辑结构B数据的存储结构C数据的逻辑结构和存储结构D数据的逻辑结构、存储结构及其数据的运算7、从逻
4、辑上可以把数据结构分为( )。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构8、以下有关数据的叙述中错误的是( )。A计算机能够处理的数据包括整数、实数、字符、声音、图像等B数据的逻辑结构是从逻辑关系上描述数据,它取决于数据的存储方式C数据存储结构的实现依赖于计算机语言D数据的运算是定义在数据的逻辑结构上的9、数据的基本单位是( )。A.数据结构 B.数据元素C.数据项 D.文件10、下列算法的时间复杂度是( ) for(i=0;im;i+ +) for(j=0;jn;j+ +) aij=i*j; AO(m2) BO(n2) CO(mn) DO
5、(m+n)11、算法分析的两个主要方面是( )。A正确性和简明性 B数据复杂性和程序复杂性C可读性和可维护性D时间复杂性和空间复杂性二、填空题:1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合,它包括三方面的内容,分别是数据的逻辑结构、( )和( )。2、数据的逻辑结构是从逻辑关系上描述数据,它与数据的()无关,是独立于计算机的。3、( )结构与数据元素本身的内容和形式无关。 4、程序段“for(i=1;i=n;i+) k+; for(j=1;j=n;j+) x=x+k;”的时间复杂度为( )。5、数据的存储结构(物理结构)可以用( )、( )、( )及散列存储等四种存储方法表示。
6、三、 判断题:1、顺序存储方式优点是存储密度大,且插入和删除运算效率高。 ( )2、顺序存储结构属于静态存储结构,链式存储结构属于动态存储结构。 ( )3、线性表的链接存储,表中元素的逻辑顺序与物理顺序一定相同。 ( )4、数据的机内表示称为数据的存储结构。 ( )5、在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定相邻。( )6、数据元素是数据的最小单位。 ( )7、基于某种逻辑结构之上的运算,其实现是惟一的。 ( )参考答案(绪论)一、选择题1234567891011BDDCADCBACD二、填空题1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合,它包括三方面
7、的内容,分别是数据的逻辑结构、(存储结构)和(运算)。2、数据的逻辑结构是从逻辑关系上描述数据,它与数据的()无关,是独立于计算机的。3、(逻辑)结构与数据元素本身的内容和形式无关。 4、程序段“for(i=1;i=n;i+) k+; for(j=1;jnext=P-next;P-next=S BP-next=S-next;S-next=P; CP-next=P;P-next=S; DP-next=S;S-next=P;3、在已知头指针的单链表中,要在其尾部插入一新结点,其算法所需的时间复杂度为( ) A(1) B(log2n) CO(n) DO(n2) 解析:单就插入运算而言,算法时间复杂度
8、为(1),但要将指针定位到链表末尾,指针移动的时间复杂度为O(n);4、对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( ) A顺序表 B用头指针表示的单循环链表 C用尾指针表示的单循环链表 D单链表 解析:尾指针是指向终端结点的指针,用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便,设一带头结点的单循环链表,其尾指针为rear,则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表,则查找终端结点的时间为O(n)。5、线性表是( ) A一个有限序列,可以为空 B一个有限序列,不能为空 C一个无
9、限序列,可以为空 D一个无限序列,不能为空6、在n个结点的双链表的某个结点前插入一个结点的时间复杂度是( ) AO(n) BO(1) CO(log2n) DO(n2)7、线性表采用链式存储时,结点的地址( ) A必须是连续的 B必须是不连续的 C连续与否均可 D必须有相等的间隔8、在单链表中,增加头结点的目的是( ) A使单链表至少有一结点 B标志表中首结点位置 C方便运算的实现 D说明单链表是线性表的链式存储实现9、带头结点的单链表head为空的判定条件是( ) Ahead = NULL; Bhead - next = NULL; Chead - next = head; Dhead ! =
10、 NULL;10、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为( ) A(1) B(n) C(n2) D(log2n)11、下列有关线性表的叙述中,正确的是( ) A线性表中的元素之间是线性关系 B线性表中至少有一个元素 C线性表中任何一个元素有且仅有一个直接前趋 D线性表中任何一个元素有且仅有一个直接后继12、在单链表中,存储每个结点需有两个域,一个是数据域,另一个是指针域,它指向该结点的( ) A直接前趋 B直接后继 C开始结点 D终端结点13、将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是( )。An B.2n-1 C.2n D.n-114、链表
11、不具有的特点是( )。A随机访问 B不必事先估计存储空间C插入删除时不需移动元素 D所需的空间与线性表成正比15、在一个单链表中,已知q所指结点是p所指结点的直接前趋,若在p,q之间插入s结点,则执行的操作是( )。 As-next=p-next;p-next=s; Bq-next=s;s-next=p;Cp-next=s-next;s-next=p; Dp-next=s;s-next=q;16、链表具有的特点是( )。A可随机访问任一元素B插入、删除需要移动元素C不必事先估计存储空间D存储空间是静态分配的17、一个顺序表一旦说明,其中可用空间大小( )A已固定B可以改变C不能固定D动态变化1
12、8、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用( )存储方式最节省时间。A 顺序表B单链表C双向链表D单循环链表19、两个指针P和Q,分别指向单链表的两个元素,P所指元素是Q所指元素的前驱的条件是( )。AP-next=QBQ-next=PCP=QDP-next=Q-next20、链表不具有的特点是( )。A可随机访问任一元素 B插入、删除不需要移动元素C不必事先估计存储空间 D所需空间与线性表长度成正比21、下面关于线性表的叙述中,错误的是( )。A线性表采用顺序存储,必须占用一片连续的存储单元B线性表采用顺序存储,便于进行插入和删除操作C线性表采用链接存储,不必
13、占用一片连续的存储单元D线性表采用链接存储,便于进行插入和删除操作22、在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是( )。A访问第i个结点(1in)和求第i个结点的直接前趋(2in)B在第i个结点后插入一个新结点(1in)C删除第i个结点(1in)D将n个结点从小到大排序23、在一个单链表中,若删除p指向结点的后继结点,则执行的操作为( )。Aq=p-next;p-next=p-next-next;free(q);Bp=p-next;q=p-next;p=q-next;free(q);Cq=p-next-next;p=p-next;free(q);Dp=p-next-next;q
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 习题集
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。