数据结构习题及答案（重要）

1、PAGE PAGE 24 第1章 算法一、选择题算法的时间复杂度是指（ ）。A）执行算法程序所需要的时间 B）算法程序中的指令条数C）算法执行过程中所需要的基本运算次数D）算法程序的长度算法的空间复杂度是指（ ）。A）算法程序的长度 B）算法程序所占的存储空间C）算法执行过程中所需要的存储空间 D）算法程序中的指令条数3.下面（ ）的时间复杂度最好（即执行时间最短）。A）O(n ) B）O() C）O(n ) D）O(n2)4.下面累加求和程序段的时间复杂度为（ ）。int sum(int a,int n) int i, s=0;for (i=0;in;i+) s+=ai;return s;

2、A）O(1 ) B）O( ) C）O(n ) D）O(n2)5.下面是将两个n阶矩阵a与b相加的结果存放到n阶矩阵c中的算法，该算法的时间复杂度为（ ）。void matrixadd(int a,int b,c,int n) int i,j; for (i=0;in;i+)for(j=0;jn;j+) cij=aij+bij;A）O(1 ) B）O() C）O( n ) D）O(n2)6.下面程序段的时间复杂度为（ ）。int i=0,s1=0,s2=0;while(in) if(i%2) s1+=i; else s2+=i; i+; A）O(1 ) B）O( ) C）O(n ) D）O(n2

3、)7.下面程序段的时间复杂度为（ ）。int prime(int n) int i=1;int x=(int)sqrt(n);while(ix) return 1;else return 0;A）O(1 ) B）O() C）O(n ) D）O() 8.下面程序段的时间复杂度为（ ）int fun(int n) int i=1,s=1; while(sn) i+;s+=i; return i;A）O(n/2) B）O() C）O(n ) D）O()9.下面程序段的时间复杂度为（ ）int i,j,m,n,a;for(i=0;im;i+) for(j=0;jn;j+) aij=i*j;A）O(m2

4、) B）O(n2 ) C）O(m*n ) D）O(m+n)10. 下面程序段的时间复杂度为（ ）int sum1(int n) int i,p=1,s=0; for(i=1;i=n;i+) p*=i; s=s+p; return s;A）O(1 ) B）O() C）O(n ) D）O(n2)二、填空题1.算法复杂度主要包括时间复杂度和 复杂度。2.一个算法的时间复杂度的计算式为 ( 3n2+2n+5 ) / n ，其数量级表示为 。3.从一维数组an中顺序查找出一个最大值元素的平均时间复杂度为 ，读取一个二维数组bmn中任一元素的时间复杂度为 。4.在下面程序段中，s = s+p语句的执行次数

