(1)（）_考试资料网

单项选择题

若push、pop分别表示入栈、出栈操作，初始栈为空且元素1、2、3依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为______。

A．321
B．213
C．231
D．123

单项选择题

栈和队列的共同点是______。

A．都是先进先出
B．都是先进后出
C．只允许在端点处插入和删除元素
D．没有共同点

单项选择题

在深度为5的满二叉树中，结点的个数为______。

A．32
B．31
C．16
D．15

单项选择题

对长度为n的线性表进行顺序查找，在最坏情况下，所需要的比较次数为（）

A．1og₂n
B．n/2
C．n
D．n+1

单项选择题

对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 ______。

A．冒泡排序为n/2
B．冒泡排序为n
C．快速排序为n
D．快速排序为n(n-1)/2

单项选择题

下列叙述中正确的是（）

A．数据的逻辑结构与存储结构必定是一一对应的
B．由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构
C．程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构
D．以上三种说法都不对

单项选择题

在深度为7的满二叉树中，叶子结点的个数为（）

A．32
B．31
C．64
D．63

单项选择题

已知N个数已存入数组A[1..M]的前N个元素中(N＜M)，为在A[i](1≤i≤N)之前插入一个新数，应先（），以挪出一个空闲位置插入该数。

A．从A开始直到A[1]，每个数向后移动一个位置
B．从A[1]开始直到A，每个数向后移动一个位置
C．从A开始直到A，每个数向前移动一个位置
D．从A开始直到A，每个数向后移动一个位置

单项选择题

数据结构主要研究数据的______。

A．逻辑结构
B．存储结构
C．逻辑结构和存储结构
D．逻辑结构和存储结构及其运算的实现

单项选择题

假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为（）

A．ABCDEFGHIJ
B．ABDEGHJCFI
C．ABDEGHJFIC
D．ABDEGJHCFI

单项选择题

采用哈希(或散列)技术构造查找表时，需要考虑冲突(碰撞)的处理，冲突是指______。

A．关键字相同的记录被映射到不同的哈希地址
B．关键字依次被映射到编号连续的哈希地址
C．关键字不同的记录被映射到同一个哈希地址
D．关键字的数目超过哈希地址的数目

单项选择题

广度优先遍历的含义是：从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。（）是图8-32的广度优先遍历序列。

A．1 2 6 3 4 5
B．1 2 3 4 5 6
C．1 6 5 2 3 4
D．1 6 4 5 2 3

单项选择题

若二维数组P[1..5,0..8]的首地址为base，数组元素按行存储，且每个元素占用1个存储单元，则元素P[3,3]在该数组空间的地址为______。

A．base+13
B．base+16
C．base+18
D．base+21

单项选择题

数据结构中的树最适合用来表示______的情况。

A．数据元素有序
B．数据元素之间具有多对多关系
C．数据元素无序
D．数据元素之间具有一对多关系

单项选择题

设数组a[1..3，1..4]中的元素以列为主序存放，每个元素占用1个存储单元，则数组元素a[2，3]相对于数组空间首地址的偏移量为（）

A．6
B．7
C．8
D．9

单项选择题

设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）

A．6
B．4
C．3
D．2

单项选择题

堆栈操作中，______保持不变。

A．堆栈的顶
B．堆栈中的数据
C．堆栈指针
D．堆栈的底

单项选择题

以下关于字符串的判定语句中正确的是______。

A．字符串是一种特殊的线性表
B．串的长度必须大于零
C．字符串不属于线性表的一种
D．空格字符组成的串就是空串

单项选择题

以下各图用树结构描述了7个元素之间的逻辑关系，其中，（）适合采用二分法查找元素。

A．
B．
C．
D．

单项选择题

已知有一维数组T[0..m*n-1]，其中m＞n。从数组T的第一个元素(T[0])开始，每隔n个元素取出一个元素依次存入数组B[1..m]中，即B[1]=T[0]，D[2]=T[n]，依此类推，那么放入B[k](1≤k≤n)的元素是______。

