数据结构复习题23571

1、第一章 绪论一、 选择题1、数据结构被形式定义为（D，S），其中D是（ B ）的有限集合，S是D上的（ H ）有限集合。A、 算法 B、数据元素 C、数据操作 D、逻辑关系 E、操作 F、映象 G、存储 H、关系2、数据结构是一门研究非数值计算的程序设计问题中计算机的（ （A1） ）以及它们之间的（ B ）和运算的学科。（1）A、操作对象 B、计算方法 C、逻辑存储 D、数据映象（2）A、结构 B、关系 C、运算 D、算法3、算法分析的目的是（ D ），算法分析的二个主要方面是（ C ）。A、给出数据结构的合理性 B、研究算法中输入输出的关系C、空间复杂性和时间复杂性 D、分析算法的效率以求改

2、进E、正确性和简明性 F、分析算法的易懂性和文档性4、在数据结构中，从逻辑上可以把数据结构分成（ C ）。A、 动态和静态结构 B、紧凑接和非紧凑结构C、线性与非线性结构 D、内部结构和外部结构5、计算机算法指的是（ C ），它必具备输入、输出和（ E ）5个特性。A、计算方法 B、排序方法 C、解决问题的有限运算序列 D、可行性、可移植性和可扩充性 E、可行性、确定性和有穷性6、线性表的顺序存储结构是一种（ A ）的存储结构，线性表的链式存储结构是一种（ B ）A、随机存取 B、顺序存取 C、索引存取 D、散列存取7、算法的时间复杂度取决于（ A ）A、 问题的规模 B、待处理数据的初态 C

3、、问题的规模和待处理数据的初态8、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ D ）A、必须是连续的 B、部分地址必须是连续的C、一定是不连续的 D、连续不连续都可以9、在以下的叙述中，正确的是（ B ）A、线性表的线性存储结构优于链式存储结构B、二维数组是它的每个数据元素为一个线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出10、根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是 ( A )A、集合中任何两个结点之间都有逻辑关系但组织形式松散B、线性结构中结点按逻辑关系依次排列形成一条锁链C、树形结构具有分

4、支、层次特性，其形态有点像自然界中的树D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11、以下说法正确的是( D )A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合二、 填空题1、数据逻辑结构包括（ 线性、树型和图型，非线性 ）四种类型，树型和图型结构合称（ ）。2、对于给定的n个元素，可以构造出的逻辑结构有（ ）、（ ）、（ ）和（ ）四种。3、算法的五个重要特性是（ ）。4、评价算法的性能从利用计算机资源角度看主要从（ 时间复杂度和空间复杂度 ）方面进行分析。5、线性结构中元素之间存在（

