考研数据结构习题及参考答案.pdf

习题1一、单项选择题A.数据兀索的组织形式C.数据存储结构1.数据结构是指（）。B.数据类型D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称 之 为（）oA.存储结构 B.逻辑结构C.链式存储结构 D.顺序存储结构3.树形结构是数据元素之间存在一种（）。A.1 对一关系 B.多对多关系C.多对一关系 D.一对多关系4,设语句x+的时间是单位时间，则以下语句的时间复杂度为（）。fbr（i=l;i=n;i+）fbr（j=i;j=n;j+）x+;A.0（1）B.0（/?2）C.0（n）D.0（n3）5.算法分析的目的是（）,算法分析的两个主要方面是（.）。（1）A.找出数据结构的合理性C.分析算法的效率以求改进（2）A.空间复杂度和时间复杂度C.可读性和文档性6.计算机算法指的是（|）,它具备输入,（1）A.计算方法C.解决问题的有限运算序列（2）A.可行性，可移植性和可扩充性C.确定性，有穷性和稳定性B.研究算法中的输入和输出关系D.分析算法的易懂性和文档性B.正确性和简明性D.数据复杂性和程序复杂性输 出 和（|）等五个特性。B.排序方法D.调度方法B.可行性，确定性和有穷性D.易读性，稳定性和安全性7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。A.低 喊 C.相同 D.不好说8.数据结构作为一门独立的课程出现是在（）年。A.1946 B.1953 C.1964 D.19689.数据结构只是研究数据的逻辑结构和物理结构,这种 观 点（）。A.正确|.错蠲C.前半句对，后半句错 D.前半句错，后半句对1 0.计算机内部数据处理的基本单位是()A.数据C.数据项D.数据库二、填空题1.数据结构按逻辑结构可分为两大类，分别是 线性结构 和 非线性结构2.数据的逻辑结构仃四种基本形态，分别是_ 线性、图和 偏。3.线性结构反映结点间的逻辑关系是 _对的，非线性结构反映结点间的逻辑关系是一 多或者是多对国 的。4.个算法的效率可分为 效率和 喊效率。5.在树型结构中，树根结点没有I 个前趋驱结点;叶子结点没有.多个o前趋 结点，其余每个结点的有且只有结点；其余每个结点的后续结点可以6.在图型结构中，每个结点的前趋结点数和后续结点数可以7.线 性 结 构 中 元 素 之 间 存 在-对一 关系;树型结构中元素之间存在 对多 关系；图 型 结 构 中 元 素 之 间 存 在 多对多 关系。8.下面程序段的时间复杂度是f o r(i=0;i n;i+4-)f o r(j=0;j n;j-H-)A i U =0；9.下面程序段的时间复杂度是。i=s=0;w h i l e(s n)i+；s+=i;10.下面程序段的时间复杂度是 os=0;f br(i=0;i n;i-H-)f o r(j=0;j n;j+)s+=B i j ;s u m=s;11.下面程序段的时间复杂度是 Oi=l；w h i l e(i =n)i=i*3;1 2,衡量算法正确性的标准通常是 o1 3.算法时间复杂度的分析通常有两种方法，即 和 的方法，通常我们对算法求时间复杂度时，采用后一种方法。三、求下列程序段的时间复杂度。1.x=0;f br(i=l;i n;i+)f br(j=i+l；j =n;j+)x+;O2.x=0;f br(i=l;i n;i+)f o r d=l；j =n-i；j+)x+;3.i n t i,j,k;f br(i=O;i n;i+)f o r(j=0;j =n;j+)c i 0 =0;f o r(k=0;k =O)&A i !=k)j-;r e t u r n (i);5.f a c t(n)i f(n=l)r e t u r n (1);e ls er e t u r n (n*f h c t(n-l);)习题1参考答案一、单项选择题1.A 2.C 3.D 4.B 5.C、A 6.C、B 7.B 8.D 9.B 10.B二、填空题1.线性结构，非线性结构2.集合，线性，树，图3.一对一，一对多或多对多4 .时间，空间5.前趋，一，后继，多6 .有多个7 .一对一，一对多，多对多8.0(2)9.0(4)1 0.0(2)1 1.O(lo g3n)1 2.程序对于精心设计的典型合法数据输入能得出符合要求的结果。1 3.事后统计，事前估计三、算法设计题l.O(n2)2.0(/)3.0(n3)4.0(n)5.0(D)-4-习题2一、单项选择题1.线性表是。A.一个有限序列，可以为空 B.一个有限序列，不可以为空C.一个无限序列，可以为空 D.个无限序列，不可以为空2.在一个长度为n的顺序表中删除第i个元素(0next=s;s-prior=p;p-next-prior=s;s-next=p-next;B.s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;C.p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;D.s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;6.设单链表中指针p指向结点m,若要删除m之后的结点(若存在)，则需修改指针的操作为。A.p-next=p-next-next;B.p=p-next;C.p=p-next-next;D.p-next=p;7.在一个长度为n的顺序表中向第i个元素(Ov ivn+1)之前插入一个新元素时，需向后移动 个元素。A.n-i B.n-i+1 C.n-i-1 D.i8.在个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点,则须执行A.s-next=p-next;p-next=sB.q-next=s;s-next=pC.p-next=s-next;s-next二p-5-D.p-n e x t=s;s-n e x t=q9.以 下 关 于 线 性 表 的 说 法 不 正 确 的 是。A.线性表中的数据元素可以是数字、字符、记录等不同类型。B.线性表中包含的数据元素个数不是任意的。C.线性表中的每个结点都有且只有一个直接前趋和直接后继。D.存在这样的线性表：表中各结点都没有直接前趋和直接后继。1 0 .线性表的顺序存储结构是一种 的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取1 1 .在顺序表中，只要知道,就可在相同时间内求出任一结点的存储地址。A.基地址 B.结点大小C.向量大小 D.基地址和结点大小1 2 .在等概率情况下，顺序表的插入操作要移动 结点。A.全部 B.一半C.三分之一-D.四分之一1 3 .在 运算中，使用顺序表比链表好。A.插入 B.删除C.根据序号查找 D.根据元素值查找1 4 .在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是。A.0(1)B.O(n)C.O(n2)D.O(lo g 2 n)1 5.设 有一个栈，元 素 的 进 栈 次 序 为 A,B,C,D,E,下列是不可能的出栈序列A.A,B,C,D,E B.B,C,D,E,AC.E,A,B,C,D D.E,D,C,B,A1 6 .在一个具有n个单元的顺序栈中，假定以地址低端(即0单元)作为栈底，以t o p作为栈顶指针，当做出栈处理时，t o p 变化为。A.t o p 不变 B.t o p=0 C.t o p-D,t o p+17 .向一个栈顶指针为h s 的链栈中插入一个s 结点时，应执行 oA.h s-n e x t=s;B.s-n e x t=h s;h s=s;C.s-n e x t=h s-n e x t;h s-n e x t=s;D.s-n e x t=h s;h s=h s-n e x t;18 .在具有n个单元的顺序存储的循环队列中，假定和re a r分别为队头指针和队尾指针，则判断队满的条件为 oA.re a r%n=f ro n t B.(f ro n t+1)%n=re a rC.re a r%n -1=f ro n t D.(re a r+1)%n=-f ro n t19 .在具有n个单元的顺序存储的循环队列中，假定价o n t 和 re a r分别为队头指针和队-6-尾指针，则 判 断 队 空 的 条 件 为。A.rear%n=front B.front+l=rearC.rear=front D.(rear+1)%n=front2 0.在一个链队列中，假定fhmt和 rear分别为队首和队尾指针，则删除一个结点的操作为 oA.front=front-next B.rear=rear-nextC.rear=front-next D.front=rear-next二、填空题1.线性表是一种典型的 结构。2.在一个长度为n 的顺序表的第i 个元素之前插入一个元素，需要后移_个元素。3.顺序表中逻辑上相邻的元素的物理位置 o4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需 一个位置,移动过程是从 向 依次移动每一个元素。5.在线性表的顺序存储中，元素之间的逻辑关系是通过 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 决定的。6.在双向链表中，每个结点含有两个指针域，-个指向 结点，另一个指向_ _ _ _ _ _ _ 结点O7.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用存储结构为宜。相反，当经常进行的是插入和删除操作时,则采用 存储结构为宜。8.顺序表中逻辑上相邻的元素，物理位置 相邻，单链表中逻辑上相邻的元素，物理位置 相邻。9.线性表、栈和队列都是 结构，可以在线性表的 位置插入和删除元素；对于栈只能在 位置插入和删除元素；对于队列只能在 位置插入元素和在位置删除元素。10.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为和;而根据指针的联接方式，链表又可分为 和。11.在 单 链 表 中 设 置 头 结 点 的 作 用 是。12.对于一个具有n 个结点的单链表，在已知的结点p 后插入一个新结点的时间复杂度为,在给定值为x 的 结 点 后 插 入 一 个 新 结 点 的 时 间 复 杂 度 为。13.对于一个栈作进栈运算时，应 先 判 别 栈 是 否 为，作退栈运算时，应先判别栈是否为,当栈中元素为m 时，作进栈运算时发生上溢，则说明栈的可用最大容量为。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 分别设在这片内存空间的两端，这样只有当时才产生上溢。14.设有一空栈，现有输入序列 1,2,3,4,5,经过 push,push,pop,push,pop,push,push后，输出序列是。15.无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为。三、简答题1.描述以下三个概念的区别：头指针，头结点，表头结点。2.线性表的两种存储结构各有哪些优缺点？3.对于线性表的两种存储结构，如果有n 个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？4.对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。5.在单循环链表中设置尾指针比设置头指针好吗？为什么？6.假定有四个元素A,B,C,D 依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。7.什么是队列的上溢现象？一般有几种解决方法，试简述之。8.下述算法的功能是什么？LinkList*Dcmo(LinkList*L)L是无头结点的单链表LinkList*q,*p;if(L&L-next)q=L;L=L-ncxt;p=L;while(p-next)p=p-next;p-next=q;q-next=NULL;return(L);四、算法设计题1.设计在无头结点的单链表中删除第i 个结点的算法。2.在单链表上实现线性表的求表长ListLength(L)运算。3.设计将带表头的链表逆置算法。4.假设有一个带表头结点的链表，表头指针为h ead,每个结点含三个域：data,next和 prioro 其中data为整型数域，next和 prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域(此域初值为NU LL)把所有结点按照其值从小到大的顺序链接起来。5.已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素(若表中存在这样的元素)的算法。6.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于m in的元素的算法。7.假定用一个单循环链表来表示队列(也称为循环队列)，该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：(1)向循环链队列插入一个元素值为X的结点；(2)从循环链队列中删除一个结点。8.设顺序表L是一个递减有序表，试写一算法，将 x 插入其后仍保持L的有序性。习题2 参考答案一、单项选择题1.A 2.A 3.D 4.C 5.D 6.A 7.B 8.B 9.C 1 0.A 1 1.D 1 2.B1 3.C 1 4.B 1 5.C 1 6.C 1 7.B 1 8.D 1 9.C 2 0.A二、填空题1 .线性2 .n-i+13 .相邻4 .前移，前，后5 .物理存储位置，链域的指针值6 .前趋，后继7 .顺序，链接8 .一定，不一定9 .线性，任何，栈顶，队尾，队头1 0 .单链表，双链表，非循环链表，循环链表1 1 .使空表和非空表统算法处理一致1 2 .0(1),0(n)1 3 .栈满，栈空，m,栈底，两个栈的栈顶在栈空间的某一位置相遇1 4 .2、31 5 .0(1)三、简答题1 .头指针是指向链表中第一个结点(即表头结点)的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。2 .线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。3 .应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。4.应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构,而链表则是一种顺序存取的存储结构。5.设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为re a r,则开始结点和终端结点的位置分别是rear-next-next和 r e a r,查找时间都是 0(1)。若用头指针来表示该链表，则查找终端结点的时间为0(n)。6.共 有 14种可能的出栈序列，即为：ABCD,ABDC,ACBD,ACDB,BACD,ADCB,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA7.在队列的顺序存储结构中，设队头指针为front,队尾指针为re a r,队列的容量(即存储的空间大小)为maxnum1,当有元素要加入队列(即入队)时，若 rear=maxnum,则会发生队列的匕溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。一般地，要解决队列的上溢现象可有以下几种方法：(1)可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低,浪费存储空间。(2)要避免出现“假溢出”现象可用以下方法解决：第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。8.该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。四、算法设计题1.算法思想为：(1)应判断删除位置的合法性，当 in-l时，不允许进行删除操作；(2)当 i=0时，删除第一个结点：(3)当 O vivn时，允许进行删除操作，但在查找被删除结点时，须用指针记住该结点的前趋结点。算法描述如下：delete(LinkList*q,int i)-10-在无头结点的单链表中删除第i个结点LinkList*p,*s;int j;if(inext;free(s);)else j=0;s=q;while(jnext;j+；if(s=NULL)printfifCantt delete);else p-next=s-next;free(s);2.由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：int ListLength(LinkList*L)求带头结点的单链表的表长int len=0;ListList*p;P=L；while(p-ncxt!=NULL)p=p-next;len+;return(len);-11-3.设单循环链表的头指针为head,类型为LinkListo逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q 结点的指针域时，设 s 指向其原前趋结点，p 指向其原后继结点，则只需进行q-next=s;操作即可，算法描述如下：void invert(LinkList*head)/逆置head指针所指向的单循环链表linklist*p,*q,*s;q=head;p=head-next;while(p!=head)当表不为空时，逐个结点逆置 s=q;q=p；p=p-next;q-next=s;)p-next=q;4.定义类型LinkList如下:typedef struct node int data;struct node*next,*prior;LinkList;此题可采用插入排序的方法，设 p 指向待插入的结点，用 q 搜索已由prior域链接的有序表找到合适位置将p 结点链入。算法描述如下：insert(LinkList*head)LinkList*p,*s,*q;p=head-next;p指向待插入的结点，初始时指向第一个结点while(p!=NULL)s=head;/s指向q结点的前趋结点q=head-prior;/q指向由prior域构成的链表中待比较的结点while(q!=NULL)&(p-dataq-data)杳找插入结点p的合适的插入位置 s=q;q=q-prior;)s-prior=p;p-prior=q;结点p插入到结点s和结点q之间p=p-next;)5 .算法描述如下：delete(LinkList*head,int max,int min)linklist*p,*q;if(head!=NULL)q=head;p=head-next;while(p!=NULL)&(p-datanext;while(p!=NULL)&(p-datanext;q-next=p;6 .算法描述如下：delete(LinkList*head,int max,int min)LinkList*p,*q;q=head;p=head-next;while(p!=NULL)if(p-datadata=max)q=p;p=p-next;)else q-next=p-next;free(p);p=q-ncxt;)7 .本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：(1)插入(即入队)算法：insert(LinkList*rcar,clcmtypc x)设循环链队列的队尾指针为rear,x为待插入的元素LinkList*p;p=(LinkList*)malIoc(sizeofLinkList);-13-if(rear=NULL)如为空队，建立循环链队列的第一个结点 rear=p;rear-next=p;链接成循环链表)else 否则在队尾插入p结点 p-next=rear-next;rear-next=p;rear=p;)(2)删 除(即 出 队)算 法：delete(LinkList*rear)设循环链队列的队尾指针为rearif(rear=NULL)空队printf(underflownn);ifi(rear-next=rear)队中只有一个结点rear=NULL;elserear-next=rear-next-next;/rear-next指向的结点为循环链队列的队头结点)8.只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：int InsertDecreaseList(SqList*L,elemtype x)int i;if(*L).len=maxlen)printfi(4overflown);rcturn(O);)fbr(i=(*L).lcn;i0&(*L).clcm i-1 0 B.i W n-15-C.l W i W n D.lW i W n+19.字符串采用结点大小为1 的链表作为其存储结构，是 指()oA.链表的长度为1B.链表中只存放1 个字符C.链表的每个链结点的数据域中不仅只存放了一个字符D.链表的每个链结点的数据域中只存放了一个字符二、填空题1 .计算机软件系统中，有两种处理字符串长度的方法：一种是,第二种是o2.两个字符串相等的充要条件是 和 o3.设字符串 S1=ABCDEF，S2=“PQRS”；则运算 S=CONCAT(SUB(SI,2,LEN(S2),SUB(SI,LEN(S2),2)后的串值为。4.串是指 o5 .空串是指,空格串是指 o三、算法设计题1 .设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1 至 第 s个单元中(每个单元存放一个字符)。现要求从此串的第巾个字符以后删除长度为t的子串，m s,t (s-m),并将删除后的结果复制在该数组的第s单元以后的单元中，试设计此删除算法。2 .设 s 和 t 是表示成单链表的两个串，试编写一个找出s中 第 1 个不在t中出现的字符(假定每个结点只存放1 个字符)的算法。习题3 参考答案一、单项选择题1.B 2.D 3.C 4.D 5.B 6.C 7.D 8.C 9.D二、填空题1 .固定长度，设置长度指针2 .两个串的长度相等，对应位置的字符相等3.“BCDEDE”4.含 n个字符的有限 序 列(n 2 0)5 .不含任何字符的串，仅含空格字符的字符串三、算法设计题1.算法描述为：int deleter,s,t,m)从串的第m个字符以后删除长度为t的子串-16-char r;int s,t,m;int i,j;fbr(i=l;i=m;i-H-)rs+i=ri;fbr(j=in+t-i;jdata!=pt-data)pt=pt-next;if(pt=NULL)ps=NULL;else ps=ps-next;s=ps;)return s;/find-17-习题4一、单项选择题1 .设二维数组A 0 n-l 按行优先顺序存储在内存中，第一个元素的地址为p,每个元素占k 个字节，则元素a,)的地址为()。A.p +i*n+j-l*k B.p+(i-l)*n+j-l*kC.p+(j-l)*n+i-l*k D.p+j*n+i-l*k2 .已知二维数组A iox io中，元素a2。的地址为56 0,每个元素占4 个字节，则元素ai。的地址为()。A.52 0B.52 2C.52 4D.51 83 .若数组A 0 m 0 n 按列优先顺序存储，则 地 址 为()。A.(aoo)+j*m+i B.L O C(aM)+j*n+iC.L O C(aM)+(j-l)*n+i-l D.L O C(aM)+(j-l)*m+i-l4.若下三角矩阵A.*.,按列顺序压缩存储在数组S aO(n+l)n/2 中，则非零元素a()的地址为()。(设每个元素占d 个字节)A.(j-D*n-生 2)(j二 D+1 *d2B.(j-1)*n-+i *d2C.2)(1-l)+i+i*d2D.(jT)*n-/2)(-D+i_2 *d25.设有广义表D=(a,b,D),其长度为(),深 度 为()。A.无穷大 B.3 C.2 D.56 .广义表A=(a),则表尾为()。A.a B.()C.空表 D.(a)7 .广义表 A=(x,(a,B),(x,(a,B),y),则运算 head(head(t ail(A)的结果为(7A.x B.(a,B)C.(x,(a,B)D.A8.下 列广义表用图来表示时，分支结点最多的是()。A.L=(x,(a,B),(x,(a,B),y)B.A=(s,(a,B)C.B=(x,(a,B),y)D.D=(a,B),(c,(a,B),D)9 .通常对数组进行的两种基本操作是()。A.建立与删除 B.索引和修改C.查找和修改 D.查找与索引-18-10.假定在数组A 中，每个元素的长度为3 个字节，行下标i 从 1到 8,列下标j 从 1到 1 0,从首地址SA 开始连续存放在存储器内，存放该数组至少需要的单元数为()。A.80 B.100 C.240 D.27011.数组A 中，每个元素的长度为3 个字节，行下标i 从 1 到 8,列下标j 从 1 到 10,从首地址S A 开始连续存放在存储器内，该数组按行存放时，元 素 A85的起始地址为()。A.SA+141B.SA+144C.SA+222D.SA+22512.稀疏矩阵一般的压缩存储方法有两种，即()。A.二维数组和三维数组 B.三元组和散列C.三元组和十字链表D.散列和卜字链表13.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算，这种观点()A.正确 B.不正确14.一个广义表的表头总是一个(A.广义表 B.元素 C.空表15.一个广义表的表尾总是一个()A.广义表 B.元素 C.空表16.数组就是矩阵，矩阵就是数组，这种说法()。A.正确 B.错误C.前句对，后句错 D.后句对D.元素或广义表D.元素或广义表二、填空题1.一维数组的逻辑结构是,存储结构是;对于二维或多维数组，分为 和 两种不同的存储方式。2.对 于 一 个 二 维 数 组 若 按 行 序 为 主 序 存 储,则 任 一 元 素 相对于A00的地址为 o3.一个广义表为(a,(a,b),d,e,(i,j),k),则该广义表的长度为_,深度为_。4.一个 稀 疏 矩 阵 为 0 0 2 0 -则对应的三元组线性表为 o3 0 0 00 0-1 50 0 0 05.一 个 n X n 的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为6.已知广义表 A=(a,b,c),(d,e,f),则运算 head(tail(ta il(A)=7.设有一个10阶的对称矩阵A,采用压缩存储方式以行序为主序存储，a 为第一个元素，其存储地址为0,每个元素占有1 个存储地址空间，则 ag 5的地址为。8.已知广义表Ls=(a,(b,c,d),e),运用head和 t a i l 函数取出L s中的原子b 的运算是-19-9.三维数组R c i d i,C 2 d z,C 3 d s 共含有 个元素。（其中：c i l c=N U L L B.p-l t a g=lC.p-l t a g=l 且 p-l c=N U L L D.以上都不对9 .设 n ,m 为一棵二叉树上.的两个结点，在中序遍历序列中n 在 m前的条件是（）。A.n 在 m右方 B.n 在 m左方C.n是 m的祖先 I）,n是 m的子孙1 0 .如 果 F是由有序树T转换而来的二叉树，那 么 T中结点的前序就是F中结点的（）。A.中序 B.前序 C.后序 D.层次序1 1 .欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二义树采用（）存储结构。A.三叉链表 B.广义表 C.二叉链表 D.顺序1 2 .下面叙述正确的是（）。A.二义树是特殊的树-22-B.二叉树等价于度为2 的树C.完全二叉树必为满二叉树D.二叉树的左右子树有次序之分13.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。A.不发生改变 B.发生改变C.不能确定 D.以上都不对14.已知一棵完全二叉树的结点总数为9 个，则最后一层的结点数为（）。A.1 B.2 C.3 I）.415.根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（）。A.是完全二叉树 B.不是完全二叉树C.是满二叉树 D.不是满二叉树二、判断题1.二叉树中每个结点的度不能超过2,所以二叉树是一种特殊的树。（）2.二叉树的前序遍历中，任意结点均处在其子女结点之前。（）3.线索二叉树是一种逻辑结构。（）4.哈夫曼树的总结点个数（多 于 1 时）不能为偶数。（）5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。（）6.树的后序遍历与其对应的二叉树的后序遍历序列相同。（）7.根据任意一种遍历序列即可唯一确定对应的二叉树。（）8.满二叉树也是完全二叉树。（）9.哈夫曼树一定是完全二叉树。（）10.树的子树是无序的。（）三、填空题1.假定一棵树的广义表表示为A（B（E）,C（F（H,I,J）,G）,D）,则该树的度为,树 的 深 度 为,终 端 结 点 的 个 数 为，单 分 支 结 点 的 个 数 为，双分 支 结 点 的 个 数 为,三 分 支 结 点 的 个 数 为,C 结 点 的 双 亲 结 点 为,其孩子结点为 和 结点。2.设 F 是 个森林，B 是由F 转换得到的二叉树，F 中有n 个非终端结点，则 B 中右指针域为空的结点有 个。3.对于一个有n 个结点的二叉树，当它为一棵 二叉树时具有最小高度，即为,当它为一棵单支树具有 高度，即为。4.由带权为3,9,6,2,5 的 5 个叶子结点构成 棵哈夫曼树，则带权路径长度为。5.在一棵二叉排序树上按 遍历得到的结点序列是一个有序序列。6.对于一棵具有n 个结点的二义树，当进行链接存储时，其二叉链表中的指针域的总数为 个，其中 个用于链接孩子结点，个空闲着。7.在一棵二又树中，度为0 的结点个数为n ,度为2 的结点个数为巾，则 n0=。8.一棵深度为k 的满二叉树的结点总数为_ _,一棵深度为k 的完全二叉树的结-23-点 总 数 的 最 小 值 为,最大值为 O9.由三个结点构成的二叉树，共有_种不同的形态。10.设高度为h 的二叉树中只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为。11.一棵含有n 个结点的k 叉树，形态达到最大深度，形态达到最小深度。12.对于一棵具有n 个结点的二叉树，若一个结点的编号为i（lWiWn）,则它的左孩子 结 点 的 编 号 为,右 孩 子 结 点 的 编 号 为,双 亲 结 点 的 编 号 为。13.对于一棵具有n 个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为个，其中 个用于链接孩子结点，个空闲着。14.哈夫曼树是指 的二叉树。15.空树是指,最小的树是指16.二叉树的链式存储结构有 和 两种。17.三叉链表比二叉链表多一个指向 的指针域。18.线索是指。19.线索链表中的rtag域值为 时，表示该结点无右孩子，此时 域为指向该结点后继线索的指针。20.本 节 中 我 们 学 习 的 树 的 存 储 结 构 有、和。四、应用题1.已知一棵树边的集合为 i,m,.,请画出这棵树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是结点g 的双亲？（4）哪些是结点g 的祖先？（5）哪些是结点g 的孩子？（6）哪些是结点e 的孩子？（7）哪些是结点e 的兄弟？哪些是结点f 的兄弟？（8）结点b 和 n 的层次号分别是什么？（9）树的深度是多少？（10）以结点c 为根的子树深度是多少？2.一棵度为2 的树与一棵二叉树有何区别。3.试分别画出具有3 个结点的树和二叉树的所有不同形态？4.已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL,写出该二叉树的先序、中序和后序遍历序列。5.一棵深度为H 的满k 叉树有如下性质：第 H 层上的结点都是叶子结点，其余各层上每个结点都有k 棵非空子树，如果按层次自上至下，从左到右顺序从1 开始对全部结点编号，回答下列问题：-24-(1)各层的结点数目是多少？(2)编号为n 的结点的父结点如果存在，编号是多少？(3)编号为n 的结点的第i 个孩子结点如果存在，编号是多少？(4)编号为n 的结点有右兄弟的条件是什么？其右兄弟的编号是多少？6.找出所有满足下列条件的二叉树：(1)它们在先序遍历和中序遍历时，得到的遍历序列相同；(2)它们在后序遍历和中序遍历时，得到的遍历序列相同；(3)它们在先序遍历和后序遍历时，得到的遍历序列相同；7.假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请写出该二叉树的后序遍历序列。8,假设一棵二叉树的后序序列为DCEGBFHKJIA,中序序歹！I为 DCBGEAHFIJK,请写出该二叉树的后序遍历序列。9.给出如图5-14所示的森林的先根、后根遍历结点序列，然后画出该森林对应的二叉树。10.给定一组权值(5,9,11,2,7,1 6),试设计相应的哈夫曼树。五、算法设计题1.一棵具有n 个结点的完全二叉树以一维数组作为存储结构，试设计个对该完全二义树进行先序遍历的算法。2.给定一棵用二叉链表表示的二叉树，其中的指针t 指向根结点，试写出从根开始，按层次遍历二义树的算法，同层的结点按从左至右的次序访问。3.写出在中序线索二叉树中结点P 的右子树中插入一个结点s 的算法。4,给定-棵二又树，用二叉链表表示，其根指针为t,试写出求该二叉树中结点n 的双亲结点的算法。若没有结点n 或者该结点没有双亲结点，分别输出相应的信息；若结点n 有双亲，输出其双亲的值。-25-习题5 参考答案一、单项选择题1 .C 2.B 3.C 4.D 5.B 6.D 7.C 8.B 9.B 1 0.B 1 1.A 1 2.D 1 3.A 1 4.B1 5 .A二、判断题l.X 2.V 3.X 4.V 5.X 6 7 7.V 8.V 9.X 1 0.X三、填空题1.3,4,6,1,1,2,A,F,G2.n+l3.完全,p i o g2(/i +l)1，最 大,n4.5 55.中序6.2 n,n-1,n+17.口 2+18.2k-l,2 巴 2k-l9.51 0.2h-l1 1.单支树，完全二叉树1 2.2 i,2 i+l,i/2 （或 i/2 ）1 3.2 n,n-1,n+11 4 .带权路径长度最小1 5 .结点数为0,只有一个根结点的树1 6 .二叉链表，三叉链表1 7 .双亲结点1 8 .指向结点前驱和后继信息的指针1 9 .1,R C h i l d2 0 .孩子表示法，双亲表示法，长子兄弟表示法四、应用题1.解答：根据给