5、为 ，p*=j 语句的执行次数为 ，该程序段的时间复杂度为 。int i=0, s=o; while(+i =n) int p=1; for(int j=1; j a2、a1 = a2、a1”、“=”、“”字符。2.求一维double型数组an中的所有元素之乘积。3.假定一维整型数组an中的每个元素值x均在0，200区间内，分别统计出落在0 x 20、20 x50、50 x80、80 x130、13 x200各区间内的元素个数。第2章 数据结构的基本概念单选题1.一个数据结构可形象地表示成B=(D,R)，其中D是（）的有限集合，R是D上的（）有限集合。 A）算法 B）数据元素 C）数据操作 D

6、）逻辑结构 A）操作 B）映像 C）存储 D）关系2. 数据结构在计算机存储空间中的存放形式称为（ ）。A）数据元素之间的关系 B）数据结构C）数据的存储结构 D）数据的逻辑结构3. 下列叙述中正确的是（ ）。A）一个逻辑结构只能有一种存储结构B）数据逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑结构可以有多种存储结构，且各种存储结构影响数据处理的效率4. 在数据结构中，与所使用的计算机无关的是数据的（ ）结构。A）逻辑 B）存储 C）逻辑和存储 D）物理5. 在存储数据时，通常不仅需要存储各数据元素的值，而且还要

7、存储（ ）。A）数据的处理方法 B）数据元素的类型 C）数据元素之间的关系 D）数据的存储方法6. 如果一个非空的数据结构满足两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为（ ）。A）线性结构 B）非线性结构 C）物理结构 D）逻辑结构7. 数据的（ ）包括插入、删除、查找、更新、排序等操作类型。A）存储结构 B）逻辑结构C）基本运算 D）算法描述8. 数据的存储结构是指（ ）。A）数据所占的存储空间 B）数据的逻辑结构在计算机中的表示C）存储在外存中的数据 D）数据在计算机中的顺序存储方式9. 在决定选取何种存储结构时，一般不考虑（ ）。A）结点个

8、数的多少 B）各结点的值如何C）对数据有哪些运算 D）所用编程语言实现这种结构是否方便10.以下说法正确的是（ ）。A）数据元素是数据的最小单位 B）数据项是数据的基本单位C）数据结构是带结构的各数据项的集合D）一些表面上很不相同的数据，可以有相同的逻辑结构11.在数据结构中，从逻辑上可以把数据结构分成（ ）。A）动态结构和静态结构 B）紧凑结构和非紧凑结构C）线性结构和非线性结构 D）内部结构和外部结构12.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。A）数据元素具有同一特点 B）不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C）每个数据元素都一

9、样D）数据元素所包含的数据项的个数要相等二、填空题1.数据的基本单位是 ，数据的最小单位是 。2. 一种数据的逻辑结构，根据需要可以表示成顺序、 、 和散列四种基本存储结构。3. 根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据分为 两大类型。4. 在一个线性结构中插入或删除任何一个结点后还应是 。5.一种数据结构的元素集合为D，它在D上的二元关系R为：D=a,b,c,d,e,f,g,hR=,则该数据结构具有 结构。6.一种数据结构的元素集合为D，它在D上的二元关系R为：D=a,b,c,d,e,f,g,hR=,则该数据结构具有 结构。7.数据的逻辑结构分为线性结构和非线性结构，其中的

10、非线性结构有 两种基本类型。简答题数据结构主要研究的三个问题是什么？一个数据结构应包含两方面的信息是什么？简述数据存储结构中的顺序存储方式。简述数据存储结构中的链式存储方式第3章 线性表及其存储结构单选题1. 在一个长度为n的顺序存储的线性表中，向第i个元素（1 i n+1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。A）n-i B）ni+1 C）ni-1 D）i2. 在一个长度为n的顺序存储的线性表中，删除第i个元素（1 i n+1）时，需要从前向后依次前移（ ）个元素。A）n-i B）ni+1 C）ni-1 D）i3. 在一个长度为n的顺序表中，存在值为x的元素。在此表中用顺序

11、搜索法，查找值为x的元素，在等概率情况下，查找成功时的平均查找长度为（ ）。A）n B）n/2 C）(n+1)/2 D）(n - 1)/24. 在一个长度为n的顺序表中，删除值为x的元素时，需要比较元素的次数和移动元素次数的和为（ ）。A）n/2 B）(n+1)/2 C）n D）n+15. 在一个顺序表的表尾，插入一个元素时的时间复杂度为（ ）。A）O(1) B）O() C）O(n) D）O(n2)6. 在一个顺序表的任意位置，插入一个元素的时间复杂度为（ ）。A）O(1) B）O() C）O(n) D）O(n/2)7. 线性表的顺序存储比链式存储最有利于进行（ ）操作。A）查找 B）表尾插入

12、或删除C）按值插入或删除 D）表头插入或删除8. 线性表的链式存储比顺序存储最有利于进行（ ）操作。A）查找 B）表尾插入或删除C）按值插入或删除 D）表头插入或删除9. 在一个单链表中，若要在pre所指向的结点之后插入一个新结点，则相继修改（ ）个指针域的值。A）2 B）1 C）3 D）410. 在带表头结点的单链表中，插入一个新结点所用算法的时间复杂度为（ ）。A）O(1) B）O() C）O(n) D）O(n/2)11.以下关于线性表的链式存储结构的叙述中，正确的是（ ）。A）存储密度大B）逻辑上相邻的结点物理上不必相邻C）可以通过计算直接确定第i个结点的存储地址D）插入、删除运算操作不

13、方便12.带头结点的单链表H为空的判定条件是（ ）。A）H=NULL B）H-next=NULLC）H-next=H D）H!=NULL13.不带头结点的单链表H为空的判定条件是（ ）。A）H=NULL B）H-next=NULLC）H-next=H D）H!=NULL14.在一个带头结点的单链表H中，若要向表头插入一个由指针p指向的新结点，则应执行的操作是（ ）A）H=p;p-next=H; B）p-next=H;H=p;C）p-next=H;p=H; D）p-next=H-next; H-next=p;15.非空的循环单链表H的尾结点（由p所指向）满足（ ）。A）p=NULL B）p-ne

14、xt=NULLC）p-next=H D）p=H16.链表不具备的特点是（ ）。A）插入删除不需要移动元素 B）可随机地访问任一结点C）不必事先估计存储空间 D）所需空间与其长度成正比17.设线性表有n个元素，以下算法中，（ ）在顺序表上实现比在链表上实现的效率更高。A）输出第i（0in-1）个元素B）交换第0个元素与第1个元素的值C）顺序输出这n个元素的值D）输出与给定值x相等的元素在线性表中的序号18.设线性表中有2n个元素，以下算法中，（ ）在单链表上实现要比在顺序表上实现效率更高。A）删除所有值为X 的元素B）在最后一个元素的后面插入一个新元素C）顺序输出前k个元素D）交换第i个元素和第

15、2ni-1个元素的值（i = 0，1，n-1）二、填空题1. 在线性表中，第一个结点 前件，其余每个结点有且只有 个前件；最后一个结点 后件，其余每个结点有且只有 个后件。2. 数据元素在线性表中的位置只取决于它们自己的 。 3. 线性表中结点的个数 n 称为线性表的 。当 n=0时，称为 。4. 用一维数组存放线性表时，数组的基本类型要与线性表中数据元素的类型 。5. 线性表的顺序存储结构存在插入、删除操作时需 数据元素的缺点。6. 线性表的两种存储结构分别是 和 。7. 线性表的顺序存储结构称为 ；线性表的链式存储结构称为 。8. 对线性单链表进行插入操作时，没有发生数据元素的 ，只是改变

16、了有关结点的 。 9. 在线性单链表中删除一个元素后，不需要 表中的数据元素，只需改变被删除元素所在结点的 的指针域即可。10. 在带表头结点的单链表中，查找第i个结点。只能从单链表的 ，沿着结点的 ，直到搜索到第i个结点为止。11. 在单链表中，若一个元素所在结点的地址为p，则其后继（件）结点的地址为 。12. 在单链表中，删除指针p所指向结点的后继结点时，需要把 的值赋给p-next指针域。 13. 在单链表中指针p所指结点的后面，插入一个指针q所指的结点时，首先把 的值赋给q-next，然后把 的值赋给p-next。14. 在一个带表头结点的单链表的表头插入或删除，与在其他位置插入或删除

17、的操作过程是否相同？ 。15. 在一个不带表头结点的单链表的表头插入或删除，与在其他位置插入或删除的操作过程是否相同？ 。 16. 在双向链表中的每一个结点，包含有两个指针域，一个指向 结点，另一个指向其 结点。17. 在一个双向链表中，通过一个结点的prior 和 next指针域，能够分别访问到该结点的 和 结点。 18.由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的 。三、简答题非空线性表的结构特征是什么？2线性表的顺序存储结构具有哪两个基本特点？3. 用一维数组存放线性表时，应注意什么？4. 简述线性表顺序存储的优点和缺点。5.

18、 什么是线性表的链式存储结构？6. 在带头结点的单链表中与在顺序表中，查找与给定元素值item相等的结点的操作有何不同？7. 带表头结点的循环链表与前面所讨论的单链表相比具有哪两个特点？四、算法设计1. 分别编写在顺序表和链表中统计出值为x的元素个数的函数，统计结果由函数值返回。2. 分别编写在顺序表和带表头结点的单链表中删除其值等于x的所有元素的函数。3. 编写在单链表中删除具有重复值的多余结点，使每个结点的值均不同的函数。第4章 栈和队列一、单选题1.下列叙述中正确的是（ ）。A）线性表是线性结构 B）栈与队列是非线性结构C）线性链表是非线性结构 D）树是线性结构2.下列关于栈的叙述中正确

19、的是（ ）。A）在栈中只能插入数据 B）在栈中只能删除数据C）栈是先进先出的线性表 D）栈是先进后出的线性表3.栈的插入和删除操作在（ ）进行。A）栈顶 B）栈底 C）任意位置 D）指定位置4.当利用大小为N的一维数组，顺序存储一个栈时，用top表示栈顶指针（指示器），用top=N表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。A）top+; B）top-; C）top=0; D）top=N-1;5. 利用数组aN顺序存储一个栈时，用top表示栈顶元素的下标位置，用top=-1表示栈空，用top=N-1表示栈满，则该数组所能存储栈的最大长度为（ ）。A）N-1 B）N

20、C）N+1 D）N+2 6. 利用数组aN顺序存储一个栈时，用top表示栈顶指针，用top=N+1表示栈空，则该数组所能存储栈的最大长度为为N，则表示栈满的条件为（ ）。A）top=1; B）top=-1;C）top=0; D）top1;7. 利用数组aN顺序存储一个栈时，用top表示栈顶指针，用top=-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作是（ ）。A）a-top=x; B）atop-=x; C）a+top=x; D）atop+=x;8. 利用数组aN顺序存储一个栈时，用top表示栈顶指针，用top=-1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作是（ ）。A）

21、return a-top; B）return atop-; C）return a+top; D）return atop+;9. 假定一个链栈的栈顶指针用top表示，则该链栈为空的条件是（ ）。A）top!=NULL; B）top=top-next;C）top=NULL; D）top!=top-next;10.假定一个链栈的栈顶指针用top表示，每个结点的结构由一个数据域data和一个指针域组成，当p指向的结点进栈时，执行的操作为（ ）。A）p-next=top;top=top-next; B）top=p;p-next=top;C）p-next=top-next;top-next=p; D）p-

22、next=top;top=p;11.假定一个链栈的栈顶指针用top表示，每个结点的结构由一个数据域data和一个指针域组成，退栈时所执行的指针操作为（ ）。A）p-next=top; B）top=top-data;C）top=top-next; D）top-next=top-next-next;12.若让元素1，2，3依次进栈，则出栈次数不可能出现（ ）的情况。A）3，2，1 B）2，1，3 C）3，1，2 D）1，3，213.若让元素1，2，3，4依次进栈，则出栈次序不可能出现（ ）的情况。A）3，2，1，4 B）2，1，4，3 C）4，3，2，1 D）1，4，2，314.下列关于队列的叙述

23、中正确的是（ ）。A）在队列中只能插入数据 B）在队列中只能删除数据C）对列是先进先出的线性表 D）队列是先进后出的线性表15.在一个顺序循环队列中，队头指针指向队头元素的（ ）位置。A）前一个 B）后一个 C）当前 D）最后16. 在一个顺序循环队列中，队尾指针指向队尾元素的（ ）位置。A）前一个 B）后一个 C）当前 D）最后17.从一个顺序循环队列中删除元素时，首先需要( )。A）前移队头指针 B）取出队尾指针所指位置上的元素C）后移队头指针 D）取出队头指针所指位置上的元素18.假设一个顺序循环队列的队头指针和队尾指针分别用front和rear表示，则判别队空的条件为（ ）。A）fro

24、nt+1=rear B）rear+1=frontC）front=0 D）front=rear19.假设一个顺序循环队列存储于数组aN中，其队头指针和队尾指针分别用front和rear表示，则判断队列满的条件为（ ）。A）(rear-1)%N=front B）(rear+1)%N=frontC）(front-1)%N=rear D）(front+1)%N=rear20. 假设一个顺序循环队列存储于数组aN中，其队头指针和队尾指针分别用front和rear表示，已知队列未满，当元素x入队时所执行的操作为（ ）。A）a+rear%N=x; B）ar+%N=x;C）a-rear%N=x; D）area

25、r-%N=x;21. 假设一个顺序循环队列存储于数组aN中，其队头指针和队尾指针分别用front和rear表示，已知队列未满，当出队并返回队头元素时所执行的操作为（ ）。A）return a+rear%N; B）return a-rear%N;C）return a+front%N; D）return afront+%N;22.假设一个链接队列的队头指针和队尾指针分别为front和rear，则判别队列空的条件为（ ）。A）front=rear B）front!=NULLC）rear!=NULL D）front=NULL23. 假设一个链接队列的队头指针和队尾指针分别为front和rear，每个结

26、点由一个数值域data和一个指针域next构成，当出队时，所进行的指针操作为（ ）。A）front=front-next; B）front-next=rear;rear=rear-next;C）rear=rear-next; D）front=front-next;front-next=rear;24.以下哪一个不是队列的基本运算（ ）。A）从队尾插入一个新元素 B）从队列中删除第i个元素C）判断一个队列是否为空 D）读取队头元素的值25.栈和队列的共同特点是（ ）。A）都是先进先出 B）都是先进后出C）都只允许在端点处插入和删除元素 D）没有共同点26.一个队列的入队序列是1，2，3，4，在队

27、列的出队序列是（ ）。A）4，3，2，1 B）1，2，3，4 C）1，4，3，2 D）3，2，4，127.下列叙述中，（ ）与在循环顺序队列中插入下一个元素有关。A）与队头指针和队尾指针的值有关B）只与队尾指针的值有关，与队头指针的值无关C）只与队头指针的值有关，与队尾指针的值无关D）与曾经进行过多少次插入操作有关二、填空题1. 在栈中，允许插入与删除的一端称为 ，而不允许插入与删除的另一端称为 。2. 往栈中插入一个元素称为 运算。从栈中删除一个元素（即删除栈顶元素）称为 运算。 3.栈又称为 表，队列又称为 表。 4.在一个用一维数组aMax表示的顺序栈中，该栈所含元素的个数最少为 个，最

28、多为 个。5.向一个顺序栈插入一个元素时，首先使 后移一个位置，然后把新元素 到这个位置上。6.从一个顺序栈删除元素时，首先取出 ，然后再使 减1。7.队列的插入操作在 进行，删除操作在 进行。8.一个顺序循环队列存于一维数组aMax中，假设队头指针和队尾指针分别为front和rear，则判断队空的条件为 ，判断队满的条件为 。9. 一个顺序循环队列存于一维数组aMax中，假设队头指针和队尾指针分别为front和rear，则求出队头指针和队尾指针的下一个位置的计算公式分别为 和 。10. 一个顺序栈存储于一维数组a 0.N-1 中，栈顶指针用top表示，当栈顶指针等于 时，则为空栈，栈顶指针等

29、于 时，则为满栈。11.在一个链栈中，若栈顶指针等于NULL，则为 ；在一个链队列中，若队头指针与队尾指针的值相同，则表示该队列为 或该队 。12.假设一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当p所指向的结点入栈时，则首先执行 操作，然后执行 操作。13. 假设一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当进行出栈运算时（栈非空），则要把栈顶指针top修改为 的值。14.向一个顺序循环队列中插入元素时，需要首先移动 ，然后再向它所指的位置 新元素。15.在一个空链队列中，假定队头指针和队尾指针分别为front和rear，当向其插入一个新结

30、点*p时，则首先执行 操作，然后执行 操作。16.假设front和rear分别为一个链队列的队头指针和队尾指针，则该链队列中只有一个结点的条件为 。 17.在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有 个元素。三、简答题1. 什么是栈？栈组织数据的原则是什么？ 2. 什么是顺序栈和链式栈？3. 简述在顺序栈的栈顶插入一个元素的操作过程。4. 简述在链栈中插入一个元素的操作过程。5. 在循环队列中，仅依据头尾指针相等，无法判断队列是“空”还是“满”。要解决这个问题，常用的两种方法是什么？6. 一个栈的输入序列为A、B、C，若输出序列由A、B、C所构

31、成，试给出全部可能的输出序列。四、应用题（写出下面算法的结果）1. void exem1(SeqStack &s) int i,a4=15,24,38,44; InitStack(s); /初始化s栈 Push(s,20); /向s栈压入20 Push(s,36); /向s栈压入36for(i=0;i4;i+) Push(s,ai); /a数组各元素入栈coutPop(s) ; /输出栈顶元素 Push(s,a2-6); While(!StackEmpty(s) CoutPop(s) ; /依次出栈 coutendl;该算法的输出结果为：2. void exam2(LinStack &s) I

32、nitStack(s); /初始化s栈 Push(s,30); /向s栈压入30 Push(s,40); Push(s,50); int x=Pop(s)+2*Pop(s); Push(s,x); int i,a4=5,8,12,15; for(i=0;i4;i+) Push(s,ai); /将数组a各元素入栈 while(!StackEmpty(s) coutPop(s) ; /依次出栈 coutendl;该算法的输出结果为：3. void exam3(SeqQueue &q) InitQueue(q); /初始化队列q int i,a4=5,8,12,15; for(i=0;i4;i+)

33、EnQueue(q,ai); /a数组各元素入队 EnQueue(q,DeQueue(q); /入队元素是出队元素EnQueue(q,30); /30入队EnQueue(q,DeQueue(q)+10);While(!QueueEmpty(q) coutDeQueue(q) ; /依次出队coutendl;该算法的输出结果为：4. void exam4(LinQueue &Lq) InitQueue(Lq); /初始化队列Lq EnQueue(Lq,25); /25入队 int i,a5=34,23,78,56,19; for(i=0;i5;i+) EnQueue(Lq,ai); /数组a各元

34、素入队 DeQueue(Lq); /进行一次出队运算 EnQueue(Lq,DeQueue(Lq); /入队元素是出队元素While(!QueueEmpty(Lq) CoutDeQueue(Lq) ; /输出队列中的元素Cout1）的结点，其双亲结点的编号为（ ）。A）(i+1)/2 B）(i - 1)/2 C）i/2 D）i/2 17. 在深度为5的满二叉树中，叶子结点的个数为（ ）。A）15 B）16 C）32 D）3118. 对一棵满二叉树，有m个树叶，n个结点，深度为h，则有（ ）。A）n=h+m B）m=h - 1 C）n=2h - 1 D）2n=2h+m19. 在一非空二叉树的中序

35、遍历序列中，根结点的右边（ ）。A）只有右子树上的所有结点 B）只有右子树上的部分结点C）只有左子树上的所有结点 D）只有左子树上的部分结点20.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ ）。A）空或只有一个结点 B）完全二叉树C）二叉排序树 D）高度等于其结点数的二叉树21.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ ）。A）发生改变 B）不发生改变 C）不能确定 D）以上都不对22.利用n个值生成的哈夫曼树中共有（ ）结点。A）n B）n+1 C）2n D）2n - 123.利用3，6，8，12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的

36、带权路径长度为（ ）。A）38 B）58 C）29 D）5524.利用3，6，8，12，5，7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（ ）。A）6 B）5 C）4 D）325.依据使用频率，为5个字符设计的哈夫曼编码不可能是（ ）。A）000,001,010,011,1 B）0000,0001,001,01,1C）000,001,01,10,11 D）00,100,101,110,11126. 依据使用频率，为5个字符设计的哈夫曼编码不可能是（ ）。A）111,110,10,01,00 B）000,001,010,011,1C）100,11,10,1,0 D）001,000,

37、01,11,10二、填空题1. 数据的逻辑结构有线性结构和非线性结构之分，树(tree)属于 。2. 树的固有特性为，一棵树是由 的，而子树又可由若干个 构成。3. 一个结点的子树数称为该结点的 。4. 在树中，所有结点中的 称为树的度。5.对于一棵具有n个结点的树，该树中所有结点的度之和为 。6.在一棵树中， 结点没有前件结点，其余每个结点有并且只有一个 结点，可以有任意多个 结点。7. 在树中，结点的子树的根，称为该结点的 ，相应地，该结点称为孩子的 。8. 在树中，各结点的层的最大值，称为树的 。9. 如果树中任一结点的各棵子树规定 是有次序的，即不能互换位置，则称该树为有序树，否则称为

38、无序树。10. n（n0）棵互不相交的树的集合，称为 。11. 依据二叉树的定义，二叉树共有 基本形态。12. 假设一棵完全二叉树的深度为k，由完全二叉树的定义知，它的k - 1层，是深度为 k - 1的 。 13.一棵深度为5的完全二叉树中结点数最少为 个，最多为 个。14.设一棵完全二叉树共有700个结点，则在该二叉树中有 个叶子结点。15.对一棵二叉树，一个结点的编号为i，若它的左孩子结点存在，则其编号为 ；若右孩子结点存在，则其编号为 ；若双亲结点存在，则编号为 。16.在一棵二叉树中，第6层上的结点数最多为 。17.假设一棵二叉树的结点数为18，则它的最小深度为 ，最大深度为 。18

39、.在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0= 。19.一棵二叉树的第i层最多有 个结点；一棵有n (n0)个结点的满二叉树，共有 个叶子结点和 个非叶子结点。（提示：假设有n个结点的满二叉树高度为h，则有n=2h1，即h= ，第h层的结点为叶结点，前h -1层的结点为非叶结点）20.结点最少的树为 ，结点最少的二叉树为 。21. 存储二叉树，通常有 结构和 结构。22.二叉链表是二叉树最常用的存储结构。通过二叉链表结点的 可以立即找到它的左、右孩子，但不能直接找到它的 。23. 遍历一棵二叉树，就是按照某种规则去访问二叉树的每个结点，而且每个结点 。24.在遍历二

40、叉树时，如果限定先左子树后右子树，根据访问根结点的次序，则有3种遍历方法，分别称为 。25. 从树中一个结点到另一个结点之间的 构成这两个结点之间的路径，路径上的 称为路径长度。26.对一棵具有n个结点的二叉树，对应二叉链表中的指针总数为 个，其中 个用于指向孩子结点， 个指针空闲着。 27. 树中所有叶子结点的带权路径长度之和称为树的 。28. 哈夫曼（Huffman）树，又称最优二叉树，是一类 最短的二叉树。29.若由3,6,8,12,10作为叶子结点的值生成一棵哈夫曼树，则该树的高度为 ，带权路径长度为 。30.已知一棵二叉树的先序和中序遍历序列如下：先序遍历序列：A，B，C，D，E，F

41、，G，H，I，J中序遍历序列：C，B，A，E，F，D，I，H，J，G则其后序遍历序列为： 。31.已知一棵二叉树的中序遍历和后序遍历序列如下：中序遍历序列：C，B，D，E，A，G，I，H，J，F后序遍历序列：C，E，D，B，I，J，H，G，F，A则其先序遍历序列为： 。32.已知一棵二叉树的先序和后序遍历序列如下：先序遍历序列：A，B，D，E，C，F后序遍历序列：D，E，B，F，C，A则其中序遍历序列为： 。33.有7个带权结点，其权值分别为3，7，8，2，6，10，14，以它们为叶子，生成一棵哈夫曼树，则带权路径长度为 ，高度为 ，双分支结点数为 。 三、简答题1. 简述树的定义。2. 简述

42、二叉树的定义。3. 简述树与二叉树的主要差别。4. 什么是完全二叉树？5. 简述采用顺序编号的完全二叉树所具有的性质（一般二叉树的性质除外）。6. 简述先序遍历二叉树的递归定义。四、算法设计1.设以二叉链表为二叉树的存储结构，结点的结构如下图所示，其中data为整数。试设计一个算法void change(BiTree r),使当结点的左孩子的值域的值大于右孩子的值域的值时，则交换其左、右子树。lchilddatarchild2.设计一个算法int count(BiTree r,datatype x)，统计出二叉树中大于给定值x的结点个数，该统计值由函数返回。3.设计一个算法void prese

43、rve(BiTree r,datatype a,int n)，对具有n个结点的二叉树进行中序遍历，并把遍历得到的结点值序列保存到数组中。第6章 图一、单项选择题1. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为（ ）。A）s B）s - 1 C）s+1 D）n2. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为（ ）。A）s B）s+1 C）s - 1 D）2s3.在一个具有n个结点的无向图中，若具有e条边，则所有顶点的度数之和为（ ）。A）n B）e C）2e D）n+e 4. 在一个具有n个顶点和e条边的无向图的邻接矩

44、阵中，非零元素的个数为（ ）。A）n B）ne C）e D）2e5. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为（ ）。A）n B）ne C）e D）2e二、填空题1. 在一个无向图中，所有顶点的度数之和等于所有边数的 倍。2. 若一个有向图的顶点集为 a, b, c, d, e, f ，其顶点偶对的集合为 , ，则出度为0的顶点个数为 ，入度为1的顶点个数为 。 3. 在一个具有n个顶点的无向图中，要连通所有顶点，则至少需要 条边。4. 表示图的两种存储结构为 和 。5. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为 。6. 对于一个具有n个顶点和e条边的

45、无向图，在其对应的邻接表中，所含边结点的个数为 。7. 图的深度优先搜索遍历，类似于树的 遍历；图的广度优先搜索遍历，类似与树的 遍历。8. 一个图的顶点偶对集合为 (a,c), (a,e), (b,e), (c,d), (d,e) ，从顶点a出发进行深度优先搜索遍历得到的顶点序列为 ；从顶点a出发进行广度优先搜索遍历得到的顶点序列为 。 第7章 查找与排序一、单项选择题1. 若查找每个元素的概率相等，则在长度为n的顺序表上，查找任一元素的平均查找长度为（ ）。A）n B）n+1 C）(n+1)/2 D）(n-1)/22. 对长度为n的单链有序表，若查找每个元素的概率相等，则查找任一元素的平均

46、查找长度为（ ）。A）n/4 B）(n+1)/2 C）n/2 D）(n-1)/23. 对长度为9的顺序存储的有序表，采用折半法查找，在等概率情况下的平均查找长度为（ ）的值除以9。A）18 B）20 C）25 D）224. 对长度为18的顺序存储的有序表，采用折半法查找，则查找第15个元素的查找长度为（ ）。A）3 B）4 C）5 D）65. 对顺序存储的有序表（5，12，20，26，37，42，46，50，64），采用折半查找，则查找元素26的查找长度为（ ）。A)2 B)3 C)4 D)5 6. 顺序查找法适合于存储结构为（ ）的线性表。A）压缩存储 B）顺序存储或链式存储C）索引存储 D

47、）散列存储7. 对线性表进行折半查找的前提条件是（ ）。A）线性表以顺序方式存储，并且按关键字的查找频率排好序B）线性表以顺序方式存储，并且按关键字的大小排好序C）线性表以链式方式存储，并且按关键字的大小排好序D）线性表以链式方式存储，并且按关键字的查找频率排好序8. 在分块查找中，若用于查找表的长度为n，它被等分为k个子表，每个子表的长度均为n/k，则分块查找的平均查找长度为（ ）。A）n+k B）k+k/n C）(k+k/n)/2+1 D）(k+k/n)/29. 在分块查找中，若用于查找表的长度为n，它被等分为若干个子表，每个子表的长度均为s，则分块查找的平均查找长度为（ ）。A）(n+s

48、)/2 B）(n+s)/2+1 C）(s+n/s)/2+1 D）(s+n/s)/210. 在分块查找中，若用于查找表的长度为144，它被等分为12个子表，每个子表的长度均为12，则分块查找的平均查找长度为（ ）。A）12 B）24 C）13 D）7911. 在分块查找中，若用于查找表的长度为117，它被等分为9个子表，则分块查找的平均查找长度为（ ）。A）11 B）12 C）13 D）912.在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（ ）。A）n B） C）(h+1)/2 D）h13.从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度的为（ ）

49、。A）O(n) B）O(1) C）O() D）O(n2)14.从具有n个结点的二叉排序树中查找一个元素，在最坏情况下的平均查找长度是（ ）。A）n B） C）(n+1)/2 D）(n-1)/215. 若对n个元素进行插入排序，在进行第i遍排序过程前，有序表中的元素个数为（ ）。A）i B）i+1 C）i-1 D）116. 若对n个元素进行插入排序，在进行第i遍排序时，为寻找插入位置，最多需要进行（ ）次元素的比较（假设第0号元素放有待查元素关键字）。A）i B）i-1 C）1 D）i+117. 若对n个元素进行插入排序，在进行第i遍排序时，假设元素ai+1的插入位置为，aj，则需要移动元素的次

50、数为（ ）。A）j-i B）i-j-1 C）i-j D）i-j+118. 对n个元素进行插入排序的过程中，共需要进行（ ）遍。A）n+1 B）n C）2n D）n-119. 对n个元素进行插入排序的时间复杂度为（ ）。A）O(1) B）O(n2) C）O(n) D）O()20. 在对n个元素进行冒泡排序的过程中，第一遍排序，最多需要进行（ ）对相邻元素之间的交换。A）n-1 B）n C）n/2 D）n+121. 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度的为（ ）。A）O(1) B）O(n2) C）O(n) D）O()22. 在对n个元素进行冒泡排序的过程中，最坏情况下的时间复杂

51、度为（ ）。A）O(1) B）O(n2) C）O(n) D）O()23. 在对n个元素进行冒泡排序的过程中，最少需要（ ）遍完成。A）1 B）n C）n-1 D）n/224. 在对n个元素进行快速排序的过程中，第一次划分最多需要移动（ ）次元素，包括开始把基准元素移动到临时变量中的一次。A）n/2 B）n-1 C）n D）n+125. 在对n个元素进行快速排序的过程中，最好情况下需要进行（ ）遍。A）n B）n/2 C） D）2n26. 在对n个元素进行快速排序的过程中，最坏情况下需要进行（ ）遍。A）n B）n/2 C） D）n-127. 在对n个元素进行快速排序的过程中，最好情况下的时间复

52、杂度为（ ）。A）O(1) B）O(n2) C）O(n) D）O()28. 在对n个元素进行快速排序的过程中，最坏情况下的时间复杂度为（ ）。A）O(1) B）O(n2) C）O(n) D）O()29. 对元素序列（3，7，5，9，1）进行快速排序，在进行第一遍划分时，需要移动元素的次数为（ ），假设不包括开始把基准元素移动到临时变量的一次。A）1 B）2 C）3 D）430. 在对下列四个序列进行快速排序时，各以第一个元素为基准进行第一遍划分，则在该次划分过程中，需要移动元素次数最多的序列为（ ）。A）1，3，5，7，9 B）9，7，5，3，1C）5，3，1，7，9 D）5，7，9，1，33

53、1.对元素序列（7，3，5，9，1，12，8，15）进行快速排序，在进行第一遍划分后，得到的左区间中元素的个数为（ ）。A）2 B）3 C）4 D）532. 在对n个元素进行选择排序的过程中，在第i遍，需要从（ ）个元素中选择出最小值元素。A）n-i+1 B）n-i C）i D）i+133. 对n个元素进行选择排序，在进行任一遍排序的过程中，为寻找最小值元素所需要的时间复杂度量级为（ ）。A）O(1) B）O(n2) C）O() D）O(n)34. 若对n个元素进行归并排序，则进行归并的遍数为（ ）。A）n B）n/2 C） D）n-1 35. 对n个元素进行归并排序，在进行每一遍的时间复杂度

54、量级为（ ）。A）O(1) B）O(n2) C）O() D）O(n)36. 若一个元素序列基本有序，则选用（ ）方法较快。A）插入排序 B）选择排序 C）归并排序 D）快速排序37. 在平均情况下，速度最快的排序方法为（ ）。A）选择排序 B）冒泡排序 C）归并排序 D）快速排序38. 排序方法中，从未排序序列中，依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）。A）归并排序 B）冒泡排序 C）插入排序 D）选择排序 39快速排序方法在（ ）情况下，最不利于发挥其长处。A）要排序的数据量太大 B）要排序的数据中含有多个相同值C）要排序的数

55、据已基本有序 D）要排序的数据个数为奇数40. 用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，若元素序列的变化情况如下：1）25，84，21，47，15，27，68，35，202）20，15，21，25，47，27，68，35，843）15，20，21，25，35，27，47，68，844）15，20，21，25，27，35，47，68，84则所采用的排序方法是（ ）。A）选择排序 B）冒泡排序C）归并排序 D）快速排序二. 填空题1. 查找是指在一个给定的数据结构中，查找某个 。2. 在查找算法中，使用关键字这个术语。关键字是指数据元素（或记录）中

56、某个数据项的值，用它可以 一个数据元素（或记录）。3. 顺序查找方法既适用于线性表的 ，也适用于线性表的 。4. 以顺序查找法从长度为n的顺序表中，成功查找一个元素时，平均查找长度为 ，时间复杂度的量级为 。5. 以顺序查找法从长度为n的顺序表中，查找第i个元素的概率为pi，查找长度为ci，则在查找成功情况下的平均查找长度的计算公式为 。6. 顺序查找长度为40的线性表，设查找每个元素的概率都相同，则在查找成功情况下的平均查找长度为 ，在查找不成功情况下的平均查找长度为 。7. 查找要求查找表采用顺序存储结构，且表中记录按关键字大小次序排列。8. 以折半查找法，从长度为50的有序表中查找一个元

57、素时，其查找长度不超过 。9. 从有序表（12，18，30，43，56，78，82，95）中，分别折半查找43和56两个元素时，其查找长度分别为 和 。 10. 折半查找所对应的判定树，是一棵 树 。11. 设长度n=50的有序表进行折半查找，在对应的判定树高度为 ，最后一层的结点数为 。12. 折半查找中，每进行一次，或者查找成功，或者查找 ，不像顺序查找，需要对表中记录逐一进行比较。折半查找的效率比顺序查找 。13. 若在分块查找中，查找表长度为n，被等分的每个子表的长度为s，则进行成功查找的平均查找长度为 。 14. 在分块查找中，若查找表的长度为96，被等分为8个子表，则进行分块查找的

58、平均查找长度为 。 15. 在分块查找中，若查找表的长度为n，被等分的每个子表的长度为，则进行成功查找的平均查找长度为 ，平均查找的时间复杂度的量级为 。16. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定 该结点的值，右子树上所有结点的值一定 该结点的值。 17. 对一棵二叉排序树进行中序遍历时，得到的中序遍历序列是一个 。18. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明 ，若元素的值小于根结点的值，则继续向 查找，若元素值大于根结点的值，则继续向 查找。19. 在向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的 插入，若元

59、素的值大于根结点的值，则接着向根结点的 插入。20. 在生成二叉排序树时，对于同样一组结点，由于结点 ，所生成的二叉排序树的形态和深度可能不同。21. 从一棵具有n个结点的二叉排序树中，查找元素的平均时间复杂度的为 。22. 从一棵具有n个结点的二叉排序树中，插入元素的平均时间复杂度为 。23. 排序又称分类，是指将一个无序序列整理成 递增（或递减）的有序序列的处理过程。24. 根据排序过程中所涉及的存储器不同，可将排序方法分为两类： 和 。25. 冒泡排序在最坏情况下记录的原始排列为反序，要经过n-1遍排序，第1遍比较n-1次，第2遍比较n-2次，依次类推。所以，算法所需总的比较次数最多为

60、。26. 冒泡排序是稳定的。冒泡排序的时间复杂度为 。27. 按查找方式的不同，插入排序又可以分为，直接插入排序和折半插入排序，前者使用 ，后者使用 。28. 在进行选择排序的第i遍排序时，从余下的 个记录中进行n - i次关键字的比较，选出 的记录作为有序序列中第i个记录，29. 每次从无序子表中，取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做 排序；每次从无序子表中挑选出一个最小元素，把它交换到有序表的一端，此种排序方法叫做 排序。30. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列时，交换它们的位置，此种排序方法叫做 排序；每次使两个相邻的有序表合并成一个有序表