数据结构(c)测试.doc

第一题、单项选择题（每题1分，5道题共5分）
1、在线性结构中，除最后一个以外的其余结点有＿＿＿＿＿＿＿＿个后继结点。
A、0
B、1
C、任意多
D、

2、下列函数中，时间复杂度最小的是＿＿＿＿＿＿＿＿。
A、nlogn+1000logn
B、n[logn] -1000logn ***
C、n*n-1000logn
D、2nlogn-1000logn

3、栈和队列属于＿＿＿＿＿＿＿＿逻辑结构。
A、线性
B、非线性
C、动态
D、静态

4、一个算法所需时间由下述递归方程表示，该算法的时间复杂度是＿＿＿＿＿＿＿＿。T(1)＝1, T(n)＝2T(n/2)+n (n>1) 其中n为问题的规模，设n为2的整数幂。
A、O(n)
B、O(logn)
C、O(nlogn)
D、O(n*n)

5、n为正整数，下列程序段的时间复杂度是＿＿＿＿＿＿＿＿。x＝n; y＝0; while(x>＝(y+1)*(y+1)) y++;
A、O(n)
B、O(n*n)
C、O(n[1/2]) ***
D、O(1)

第二题、多项选择题（每题2分，5道题共10分）
1、数据结构的三要素是指＿＿＿＿＿＿＿＿。
A、数据元素
B、逻辑结构
C、物理结构
D、顺序结构
E、链式结构

2、下列说法中，正确的是＿＿＿＿＿＿＿＿。
A、数据元素是数据的基本单位
B、数据项是数据中不可分割的最小标识单位
C、数据可由若干个数据元素组成
D、数据项可由若干个数据元素组成

3、算法分析的主要方面是＿＿＿＿＿＿＿＿。
A、时间复杂度
B、空间复杂度
C、数据复杂性
D、程序复杂性

4、一个"好"的算法应达到的目标有＿＿＿＿＿＿＿＿。
A、正确性
B、可行性
C、可读性
D、健壮性
E、高效与低存储量
F、确定性

5、研究数据结构就是研究＿＿＿＿＿＿＿＿。
A、数据的逻辑结构
B、数据的物理结构
C、数据在运算上的实现
D、数据的复杂度

第三题、判断题（每题1分，5道题共5分）
1、任何数据结构都具备三个基本运算：插入、删除和查找。（ ）
正确
错误

2、数据元素可以由很多数据项组成。 （ ）
正确
错误

3、数据元素是数据的基本单位。 （ ）
正确
错误

4、算法分析的目的是研究算法中输入和输出的关系。 （ ）
正确
错误

5、在计算机科学中，数据的含义可以很广泛，图像、声音等都可以通过编码的形式而归之于数据的范畴。 （ ）
正确
错误

第二章
1、顺序表是线性表的一种＿＿＿＿＿＿＿的存储结构。
A、顺序存取
B、随机存取
C、索引存取
D、

2、在一个单链表中，在p所指结点之后插入s所指结点应执行＿＿＿＿＿＿＿＿。
A、s->next＝p;p->next＝s;
B、s->next＝p->next;p->next＝s;
C、s->next＝p->next;p ＝s;
D、p->next＝s;s->next＝p;

3、在n个元素的单链表中插入或删除一个元素的算法的时间复杂度为＿＿＿＿＿＿＿＿。
A、O(1)
B、O(n)
C、O(n*n)
D、

4、建立n个元素的单链表，其算法的时间复杂度为＿＿＿＿＿＿＿＿。
A、O(1)
B、O(n)
C、O(n*n)
D、

5、建立n个元素的有序单链表，其算法的时间复杂度为＿＿＿＿＿＿＿＿。
A、O(1)
B、O(n)
C、O(n*n)
D、O(n*n*n)

