国家开放大学20232024《数据结构》模拟试卷及答案解析（2024年）.docx

《国家开放大学20232024《数据结构》模拟试卷及答案解析（2024年）.docx》由会员分享，可在线阅读，更多相关《国家开放大学20232024《数据结构》模拟试卷及答案解析（2024年）.docx（69页珍藏版）》请在三一文库上搜索。

1、国家开放大学2023.2024学年数据结构模拟试卷及答案解析第一章绪论一、选择题1、把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）oA.给相关变量分配存储单元B.物理结构C.算法的具体实现D.逻辑结构2、下列说法中，不正确的是（）oA.数据项是数据中不可分割的最小可标识单位B.数据元素是数据的基本单位C.数据可有若干个数据元素构成D.数据项可由若干个数据元素构成3、一个存储结点存储一个（）oA.数据元素B.数据结构C.数据项D.数据类型4、数据结构中，与所使用的计算机无关的是数据的（）oA.存储结构B.物理和存储结构C.物理结构D.逻辑结构5、下列的叙述中，不属于算法特性的是（）

2、oA.可行性B.输入性C.可读性D.有穷性6、算法的时间复杂度与（）有关。A.计算机的操作系统B.算法本身C.数据结构D.所使用的计算机。7、口面程序段的时间复杂度是（)oi=s=0;while (sn)i+；s+=i;A.O(n0.5)B. O(log2n)C. O(n)D.O(1)8、卜面程序段的时间复杂度是（)oint(unsigned int n)if (n=0 I n=l) return 1;else return n*f(n-l);A.O(1)B. O(log2n)C. O(n!)D. O(n)10、在数据结构中，从逻辑上可以把数据结构分为A.动态结构和静态结构B.紧凑结构和非紧凑

3、结构C.内部结构和外部结构D.线性结构和非线性结构11、执行下面程序段时，执行S语句的次数为（)ofor (int i=l;i=n;i+)S;A.n2B.n22C.n(n+1)D.n(n+1)212、数据的存储结构包括数据元素的表示和（)oA.数据元素间的关系的表示B.数据处理的方法C.数据元素的类型D.相关算法13、树状结构中数据元素的位置之间存在（）的关系。A.一对一B.多对多C.每一个元素都有一个直接前驱和一个直接后继D.一对多14、一种逻辑结构（）oA.与存储该逻辑结构的计算机相关B.只能有唯一的存储结构C,可以有不同的存储结构D.是指某一种数据元素的性质15、把数据存储到计算机中，并

4、具体体现数据元素间的逻辑结构称为（）oA.逻辑结构B.数据元素的存储C,存储结构D.给数据元素分配存储空间二、判断题1 .数据元素是数据的最小单位。（）2 .数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。（）3 .算法和程序原则上没有区别，在讨论数据结构时二者是通用的。（）4 .数据的逻辑结构与数据元素本身的内容和形式无关。（）5 .算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（）6 .只有用面向对象的计算机语言才能描述数据结构算法。（）7 .数据元素可以有一个或多个数据项组成。（）8 .数据元素之间的抽象关系称为物理结构。（）9 .数据的逻

