2023年大连东软数据结构题库

1.6习题１.６.1知识点：数据结构的定义一、选择题1①数据结构通常是研究数据的（A）及它们之间的互相联系。Ａ．存储和逻辑结构B．存储结构C.顺序结构D.链式存储结构２①数据在计算机存储器内表达时，物理地址与逻辑地址相同并且是连续的,称之为（C）A．存储结构B.逻辑结构Ｃ．顺序存储结构D.链式存储结构3①线性结构是数据元素之间存在一种(D）。A.一对多关系B.多对多关系C多对一关系Ｄ一对一关系4①计算机内部数据解决的基本单位是(B）。Ａ.数据B.数据元素Ｃ.数据项Ｄ.数据库5②从逻辑上可以把数据结构分为（C）两大类。【武汉交通科技1996】A．动态结构、静态结构B.顺序结构、链式结构Ｃ.线性结构、非线性结构D．初等结构、构造型结构二、填空题1①数据结构按逻辑结构可分为四大类，它们分别是集合、线性、树、图。2①数据的存储结构可用四种基本的存储方法表达，它们分别是顺序、链式、散列、索引。判断题（F）1①数据元素是数据的最小单位。（T)2①记录是数据解决的最小单位。（F)３①数据的逻辑结构是指数据的各数据项之间的逻辑关系。（T)４①数据的物理结构是指数据在计算机内的实际存储形式。简答题１①简述什么是数据结构?2②数据结构与数据类型有什么区别?【哈尔滨工业２023】１．6.2知识点：算法的概念一、选择题1①计算机算法指的是（Ｃ)A．计算方法 ﻩB.排序方法 ﻩC.解决问题的有限运算序列 D．调度方法2①算法分析的目的是((１)C）,算法分析的两个重要方面（（2)A)．A.找出数据结构的合理性ﻩﻩB．研究算法中的输入与输出的关系C.分析算法的效率以求改善 Ｄ.分析算法的易查性和文档性A.空间复杂度和时间复杂度ﻩB.对的性和简明性Ｃ．可读性和文档性ﻩﻩﻩD.数据复杂性和程序复杂性3②设语句Ｘ+＋的时间是单位时间,则语句：for（ｉ=1;i＜＝n；i++）ｘ＋+；时间复杂度为（C）。Ａ．Ｏ(1）Ｂ．Ｏ(n）C.O（n2）D．O(n3）4②算法的计算量的大小称为计算的(Ｂ)。【北京邮电２0２3】A.效率Ｂ.复杂性Ｃ．现实性D．难度5②算法的时间复杂度取决于（C）【中科院计算所1998】A．问题的规模B．待解决数据的初态C．A和B6②下面关于算法说法错误的是(A)【南京理工202３】A.算法最终必须由计算机程序实现Ｂ．为解决某问题的算法同为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上几个都是错误的７②下面说法错误的是（D）【南京理工２02３】算法原地工作的含义是指不需要任何额外的辅助空间在相同的规模n下,复杂度Ｏ(n）的算法在时间上总是优于复杂度Ｏ(２n)的算法所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界同一个算法，实现语言的级别越高,执行效率就越低A．(1）B.(1）,(2)C．(1）,（4)D.(3)8②程序段fｏr(ｉ＝n-1;i>=１;i+＋）for（j=1;j<=i;j++）ｉｆ(A[j]>A[j＋１]）A[ｊ]与A[j+1］对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（D）【南京理工1９９8】A.O（n）B.O(ｎloｇ2n）C.Ｏ（n３)D.O（n2)二、填空题1①以夹杂自然语言和程序语句的形式来描述解决问题的方法称为__＿_伪码______＿_。２①一个算法的效率可分为___时间___＿＿_效率和＿_空间___＿＿＿_效率．3②有一个程序片断如下:for(i=0;i<ｎ;ｉ++）x＝x+1；则其时间复杂度为：＿O（n）________4②有一个程序片断如下:fｏr（ｉ=０;ｉ<n；ｉ＋+）for ﻩ(j＝i;ｊ<n;ｊ++）fｏr（k=j;k＜n;ｋ++)m=１;则其时间复杂度为:O（ｎ3)5②有一个程序片断如下:for(ｉ=０;i<n;i++）{j＝ｉ；whｉｌe(ｊ>=2)ｊ=ｊ／2；}则其时间复杂度为:O（nｌog２ｎ）判断题(Ｔ)1①算法的优劣与算法描述语言无关，但与所用计算机有关。(T)2①健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(F）3①程序一定是算法。简答题1①如何判断一个算法的好坏？2③调用下列C函数f(ｎ）回答下列问题:（1)试指出ｆ（n）值的大小,并写出f(n)值的推导过程；（2)假定n=5，试指出f（５)值的大小和执行f（5）时的输出结果。C函数:intf（intｎ)｛inti,ｊ,ｋ,sｕm=０;foｒ(i=l;i<ｎ+1;i++）{for(j=n;j>ｉ-1；j--)ｆｏr（ｋ=１;ｋ<ｊ+1;k++）suｍ++；prｉntｆ（"sｕm=%d\n"，sｕm）;｝return（ｓum）;｝【华中理工2023】2.７习题２.７．1知识点：线性表的逻辑结构一、选择题1①线性表Ｌ=（a1,a２,…,an),下列说法对的的是(D)。A．每个元素都有一个直接前驱和一个直接后继。B．线性表中至少要有一个元素。C.表中诸元素的排列顺序必须是由小到大或由大到小。Ｄ．除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。2①在线性表的下列运算中，不改变数据元素之间结构关系的运算是(D)。A.插入B．删除 ﻩＣ.排序D．定位３①线性表是具有n个（C）的有限序列（ｎ>0）。【清华1998】A．表元素Ｂ.字符C.数据元素D．数据项E．信息项二、判断题（T)1①线性表中的每个结点最多只有一个前驱和一个后继。(F)2①线性表中的每个结点都至少有一个前驱结点和后继结点。（F）3①线性表是N个数的有限序列。（Ｆ)４①同一线性表的数据元素可以具有不同的特性。（Ｔ）5①线性表的长度n就是表中数据元素的个数,当n=０时，称为空表。(T）6①线性表是一个相称灵活的数据结构，它的长度可根据需要增长或缩短。（F）7①对线性表中的数据元素只能进行访问，不能进行插入和删除操作。2.7.2知识点：线性表的顺序存储结构一、选择题1①在一个长度为n的顺序表中，在第i个元素(1<=i<＝n+1）之前插入一个新元素时需向后移动（B）个元素． A．n-1ﻩB．n-i+1ﻩＣ.ｎ－i-１ Ｄ.ｉ2①若某线性表中最常用的操作是取第ｉ个元素和找第i个元素的前趋元素,则采用（D)存储方式最节省时间。A．单链表B.双链表C．单向循环D．顺序表3②一个数组第一个元素的存储地址是10０,每个元素的长度为2,则第5个元素的地址是（B）A.11０B.108C．１00D.1204①下述哪一条是顺序存储结构的优点(A)。【北方交通２023】A.存储密度大B.插入运算方便C.删除运算方便D．可方便地用于各种逻辑结构的存储表达5③若长度为ｎ的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为（C） ﻩ（1<=i＜=n+1）。【北京航空航天19９9】A.Ｏ（0）B.O（１）Ｃ.O（n)D.Ｏ(n２）6③对于顺序存储的线性表，访问结点和增长、删除结点的时间复杂度为(C）。【青岛202３】A.O（n)O(n）B.O(n）O(１）Ｃ.O（1)Ｏ(ｎ）D．O（1)O（１)填空题1①线性表的顺序存储的缺陷是在任意位置上＿＿_插入＿__＿_数据与_＿＿_删除_____数据费时间。2①设一线性表的顺序存储，总存储容量为Ｍ，其元素存储位置的范围为__0～M-1_＿________。３①向一个长度为n的向量中删除第i个元素（1≤i≤n)时,需向前移动＿___n-i＿_____个元素。简答题１③已知线性表的存储结构为顺序表,阅读下列算法，并回答问题：voｉdf30(SeqＬｉst*L）{ｉｎti，j;ｆｏr(i=ｊ=０;i＜L->leｎgth;i++）iｆ(L->ｄatａ[ｉ］＞=0）{ｉf(i!=ｊ）L-＞datａ[j]＝Ｌ->datａ［i];j＋＋;}Ｌ－＞length＝ｊ;｝设线性表L=(21,-７，-８，19，0,-1１,３4，3０,-10)，写出执行ｆ30(&Ｌ）后Ｌ状态;(2１，1９,0,34,３0)简述算法ｆ3０的功能。删除顺序表中小于0的元素四、编程题１④已知顺序表La中数据元素按非递减有序排列。试写一个算法，将ｘ插入到La的合适位置上，保持该表的有序性。2.7．3知识点：线性表的链式存储结构一、选择题１①链表是一种采用(B）存储结构存储的线性表。A.顺序B．链式C.星式D.网状2①链接存储的存储结构所占存储空间(A）。A.分两部分，一部分存放结点值，另一部分存放表达结点间关系的指针。B.只有一部分,存放结点值。Ｃ.只有一部分，存储表达结点间关系的指针。Ｄ．分两部分,一部分存放结点值，另一部分存放结点所占单元数。3①线性表若采用链式存储结构时,规定内存中可用存储单元的地址（D）。Ａ．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以4①线性表L在(B)情况下合用于使用链式结构实现。Ａ.需经常修改Ｌ中的结点值B．需不断对L进行删除插入C．Ｌ中具有大量的结点D.L中结点结构复杂5①对单链表表达法,以下说法错误的是(Ｃ)。A．数据域用于存储线性表的一个数据元素。Ｂ．指针域(或链域)用于存放一个指向本结点所含数据元素的直接后继所在结点的指针。C.所有数据通过指针的链接而组织成单链表。D.NULL称为空指针，它不指向任何结点只起标志作用。６①以下说法对的的是（Ｄ）。A．顺序存储方式的优点是存储密度大且插入、删除运算效率高Ｂ.链表的每个结点中都恰好包含一个指针C.线性表的顺序存储结构优于链式存储结构D．顺序存储结构属于静态结构而链式结构属于动态结构7①以下说法错误的是(Ｄ)。A.求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低Ｂ.顺序存储的线性表可以随机存取Ｃ.由于顺序存储规定连续的存储区域,所以在存储管理上不够灵活D．线性表的链式存储结构优于顺序存储结构8①不带头结点的单链表ｈeaｄ为空的鉴定条件是(A）。A．head＝＝ＮULＬB.head-＞ｎext==ＮＵLLC.hｅaｄ－>ｎext==heａdD．heaｄ!=ＮUＬL9①带头结点的单链表ｈeaｄ为空的鉴定条件是(Ｂ)。Ａ．head==NUＬLＢ．head-＞next==NULLC．head-＞nｅxt=＝hｅadD.hｅad!=NULＬ10②在头指针为head的非空单循环链表中，指针p指向尾结点,下列关系成立的是(Ａ)。Ａ.ｐ-＞ｎeｘt==hｅaｄB．p->ｎｅxt-＞next＝=headC.p－>nｅxｔ==ＮＵLＬＤ.p=＝head11②在一个单链表中,已知q所指结点是p所指结点的前驱结点，若在ｑ和p之间插入s结点,则执行语句(C)。A.s-＞ｎext=p-＞nｅxt;p->ｎext=ｓ;Ｂ．p->next=ｓ-＞next;s->nｅxt=ｐ；C.q->neｘt=ｓ;s->nｅxt=ｐ;D.p->next=s；s－>neｘｔ=q；12②在一个单链表中，若p所指结点不是最后结点,在p之后插入ｓ结点，则应执行语句(B）。A.ｓ－>next＝p:p-＞ｎｅxt=ｓ;B．s->ｎext=p->neｘt;ｐ－＞nｅxt=s;C．s－>ｎext=p-＞ｎｅｘt;ｐ=s;D．p->next=ｓ;s->next=p；13②在一个单链表中,若删除p所指结点的后续结点，则应执行语句(A)。A．p-＞ｎext=p-＞neｘt->nｅxt;B．p=p->neｘt;p->next＝ｐ－>ｎeｘt->nexｔ;C.p->next＝p-＞neｘt;D．p=ｐ->nexｔ-＞next；14②指针ｐ、ｑ和r依次指向某循环链表中三个相邻的结点，互换结点*q和结点*r在表中顺序的程序段是（Ａ）。A.p－>ｎｅxt=ｒ;ｑ->next=r-＞next；r－>neｘt=ｑ;Ｂ.p->ｎext=r；r-＞ｎext＝q；q->next=r->nｅｘｔ;C.r->ｎｅxt＝ｑ；q->ｎext=r->nｅｘt；p-＞ｎｅxt=ｒ;Ｄ.r-＞nｅxt=q；p->next＝r;q->next＝r-＞nｅxt；15①链表不具有的特点是(B）【福州1998】Ａ.插入、删除不需要移动元素Ｂ．可随机访问任一元素C.不必事先估计存储空间ﻩ D．所需空间与线性长度成正比16①下面的叙述不对的的是(BC)【南京理工１9９6】A．线性表在链式存储时,查找第ｉ个元素的时间同i的值成正比B.线性表在链式存储时,查找第ｉ个元素的时间同i的值无关C.线性表在顺序存储时，查找第i个元素的时间同ｉ的值成正比D．线性表在顺序存储时，查找第ｉ个元素的时间同i的值无关17①下面关于线性表的叙述中，错误的是哪一个？（B)【北方交通2023】Ａ.线性表采用顺序存储,必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储,不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。１8①在一个以h为头的单循环链中，p指针指向链尾的条件是（A)【南京理工19９8】Ａ.p->ｎｅxt=hB.ｐ->ｎeｘt＝NUＬLC．p－>ｎext-＞next＝hD．ｐ->ｄata=-１19②若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则运用（A）存储方式最节省时间。【哈尔滨工业2023】Ａ．顺序表B．双链表C.带头结点的双循环链表D．单循环链表2０②某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用（Ｄ）存储方式最节省运算时间。【南开2０23】A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表2１②设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(Ｄ）最节省时间。【合肥工业２0２３】A.单链表B.单循环链表Ｃ．带尾指针的单循环链表Ｄ．带头结点的双循环链表22②线性表(a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间复杂性为（C）【中山1９99】A．O(i）B.O（1)C．O（ｎ)Ｄ．Ｏ(ｉ－1)23③完毕在双循环链表结点ｐ之后插入ｓ的操作是(Ｄ)。【北方交通１９99】A．p－>neｘt:=s;s->priou:=p;p->ｎｅｘｔ-＞priｏu：＝ｓ；ｓ-＞neｘt:=p->nｅxt;B.p-＞neｘt->priou:＝s;p->next:=s；s->ｐｒiou:=ｐ;s－>ｎeｘｔ:=p->nｅｘt;Ｃ.s->ｐｒｉou:=p;s->nｅxt：=p->neｘt；p->next:=ｓ;p->nexｔ->priｏu:=s;D.s->pｒiｏｕ:=p;s->nｅxｔ:=p-＞next;p－＞ｎext-＞priou:=s;p->next:=s;24③在双向循环链表中，在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是(C)。【北京邮电１998】【青岛202３】注：双向链表的结点结构为(llｉnk,data,rlink）。供选择的答案：Ａ.p-＞lｌｉnk=q；ｑ->ｒlink=p；ｐ->llink－>rlｉｎｋ=q；q->llｉnｋ=q；B．p->llinｋ=q;p－>llink－＞rｌink=q;q－>rlｉnk=p；q-＞llink=ｐ-＞ｌlｉnk；C．q-＞ｒlink=p;q-＞ｌlink＝p->ｌlink;ｐ->lｌink－>rlｉnk=q;p->lｌｉnk=ｑ;D.q-＞ｌlink=ｐ->llｉｎｋ;ｑ-＞ｒlｉnk:=p;p-＞lｌiｎｋ＝q；p->llｉｎk＝ｑ；25③在双向链表存储结构中,删除ｐ所指的结点时需修改指针(A）。【西安电子科技１９98】A.p－＞ｐrｉor->nｅxt＝p－>neｘtp->next->prior=p->priｏr;B．p->prioｒ=p->prｉｏr->pｒiorp->priｏr->next=p;C．p->prior-＞priｏｒ:=ｐp->neｘt=p－＞next－＞nｅｘtＤ．p－＞next=（p->priｏr)->priｏrp->priｏr＝p-＞next－>next二、填空题１①线性表的链式存储是用___malloc___＿__语句实现空间单元动态分派。２①单链表是___线性表＿＿_＿＿的链接存储表达。３①头结点地址指针为L的循环单链表，空表的判别标志是___L-＞nｅxt==NUＬL_＿_。4①在一个单链表中删除p所指结点时,应执行以下操作:ｑ=p->next；ｐ->ｄata=p->nexｔ->datａ；p－>next=q->ｎｅxｔ＿_＿_＿__＿_;free(q）;５③下段程序的功能:有一头指针为ｈead的链表，将ｎｅｗ指针指向的节点插入到data域为7的节点的后边。将程序补充完整。P=heaｄ;while（Ｐ!=ＮUＬL)｛if(P->ｄaｔa==7）/＊找到位置插入结点后跳出循环*／{(1）_nｅw－>next＝p->ｎext__＿_____＿＿_____；（2）_p->next=ｎｅw____＿__＿＿＿_____;(3）__＿___ｂreａｋ＿_＿＿__＿_＿_;}elsｅ（4)__＿p=ｐ->ｎｅxt____＿_＿____＿__;／＊指针后移*/}if（P＝=NＵLL）ｐrｉｎtf(“\nthｅｐositionｉsn’teｘist!”)；6③假设某个不设头指针的无头结点单向循环链表的长度大于1,ｓ为指向链表中某个结点的指针。算法f30的功能是，删除并返回链表中指针s所指结点的前驱。请在空缺处填入合适的内容，使其成为完整的算法。typedefｓtrｕcｔｎode｛ＤａtａＴyｐeｄata;sｔｒｕctｎode*ｎeｘｔ;｝*ＬinkLisｔ;DataTypeｆ30（LinkLiｓｔｓ)｛ＬinｋListｐrｅ,p;ＤaｔaTyｐeｅ；pｒｅ=s；p=ｓ－＞next;whilｅ（(1）__p->ｎｅxｔ!=s＿_＿_){prｅ＝p;（２）p=p->neｘt___＿__＿＿_＿__;}pre－>ｎext＝（3)__p－＞ｎext＿＿_______＿__；e=p->dａta;fｒee(ｐ);retｕrｎｅ;}判断题(F）1①单链表从任何一个结点出发，都能访问到所有结点。（F）2①线性表的每个结点只能是一个简朴类型,而链表的每个结点可以是一个复杂类型。简答题1①描述以下几个概念:顺序存储结构、链式存储结构、顺序表、有序表。２②描述以下三个概念的区别:头指针、头结点、首元结点。在单链表中设立头结点的作用是什么?3②线性表有两种存储结构：一是顺序表，二是链表,试问：（1)假如有ｎ个线性表同时共存,并且在解决过程中各表的长度会动态地发生变化，线性表的总数也会自动地ﻩ改变。在此情况下，应选用哪种存储结构？为什么？链表(２)若线性表的总数基本稳定,且很少进行插入和删除，但规定以最快的速度存取线性表中的元素,那么应采 用哪种存取结构?为什么?顺序表4③假设本测试中使用的链表如图2.４5所示，结点定义如下:struｃtＬｉst{iｎtdａｔa;ｓｔructＬist＊next；}；typedｅfsｔruｃtLiｓtＮｏde;ｔｙpedefＮode*Ｌiｎk;LiｎkＰ,Q,R,S，head;Lｉnkｐoｉｎter，bａck,new;对以下单链表分别执行下列程序段，规定分别画出结果图。(1）Q=ｈead->next->next；Ｑ指向7(2）R->ｄata＝P－>daｔa;3变5（3)Ｒ->ｄaｔａ=Ｐ－>nexｔ->dａｔａ;３变７S=P;while(S->next!＝ＮULＬ){S-＞data=S-＞daｔａ*2；S=S->nｅxt;}4101４６8Ｓ=P；wｈｉle（S!=NUＬL）{Ｓ-＞data=S->daｔa＊2;S=S－>ｎexｔ;｝410146165③假设本测试中使用的链表如图2.45所示，结点定义如第4题所示。画出执行如下程序段后各指针及链表的示意图。ｈｅaｄ＝（Lｉnk)malloc(ｓizeof(Node)）;ｈｅad－>data=0;heａd->neｘt＝NULＬ;P=ｈeaｄ;fｏr(ｉ=1;i<4;i+＋){new=(Linｋ)malloc(sizeof（Ｎode)）;neｗ->data=2*ｉ;ｎeｗ->ｎext=NULＬ;Ｐ－>neｘt=nｅw;P=new;｝创建了一个链表，数据元素为0,2,4，6,并且p和nｅｗ都指向尾结点6③有一链表如下图所示,阅读程序给出程序的输出结果。图２.４６6题图P＝hｅａd;ｗｈilｅ(P!=NULL){printf(“\ｎdatａ=%d”,P->data）；P=Ｐ－＞neｘt;if(Ｐ!=NULL) ﻩﻩＰ=P->ｎeｘt;}Data＝1Ｄatａ=3Data=5五、编程题1④一个单链表，其头指针为head,编写一个函数计算数据域为x的节点个数。2④已知单链表Lａ中数据元素按非递减有序排列。按两种不同情况，分别写出算法,将元素ｘ插入到La的合ﻩ适位置上,保持该表的有序性：(1)La带头结点；（2）Ｌa不带头结点。3④试写一个算法,实现顺序表的就地逆置,即在原表的存储空间将线性表（a1,ａ２，…,ａn−１，an)逆置为（aｎ，ａﻩｎ−1，…,a2,ａ1)。4④设计一个算法，求Ａ和Ｂ两个单链表表达的集合的交集、并集合差集。3.7习题３．７.1知识点：栈的基本概念一、选择题1①下列哪种数据结构常用于函数调用（A)。 A.栈Ｂ．队列Ｃ．链表D．数组2①编译器中通常以哪种数据结构解决递归程序调用（C）ﻩﻩ A．队列ﻩＢ．数组 Ｃ．栈D．记录3①下列哪些数据结构可用来实现栈（D)。(1)链表(２）数组（３）树(4）图ﻩＡ.(2），（3) Ｂ.（2)，（4）C.(1)，(4)ﻩD.（1),(2)4②元素的入栈序列是a，b,c,d,则栈的不也许的输出序列是（C）。A.ｄｃbaB．aｂcdC．ｄｃabD.ｃｂａd5②已知栈的最大容量为４。若进栈序列为1，2，３,４，5,6，且进栈和出栈可以穿插进行,则也许出现的出栈序列为（Ｃ）。A.５,4，３,2,1,6B.２,3，5，6,1,4Ｃ．３，2,5，4，1，6D．1,4，6，5,２,36②若以S和X分别表达进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列是（D）。Ａ.SXSSＸXＸXB．SＸＸＳXSSＸC.SXSＸXSSXD.SSSXXSXＸ７①对于栈操作数据的原则是（B)。【青岛2023】A.先进先出B.后进先出C.后进后出D.不分顺序8①栈在（Ｄ）中应用。【中山1998】Ａ．递归调用B．子程序调用Ｃ．表达式求值D．A,B,Ｃ9②一个栈的输入序列为1２3…n，若输出序列的第一个元素是n,输出第ｉ（1＜=i<=n)个元素是(B)。【中山1999】Ａ.不拟定B．n-i+1Ｃ.ｉD．n-ｉ１０②若一个栈的输入序列为1,２,3,…，n，输出序列的第一个元素是i，则第j个输出元素是(Ｄ)。【武汉２０23】Ａ．i－ｊ-1B．i－jC.ｊ－i＋1D．不拟定的１1②有六个元素６,５,4,3，２,１的顺序进栈，问下列哪一个不是合法的出栈序列？（C)【北方交通20２3】A．54361２Ｂ．４53162C.3４6５21D．234１５61２②输入序列为ABC,可以变为ＣBA时，通过的栈操作为(B）【中山1999】Ａ.pｕsｈ,pop,puｓｈ，pｏp,pusｈ,popB．pusｈ,ｐuｓh，puｓh,pop,poｐ，ｐoｐＣ．pusｈ,push，ｐop，pop，push,poｐＤ.push，ｐｏp,ｐuｓh,push，pｏｐ,pop13②设计一个判别表达式中左,右括号是否配对出现的算法，采用（D)数据结构最佳。【西安电子科技1９96】A．线性表的顺序存储结构B．队列C.线性表的链式存储结构D.栈二、填空题1①栈是一种特殊的线性表,允许插入和删除运算的一端称为栈顶，不允许插入和删除运算的一端称为栈底。2①对于顺序存储的栈，由于栈的空间是有限的，在进行入栈运算时,也许发生栈的上溢,在进行出栈 运算时,也许发生栈的下溢。３①表达式求值是栈应用的一个典型例子。４①栈是__一种特殊__＿_＿的线性表,其运算遵循_＿__先进后出____＿＿______＿的原则。【北京科技1997】５②设有一个空栈,栈顶指针为１0０0H(十六进制）,现有输入序列为1,２,3,４,5，通过PUSH,PUＳH，POＰ,ＰUSH,PＯP,PUＳH,ＰUSH之后,输出序列是2,3，__＿____，而栈顶指针值是ﻩ＿100０Ｃ_____H。设栈为顺序栈，每个元素占4个字节。【西安电子科技19９8】６②用S表达入栈操作，Ｘ表达出栈操作,若元素入栈的顺序为1234,为了得到134２出栈顺序，相应的S和 X的操作串为___＿_____sxssxｓxx_＿_____＿_＿。【西南交通202３】三、判断题(Ｆ)1①栈具有先进先出的特性。(T）2①栈用于实现子程序调用。（F）３①栈和链表是两种不同的数据结构。(T）4①栈顶的位置是随着操作而变化的。（T）5①栈和队列逻辑上都是线性表。(T）６①栈是实现过程和函数等子程序所必需的结构。【合肥工业202３】(Ｆ）7②即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也 一定相同。【北京邮电１999】(T)8②若输入序列为１,２,３,４，5，６,则通过一个栈可以输出序列３，2,５,6,4,１。【上海海运199５】(Ｆ)9②若输入序列为1,2,3,4，5,６,则通过一个栈可以输出序列１，5，4,6,2,3。【上海海运１９99】四、简答题1①什么是栈？试举两个应用实例。２①简述栈和线性表的差别。3③计算表达式6*3/2-5*１,规定绘出堆栈的解决过程。5②有5个元素，其入栈顺序为：A，B，Ｃ,Ｄ,Ｅ，在各种也许的出栈顺序中,以元素C,Ｄ最先出栈（即C第一个且D第二个出栈）的顺序有哪几个？【西南交通2023】3.7.２知识点:栈的存储一、选择题１①假如以链表作为栈的存储结构，则入栈操作时（B）。A.必须判别栈是否满B.对栈不作任何判别C．必须判别栈是否空Ｄ．判别栈元素的类型2①上溢现象通常出现在（A)。Ａ．顺序栈的入栈操作过程中B．顺序栈的出栈操作过程中C．链栈的入栈操作过程中Ｄ.链栈的出栈操作过程中3①鉴定一个栈ＳT（最多元素为m0）为空的条件是(B)Ａ.ST->top！＝0B．ST－＞toｐ==０C．ＳT-＞tｏp!=ｍ0D．ＳT－>ｔop==m04①链表仿真堆栈时,栈空的条件是(B)。ﻩﻩA.toｐ<maxｓize－１B．tｏｐ=＝ＮULLC．没有限制D.tｏp＜05①链表仿真堆栈时,栈满的条件是(C)。 A.top<maxｓizｅ-1B．top==NUＬLＣ．没有限制D.top＜06②在用链表仿真堆栈时（假设sｔack为栈顶指针),将new指针指向的节点执行入栈操作应执行(B)A．nｅw－>nexｔ＝ｓtack->neｘt;stack=ｎew；B.neｗ-＞neｘｔ=sｔaｃk；ｓｔaｃk=ｎｅw；Ｃ.ｎeｗ->next=ｓｔaｃｋ;ｓtaｃk＝new->nexｔ；Ｄ．stacｋ=new;sｔack-＞ｎｅｘt＝new->neｘｔ;7②若一个栈以向量V[1..n]存储，初始栈顶指针ｔoｐ为n+1,则下面x进栈的对的操作是（Ｃ)。【南京理工199８】A.top=ｔop＋1;V[ｔop]=xＢ.V[ｔoｐ]＝x；tｏｐ＝top＋1C.ｔop＝ｔop-1;V[tｏｐ]＝ｘD.V[top]=x;toｐ＝tｏp－1８②执行完下列语句段后,i值为：(B）。【浙江２０23】inｔf（ｉntx){return((x>０）？ｘ*f（x-１）:2);｝ｉｎti;i=f(f（1)）;Ａ.2B．4C．8D．无限递归填空题1②以下语句是堆栈的入栈操作,用全局数组ｓtack仿真堆栈，数组类型是inｔ,大小是MaxＳｉｚe，栈顶指针是ｔop,初始化等于－1。voidｐｕsh(ｉntvａlue）{ｉf(toｐ＞MaxSiｚe-1)ｒeｔurｎ–1;elｓe{ｔop++;ｓｔａck[tｏp］=vａlue;}｝指出有错误的语句：＿__3_____写出改正后的语句：＿__＿_top＝=MaｘＳiｚe-1___＿_＿_2②以下语句是数据从堆栈中取出操作，top为栈顶指针，ｓtack为堆栈数组。01ｉntｐop(）０2{inttｅｍｐ;iｆ(toｐ==0)reｔurｎ–1；eｌse｛teｍp＝stack[toｐ］；toｐ――;}reｔuｒnteｍp; 1２}指出有错误的语句:＿＿＿___＿＿＿____＿_＿＿＿＿_＿＿_写出改正后的语句:_＿_＿___8,9互换_＿__＿＿＿_＿____＿＿_编程题1④假设一个算术表达式中可以包含圆括号“（”和“)”，编写判别给定表达式中所含括号是否对的配对出现的算法。２④编写斐波那契（Fibonacci)数列的递归算法和迭代算法。F０=0, Ｆ1=1,ﻩＦFｎ＝−n1+−Ｆｎｎ２(>=2）3.7.3知识点:队列的基本概念及其应用一、选择题1①下列哪种数据结构常用于系统程序的作业调度(Ｂ) A．栈 Ｂ.队列C．链表Ｄ.数组2①在解决计算机主机与打印机之间速度不匹配问题时通常设立一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印.该缓冲区应当是一个(B）结构.A．堆栈Ｂ．队列C.数组Ｄ．线性表3②设栈S和队列Ｑ的初始状态为空，元素ｅ1、e2、e3、ｅ4、e5、e6依次通过栈S,一个元素出栈后即进入队列Ｑ，若6个元素出队的序列是e2、e4、ｅ３、e6、ｅ5、e1，则栈Ｓ的容量至少应当是(C）A．６B.４C.３D．２４①栈和队列的共同点是（C)。【燕山２02３一、１(2分）】A.都是先进先出 ﻩ B．都是先进后出C．只允许在端点处插入和删除元素ﻩ D．没有共同点二、填空题1①栈和队列都是线性结构,对于栈只能在____栈顶＿＿_＿＿_位置插入和删除元素，对于队列只能在___＿__队尾__＿＿＿＿__位置插入元素和＿_＿_＿队头__＿_＿＿＿＿＿位置删除元素。2②队列的队尾位置通常是随着＿____入队____＿_＿＿_操作而变化的。3①队列的特点是＿______先进先出_____＿__＿____＿___。【北京理工２0２3】4②循环队列的引入，目的是为了克服_______＿假溢出_＿＿____＿＿＿__＿_＿_。【厦门2023】三、判断题（Ｔ)1①队列中所有的插入操作都发生在表的一端,删除则发生在表的另一端。（F）2①队列为先进后出的结构。(F)3①队列必须用数组来表达。（T）4①队列用于操作系统中的作业调度。（T)5①栈和队列逻辑上都是线性表。（T）6①栈和队列是在程序中常用的两种数据结构。(T)7①栈与队列是一种特殊操作的线性表。【青岛２0２3】(Ｔ）8①栈和队列都是限制存取点的线性结构。【中科院软件所1999】（Ｆ)9①队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。【上海海运1９９8】(F）10①通常使用队列来解决函数或过程的调用。【南京航空航天１997】（Ｆ)1１①队列逻辑上是一个下端和上端既能增长又能减少的线性表。【上海交通19９8】(T）12①栈和队列都是线性表，只是在插入和删除时受到了一些限制。【北京邮电2０23】四、简答题1①什么是队列？试举两个应用实例。2①说明线性表、栈和队列的异同点。3①顺序队的“假溢出”是如何产生的?什么是循环队列?如何知道循环队列是空还是满？五、编程题１④假设称正读和反读都相同的字符序列为“回文”,例如‘ａbba’和‘aｂcba’是回文，‘ａbｃde’和‘ａbaｂａｂ’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。３．7.4知识点：队列的存储一、选择题1①循环队列用数组A[maxｓizｅ]表达，下面哪个选项表达该循环队列队满（B)Ａ．ｒｅａr==maxsize-1B.front==(rｅaｒ+1)%maxsiｚeC．rｅar-fｒoｎt==maxsizeD.rｅaｒ-front==maxsize－12①在用数组ｑueue[maxsize]仿真队列时(temp为int型变量)，假设队列中至少有一个元素，出队列操作应执行以下（Ｄ)A．tｅmｐ＝queｕe［reaｒ]；ｒear－－；Ｂ.reaｒ++；tｅmp=queue［rｅａr］;C．temp=queuｅ［front]；front-－;Ｄ.froｎｔ+＋;tｅｍp＝ｑueue［front];３①数组Ｑ[n]用来表达一个循环队列,f为当前队列头元素的前一位置,ｒ为队尾元素的位置,假定队列中元素的个数小于ｎ，计算队列中元素的公式为(D)A．r－ｆ;Ｂ．(n+ｆ-r)％n；Ｃ.n+r-fＤ．（n＋r-ｆ）％n４②判断一个队列QU(最多元素为m0)为空的条件是（C）。ﻩＡ.ｒear－front==m０ﻩＢ．rear-ｆront－1＝=ｍ０ Ｃ．front＝=rearﻩﻩＤ．fｒｏｎt==ｒeａr+１５②一个队列(数组仿真,最多元素为MａxSｉzｅ）下列哪个选项表达了队列空间所有被运用？(A）A．ｒear–fｒoｎｔ==MａxＳizeＢ.rear–froｎt==MaxＳiｚe–１Ｃ．reaｒ==fronｔＤ．reaｒ+１==fｒont6②鉴定一个循环队列(数组仿真，最多元素为MaxSｉze)为空的条件是？(A)A.froｎｔ＝=rearB.fｒonｔ!=reａrC．frｏｎｔ==(ｒear＋1)％MaxSｉzｅD．front!=（rear＋１）%ＭａxSｉze7①用单链表表达的链式队列的队头在链表的（A）位置。【清华19９8】Ａ．链头B.链尾C.链中Ｄ．任何8②用不带头结点的单链表存储队列时,其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（Ｄ)。【北京理工2０２3】A.仅修改队头指针Ｂ.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都也许要修改9②假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和reａr,则当前队列中的元素个数为（A）。【北京工商2０23】A.(rear－ｆronｔ+ｍ)%ｍB.rear-frｏnt＋１C.（ｆｒｏnt-rear+m)％ｍD.(rear－froｎt)％m１0②循环队列存储在数组A[0.．m］中，则入队时的操作为(D)。【中山1999】A.rear=reａr+1B.rear=(reａr＋１)mod（m-1）C.ｒｅar=（rｅaｒ+1)moｄｍD.reａr=（ｒｅａr+1）moｄ(m+１)1１②若用一个大小为6的数组来实现循环队列,且当前rｅaｒ和ｆｒont的值分别为０和３，当从队列中删除一个元素，再加入两个元素后,reaｒ和fronｔ的值分别为多少？（B）【浙江1９99】A．1和5Ｂ．2和4Ｃ．4和２Ｄ.5和112②用链接方式存储的队列，在进行插入运算时(Ｂ）。【北方交通2023】A．仅修改头指针B．仅修改尾指针C.头、尾指针都要修改D.头、尾指针也许都要修改二、填空题1①栈、队列的建立可使用两种结构:＿_____顺序__＿＿__＿_结构和___＿链式__＿__＿结构。２②假设为循环队列分派的向量空间为Ｑ[2０］，若队列的长度和队头指针值分别为1３和１７,则当前尾指针的值为__10_____＿＿_____。3③以下语句是环状队列的出队操作,用数组ｑｕeue仿真环状队列,数组类型是int,大小是MaｘSize，队尾指针是ｒｅar，队头指针是fｒont。ｉntｄelｑueｕe(）{intteｍｐ;if(ｆronｔ==rear）rｅｔurn–1;ｅｌse{ｆrｏｎt＋+；ｔeｍｐ=queｕe[ｆroｎt]；queuｅ[frｏnt］＝0；rｅturntｅmｐ；}｝指出有错误的语句:_＿_______＿8____＿_＿＿_______写出改正后的语句：_____＿__fronｔ=(fｒont+1)％ＭaxSizｅ___＿＿________＿_4②区分循环队列的满与空，只有两种方法,它们是____设标志＿___和______少用一片空间____＿__。【北京邮电２023】5②设循环队列存放在向量sｑ.data[0..M]中,则队头指针sq．ｆroｎt在循环意义下的出队操作可表达为__sq.front=(ｓq．fｒｏｎｔ+1)%（M+1)_＿___，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sｑ．rｅar），则队满的条件为_sq.ｆrｏnt＝=（sｑ.rｅaｒ+1)%(Ｍ＋１)___。【长沙铁道1997】三、判断题(T）1①栈和队列的存储方式既可是顺序方式,也可是链接方式。（Ｔ)2①单链表形式的队列,头指针Ｆ指向队列的第一个结点，尾指针R指向队列的最后一个结点。（Ｆ）３①循环队列通常用指针来实现队列的头尾相接。【南京航空航天1９96】（Ｔ）４①循环队列也存在空间溢出问题。【青岛2023】四、简答题1②设循环队列的容量为４０（序号从0到39），现通过一系列的入队和出队运算后，有（1)ｆrｏnt=１１，rear＝1９;(2）ｆrｏnt＝19,rear=11；问在这两种情况下，循环队列中各有元素多少个?8，3２2②假设CQ[0,…，10]是一个环状队列,初始状态ｆront=rｅａr=１，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。(1）ｄ,ｅ，b,ｇ，ｈ入队；(2)d,e出队；(3)I，j，ｋ,l,m入队；（４）b出队;(５)n,ｏ,p,q，r入队。3③阅读下列算法，并回答问题(注：lnitＱuｅｕe、EnQｕeuｅ、ＤeQueｕe和QuｅuｅEmpｔy分别是队列初始化、入列、出队和判队空的操作）。vｏｉdf31（Quｅue*Q,Qｕeue＊Q1,Queue＊Ｑ2）{iｎtｅ；lnitQｕｅｕｅ（Q1);lniｔQｕeue（Q2）；whilｅ（！QｕeueＥmpty（Q)）{e＝DｅＱuｅue（Q);if(e＞＝0)EnQueｕｅ(Q1，e);elseEｎQｕeue（Ｑ2,e）}}（1)Q、Ｑ1和Ｑ２都是队列结构，设队列Q=（１，0,－5,2，-４，-6，９）,其中１为队头元素，写出执行f3１（&Q，&Q1,&Ｑ２)之后队列Q、Ｑ１和Q2的状态；Q为空Q1=(１，0,2,9)Ｑ2=（-５,－4,-6)(2）简述算法f３1的功能。4③阅读如下程序,并回答下列问题(注:lnitQuｅuｅ、EnQｕｅue、DｅQｕeuｅ和ＱｕｅｕeＥｍｐty分别是队列初始化、入列、出队和判队空的操作）。ｖoidｆ31（Queue*Q）{DatａTypee;if（!QueｕeＥmpty（Q）){e=DeQueuｅ(Ｑ)；f3１（Q);ＥnＱueuｅ（Q,e）;}｝设队列Q=（1，3,5,２，4,６）。写出执行算法f31后的队列Q；Q=（6,4,3,5,3,１)简述算法f31的功能。将队列反转5③阅读如下程序,它的功能是清空带头结点的链队列Q。请在空缺处填入合适的内容,使成为一个完整的算法。typedeｆstｒuctnｏdｅ｛DataＴypeｄaｔa;ｓtｒｕctnｏde＊ｎexｔ;}QuｅueNoｄe;tｙpedeｆstruct{QuｅuｅNｏdｅ*front；//队头指针QuｅueNoｄe*rｅar；／／队尾指针}LiｎｋQueue;voidf3１（ＬinkＱuｅue＊Ｑ）｛QｕeueNode*p,*s;p＝（1）;whｉle(ｐ！＝NＵLL）{s＝p；p＝p->nｅxt;ｆreｅ(s);（2）=NＵLL;Q->ｒｅar=（3）;}_＿＿__＿p=Q->frｏnt->next＿___＿＿_＿__＿__＿_____＿______Q->fｒｏnt－＞next=NULL____＿_________________Q－>reaｒ=Ｑ-＞ｆrｏnｔ____＿_＿_______＿__＿_五、编程题1④假设将循环队列定义为：以变量ｒeａr和lengtｈ分别指示循环队列中队尾元素的位置和内含元素的个数。试给 出此循环队列的队满条件,并写出相应的入队列和出队列的算法。2④假设以带头结点的循环链表表达队列，并且只设一个指针指向队尾元素结点（注意不设头指针）,试编写相应 的队列初始化、入队列和出队列的算法。４.9习题4.9.1知识点:树和二叉树的基本概念一、选择题1②在一棵具有ｎ个结点的完全二叉树中,分支结点的最大编号为(D)。假定树根结点的编号为0。 A.(n-1）/2 B.n/2ﻩ ﻩＣ．n／２+１ Ｄ．ｎ／2-12②在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（Ｃ)。假定根结点的编号为０。A.2i ﻩB．2i-１ ﻩ ﻩＣ．2i+1ﻩ ﻩﻩﻩﻩD.2i+23②在一棵具有３５个结点的完全二叉树中，该树的高度为（A）。假定空树的高度为-１。A．5ﻩ ﻩ B．6 ﻩﻩ C.7ﻩﻩﻩﻩ ﻩD．8４②树中所有结点的度等于所有结点数加（Ｃ)。Ａ.０ Ｂ．１ ﻩﻩ C．－1ﻩ ﻩ D.2５②在一棵具有n个结点的二叉树的第i层上（假定根结点为第０层,ｉ大于等于0而小于等于树的高度),最多具有(A）个结点。ﻩＡ．2ｉ ﻩ ﻩ ﻩ B．２i+1 Ｃ.2i−１ﻩﻩ ﻩﻩ ﻩ D．2n６②在一棵完全二叉树中，假定根结点的编号为０，则对于编号为I(I＞０)的结点，其双亲结点的编号为(B)。ﻩA.(I+1)/2ﻩﻩﻩ ﻩﻩＢ．(I-1）／2ﻩC．I/2ﻩﻩ ﻩ ﻩﻩ D.I/2－17③在一棵具有n个结点的二叉树中,所有结点的空子树个数等于(C)。A.nB.n-1Ｃ.n+1Ｄ.2*n8③在一棵高度为h（假定根结点的层号为0）的完全二叉树中，所含结点个数不小于（D）。ﻩＡ．2h−1ﻩﻩﻩ ﻩﻩ B．２h＋1 Ｃ.21h−ﻩ ﻩ D．２h9②如下的4棵二叉树中，（D）不是完全二叉树。 Ａ ﻩ ﻩ B ﻩ Ｃﻩ ﻩ D图4.471０题图１0②深度为5的二叉树至多有(C)个节点。ﻩA.１6 ﻩ Ｂ.3２ﻩＣ．3１ ﻩﻩﻩﻩ ﻩﻩD．１0１1③对一棵满二叉树而言，ｍ个树叶,ｎ个节点,深度为h，则下列哪个等式对的(D)。A.n=h+m ﻩ ﻩﻩ B．h+m＝2nﻩC.m=n－1 ﻩﻩﻩD．ｎ＝２h-112②有一棵非空的二叉树,共有n个节点，其中分支度为２的结点有w个，则分支度为1的结点个数为(Ｂ）。 Ａ.ｎ-２ｗ ﻩ ﻩﻩﻩﻩB.ｎ－2ｗ－1ﻩC．n-w+1 ﻩﻩﻩ D.ｎ-2w＋11３②具有n(n＞0)个结点的完全二叉树的深度为(C)。A．log2nﻩ ﻩﻩﻩﻩ Ｂ.loｇ2ｎ C．lｏg２n+１ ﻩﻩﻩD.（lｏｇ2n)+1１4②设树Ｔ的度为4，其中度为１,2,3和4的结点个数分别为4,２,1,1则T中的叶子数为(D)【南京理工2023】Ａ.５B．6C.7D．81５②在下述结论中，对的的是(D）。【南京理工19９９】（1）只有一个结点的二叉树的度为0;(２）二叉树的度为2；（3)二叉树的左右子树可任意互换;(４）深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.（1)(2）（3）B．(２)(3）(4)Ｃ.（2)(４)D.（1）（4）16②若一棵二叉树具有10个度为2的结点，５个度为1的结点,则度为0的结点个数是(B)【北京工商２02３】A.9B．1１Ｃ．15D．不拟定17②一棵完全二叉树上有1001个结点,其中叶子结点的个数是（Ｅ）。【西安交通1996】A．２50B．500Ｃ．2５４D.505Ｅ.以上答案都不对二、填空题１②由3个结点所构成的二叉树有＿__５_＿_种形态；16个结点可构造出________种不同形态的二叉树。2②将具有82个结点的完全二叉树从根结点开始顺序编号，根结点为第0号,其他结点自上向下,同一层自 左向右连续编号。则第40号结点的双亲结点的编号为__＿14_____。3①在一棵树中，_根___＿＿结点没有前驱结点。４②假定一棵二叉树的结点个数为１８,则它的最小高度为＿_4___＿。假定根结点的高度为0。5②假定一棵三叉树（即度为３的树)的结点个数为５0,则它的最小高度为＿_4_。假定根结点的高度为0。6②一棵高度为5的完全二叉树中，最多包具有__63____个结点。假定根结点的高度为０。7②在一棵三叉树中,度为3的结点数有2个,度为2的结点数有1个,度为１的结点数为2个,那么度为０的结点数有___6＿_＿个。8②在一棵高度为3的四叉树中,最多具有＿_2１__＿＿结点。9②一棵深度为6的满二叉树有____31_＿个分支结点和＿_3２＿__＿个叶子。10②一棵具有25７个结点的完全二叉树，它的深度为__＿9__＿。11②设一棵完全二叉树具有１00０个结点，则此完全二叉树有__５00___＿个叶子结点,有_＿_499９___个度为ﻩ 2的结点，有_＿1_＿__个结点只有非空左子树,有＿_＿0___个结点只有非空右子树。１2②对于一棵具有n个结点的树,该树中所有结点的度数之和为__n-１_______。13②一棵具有ｎ个结点的二叉树，若它有n0个叶子结点,则该二叉树上度为１的结点n1=_ｎ-2n０+1_＿_＿_。１4②假如结点A有3兄弟,并且B是A的双亲,则B的度是___4＿__。15②对于一棵完全二叉树，设一个结点的编号为i,若它的左孩子结点存在，则其编号为_＿2*i_____＿；若右 ﻩ 孩子结点存在，则其编号为_2*i+1＿_____＿;而双亲结点的编号为＿___ｉ/2＿＿___。16②深度为ｋ的完全二叉树至少有２ｋ-1个结点,至多有２k-１个结点。【厦门202３】【南京理工1999】17②已知一棵度为3的树有2个度为1的结点,3个度为２的结点，4个度为3的结点，则该树有____12＿__＿_个叶子结点。【厦门202３】18②一棵有n个结点的满二叉树有___０____＿_个度为1的结点、有__(n+1)/2＿______个分支（非终端）结点和_＿(ｎ-1)／2__＿_＿＿_个叶子,该满二叉树的深度为___log2n+1ﻩ_＿____。【华中理工2023】三、判断题（Ｔ）1①二叉树中每个结点的两棵子树是有序的。（F）2①二叉树中每个结点有两棵非空子树或有两棵空子树。（F)3②对于一棵非空二叉树,它的根结点作为第一层,则它的第i层上最多能有２i-1个结点。(T)4②具有12个结点的完全二叉树有5个度为2的结点。（Ｔ）5①完全二叉树的某结点若无左孩子,则它必是叶结点。（Ｆ）6②二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。(T)7②当k≥１时，高度为ｋ的二叉树至多有２1k−个结点。(Ｆ)8②一棵具有n个结点的完全二叉树,它的高度是lｏg2n+1。(F)9①二叉树就是结点度为2的树。【长沙铁道１9９７】【中科院软件所1997】(Ｆ)10②完全二叉树一定存在度为1的结点。【青岛2０２３】(T）11①树形结构中元素之间存在一个对多个的关系。【燕山1998】（Ｆ）１2①树与二叉树是两种不同的树型结构。【东南２023】四、简答题1③已知一棵度为ｍ的树中有N1个度为1的结点，N2个度为2的结点,…,Nｍ个度为m的结点。试问该树中有多少个叶子结点?２③树和二叉树之间有什么样的区别与联系？【西北工业1９98】【厦门2023】【燕山20２3】４.９.2知识点：二叉树和树的存储结构一、选择题1①在一棵树的左子女-右兄弟表达法中,一个结点的右孩子是该结点的(Ａ）结点。ﻩA．兄弟ﻩﻩＢ．子女C.祖先 D.子孙2②在一棵树的静态双亲表达中,每个存储结点包含(Ｂ)个域。 A.1ﻩ B．2C.3 D．4３②在一棵二叉树的二叉链表中,空指针域数等于非空指针域数加（A)。 A．２ B．１C．0 ﻩD．-１4②二叉树是非线性数据结构,所以（C）。 A.它不能用顺序存储结构存储 B.它不能用链式存储结构存储C．顺序存储结构和链式存储结构都能存储D．顺序存储结构和链式存储结构都不能使用5②运用二叉链表存储树,则根结点的右指针是(B)。【青岛202３】A.指向最左孩子B．指向最右孩子C.空D.非空６②在下列存储形式中,哪一个不是树的存储形式？（Ｄ）【北方交通2023】A.双亲表达法B.孩子链表表达法Ｃ.孩子兄弟表达法Ｄ.顺序存储表达法7②一棵有ｎ个结点的二叉树,按层次从上到下,同一层从左到右顺序存储在一维数组Ａ［1．.n］中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组Ａ中的位置是(Ｂ）【南京理工2023】A．A［2i]（２i＜=n）Ｂ.A[２i+1](２i+1<=n)C．A［i－2]D.条件不充足，无法拟定填空题１①二叉树通常有___顺序_＿＿__＿存储结构和__＿__链式_______存储结构。判断题（T)１②若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有ｎ-1个非空指针域。(T)2①树适合于表达层次关系。(T）３②完全二叉树的存储结构通常采用顺序存储结构。【南京航空航天１996】四、简答题1②描述二叉树的顺序存储。2②描述二叉树的链式存储。4．９.3知识点:树、森林向二叉树的转换选择题1②把一棵树转换为二叉树后,这棵二叉树的形态是(Ａ）。 A．唯一的ﻩﻩﻩﻩﻩﻩ ﻩB．有多种 C.有多种,但根结点都没有左孩子ﻩﻩD.有多种,但根结点都没有右孩子2②如下图所示的二叉树Ｔ2是由森林T１转换而来的二叉树,那么森林Ｔ1有（C）个叶子结点。AABEDJIGHCF图4.48２题图 A.4 ﻩＢ．5C．６ﻩ Ｄ．7填空题1②设森林Ｆ中有4棵树，第1、2、3、4棵树的结点个数分别为ｎ１、ｎ２、ｎ3、n4,当把森林F转换成一棵二叉树后，其根结点的左子树中有＿＿_＿ｎ1-1_＿__＿__＿＿_＿_个结点。２②将森林或树转换成二叉树时，所有的水平线段以左边结点为轴心_顺时针＿_旋转4５o。3②运用树的孩子兄弟表达法存储,可以将一棵树转换为＿二叉树_＿_＿____。【重庆2023】三、判断题(T）１②将森林或树转换成二叉树时，在所有相邻兄弟结点（森林中每棵树的根结点可以当作是兄弟结点）之间加一水平连线。（T)2②将森林或树转换成二叉树时,对每个非叶子结点ｋ，除了其最左边的孩子结点外，删去k与其他孩子结点的连线。（F)3②将一棵树转换成二叉树后,根结点没有左子树。（F)４②必须把一般树转换成二叉树后才干进行存储。【南京航空航天19９７】四、简答题1③把如图所示的树转化成二叉树。ABABDGJMIKLCEFH２③如何把森林转换成二叉树。4.4９1题图4.9．４知识点：树与二叉树的遍历图一、选择题1②已知某二叉树的后序遍历序列是dabｅｃ，中序遍历序列是deｂａc，则它的前序遍历序列是(Ｄ)。 Ａ．acbeｄ B．ｄecaｂＣ．ｄeabc Ｄ.cｅdba2②在一棵非空的二叉树的中序遍历序列中，根节点的右边(Ｂ)。A．只有左子树上的所有节点B.只有右子树上的所有节点C.只有左子树上的部分节点Ｄ.只有右子树上的部分节点3②下列二叉树的后序遍历序列是（C)。aabcdfgexyh图4．5０3题图 A.aｂdecfghxy ﻩＢ．ａbdｇｃehｆxyC．ｇｄbhｅxyfcａ D．ｄgbaｅhcｘfｙ４②任何一棵二叉树的叶节点在前序、中序和后序遍历序列中的相对顺序(A）。 Ａ．不发生改变ﻩ Ｂ．发生改变C．不能拟定ﻩD．以上都不对5②线索二叉树是一种(Ｃ)结构。ﻩA．逻辑 Ｂ．逻辑和存储C．物理 ﻩＤ.线性6②将下图的二叉树按中序线索化，结点X的右指针和Ｙ的左指针分别指向（C)ﻩA.A,D B.B，CC.Ｄ，A D.C,ＡAABDCEXY图４.５16题图7②引入线索二叉树的目的是(A）。【南京理工1９98】ﻩＡ．加快查找结点的前驱或后继结点的速度ﻩB．为了能在二叉树中方便插入和删除ﻩC.为了能方便找到双亲ﻩ ﻩﻩﻩD．使二叉树的遍历结果唯一8②树的后根遍历序列等同于该树相应的二叉树的(Ｂ）。【北京理工2023】Ａ.先序序列B.中序序列C．后序序列9②一棵二叉树的前序遍历序列为ABＣDEFG,它的中序遍历序列也许是（B）【北京工业20２３】A.CABDEFGB.ABＣDEFGC.DAＣEＦＢGＤ.AＤCFＥG10②已知一棵二叉树的前序遍历结果为AＢCDEF,中序遍历结果为ＣＢＡＥＤF,则后序遍历的结果为（Ａ）。【浙江1999】A.CBEFＤAＢ.FEDＣBAC．CBEDFAD.不定１1②某二叉树中序序列为A，B，Ｃ,Ｄ，E，Ｆ，Ｇ，后序序列为B，D,Ｃ,A,F，Ｇ,E则前序序列是：（B）【南京理工2023】Ａ.E，G，F,A,C，Ｄ，ＢB．E,A，C，B,Ｄ,G，FＣ.E，A,G，C，F，B，DD.上面的都不对１2②对于前序遍历与中序遍历结果相同的二叉树为(ＢＦ)；对于前序遍历和后序遍历结果相同的二叉树为(B)。【中科院计算所1999】A．一般二叉树B．只有根结点的二叉树C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树Ｅ.所有结点只有左子数的二叉树F.所有结点只有右子树的二叉树二、填空题1②在二叉树的一维数组存储方式中,父节点和右孩子的索引值之间满足的关系是＿２倍加1_＿＿____。2②在中序线索化二叉树时，采用__中序______遍历方法最合适。3②线索二叉树中的左线索指向其＿_前驱＿_＿_＿_,右线索指向其__后继__＿___。【哈尔滨工业20２３】三、判断题（T)1②