第二题、多项选择题（每题2分，5道题共10分）
1、顺序表的特点是＿＿＿＿＿＿＿＿。
A、随机存取
B、顺序存取
C、逻辑相邻的元素物理位置也相邻
D、元素的物理位置可以相邻也可以不相邻

2、单链表的特点是＿＿＿＿＿＿＿＿。
A、随机存取
B、顺序存取
C、逻辑相邻的元素物理位置也相邻
D、元素的物理位置可以相邻也可以不相邻

3、在双向循环链表（L为头指针）中，指针p所指结点为尾结点的条件是＿＿＿＿＿＿＿＿。
A、p＝＝L
B、p->next＝＝L
C、L->prior＝＝p
D、L->next＝＝p

4、一元多项式中非零项的系数指数对所成的线性表可用＿＿＿＿＿＿＿＿来表示。
A、顺序结构
B、链式结构
C、逻辑结构
D、索引结构

5、在双向循环链表中，若要在指针q所指结点的后面插入一个s所指结点，则须执行下列语句：s->prior＝q;s->next＝q->next; ＿＿＿＿＿＿＿;q->next＝s;
A、q->next->prior＝s
B、s＝q
C、s->next->prior＝s
D、s->prior->next＝q

第三题、判断题（每题1分，5道题共5分）
1、在单链表中插入或删除元素时是以结点的指针变化来反映逻辑关系的变化，因此不需要移动元素。
正确
错误

2、整个单链表的存取必须从头指针开始沿链表进行，因此单链表中的元素是可以进行随机存取的。
正确
错误

3、一元多项式的链式存储结构优于顺序存储结构。 （ ）
正确
错误

4、在双向循环链表中插入或删除元素时仅需要修改结点的指针，不需要移动元素，因此算法的时间复杂度为O(1)。 （ ）
正确
错误

5、用线性链表表示一元多项式时，其有序性是指链表中的结点按此项的系数由小到大有序排列。
正确
错误

第一题、单项选择题（每题1分，5道题共5分）
1、在一个单链表中，在p所指结点之后插入s所指结点应执行＿＿＿＿＿＿＿＿。
A、s->next＝p;p->next＝s;
B、s->next＝p->next;p->next＝s;
C、s->next＝p->next;p ＝s;
D、p->next＝s;s->next＝p;

2、若在线性表的任何位置上删除元素的概率是相等的，那么在长度为n的顺序表中删除一个元素时需平均移动＿＿＿＿＿＿＿＿个元素。
A、n
B、(n-1)/2
C、n/2
D、(n+1)/2

3、在n个元素的单链表中插入或删除一个元素的算法的时间复杂度为＿＿＿＿＿＿＿＿。
A、O(1)
B、O(n)
C、O(n*n)
D、

4、建立n个元素的单链表，其算法的时间复杂度为＿＿＿＿＿＿＿＿。
A、O(1)
B、O(n)
C、O(n*n)
D、

5、建立n个元素的有序单链表，其算法的时间复杂度为＿＿＿＿＿＿＿＿。
A、O(1)
B、O(n)
C、O(n*n)
D、O(n*n*n)

第二题、多项选择题（每题2分，5道题共10分）
1、在双向循环链表中，若s是指向表中某结点的指针，则＿＿＿＿＿＿＿＿。
A、s->next＝＝s
B、s->next->prior＝＝s
C、s->prior->next ＝＝s
D、s-> prior＝＝s

2、顺序表的特点是＿＿＿＿＿＿＿＿。
A、随机存取
B、顺序存取
C、逻辑相邻的元素物理位置也相邻
D、元素的物理位置可以相邻也可以不相邻

3、单链表是用一组任意的存储单元来存储线性表的元素，这些存储单元之间＿＿＿＿＿＿＿＿。
A、必须不连续
B、可以是连续的
C、必须连续
D、可以是不连续的

4、在线性表的下列存储结构中，读取元素花费时间相同的是＿＿＿＿＿＿＿＿。
A、顺序表
B、单链表
C、循环链表
D、双向链表