5、辑结构在计算机中的表示称为逻辑结构。（）10 .数据的逻辑结构是与存储该结构的计算机相关的。（）11 .数据结构中,元素之间存在多对多的关系称为树状结构。()12 .通常可以把某城市中各公交站点间的线路图抽象成树型结构。()13 .通常可以把一本含有不同章节的书的目录结构抽象成线性结构。()14 .结构中的数据元素存在多对多的关系称为图形结构。()15 .数据结构中，数据可以由一个或多个数据项组成。()三、程序题指出下列各算法的时间复杂度。intprime(intn)inti=l;int=(int)sqrt(n);while(+ix)return1;elsereturn0;2、intsuml(

6、intn)(intp=l,s=O;for(inti=l;i=n;i+)P*=i；s+=p;)returns;)3、 intsum2(intn)ints=0;for(int1=1;l=n;1+)intp=l;for(intj=l;j=l;j+)P*=j；s+=p;returns;)4、 intfun(intn)intI=Izs=l;while(snext=NULLB.p-next=q-nextC.p=q-nextD.p-next=q4、在一个单链表中P所指结点之后插入一个S所指的结点时，可执行（）。A.p-next=s;s-next=p-nextB.p-next=s-next;C.s-next=

7、p-next;p-next=s;D.p=s-next5、非空的单向循环链表的尾结点满足（）（设头指针为head,指针P指向尾结点）。A.p-next=headB.p=NULLC.P=headD.p-next=NULL6、链表不具有的特点是（）0A.不必事先估计存储空间B.可随机访问任一元素C.逻辑上相邻的元素在物理位置上不一定相邻D.插入删除不需要移动元素7、带头结点的链表为空的判断条件是（）（设头指针为head）。A. head-next=headB. head=NULLC. head-next=NULLD. head!=NLL8、在一个长度为n的顺序表中为了删除第5个元素，由第6个元素开始

8、从后到前依次移动了15个元素。则原顺序表的长度为（）0A.19B.21C.20D.259、有关线性表的正确说法是（）0A.线性表至少要求一个元素B.每个元素都有一个直接前驱和一个直接后继C.表中的元素必须按由小到大或由大到下排序D.除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继10、向一个有127个元素的顺序表中插入一个新元素，并保持原来的顺序不变,平均要移动（）个元素。A.63.5B.7C.63D.811、一个顺序表第一个元素的存储地址是90,每个元素的长度为2,则第6个元素的地址是（）oA.106B.98C.102D.10012、在一个不带头结点的单循环链表中，

9、p、q分别指向表中第一个结点和尾结点，现要删除第一个结点，且p、q仍然分别指向新表中第一个结点和尾结点。可用的语句是p=p-next;和（）oA.q-next=pB.p-next=qC.q=pD.p=q-next13、在线性表的顺序结构中，以下说法正确的是（）0A.逻辑上相邻的元素在物理位置上不一定相邻B.数据元素是不能随机访问的C.进行数据元素的插入、删除效率较高D.逻辑上相邻的元素在物理位置上也相邻14、对链表，以下叙述中正确的是（）0A.不能随机访问任一结点B.插入删除元素的操作一定要要移动结点C.结点占用的存储空间是连续的D.可以通过下标对链表进行直接访问15、设有一个长度为n的顺序表

10、要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。A.n-i+1B.iC.n-i-1D.n-i16、在一个单链表HL中，若要向表头插入一个由指针P指向的结点，则执行A. HL=p;p-next=HL;B. p-next=HL;HL=p;C. p-next=HL;p=HL;D. p-next=HL-next;HL-next=p;17、在一个单链表中，已知q所指结点是P所指结点的前驱结点，若在q和P之间插入S结点，则以下操作哪个是正确的（）oA. s-net=p-next;p-net=s;B. p-net=s-next;s-net=p;C. p-nex

11、t=s;s-next=q;D. q-next=s;s-next=p;18、在循环双链表的p所指结点之后插入s所指结点的操作是（）oA.p-right=s;s-left=p;p-right-left=s;s-right=p-right;B. p-right=S;p-right-left=S;s-left=p;s-right=p-right;C. s-left=p?s-right=p-right;p-right=s;p-right-left=s;D. s-left=p;s-right=p-right:p-right-left=s;p-right=s;19、若HL为一个不带表头结点的循环单链表的表头

12、指针，若有HL-next=HL条件存在，则该循环单链表是（）oA.空表B.只有1个元素；C.空表或只有一个元素D.非空表20、若HL为一个带表头结点的单链表的表头指针，则该表为空表的条件是A.HL=NLLB.HL-next=NLLC.HL-next=HLD.HL!=NLL21、设头指针为head的非空的单向链表，指针P指向尾结点,则通过以下操作()可使其成为单向循环链表。选择一项：A.head=p;B.p=head;C.p-next=NULL;D.p-next=head;二、判断题1、设有一个不带头结点的单向循环链表，结点的指针域为next,指针P指向尾结点，现要使P指向第一个结点，可用语句p

13、p-next*()2、设有一个单向链表，结点的指针域为next,头指针为head,P指向尾结点，为了使该单向链表改为单向循环链表，可用语句p-next=head。()3、设有一个单向循环链表，结点的指针域为next,头指针为head,指针P指向表中某结点，若逻辑表达式p-next=head;的结果为真，则P所指结点为尾结点。()4、要在一个单向链表中P所指向的结点之后插入一个S所指向的新结点，若链表中结点的指针域为next,可执行p-next=s;s-next=p-next;的操作。()5、要在一个单向链表中删除P所指向的结点，已知q指向P所指结点的直接前驱结点，若链表中结点的指针域为nex

14、t,则可执行q-next=p-next0()6、要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为next,头指针为head,尾指针为p,则可执彳亍head=head-next;p-next=head:。()7、设有一个单向循环链表，头指针为head,链表中结点的指针域为next,p指向尾结点的直接前驱结点，若要删除尾结点，得到一个新的单向循环链表，可执行操作p-next=head;。()8、设有一个长度为40的顺序表,要删除第8个元素需移动元素的个数为3。()9、线性表用关键字的顺序方式存储，可以用二分法排序。()10、线性表用顺序方式存储可以

15、随机访问。()三、程序填空1、设线性表以不带头结点的单向链表存储，链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data,完成程序中空格部分。#defineNULLOvoidmain()NODE*headz*p;p=head;*p为工作指针*/doprintf(%dn,1；2;while3I：2、设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，P指向链表中结点a,(设链表中没有结点的数据域与结点a的数据域相同)，写出相关语句(1)使该单向链表成为单向循环链表(2)插入结点s,使它成为a结点的直接前驱q=p;x=p-data;while(4)

16、q=q-next;q-next=head;q=p;p=p-next;while(p-data!=x)q=p;5)s-next=p;3、设有一个不带头结点的单向链表，头指针为head,p、PreP是指向结点类型的指针，该链表在输入信息时不慎把相邻两个结点的信息重复输入，以下程序段是在该单向链表中查找这相邻两个结点，把该结点的数据域data打印出来，并把其中之一从链表中删除，填写程序中的空格。prep=head;p=prep-next;while(p-data!=prep-data)prep=p;7;)Printf(min=%d”,8)；prep-next=9;第三章数组和广义表一、选择题1 .若