5、一对一 ）关系，树型结构中元素之间存在（ 一对多 ）关系，图型结构中元素之间存在（ 多对多 ）关系。6、下面程序段的时间复杂度是（ O(n) ）。i=s=0; while(sn) i+;s+;7、下面程序段的时间复杂度是（ O(m*n) ）。s=0; for(I=0;In;I+) for(j=0;jnext=NULL C、head-next=head D、head!=NULL6、不带头结点的单链表head为空的判定条件是（ A ）。 A、head=NULL B、head-next=NULL C、head-next=head D、head!=NULL7、非空的循环单链表head的尾结点P满足（

6、C ）。A、P-NEXT=NULL B、p=NULL C、p-next=head D、p=head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ）。A、O(1) B、O(n) C、O(n2) D、O(nlog2n)9、在一个单链表中，若删除P所指结点的后继结点，则执行（A）。、p-next=p-next-next 、p=p-next;p-next=p-next-next 、p-next=p-next; 、p=p-next-next; 10、在一个单链表中，若在所指结点之后插入所指结点，则执行（B）。、s-next=p;p-next=s; 、s-next=p-

7、next;p-next=s; 、s-next=p-next;p=s; 、p-next=s;s-next=p;11、在一个单链表中，已知q是p的前趋结点，若q和p之间插入结点s，则执行（C）。、s-next=p-next;p-next=s; 、p-next=s-next;s-next=p; 、q-next=s;s-next=p;、p-next=s;s-next=q;12、假设双链表结点的类型如下：typedef struct linknodeint data;数据域struct linknode *llink;指向前趋结点的指针域struct linknode *rlink;指向后继结点的指针域

8、bnode现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（C）。、q-rlink=p;q-llink=p-llink;p-llink=q;p-llink-rlink=q;、p-llink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llink、q-llink=p-rlink;q-rlink=p;p-llink-rlink=q;p-llink=q;、以上都不对、如上题结点结构，如在此非空循环双向链表的结点p之后插入结点s的操作序列是（D）。、p-rlink=s;s-llink=p;p-rlink-llink

9、=s;s-rlink=p-rlink;、p-rlink-s;p-rlink-llink=s;s-llink=p;s-rlink=p-rlink;、s-llink=p;s-rlink=p-rlink;p-rlink=s;p-rlink-llink=s;、s-llink=p;s-rlink=p-rlink;p-rlink-llink=s;p-rlink=s;14、在一个长度为n的单链表上，设有头和尾两个指针，执行（ACD）操作与链表的长度无关。、删除单链表中的第一个元素、删除单链表中最后一个元素、在单链表第一个元素前插入一个新元素、在单链表最后一个元素后插入一个新元素15、线性结构中的一个结点代表

10、一个（ A ）A、数据元素 B、数据项 C、数据 D、数据结构16、非空线性表L=(a1,a2,ai,an)，下列说法正确的是（ D ）A、每个元素都有一个直接前驱和直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小的D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继17、顺序表是线性表的（ B ）A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构18、对于顺序表，以下说法错误的是（ A ）A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B、顺序表的所有存储结点按相应数据元素间的逻辑关系

11、决定的次序依次排列C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中19、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ B ）为标准操作。A、插入操作 B、结点移动 C、算术表达式 D、删除操作20、对于顺序表的优缺点，以下说法错误的是（ C ）A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删除运算较方便D、由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)21、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ A ）存储方

12、式最节省时间。A、顺序表 B、单链表 C、双链表 D、单循环链表22、循环链表主要优点是（ D ）A、不再需要头指针了B、已知某个结点的位置后，能够容易找到它的直接前趋C、在进行插入、删除运算时，能更好地保证链表不断开D、从表中任一结点出发都能扫描到整个链表23、在线性表的下列存储结构中，读取元素花费时间最少的是（ D ）A、单链表 B、双链表 C、循环链表 D、顺序表二、填空题、在线性结构中，第一个结点（无）前趋结点，其余每个结点有且只有（一）个前趋结点。、在顺序表中插入或删除一个元素，需要平均移动（一半）元素，具体移动的元素个数与（该元素的位置）有关。、已知是无表头结点的单链表，试从下列提

13、供的答案中选择合适的语句序列，分别实现：（）表首插入结点的语句序列是（）。（）表尾插入结点的语句序列是（）。、-next=S; 、P=L; 、L=S; 、P-next=S-next; 、S-next=P-next; 、S-next=L; 、S-next=NULL; 、while(P-next!=Q)p=p-next; 、while(P-next!=NULL)P=P-next;4、已知L是带表头结点的非空单链表，试从下列提供的答案中选择合适的语句序列。（1）删除首元结点的语句序列是（ ） ,（2）删除尾元结点的语句序列是（ ）A、P=P-next; B、P-next=P-next-next; C

14、、while(P!=NULL)p=p-next; D、while(Q-next!=NULL)P=Q;Q=Q-next; E、while(P-next!=Q)P=P-next;F、Q=P; G、Q=P-next; H、P=L; I、L=L-next; J、free(Q);5、已知L是带表头结点的非空链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 （1）删除P结点的直接后继结点的语句序列是（ ）, （2）删除P结点的直接前趋结点的语句序列是（ ）A、P-next=P-next-next; B、P=P-Pnext-next; C、while(P-next!=Q

15、)P=P-next;D、while(P-next-next=Q)P=P-next; E、Q=P; F、Q=P-next; G、P=L;H、L=L-next; I、free(Q);6、已知结点编号，在各结点查找概率相等的情况下，从n个结点的单链表中查找一个结点，平均要访问（ 2/n ）个结点，从n个结点的双链表中查找一个结点，平均要访问（ 4/n ）个结点。7、对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是（ O(1 ) ）；在值域为给定值的结点后插入一个新结点的时间复杂度是（ O(n) ）。1、 8、单链表是（ 线性表 ）的链接存储表示。2、 9、单链表中设置头结