5、在双向循环链表中，我们通常可设置＿＿＿＿＿＿＿＿来表示整个链表。
A、头指针
B、尾指针
C、指向任意结点的指针

第三题、判断题（每题1分，5道题共5分）
1、单链表的头结点表示的是线性表中的第一个元素。 （ ）
正确
错误

2、一元多项式的链式存储结构优于顺序存储结构。 （ ）
正确
错误

3、在双向循环链表中插入或删除元素时仅需要修改结点的指针，不需要移动元素，因此算法的时间复杂度为O(1)。 （ ）
正确
错误

4、在循环链表中设尾指针比设头指针方便。 （ ）
正确
错误

5、用线性链表表示一元多项式时，其有序性是指链表中的结点按此项的系数由小到大有序排列。
正确
错误

第三章
1、在顺序栈中，base、top分别为栈底、栈顶指针，则＿＿＿＿＿＿＿时表明栈空。
A、base＝＝NULL
B、top＝＝ NULL
C、base＝＝top
D、

2、非空顺序栈中的栈顶指针始终指向栈顶元素的＿＿＿＿＿＿＿位置上。
A、上一个
B、当前
C、下一个
D、

3、将递归算法转换成对应的非递归算法时，通常使用＿＿＿＿＿＿＿保存中间结果。
A、栈
B、队列
C、图
D、树

4、非空循环队列中的队尾指针始终指向队尾元素的＿＿＿＿＿＿＿位置上。
A、上一个
B、当前
C、下一个
D、

5、在循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，则队列空的判定方法是＿＿＿＿＿＿＿。
A、f＝＝r
B、(f+1) ％ (m+1)＝＝r
C、(r+1) ％ (m+1)＝＝f
D、(r+1) ％ m＝＝f

第二题、多项选择题（每题2分，5道题共10分）
1、循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，此时队空、队满的判断条件都是f＝＝r,为解决此矛盾，通常可采用＿＿＿＿＿＿＿。
A、另设一个标志位来辅助判断队空还是队满
B、牺牲一个元素空间，以Q中存放m个元素时认为队列满
C、无法解决此矛盾，改用链队列表示

2、一个栈的入栈序列是{1,2,3,4,5},则栈的不可能的输出序列是＿＿＿＿＿＿＿。
A、54321
B、12345
C、45231
D、32514
E、14325

3、一个队列的入队序列是{1,2,3,4},则队列不可能的输出序列是＿＿＿＿＿＿＿。
A、4321
B、1234
C、1432
D、3241

4、下列叙述中，错误的是＿＿＿＿＿＿＿。
A、栈是一种FIFO的数据结构。
B、队列是一种LIFO的数据结构。
C、编程时，栈可以用静态或动态的数据类型实现。
D、编程时，队列可以用静态或动态的数据类型实现。

5、在链队列中，若插入一个元素，则＿＿＿＿＿＿＿。
A、必须修改尾指针
B、必须修改头指针
C、不必修改尾指针
D、不必修改头指针

第三题、判断题（每题1分，5道题共5分）
1、若用户无法估计所用队列的最大长度，则最好采用链队列。 （ ）
正确
错误

2、栈的一个重要应用是在程序设计语言中实现递归。 （ ）
正确
错误

3、队列只能有一种输出序列，即队列中的元素只能按照进入队列的顺序依次出队。（ ）
正确
错误

4、在实际应用中，双端队列比栈和队列应用更广泛。 （ ）
正确
错误

5、在循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，用设标志位的方法解决队空队满判断条件相同的问题，，则队长的计算方法是（r-f+m+1）％ m。
正确
错误

第四章
1、串的长度是＿＿＿＿＿＿＿＿。
A、串中不同字母的个数
B、串中不同字符的个数
C、串中所含字符的个数，且大于0
D、串中所含字符的个数

