下载文档原格式
1、数据结构研究的内容是（ D ）。
A）数据的逻辑结构 B）数据的存储结构C）建立在相应逻辑结构和存储结构上的算法 D）包括以上三个方面2、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ C ）。
A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法3、（ C ）在进行插入操作时，常产生假溢出现象。
A）顺序栈 B）循环队列C）顺序队列 D）链队列4、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。
A）3 B）4 C）5 D）15、设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（ B ）。
A）3，2，5，6，4，1 B）1，5，4，6，2，3C）2，4，3，5，1，6 D）4，5，3，6，2，16、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。
A）9 B）11 C）15 D）不能确定7、设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（ B ）。
A）3，2，5，6，4，1 B）1，5，4，6，2，3C）2，4，3，5，1，6 D）4，5，3，6，2，18、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。
A）loc(A1)+i*c B）loc(A1)+(i-1)*cC）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c9、广义表head(((a,b),(c,d)))的运算结果为（ A ）。
A）(a,b) B）(c,d)C）空表 D）（（a,b）,(c,d)）10、n个顶点的图的最小生成树必定（ D ），是不正确的描述。
A）不唯一 B）权的总和唯一C）不含回路 D）有n条边11、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。
A）3 B）4 C）5 D）112、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。
《数据结构》2015年春学期在线作业（三）单选题1. 设在二叉排序树上要删除P指向的节点，且设f指向P的父结点，P为f的左孩子,P结点只有左子树,无右子树,那么应做的操作是什么？（）。
A. f->lchild=nullB. f->lchild=p->lchildC. f->lchild=p->rchildD. 都不是?正确答案：B2. 设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（）。
A. G’为G 的子图B. G’为G 的连通分量C. G’为G的极小连通子图且V’=VD. G’为G的一个无环子图?正确答案：B3. 希尔排序和快速排序分别属于（）。
A. 交换排序选择排序B. 插入排序选择排序C. 选择排序归并排序D. 交换排序选择排序?正确答案：B4. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（）次探测。
A. kB. k-1C. k(k-1)/2D. 1+k(k-1)/2?正确答案：C5. 图结构的广度优先搜索遍历算法中使用了（）。
A. 堆栈B. 队列C. 堆栈和队列D. 以上都不正确。
?正确答案：B6. 对于一组结点，从空树开始，把他们插入到二叉排序树中，就建立了一棵二叉排序树。
这时，整个二叉排序树的形状取决于（）。
A. 结点的输入顺序B. 结点的存储结构C. 结点的取值范围D. 计算机的硬件?正确答案：A7. 以下说法错误的是（）。
A. 散列法存储的基本思想是由关键码的值决定数据的存储地址。
B. 散列表的结点中只包含数据元素自身的信息，不包含任何指针。
C. 装填因子是散列法的一个重要参数，它反映散列表的装填程度。
D. 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。
?正确答案：B8. 二叉查找树的查找效率与二叉树的树型有关, 在（）时其查找效率最低。
第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（）。
A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）。
A．顺序队列 B. 链表 C.有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。
（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
数据结构与算法课后习题解答数据结构与算法课后习题解答第一章绪论（参考答案）1.3 (1) O(n)(2) (2) O(n)(3) (3) O(n)(4) (4) O(n1/2)(5) (5) 执行程序段的过程中，x,y值变化如下：循环次数x y0（初始）91 1001 92 1002 93 100。
9 100 10010 101 10011 9112。
20 9921 91 98。
30 101 9831 91 97到y=0时，要执行10*100次，可记为O（10*y）=O（n）数据结构与算法课后习题解答1.5 2100 , (2/3)n , log2n , n1/2 , n3/2 , (3/2)n , nlog2n , 2 n , n! , n n第二章线性表(参考答案)在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#define ***** 1024typedef int ElemType;// 实际上，ElemTypetypedef struct{ ElemType data[*****];int last; // last}sequenlist;（2*next；}linklist;（3）链式存储结构（双链表）typedef struct node{ElemType data;struct node *prior,*next；数据结构与算法课后习题解答}dlinklist;（4）静态链表typedef struct{ElemType data;int next;}node;node sa[*****];2.1 la，往往简称为“链表la”。
是副产品）2.2 23voidelenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的{ int i=0,j;while (ielenum A[i]=x) i++; // 查找插入位置for (j= elenum-1;jj--) A[j+1]=A[j];// 向后移动元素A[i]=x; // 插入元素数据结构与算法课后习题解答} // 算法结束24void rightrotate(ElemType A[],int n,k)// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。
2.3 课后习题解答2.3.2 判断题1．线性表的逻辑顺序与存储顺序总是一致的。
（×）2．顺序存储的线性表可以按序号随机存取。
（√）3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
（×）4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。
（√）5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
（×）6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
（√）7．线性表的链式存储结构优于顺序存储结构。
（×）8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。
（√）9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
（×）11．静态链表既有顺序存储的优点，又有动态链表的优点。
所以它存取表中第i个元素的时间与i无关。
（×）12．线性表的特点是每个元素都有一个前驱和一个后继。
（×）2.3.3 算法设计题1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。
试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。
int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/else {i=*elenum;while (i>=0 && A[i]>x) /*边找位置边移动*/{A[i+1]=A[i];i--;}A[i+1]=x; /*找到的位置是插入位的下一位*/(*elenum)++;return 1; /*插入成功*/}}时间复杂度为O(n)。
第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．部结构和外部结构（2）与数据元素本身的形式、容、相对位置、个数无关的是数据的（）。
A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说确的是（）。
A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）。
A．顺序队列 B. 链表 C.有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。
（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
《数据结构与算法》习题与答案（解答仅供参考）一、名词解释：1. 数据结构：数据结构是计算机存储、组织数据的方式，它不仅包括数据的逻辑结构（如线性结构、树形结构、图状结构等），还包括物理结构（如顺序存储、链式存储等）。
它是算法设计与分析的基础，对程序的效率和功能实现有直接影响。
2. 栈：栈是一种特殊的线性表，其操作遵循“后进先出”（Last In First Out, LIFO）原则。
在栈中，允许进行的操作主要有两种：压栈（Push），将元素添加到栈顶；弹栈（Pop），将栈顶元素移除。
3. 队列：队列是一种先进先出（First In First Out, FIFO）的数据结构，允许在其一端插入元素（称为入队），而在另一端删除元素（称为出队）。
常见的实现方式有顺序队列和循环队列。
4. 二叉排序树（又称二叉查找树）：二叉排序树是一种二叉树，其每个节点的左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。
这种特性使得能在O(log n)的时间复杂度内完成搜索、插入和删除操作。
5. 图：图是一种非线性数据结构，由顶点（Vertex）和边（Edge）组成，用于表示对象之间的多种关系。
根据边是否有方向，可分为有向图和无向图；根据是否存在环路，又可分为有环图和无环图。
二、填空题：1. 在一个长度为n的顺序表中，插入一个新元素平均需要移动______个元素。
答案：(n/2)2. 哈希表利用______函数来确定元素的存储位置，通过解决哈希冲突以达到快速查找的目的。
答案：哈希（Hash）3. ______是最小生成树的一种算法，采用贪心策略，每次都选择当前未加入生成树且连接两个未连通集合的最小权重边。
答案：Prim算法4. 在深度优先搜索（DFS）过程中，使用______数据结构来记录已经被访问过的顶点，防止重复访问。
答案：栈或标记数组5. 快速排序算法在最坏情况下的时间复杂度为______。
一、填空题（每空1分，共10分）1. _数据_即信息的载体，是对客观事物的符合表示，指能输入到计算机中并能被计算机程序处理的符合的总称。
2. 线性结构中元素之间存在_一对一_关系；树型结构中元素之间存在_一对多_关系；图型结构中元素之间存在_多对多_关系。
3. 在双向链表中，每个结点含有两个指针域，一个指向_直接前趋_结点，另一个指向_直接后继_结点。
4. 两个字符串相等的条件是两串长度相等和_各个对应位置的字符相等。
5. 对于一个有n个结点的二叉树，当它为一棵_完全_二叉树时具有最小高度，当它为一棵单支树具有最大高度，其最大高度为_n_。
二、选择题（每题2分，共24分）1.A2.B3.A4.A5.D6.C7.C8.D9.C 10.C 11.B 12.D三、判断题（每题1分，共10分）1.√2.×3.×4.×5.×6.×7.√8.√9.√ 10.×四、简答题（共16分）1．简述什么是数据结构，并说明有哪几类基本结构。
（7分）答：数据结构是数据元素的组织形式，或数据元素相互之间存在的一种或多种特定关系的集合。
（3分）数据结构有四类基本形式：集合、线性结构、树型结构和图状结构。
（4分）2．比较对一般线性表、栈和队列三种结构数据进行操作的不同之处？（9分）答：一般线性表可在表的任意位置进行插入和删除操作；（3分）栈限定仅在表的一端进行插入或删除操作，栈的修改是按“后进先出”的原则进行的；（3分）队列限定只能在表的一端进行插入，在表的另一端进行删除，是一种“先进先出”的线性表。
（3分）五、分析题（共40分）1. 已知一棵树边的集合为{<i，m>，<i，n>，<e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>}，请画出这棵树，并回答下列问题：（12分）（1）哪个是根结点？ a (1分)（2）哪些是叶子结点？ d m n f j k l (1分)（3）哪个是结点f的双亲？ c (1分)（4）哪些是结点g的孩子？ j k (1分)（5）哪些是结点e的兄弟？ d (1分)（6）哪些是结点h的祖先？ a c (1分)（7）结点c的度是多少？ 3 (1分)（8）结点i的层次号分别是什么？ 4 (1分)（9）树的深度是多少？ 5 (1分)（10）以结点e为根的子树深度是多少？3 (1分)(2分) 2．写出下列树的先序、中序、后序遍历序列。
数据结构与算法测试题+参考答案一、单选题（共80题，每题1分，共80分）1、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？A、仅有头指针的单循环链表B、双链表C、仅有尾指针的单循环链表D、单链表正确答案：C2、数据结构研究的内容是（）。
A、数据的逻辑结构B、数据的存储结构C、建立在相应逻辑结构和存储结构上的算法D、包括以上三个方面正确答案：D3、下列关于无向连通图特征的叙述中，正确的是：所有顶点的度之和为偶数边数大于顶点个数减1至少有一个顶点的度为1A、只有1B、1和2C、1和3D、只有2正确答案：A4、下面的程序段违反了算法的（）原则。
void sam(){ int n=2;while (n%2==0) n+=2;printf(“%d”,n);}A、确定性B、可行性C、有穷性D、健壮性正确答案：C5、对任意给定的含 n (n>2) 个字符的有限集 S，用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树 T1 和 T2。
下列叙述中，正确的是：A、出现频次不同的字符在 T2 中处于相同的层B、出现频次不同的字符在 T1 中处于不同的层C、T1 的高度大于 T2 的高度D、T1 与 T2 的结点数相同正确答案：A6、数据序列{ 3，2，4，9，8，11，6，20 }只能是下列哪种排序算法的两趟排序结果？A、快速排序B、选择排序C、插入排序D、冒泡排序正确答案：A7、设散列表的地址区间为[0,16]，散列函数为H(Key)=Key%17。
采用线性探测法处理冲突，并将关键字序列{ 26，25，72，38，8，18，59 }依次存储到散列表中。
元素59存放在散列表中的地址是：A、11B、9C、10D、8正确答案：A8、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：A、每次划分后，先处理较短的分区可以减少递归次数B、递归次数与每次划分后得到的分区处理顺序无关C、递归次数与初始数据的排列次序无关D、每次划分后，先处理较长的分区可以减少递归次数正确答案：B9、以下数据结构中，（）是非线性数据结构。
单选题1.【第1章第2节】数据结构课程主要研究以下三方面的内容，它们是______。
∙ A 数据、数据元素、数据类型∙ B 数据元素、数据类型、算法实现∙ C 数据元素、数据的逻辑结构、数据的存储结构∙ D 数据的逻辑结构、数据的存储结构、数据的运算∙单选题2.【第1章第2节】在数据结构中，与所使用的计算机无关的是数据的____结构。
∙ A 存储∙ B 物理∙ C 逻辑∙ D 物理与存储∙判断题3.【第1章第2节】逻辑结构相同时物理结构也应该相同。
∙正确错误∙单选题4.【第1章第3节】设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为______。
∙ A O（log2n）∙ B O(n)∙ C O(nlog2n)∙ D O(n^2)∙单选题5.【第1章第3节】计算机算法是指______。
∙ A 计算方法∙ B 排序方法∙ C 调度方法∙ D 解决问题的有限运算序列∙判断题6.【第1章第3节】所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界∙正确错误∙单选题7.【第3章第2节】在长度为n 的双链表中某结点（已知其地址）之前，插入一个新结点的时间复杂度是_____ 。
∙ A O(n)∙ B O(log2n)∙ C O(1)∙ D O(n^2)∙单选题8.【第3章第2节】线性表按链式方式存储时，每个结点的存储包括_____两部分。
∙ A 数据值与符号∙ B 数据与指针∙ C 数据与表名∙ D 数据项与符号∙单选题9.【第3章第2节】链表不具有的特点是_____。
∙ A 可随机访问任一元素∙ B 插入和删除不需要移动元素∙ C 不必事先估计存储空间∙ D 所需空间和线性表长度成正比∙单选题10.【第3章第2节】对顺序存储的线性表，设其长度为n，且在任何位置上插入或删除操作都是等概率的。
则插入一个元素时平均要移动表中的_____个元素。
∙ A n/2∙ B (n+1)/2∙ C (n-1)/2∙ D n∙单选题11.【第3章第2节】在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是______。
∙ A O(n)∙ B O(log2n)∙ C O(1)∙ D O(n^2)∙单选题12.【第3章第2节】线性表采用链式存储时，其地址_____。
∙ A 必须是连续的∙ B 必须是不连续的∙ C 连续与否均可∙ D 部分地址必须是连续的∙13.【第3章第2节】若要求能快速地实现在链表的末尾插入和删除结点的运算，则选择_____最合适。
∙ A 单链表∙ B 带尾指针的单循环链表∙ C 双链表∙ D 双循环链表∙单选题14.【第3章第2节】带头结点的单链表Head为空表的判定条件是______。
∙ A Head->next==Head∙ B Head->next==NULL∙ C Head!=NULL∙ D Head==NULL单选题15.【第3章第2节】顺序表的特点是______。
∙ A 逻辑上相邻的结点其物理位置不相邻∙ B 逻辑上相邻的结点其物理位置亦相邻∙ C 顺序表不是随机存储结构∙ D 在顺序表中插入和删除操作比在链表上方便∙单选题16.【第3章第2节】在一个长度为n的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时需向后移动_______个元素。
∙ A 1∙ B n-i∙ C n-i-1∙ D n-i+1单选题17.【第3章第2节】向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动_____个元素。
∙ A 115∙ B 114∙ C 58∙ D 57∙判断题18.【第3章第2节】在n个元素的顺序表中删除第i个元素，需要移动n-i个元素。
∙正确错误∙单选题19.【第3章第3节】栈结构通常采用的两种存储结构是_____。
∙ A 线性存储结构和链表存储结构∙ B 散列方式和索引方式∙ C 链表存储结构和数组∙ D 线性存储结构和非线性存储结构∙单选题20.【第3章第3节】一个栈的进栈序列是a,b,c,d,e, 则栈的不可能的出栈序列是_____。
∙ A edcba∙ B dceab∙ C decba∙ D abcde∙21.【第3章第3节】作进栈操作时，应先判断栈是否为_____。
∙ A 空∙ B 满∙ C 上溢∙ D 下溢∙单选题22.【第3章第3节】若某堆栈的输入序列为1，2，3，…，n-1，n，输出序列的第1个元素为n，则第i个输出元素为______。
∙ A n-i+l∙ B n-i∙ C i∙ D 哪个元素无所谓单选题23.【第3章第3节】当字符序列 x5y 作为字符堆栈的输入时，输出长度为3的且可以作为C语言标识符的个数是____。
∙ A 3个∙ B 4个∙ C 5个∙ D 6个∙单选题24.【第3章第3节】采用不带尾指针的单链表方式表示一个栈，便于结点的插入与删除。
栈顶结点的插入与删除通常在链表的_____进行。
∙ A 任意位置∙ B 链表头尾两端∙ C 链表头一端∙ D 链表尾一端∙单选题25.【第3章第3节】一个栈的入栈序列是a,b,c,d, 则下列序列中不可能的输出序列是_______。
∙ A acbd∙ B dcba∙ C acdb∙ D dbac∙判断题26.【第3章第3节】判断顺序储存下堆栈s是空的条件是s.top==0。
∙正确错误∙27.【第3章第4节】队列的操作原则是_____。
∙ A 先进先出∙ B 先进后出∙ C 只能进行插入∙ D 只能进行删除∙单选题28.【第3章第4节】判断一个循环队列是空队列的条件是_____。
∙ A Q.rear==Q.front∙ B Q.front==0∙ C Q.rear==0∙ D (Q.rear+1)%maxsize==Q.front∙29.【第3章第4节】判断顺序储存下队列q是空的条件是q.front==q.rear。
∙正确错误∙单选题30.【第4章第1节】对线性表进行二分查找时，要求线性表必须____。
∙ A 以顺序方式存储∙ B 以顺序方式存储且元素有序∙ C 以链式方式存储∙ D 以链式方式存储且元素有序∙单选题31.【第4章第1节】在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做____次关键码比较。
∙ A 2∙ B 3∙ C 4∙ D 5∙单选题32.【第4章第1节】若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至____。
∙ A 该中间位置∙ B 该中间位置－1∙ C 该中间位置＋1∙ D 该中间位置／2∙单选题33.【第4章第2节】树最适合用来表示_____。
∙ A 有序数据元素∙ B 无序数据元素∙ C 元素之间具有分支层次关系的数据∙ D 元素之间无联系的数据∙单选题34.【第4章第2节】若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是____。
∙ A 根结点无右子树的二叉树∙ B 根结点无左子树的二叉树∙ C 根节点可能有左子树和右子树的二叉树∙ D 各结点只有一个儿子的二叉树∙判断题35.【第4章第2节】任何一个森林都可以唯一地与一棵二叉树对应。
∙正确错误∙判断题36.【第4章第2节】n(n>0)个结点的树有n-1条边。
∙正确错误∙单选题37.【第4章第3节】任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序____。
∙ A 不发生变化∙ B 发生变化∙ C 不能确定∙ D 以上都不对∙单选题38.【第4章第3节】设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是_____。
∙ A 6∙ B 5∙ C 4∙ D 3∙单选题39.【第4章第3节】某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是_____的二叉树。
∙ A 空或只有一个结点∙ B 高度等于其结点数∙ C .任一结点无左孩子∙ D 任一结点无右孩子∙单选题40.【第4章第3节】关于二叉树的三种遍历，下列说法正确的是____。
∙ A 任意两种遍历序列都不可以唯一决定该二叉树∙ B 任意两种遍历序列都可以唯一决定该二叉树∙ C 先序遍历序列和后序遍历序列可以唯一决定该二叉树∙ D 先序遍历序列和中序遍历序列可以唯一决定该二叉树∙单选题41.【第4章第3节】已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是____。
∙ A acbed∙ B decab∙ C deabc∙ D cedba∙单选题42.【第4章第3节】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为_____(注意C和D中h是指数)。
∙ A 2h-1∙ B 2(h-1)∙ C 2*h-1∙ D 2*h∙单选题43.【第4章第3节】设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是____。
∙ A a是b祖先∙ B a是b子孙∙ C a在b左方∙ D a在b右方∙单选题44.【第4章第3节】树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。
这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。
那么以下结论中_____是正确的。
∙ A 树的先根遍历序列与其对应的二叉树的先序遍历序列相同∙ B 树的后根遍历序列与其对应的二叉树的后序遍历序列相同∙ C 树的先根遍历序列与其对应的二叉树的中序遍历序列相同∙ D 以上都不对∙单选题45.【第4章第3节】在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列。
∙ B 不正确∙单选题46.【第4章第3节】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____(注意C和D中h为指数)。
∙ A 2h-1∙ B 2(h-1)∙ C 2*h-1∙ D 2*h∙单选题47.【第4章第3节】如果某二叉树的先序遍历序列是abdcef，中序遍历序列是dbaefc，则其后序遍历序列是____。
∙ A dbafec∙ C efcdba∙ D dbfeca∙判断题48.【第4章第3节】满二叉树一定是完全二叉树，反之不然。
∙正确错误∙判断题49.【第4章第3节】任何二叉树的叶子数都要比度为2的结点数多。
∙正确错误∙判断题50.【第4章第3节】由二叉树的前序和中序遍历序列可惟一构造这棵二叉树。
∙正确错误∙单选题51.【第4章第4节】若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过____。
∙ A n/2∙ B n∙ C (n+1)/2∙ D n+1∙判断题52.【第4章第4节】二叉排序树一般用于查找某个元素。