16、点的作用是（ 插入和删除首元素时不必进行特殊处理 ）。10、在单链表中，除首元结点外，任一结点的存储位置由（ ）指示。11、在非空双向循环链表中，在结点q的前面插入结点p的过程如下： p-prior=q-prior; q-prior-next=p;p-next=q;( );12、在双向链表中，每个结点有两个指针域，一个指向（ ），另一个指向（ ）。13、顺序表中逻辑上相邻的元素的物理位置（ ）相邻。单链表中逻辑上相邻的元素的物理位置（ ）相邻。 14、为了便于讨论，有时将含n(n0)个结点的线性结构表示成(a1，a2,an)，其中每个ai代表一个_。a1称为_结点，an称为_结点，i称为ai在

17、线性表中的_。对任意一对相邻结点ai、ai1(1in),ai称为ai1的直接_，ai1称为ai的直接_。15、线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接_前趋_外，其他结点有且仅有一个直接_前驱、_；除终端结点没有直接_后继、_外，其它结点有且仅有一个直接_后继_.16、所有结点按1对1的邻接关系构成的整体就是_线性_结构。17、线性表的逻辑结构是_线性_结构。其所含结点的个数称为线性表的_长度_。18、在单链表中，指针p所指结点为最后一个结点的条件是_ pnext=NULL _。三、判断题1. 顺序存储的线性表可以随机存取。T2. 顺序存储的线性表的插入和删除操作不需要付

18、出很大的代价，因为平均每次操作只有近一半的元素需要移动。F3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。T4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。F5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。T6. 在单链表中，可以从头结点进行查找任何一个元素。T7. 线性表的链式存储结构优于顺序存储结构。F8. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。T9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。F10

19、. 顺序存储方式只能用于存储线性结构。F第三章栈与队列 练习题一、 选择题1、栈结构通常采用的两种存储结构是（ A ）。A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构2、设栈ST用顺序存储结构表示，则栈ST为空的条件是（ B ）A、ST.top-ST.base0 B、ST.top-ST.base=0 C、ST.top-ST.basen D、ST.top-ST.base=n3、向一个栈顶指针为HS的链栈中插入一个s结点时，则执行（ C ）A、HS-next=s; B、s-next=HS-next;HS-next=s; C、s-next

20、=HS;HS=s; D、s-next=HS;HS=HS-next;4、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删除结点的值，则执行（ C ）A、x=HS;HS=HS-next; B、HS=HS-next;x=HS-data; C、x=HS-data;HS=HS-next; D、s-next=Hs;Hs=HS-next;5、表达式a*(b+c)-d的后缀表达式为（ B ）A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd6、中缀表达式A-（B+C/D）*E的后缀形式是（ D ）A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABC

21、D/+E*-7、一个队列的入列序列是1，2，3，4， 则队列的输出序列是（ B ）A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，18、循环队列SQ采用数组空间SQ.base0,n-1存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为空的条件是（ C ）A、Q.rear-Q.front=n B、Q.rear-Q.front-1=n C、Q.front=Q.rear D、Q.front=Q.rear+19、循环队列SQ采用数组空间SQ.base0,n-1存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为满的条件是（ C