2、空串是＿＿＿＿＿＿＿＿。
A、由空格组成的串
B、串长为1的串
C、不含任何字符的串
D、

3、空格串的长度为＿＿＿＿＿＿＿＿。
A、0
B、1
C、串中空格的个数
D、

4、设串s＝’I am a student.’,则s的长度为＿＿＿＿＿＿＿＿。
A、11
B、12
C、15
D、16

5、设串s＝’student.’,t＝’good ’,则执行Strinserｔ(s,1,t)后，s为＿＿＿＿＿＿＿＿。
A、’good student.’
B、’good student’
C、’goodstudent’
D、’ good teacher’

第二题、多项选择题（每题2分，5道题共10分）
1、两个串相等的充分必要条件是＿＿＿＿＿＿＿＿＿＿。
A、串长相等且各对应位置字符相等
B、所含字符集合相同
C、所含字符个数相同
D、串值相等

2、串用定长顺序存储方式表示时，有可能发生"截断"的操作有＿＿＿＿＿＿＿＿＿＿。
A、串连接
B、求子串
C、串替换
D、插入串
E、删除子串

3、以下关于块链结构的说法正确的是＿＿＿＿＿＿＿＿＿＿。
A、结点大小小，则存储密度小
B、结点大小小，则存储密度大
C、结点大小小，则占用存储空间多
D、结点大小小，则占用存储空间少

4、文本编辑程序中要设立＿＿＿＿＿＿＿＿＿＿来指示当前操作的字符位置。
A、页指针
B、行指针
C、字符指针
D、文件指针

5、以下关于串的存储方式的说法中正确的是＿＿＿＿＿＿＿＿＿＿。
A、定长顺序表示和堆分配表示都是串的顺序存储表示
B、定长顺序表示的串的存储空间是编译时预先分配的一个比较大的连续空间
C、堆分配表示的串的存储空间是在程序执行过程中动态分配的
D、堆分配存储表示时的空串不占用连续的存储区

第三题、判断题（每题1分，5道题共5分）
1、空串和空格串是相同的。 （ ）
正确
错误

2、串也有两种存储结构：顺序结构和链式结构。 （ ）
正确
错误

3、串的链式结构优于其顺序存储结构。 （ ）
正确
错误

4、在串的块链存储结构中，设尾指针的目的是为了便于进行联结操作。 （ ）
正确
错误

5、在C语言中，用动态分配函数进行管理的自由存储区称为"堆"。 （ ）
正确
错误

第六章
第一题、单项选择题（每题1分，5道题共5分）
1、一个有n个顶点的无向图若是连通图，则至少有＿＿＿＿＿＿＿＿条边。
A、n
B、n+1
C、n-1
D、n/2

2、在一个有向图中，所有顶点的入度之和等于所有边数的＿＿＿＿＿＿＿＿倍。
A、1/2
B、1
C、2
D、4

3、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的＿＿＿＿＿＿＿＿倍。
A、1/2
B、1
C、2
D、4

4、邻接表是图的一种＿＿＿＿＿＿＿＿。
A、顺序存储结构
B、链式存储结构
C、索引存储结构
D、散列存储结构

5、对一个以邻接表为存储结构、有n个顶点e条边的无向连通图，深度优先遍历图的时间复杂度是＿＿＿＿＿＿＿＿。
A、O(n)
B、O(n*n)
C、O(n+e)
D、O(n*e)

第二题、多项选择题（每题2分，5道题共10分）
1、判断一个有向图是否存在回路，可以用＿＿＿＿＿＿＿＿。
A、深度优先遍历算法
B、广度优先遍历算法
C、拓扑排序方法
D、求最短路径方法

2、下列说法中正确的有＿＿＿＿＿＿＿＿。
A、图的遍历过程中每个顶点仅被访问一次
B、图的深度优先遍历算法不适用于有向图
C、图的深度优先遍历过程是一个递归过程
D、遍历图的基本方法有深度优先遍历和广度优先遍历

