2023年电大数据结构本形成性考核册作业

数据结构（本)形成性考核作业册使用说明本作业册是中央广播电视大学计算机科与技术专业（本科）数据结构(本）课程形成性考核的依据,与《数据结构(本科）》教材（李伟生主编,中央电大出版社出版)配套使用。数据结构（本）课程是中央广播电视大学计算机科学技术专业的一门统设必修、学位课程，4学分,共72学时。其中实验24学时,开设一学期。本课程的特点是综合性、实践性强,内容抽象,在专业中具有承上启下的作用。因此，在学习本课程时，要注意理论联系实际，结合教学内容进行上机实践,认真完毕作业和实验内容。本课程的总成绩按百分制记分，其中形成性考核所占的比例为30%,终结性考试占7０％（闭卷，答题时限为９0分钟)。课程总成绩达成６０分及以上者为合格，可以获得该课程的学分。本课程的学位课程学分为70分，即课程总成绩达成70分及以上者有资格申请专业学位。本课程共设计了4次形考作业,每次形考作业均涉及实验内容,由各地电大根据学生对作业中各种题型练习和实验的完毕情况进行考核。对于实验内容规定按实验规定认真完毕，并提交实验报告。数据结构(本)课程作业作业1(本部分作业覆盖教材第1-２章的内容）一、单项选择题1．在数据结构中，从逻辑上可以把数据结构分为(）。A．动态结构和静态结构B．紧凑结构和非紧凑结构Ｃ.线性结构和非线性结构D.内部结构和外部机构2.下列说法中，不对的的是()。Ａ.数据元素是数据的基本单位Ｂ.数据项是数据中不可分割的最小可标记单位C．数据可有若干个数据元素构成Ｄ．数据项可由若干个数据元素构成3．一个存储结点存储一个（）。A.数据项Ｂ.数据元素C．数据结构D.数据类型４.数据结构中,与所使用的计算机无关的是数据的(）。A．存储结构Ｂ.物理结构C．逻辑结构D．物理和存储结构５．下列的叙述中,不属于算法特性的是()。A.有穷性B.输入性C．可行性D.可读性６．算法分析的目的是()。Ａ.找出数据结构的合理性B.研究算法中的输入和输出的关系Ｃ．分析算法的效率以求改善Ｄ.分析算法的易懂性和文档性７．数据结构是一门研究计算机中(

)对象及其关系的科学。A.数值运算

B．非数值运算C．集合

D.非集合8.算法的时间复杂度与（)有关。Ａ.所使用的计算机B．与计算机的操作系统Ｃ．与算法自身D．与数据结构9．设有一个长度为ｎ的顺序表，要在第i个元素之前(也就是插入元素作为新表的第ｉ个元素)，则移动元素个数为()。A．ｎ-i+1B．ｎ-iＣ.n-ｉ-1Ｄ.i1０.设有一个长度为n的顺序表,要删除第ｉ个元素移动元素的个数为(）。A.n-i+１B．n-iＣ.n-i-１D.i11.在一个单链表中,p、q分别指向表中两个相邻的结点，且ｑ所指结点是p所指结点的直接后继,现要删除q所指结点，可用语句()。A.p=ｑ->nexｔB．p->nexｔ=ｑＣ．p->ｎeｘt=qｎｅｘtD.q->ｎｅxt=ＮULL１2.在一个单链表中ｐ所指结点之后插入一个s所指的结点时,可执行(）。A.ｐ－>next=s;snext=pneｘtB.p->next=snexｔ;C.p=ｓ-＞nextD.s->next=p-＞nｅxt;p-＞ｎext＝s；13．非空的单向循环链表的尾结点满足(

）（设头指针为ｈead，指针p指向尾结点)。A．．P－>ｎext＝=NULLB．P==NULLC．P-＞nｅxｔ==headD.P=＝hｅad14．链表不具有的特点是(）。A．可随机访问任一元素Ｂ.插入删除不需要移动元素Ｃ．不必事先估计存储空间D.所需空间与线性表长度成正比15.带头结点的链表为空的判断条件是（

)(设头指针为ｈead）。Ａ．heａd==NULLＢ.ｈeaｄ->ｎext==NULL

C．head->next＝=heaｄ

Ｄ.heａd!＝NUＬL１6．在一个单链表中，p、q分别指向表中两个相邻的结点，且ｑ所指结点是p所指结点的直接后继,现要删除ｑ所指结点，可用语句(

)。A.p=q－>nｅxtB．p->neｘt＝ｑ

C．p－>nｅｘt=q->ｎextD.q->nｅｘt=NULL1７.在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为(）。Ａ.r=ｆ->next；B.r=r－＞nｅｘt;Ｃ.ｆ=f->neｘｔ;D.f＝r->ｎexｔ;１８．在一个链队中,假设f和r分别为队头和队尾指针,则插入s所指结点的运算为（)。Ａ．f->ｎｅｘt=s;ｆ=s;B.ｒ-＞neｘt＝s;r=s;C.s-＞nexｔ=r；ｒ=s;D.s->nｅxt=f;f=s;19.一个顺序表第一个元素的存储地址是９0,每个元素的长度为2,则第6个元素的地址是（）。A.9８B．100C．1０2D.１20．有关线性表的对的说法是（）。A．每个元素都有一个直接前驱和一个直接后继B.线性表至少规定一个元素C.表中的元素必须按由小到大或由大到下排序D．除了一个和最后一个元素外,其余元素都有一个且仅有一个直接前驱和一个直接后继二、填空题1．在一个长度为n的顺序存储结构的线性表中，向第i(1in+1)个元素之前插入新元素时,需向后移动个数据元素。2.从长度为n的采用顺序存储结构的线性表中删除第ｉ(1in+１)个元素,需向前移动个元素。3．数据结构按结点间的关系,可分为4种逻辑结构：、、、。4.数据的逻辑结构在计算机中的表达称为或。５.除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为，每个结点可有任意多个前驱和后继结点数的结构为。6．算法的５个重要特性是、、、、。7．数据结构中的数据元素存在多对多的关系称为________结构。８．数据结构中的数据元素存在一对多的关系称为＿_＿___＿_结构。9.数据结构中的数据元素存在一对一的关系称为______＿_结构。10．规定在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为____＿___和＿____＿＿＿。11．在一个单链表中ｐ所指结点之后插入一个ｓ所指结点时,应执行________和ｐ->ｎext＝s;的操作。12.设有一个头指针为hｅaｄ的单向循环链表,ｐ指向链表中的结点,若p-＞neｘt==__＿＿＿_＿_，则p所指结点为尾结点。13．在一个单向链表中,要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作＿__＿____。1４.设有一个头指针为heaｄ的单向链表,ｐ指向表中某一个结点,且有p->ｎeｘt=＝NULL，通过操作__＿___＿_，就可使该单向链表构导致单向循环链表。15．每个结点只包含一个指针域的线性表叫。１６．线性表具有和两种存储结构。17．数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系无关,是独立于计算机的。18．在双向循环链表的每个结点中包含指针域，其中next指向它的，prｉｏr指向它的,而头结点的pｒｉor指向,尾结点的nexｔ指向。19.单向循环链表是单向链表的一种扩充,当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为;当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向。20．线性链表的逻辑关系时通过每个结点指针域中的指针来表达的。其逻辑顺序和物理存储顺序不再一致，而是一种存储结构，又称为。三、问答题１.简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？2．解释顺序存储结构和链式存储结构的特点,并比较顺序存储结构和链式存储结构的优缺陷。３.什么情况下用顺序表比链表好？4．头指针、头结点、第一个结点(或称首元结点)的区别是什么？5.解释带头结点的单链表和不带头结点的单链表的区别。四、程序填空题１.下列是用尾插法建立带头结点的且有ｎ个结点的单向链表的算法,请在空格内填上适当的语句。NOＤE*creatｅ1(n）/*对线性表(１，2,．...．,n),建立带头结点的单向链表*／{ＮＯDE*hｅad,*p，*q;inti;p=(NODE*)maｌloc（siｚeｏｆ（NOＤE));hｅad=p；ｑ＝p；p->neｘｔ=ＮＵLL;for(ｉ=1;ｉ<=n;i++）{p=(NOＤE＊）malloｃ(sｉzｅof（NODE));(1）;ﻩ（2)； （３）;ﻩ(4）；｝ｒeｔuｒn（ｈead）;｝２．下列是用头插法建立带头结点的且有ｎ个结点的单向链表的算法，请在空格内填上适当的语句。ＮODE*ｃｒeａte2（ｎ)/*对线性表(ｎ,n－１,.．.．.,１),建立带头结点的线性链表*/{ＮODE*head,*ｐ,*q；inti；p=(NＯDＥ*)mａlloc(sｉｚeoｆ(ＮODE));(1）;p－>next＝NULL;（2）;for(ｉ＝１;i<=ｎ;i＋+)｛ｐ=(ＮODE*)ｍaｌloc(ｓizeof(NODＥ)）;ｐ->datａ＝i;ﻩiｆ(i==1）ﻩ(３）；ﻩﻩelse(4）；(5);}rｅturn(head)；｝3.下列是在具有头结点单向列表中删除第i个结点，请在空格内填上适当的语句。inｔｄeｌete(ＮODE*ｈead,inti){NODE*p,*q；ｉｎtj;q=heａd；j=0；while((ｑ!=NULL)&&(j＜i－1))/*找到要删除结点的直接前驱，并使q指向它*／{q＝q->next;j++;｝ｉf（ｑ==NＵＬL)return(0);（１）;（２）;frｅe(p);return（1);}五、完毕:实验1――线性表根据实验规定(见教材P201－２02)认真完毕本实验，并提交实验报告。数据结构(本）课程作业2(本部分作业覆盖教材第3－５章的内容)一、单项选择题1.若让元素1,2,3依次进栈,则出栈顺序不也许为()。A．3,2，１B．２，1,3C.3，1,2D．1,3，2２．一个队列的入队序列是1,2，3,4。则队列的输出序列是()。A．4,3,2，1B.1,2,3，４C.1，4，3，2Ｄ.3，２,4,13.向顺序栈中压入新元素时，应当(）。A．先移动栈顶指针,再存入元素B.先存入元素，再移动栈顶指针C．先后顺序无关紧要D．同时进行4.在一个栈顶指针为top的链栈中,将一个p指针所指的结点入栈,应执行（）。Ａ．top->nｅxt=p;B．p->next=top-＞nｅxt;tｏp-＞nｅxt＝p;C．p-＞nｅｘt＝ｔop；top=p;Ｄ．ｐ->nｅxt=tｏｐ->next;top=ｔoｐ－>nｅｘt；5.在一个栈顶指针为ｔop的链栈中删除一个结点时,用ｘ保存被删结点的值,则执行（)。A.x=ｔop;top=tｏp->next;Ｂ．x＝tｏｐ-＞ｄata;C.tｏp=ｔoｐ->next;ｘ=ｔop->dａta;D．x＝top->dａtａ;ｔop=toｐ－>ｎeｘt；6．一般情况下，将递归算法转换成等价的非递归算法应当设立（）。A.栈Ｂ．队列C.堆栈或队列Ｄ．数组7.表达式ａ＊（ｂ+c)-d的后缀表达式是()。A．ａｂcd*+-Ｂ．ａbc+*ｄ-C．aｂc*++d-D.-+＊aｂcd８.判断一个顺序队列ｓq（最多元素为m0)为空的条件是(）。Ａ．sq-＞ｒear－sｑ-＞fronｔ==m0B．ｓｑ－>ｒeａr-sq->froｎｔ-１==m０C．sq-＞fｒont==sq->reａrD．sｑ->ｆｒｏｎt＝＝sq->ｒear+１9．判断一个循环队列Q(最多元素为m0）为空的条件是（)。A．Q->front=＝Ｑ->ｒearB.Ｑ->front!=Q－＞reａrC．Q->ｆront=＝（Ｑ->ｒｅar＋1)%m０D.Q-＞fｒoｎｔ!=(Q->rｅar+１)%m０1０.判断一个循环队列Q(最多元素为ｍ0)为空的条件是（）。A．Q->fronｔ==Q－>reaｒB．Q-＞front!=Q->reａrC.Q->frｏnｔ=＝(Q－>rｅaｒ+１）%m０D．Q->fｒont!=(Q->reａｒ+1)%ｍ０1１．判断栈Ｓ满（元素个数最多ｎ个)的条件是（)。A．s->top==0B.s->ｔｏp!=0C．s->top＝＝ｎ-1D.s-＞ｔop!＝n－112．一个队列的入队顺序是a,b,ｃ,ｄ，则离队的顺序是()。A．a,d,cbＢ．ａ，b,ｃ,dC．d，c,ｂ,ａD．ｃ,b,d，ａ1３.假如以链表作为栈的存储结构，则退栈操作时(）。A.必须判断栈是否满B.判断栈元素类型C.必须判断栈是否空D.对栈不作任何判断14．在解决计算机主机与打印机之间速度不匹配问题时通常设立一个打印数据缓冲区,主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应当是一个（）结构。Ａ．堆栈Ｂ．队列C.数组Ｄ．先性表15．一个递归算法必须涉及(）。A．递归部分ﻩ B.终止条件和递归部分 Ｃ.迭代部分ﻩD.终止条件和迭代部分1６．从一个栈顶指针为ｔoｐ的链栈中删除一个结点时,用变量x保存被删结点的值,则执行(）。Ａ.x=ｔop-＞data;top=toｐ->nｅxt;B.ｘ＝top->daｔa；C．top=tｏp->next;ｘ=top->datａ；D.top=ｔop->nｅxt；x=data;17．在一个链队中,假设f和r分别为队头和队尾指针,则删除一个结点的运算为（）。A．r=f－>nｅxt；Ｂ．r=ｒ->ｎexｔ；Ｃ.f=f->ｎext；D．f=r->nｅxｔ;18．在一个链队中,假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（）。A．f-＞next=s；f=s;Ｂ．r-＞neｘt=s;r=s;C.s->ｎext=r；ｒ=s；D．s->next=f;f=s;19.以下陈述中对的的是(）。A.串是一种特殊的线性表B．串的长度必须大于零Ｃ.串中元素只能是字母D.空串就是空白串２0．设有两个串p和q,其中q是p的子串,q在p中初次出现的位置的算法称为（)。Ａ．求子串B.连接Ｃ.匹配D.求串长２1.串是（)。A．不少于一个字母的序列B．任意个字母的序列C.不少于一个字符的序列D.有限个字符的序列22.串的长度是指（)。A.串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数23.若串S==“Eｎglish”,其子串的个数是()。A．9B．1６Ｃ24.下面关于串的叙述中，不对的的是（）。Ａ．串是字符的有限序列B.空串是由空格构成的串Ｃ.模式匹配是串的一种重要运算D．串即可以采用顺序存储，也可以采用链式存储２5.串与普通的线性表相比较，它的特殊性体现在(）。Ａ．顺序的存储结构B．链接的存储结构Ｃ.数据元素是一个字符D.数据元素可以任意26．空串与空格串()。Ａ.相同Ｂ.不相同C．也许相同D.无法拟定２7．两个字符串相等的条件是()。A.两串的长度相等B.两串包含的字符相同Ｃ.两串的长度相等，并且两串包含的字符相同Ｄ.两串的长度相等，并且相应位置上的字符相同28.在实际应用中,要输入多个字符串,且长度无法预定。则应当采用()存储比较合适(）。Ａ．链式Ｂ．顺序Ｃ.堆结构D.无法拟定２9.一维数组A采用顺序存储结构,每个元素占用6个字节,第６个元素的存储地址为100,则该数组的首地址是（)。A．64B.28C.7０Ｄ.90３0.稀疏矩阵采用压缩存储的目的重要是(）。A.表达变得简朴B．对矩阵元素的存取变得简朴C．去掉矩阵中的多余元素D.减少不必要的存储空间的开销３1.一个非空广义表的表头（）。A.不也许是原子B.只能是子表Ｃ.只能是原子D.可以是子表或原子32．常对数组进行的两种基本操作是(）。Ａ.建立与删除Ｂ．索引与、和修改C.查找和修改D．查找与索引33．设二维数组A[5][6]按行优先顺序存储在内存中,已知A［0][0]起始地址为100０，每个数组元素占用5个存储单元,则元素A[４][4]的地址为（)。Ａ.1140B．１１45C.1120D.112534.设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始),则矩阵中元素a９,2在一维数组B中的下标是（)。A.41B．32C35．一个非空广义表的表头(）。A．不也许是子表B．只能是子表Ｃ.只能是原子Ｄ.可以是子表或原子二、填空题1．栈是限定在表的一端进行插入和删除操作的线性表，又称为。2.队列的特性是。3．往栈中插入元素的操作方式是:先，后。４.删除栈中元素的操作方式是:先,后。5.循环队列队头指针在队尾指针位置,队列是“满”状态６.在队列的顺序存储结构中，当插入一个新的队列元素时,尾指针，当删除一个元素队列时，头指针。7.循环队列的引入,目的是为了克服。8.向顺序栈插入新元素分为三步：第一步进行判断，判断条件是；第二步是修改；第三步是把新元素赋给。同样从顺序栈删除元素分为三步：第一步进行判断，判断条件是。第二步是把；第三步。９．假设以S和X分别表达入栈和出栈操作，则对输入序列a，b，ｃ,d,e一系列栈操作SSXSXSSXXＸ之后，得到的输出序列为。10.一个递归算法必须涉及和。11．判断一个循环队列ＬU（最多元素为m0)为空的条件是。１2.在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中,都需要使用栈,对于前者,进入栈中的元素为表达式中的,而对于后者,进入栈的元素为，中缀表达式(a＋b)/c-（f-d/ｃ)所相应的后缀表达式是。1６．向一个栈顶指针为h的链栈中插入一个s所指结点时,可执行____＿___和h=s;操作。(结点的指针域为next）１7.从一个栈顶指针为h的链栈中删除一个结点时,用x保存被删结点的值，可执行x=h－>dａta;和＿＿_＿__＿＿。（结点的指针域为nｅｘt）１8．在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为_＿______和r=s；（结点的指针域为next）19．在一个链队中，设ｆ和r分别为队头和队尾指针，则删除一个结点的操作为________。(结点的指针域为nｅｘt)２０．串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是。21．串的两种最基本的存储方式是和。22.空串的长度是;空格串的长度是。23．需要压缩存储的矩阵可分为矩阵和矩阵两种。2４．设广义表Ｌ=((），()）,则表头是,表尾是，L的长度是。2５.广义表Ａ(（a,b,c)，(d，e,f））的表尾为。26．两个串相等的充足必要条件是___＿___＿__。27．设有n阶对称矩阵Ａ,用数组s进行压缩存储,当iｊ时，A的数组元素aｉj相应于数组s的数组元素的下标为____＿＿＿。(数组元素的下标从1开始）2８.对稀疏矩阵进行压缩存储，矩阵中每个非零元素相应的三元组涉及该元素的＿_＿＿_＿_、_____＿_和_＿_＿＿__三项信息。三、问答题1．简述栈和一般线性表的区别。2．简述队列和一般线性表的区别。3．链栈中为什么不设头结点？4．运用一个栈，则:（1）假如输入序列由A，B，C组成，试给出所有也许的输出序列和不也许的输出序列。（2）假如输入序列由A,B，C，D组成,试给出所有也许的输出序列和不也许的输出序列。5．用S表达入栈操作，X表达出栈操作，若元素入栈顺序为12３４，为了得到1342出栈顺序，相应的Ｓ和X操作串是什么?６．有5个元素,其入栈顺序为:A、B、C、D、E,在各种也许的出栈顺序中，以元素C、D最先的顺序有哪几个?7．写出以下运算式的后缀算术运算式⑴３x2+ｘ－1/x+５⑵(Ａ+Ｂ)*C-D／(E+F)＋G８.在什么情况下可以用递归解决问题？在写递归程序时应注意什么？9．简述广义表和线性表的区别和联系。四、程序填空题1．在下面空格处填写适当的语句,以使下面的循环队列的入队和出队算法完整。ｄefineＴRUE1;defiｎｅFALSE0;defｉneMAＸＳIＺＥ100;tyｐedeｆcharｅlｅｍtｙpe；ｔypedefstrucｔ{Elemtypeｑｕeue［ＭAXSＩＺＥ］；intfront,rｅａr;}sequeｕｅtype;SｅqｕeueｔypeQ;intencqueｕｅ(sequｅuetype*Q,eｌemtypex）ｉｆ(（1)）Prinｔf(〝Thecicularqueueisfｕll!\n〞)；returｎ(FALSＥ）;eｌｓｅ(２）(３)return（TRUE);｝/*encqｕｅue*/ｅlemtｙpedel_cｑuｅue(sequeuetype＊Ｑ)ｉｆ((4))Printf(〝Theqｕeueisemｐtｙ！＼n〞）reｔurn（NUＬL);else(5)Reｔｕｒn（Q－queuｅ[Ｑ->ｆrｏｎt］);/*deｌ＿cqueuｅ*/２.在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。ｉntwrite(LｉnｋQｕeue*q）{QｕeueＮode*p；if(ｑ->ｆｒont=＝ｑ->ｒeaｒ）/*队空*/{ｐriｎtｆ(“undｅrflｏw”);exit(0);}while(q->fronｔ->nｅxt！=NULL){p=q-＞ｆrｏnt->nｅxt；（1）pｒiｎtf（“%4d”，ｐ->data）；(2)｝（3）；／*队空时，头尾指针指向头结点*/｝五、综合题１.设栈S和队列Q的初始状态为空，元素e1,e２,e3，e４,e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是ｅ２,e4,e3，e6,e5,ｅ1，则栈S的容量至少应当是多少？2．假设用循环单链表实现循环队列,该队列只使用一个尾指针rｅar,其相应的存储结构和基本算法如下；（1)初始化队列ｉnitqueue（Q）：建立一个新的空队列Ｑ。(2）入队列eｎqｕeｕe（Q,x):将元素ｘ插入到队列Q中。(３）出队列ｄｅｌqueue(Q）：从队列Ｑ中退出一个元素。(４）取队首元素geｔheaｄ(Q):返回当前队首元素。(5)判断队列是否为空:ｅmｐtyqｕｅue（Q)。（6)显示队列中元素：dispqｕｅue(Q)。六、完毕:实验２――栈、队列、递归程序设计根据实验规定(见教材P20３)认真完毕本实验,并提交实验报告。数据结构(本)课程作业作业3(本部分作业覆盖教材第６－7章的内容)一、单项选择题1.假定一棵二叉树中，双分支结点数为1５，单分支结点数为３0,则叶子结点数为（)。A．15Ｂ．1６C2．二叉树第k层上最多有()个结点。A.2ｋB．2k-１C.２ｋ-1D．2ｋ-13．二叉树的深度为k,则二叉树最多有()个结点。A．2kB.2k－1C.2k-1Ｄ.2k-14.设某一二叉树先序遍历为abdec,中序遍历为dbeac,则该二叉树后序遍历的顺序是()。A.abdｅcB.debａｃC．debｃａD．abedｃ５.树最适合于用来表达（)。A．线性结构的数据B．顺序结构的数据C．元素之间无前驱和后继关系的数据D．元素之间有包含和层次关系的数据6．设a,b为一棵二叉树的两个结点,在后续遍历中，ａ在b前的条件是()。A.a在ｂ上方Ｂ．ａ在b下方C.a在b左方D．a在b右方7．权值为{１,2，6,8}的四个结点构成的哈夫曼树的带权途径长度是（)。A．１8Ｂ.28C．１9Ｄ.298．将具有150个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为6９的结点的双亲结点的编号为（)。A.33Ｂ．3４Ｃ.３5D.３６9.假如将给定的一组数据作为叶子数值,所构造出的二叉树的带权途径长度最小，则该树称为（)。A.哈夫曼树B．平衡二叉树C．二叉树Ｄ．完全二叉树1０.下列有关二叉树的说法对的的是（)。A.二叉树中度为0的结点的个数等于度为2的结点的个数加１Ｂ.二叉树中结点个数必大于０C．完全二叉树中，任何一个结点的度,或者为0或者为2D．二叉树的度是2１1.在一棵度为３的树中，度为3的结点个数为２，度为2的结点个数为１,则度为0的结点个数为（）。A．4B．5C．６D.７12．在一棵度具有5层的满二叉树中结点总数为()。Ａ．３１B．32Ｃ.33D.16１3．运用n个值作为叶结点的权生成的哈夫曼树中共包具有(）个结点。Ａ.nB.n+１C．2＊nＤ.2*ｎ-114.运用n个值作为叶结点的权生成的哈夫曼树中共包具有（)个双支结点。A.nB.n-1Ｃ．n+1D．2１5.运用3、６、8、12这四个值作为叶子结点的权,生成一棵哈夫曼树，该树中所有叶子的最长带权途径长度为()。Ａ．18B.16C.12Ｄ．316．在一棵树中,()没有前驱结点。A.分支结点B．叶结点C．树根结点D.空结点17．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为()。A.2iＢ．2i-1D．2ｉ＋118．设一棵哈夫曼树共有n个叶结点，则该树有（）个非叶结点。Ａ.nＢ.ｎ-1C．n＋11９.设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有(）个结点。A．2nB．２ｎ－1C.２ｎ+1Ｄ．2ｎ+2２0.一棵完全二叉树共有5层，且第5层上有六个结点,该树共有（）个结点。A.20B.２1C.23Ｄ21.在一个图G中，所有顶点的度数之和等于所有边数之和的(）倍。A.1／2B.1C．2Ｄ.422．在一个有像图中,所有顶点的入度之和等于所有顶点的出度之和的(）倍。A.邻接矩阵表达法Ｂ．邻接表表达法C．逆邻接表表达法D.邻接表和逆邻接表2３．在图的存储结构表达中,表达形式唯一的是()。A.nB．n１Ｃ．ｎ1D.n／224.一个具有n个顶点的无向完全图包含（）条边。A.n（n1）B．n（ｎ1）C.n(n1）／2D.n（n1)／２25．一个具有n个顶点的有向完全图包含（）条边。A．ｎ（n1）Ｂ.n(n1）C．ｎ（ｎ1）/2D．n(ｎ1)/2２６.对于具有n个顶点的图，若采用邻接矩阵表达，则该矩阵的大小为(）。Ａ．ｎＢ.n2C.n1D．(n1)27．对于一个具有n个顶点和ｅ条边的无向图,若采用邻接表表达，则表头向量的大小为（)。A．nＢ.ｅC.2nD.2ｅ28．对于一个具有n个顶点和e条边的无向图，若采用邻接表表达，则所有顶点邻接表中的结点总数为()。A．ｎB.ｅC.2nD.２e２９.在有向图的邻接表中,每个顶点邻接表链接着该顶点所有（）邻接点。Ａ．入边B．出边C．入边和出边D.不是入边也不是出边3０.在有向图的逆邻接表中,每个顶点邻接表链接着该顶点所有()邻接点。A.入边B.出边C．入边和出边D．不是入边也不是出边31．邻接表是图的一种()。A.顺序存储结构B．链式存储结构C.索引存储结构D．散列存储结构32．假如从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是（）。A.完全图B．连通图Ｃ．有回路Ｄ．一棵树33．下列有关图遍历的说法不对的的是（）。A.连通图的深度优先搜索是一个递归过程B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特性C.非连通图不能用深度优先搜索法Ｄ．图的遍历规定每一顶点仅被访问一次34.无向图的邻接矩阵是一个()。ﻩA.对称矩阵B．零矩阵C.上三角矩阵D.对角矩阵3５．图的深度优先遍历算法类似于二叉树的（)遍历。Ａ．先序B.中序C.后序D.层次３6.已知下图所示的一个图,若从顶点V1出发,按深度优先搜索法进行遍历,则也许得到的一种顶点序列为()。A.Ｖ1V2V4Ｖ8V3Ｖ５V6V7B.V1V２V4V５V8V3V6V7Ｃ．V1V2V4Ｖ８V5Ｖ3Ｖ6V7D.V1V3Ｖ6V7V2Ｖ4Ｖ5V8V6V6V7V1V2V3V8V4V5二、填空题1．结点的度是指结点所拥有的。2．树的度是指。3.度大于０的结点称作或。4.度等于0的结点称作或。5.在一棵树中,每个结点的或者说每个结点的称为该结点的,简称为孩子。６.一个结点称为其后继结点的。7.具有的结点互称为兄弟结点，简称为兄弟。８．每个结点的所有子树中的结点被称为该结点的。9.从根结点到该结点所经分支上的所有结点称为该结点的。10.树的深度或高度是指。11.m(ｍ0)棵互不相交的树的集合称为。12．度为k的树中的第i层上最多有结点。１3．深度为k的二叉树最多有结点。14.在一棵二叉树中,假如树中的每一层都是满的,则称此树为;但假如出最后一层外,其余层都是满的,并且最后一层是满的，或者是在缺少若干连续个结点,则称此二叉树为。１5.具有n个结点的完全二叉树的深度是。16.先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作,否则进行如下操作，访问二叉树的;先序遍历二叉树的，先序遍历二叉树的。17．中序遍历二叉树的的操作定义为；若二叉树为空,则为空操作，否则进行如下操作，中序遍历二叉树的;访问而叉树的,中序遍历二叉树的。1８.后序遍历二叉树的的操作定义为;若二叉树为空，则为空操作,否则进行如下操作,后序遍历二叉树的;后序遍历二叉树的，访问而叉树的。１9.将树中结点赋上一个有着某种意义的实数，称此实数为该结点的。２0.树的带权途径长度为树中所有叶子结点的。21．哈夫曼树又称为,它是n个带权叶子结点构成的所有二叉树中带权途径长度WPL。22．若以４，5，６，7,８作为叶子结点的权值构造哈夫曼树，则其带权途径长度是。23．具有m个叶子结点的哈夫曼树共有结点。2４．在图中,任何两个数据元素之间都也许存在关系,因此图的数据元素之间是一种的关系。25．图的邻接矩阵表达法是用一个来表达图中顶点之间的相邻关系。２6．邻接表是图中的每个顶点建立一个邻接关系的。27．图的遍历是从图的某一顶点出发,按照一定的搜索方法对图中各做访问的过程。28．图的深度优先搜索遍历类似于树的遍历。２9.图的广度优先搜索类似于树的遍历。３0．具有n个顶点的有向图的邻接矩阵，其元素个数为。30.具有n个顶点的无向图至少有条边,才干保证其为一个连通图。31.图常用的两种存储结构是和。32.一个AOＶ网(顶点活动图)应当是一个。即不应当带有回路,否则回路上的所有活动都。３3．用邻接矩阵存储有向图G，其第ｉ行的所有元素之和等于顶点i的。34.在有n个顶点的有向图中,每个顶点的度最大可达。35.在一个带权图中,两顶点之间的最段途径最多通过条边。36．为了实现图的深度优先搜索遍历,其非递归的算法中需要使用的一个辅助数据结构为。三、综合题1．写出如下图所示的二叉树的先序、中序和后序遍历序列。aajfghidceb2．已知某二叉树的先序遍历结果是：A,B，D，G，C，E,H，L，Ｉ,Ｋ，M,Ｆ和Ｊ,它的中序遍历结果是:G,D,B,Ａ,Ｌ，H，Ｅ,K,I，Ｍ，C，F和J,请画出这棵二叉树,并写出该二叉树后续遍历的结果。3．已知一棵完全二叉树共有８９２个结点，求⑴树的高度⑵叶子结点数⑶单支结点数⑷最后一个非终端结点的序号4.给出满足下列条件的所有二叉树。(1）先序和中序相同(2)中序和后序相同（3）先序和后序相同5．假设通信用的报文由９个字母A、B、C、D、Ｅ、Ｆ、Ｇ、H和I组成,它们出现的频率分别是:１0、2０、5、15、8、2、3、７和30。请请用这９个字母出现的频率作为权值求：（1）设计一棵哈夫曼树；(2)计算其带权途径长度WPＬ;（3）写出每个字符的哈夫曼编码。６.请根据以下带权有向图G（1）给出从结点v1出发分别按深度优先搜索遍历G和广度优先搜索遍历G所得的结点序列；（2)给出G的一个拓扑序列;（3）给出从结点ｖ1到结点v8的最短途径。7.已知无向图Ｇ描述如下：G=(V,E）V={V1,Ｖ2,V3,V4，Ｖ5}E={(Ｖ１,V２），（Ｖ1,V4)，(Ｖ2，Ｖ4)，(Ｖ3,Ｖ4）,(V2,V5）,(V3,V4），（V3,V5)}（1)画出Ｇ的图示；(2）然后给出Ｇ的邻接矩阵和邻接表;(3)写出每个顶点的度。8．回答下列问题：⑴对于存储结构采用邻接矩阵的无向图,如何判断下列有关问题?①图中有多少条边？②任意两顶点间是否有边相连？③任意一个顶点的度是多少?⑵对于存储结构采用邻接表的有向图,如何判断下列有关问题?①图中有多少条边?②图中是否存在从Vi到Vj的边？③如何求顶点Vi的入度和出度？四、程序填空题１.下面函数的功能是返回二叉树BＴ中值为X的结点所在的层号,请在划有横线的地方填写合适内容。ｉntNodeLevel(structBｉｎTreｅNodｅ*BT,chaｒＸ）{iｆ(ＢT＝=NＵＬL)retｕrn０;/*空树的层号为0＊／elseiｆ(BT->dａtａ==X)rｅtｕｒn1;/＊根结点的层号为1*//*向子树中查找X结点*/elｓe{ｉｎtc1＝ＮｏdeLevｅl(BＴ-＞ｌｅｆt,X);ｉｆ(c1>＝1)_＿_(1)＿_＿_＿__＿___;ｉntｃ２＝______(2)＿__＿____＿＿;if___(3)___________＿_＿＿＿_＿;//若树中不存在X结点则返回0elsｅreturｎ0;}}2.下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边,请在划有横线的地方填写合适内容。voiｄdfstｒee(aｄjmatrixGＡ，ｉnti,ｉｎｔｎ){intj；ｖｉsiteｄ[i]=1;(1)ｉf(GＡ［ｉ］[j]!=0&&GA［i][j]！=ＭaxValｕｅ&&！visiteｄ[j］)｛priｎtf("(％d,％d)%d,"，i,j，GA[i][j]);(２）｝｝五、算法设计题1.写一个将一棵二叉树复制给另一棵二叉树的算法。2.根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数ＢT初始指向二叉树的根结点。intBＴreeLeafＣouｎt(ｓtructBTrｅeNode*BT)；3.已知有n个顶点的有向图邻接表,设计算法分别实现下列功能：（1)求出图Ｇ中每个顶点的出度、入度。（２)计算图中度为0的顶点数。六、完毕:实验3――栈、队列、递归程序设计实验４——图的存储方式和应用根据实验规定(见教材P20３）认真完毕本实验,并提交实验报告。数据结构（本)课程作业(４)(本部分作业覆盖教材第8－9章的内容)一、单项选择题1.顺序查找方法适合于存储结构为()的线性表。Ａ．散列存储B.索引存储C.散列存储或索引存储D.顺序存储或链接存储2.对线性表进行二分查找时，规定线性表必须（)。A．以顺序存储方式B．以链接存储方式C.以顺序存储方式,且数据元素有序D．以链接存储方式，且数据元素有序3．假如规定一个线性表既能较快地查找，又能动态适应变化规定,可以采用（）查找方法。A．顺序B．分块C．折半D.散列4．对于一个线性表,若规定既能进行较快地插入和删除,又规定存储结构可以反映数据元素之间的逻辑关系,则应当(）。A．以顺序存储方式B．以链接存储方式Ｃ．以索引存储方式Ｄ.以散列存储方式5.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为(）。A.ｎＢ.ｎ/2C．(n+1）/２D．(n-1)／26.采用折半查找方法查找长度为n的线性表时,每个元素的平均查找长度为（)。A．O(ｎ*ｎ)B.Ｏ(ｎｌog２n)Ｃ．Ｏ(ｎ)D.s(loｇ２n)7.哈希函数有一个共同的性质,即函数值应当以（）取其值域的每个值。A.最大约率B.最小概率C．平均概率D.同等概率8．有一个长度为１0的有序表，按折半查找对该表进行查找,在等概率情况下查找成功的平均比较次数为()。A.29／１０B．３１／10C9.已知一个有序表为｛１1,22,３3,４4,55，66，7７,88，99}，则顺序查找元素5５需要比较(）次。A.3Ｂ.4１0.顺序查找法与二分查找法对存储结构的规定是（)。A.顺序查找与二分查找均只是合用于顺序表B.顺序查找与二分查找均既合用于顺序表,也合用于链表C.顺序查找只是合用于顺序表D．二分查找合用于顺序表11．有数据{53,30,37,１2，4５，24,96},从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小,应当选择的序列是（）。Ａ．45，24,５3,12,37,96,30B.３７,24，12,３0,53，4５,９6C.１2,２４,30,37，45，53,96D．３0，24，1２，37,45,9６,5312．对有18个元素的有序表作二分(折半）查找，则查找Ａ[3]的比较序列的下标也许为()。A．1、2、３B.９、5、2、３C.9、5、3Ｄ．9、４、2、３１３.对于顺序存储的有序表{5，１2,20，２6,37，４2,4６,50,6４}，若采用折半查找,则查找元素26的比较次数是()。A．3Ｂ.3C．４D.１４．关于哈希查找的说法对的的是()。Ａ.除留余数法是最佳的B.哈希函数的好坏要根据具体情况而定C.删除一个元素后,不管用哪种方法解决冲突,都只需简朴地把该元素删除掉D．由于冲突是不可避免的,所以装填因子越小越好15.在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（)。A．冒泡排序B.希尔排序C.直接选择排序D.直接插入排序16．从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的对的的位置上，此方法称为(）A.插入排序Ｂ．选择排序C.互换排序Ｄ.归并排序17．从未排序序列中挑选元素,并将其放入已排序序列的一端，此方法称为(）。A.插入排序Ｂ.互换排序C.选择排序D.归并排序18.依次将每两个相邻的有序表合并成一个有序表的排序方法称为(）。 A.插入排序B.互换排序C.选择排序D.归并排序19.当两个元素出现逆序的时候就互换位置,这种排序方法称为(）。Ａ.插入排序Ｂ.互换排序C．选择排序Ｄ.归并排序20.每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字,右区间中记录的关键字均大于等于基准记录的关键字,这种排序称为（)。Ａ．插入排序Ｂ.快速排序C.堆排序D.归并排序21.在正常情况下，直接插入排序的时间复杂度为（)。A.O（ｌoｇ2n)B.O(n)C.O(ｎlog2ｎ)Ｄ.O(n2)22.在正常情况下,冒泡排序的时间复杂度为（)。A.Ｏ(loｇ2n）B．O(n）C.O(nｌｏg2n)Ｄ.O(n２)２3.在归并排序中，归并趟数的数量级为（）。A.O（ｌog２n)B.Ｏ(n)C.O(nlｏｇ2n)D.Ｏ(n2）2４.在待排序元素基本有序的情况下，效率最高的排序方法是()。A.插入排序B.快速排序Ｃ.堆排序D.归并排序２5.下面几种排序方法中，规定内存量最大的是()。A.插入排序Ｂ.互换排序C.选择排序D．归并排序26.在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是()。A．希尔排序B.冒泡排序C.插入排序D.选择排序２7.快速排序方法在(）情况下最不利于发挥其长处。A.要排序的数据量太大B．要排序的数据中具有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数28．下述几种排序方法中，平均情况下占用内存量最大的是()方法。A.插入排序B.选择排序Ｃ．快速排序Ｄ.归并排序2９.若构造一棵具有n个结点的二叉树排序，在最坏的情况下，其深度不会超过()。A.ｎ/２B.nC.(n1）/２D.n130.对数据元素序列(49,72，68,13,38,50，97,２7)进行排序,前三趟排序结果时的结果依次为第一趟：49，72，６8，１３,３8，50，97,２7;第二趟:49,68，72，13,38，50,97,27;第三趟:１3，49,68,72，38,５0，97,2７。该排序采用的方法是（)。A．插入排序法B.选择排序法C.冒泡排序法D.堆积排序法31.对具有n个元素的任意序列采用插入排序法进行排序,排序趟数为()。A．n-1B.ｎC.n+1Ｄ．loｇ2ｎ3２．对序列（49,3８,6５,９7,76,13，４７，5０)采用直接插入排序法进行排序，要把第七个元素47插入到已排序中，为寻找插入的合适位置需要进行(）次元素间的比较。Ａ.3B.4Ｃ.5D.33.下面四种排序方法中,()是一种稳定性排序方法。Ａ.插入排序法B.选择排序法C．快速排序法D．希尔排序法３４.一组记录的关键字序列为（46,79，56,38，4０，８4），运用快速排序，以第一个关键字为分割元素,通过一次划分后结果为()。Ａ．40,38,46，79,56,84Ｂ．４0，３8，46，84,５6,79C．40，３８,46，５6,79,84D．38,４0，4６，5６,７9,843５．一组记录的关键字序列为(４6,79,５6，38,４０，84)，运用堆排序的方法建立的初始堆为(）。A．７9,4６,56，38，4０，84B.84,79，5６，38,40，4６C.８4,7９，56，46,40,38，Ｄ.８4,56，７９,40，4６,38３6.一组记录的关键字序列为(25,48,１６,35,79，82,23,４0，36，72)，其中，具有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为（）。Ａ．１6,２５，３5，4８,23，４0,79，82,36，72B.16，25,35,4８,７9，８2，２３,36,40，７2C．16,25，48,３5,79,８２,23，36，40，72D.１６，25,3５,48，7９,２3，３6,40，82,7２3７.已知10个数据元素为（５4，28，16,3４,73，6２,95，60，26,４3）,对该数列从小到到大排序,通过一趟冒泡排序后的序列为(）。A．16,２8，３4,54，73,62，60，26，43，9５B．28,1６,３4,5４，6２,73，60，2６,4３，95C．2８,1６,３４，5４，62,60,７３，26,4３,９5D．16,28，３4,54,62，60，73,2６，4３,95３8.用某种排序的方法对线性表(25,84，2１,47，15，27，6８，3５，20）进行排序时，元素序列的变化情况如下:（1)25，84，２1,47，15，27,68,35,20（2)2０，15，21，25，4７，２7,68，3５，8４(３）１5，２0,21,25,３5,27，4７,68，84（4)15,２0,2１,25,27,35,47,6８，84其所采用的排序方法是（)。A.希尔排序B.归并排序C.快速排序D.直接选择排序二、填空题1．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。2.假如对查找表只进行查询某个特定的数据元素是否在查找表中，以及查找