17、让元素1,2,3依次进栈，则出栈顺序不可能为（）。A.3,2,1B.2,1,31 .3,1,2D.1,3,22 .一个队列的入队序列是1,2,3,4。则队列的输出序列是（）o4150,则栈的不可能输出序列是（）40,30,50,10,20A.4,3,2,1B.1,2,3,C.1,4,3,2D.3,2,4,3 .一个栈的进栈序列是10,20,30,40,（进栈出栈可以交替进行）。A.10,20,30,40,50B.50,40,30,2（UO按该栈的可能输出序列依次入队列，该 ）（进栈出栈可以交替进行）。B. 10, 6, 4, 8C.40z50,30,20,10D.4 .元素4,6,8,10按顺

18、序依次进栈，队列的可能输出序列是（A.10,8,4,6D. 10, 8, 6, 4)0C.8,4,6,105 .向顺序栈中压入新元素时，应当（A.先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针C.先后次序无关紧要D.同时进行6 .在一个栈顶指针为top的链栈中,将一个p指针所指的结点入栈,应执行（）0A. top-next=p;B. p-next=top-next;top-next=p;C. p-net=top;top=p;D. p-next=top-next;top=top-next;7 .在一个栈顶指针为top的链栈中删除一个结点时，用X保存被删结点的值，则执行（）oA.x=to

19、p;top=top-next;B. x=top-data;C. top=top-next;x=top-data;D. x=top-data;top=top-next;）o8 .一般情况下，将递归算法转换成等价的非递归算法应该设置（A.栈B.队列C.堆栈或队列D.数组9 .表达式a*（b+c）-d的后缀表达式是（）o+A.abed*+-B.abc+*d-C.abc*+d-D.-+*abcd10 .判断一个顺序队列Sq（最多元素为m）为空的条件是（）oA.sq-rear-sq-front=mB.sq-rear-sq-front-l=mC.sq-front=sq-rearD.sq-front=sq-

20、rear+l11 .判断一个循环队列Q（最多元素为m）为满的条件是（）。A. Q-front=Q-rearB. Q-front!=Q-rearC. Q-front=（Q-rear+l）% mD. Q-front= （Q-rear+l）% m12 .判断栈S满（元素个数最多n个）的条件是（）oA.s-top=0B.s-top!=0C.s-top=n-lD.s-top!=n-l13 .一个队列的入队顺序是a,bed,则离队的顺序是（）0A. azd,cbB.a,b,c,dC.d,c,b,aD.c,b,d,a14 .如果以链表作为栈的存储结构，则退栈操作时（）0A.必须判断栈是否满C.必须判断栈是否