3、任何一个无向连通图的最小生成树＿＿＿＿＿＿＿＿。
A、只有一棵
B、可能有多棵
C、可能不存在
D、可能有一棵

4、在拓扑排序中，拓扑序列的第一个顶点一定是＿＿＿＿＿＿＿＿的顶点。
A、入度为0
B、没有前驱
C、出度为0
D、没有后继

5、有向图的拓扑有序序列＿＿＿＿＿＿＿＿。
A、可能存在
B、一定存在
C、可能有多个
D、肯定有多个

第三题、判断题（每题1分，5道题共5分）
1、图结构中，每个结点的前驱结点数和后续结点数都可以有任意多个。（ ）
正确
错误

2、在n个顶点的无向图中，若边数大于n-1，则该图一定是连通图。 （ ）
正确
错误

3、只要能提高关键活动的速度，就能缩短整个工程的工期。 （ ）
正确
错误

4、从某顶点开始对有向图进行深度优先遍历，若所得的遍历序列唯一，则可断定其弧数为n-1（n为图中顶点数）。 （ ）
正确
错误

5、若有向图的拓扑排序序列唯一，则图中必定仅有一个顶点的入度为0，一个顶点的出度为0。 （ ）
正确
错误

第七
第一题、单项选择题（每题1分，5道题共5分）
1、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相等，用顺序查找来确定结点所在的块，每块有＿＿＿＿＿＿＿个元素时查找效率最佳。
A、10
B、25
C、6
D、625

2、有一个有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}中折半查找值为82的结点时，＿＿＿＿＿＿＿次比较后查找成功。
A、1
B、2
C、4
D、8

3、高度为5的二叉平衡树至少有＿＿＿＿＿＿＿个结点。
A、10
B、12
C、15
D、17

4、假设有k个关键字互为同义词，若用线性探测再散列法将这k个关键字存入散列表中，则至少需要进行＿＿＿＿＿＿＿次探测。
A、k-1
B、k
C、k+1
D、k(k+1)/2

5、在对查找表的查找过程中，若被查找的元素不存在，则把该元素插入到查找表中，这种方式主要适合于＿＿＿＿＿＿＿。
A、静态查找表
B、动态查找表
C、静态查找表与动态查找表
D、两种表都不合适

第二题、多项选择题（每题2分，5道题共10分）
1、分块查找的平均查找长度与＿＿＿＿＿＿＿有关。
A、表长
B、块数
C、块中元素个数
D、索引表的查找方式

2、构造哈希表时解决冲突常用的方法有＿＿＿＿＿＿＿。
A、数字分析法、除余法、平方取中法
B、链地址法、线性探测再散列法
C、开放定址法
D、再哈希法、建立公共溢出区

3、在各种查找方法中，平均查找长度与表长有关的查找方法是＿＿＿＿＿＿＿。
A、哈希表查找
B、顺序查找
C、折半查找
D、排序树查找

4、对于10个元素的有序表进行折半查找，须比较3次方可查找成功的元素在表中的位置有＿＿＿＿＿＿＿。
A、1
B、2
C、3
D、4
E、5
F、6
G、7
H、8

5、对序列{50，72，43，85，75，20，35，45，30}按顺序建二叉排序树，则在树中须比较3次方可查找成功的元素有＿＿＿＿＿＿＿。
A、72
B、43
C、85
D、75
E、20
F、35
G、45
H、30

第三题、判断题（每题1分，5道题共5分）
1、折半查找和二叉排序树查找的时间性能相同。 （ ）
正确
错误

2、在索引顺序表上实现分块查找，在等概率的情况下，其平均查找长度不仅与表的元素个数有关，而且与每一块中的元素个数有关。 （ ）
正确
错误

3、若散列表的装填因子小于1，则可避免冲突的产生。 （ ）
正确
错误

