2017年电大电大数据结构(本)形成性考核册(作业1-4)原题带答案.doc
《2017年电大电大数据结构(本)形成性考核册(作业1-4)原题带答案.doc》由会员分享,可在线阅读,更多相关《2017年电大电大数据结构(本)形成性考核册(作业1-4)原题带答案.doc(14页珍藏版)》请在咨信网上搜索。
1、数据结构(本)课程作业作业1(本部分作业覆盖教材第1-2章的内容)14一、单项选择题1在数据结构中,从逻辑上可以把数据结构分为(C )。A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部机构2下列说法中,不正确的是( D )。A数据元素是数据的基本单位 B数据项是数据中不可分割的最小可标识单位 C数据可有若干个数据元素构成 D数据项可由若干个数据元素构成3一个存储结点存储一个( B )。A数据项 B数据元素 C数据结构 D数据类型4数据结构中,与所使用的计算机无关的是数据的( C )。A存储结构 B物理结构C逻辑结构 D物理和存储结构5下列的叙述中,不属于算
2、法特性的是( D )。A有穷性 B输入性 C可行性 D可读性6算法分析的目的是( C )。 A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性7数据结构是一门研究计算机中(B )对象及其关系的科学。A数值运算 B非数值运算C集合 D非集合 8算法的时间复杂度与( C )有关。 A所使用的计算机 B与计算机的操作系统 C与算法本身 D与数据结构9设有一个长度为n的顺序表,要在第i个元素之前(也就是插入元素作为新表的第i个元素),则移动元素个数为( A )。 An-i+1 Bn-i Cn-i-1 Di10设有一个长度为n的顺序表,要删除第i
3、个元素移动元素的个数为( B )。 An-i+1 Bn-i Cn-i-1 Di11在一个单链表中,p、q分别指向表中两个相邻的结点,且q所指结点是p所指结点的直接后继,现要删除q所指结点,可用语句( C )。 Ap=q-next Bp-next=q Cp-next=qnext Dq-next=NULL12在一个单链表中p所指结点之后插入一个s所指的结点时,可执行( D )。 Ap-next= s; snext= pnext Bp-next=snext; Cp=s-next Ds-next=p-next; p-next=s;13非空的单向循环链表的尾结点满足(C )(设头指针为head,指针p指
4、向尾结点)。 A.P-next= =NULL BP= =NULL CP-next= =head DP= = head 14链表不具有的特点是( A )。 A可随机访问任一元素 B插入删除不需要移动元素 C不必事先估计存储空间 D所需空间与线性表长度成正比15带头结点的链表为空的判断条件是(B )(设头指针为head)。Ahead = =NULLBhead-next= =NULL Chead-next= =headDhead!=NULL16在一个单链表中,p、q分别指向表中两个相邻的结点,且q所指结点是p所指结点的直接后继,现要删除q所指结点,可用语句(C )。Ap=q-nextBp-next=
5、qCp-next=q-nextDq-next=NULL17在一个链队中,假设f和r分别为队头和队尾指针,则删除一个结点的运算为(C )。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;18在一个链队中,假设f和r分别为队头和队尾指针,则插入s所指结点的运算为( B )。 Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s;19.一个顺序表第一个元素的存储地址是90,每个元素的长度为2,则第6个元素的地址是(B )。A98 B100 C102 D10620有关线性表的正确说法是( D )。
6、A每个元素都有一个直接前驱和一个直接后继 B线性表至少要求一个元素C表中的元素必须按由小到大或由大到下排序 D除了一个和最后一个元素外,其余元素都有一个且仅有一个直接前驱和一个直接后继二、填空题1在一个长度为n的顺序存储结构的线性表中,向第i(1in+1)个元素之前插入新元素时,需向后移动 n-i+1 个数据元素。2从长度为n的采用顺序存储结构的线性表中删除第i(1in+1)个元素 ,需向前移动 n-i 个元素。3数据结构按结点间的关系,可分为4种逻辑结构: 集合 、 线性结构 、 树形结构 、 图状结构 。4数据的逻辑结构在计算机中的表示称为 物理结构 或 存储结构 。5除了第1个和最后一个
7、结点外,其余结点有且只有一个前驱结点和后继结点的数据结构为 线性结构 ,每个结点可有任意多个前驱和后继结点数的结构为 非线性结构 。6算法的5个重要特性是 有穷性 、 确定性 、 可形性 、 有零个或多个输入 、 有零个或多个输出 。7数据结构中的数据元素存在多对多的关系称为_图状结构_结构。8数据结构中的数据元素存在一对多的关系称为_树形结构_结构。9数据结构中的数据元素存在一对一的关系称为_线性结构_结构。10要求在n个数据元素中找其中值最大的元素,设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_ n-1_和 _ O(n)_ 。11在一个单链表中p所指结点之后插入一个s所指
8、结点时,应执行_ s-next=p-next _和p-next=s;的操作。12设有一个头指针为head的单向循环链表,p指向链表中的结点,若p-next= =_ head _,则p所指结点为尾结点。13在一个单向链表中,要删除p所指结点,已知q指向p所指结点的前驱结点。则可以用操作_ q-next=p-next _。14设有一个头指针为head的单向链表,p指向表中某一个结点,且有p-next= =NULL,通过操作_ p-next=head _,就可使该单向链表构造成单向循环链表。15每个结点只包含一个指针域的线性表叫 单链表 。16线性表具有 顺序存储 和 链式存储 两种存储结构。17数
9、据的逻辑结构是从逻辑关系上描述数据,它与数据的关系 存储结构 无关,是独立于计算机的。18在双向循环链表的每个结点中包含 两个 指针域,其中next指向它的 直接后继 ,prior指向它的 直接前驱 ,而头结点的prior指向 尾结点 ,尾结点的next指向 头结点 。19单向循环链表是单向链表的一种扩充,当单向链表带有头结点时,把单向链表中尾结点的指针域由空指针改为 头结点的指针 ;当单向链表不带头结点时,则把单向链表中尾结点的指针域由空指针改为指向 指向第一个结点的指针 。20线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致,而是一种 链式 存储结构
10、,又称为 链表 。 三、问答题1简述数据的逻辑结构和存储结构的区别与联系,它们如何影响算法的设计与实现?答:若用结点表示某个数据元素,则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见,数据的逻辑结构是反映数据之间的固有关系,而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同,逻辑上相邻的结点,其物理地址未必相同,但可通过结点的内部信息,找到其相邻的结点,从而保留了逻辑结构的特点。采用的存储结构不同,对数据的操作在灵活性,算法复杂度等方面差别较大。2解释顺序存储结构和链式存储结构的特点,并比较顺序存储结构和链式存储结构的优缺点。答
11、:顺序结构存储时,相邻数据元素的存放地址也相邻,即逻辑结构和存储结构是统一的,要求内存中存储单元的地址必须是连续的。优点:一般情况下,存储密度大,存储空间利用率高。缺点:(1)在做插入和删除操作时,需移动大量元素;(2)由于难以估计,必须预先分配较大的空间,往往使存储空间不能得到充分利用;(3)表的容量难以扩充。链式结构存储时,相邻数据元素可随意存放,所占空间分为两部分,一部分存放结点值,另一部分存放表示结点间关系的指针。优点:插入和删除元素时很方便,使用灵活。缺点:存储密度小,存储空间利用率低。3什么情况下用顺序表比链表好?答:顺序表适于做查找这样的静态操作,链表适于做插入和删除这样的动态操
12、作。如果线性表的变化长度变化不大,且其主要操作是查找,则采用顺序表;如果线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。4头指针、头结点、第一个结点(或称首元结点)的区别是什么?头结点是在链表的开始结点之前附加的一个结点;第一个结点(或称首元结点)是链表中存储第一个数据元素的结点;头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针。5解释带头结点的单链表和不带头结点的单链表的区别。答:带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。在结构上,带头结点的单链表,不管链表是否为空,均含有一个头结点,不带头结点的单链表不含头结点。在操作上,带头结点
13、的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点,算法步骤都相同。不带头结点的单链表,其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。四、程序填空题1下列是用尾插法建立带头结点的且有n个结点的单向链表的算法,请在空格内填上适当的语句。NODE *create1(n)/* 对线性表(1,2,.,n),建立带头结点的单向链表 */ NODE *head,*p,*q; int i; p=(NODE *)malloc(sizeof(NODE); head=p; q=p; p-next=NULL; for(i=1;idata=i
14、; (2)p-next=NULL ; (3)q-next=p ; (4) q=p ; return(head);2下列是用头插法建立带头结点的且有n个结点的单向链表的算法,请在空格内填上适当的语句。NODE *create2(n)/*对线性表(n,n-1,.,1),建立带头结点的线性链表 */ NODE *head,*p,*q; int i; p=(NODE *)malloc(sizeof(NODE); (1) head=p ; p-next=NULL; (2) q=p ; for(i=1;idata=i; if(i=1) (3) p-next=NULL ; else(4) p-next=q-
15、next ;(5) q-next=p ; return(head);3下列是在具有头结点单向列表中删除第i个结点,请在空格内填上适当的语句。int delete(NODE *head,int i)NODE *p,*q; int j; q=head;j=0; while(q!=NULL)&(jnext;j+; if(q=NULL) return(0);(1) p=q-next ; (2) q-next=p-next ; free(p); return(1);五、完成:实验1线性表根据实验要求(见教材P201-202)认真完成本实验,并提交实验报告。数据结构(本)课程作业2(本部分作业覆盖教材第3
16、-5章的内容)一、单项选择题1若让元素1,2,3依次进栈,则出栈顺序不可能为( C )。A3,2,1 B2,1,3 C3,1,2 D1,3,22一个队列的入队序列是1,2,3,4。则队列的输出序列是( B )。A4,3,2,1 B1,2,3,4 C1,4,3,2 D3,2,4,13向顺序栈中压入新元素时,应当( A )。A先移动栈顶指针,再存入元素 B先存入元素,再移动栈顶指针 C先后次序无关紧要 D同时进行4在一个栈顶指针为top的链栈中,将一个p指针所指的结点入栈,应执行( C )。Atop-next=p; Bp-next=top-next; top-next=p;Cp-next=top;
17、 top=p; Dp-next=top-next; top=top-next;5在一个栈顶指针为top的链栈中删除一个结点时,用 x保存被删结点的值,则执行( B )。Ax=top;top=top-next; Bx=top-data;Ctop=top-next; x=top-data; Dx=top-data; top=top-next;6一般情况下,将递归算法转换成等价的非递归算法应该设置( A )。A栈 B队列C堆栈或队列 D数组7表达式a*(b+c)-d的后缀表达式是( B )。 Aabcd*+- Babc+*d- Cabc*+d- D-+*abcd8判断一个顺序队列sq(最多元素为m0
18、)为空的条件是( C )。 Asq-rear-sq-front= m0 Bsq-rear-sq-front-1= = m0 Csq-front=sq-rear Dsq-front=sq-rear+19判断一个循环队列Q(最多元素为m0)为空的条件是( A )。 AQ-front=Q-rear BQ-front!=Q-rear CQ-front=(Q-rear+1)% m0 DQ-front!= (Q-rear+1)%m0 10判断栈S满(元素个数最多n个)的条件是(C )。 As-top=0 Bs-top!=0 Cs-top=n-1 Ds-top!=n-1 11一个队列的入队顺序是a,b,c,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2017 电大 数据结构 形成 考核 作业 原题带 答案
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。