21、空B.判断栈元素类型D.对栈不作任何判断15 .在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。A.堆栈B.队列C.数组D.先性表16 .一个递归算法必须包括（）0A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分17 .从一个栈顶指针为top的链栈中删除一个结点时，用变量X保存被删结点的值，则执行（）0A.x=top-data;top=top-next;B.x=top-data;C.top=top-next;=top-data;D.top=top-nex

22、t;x=data;18 .在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）0A.r=f-next;B.r=r-next;C.f=f-next;D.f=r-next;19 .在一个链队中，假设f和r分别为队头和队尾指针，则插入S所指结点的运算为（）oA.f-next=s;f=s;B.r-next=s;r=s;C.s-next=r;r=s;D.s-next=f;f=s;20 .在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则从该对列中删除一个结点并把结点的值保存在变量X中的运算为（）。+A.x=r-data;r=r-next;B.r=r-next;x=r-dat

23、aC.x=f-data;f=f-net;D.f=f-next;x=f-data21 .栈和队列的共同特点是（）0A.都是先进后出B.元素都可以随机进出C.只容许在端点处插入和删除元素D.都是先进先出22 .栈的插入和删除操作在（）进行。A.栈顶B.栈底C.任意位置D.指定位置23 .在一个顺序队列中，队首指针指向队首元素的（）位置。A.前一个B.后一个C.当前D.后面24 .当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）oA.n-2B.n-1C.nD.n+125 .从一个顺序存储的循环队列中删除一个元素时，首先需要（）。A.队头指针加一B.队头指针减一C.取出队头指针所指的元素

24、D.取出队尾指针所指的元素二、判断题1 .链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。（）2 .在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。（）3 .栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。（）4 .若让元素1,2,3依次进栈，则出栈次序132是不可能出现的情况。（）5 .在用单链表表示的链式队列Q中，队头指针为Q-front,队尾指针为Q-rear,则队空条件为Q-front=Q-rear0（）6 .递归定义的数据结构通常用递归算法来实现对它的操作。（）7 .递归的算法简单、易懂、容易编写，而且执行效率也高。（）8 .递归调用算法与相同功能

25、的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制J,所以时间与空间开销通常都比较大。（）9 .用非递归方法实现递归算法时一定要使用递归工作栈。（）10 .栈是限定在表的一端进行插入和删除操作的线性表,又称为先进后出表。（）IL队列的特性是先进后出。（）12 .往栈中插入元素的操作方式是：先写入元素，后移动栈顶指针。（）13 .循环队列队头指针在队尾指针前一个位置，队列是“满”状态。（）14 .在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针后移，当删除一个元素队列时，头指针后移。（）15 .向一个栈顶指针为h的链栈（结点的指针域为next）中插

26、入一个S所指结点时,先执行s-next=h,再执行h=s操作。（）16 .一个递归算法不必包括递归终止条件。（）17 .在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有1个结点。（）18 .在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（）三、程序选择题1.在下面空格处填写一条语句，以使下面的链式队列全部元素出队的算法完整。 int write(LinkQueue *q) QueueNode *p;if (q-front=q-rear)printf(队空!无元素可取);eit(0);)while (q-front-next != NULL)p=q-f

27、ront-next;q-front-next=p-next;Printf(%4d”,p-data);free(p);)/*队空s7/*出队*/*释放已出队结点*/*队空时，头尾指针指向头结点*/A. q-front=q-rear;B. q=q-next;C. q-rear=q-front;D. p=p-next;2.在下面空格处填写适当的语句，以使下面的循环队列的入队和出队算法完整defineMAXSIZE100;typedefcharElemtype;typedefstructElemtypequeueMAXSIZE;intfront,rear;Jsequeuetype;Sequeuetyp