4、平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树。 （ ）
正确
错误

5、对B树中任意非叶子结点中的某关键字k，比k小的最大关键字和比k大的最小关键字一定都在叶子结点中。 （ ）
正确
错误

第八章
1、下列方法中，＿＿＿＿＿＿＿＿是稳定的排序方法。
A、堆排序
B、希尔排序
C、快速排序
D、折半插入排序

2、在所有排序方法中，关键字之间比较的次数与记录的初始排列次序无关的是＿＿＿＿＿＿＿。
A、希尔排序
B、起泡排序
C、选择排序
D、插入排序

3、在下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是＿＿＿＿＿＿＿。
A、堆排序
B、起泡排序
C、快速排序
D、直接插入排序

4、在下列排序方法中，在待排序的数据有序时, 花费时间反而最多的是＿＿＿＿＿＿＿。
A、堆排序
B、起泡排序
C、快速排序
D、希尔排序

5、数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用＿＿＿＿＿＿＿方法最节省时间。
A、堆排序
B、简单选择排序
C、快速排序
D、希尔排序

第二题、多项选择题（每题2分，5道题共10分）
1、下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(nlogn)。
A、希尔排序
B、堆排序
C、归并排序
D、简单选择排序

2、下列排序方法中，在最坏情况下算法的时间复杂度仍为O(nlogn)的有＿＿＿＿＿＿＿＿。
A、归并排序
B、堆排序
C、快速排序
D、希尔排序

3、下列排序方法中，平均时间复杂度最好的方法有＿＿＿＿＿＿＿＿。
A、希尔排序
B、堆排序
C、快速排序
D、冒泡排序

4、下列插入排序方法中，时间复杂度为O(n2)的方法有＿＿＿＿＿＿＿＿。
A、折半插入排序
B、希尔排序
C、2-路插入排序
D、直接插入排序

5、待排序序列为{46,79,56,38,40,84}，则下列序列中不是用堆排序的方法建立的初始堆为＿＿＿＿＿＿＿＿。
A、{79,46,56,38,40,84}
B、{84,79,56,38,40,46}
C、{84,79,56,46,40,38}
D、{84,56,79,40,46,38}

第三题、判断题（每题1分，5道题共5分）
1、用折半插入排序所需的比较次数和待排序记录的初始排列状态有关。（ ）
正确
错误

2、在执行某排序算法的过程中，如果出现了关键字朝着最终排序序列位置相反方向移动的现象，则该算法是不稳定的。 （ ）
正确
错误

3、用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。 （ ）
正确
错误

4、快速排序算法在每趟排序结束时都能找到一个元素放到其最终位置上。 （ ）
正确
错误

5、在堆排序过程中，在输出一个根之后的调整过程中，"临时根"结点的值将会最终被放到"叶子结点"上。 （ ）
正确
错误

八章我的
1、排序方法中，从未排序序列中挑选元素，将其依次放至已排序序列（初始为空）的一端的方法，称为＿＿＿＿＿＿＿。
A、希尔排序
B、归并排序
C、选择排序
D、基数排序

2、数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用＿＿＿＿＿＿＿方法最节省时间。
A、堆排序
B、简单选择排序
C、快速排序
D、希尔排序

3、对于关键字序列{12，13，10，18，60，15，7，18，25，100}用筛选法建堆，必须从关键字为＿＿＿＿＿＿＿的结点开始。
A、12
B、10
C、60
D、15

4、对n个记录的序列进行堆排序，最坏情况下的时间复杂度为＿＿＿＿＿＿。
A、O(logn) .
B、O(nlogn)
C、O(n)
D、O(n*n)

5、要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选择＿＿＿＿＿＿＿方法。
A、快速排序
B、归并排序
C、堆排序
D、基数排序

第二题、多项选择题（每题2分，5道题共10分）
1、下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(n2)。
A、希尔排序
B、冒泡排序
C、快速排序
D、直接插入排序