22、）A、Q.front=Q.rear B、Q.front!=Q.rear C、Q.front=(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n10、若在一个大小为6的数组上实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ A ）A、1，5 B、2, 4 C、4，2 D、5，111、用单链表表示的链式队列的队头在链表的（ A ）位置A、链头 B、链尾 C、链中12、判定一个链队列Q（最多元素为n个）为空的条件是（ A ）A、Q.front=Q.rear B、Q.front!=Q.rear C

23、、Q.front=(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n13、在链队列Q中，插入s所指结点需顺序执行的指令是（ B ）A、Q.front-next=s;f=s; B、Q.rear-next=s;Q.rear=s; C、s-next=Q.rear;Q.rear=s; D、s-next=Q.front;Q.front=s;14、在一个链队列Q中，删除一个结点需要执行的指令是（ C ）A、Q.rear=Q.front-next; B、Q.rear-next=Q.rear-next-next; C、Q.front-next=Q.front-next-next; D、Q

24、.front=Q.rear-next;15、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ D ）A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。16、栈和队列的共同点是（ C ）A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点17、消除递归（ B ）需要使用栈。A、一定 B、不一定18、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（ B ）A、2 B、 3 C、 5

25、 D、 6 19、若一个栈的输入序列是a,b,c，则通过入、出栈操作可能得到a,b,c的不同排列个数为（ B ）A、 4 B、 5 C、 6 D、 7 20、设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（ A ）0 maxsize-1A、a3,a1,a4,a2 B、 a3,a2,a4,a1 C、 a3,a4,a2,a1 D、 a4,a3,a2,a1 a1a2Topa3 图3.121、链栈和顺序栈相比，有一个比较明显的优势是（ A ）A、通常不会出现栈满的情况 B、 通常不会出现栈空的情况 C、 插入操作更容易实现 D、 删除操作更加容易实现22、若

26、一个栈的输入序列是1,2,3,4,n，输出序列的第一个元素是n，则第i个输出元素是（ C ）A、不确定 B、 n-i C、 n-i+1 D、n-i-123、以下说法正确的是( A )A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。二、 判断题1、 在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。T2、 链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。F

27、3、 若一个栈的输入序列为1，2，3，n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=i+1(i=1,2, ,n)。F4、 在链队列中，即使不设置尾指针也能进行入队操作。T5、 在对链队列（带头指针）做出队操作时，不会改变front指针的值。F6、 循环队列中元素个数为rear-front。F7、 一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2。F8、 一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。T9、 若以链表作为栈的存储结构，则进栈需要判断栈是否满。F10、 若以链表作为栈的存储结构，则出栈需要判断栈是否空

28、。T三、 填空题1、栈的特点是（先进后出 ），队列的特点是（ 先进先出 ）。2、线性表、栈、队列都是（线性）结构，可以在线性表的（任何 ）位置插入和删除元素；对于栈只能在（栈顶 ）插入和删除元素；对于队列只能在（队尾 ）插入元素和在（队首 ）位置删除元素。3、有程序如下，则此程序的输出结果（栈的元素类型是SelemType为char）是（ ）。Void main() stack s; char x,y; initstack (s); x=c;y=k;push(s,x);push(s,a);push(s,y);pop(s,x);push(s,t);push(s,x);pop(s,x);push(

29、s,s);while(!stackempty(s)pop(s,y);printf(y);printf(x);4、在栈顶指针为HS的链栈中，判定栈空的条件是（ HS=NULL ）。5、向栈中压入元素的操作是先（ 存入元素， ）后（ 移动栈顶指针 ）。6、对栈进行退栈操作是先（ 移动栈顶指针， ）后（ 取出元素 ）。7、用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（ 1 ）和（ n ）；若只设尾指针，则出队和入队的时间复杂度分别是（ 1 ）和（ 1 ）。8、从循环队列中删除一个元素时，其操作是（ 先取出元素，后移动对尾指针 ）。9、在一个循环队列中，队首指针指向队首元

30、素的（ 前一个位置 ）。10、在具有n个单元的循环队列中，队满时共有（ n-1 ）个元素。11、在HQ的链队列中，判断只有一个结点的条件是（ HQ.front=HQ.rear ）。12、设栈S和队列Q的出始状态为空，元素a,b,c,d,e,f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b,d,c,f,e,a 则栈S的容量至少应该是（ ）。13、有程序如下，则此程序的输出结果（队列的元素类型是QSelemType为char）是（ ）。Void main() char x=e,y=c;enqueue(q,h);enqueue(q,r);enqueue(q,y);dequeu

31、e(q,x);enqueue(q,x);degueue(q,x);enqueue(q,a);while(!queueempty(q)dequeue(q,y);printf(y);printf(x);14、有如下递归函数：int dunno(int m)int value;if(m=0)value=3;else value=dunno(m-1)+5;return(value); 执行语句printf(“%dn”,dunno(3);的结果是（ ）。 第五章复习题一、 选择题1、在以下 讲述中，正确的是（ ）。A、线性表的现行存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈

32、的操作方式是先进先出 D、队列的操作方式是先进后出2、若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ ）。A、正确 B、错误3、二维数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A47的起始地址为（ ）。A、SA+141 B、SA+180 C、SA+222 D、SA+2254、数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（ ）。A、80 B、100 C、2

33、40 D、2705、常对数组进行的两种基本操作是（ ）。A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引6、将一个A1515的下三角矩阵（第一个元素为A11），按行优先存入一维数组B120中，A中元素A65在B数组中的位置K为（ ）。A、19 B、26 C、21 D、157、若广义表A满足Head(A)=Tail(A)，则A为（ ）。 A、（） B、（） C、（），（） D、（），（），（）8、广义表（a）,a）的表头是（ ），表尾是（ ）。 A、a B、b C、(a) D、(a)9、广义表（a,b）,c,d）的表头是（ ），表尾是（ ）。A、a B、b C、(a,b) D、(c

34、,d)10、广义表（a）的表头是（ ），表尾是（ ）。A、a B、(a) C、() D、(a)11、广义表（a,b,c,d）的表头是（ ），表尾是（ ）。A、a B、(a) C、(a,b) D、(b,c,d)12、广义表（a,b,c,d）的表头是（ ），表尾是（ ）。A、a B、() C、(a,b,c,d) D、(a,b,c,d)13、下面结论正确的是（ ）。 A、一个广义表的表头肯定不是一个广义表 B、一个广义表的表尾肯定是一个广义表C、广义表L=（），（A，B）的表头为空表 D、广义表中原子个数即为广义表的长度14、广义表A=（A,B,(C,D),(E,(F,G)），则head(tail(

35、head(tail(tail(A)=( ) A、(G) B、(D) C、C D、 D15、已知广义表L=(x,y,z),a,(u,t,w)，从L表中取出原子项t的操作是（ ）。A、Head(Head(Tail(Tail(L) B、Tail(Head(Head(Tail(L) C、Head(Tail(Head(Tail(L) D、Head(Tail(Head(Tail(Tail(L)16、设A=(a,b,(c,d),(e,(f,g)，则Head(Tail(Head(Tail(Tail(A)=( ) A. (g) B.(d) C.c D.d17、对矩阵压缩存储是为了（ ）A、方便运算 B、节省空间

36、 C、方便存储 D、提高运算速度18、稀疏矩阵一般的压缩存储方法有两种，即（ ） A、二元数组和三元数组 B、三元组和散列 C、三元组和十字链表 D、散列和十字链表二、 判断题1 数组是同类型值的集合。2 数组的存储结构是一组连续的内存单元。3 数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。4 插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。5 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。6 广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。7 线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，

37、则广义表便成为线性表。8 广义表中原子个数即为广义表的长度。9 广义表中元素的个数即为广义表的深度。三、 填空题1、设a是含有N个分量的整数数组，则求该数组中最大整数的递归定义为（ ），最小整数的递归定义为（ ）。2、二维数组A105采用行序为主方式存储，每个元素占4个存储单元，并且A53的存储地址是1000，则A82的地址是（ ）。3、二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是Loc(A00)，则Aij的地址是（ ）。4、广义表的（ ）定义为广义表中括弧的重数。5、设广义表L=（），（），则Head(L)=（ ）；Tail(L)=（ ）；L的长度是

38、（ ）；L的深度是（ ）。6、广义表中的元素可以是（ ），其描述宜采用程序设计语言中的（ ）表示。7、广义表(a)的表头是（ ），表尾是（ ）。8、广义表(a),(b),c),(d)的表头是（ ），表尾是（ ）。9、设广义表A=(x,(a,b),c,d)，则Head(Head(Tail(A)=（ ）。10、设广义表A=(a,b,c),B=(A,(c,d),C=(a,(B,A),(e,f)，则（1）Head(A)=( ) (2) Tail(B)=( ) (3) Head(Head(Head(Tail(C)=( )11、下三角矩阵A1.N,1.N的下三角元素已压缩到一维数组S1.N*（N+1）/2

39、+1中，若按行序为主序存储，则AI,j对应的S中的存储位置是 。12、已知一个稀疏矩阵为 ，则对应的三元组表表示为 。13、一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为 。14、三维数组Ac1.d1,c2.d2.,c3.d3共有 个元素。15、数组A1.10,-2.6,2.8以行优先顺序存储，设基地址为100，每个元素占3个存储单元，则元素A5,0,7的存储地址是 。16、将一个下三角矩阵A1.100,1.100按行优先存入一维数组B1.n中，A中元素A66,65在B数组中的位置为 。第六章：树和二叉树复习题一、 选择题1、 有一“遗传”关系，设x是y的父亲，则x可以把它的属性

40、遗传给y，表示该遗传关系最适合的数据结构是（ B ） A、向量 B、树 C、图 D、二叉树2、树最适合用来表示（ B ）A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据3、树B的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ C ）A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c)4、对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ C ）次序的遍历实现二叉树的结点编号。A、

41、先序 B、中序 C、后序 D、从根开始按层次遍历5、按照二叉树的定义，具有3个结点的二叉树有（ C ）种。A、3 B、4 C、5 D、66、在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则数的最大高度为（E ），其叶结点数为（ G ）；树的最小高度为（ B ），其叶结点数为（G ）；若采用链表存储结构，则有（ I ）个空链域。A、n/2 B、 log2n+1 C、log2n D、n E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1 K、n2 L、n1+17、对一棵满二叉树，m个树叶，n个结点，深度为h，则（ D

42、）A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-18、设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ B ），至多为（ D ）。A、2h B、2h-1 C、2h-1 D、2h-19、在一棵二叉树上第5层的结点数最多为（ B ）（假设根结点的层数为1）A、8 B、16 C、15 D、3210、深度为5的二叉树至多有（ C ）个结点。A、16 B、32 C、31 D、1011、一棵有124个叶结点的完全二叉树，最多有（ B ）个结点A、247 B、248 C、249 D、25012、含有129个叶子结点的完全二叉树，最少有（ D ）个结点A、2

43、54 B、255 C、256 D、25713、假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）个。A、15 B、16 C、17 D、4716、用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R1n中，结点Ri若有左子树，则左子树是结点（ B ）。A、R2i+1 B、R2i C、Ri/2 D、R2i-117、在一棵非空二叉树的中序遍历序列中，根结点的右边（ A ）。A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的所有结点 D、只有左子树上的部分结点18、任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序（ A ）。A、不发生改

44、变 B、发生改变 C、不能确定 D、以上都不对19、设n、m为一棵树上的两个结点，在中序遍历时，n在m前的条件是（ C ）。A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙20、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前驱为（ D ），后序遍历中结点B的直接后继是（ E ）。A、B B、D C、A D、I E、F F、C21、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ D ）。A、acbed B、decab C、deabc D、cedba22、若二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（ C ）遍历方法最合适。A、前序 B、中序 C、后序 D、层次23、线索二叉树是一种（ C ）结构。A、逻辑 B、逻辑和存储 C、物理 D、线性24、如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的（ A ）。A、前序 B、中序 C、后序 D、层次序25、设T是哈夫曼树，具有5个叶结点，树T的高度最高可以是（ DE ）。A、1 B、2 C、3 D、4 E、5 F、626、由带权为8，2，5，7的四个叶子结点构造一棵