28、eQ;intencqueue(sequeuetype*Q,elemtypex)if(Q-rear+l)%MAXSIZE=Q-front)Printf(队列已满!n)；return1;elsejIQ-rear=(Q-rear+l)%MAXSIZE;(1)return0;)*入队算法*/Elemtypedel_CqUeUe(SeqUeUetyPe*Q)/if(2)/IPrintf(队列为空!n)；return1;else(Q-front=(Q-front+l)%MAXSIZE;return(Q-queueQ-front);*出队算法*/A. (1)(Q-rear+l)%MAXSIZE=Q-fron

29、t(2)Q-front=(Q-front+l)%MAXSIZE;B. (1)(Q-front+l)%MAXSIZE=Q-rear(2)Q-rear=(Q-rear+l)%MAXSIZE;C. (1)Q-front=Q,-rear(2)Q-queueQ-rear=x;D. (1)Q-queueQ-rear=x;(2)Q-front=Q-rear3.写出下列程序执行后的结果SeqQueueQ;InitQueue(Q);inta4=5,8,12,15;for(inti=0;i4;i+)lnQueue(Q,ai);InQUeUe(Q,OutQueue(Q);InQUelle(Q,30);InQUeUe

30、CboUtQUelle(Q)+10);while(!QueueEmpty(Q)Printf(%d”,OutQueue(Q);执行后的输出结果为：oA. 58121530B. 121553018C. 812153018D. 1215518304.写出下列程序执行后的结果SeqStackS;InitStack(三);Push(S,3);Push(S,4);Push(Sz5);intx=Pop(三)+2*Pop(三);Push(Szx);inti,a4=5,8,12,15;for(i=0;itop=MaxSize-l)Printfr栈满溢出错误!nw);exit(l);)s-datas-top=x

31、)A. s-top=s-data;B. s-data+;C. s-top+;D. s-data=s-top;6 .在下面空格处填写一条语句，以使下面的出栈算法完整。EIemTypePop(structSeqStack*s,ElemTypex)If(StackEmpty(s)Printf(栈下溢出错误！n)；exit(l);)x=s-datas-top;returnx;)A. s-top-;B. s-data-;C. s-top=s-data;D. s-data=s-top;第四章字符串一、选择题1 .以下陈述中正确的是（）0B.串的长度必须大于零D.空串就是空白串A.串是一种特殊的线性表C.

32、串中元素只能是字母2 .设有两个串P和q,其中q是P的子串，q在P中首次出现的位置的算法称为（）05.若串S= English”，其子串的个数是（A.求子串C.匹配3 .串是（）oA.不少于一个字母的序列C.不少于一个字符的序列4 .串的长度是指（）oA.串中所含不同字母的个数C.串中所含不同字符的个数B.连接D.求串长B.任意个字母的序列D.有限个字符的序列B.串中所含字符的个数D.串中所含非空格字符的个数）o+A.9B.16C.36D.286 .下面关于串的叙述中，不正确的是（）0A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串即可以采用顺序存储，也可以采

33、用链式存储7 .串与普通的线性表相比较，它的特殊性体现在（）0A.顺序的存储结构C.数据元素是一个字符8 .空串与空格串（ ）o BA.相同B.不相同9 .两个字符串相等的条件是（B.链接的存储结构D.数据元素可以任意C.可能相同D.无法确定A.两串的长度相等8 .两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同10 .串函数StrCat(a,b)的功能是进行串()。A.比较B.复制C.赋值D.连接11 .串函数StremP(aABCdw,“ABCD”)的值为()。A.0B.-1C.1D.312 .设主串为FABcCDABcdEFaBc”