2、下列快速排序方法中，＿＿＿＿＿＿＿＿是稳定的排序方法。
A、归并排序
B、希尔排序
C、快速排序
D、基数排序

3、在所有排序方法中，关键字之间的比较次数与记录的初始排列次序有关的是＿＿＿＿＿＿＿。
A、希尔排序
B、快速排序
C、选择排序
D、插入排序

4、下列插入排序方法中，时间复杂度为O(n2)的方法有＿＿＿＿＿＿＿＿。
A、折半插入排序
B、希尔排序
C、2-路插入排序
D、直接插入排序

5、待排序序列为{46,79,56,38,40,84}，则下列序列中不是用堆排序的方法建立的初始堆为＿＿＿＿＿＿＿＿。
A、{79,46,56,38,40,84}
B、{84,79,56,38,40,46}
C、{84,79,56,46,40,38}
D、{84,56,79,40,46,38}

第三题、判断题（每题1分，5道题共5分）
1、在执行某排序算法的过程中，如果出现了关键字朝着最终排序序列位置相反方向移动的现象，则该算法是不稳定的。 （ ）
正确
错误

2、只有在初始数据表为逆序时，冒泡排序所执行的比较次数最多。 （ ）
正确
错误

3、在一个大顶堆中，最小元素不一定在最后。 （ ）
正确
错误

4、用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。 （ ）
正确
错误

5、快速排序算法在每趟排序结束时都能找到一个元素放到其最终位置上。 （ ）
正确
错误

5张
第一题、单项选择题（每题1分，5道题共5分）
1、深度为5的满二叉树有＿＿＿＿＿＿＿＿个结点。
A、16
B、32
C、31
D、10

2、具有100个结点的完全二叉树的深度为＿＿＿＿＿＿＿＿。
A、6
B、7
C、8
D、9

3、一棵二叉树的先序和后序序列正好相反，则该二叉树一定是＿＿＿＿＿＿＿＿。
A、空或只有一个结点
B、高度等于其结点数
C、任一结点无左孩子
D、任一结点无右孩子

4、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为＿＿＿＿＿＿＿＿。
A、2h
B、2h-1
C、2h+1
D、h+1

5、按照二叉树的定义，具有3个结点的二叉树有＿＿＿＿＿＿＿＿种形态。
A、3
B、4
C、5
D、6

第二题、多项选择题（每题2分，5道题共10分）
1、在二叉树中，某个结点的祖先＿＿＿＿＿＿＿＿。
A、可能不存在
B、可能有多个
C、肯定有多个
D、肯定有一个
E、可能有一个
F、肯定不存在

2、在非空树中，叶子结点＿＿＿＿＿＿＿＿。
A、至少有一个
B、至多有一个
C、可能有多个
D、肯定有多个
E、可能不存在

3、树可采用的存储结构有＿＿＿＿＿＿＿＿。
A、顺序结构
B、多重链表
C、二叉链表
D、孩子链表

4、后序序列和中序序列相同的二叉树有＿＿＿＿＿＿＿＿。
A、空二叉树
B、左单支树
C、右单支树
D、根树

5、先序序列和后序序列相同的二叉树有＿＿＿＿＿＿＿＿。
A、空二叉树
B、左单支树
C、右单支树
D、根树

第三题、判断题（每题1分，5道题共5分）
1、二叉树的先、中、后序遍历序列中，叶子结点的相对顺序不会发生改变。（ ）
正确
错误

2、在一棵非空二叉树的中序遍历序列中，根结点的右边只有其右子树上的所有
正确
错误

3、线索二叉树是一种物理结构。 （ ）
正确
错误

4、有n个结点并且其高度为n的二叉树的数目为2n-1。 （ ）
正确
错误

5、用树的前序遍历和中序遍历序列可以导出树的后序遍历。 （ ）
正确
错误