数据结构试题集(包含答案完整版).pdf
《数据结构试题集(包含答案完整版).pdf》由会员分享,可在线阅读,更多相关《数据结构试题集(包含答案完整版).pdf(78页珍藏版)》请在咨信网上搜索。
1、第一章第一章 概论概论一、选择题一、选择题1、研究数据结构就是研究(研究数据结构就是研究(D )。A.数据的逻辑结构数据的逻辑结构 B.数据的存储结构数据的存储结构 C.数据的逻辑结构和存储结构数据的逻辑结构和存储结构 D.数据的逻辑结构、存储结数据的逻辑结构、存储结构及其基本操作构及其基本操作2、算法分析的两个主要方面是(算法分析的两个主要方面是(A)。A.空间复杂度和时间复杂度空间复杂度和时间复杂度B.正确性和简单性正确性和简单性C.可可读性和文档性读性和文档性 D.数据复杂性和程序复杂性数据复杂性和程序复杂性3、具有线性结构的数据结构是(具有线性结构的数据结构是(D)。A.图图 B.树树
2、C.广义表广义表 D.栈栈4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、备输入、输出、(B )等)等5个特性。个特性。A.可执行性、可移植性和可扩充性可执行性、可移植性和可扩充性B.可执行性、有穷性可执行性、有穷性和确定性和确定性C.确定性、有穷性和稳定性确定性、有穷性和稳定性 D.易读性、稳定性和确易读性、稳定性和确定性定性5、下面程序段的时间复杂度是(、下面程序段的时间复杂度是(C)。for(i=0;im;i+)for(j=0;jn;j+)aij=i*j;A.O(m2)B.O(n2)C.O(m*n)D.
3、O(m+n)6、算法是(算法是(D )。A.计算机程序计算机程序 B.解决问题的计算方法解决问题的计算方法C.排排序算法序算法 D.解决问题的有限运算序列解决问题的有限运算序列7、某算法的语句执行频度为(、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示其时间复杂度表示(C )。A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n)8、下面程序段的时间复杂度为(下面程序段的时间复杂度为(C)。i=1;while(i=n)i=i*3;A.O(n)B.O(3n)C.O(log3n)D.O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元数据
4、结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的(素以及它们之间的()和运算等的学科)和运算等的学科。A.结构结构B.关系关系C.运算运算D.算法算法10、下面程序段的时间复杂度是(、下面程序段的时间复杂度是(A )。i=s=0;while(s=(y+1)*(y+1)y=y+1;A.O(n)B.C.O(1)D.O(n2)(nO二、填空题二、填空题1、程序段、程序段“i=1;while(inext=head B.p-next=NULL C.p=NULL D.p=head6、链表不具有的特点是、链表不具有的特点是()。A.可随机访问任一元素可随机访问任一元素B.插入删除不需要
5、移动元素插入删除不需要移动元素C.不必事先估计存储空间不必事先估计存储空间D.所需空间与线性表长度成正比所需空间与线性表长度成正比7、在双向循环链表中,在、在双向循环链表中,在p指针所指的结点后插入一个指针指针所指的结点后插入一个指针q所指向的所指向的新结点,修改指针的操作是(新结点,修改指针的操作是()。A.p-next=q;q-prior=p;p-next-prior=q;q-next=q;B.p-next=q;p-next-prior=q;q-prior=p;q-next=p-next;C.q-prior=p;q-next=p-next;p-next-prior=q;p-next=q;D
6、.q-next=p-next;q-prior=p;p-next=q;p-next=q;8、线性表采用链式存储时,结点的存储地址(、线性表采用链式存储时,结点的存储地址()。A.必须是连续的必须是连续的B.必须是不连续的必须是不连续的C.连续与否均可连续与否均可 D.和头结点的存储地址相连续和头结点的存储地址相连续9、在一个长度为、在一个长度为n的顺序表中删除第的顺序表中删除第i个元素,需要向前移动(个元素,需要向前移动()个)个元素元素。A.n-i B.n-i+1C.n-i-1 D.i+110、线性表是线性表是n个(个()的有限序列。)的有限序列。A.表元素表元素B.字符字符C.数据元素数据元
7、素D.数数据项据项11、从表中任一结点出发,都能扫描整个表的是(、从表中任一结点出发,都能扫描整个表的是()。A.单链表单链表 B.顺序表顺序表C.循环链表循环链表 D.静态链表静态链表12、在具有、在具有n个结点的单链表上查找值为个结点的单链表上查找值为x的元素时,其时间复杂度为的元素时,其时间复杂度为()。A.O(n)B.O(1)C.O(n2)D.O(n-1)13、线性表、线性表L=(a1,a2,an),下列说法正确的是下列说法正确的是()。A.每个元素都有一个直接前驱和一个直接后继每个元素都有一个直接前驱和一个直接后继 B.线性表中至少要有一个元素线性表中至少要有一个元素C.表中诸元素的
8、排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个和最后一个元素外,其余每个元素都由一个且仅有一除第一个和最后一个元素外,其余每个元素都由一个且仅有一个直接前驱和直接后继个直接前驱和直接后继14、一个顺序表的第一个元素的存储地址是、一个顺序表的第一个元素的存储地址是 90,每个元素的长度为,每个元素的长度为2,则第,则第 6 个元素的存储地址是(个元素的存储地址是()。A.98 B.100C.102 D.10615、在线性表的下列存储结构中,读取元素花费的时间最少的是(、在线性表的下列存储结构中,读取元素花费的时间最少的是()。A.单链表单链表 B.双链表
9、双链表 C.循环链表循环链表 D.顺顺序表序表16、在一个单链表中,若删除、在一个单链表中,若删除p所指向结点的后续结点,则执行所指向结点的后续结点,则执行()。A.p-next=p-next-next;B.p=p-next;p-next=p-next-next;C.p=p-next;D.p=p-next-next;17、将长度为、将长度为n的单链表连接在长度为的单链表连接在长度为m的单链表之后的算法的时间复杂的单链表之后的算法的时间复杂度为(度为()。A.O(1)B.O(n)C.O(m)D.O(m+n)18、线性表的顺序存储结构是一种(、线性表的顺序存储结构是一种()存储结构。)存储结构。A
10、.随机存取随机存取B.顺序存取顺序存取C.索引存取索引存取D.散列存取散列存取19、顺序表中,插入一个元素所需移动的元素平均数是(、顺序表中,插入一个元素所需移动的元素平均数是()。A.(n-1)/2 B.n C.n+1 D.(n+1)/210、循环链表的主要优点是(、循环链表的主要优点是()。A.不再需要头指针不再需要头指针 B.已知某结点位置后能容易找到其已知某结点位置后能容易找到其直接前驱直接前驱 C.在进行插入、删除运算时能保证链表不断开在进行插入、删除运算时能保证链表不断开 D.在表中任一结点出发都能扫描整个链表在表中任一结点出发都能扫描整个链表11、不带头结点的单链表、不带头结点的
11、单链表 head 为空的判定条件是(为空的判定条件是(A )。A.head=NULL B.head-next=NULL C.head-next=head D.head!=NULL答案答案 B 是带头结点的是带头结点的12、在下列对顺序表进行的操作中,算法时间复杂度为、在下列对顺序表进行的操作中,算法时间复杂度为O(1)的是(的是()。A.访问第访问第i个元素的前驱(个元素的前驱(1next=s-next;s-next=p;B.s-next=p;q-next=s-next;C.p-next=s-next;s-next=q;D.s-next=q;p-next=s-next;14、在以下的叙述中,正
12、确的是、在以下的叙述中,正确的是()。A.线性表的顺序存储结构优于链表存储结构线性表的顺序存储结构优于链表存储结构B.线性表的顺序存储结构适用于频繁插入线性表的顺序存储结构适用于频繁插入/删除数据元素的情况删除数据元素的情况C.线性表的链表存储结构适用于频繁插入线性表的链表存储结构适用于频繁插入/删除数据元素的情况删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构线性表的链表存储结构优于顺序存储结构15、在表长为、在表长为 n 的顺序表中,当在任何位置删除一个元素的概率相同时,的顺序表中,当在任何位置删除一个元素的概率相同时,删除一个元素所需移动的平均个数为(删除一个元素所需移动的平均
13、个数为()。A.(n-1)/2 B.n/2 C.(n+1)/2D.n16、在一个单链表中,已知、在一个单链表中,已知 q 所指结点是所指结点是 p 所指结点的前驱结点,若在所指结点的前驱结点,若在q 和和 p 之间插入一个结点之间插入一个结点 s,则执行(,则执行()。A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;C.q-next=s;s-next=p;D.p-next=s;s-next=q;17、在单链表中,指针、在单链表中,指针p指向元素为指向元素为x的结点,实现删除的结点,实现删除x的后继的语句的后继的语句是(是()。A.p=p-ne
14、xt;B.p-next=p-next-next;C.p-next=p;D.p=p-next-next;18、在头指针为、在头指针为head且表长大于且表长大于1的单循环链表中,指针的单循环链表中,指针p指向表中某指向表中某个结点,若个结点,若p-next-next=head,则(,则()。A.p指向头结点指向头结点B.p指向尾结点指向尾结点C.p的直接后继是的直接后继是头结点头结点D.p的直接后继是尾结点的直接后继是尾结点二、填空题二、填空题1、设单链表的结点结构为(、设单链表的结点结构为(data,next)。已知指针。已知指针p指向单链表中的指向单链表中的结点,结点,q指向新结点,欲将指向
15、新结点,欲将q插入到插入到p结点之后,则需要执行的语句:结点之后,则需要执行的语句:;。答案:答案:q-next=p-nextq-next=p-next p-next=qp-next=q2、线性表的逻辑结构是、线性表的逻辑结构是 ,其,其所含元素的个数称为线性表的所含元素的个数称为线性表的 。答案:线性结构答案:线性结构 长度长度3、写出带头结点的双向循环链表、写出带头结点的双向循环链表 L 为空表的条件为空表的条件 。答案:答案:L-prior=L-next=L4、带头结点的单链表、带头结点的单链表 head 为空的条件是为空的条件是 。答案:答案:head-next=NULL5、在一个单链
16、表中删除、在一个单链表中删除p所指结点的后继结点时,应执行以下操作:所指结点的后继结点时,应执行以下操作:q=p-next;p-next=_ q-next _;三、判断题三、判断题1、单链表不是一种随机存储结构。单链表不是一种随机存储结构。2、在具有头结点的单链表中,头指针指向链表的第一个数据结点。、在具有头结点的单链表中,头指针指向链表的第一个数据结点。3、用循环单链表表示的链队列中,可以不设队头指针,仅在队尾设置、用循环单链表表示的链队列中,可以不设队头指针,仅在队尾设置队尾指针。队尾指针。4、顺序存储方式只能用于存储线性结构。、顺序存储方式只能用于存储线性结构。5、在线性表的顺序存储结构
17、中,逻辑上相邻的两个元素但是在物理位、在线性表的顺序存储结构中,逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。置上不一定是相邻的。6、链式存储的线性表可以随机存取、链式存储的线性表可以随机存取。X四、程序分析填空题四、程序分析填空题1、函数、函数GetElem实现返回单链表的第实现返回单链表的第i个元素,请在空格处将算法补充个元素,请在空格处将算法补充完整。完整。int GetElem(LinkList L,int i,Elemtype*e)LinkList p;int j;p=L-next;j=1;while(p&ji)return ERROR;*e=(2);return OK;答案:
18、答案:(1)p=p-nextp=p-next (2)p-data(2)p-data2、函数实现单链表的插入算法,请在空格处将算法补充完整。、函数实现单链表的插入算法,请在空格处将算法补充完整。int ListInsert(LinkList L,int i,ElemType e)LNode*p,*s;int j;p=L;j=0;while(p!=NULL)&(jnext;j+;if(p=NULL|ji-1)return ERROR;s=(LNode*)malloc(sizeof(LNode);s-data=e;(1);(2);return OK;/*ListInsert*/答案:答案:(1)s-
19、next=p-nexts-next=p-next (2)p-next=s(2)p-next=s3、函数、函数ListDelete_sq实现顺序表删除算法,请在空格处将算法补充实现顺序表删除算法,请在空格处将算法补充完整。完整。int ListDelete_sq(Sqlist*L,int i)int k;if(iL-length)return ERROR;for(k=i-1;klength-1;k+)L-slistk=(1);(2);return OK;答案:(答案:(1)L-slistk+1L-slistk+1 (2 2)-L-Length-L-Length 4、函数实现单链表的删除算法,请在
20、空格处将算法补充完整。、函数实现单链表的删除算法,请在空格处将算法补充完整。int ListDelete(LinkList L,int i,ElemType*s)LNode*p,*q;int j;p=L;j=0;while((1))&(jnext;j+;if(p-next=NULL|ji-1)return ERROR;q=p-next;(2);*s=q-data;free(q);return OK;/*listDelete*/答案:答案:(1)p-next!=NULL (2)p-next=q-next5、写出算法的功能。、写出算法的功能。int L(head)node*head;int n=0
21、;node*p;p=head;while(p!=NULL)p=p-next;n+;return(n);答案:求单链表答案:求单链表head的长度的长度五、综合题五、综合题1、编写算法,实现带头结点单链表的逆置算法。、编写算法,实现带头结点单链表的逆置算法。答案:答案:void invent(Lnode*head)Lnode*p,*q;if(!head-next)return ERROR;p=head-next;q=p-next;p-next=NULL;while(q)p=q;q=q-next;p-next=head-next;head-next=p;2、有两个循环链表,链头指针分别为、有两个循
22、环链表,链头指针分别为 L1 和和 L2,要求写出算法将,要求写出算法将 L2 链链表链到表链到 L1 链表之后,且连接后仍保持循环链表形式。链表之后,且连接后仍保持循环链表形式。答案:答案:void merge(Lnode*L1,Lnode*L2)Lnode*p,*q;while(p-next!=L1)p=p-next;while(q-next!=L2)q=q-next;q-next=L1;p-next=L2;3、设一个带头结点的单向链表的头指针为、设一个带头结点的单向链表的头指针为 head,设计算法,将链表的,设计算法,将链表的记录,按照记录,按照 data 域的值递增排序。域的值递增排
23、序。答案:答案:void assending(Lnode*head)Lnode*p,*q,*r,*s;p=head-next;q=p-next;p-next=NULL;while(q)r=q;q=q-next;if(r-datadata)r-next=p;head-next=r;p=r;elsewhile(!p&r-datap-data)s=p;p=p-next;r-next=p;s-next=r;p=head-next;4、编写算法、编写算法,将一个头指针为将一个头指针为 head 不带头结点的单链表改造为一个单向不带头结点的单链表改造为一个单向循环链表,并分析算法的时间复杂度。循环链表,并
24、分析算法的时间复杂度。答案:答案:void linklist_c(Lnode*head)Lnode*p;p=head;if(!p)return ERROR;while(p-next!=NULL)p=p-next;p-next=head;设单链表的长度(数据结点数)为设单链表的长度(数据结点数)为 N,则该算法的时间主要花费在查找,则该算法的时间主要花费在查找链表最后一个结点上(算法中的链表最后一个结点上(算法中的 while 循环)循环),所以该算法的时间复杂,所以该算法的时间复杂度为度为 O(N)。5、已知、已知head为带头结点的单循环链表的头指针,链表中的数据元素依为带头结点的单循环链表
25、的头指针,链表中的数据元素依次为(次为(a1,a2,a3,a4,an),A为指向空的顺序表的指针。阅读以为指向空的顺序表的指针。阅读以下程序段,并回答问题:下程序段,并回答问题:(1)写出执行下列程序段后的顺序表)写出执行下列程序段后的顺序表A中的数据元素;中的数据元素;(2)简要叙述该程序段的功能。)简要叙述该程序段的功能。if(head-next!=head)p=head-next;A-length=0;while(p-next!=head)p=p-next;A-dataA-length+=p-data;if(p-next!=head)p=p-next;答案:答案:(1)(a2,a4,)(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 试题 包含 答案 完整版
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。