34、以下模式串能与主串成功匹配的是(A.EFaBcB.ABCdEC.DABCCD.FAbcC13 .以下四个串中最小的是()0A.”ABADFB.ABAFDC.”ABADFAD.ABAF14 .在实际应用中，要输入多个字符串，且长度无法预定。则应该采用()存储比较合适。A.链式B.顺序C.堆结构D.无法确定二、判断题1 .用字符数组存储长度为n的字符串，数组长度至少为n+1。()2 .串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是字符。()3 .串的两种最基本的存储方式是顺序和链接。()4 .空串的长度是1。()5 .一个空格的串的长度是0。()6 .两个串相等的充分必要条件是每一个对

35、应位置的字符相同。()7 .字符串al=heijingz,za2=hen,a3=heifangvza4=heni最小的是a2o()8 .串函数StrCmP(uABCd,rtABCDw)的值为()三、程序选择题1 .一下程序段的结果是：C的值为()char*a5=12378,7,1237,7,1236789,7,1237,7,123708wintizc=0for(i=0;i5;i+)if(strcmp(ai,1237w)=0)c+;A.2B.5C.0D.12372 .以下程序段的结果是：C的值为()+Chara=1236789；int*p=a,c=O;While(*p+)c+;A.8B.7C.1

36、0D.12第五章数组和广义表一、选择题1. 一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为IO0,则该数组的首地址是（）o+A.64B.28C.70D.90）o对矩阵元素的存取变得简单减少不必要的存储空间的开销B.只能是子表D.可以是子表或原子）0B.索引与修改D.查找与索引2 .稀疏矩阵采用压缩存储的目的主要是（A.表达变得简单B.C.去掉矩阵中的多余元素D.3 .一个非空广义表的表头（）oA.不可能是原子C.只能是原子4 .常对数组进行的两种基本操作是（A.建立与删除C.查找和修改5 .设二维数组A6按行优先顺序存储在内存中，已知A起始地址为1000每个数组元素占

37、用5个存储单元，则元素A4的地址为（）oA.1140B.1145C.1120D.11256 .设有一个20阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（）o)oD. 38A.41B.32C.187 .广义表的(a,(d,azb),h,(e,(iJ)zk)深度是(A.6B.10C.8D.48 .广义表(f,hJabdzc),dzez(ij)的长度是A.6B.10C.8D.49.设有一个广义表A (a),其表尾为()oA. aB.()C. OD. (a)10.下列广义表中的线性表是()0A. E(a

38、b,c) B. E(a,E)C. E(a,b) D. E(azL ()二、判断题L使用三元组表示稀疏矩阵中的非零元素能节省存储空间。()2 .一个广义表的表头总是一个广义表。()3 .一个广义表的表尾总是一个表。()4 .一个广义表(a),(b),c)z(d)的长度为3,深度为4o()5 .一个广义表(a)z(bLc),(d)的表尾是(b),c)z(d)o()6 .需要压缩存储的矩阵可分为特殊矩阵矩阵和稀疏矩阵矩阵两种。()7 .设广义表L=(),(),则其表头是(O)0()8 .设广义表L=(),(),则其表尾是()。()9 .设广义表L=(),(),则其长度是0。()10 .广义表A(

39、a,bzc),(d,e,f)的表尾为(d,e,f)()11 .对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行号、列号和元素值三项信息。()12 .设有n阶对称矩阵A,用一维数组S压缩存储A的下三角元素，S的下标从零开始，元素s26相应于A中的元素为a7,6。()第六章树和二叉树一、选择题1 .树最适合用来表示（）0A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2 .树中所有结点的度等于所有结点数加（）oA.1B.OC.2D.-13 .对于一个满二叉树，m个树叶，n个结点，深度为h,则（）oA.n=h+mB.h+m=2nC.m=h

40、1D.n=2h-14 .如图所示一棵二叉树中，（C）不是完全二叉树。5.深度为5的二叉树至多有（）个结点。A.16B.32C.31D.106.假定一棵二叉树中，双分支结点数为15,单分支结点数为30,则叶子结点数为（）0A.15B.16C.17D.477.二叉树第k层上最多有（）个结点。A.2kB.2k-lC.2k-lD.2k-l8.在一棵度具有5层的满二叉树中结点总数为A.31B.32()oC.33D.169.在一棵二叉树上，第5层的结点数最多为（A.8B.15)oC.16D.3210.具有127个结点的完全二叉树其深度为（A.8B.7)oC.6D.511.设一棵二叉树中没有度为1的结点，

41、已知叶子结点数为n,此树的结点数为()oA. 2n+2B. 2n+lC. 2nD. 2n-l12 .设二叉树中有n2个度为2的结点，nl个度为1的结点，n个叶子结点，则此二叉树中空指针域个数为（）oA.O+nl+n2B.n2+nl+2nC.2n2+nlD.2nO+nl13 .n个结点的二叉树中，用二叉链表做存储，非空指针数目为（）oA.nB.2nC.n-1D.n+114 .在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）0A.0B.1C.2D.-115 .在一非空二叉树的中序遍历序列中，根结点的右边（）0A,只有右子树上的所有结点B.只有右子树上的部分结点C,只有左子树上的所有结点D.只有左子树上的部分结点16 .如图所示二叉树的中序遍历序列是（）oA.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh17 .设n、m为一棵二叉树上的两个结点，中序遍历时n在m前的条件是（）。A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙18 .某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定（）0A.空或