202210 平时测验：
¶ 平时测验1
- 若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（ ）。
-
顺序存储结构
-
链式存储结构
-
索引存储结构
-
→散列存储结构←
答案解析：本题考核散列存储的基本概念
- 设顺序表有10个元素，则在第5个元素前插入一个元素所需移动元素的个数为（ ）。
-
5
-
→6←
-
7
-
9
答案解析：在第5个元素前插入元素需要将第5个元素开始的所有元素后移，所以本题答案为B。
- 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）。
-
O（1）
-
O（n）
-
→**O（m）**←
-
O（m+n）
答案解析：本题考核单链表的基本特点
- 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。
-
顺序表
-
用头指针表示的单循环链表
-
→用尾指针表示的单循环链表←
-
单链表
答案解析：本题考核循环单链表的基本特点。
- 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( )。
-
→n-i+1←
-
n-i
-
i
-
i-1
答案解析：本题考核顺序表的插入运算。
- 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是()
-
(e,f)
-
→**((e,f))**←
-
(f)
-
( )
答案解析：考核广义表的基本操作
- 链栈与顺序栈相比，比较明显的优点是( )。
-
插入操作更加方便
-
删除操作更加方便
-
不会出现下溢的情况
-
→不会出现上溢的情况←
答案解析：链栈采用动态内存分配，一般不会出现栈满的情况，即一般不会出现上溢的情况。所以答案选D。
- 队列和栈的主要区别是（ ）。
-
→限定插入和删除的位置不同←
-
存储结构不同
-
所包含的运算个数不同
-
逻辑结构不同
答案解析：本题考核栈与队列的基本特点
- 若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为（）。
-
→**O(n)**←
-
O(1)
-
O(n2)
-
O(n3)
答案解析：本题考核顺序表的插入运算的时间复杂度。
- 计算机识别、存储和加工处理的对象被统称为( )
-
→数据←
-
数据元素
-
数据结构
-
数据类型
答案解析：本题考核数据的基本概念
- 设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f,g依次入栈S。若每个元素出栈后立即进入队列Q，且7个元素出列的顺序是b,d,c,f,e,a,g，则栈S的容量至少是（）。
-
1
-
2
-
→3←
-
4
答案解析：本题考核栈与队列的性质以及进栈、出栈、进队、出队等基本操作方法。
- 算法指的是（ ）。
-
计算机程序
-
解决问题的计算方法
-
排序算法
-
→解决问题的有限运算序列←
答案解析：考核算法的基本概念
- 线性表采用链式存储时，结点的存储地址（ ）
-
必须是不连续的
-
→连续与否均可←
-
必须是连续的
-
和头结点的存储地址相连续
答案解析：链式存储分配的结点在内存连续与不连续均可，所以答案选B。
- 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是（ ）。
-
p=p->next;
-
→**p->next=p->next->next;**←
-
p->next=p;
-
p=p->next->next;
答案解析：本题考核单链表结点删除的基本操作
- 下面程序段的时间复杂度（）。for(i=0;i<m;i++) for(j=0;j<n;j++) a[i][j]=i*j;
-
O(m2)
-
O(n2)
-
→**O(m*n)**←
-
O(m+n)
答案解析：考核时间复杂度计算方法。
- 在一个长度为n的顺序表中删除第i个元素（1<=i<=n）时，需向前移动（）个元素。
-
→n-i←
-
n-i+1
-
n-i-1
-
i
答案解析：考核顺序表的基本操作
- 在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（）。
-
O(1)
-
→**O(n)**←
-
O(n2)
-
O(nlog2n)
答案解析：因要保持有序，所以需要查找插入结点的位置，而在链表中查找结点位置的时间复杂度为O(n)，所以本题选B。
- 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( )。
-
操作的有限集合
-
映象的有限集合
-
类型的有限集合
-
→关系的有限集合←
答案解析：本题考核数据结构的基本概念
- 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
-
必须是连续的
-
部分地址必须是连续的
-
一定是不连续的
-
→连续不连续都可以←
答案解析：考核链式存储结构的特点
- 下面程序段中a[i][j]=0语句执行的时间复杂度是( )。for(i=0;i<n;i++) for(j=1;j<m;j++) a[i][j]=0；
-
O(n)
-
O(m+n+1)
-
O(m+n)
-
→**O(m*n)**←
答案解析：本题考核时间复杂度的计算方法
- 在一个单链表中，若删除p所指结点的后续结点，则执行（）。
-
→**p->next=p->next->next;**←
-
p=p->next; p->next=p->next->next;
-
p->next=p->next;
-
p =p->next->next;
答案解析：考核单链表的删除操作
- 对矩阵压缩存储是为了（ ）。
-
方便运算
-
→节省空间←
-
方便存储
-
提高运算速度
答案解析：压缩存储就是为了节省存储空间。
- 表达式a(b+c)-d的后缀表达式是()。*
-
abc*d+-
-
→**abc+*d-**←
-
abc*+d-
-
-+*abcd
答案解析：本题考核中缀表达式转后缀表达式的基本方法。
- 操作系统的CPU管理程序为实现先来先服务的作业管理，需要设置一个存储区，用于记录当前用户作业，这个存储区的逻辑结构是（ ）。
-
栈
-
→队列←
-
树
-
图
答案解析：本题考核队列的基本特点。
- 非空的循环单链表head的尾结点（由p所指向）满足（）。
-
p->next==NULL
-
p==NULL
-
→p->next==head←
-
p==head
答案解析：本题考核循环单链表的基本特点。
¶ 平时测验2
- 已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列当前长度为()
-
5
-
6
-
→16←
-
17
答案解析：考核顺序循环队列的特点
- 一棵含18个结点的二叉树的高度至少为( )。
-
3
-
4
-
→5←
-
6
答案解析：当二叉树为完全二叉树时该树具有最小高度。本题考核二叉排序树的基本概念。
- 若邻接表中有奇数个表结点，则一定（）。
-
图中有奇数个顶点
-
图中有偶数个顶点
-
图为无向图
-
→图为有向图←
答案解析：本题考核图的邻接表存储结构及其特点。
- 下列陈述中正确的是( )
-
二叉树是度为2的有序树
-
二叉树中结点只有一个孩子时无左右之分
-
二叉树中必有度为2的结点
-
→二叉树中最多只有两棵子树，并且有左右之分←
答案解析：本题考核二叉树与度为二的树的区别，答案选D。
- 队列和栈的主要区别是（ ）。
-
→限定插入和删除的位置不同←
-
存储结构不同
-
所包含的运算个数不同
-
逻辑结构不同
答案解析：本题考核栈与队列的基本特点
- 从广义表L=(((e),c,d))中分解得到原子c的操作为( )。
-
head(head(head(L)))
-
→**head(tail(head(L)))**←
-
tail(head(head(L)))
-
tail(tail(head(L)))
答案解析：本题考核广义表的基本操作。
- 设栈的输入序列为（1、2、3、4），则不可能的出栈序列为（ ）。
-
1243
-
2134
-
→4312←
-
1432
答案解析：本题考核栈的进栈与出栈特点，根据先进后出、后进先出的特点，可知本题答案选C。
- 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）。
-
→队列←
-
栈
-
线性表
-
有序表
答案解析：层次遍历二叉树需要用到队列结构。
- 链栈与顺序栈相比，比较明显的优点是( )。
-
插入操作更加方便
-
删除操作更加方便
-
不会出现下溢的情况
-
→不会出现上溢的情况←
答案解析：链栈采用动态内存分配，一般不会出现栈满的情况，即一般不会出现上溢的情况。所以答案选D。
- 设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f,g依次入栈S。若每个元素出栈后立即进入队列Q，且7个元素出列的顺序是b,d,c,f,e,a,g，则栈S的容量至少是（）。
-
1
-
2
-
→3←
-
4
答案解析：本题考核栈与队列的性质以及进栈、出栈、进队、出队等基本操作方法。
- 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是（）。
-
O(n)
-
→**O(e)**←
-
O(n+e)
-
O(n*e)
答案解析：考核邻接表的基本特点
- 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )。
-
2，4，3，1，5，6
-
4，3，2，1，5，6
-
→2，3，5，1，6，4←
-
3，2，4，1，6，5
答案解析：核具有先进后出，后进先出的特点，根据这个特点，可知本题答案为C。
- 对矩阵压缩存储是为了（ ）。
-
方便运算
-
→节省空间←
-
方便存储
-
提高运算速度
答案解析：压缩存储就是为了节省存储空间。
- 按照二叉树的定义，具有三个结点的二叉树有（ ）。
-
→5种←
-
4种
-
3种
-
6种
答案解析：二叉树严格区分左、右子树，根据定义易知具有三个结点的二叉树共有5种。
- 从广义表LS＝（(p, q), r, s）中分解出原子q的运算是（）。
-
tail (head (LS))
-
→**head (tail (head (LS)))**←
-
head (tail (LS))
-
tail (tail (head (LS)))
答案解析：本题考核广义表的基本操作。
- 顺序循环队列中（数组的大小为6），队头指示front和队尾指示rear的值分别为3和0，当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（）。
-
5和1
-
2和4
-
1和5
-
→4和2←
答案解析：本题考核顺序循环队列的基本特点。
-
设有向图的邻接链表如图所示，则该图的边的数目是（ ）。
-
→6←
-
7
-
8
-
12
答案解析：本题考核图的邻接表存储结构的基本特点。
- 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是()
-
(e,f)
-
→**((e,f))**←
-
(f)
-
( )
答案解析：考核广义表的基本操作
- 关于栈和队列的说法中正确的是（ ）。
-
→栈和队列都是线性结构←
-
栈是线性结构，队列不是线性结构
-
栈不是线性结构，队列是线性结构
-
栈和队列都不是线性结构
答案解析：栈和队列都是一种特殊的线性表。
- 引起循环队列队头位置发生变化的操作是( )。
-
→出队←
-
入队
-
取队头元素
-
取队尾元素
答案解析：本题考核循环队列的基本操作。
- 栈是一种特殊的线性表，具有（）性质。
-
先进先出
-
→先进后出←
-
后进后出
-
顺序进出
答案解析：考核栈的基本概念
- 判定“带头结点的链队列为空”的条件是( )。
-
Q.front==NULL
-
Q.rear==NULL
-
→Q.front==Q.rear←
-
Q.front!=Q.rear
答案解析：本题考核链队列的基本概念，答案选C。
- 无向图G=（V，E），其中：V={a,b,c,d,e,f}，E={（a,b），（a,e），（a,c），（b,e），（c,f），（f,d），（e,d）}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
-
a,b,e,c,d,f
-
a,c,f,e,b,d
-
→a,e,d,f,c,b←
-
a,e,b,c,f,d
答案解析：考核深度优先遍历的基本思想
- 如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（）。
-
有向完全图
-
连通图
-
强连通图
-
→有向无环图←
答案解析：本题考核图的邻接矩阵存储结构的基本特点。
- 以二叉链表作为二叉树的存储结构，有具有n个结点的二叉链表中（n>0），空链域的个数为（ ）。
-
2n-1
-
→n+1←
-
n-1
-
2n+1
答案解析：n个结点的二叉树共有n-1条边，所以空链域的个数为n+1。
¶ 平时测验3
- 对于哈希函数H(key)=key%13，被称为同义词的关键字是（）。
-
35和41
-
23和39
-
→25和51←
-
15和44
答案解析：考核散列存储中同义词的基本概念
- 查找运算主要是对关键字的（ ）。
-
移位
-
交换
-
→比较←
-
定位
答案解析：查找运算主要是通过比较判断是否查找成功。
- 在待排关键字序列基本有序的前提下，效率最高的排序方法是( )。
-
→直接插入排序←
-
快速排序
-
直接选择排序
-
归并排序
答案解析：直接插入排序在序列基本有序的情况下，具有较好的排序效率。本题答案选A。
- 下列说法错误的是（）。
-
冒泡排序在数据有序的情况下具有最少的比较次数。
-
直接插入排序在数据有序的情况下具有最少的比较次数。
-
二路归并排序需要借助O（n）的存储空间。
-
→**基数排序适合于实型数据的排序。**←
答案解析：考核各种排序的基本思想
- 若对下面无向图进行深度优先遍历，得到的正确遍历序列是
-
h,c,a,b,d,e,g,f
-
e,a,f,g,b,h,c,d
-
d,b,c,a,h,e,f,g
-
→a,b,c,d,h,e,f,g←
答案解析：按照无向图进行深度优先遍历算法，选项A中访问完顶点c后，不能访问a；选项B中访问完顶点a后，不能访问f；选项C中访问完顶点c后，不能访问a。
- 有数据{53，30，37，12，45，24，96}，从空二叉树开始逐步插入数据形成二叉排序树，若希望高度最小，则应该选择下列（）的序列输入。
-
→37,24,12,30,53,45,96←
-
45,24,53,12,37,96,30
-
12,24,30,37,45,53,96
-
30,24,12,37,45,96,53
答案解析：考核二叉排序树的建立算法
- 适用于折半查找的表的存储方式及元素排列要求为（）。
-
链式方式存储，元素无序
-
链式方式存储，元素有序
-
顺序方式存储，元素无序
-
→顺序方式存储，元素有序←
答案解析：考核折半查找的基本概念
- 若需在O（nlogn）的时间内完成对数组的排序，且要求排序算法是稳定的，则可选择的排序方法是（）。
-
堆排序
-
→归并排序←
-
快速排序
-
直接插入排序
答案解析：考核各种排序算法的稳定性与时间复杂度
- 排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ）。
-
选择排序
-
快速排序
-
冒泡排序
-
→插入排序←
答案解析：选择排序，快速排序和冒泡排序在一趟排序后有一个元素可以确定其最终位置。而插入排序是将一个数据插入到有序树的适当位置，这个位置不一定是最终的位置。
- 下列选项中，既能在顺序存储结构也能在链式存储结构上进行查找的方法是
-
散列查找
-
→顺序查找←
-
二分查找
-
以上选项均不能
答案解析：能在顺序存储结构也能在链式存储结构上进行查找的方法是顺序查找。
- 在下列算法中，（）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。
-
堆排序
-
→插入排序←
-
冒泡排序
-
快速排序
答案解析：本题考核插入排序的基本思想。
- 希尔排序的增量序列必须是（ ）。
-
递增的
-
随机的
-
→递减的←
-
非递减的
答案解析：希尔排序是一种改进的插入排序，要求增量序列必须递减的。
- 对一组数据(2，12，16，88，5，10)进行排序，若前3趟排序结果如下：第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88则采用的排序方法是
-
→冒泡排序←
-
希尔排序
-
归并排序
-
基数排序
答案解析：第一趟排序结果显示最大元素88到了最后一个位置，第二趟排序结果显示第二大元素16到了倒数第2个位置，第三趟排序结果显示第3大元素12到了倒数第3个位置。初步判断是冒泡排序。在按照冒泡排序的原理分析每一趟的排序，显示是按照冒泡排序进行的。
- 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为( )。
-
(19，23，56，34，78，67，88，92)
-
(23，56，78，66，88，92，19，34)
-
(19，23，34，56，67，78，88，92)
-
→**(19，23，67，56，34，78，92，88)**←
答案解析：本题考核希尔排序的基本思想。
- 一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（）方法。
-
快速排序
-
→堆排序←
-
插入排序
-
二路归并排序
答案解析：本题考核堆排序的基本特点。
- 如果某二叉树的前序遍历序列为abced，中序遍历序列为cebda，则该二叉树的后序遍历序列是
-
cedba
-
decba
-
→ecdba←
-
ecbad
答案解析：根据前序遍历序列和中序遍历序列可以恢复二叉树，如图所示。
对该二叉树的后序遍历序列为：ecdba。
- 设二叉排序树中关键字由1至1000的整数构成，现要检索关键字为363的结点，下述关键字序列哪一个不可能是二叉排序树上搜索到的序列（ ）。
-
2， 252， 401， 398， 330， 344， 397， 363
-
924， 220， 911， 244， 898， 258， 362， 363
-
→952， 202， 911， 240， 912， 245， 363←
-
2， 399， 387， 219， 266， 382， 381， 278， 363
答案解析：本题考核二分查找的基本思想。
- 在一棵5阶B树中，每个非根结点中所含关键字的个数最少是
-
1
-
→2←
-
3
-
4
答案解析：每个非根结点中所包含的关键字个数满足：
- 在下列各棵二叉树中，二叉排序树是()。
- A
- →B←
- C
- D
- 已知广义表LS=(((a))，((b，(c))，(d，(e，f)))，())，LS的长度是
-
2
-
→3←
-
4
-
5
答案解析：广义表LS有3个元素：((a))、((b，(c))，(d，(e，f)))和()，所以其长度是3。
- 线性表适合于顺序查找的存储结构是（ ）。
-
索引存储
-
压缩存储
-
→顺序存储或链式存储←
-
散列存储
答案解析：顺序存储或链式存储都可以采用顺序查找。
- 若用一个大小为7的数组作为循环队列的存储结构，且当前rear和front的值分别为2和4，在此之前的操作是从队列中删除了一个元素及加入两个元素，请问这3个操作之前rear和front的值分别是
-
0和1
-
→0和3←
-
3和6
-
4和5
答案解析：从队列中删除元素的操作要改变front的值，往队中加入元素要改变rear的值。本题在此之前的操作是从队列中删除了一个元素，说明front进行了front=（front+1）%7操作，front现在的值是4，则这个操作之前front的值是3。在此之前的操作往队里加入两个元素，则rear进行了rear=（rear+1）%7操作，rear现在的值是2，则这个操作之前rear的值是0。
- 已知一组关键字为{[25,48],[36,72],[79,82],[23,40],[16,35]}，其中每相邻两个为有序子序列。采用归并排序对这些子序列进行一趟两两归并的结果是( )。
-
→**{25,36,48,72,23,40,79,82,16,35}**←
-
答案解析：本题考核归并排序的基本思想。
- 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上的是
-
A插入排序
-
B希尔排序
-
C归并排序
-
→D直接选择排序←
答案解析：直接选择排序基本思想是：每次从待排序的无序区中选择出关键字值最小的记录，将该记录与该区中的第一个记录交换位置。初始时，R[1…n]为无序区，有序区为空。第一趟排序是在无序区R[1…n]中选出最小的记录，将它与R[1]交换，R[1]为有序区；第二趟排序是在无序区R[2…n]中选出最小的记录与R[2]交换，此时R[1…2]为有序区；依此类推，做n-1趟排序后，区间R[1…n]中记录递增有序。
- 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（）。
-
→插入排序←
-
归并排序
-
冒泡排序
-
堆排序
答案解析：本题考核直接插入排序的基本概念。
¶ 平时测验4
- 一棵二叉排序树中，关键字n所在结点是关键字m所在结点的祖先，则
-
n一定大于m
-
n一定小于m
-
n一定等于m
-
→n与m的大小关系不确定←
答案解析：由二叉排序树定义可知，其右子树上所有结点的值均大于根结点的值，则左子树上所有结点的值均小于根结点的值，因为题目中m和n并没有给出是左子树还是右子树，所以大小关系不确定。
- 下列选项中，与数据存储结构直接相关的是
-
线性表
-
→双向链表←
-
二叉树
-
有向图
答案解析：双向链表的每个节点中储存有两个指针，这两个指针分别指向前一个节点的地址和后一个节点的地址，这样无论通过那个节点都能够寻找到其他的节点。线性表、二叉树和有向图需要查找某一个元素时，都必须从第一个元素开始进行查找。
- 若从顶点a开始对下图进行广度优先遍历，则不可能得到的遍历序列是
-
a，b，c，e，f，d
-
a，c，b，e，f，d
-
→a，c，e，b，d，f←
-
a，e，b，c，f，d
答案解析：广度优先搜索的基本思想：先访问出发点Vi，接着依次访问Vi的所有未被访问接点Vi1，Vi2……，并标记为已经访问，然后再按照Vi1，Vi2……的次序访问每一个顶点的所有未曾访问的顶点半标记为访问。答案的4个选项都以顶点a为出发点，b,c,e的顺序可以任意，但d,f的顺序受e,c被访问的先后顺序影响，答案C中，以a为出发点，接点是c,e,b,因为先访问的C，那么下一步要先访问f，才能再访问d,这个顺序不正确，所以答案为C。
- 用邻接矩阵表示有n个顶点和e条边的无向图，采用压缩方式存储，矩阵中零元素的个数是
-
→n(n+1)/2-e←
-
n(n+1)/2—2e
-
n×n-e
-
n×n一2e
答案解析：有n个顶点的无向图的邻接矩阵一共有n*n个元素，由于是对称矩阵，采用压缩存储，共存储n(n+1)/2个元素，其中只有e个元素是非零元素，其他都是零元素，共n(n+1)/2-e个。
- 设指针变量head指向非空单循环链表的头结点,指针变量p指向终端结点,next是结点的指针域,则下列逻辑表达式中,值为真的是
-
p->next->next==head
-
→p->next==head←
-
p->next->next==NULL
-
p->next==NULL
答案解析：循环单链表的特点就是最后一个结点的指针不为空，而是指向链表的头结点。
- 设一组记录的关键字为{12，22，10，20，88，27，54，11}，散列函数为H(key)=key%11，用拉链法解决冲突，则散列地址为0的链中结点数是
-
1
-
2
-
→3←
-
4
答案解析：散列地址为0的结点即是关键字可以整除11，记录中，22，88，11都可以整除11，所以结点数为3，答案为C。
- 设散列表长m=14，散列函数H（key）=key％11。表中己保存4个关键字：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址均为空。保存关键字49时存在冲突，采用线性探查法来处理。则查找关键字49时的探查次数是
-
1
-
2
-
→4←
-
8
答案解析：h(49)=5,散列地址5已经被占，因此探查h1=(5+1)%11=6,但散列地址6也已经被占，再探查h2=(6+1)%11=7,散列地址7也被占了，再探查h3=(7+1)%11=8,此地址是开放的，可将49插入。
- 下列叙述中，不正确的是
-
→算法解决的只能是数值计算问题←
-
同一问题可以有多种不同算法
-
算法的每一步操作都必须明确无歧义
-
算法必须在执行有限步后结束
答案解析：本题可以用排除法，算法的5个准则：有穷性，即算法中每一条指令的执行次数都是有限的。确定性：算法中每一条指令的含义都必须明确，无二义性。同一个问题可以用多种算法。BCD都是正确的，答案是A。
- 若完全二叉树T包含20个终端结点，则T的结点数最多是
-
38
-
39
-
→40←
-
41
答案解析：由完全二叉树定义可知，在完全二叉树中除最下面一层外，各层结点都达到最大值，每一层上结点个数恰好是上一层结点个数的2倍。所以答案为C。
- 广义表（（a，b），（c，d））的表尾是
-
b
-
d
-
（c，d）
-
→**（（c，d））**←
答案解析：当表为非空时，称第一个元素是表头，其余元素组成的表称为表尾，该题的表头是（a,b）,表尾是（（c,d））,答案为D。
- 已知广义表LS=(((a,b)),((c,(d)),(e,f))),(g,h)),LS的深度是
-
2
-
3
-
→4←
-
5
答案解析：一个表展开后所含括号的层数称为广义表的深度。即表中每个元素的括号匹配数加1
- 下列排序方法中，稳定的排序方法是
-
希尔排序
-
→归并排序←
-
堆排序
-
快速排序
答案解析：这个题考查各种排序方法的稳定性，教材190页内部排序方法的分析与比较中总结到，直接插入、冒泡、归并、基数排序算法是稳定的，直接选择、希尔、快速、堆排序算法是不稳定的
- 设栈的入栈序列为12345经过入、出栈操作后，可能得到的出栈序列是
-
23514
-
42135
-
34125
-
→34215←
答案解析：栈的特点：后进先出。答案D正确。进出顺序为：1进2进3进3出4进4出2出1出5进5出。其他选项均违背了后进先出的原则。
- 无向图G中所有顶点的度数之和是20，则G中的边数是
-
→10←
-
20
-
30
-
40
答案解析：一条边是2度，20除以2等于10条边。
- 下列排序算法中，比较操作的次数与待排序序列初始排列状态无关的是
-
快速排序
-
→直接选择排序←
-
泡排序
-
直接插入排序
答案解析：教材191页排序方法的选取一节中讲到，关键字比较次数与记录的初始排列顺序无关的排序方法是选择排序。故答案选B。
- 若图G是一个含有n个顶点的强连通有向图，则G的边数至少是
-
n-1
-
→n←
-
n*(n+1)/2
-
n*(n+l)
答案解析：强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径及v2到v1的路径的图。最少的情况：即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有n条边。
- 对数据序列（25，15，7，18，10，0，4）采用直接插入排序进行升序排序，两趟排序后，得到的排序结果为
-
0，4，7，18，10，25，15
-
O，4，25，15，7，18，10
-
7，15，10，O，4，18，25
-
→7，15，25，18，10，O，4←
答案解析：初始【25】【15，7，18，10，0，4】第一趟【15，25】【7，18，10，0，4】第二趟【7，15，25】【18，10，0，4】
- 已知一棵高度为4的完全二叉树T共有5个叶结点,则T中结点个数最少是
-
→9←
-
10
-
11
-
12
答案解析：深度为4的二叉树，其前3层是一棵满二叉树，至少得有7个结点，而题目中结出有5个是叶子结点，那么第三层的结点中得有一个得有左右子结点，这要T中结点个数至少是9个。
- 下列排序算法中，稳定的是
-
堆排序
-
直接选择排序
-
→冒泡排序←
-
希尔排序
答案解析：这个题考查各种排序方法的稳定性，教材190页内部排序方法的分析与比较中总结到，直接插入、冒泡、归并、基数排序算法是稳定的，直接选择、希尔、快速、堆排序算法是不稳定的，所以答案为C。
- 对下面的二叉树进行中序线索化后，结点f的右指针指向的结点是
-
a
-
b
-
c
-
→e←
答案解析：中序遍历的操作顺序：左子树，根结点，右子树。答案为D。
- 设有向图G含有n个顶点、e条边，使用邻接表存储。对G进行广度优先遍历的算法的时间复杂度是
-
O(n)
-
O(e)
-
→**O(n+e)**←
-
O(n×e)
答案解析：邻接表存储的有向图进行广度优先遍历的时间复杂度与图中的顶点个数以及边数都相关
- 一组记录的关键码为(45，68，57，13，24，89)，利用堆排序算法进行升序排序，建立的初始堆为
-
68，45，57，13，24，89
-
→89，68，57，13，24，45←
-
89，68，57，45，24，13
-
89，57，68，24，45，13
答案解析：根据教材183页堆排序定义，建堆过程如下：
-
在下面3阶B树中插入关键字65后，其根结点内的关键字是
-
5390
-
53
-
90
-
→65←
答案解析：在B树中插入一个结点的过程：先在最低层的某个非终端结点中添加一个关键字。若该结点中关键字的个数不超过m-1，则插入完成，否则要产生结点“分裂”。“分裂”结点时把结点分成两个，将中间的一个关键字拿出来插入到该结点的双亲结点上，如果双亲结点中已有m-1个关键字，则插入后将引起双亲结点的分裂，这一过程可能波及B树的根结点，引起根结点的分裂，从而使B树长高一层。具体过程：因为65介于61和70之间，所以插到该节点中，但插入后节点数超过了2，所以要分裂，把65拿到双新结点中，同时61和70分成两个结点，但这时53和90这个结点中因为插入了65，关键字超过了3，也要分裂，65升为双亲结点，53和90分成两个结点。所以该题答案为D。
- 设栈的初始状态为空,元素123456依次入栈,栈的容量是3能够得到的出栈序列是
-
126435
-
→243651←
-
312546
-
326514
答案解析：栈的特点：后进先出，且容量为3.答案B的顺序为：1进，2进，2出，3进，4进，4出，3出，5进，6进，6出，5出，1出。
- 若对二叉排序树进行遍历，则下列遍历方式中，其遍历结果为递增有序的是
-
前序遍历
-
→中序遍历←
-
后序遍历
-
按层遍历
答案解析：根据二叉排序树的定义它的右子树非空，则右子树上的所有结点的值均大于根结点的值，若它的左子树为非空，则左子树上所有结点的值均小于根结点的值，左、右子树本身又是一棵二叉排序树。因为中序遍历是先左子树，再根结点，再右子树，所以按中序遍历二叉排序树所得到的遍历序列是一个递增有序序列。