A．T[(k-1)*n]
B．T(k*
C．T[(k-1)*m]
D．T[k*m]

填空题

设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为（）

答案： ACBEGFD

单项选择题

在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是______。

A．直接插入排序
B．冒泡排序
C．简单选择排序
D．归并排序

单项选择题

为了用一个数代表一批数，人们常用这批数据的算术平均值(简称平均值)或中位数来代表。中位数就是位于这批数中间的数(大于它的数与小于它的数一样多)。对于奇数个数而言，排序后很容易确定中间那个数；对于偶数个数而言，排序后中间会有两个数，再取这两个数的算术平均，就是中位数。以下关于平均值与中位数的叙述中，______是不正确的。

A．中位数比平均值稳健，不易受极端值影响
B．每个数据加倍后，平均值也加倍；每个数据增加1后，平均值也增加1
C．三组各有n个数据有三个中位数，它们的中位数就是这三组数据全体的中位数
D．三组各有n个数据有三个平均值，它们的平均值就是这三组数据全体的平均值

单项选择题

数组A[-5..5,0..8]按列存储。若第一个元素的首地址为100，且每个元素占用4个存储单元，则元素A[2,3]的存储地址为______。

A．244
B．260
C．364
D．300

单项选择题

判断“链式队列为空”的条件是______(front为头指针，rear为尾指针)。

A．front==NULL
B．rear==NULL
C．front==rear
D．front!=rear

单项选择题

某二叉树中度为2的结点有18个，则该二叉树中有______个叶子结点。

A．18
B．19
C．8
D．20

单项选择题

若线性表(23,14,45,12,8,19,7)采用散列法进行存储和查找。设散列函数为 H(Key)=Key mod 7并采用线性探查法(顺序地探查可用存储单元)解决冲突，则构造的散列表为______，其中，mod表示整除取余运算。

A．哈希地址 0 1 2 3 4 5 6 关键字 14 8 23 45 7 12 19
B．哈希地址 0 1 2 3 4 5 6 关键字 7 8 12 14 19 23 45
C．哈希地址 0 1 2 3 4 5 6 关键字 7 8 23 45 12 19 14
D．哈希地址 0 1 2 3 4 5 6 关键字 14 7 12 8 45 23 19

单项选择题

下面的排序方法中，关键字比较次数与记录的初始排列无关的是______。

A．希尔排序
B．冒泡排序
C．直接插入排序
D．直接选择排序

单项选择题

无向图的邻接矩阵一定是（）

A．对角矩阵
B．稀疏矩阵
C．三角矩阵
D．对称矩阵

单项选择题

在具有100个结点的树中，其边的数目为______。

A．101
B．100
C．99
D．98

单项选择题

在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为______。

A．63
B．64
C．6
D．7

单项选择题

下面叙述不正确的是______。

A．算法的执行效率与数据的存储结构有关
B．算法的空间复杂度是指执行这个算法所需要的内存空间
C．算法的有穷性是指算法必须能在执行有限个步骤之后终止
D．算法的时间复杂度是指执行这个算法所需要的时间

单项选择题

设有100个结点，用二分法查找时，最大比较次数是______。

A．25
B．50
C．10
D．7

单项选择题

在排序算法中每一项都与其他诸项进行比较，计算出小于该项的项的个数，以确定该项的位置叫______。

A．插入排序
B．交换排序
C．选择排序
D．枚举排序

单项选择题

设最优的分配方案为完成这三项工作所需的总天数最少，则在最优分配方案中，（）

A．甲执行P
B．甲执行Q
C．乙执行P
D．乙执行R

单项选择题

若需将一个栈S中的元素逆置，则以下处理方式中正确的是______。

A．将栈S中元素依次出栈并入栈T，然后栈T中元素依次出栈并进入栈S
B．将栈S中元素依次出栈并入队，然后使该队列元素依次出队并进入栈S
C．直接交换栈顶元素和栈底元素
D．直接交换栈顶指针和栈底指针

单项选择题

二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行______遍历，可得到一个结点元素的递增序列。

A．先序(根、左、右)
B．中序(左、根、右)
C．后序(左、右、根)
D．层序(从树根开始，按层次)

单项选择题

若原始数据序列(23,4,45,67,12,8,19,7)采用直接插入排序法(顺序地将每个元素插入到它之前的适当位置)排序，则进行完第4趟后的排序结果是______。

A．4,8,45,23,67,12,19,7
B．4,7,8,12,23,45,67,19
C．4,12,8,19,7,23,45,67
D．4,12,23,45,67,8,19,7

单项选择题

n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）

A．O(1)
B．O(1og₂
C．O(n²)
D．O(

单项选择题

在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为______。

A．63
B．64
C．6
D．7

单项选择题

对于n个元素的关键字序列{k₁,k₂,…,k_n}，若将其按次序对应到一棵具有n个结点的完全二叉树上，使得任意结点都不大于其孩子结点(若存在孩子结点)，则称其为小顶堆。根据以上定义，（）是小顶堆。

A.
B.
C.
D.

单项选择题

对图8-16所示的二叉树进行中序遍历(左子树，根，右子树)的结果是（）

A．2 5 3 4 6 1
B．2 5 3 4 1 6
C．2 6 5 4 1 3
D．2 6 4 5 3 1

单项选择题

如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用______的方法。

A．分块
B．顺序
C．二分法
D．基于属性

单项选择题

若一个栈以向量V[1..n)存储，且空栈的栈顶指针top为n+1，则将元素x入栈的正确操作是______。

A．top=top+1；V[top]=x；
B．V[top]=x；top=top+1；
C．top=top-1；V[top]=x；
D．V[top]=x；top=top-1；

单项选择题

一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 ______。

A．219
B．221
C．229
D．231

单项选择题

如果待排序序列中两个元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。______是稳定的排序方法，因为这种方法在比较相邻元素时，值相同的元素并不进行交换。

A．冒泡排序
B．希尔排序
C．快速排序
D．简单选择排序

单项选择题

对于长度为11的顺序存储的有序表，若采用折半查找(向下取整)，则找到第5个元素需要与表中的______个元素进行比较操作(包括与第5个元素的比较)。

A．5
B．4
C．3
D．2

单项选择题

若in、out分别表示入、出队操作，初始队列为空且元素a、b、c依次入队，则经过操作序列in、in、out、out、in、out之后，得到的出队序列为（）

A．cba
B．bac
C．bca
D．abc

单项选择题

冒泡排序在最坏情况下的比较次数是（）

A．n(n+1)/2
B．nlog₂n
C．n(n-1)/2
D．n/2

单项选择题

在程序的执行过程中，用______结构可以实现嵌套调用函数的正确返回。

A．队列
B．栈
C．树
D．图

单项选择题

设有二叉树如图8-15所示。
对此二叉树先序遍历的结果为（）

A．ABCDEF
B．BDAECF
C．ABDCEF
D．DBEFCA

单项选择题

对具有n个元素的有序序列进行二分查找时，（）

A．查找元素所需的比较次数与元素的位置无关
B．查找序列中任何一个元素所需要的比较次数不超过log₂(n+1)
C．元素位置越靠近序列后端，查找该元素所需的比较次数越少
D．元素位置越靠近序列前端，查找该元素所需的比较次数越少

单项选择题

在下列算法中，______算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。

A．堆排序
B．冒泡排序
C．插入排序
D．快速排序

单项选择题

若线性表采用链式存储结构，则适用的查找方法为______。

A．随机查找
B．散列查找
C．二分查找
D．顺序查找

单项选择题

已知递归函数f(n)的功能是计算1+2+…+n，且n≥1，应采用的代码段是______。

A．if n＞1 then return 1 else return n+f(n-1)
B．if n＞1 then return 1 else return n+f(n+1)
C．if n＜1 then return 0 else return n+f(n-1)
D．if n＜1 then return 0 else return n+f(n+1)

单项选择题

与单向链表相比，双向链表______。

A．需要较少的存储空间
B．遍历元素需要的时间较长
C．较易于访问相邻结点
D．较易于插入和删除元素

单项选择题

在一棵非空二叉树中，叶子节点的总数比度为2的节点总数多 (43) 个。

A．-1
B．0
C．1
D．2

单项选择题

在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的排序算法是（）

A．冒泡排序
B．基数排序
C．快速排序
D．归并排序

单项选择题

下列数据结构中，能用二分法进行查找的是______

A．顺序存储的有序线性表
B．线性链表
C．二叉链表
D．有序线性链表

单项选择题

______是线性结构的数据结构。

A．列表
B．高维数组
C．双端队列
D．二叉树

单项选择题

字符串是一种线性表，其特殊性表现在______。

A．它的数据元素是一个字符
B．它可以链式存储
C．它可以顺序存储
D．它的数据元素可以是多个字符

单项选择题

下列对于线性链表的描述中正确的是______。

A．存储空间不一定连续，且各元素的存储顺序是任意的
B．存储空间不一定连续，且前件元素一定存储在后件元素的前面
C．存储空间必须连续，且前件元素一定存储在后件元素的前面
D．存储空间必须连续，且各元素的存储顺序是任意的

单项选择题

在最坏情况下，下列排序方法中时间复杂度最小的是______。

A．冒泡排序
B．快速排序
C．插入排序
D．堆排序

单项选择题

在数据结构中，结点(数据元素)及结点间的相互关系组成数据的逻辑结构。按逻辑结构的不同，数据结构通常可分为______两类。

A．线性结构和非线性结构
B．紧凑结构和稀疏结构
C．动态结构和静态结构
D．内部结构和外部结构

单项选择题

链表不具备的特点是______。

A．可随机访问任何一个元素
B．插入、删除操作不需要移动元素
C．无需事先估计存储空间大小
D．所需存储空间与线性表长度成正比

单项选择题

判断一个表达式中左右括号是否匹配，采用______实现较为方便。

A．线性表的顺序存储
B．队列
C．线性表的链式存储
D．栈

单项选择题

某循环队列的容量为M，队头指针指向队头元素，队尾指针指向队尾元素之后，如图 8-8所示(M=8)，则队列中的元素数目为（）(MOD表示整除取余运算)。

A．rear-front
B．front-rear
C．(rear-front+MODM
D．(front-rear+MODM

单项选择题

在链表结构中，采用（）可以用最少的空间代价和最高的时间效率实现队列结构。

A．仅设置尾指针的单向循环链表
B．仅设置头指针的单向循环链表
C．仅设置尾指针的双向链表
D．仅设置头指针的双向链表

单项选择题

从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为______。

A．插入排序
B．选择排序
C．希尔排序
D．归并排序

单项选择题

采用邻接表表示一有向图，若图中某顶点的入度和出度分别为d1和d2，则该顶点对应的单链表的结点数为______。

A．d1
B．d2
C．d1-d2
D．d1+d2

单项选择题

二叉树的查找有深度优先和广度优先二类，深度优先包括______。

A．前序遍历、后序遍历、中序遍历
B．前序遍历、后序遍历、层次遍历
C．前序遍历、中序遍历、层次遍历
D．中序遍历、后序遍历、层次遍历

单项选择题

在执行递归过程时，通常使用的数据结构是______。

A．堆栈(stac
B．队列(queu
C．图(grap
D．树(tre

单项选择题

PUSH和POP命令常用于______操作。

A．队列
B．数组
C．栈
D．记录

单项选择题

对图8-30所示的二叉树进行后序遍历(左子树，右子树，根)的结果是（）

A．5 2 3 4 6 1
B．5 2 3 4 1 6
C．2 6 4 1 3 5
D．2 5 6 4 3 1

单项选择题

数据的存储结构是指______。

A．数据所占的存储空间量
B．数据的逻辑结构在计算机中的表示
C．数据在计算机中的顺序存储方式
D．存储在外存中的数据

单项选择题

下列对于线性链表的描述中正确的是______。

A．存储空间不一定连续，且各元素的存储顺序是任意的
B．存储空间不一定连续，且前件元素一定存储在后件元素的前面
C．存储空间必须连续，且前件元素一定存储在后件元素的前面
D．存储空间必须连续，且各元素的存储顺序是任意的

单项选择题

为了描述n个人之间的同学关系，可用______结构表示。

A．线性表
B．树
C．图
D．队列

单项选择题

前序遍历序列与中序遍历序列相同的二叉树为 (1) ，前序遍历序列与后序遍历序列相同的二叉树为 (2) 。
(1)（）

A．根结点无左子树的二叉树
B．根结点无右子树的二叉树
C．只有根结点的二叉树或非叶子结点只有左子树的二叉树
D．只有根结点的二叉树或非叶子结点只有右子树的二叉树

单项选择题

堆排序是一种基于_（1）_的排序方法，_（2）_不是堆。
(1)（）

A．计数
B．插入
C．选择
D．归并

单项选择题

设有n个结点进行排序，不稳定排序是 (1) ；快速排序的最大比较次数是 (2) 。
(1)（）

A．直接插入排序
B．冒泡排序
C．Shell排序
D．归并排序

问答题

图的存储结构主要有邻接表和 (1) ，若用邻接表来存储一个图，则需要保存一个 (2) 存储的结点表和若干个 (3) 存储的关系表(又称边表)。 (1) （）

答案：

A．转移矩阵
B．邻接矩阵
C．状态矩阵
D．优先矩阵

单项选择题

在排序算法中，两两比较待排序的记录，当发现不满足顺序要求时，变更它们的相对位置，这就是 (1) 排序。每次从未排序的记录中挑出最小(或最大)关键码值的记录，加入到已排序记录的末尾，这是 (2) 排序。
(1)（）

A．插入
B．枚举
C．交换
D．归并
E．基数
F．选择
G．希尔

单项选择题

可以用栈来检查算术表达式中的括号是否匹配。分析算术表达式时，初始栈为空，从左到右扫描字符，遇到字符“(”就将其入栈，遇到“)”就执行出栈操作。对算术表达式“(a+b*(a+b))/c)+(a+b)”，检查时， (1) ；对算术表达式“((a+b/(a+b)-c/a)/b”，检查时， (2) 。这两种情况都表明所检查的算术表达式括号不匹配。

(1)（）

A．栈为空却要进行出栈操作
B．栈已满却要进行入栈操作
C．表达式处理已结束，栈中仍留下有字符“(”
D．表达式处理已结束，栈中仍留下有字符“)”

单项选择题

满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为h(h＞1)的满二叉树，其结点总数为 (1) 。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从1、2、3、…依次编号，则对于树中编号为i的非叶子结点，其右子树的编号为 (2) (高度为3的满二叉树如图8-17所示)。

(1)（）

A．2^h
B．2^h-1
C．2^h-1
D．2^h-1+1

问答题

图的存储结构主要有邻接表和 (1) ，若用邻接表来存储一个图，则需要保存一个 (2) 存储的结点表和若干个 (3) 存储的关系表(又称边表)。

(2) （）

答案：

A．顺序
B．链接
C．散列
D．分块

单项选择题

前序遍历序列与中序遍历序列相同的二叉树为 (1) ，前序遍历序列与后序遍历序列相同的二叉树为 (2) 。
(2)（）

A．非叶子结点只有左子树的二叉树
B．只有根结点的二叉树
C．根结点无右子树的二叉树
D．非叶子结点只有右子树的二叉树

单项选择题

设有n个结点进行排序，不稳定排序是 (1) ；快速排序的最大比较次数是 (2) 。
(2) （）

A．nlog₂n
B．n²
C．n²/2
D．n

单项选择题

对于二维数组a[1..4,3..6]，设每个元素占两个存储单元，若分别以行和列为主序存储，则元素a[3,4]相对于数组空间起始地址的偏移量分别是 (1) 和 (2) 。
(1)（）

A．12
B．14
C．16
D．18

单项选择题

在排序算法中，两两比较待排序的记录，当发现不满足顺序要求时，变更它们的相对位置，这就是 (1) 排序。每次从未排序的记录中挑出最小(或最大)关键码值的记录，加入到已排序记录的末尾，这是 (2) 排序。
(2)（）

A．插入
B．枚举
C．交换
D．归并
E．基数
F．选择
G．希尔

单项选择题

堆排序是一种基于_（1）_的排序方法，_（2）_不是堆。
(2)（）

A．15,28,25,56,68,63,30
B．15,28,25,30,68,63,56
C．68,28,63,25,15,56,30
D．68,56,39,63,28,25,15

单项选择题

满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为h(h＞1)的满二叉树，其结点总数为 (1) 。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从1、2、3、…依次编号，则对于树中编号为i的非叶子结点，其右子树的编号为 (2) (高度为3的满二叉树如图8-17所示)。

(2)（）

A．2i
B．2i-1
C．2i+1
D．2i+2

单项选择题

可以用栈来检查算术表达式中的括号是否匹配。分析算术表达式时，初始栈为空，从左到右扫描字符，遇到字符“(”就将其入栈，遇到“)”就执行出栈操作。对算术表达式“(a+b*(a+b))/c)+(a+b)”，检查时， (1) ；对算术表达式“((a+b/(a+b)-c/a)/b”，检查时， (2) 。这两种情况都表明所检查的算术表达式括号不匹配。
(2) （）

A．栈为空却要进行出栈操作
B．栈已满却要进行入栈操作
C．表达式处理已结束，栈中仍留下有字符“(”
D．表达式处理已结束，栈中仍留下有字符“)”

单项选择题

对于二维数组a[1..4,3..6]，设每个元素占两个存储单元，若分别以行和列为主序存储，则元素a[3,4]相对于数组空间起始地址的偏移量分别是 (1) 和 (2) 。
(2)（）

A．12
B．14
C．16
D．18

单项选择题

前序遍历序列与中序遍历序列相同的二叉树为 (1) ，前序遍历序列与后序遍历序列相同的二叉树为 (2) 。
(1)（）

A．1
B．2
C．5
D．15

单项选择题

二叉树 (1) 。在完全的二叉树中，若一个结点没有 (2) ，则它必定是叶结点。
每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子结点是N在原树里对应结点的 (3) ，而N的右子结点是它在原树里对应结点的 (4) 。
(1)（）

A．是特殊的树
B．不是树的特殊形式
C．是两棵树的总称
D．是只有两个根结点的树形结构

问答题

图的存储结构主要有邻接表和 (1) ，若用邻接表来存储一个图，则需要保存一个 (2) 存储的结点表和若干个 (3) 存储的关系表(又称边表)。

(3) （）

答案：

A．顺序
B．链接
C．散列
D．分块

单项选择题

设有n个结点进行排序，不稳定排序是 (1) ；快速排序的最坏时间是 (2) 。
(1)（）

A．直接插入排序
B．冒泡排序
C．希尔排序
D．归并排序

单项选择题

在直接插入排序、冒泡排序、简单选择排序和快速排序方法中，能在第一趟排序结束后就得到最大(或最小)元素的排序方法是（）

A．冒泡排序和快速排序
B．直接插入排序和简单选择排序
C．冒泡排序和简单选择排序
D．直接插入排序和快速排序

单项选择题

设W为一个二维数组，其每个数据元素占用6个字节，行下标范围从0到8，列下标范围从2到5，则二维数组W的数据元素共占用（）个字节。

A．480
B．192
C．216
D．144

填空题

阅读下列说明、流程图和算法进行填空。
下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4,2,8,3,6)，以4为基准数的划分过程如图8-34所示。
算法说明：将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[],int low,int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[],int L,int H)的功能是实现数组A中元素的递增排序。
算法如下。
void sort(int A[]，int L，int H) {
if (L＜H) {
k=p(A,L,H)； //p()返回基准数在数组A中的下标
sort( (4) )； //小于基准数的元素排序
sort( (5) )； //大于基准数的元素排序
}
}

（1）（）

答案：

j--

单项选择题

正规式(1|3|5)(202)(c|de)表示的正规集合中元素数目为 (1) ， (2) 是该正规集合中的元素。
(1)（）

A．6
B．7
C．8
D．无穷

单项选择题

前序遍历序列与中序遍历序列相同的二叉树为 (1) ，前序遍历序列与后序遍历序列相同的二叉树为 (2) 。

(2)（）

A.A
B.B
C.C
D.D

单项选择题

二叉树 (1) 。在完全的二叉树中，若一个结点没有 (2) ，则它必定是叶结点。
每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子结点是N在原树里对应结点的 (3) ，而N的右子结点是它在原树里对应结点的 (4) 。
(2)（）

A．左子结点
B．右子结点
C．左子结点或者没有右子结点
D．兄弟

单项选择题

设有n个结点进行排序，不稳定排序是 (1) ；快速排序的最坏时间是 (2) 。
(2)（）

A．O(nlog₂
B．O(n²)
C．O(n²/2)
D．O(

单项选择题

正规式(1|3|5)(202)(c|de)表示的正规集合中元素数目为 (1) ， (2) 是该正规集合中的元素。
(2)（）

A．135202cde
B．1202c
C．302cde
D．52c

填空题

阅读下列说明、流程图和算法进行填空。
下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4,2,8,3,6)，以4为基准数的划分过程如图8-34所示。
算法说明：将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[],int low,int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[],int L,int H)的功能是实现数组A中元素的递增排序。
算法如下。
void sort(int A[]，int L，int H) {
if (L＜H) {
k=p(A,L,H)； //p()返回基准数在数组A中的下标
sort( (4) )； //小于基准数的元素排序
sort( (5) )； //大于基准数的元素排序
}
}
（2）（）

答案： i++

单项选择题

现需要将数字2和7分别填入6个空格中的2个(每个空格只能填入一个数字)，已知第1格和第2格不能填7，第6格不能填2，则共有（）种填法。

A．12
B．16
C．17
D．20

单项选择题

设W为二维数组，其中每个数据元素占用6个字节，行下标i从0到8 ，列下标j从2到5,W中第6行的元素和第4列的元素共占用（）个字节。

A．78
B．72
C．66
D．84

单项选择题

二叉树 (1) 。在完全的二叉树中，若一个结点没有 (2) ，则它必定是叶结点。
每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子结点是N在原树里对应结点的 (3) ，而N的右子结点是它在原树里对应结点的 (4) 。
(3)（）

A．最左子结点
B．最右子结点
C．最邻近的右兄弟
D．最邻近的左兄弟
E．最左的兄弟最右的兄弟

填空题

阅读下列说明、流程图和算法进行填空。
下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4,2,8,3,6)，以4为基准数的划分过程如图8-34所示。
算法说明：将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[],int low,int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[],int L,int H)的功能是实现数组A中元素的递增排序。
算法如下。
void sort(int A[]，int L，int H) {
if (L＜H) {
k=p(A,L,H)； //p()返回基准数在数组A中的下标
sort( (4) )； //小于基准数的元素排序
sort( (5) )； //大于基准数的元素排序
}
}

（3）（）

答案： A[i]←pivot 或 A[j]←pivot

单项选择题

许多工作需要用曲线来拟合平面上一批离散的点，以便于直观了解趋势，也便于插值和预测。例如，对平面上给定的n个离散点（（Xi，Yi）｜i=1，…，n），先依次将每4个点分成一组，并且前一组的尾就是后一组的首；再对每一组的4个点，确定一段多项式函数曲线使其通过这些点。一般来说，通过给定的4个点可以确定一条（）次多项式函数曲线恰好通过这4个点。

A．2
B．3
C．4
D．5

单项选择题

设W为二维数组，其中每个数据元素占用6个字节，行下标i从0到8，列下标j从2到5，若按行顺序存放W，其起始地址的字节号为100，则W的最后一个数据元素的起始地址的字节号为（）

A．310
B．311
C．315
D．314

单项选择题

二叉树 (1) 。在完全的二叉树中，若一个结点没有 (2) ，则它必定是叶结点。
每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子结点是N在原树里对应结点的 (3) ，而N的右子结点是它在原树里对应结点的 (4) 。
(4)（）

A．最左子结点
B．最右子结点
C．最邻近的右兄弟
D．最邻近的左兄弟
E．最左的兄弟最右的兄弟

单项选择题

设A是n*n常数矩阵(n＞1)，X是由未知数X1，X2，…，Xn组成的列向量，B是由常数b1，b2，…，bn组成的列向量，线性方程组AX=B有唯一解的充分必要条件不是（）

A．A的秩等于n
B．A的秩不等于0
C．A的行列式值不等于0
D．A存在逆矩阵

填空题

阅读下列说明、流程图和算法进行填空。
下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4,2,8,3,6)，以4为基准数的划分过程如图8-34所示。
算法说明：将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[],int low,int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[],int L,int H)的功能是实现数组A中元素的递增排序。
算法如下。
void sort(int A[]，int L，int H) {
if (L＜H) {
k=p(A,L,H)； //p()返回基准数在数组A中的下标
sort( (4) )； //小于基准数的元素排序
sort( (5) )； //大于基准数的元素排序
}
}
（4）（）

答案： A, L, k-A

单项选择题

某研究机构有n名研究人员（n＞2），其每个人都与一名以上的同事有过研究项目合作关系，那么用（）结构表示该机构研究人员间的项目合作关系较为合适。

A．树
B．图
C．栈
D．队列

填空题

阅读下列说明、流程图和算法进行填空。
下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4,2,8,3,6)，以4为基准数的划分过程如图8-34所示。
算法说明：将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[],int low,int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[],int L,int H)的功能是实现数组A中元素的递增排序。
算法如下。
void sort(int A[]，int L，int H) {
if (L＜H) {
k=p(A,L,H)； //p()返回基准数在数组A中的下标
sort( (4) )； //小于基准数的元素排序
sort( (5) )； //大于基准数的元素排序
}
}
（5）（）

答案： A, k+A,H

设有n个结点进行排序，不稳定排序是 (1) ；快速排序的最坏时间是 (2) 。 (1)（）

你可能感兴趣的试题

若push、pop分别表示入栈、出栈操作，初始栈为空且元素1、2、3依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为______。

栈和队列的共同点是______。

在深度为5的满二叉树中，结点的个数为______。

对长度为n的线性表进行顺序查找，在最坏情况下，所需要的比较次数为（）

对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 ______。

下列叙述中正确的是（）

一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i(1≤i≤n)个元素是______。

用二分法来检索数据，最确切的说法是______。

n个元素依次全部进入栈后，再陆续出栈并经过一个队列输出。那么，______。

设初始栈为空，s表示入栈操作，x表示出栈操作，则______是合法的操作序列。

设栈S初始状态为空。元素a、b、c、d、e、f依次通过栈S，若出栈的顺序为c、f、 e、 d、b、a，则栈S的容量至少应该为______。

以下数据结构中属于线性数据结构的是______。

对长度为n的线性表排序，在最坏的情况下，比较次数不是n(n-1)/2的排序方法是______。

在深度为7的满二叉树中，叶子结点的个数为（）

已知N个数已存入数组A[1..M]的前N个元素中(N＜M)，为在A[i](1≤i≤N)之前插入一个新数，应先（），以挪出一个空闲位置插入该数。

数据结构主要研究数据的______。

假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为（）

采用哈希(或散列)技术构造查找表时，需要考虑冲突(碰撞)的处理，冲突是指______。

若二维数组P[1..5,0..8]的首地址为base，数组元素按行存储，且每个元素占用1个存储单元，则元素P[3,3]在该数组空间的地址为______。

数据结构中的树最适合用来表示______的情况。

设数组a[1..3，1..4]中的元素以列为主序存放，每个元素占用1个存储单元，则数组元素a[2，3]相对于数组空间首地址的偏移量为（）

设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）

堆栈操作中，______保持不变。

以下关于字符串的判定语句中正确的是______。

以下各图用树结构描述了7个元素之间的逻辑关系，其中，（）适合采用二分法查找元素。

已知有一维数组T[0..m*n-1]，其中m＞n。从数组T的第一个元素(T[0])开始，每隔n个元素取出一个元素依次存入数组B[1..m]中，即B[1]=T[0]，D[2]=T[n]，依此类推，那么放入B[k](1≤k≤n)的元素是______。

设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为（）

在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是______。

数组A[-5..5,0..8]按列存储。若第一个元素的首地址为100，且每个元素占用4个存储单元，则元素A[2,3]的存储地址为______。

判断“链式队列为空”的条件是______(front为头指针，rear为尾指针)。

某二叉树中度为2的结点有18个，则该二叉树中有______个叶子结点。

若线性表(23,14,45,12,8,19,7)采用散列法进行存储和查找。设散列函数为 H(Key)=Key mod 7并采用线性探查法(顺序地探查可用存储单元)解决冲突，则构造的散列表为______，其中，mod表示整除取余运算。

下面的排序方法中，关键字比较次数与记录的初始排列无关的是______。

无向图的邻接矩阵一定是（）

在具有100个结点的树中，其边的数目为______。

在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为______。

下面叙述不正确的是______。

设有100个结点，用二分法查找时，最大比较次数是______。

在排序算法中每一项都与其他诸项进行比较，计算出小于该项的项的个数，以确定该项的位置叫______。

设最优的分配方案为完成这三项工作所需的总天数最少，则在最优分配方案中，（）

若需将一个栈S中的元素逆置，则以下处理方式中正确的是______。

若原始数据序列(23,4,45,67,12,8,19,7)采用直接插入排序法(顺序地将每个元素插入到它之前的适当位置)排序，则进行完第4趟后的排序结果是______。

n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）

在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为______。

对于n个元素的关键字序列{k1,k2,…,kn}，若将其按次序对应到一棵具有n个结点的完全二叉树上，使得任意结点都不大于其孩子结点(若存在孩子结点)，则称其为小顶堆。根据以上定义，（）是小顶堆。

对图8-16所示的二叉树进行中序遍历(左子树，根，右子树)的结果是（）

如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用______的方法。

若一个栈以向量V[1..n)存储，且空栈的栈顶指针top为n+1，则将元素x入栈的正确操作是______。

一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 ______。

如果待排序序列中两个元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。______是稳定的排序方法，因为这种方法在比较相邻元素时，值相同的元素并不进行交换。

对于长度为11的顺序存储的有序表，若采用折半查找(向下取整)，则找到第5个元素需要与表中的______个元素进行比较操作(包括与第5个元素的比较)。

若in、out分别表示入、出队操作，初始队列为空且元素a、b、c依次入队，则经过操作序列in、in、out、out、in、out之后，得到的出队序列为（）

冒泡排序在最坏情况下的比较次数是（）

在程序的执行过程中，用______结构可以实现嵌套调用函数的正确返回。

设有二叉树如图8-15所示。 对此二叉树先序遍历的结果为（）

对具有n个元素的有序序列进行二分查找时，（）

在下列算法中，______算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。

若线性表采用链式存储结构，则适用的查找方法为______。

已知递归函数f(n)的功能是计算1+2+…+n，且n≥1，应采用的代码段是______。

与单向链表相比，双向链表______。

在一棵非空二叉树中，叶子节点的总数比度为2的节点总数多 (43) 个。

在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的排序算法是（）

下列数据结构中，能用二分法进行查找的是______

______是线性结构的数据结构。

字符串是一种线性表，其特殊性表现在______。

下列对于线性链表的描述中正确的是______。

在最坏情况下，下列排序方法中时间复杂度最小的是______。

在数据结构中，结点(数据元素)及结点间的相互关系组成数据的逻辑结构。按逻辑结构的不同，数据结构通常可分为______两类。

链表不具备的特点是______。

判断一个表达式中左右括号是否匹配，采用______实现较为方便。

某循环队列的容量为M，队头指针指向队头元素，队尾指针指向队尾元素之后，如图 8-8所示(M=8)，则队列中的元素数目为（）(MOD表示整除取余运算)。

在链表结构中，采用（）可以用最少的空间代价和最高的时间效率实现队列结构。

从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为______。

采用邻接表表示一有向图，若图中某顶点的入度和出度分别为d1和d2，则该顶点对应的单链表的结点数为______。

二叉树的查找有深度优先和广度优先二类，深度优先包括______。

在执行递归过程时，通常使用的数据结构是______。

PUSH和POP命令常用于______操作。

对图8-30所示的二叉树进行后序遍历(左子树，右子树，根)的结果是（）

设有n个结点进行排序，不稳定排序是 (1) ；快速排序的最坏时间是 (2) 。
(1)（）

对于n个元素的关键字序列{k₁,k₂,…,k_n}，若将其按次序对应到一棵具有n个结点的完全二叉树上，使得任意结点都不大于其孩子结点(若存在孩子结点)，则称其为小顶堆。根据以上定义，（）是小顶堆。

设有二叉树如图8-15所示。
对此二叉树先序遍历的结果为（）

前序遍历序列与中序遍历序列相同的二叉树为 (1) ，前序遍历序列与后序遍历序列相同的二叉树为 (2) 。
(1)（）

堆排序是一种基于_（1）_的排序方法，_（2）_不是堆。
(1)（）

设有n个结点进行排序，不稳定排序是 (1) ；快速排序的最大比较次数是 (2) 。
(1)（）

在排序算法中，两两比较待排序的记录，当发现不满足顺序要求时，变更它们的相对位置，这就是 (1) 排序。每次从未排序的记录中挑出最小(或最大)关键码值的记录，加入到已排序记录的末尾，这是 (2) 排序。
(1)（）

图的存储结构主要有邻接表和 (1) ，若用邻接表来存储一个图，则需要保存一个 (2) 存储的结点表和若干个 (3) 存储的关系表(又称边表)。

(2) （）

前序遍历序列与中序遍历序列相同的二叉树为 (1) ，前序遍历序列与后序遍历序列相同的二叉树为 (2) 。
(2)（）

设有n个结点进行排序，不稳定排序是 (1) ；快速排序的最大比较次数是 (2) 。
(2) （）

对于二维数组a[1..4,3..6]，设每个元素占两个存储单元，若分别以行和列为主序存储，则元素a[3,4]相对于数组空间起始地址的偏移量分别是 (1) 和 (2) 。
(1)（）

在排序算法中，两两比较待排序的记录，当发现不满足顺序要求时，变更它们的相对位置，这就是 (1) 排序。每次从未排序的记录中挑出最小(或最大)关键码值的记录，加入到已排序记录的末尾，这是 (2) 排序。
(2)（）

堆排序是一种基于_（1）_的排序方法，_（2）_不是堆。
(2)（）

对于二维数组a[1..4,3..6]，设每个元素占两个存储单元，若分别以行和列为主序存储，则元素a[3,4]相对于数组空间起始地址的偏移量分别是 (1) 和 (2) 。
(2)（）

前序遍历序列与中序遍历序列相同的二叉树为 (1) ，前序遍历序列与后序遍历序列相同的二叉树为 (2) 。
(1)（）

图的存储结构主要有邻接表和 (1) ，若用邻接表来存储一个图，则需要保存一个 (2) 存储的结点表和若干个 (3) 存储的关系表(又称边表)。

(3) （）

设有n个结点进行排序，不稳定排序是 (1) ；快速排序的最坏时间是 (2) 。
(1)（）

正规式(1|3|5)(202)(c|de)表示的正规集合中元素数目为 (1) ， (2) 是该正规集合中的元素。
(1)（）

前序遍历序列与中序遍历序列相同的二叉树为 (1) ，前序遍历序列与后序遍历序列相同的二叉树为 (2) 。

(2)（）

设有n个结点进行排序，不稳定排序是 (1) ；快速排序的最坏时间是 (2) 。
(2)（）

正规式(1|3|5)(202)(c|de)表示的正规集合中元素数目为 (1) ， (2) 是该正规集合中的元素。
(2)（）