微信小程序注：不含主观题
第 1 题
算法的时间复杂度取决于( )
A
问题的规模
B
待处理数据的初态
C
前两个都是
第 2 题
计算机算法指的（ ），它必须具可读性、健壮性、高性能 这四个个特性。
A
计算方法
B
排序方法
C
解决问题的步骤序列
D
调度方法
第 3 题
从逻辑上可以把数据结构分为（ ）两大类。
A 动态结构、静态结构
B 顺序结构、链式结构
C 线性结构、非线性结构
D 初等结构、构造型结构
数据结构中，与所使用的计算机无关的是数据的（ ）结构。
A
存储
B
物理
C
逻辑
D
物理和存储
第 5 题
算法分析的目的是（ ）。
A
找出数据结构的合理性
B
分析算法的效率以求改进
C
研究算法中输入和输出的关系
D
分析算法的易懂性和文档性
第 6 题
计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备具备输入、 输出和
( )等 5 个特性。
A
可行性、可移植性和可扩充性
B
易读性、稳定性和安全性
C
确定性、有穷性和稳定性
D
可行性、确定性和有穷性
第 7 题
下面程序的时间复杂度为 （ ）。
for(i=0;i<m;i++)
for(j=0;j<n;j++)
a[i][j]=i*j;
A
O(m*n)
B
O(n*n)
C
O(m*m)
D
O(m+n)
第 8 题
程序段
i=0;s=0;
while(++i<=n)
{ int p=1;
for(j=0; j<i; j++)
p*=j;
s=s+p;
}
该程序段的时间复杂度为 （ ） 。
A
O(n)
B
O(n*logn)
C
O(n*n*n)
D
O(n*n)
第 9 题
以下数据结构中，（ ）是非线性数据结构
A
树
B
字符串
C
队
D
栈
第 10 题
顺序存储设计时，存储单元的地址（ ）。
A
一定连续
B
一定不连续
C
不一定连续
D
部分连续， 部分不连续
第 11 题
数据的逻辑结构是指数据的各数据项之间的逻辑关系。( )
第 12 题
数据项是数据处理的最小单位。( )
第 13 题
算法的优劣与算法描述语言无关，但与所用计算机有关。( )
第 14 题
健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )
第 15 题
算法可以用不同的语言描述，如果用 C 语言或 PASCAL 语言等高级语言来描述， 则算法实际上就是程序了。( )
第 16 题
程序一定是算法。( )
第 17 题
数据结构的抽象操作的定义与具体实现无关。( )
第 18 题
所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。( )
第 19 题
同一个算法，实现语言的级别越高， 执行效率就越低。( )
第 20 题
算法效率的评价用时间复杂度和空间复杂度两个方面进行。( )
第二章测试 线性表
第 1 题
线性表是具有 n 个（ ）的有限序列（n>0）。
A
表元素
B
字符
C
数据元素
D
数据项
E
信息项
第 2 题
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运 算，则利用（ ）存储方式最节省时间。
A
顺序表
B
双链表
C
带头结点的双循环链表
D
单循环链表
第 3 题
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素， 则采用（ ）存储方式最节省运算时间。
A
单链表
B
仅有头指针的单循环链表
C
双链表
D
仅有尾指针的单循环链表
第 4 题
设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ ）最节省时 间。
A
单链表
B
单循环链表
C
带尾指针的单循环链表
D
带头结点的双循环链表
第 5 题
链表不具有的特点是( )
A
插入、删除不需要移动元素
B
可随机访问任一元素
C
不必事先估计存储空间
D
所需空间与线性长度成正比
第 6 题
一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地 址是（ ）。
A
110
B
108
C
100
D
120
在 n 个结点的顺序表中， 算法的时间复杂度是 O（1）的操作是（ ）。
A
访问第 i 个结点（1≤i≤n）和求第 i 个结点的直接前驱（2≤i≤n）。
B
在第 i 个结点后插入一个新结点（1≤i≤n）
C
删除第 i 个结点（1≤i≤n）
D
将 n 个结点从小到大排序
第 8 题
非空的循环单链表 head 的尾结点 p 满足（ ）。
A
p->next=head
B
p->next=NULL
C
p=NULL
D
p=head
第 9 题
链式存储的存储结构所占存储空间（ ）。
A
分两部分， 一部分存放结点值， 另一部分存放表示结点间关系的指针
B
只有一部分，存放结点值
C
只有一部分，存储表示结点间关系的指针
D
分两部分， 一部分存放结点值， 另一部分存放结点所占单元数
第 10 题
单链表的存储密度（ ）。
A
大于 1
B
等于 1
C
小于 1
D
不能确定
第 11 题
已知 L 是不带头结点的单链表， 且 P 结点既不是首元结点，也不是尾元结点，试 选择合适的语句序列，完成在 P 结点后插入 S 结点的语句序列。( )
A
S->next=P->next; P->next=S;
B
P->next=S; S->next=P->next;
C
P->next=S;
D
P->next=S;
第 12 题
12 已知 L 是不带头结点的单链表，且 P 结点既不是首元结点，也不是尾元结点， 试选择合适的语句序列， 完成在 P 结点前插入 S 结点的语句序列。( )
A
S->next=P->next; P->next=S;
B
P->next=S;S->next=P->next;
C
Q=L; while(Q->next!=P) Q=Q->next; S->next=P; Q->next=S;
D
Q=L; while(Q->next!=P) Q=Q->next;Q->next=S; S->next=P;
第 13 题
下述算法的功能是什么?( )
A
删除最后一个结点
B
将开始结点删除，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
C
将开始结点摘下链接到最后一个结点后面，而原来的第二个结点成为新的开始结 点，返回新链表的头指针。
D
将最后结点摘下链接到放到第一个结点之前
第 14 题
在顺序表中插入或删除一个元素，需要平均移动（ ）的元素， 具体移动的元素个 数与 表长和该元素在表中的位置有关。
A
表中所有
B
表中一半
第 15 题
双向循环链表的头指针为 head，若带头结点， 则表空的条件是（ ）。
A
head->next= =NULL
B
head= =NULL
C
head->next==head 或者 head->prior==head
第 16 题
对任何数据结构链式存储结构一定优于顺序存储结构。( )
第 17 题
链式存储结构对存储的数据区域连续或不连续没有要求。( )
第 18 题
线性表采用顺序存储，必须占用一片连续的存储单元。( )
第 19 题
线性表采用链接存储，插入和删除操作需要移动数据元素。( )
第 20 题
在循环链表 L 中，已知指针 p 指向某一结点， 可以找到 p 的前驱。( )
第 21 题
顺序存储方式只能用于存储线性结构。( )
第 22 题
在长度为 n 的单链表 L 中查找某个数据元素必须从头指针出发逐个查找比较，所 以时间复杂度为 O(n)。( )
第 23 题
链式存储结构的线性表,进行插入、删除操作时，任何情况下都比在顺序存储结构 中效率高。( )
第 24 题
线性表的顺序存储结构是可以按序号随机存取的。( )
第 25 题
集合与线性表的区别在于是否按关键字排序。( )
第三章测试 栈与队列
第 1 题
对于队列操作数据的原则是()
A
先进先出
B
后进先出
C
后进后出
D
不分顺序
第 2 题
表达式 a*(b+c)-d 的后缀表达式是 ( )
A
abcd*+-
B
-+*abcd
C
abc*+d-
D
abc+*d-
第 3 题
在设计递归函数时， 如不用递归过程就应借助于数据结构(
)
A
队列
B
线性表
C
广义表
D
栈
第 4 题
若已知一个栈的入栈序列是 1，2，3，…，n，其输出序列为 p1，p2，p3，…，pn， 若 p1=n，则 pi 为 （
）
A
i
B
n=i
C
n-i+1
D
不确定
第 5 题
栈和队列的共同点是（ ）
A
都是后进先出
B
都是先进先出
C
只允许在端点处插入和删除元素
D
没有共同点
第 6 题
判定一个循环队列 Q（最多有 m0 个元素采用“少用一个元素空间 ”来判别队空队
满）为满的条件是( )
A
Q->front= =Q->rear
B
Q->front!= =Q->rear
C
Q->front= =! (Q->rear+1)%m0
D
Q->front = =(Q->rear+1)%m0
第 7 题
7、一个递归算法必须包括（ ）。
A
递归部分
B
终止条件和递归部分
C
迭代部分
D
终止条件和迭代部分
第 8 题
用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队 尾结点，则在进行删除操作时（ ）。
A
仅修改队头指针
B
仅修改队尾指针
C
队头、队尾指针都要修改
D
队头,队尾指针都可能要修改
第 9 题
递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。
A
队列
B
多维数组
C
栈
D
线性表
第 10 题
在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否 ( ②)。当栈中元素为 n 个,作进栈运算时发生上溢,则说明该栈的最大容量为 ( ③ )。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存 空间时,应将两栈的 ( ④)分别设在这片内存空间的两端,这样,当( ⑤ )时， 才产生上溢。
A
满，空，n,栈底，两个栈的栈顶在栈空间的某一位置相遇.
B
空，满，n,栈底，其中一个栈的栈顶到达栈空间的中心点.
C
满，空，n+1,深度， 两个栈的栈顶在栈空间的某一位置相遇.
D
空，满，n/2,栈底， 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.
E
上溢， 空， n-1,栈底，其中一个栈的栈顶到达栈空间的中心点.
第 11 题
消除递归不一定需要使用栈，此说法对吗？( )
第 12 题
两个栈共享一片连续内存空间时， 为提高内存利用率，减少溢出机会，应把两个 栈的栈底分别设在这片内存空间的两端。( )
第 13 题
有 n 个数顺序（依次）进栈，出栈序列有 Cn 种，Cn=[1/（n+1）]*（2n）!/[(n!)*(n!)]。 ( )
第 14 题
栈与队列是一种特殊操作的线性表。( )
第 15 题
若输入序列为 1,2,3,4,5,6,则通过一个栈可以输出序列 3,2,5,6,4,1. ( )
第 16 题
只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。( )
第 17 题
7、栈是一种插入与删除操作在表的一端进行的线性表，是一种先进后出型结构。 ( )
第 18 题
队列逻辑上是一个下端和上端既能增加又能减少的线性表。( )
第 19 题
循环队列可以用顺序结构存储也可以用链式存储结构实现。( )
第 20 题
栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。( )
第五章测试 数组与广义表
第 1 题
下面关于串的的叙述中， 哪一个是不正确的？ ( )
A
串是字符的有限序列
B
空串是由空格构成的串
C
模式匹配是串的一种重要运算
D
串既可以采用顺序存储， 也可以采用链式存储
若串 S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行
concat(replace(S1,substr(S1,4,3),S3),substr(S4,index(S2,‘8’),length( S2)))其结果为( )
A
ABC###G0123
B
ABCD###2345
C
ABC###G1234
D
ABCD###1234
第 3 题
设有两个串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为 ( )
A
求子串
B
联接
C
模式匹配
D
求串长
第 4 题
模式匹配算法是在主串中快速寻找模式的一种有效的方法， 如果设主串的长度为 m，模式的长度为 n，朴素的模式匹配算法的时间复杂性是（）。
A
m+n
B
m*n
C
m
D
n
第 5 题
两个字符串 A 和 B 的长度分别为 m 和 n。求这两个字符串最大共同子串算法的时 间复杂度为 T(m,n)。最优的 T(m,n)为：（ ）。
A
O（m*n）
B
O（m）
C
O（n）
D
O（m+n）
第 6 题
假设有 60 行 70 列的二维数组 a[1…60, 1…70]以列序为主序顺序存储，其基地 址为 10000，每个元素占 2 个存储单元，那么第 32 行第 58 列的元素 a[32,58]的 存储地址为（ ） 。（无第 0 行第 0 列元素）
A
16902
B
16904
14454
D
答案 A、B、C 均不对
第 7 题
设矩阵 A 是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数 组 B[1, n(n-1)/2]中， 对下三角部分中任一元素 ai,j(i≤j), 在一维数组 B 中下 标 k 的值是（）。
A
i(i-1)/2+j-1
B
i(i-1)/2+j
C
i(i+1)/2+j-1
D
i(i+1)/2+j
第 8 题
下面说法不正确的是（ ）。
A
广义表的表头总是一个广义表
B
广义表的表尾总是一个广义表
C
广义表难以用顺序存储结构
D
广义表可以是一个多层次的结构
第 9 题
对特殊矩阵采用压缩存储的目的主要是为了（ ）。
A
使表达变得简单
B
对矩阵元素的存取变得简单
C
去掉矩阵中的多余元素
D
减少不必要的存储空间
第 10 题
稀疏矩阵一般的压缩存储方式有两种，即（ ）。
A
二维数组和三维数组
B
三元组表和散列表
C
散列表和十字链表
D
三元组表和十字链表
第 11 题
串的存储结构有：顺序串和链串。( )
第 12 题
从数据结构角度讲，串属于线性结构。与线性表的不同在于串的数据元素是字符， 同时操作对象常常是一个串。( )
第 13 题
空格是一个字符，其 ASCII 码值是 32。空格串是由空格组成的串，其长度等于空 格的个数。空串是不含任何字符的串，即空串的长度是零。( )
第 14 题
数组不适合作为任何二叉树的存储结构。( )
第 15 题
稀疏矩阵压缩存储后， 必会失去随机存取功能。( )
第 16 题
数组是同类型值的集合。( )
第 17 题
一个稀疏矩阵 Am*n 采用三元组形式表示， 若把三元组中有关行下标与列下标 的值互换， 并把 m 和 n 的值互换，则就完成了 Am*n 的转置运算。( )
第 18 题
二维以上的数组其实是一种特殊的广义表。( )
第 19 题
广义表的取表尾运算， 其结果通常是个表，但有时也可是个单元素值。( )
第 20 题
广义表 L=（a，（b，c）），进行 Tail（L）操作后的结果为（（b，c））。( )
第六章测试 树与二叉树
第 1 题
设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是( ) A
A*B+C/(D*E)+(F-G)
B
(A*B+C)/(D*E)+(F-G)
C
(A*B+C)/(D*E+（F-G）)
D
A*B+C/D*E+F-G
第 2 题
在下述结论中， 正确的是( )
①只有一个结点的二叉树的度为 0; ②二叉树的度为 2； ③二叉树的左右子树 可任意交换; ④深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉 树的结点个数。
A
①②③
B
②③④
C
②④
D
第 3 题
设森林 F 对应的二叉树为 B，它有 m 个结点， B 的根为 p,p 的右子树结点个数为 n,森林 F 中第一棵树的结点个数是( )
A
m-n
B
m-n-1
C
n+1
D
条件不足， 无法确定
第 4 题
若一棵二叉树具有 10 个度为 2 的结点， 5 个度为 1 的结点， 则度为 0 的结点个数 是( )
A
9
B
11
C
15
D
不确定
第 5 题
设森林 F 中有三棵树，第一，第二， 第三棵树的结点个数分别为 M1，M2 和 M3。与 森林 F 对应的二叉树根结点的右子树上的结点个数是（ ）。
A
M1
B
M1+M2
C
M3
D
M2+M3
第 6 题
一棵完全二叉树上有 9 个结点， 其中叶子结点的个数是( )
A
2
B
5
C
4
D
3
E
以上答案都不对
第 7 题
设给定权值总数有 n 个，其哈夫曼树的结点总数为( )
A
不确定
B
2n
C
2n+1
D
2n-1
第 8 题
二叉树的第 I 层上最多含有结点数为( )
A
2^I
B
2^(I-1)-1
C
2^(I-1)
D
2^I -1
第 9 题
对于有 n 个结点的二叉树, 其高度为( )
A
n(log2(n))
B
log2(n)
C
log2n+1
D
不确定
第 10 题
高度为 K 的二叉树最大的结点数为（ ）。
A
2^k
B
2^(k-1)
C
2^k -1
D
2^(k-1)-1
第 11 题
利用二叉链表存储树， 则根结点的右指针是（ ）。
A
指向左孩子
B
指向右孩子
C
空
D
非空
第 12 题
树的后根遍历序列等同于该树对应的二叉树的（ ）.
A
先序序列
B
中序序列
C
后序序列
第 13 题
在下列存储形式中， 哪一个不是树的存储形式？( )
A
双亲表示法
B
孩子链表表示法
C
孩子兄弟表示法
D
顺序存储表示法
第 14 题
已知一棵二叉树的前序遍历结果为 ABCDEF,中序遍历结果为 CBAEDF,则后序遍历 的结果为（ ）。
A
CBEFDA
B
FEDCBA
C
CBEDFA
不定
第 15 题
由 3 个结点可以构造出多少种不同的树？( )
A
2
B
3
C
4
D
5
第 16 题
树在计算机内的表示方式有(
)。
A
顺序存储结构、链式存储结构
B
多重链表表示法
C
双亲表示法、孩子表示法、孩子兄弟表示法
第 17 题
现有按中序遍历二叉树的结果为 abc，问有（ ）种不同的二叉树可以得到这一遍
历结果。
A
2
B
3
C
4
D
5
第 18 题
深度为 k 的完全二叉树至少有（ ）个结点。
A
2^(k-1)
B
2^k-1
C
2^k
D
2^(k+1)
第 19 题
设有 N 个结点的完全二叉树顺序存放在向量 A[1:N]中， 其下标值最大的分支结点
为(
)。
A
N
B
C
N-1
D
N/2
第 20 题
二叉树与树、森林之间依据（ ）可以互相转换。
A
顺序存储结构
B
孩子表示法
C
孩子兄弟表示法
第 21 题
二叉树是度为 2 的有序树。( )
第 22 题
完全二叉树一定存在度为 1 的结点。( )
第 23 题
对于有 N 个结点的二叉树，其高度为 log2n。( )
第 24 题
深度为 K 的二叉树中结点总数≤2^k-1。( )
第 25 题
对一棵二叉树进行层次遍历时， 应借助于队列实现。( )
第 26 题
由一棵二叉树的前序序列和后序序列可以唯一确定它。( )
第 27 题
完全二叉树中， 若一个结点没有左孩子， 则它必是树叶。( )
第 28 题
二叉树只能用二叉链表表示。( )
第 29 题
一棵有 n 个结点的二叉树，从上到下， 从左到右用自然数依次给予编号，则编号 为 i 的结点的左儿子的编号为 2i(2i< n)，右儿子是 2i+1（2i+1<n）。( )
第 30 题
给定一棵树， 可以找到唯一的一棵二叉树与之对应。( )
第 31 题
二叉树中每个结点至多有两个子结点,而对一般树则无此限制.因此,二叉树是树 的特殊情形。( )
第 32 题
必须把一般树转换成二叉树后才能进行存储。( )
将一棵树转成二叉树，根结点没有右子树。( )
第 34 题
树与二叉树是两种不同的树型结构。( )
第 35 题
当一棵具有 n 个叶子结点的二叉树的 WPL 值为最小时，称其树为 Huffman 树，且 其二叉树的形状必是唯一的。( )
第 36 题
用二叉链表存储包含 n 个结点的二叉树时，结点的 2n 个指针区域中有 n+1 个空 指针。( )
第 37 题
二叉树由根结点， 左子树，右子树三个基本单元组成， 所以， 二叉树有五种基本 形态。( )
第 38 题
树和森林都可以转换为二叉树， 转换而来的二叉树均没有右子树。( )
第 39 题
哈夫曼树是用来构建哈夫曼编码的， 在哈夫曼树中没有度为 1 的结点。( )
第 40 题
二叉树的前序遍历序列和后序遍历序列正好相反的二叉树只有一个结点。( )
第七章测试 图
第 1 题
设无向图的顶点个数为 n，则该图最多有（ ）条边。
A n-1
B n(n-1)/2
C n(n+1)/2
D 0
E n^2
第 2 题
在一个无向图中，所有顶点的度数之和等于所有边数的 2 倍，在一个有向图中， 所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A 1/2
B 2
C 1
D 4
第 3 题
下列哪一种图的邻接矩阵是对称矩阵？( )
A 有向图
B 无向图
C AOV 网
D AOE 网
第 4 题
从邻接阵矩 A（如下图所示）可以看出， 该图共有（ ）个顶点。
A 2
B 3
C 6
D 4
E 以上答案均不正确
第 5 题
4 题中的邻接矩阵 A，如果是有向图， 该图共有（ ）条弧。
A 2
B 3
C 6
D 4
E 以上答案均不正确
第 6 题
4 题中的邻接矩阵 A，如果是无向图， 该图共有（ ）条边。
A 2
B 3
C 6
D 4
E 以上答案均不正确
第 7 题
下列说法不正确的是( )
A 图的遍历是从给定的源点出发每一个顶点仅被访问一次
B 遍历的基本算法有两种：深度遍历和广度遍历
C 图的深度遍历不适用于有向图
D 图的深度遍历是一个递归过程
第 8 题
无 向 图 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 出发进行深度优先遍历，得到的顶点序列正确的是( )
A a,b,e,c,d,f
B a,c,f,e,b,d
C a,e,b,c,f,d
D a,e,d,f,c,b
第 9 题
对题 8 中的无向图 G=(V,E)从 a 出发进行广度优先遍历，得到的顶点序列正确的 是( )
A a,b,e,c,d,f
B a,c,f,e,b,d
C a,e,b,c,f,d
D a,e,d,f,c,b
第 10 题
在无向图 G 的邻接表表示中，每个顶点的邻接点建立一个单链表， 称之为结点的 邻接表，邻接表中所含的结点数等于该顶点的( )
A 度数
B 依附的边数
C 出度
D 入度
第 11 题
在有向图 G 的邻接表表示中，每个顶点的邻接点建立一个单链表， 称之为结点的 邻接表，邻接表中所含的结点数等于该顶点的( )
A 度数
B 依附的边数
C 出度
D 入度
第 12 题
在图采用邻接矩阵存储时，Prim 算法的时间复杂度为( )
A O(n)
B O(n+e)
C O(n2)
D O(n3)
第 13 题
求解 Floyd 算法的时间复杂度为( )
A O（n）
B O（n+c）
C O（n*n）
D O（n*n*n）
第 14 题
任何一个无向连通图的最小生成树( )
A 只有一棵
B 有一棵或多棵
C 一定有多棵
D 可能不存在
第 15 题
构造连通网最小生成树的两个典型算法是( )
A Floyd 算法和 Prim 算法
B Prim 算法和 kruskal 算法
C Prim 算法和 Dijkstra 算法
D Dijkstra 算法和 Prim 算法
第 16 题
树中的结点和图中的顶点就是指数据结构中的数据元素( )
第 17 题
在 n 个结点的无向图中， 若边数大于 n-1,则该图必是连通图( )
第 18 题
有 e 条边的无向图， 在邻接表中有 e 个结点( )
第 19 题
强连通图的各顶点间均可达( )
第 20 题
用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关( )
第 21 题
有向图 G 的强连通分量是指有向图的极大强连通子图( )
第 22 题
在有向图的邻接矩阵表示中， 第 I 个顶点入度就是第 I 列非零元素个数( )
第 23 题
邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图， 而 只能使用邻接表存储形式来存储它( )
第 24 题
为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需 使用队列存放被访问的结点以实现遍历( )
第 25 题
只有连通无向图存在生成树，不连通的图存在生成森林( )
第 26 题
Prim（普里姆） 算法适用于求边稀疏的网的最小生成树( )
第 27 题
连通图上各边权值均不相同，则该图的最小生成树是唯一的( )
第 28 题
Dijkstra 算法是用来求从源点到其余各顶点的最短路径的，该算法是按路径长度 递增次序依次产生的( )
第 29 题
判断一个有 n 个顶点的无向图是一棵树的条件是有 n-1 条边( )
对于一个具有 n 个顶点 e 条弧的有向图， 用逆邻接表存储，方便获取顶点的入度 ( )
第 31 题
可以利用图的遍历过程来判断一个图是否连通，并可得到其连通分量。如果在遍 历的过程中，不止一次调用遍历过程，则说明该图是一个非连通图。调用遍历过 程的次数就是该图连通分量的个数( )
第八章测试 查找算法
第 1 题
若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找 法查找一个记录，其平均查找长度 ASL 为( )。
A
(n-1)/2
B
n/2
C
(n+1)/2
D
n
第 2 题
下面关于二分查找的叙述正确的是 ( )
A
表必须有序，表可以顺序方式存储， 也可以链表方式存储
B
表必须有序，而且只能从小到大排列
C
表必须有序且表中数据必须是整型， 实型或字符型
表必须有序，且表只能以顺序方式存储
第 3 题
当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查 找，但前者比后者的查找速度( )
A
必定快
B
不一定
C
在大部分情况下要快
D
取决于表递增还是递减
第 4 题
当采用分快查找时， 数据的组织方式为 ( )
A
数据分成若干块，每块内数据有序
B
数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小） 的数据组成索引块
C
数据分成若干块，每块内数据有序， 每块内最大（或最小）的数据组成索引块
D
数据分成若干块，每块（除最后一块外） 中数据个数需相同
既希望较快的查找又便于线性表动态变化的查找方法是 ( )
A
顺序查找
B
折半查找
C
索引顺序查找
D
哈希法查找
第 6 题
分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )
A
(100，80， 90， 60， 120，110，130）
B
(100，120，110，130，80， 60， 90）
C
(100，60， 80， 90， 120，110，130）
D
(100，80， 60， 90， 120，130，110)
第 7 题
设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}， 用链地址法构造散列表， 散列函数为 H（key）=key MOD 13,散列地址为 1 的链中 有（ ）个记录。
A
B
2
C
3
D
4
第 8 题
下面关于哈希(Hash，杂凑)查找的说法正确的是( )
A
哈希函数构造的越复杂越好，因为这样随机性好， 冲突小
B
除留余数法是所有哈希函数中最好的
C
不存在特别好与坏的哈希函数， 要视情况而定
D
若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素 删去即可
第 9 题
散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
A
最大概率
B
最小概率
C
平均概率
D
同等概率
第 10 题
将 10 个元素散列到 100000 个单元的哈希表中， 则（ ）产生冲突。
A
一定会
B
一定不会
C
仍可能会
第 11 题
已知一个长度为 11 的顺序表 L，其元素按关键字有序排列， 若采用折半查找法查 找一个不存在的元素，则比较次数最多的是（ ）次
A
3
B
4
C
5
D
6
第 12 题
如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二 叉排序树检索时，平均比较次数为 。
A
(n+1)/2
B
n/2
C
log2n
D
n
第 13 题
在哈希查找中， “ 比较 ”操作一般也是不可避免的。
第 14 题
哈希函数越复杂越好，因为这样随机性好，冲突概率小.
第 15 题
装填因子是散列表的一个重要参数， 它反映散列表的装满程度。
第 16 题
哈希法的平均查找长度不随表中结点数目的增加而增加，而是随负载因子的增大 而增大。
第 17 题
哈希表的结点中只包含数据元素自身的信息， 不包含任何指针。
第 18 题
若哈希表的负载因子 α<1，则可避免碰撞的产生。
第 19 题
查找相同结点的效率折半查找总比顺序查找高。
第 20 题
用顺序表和单链表表示的有序表均可使用折半查找方法来提高查找速度。
第 21 题
在索引顺序表中，实现分块查找， 在等概率查找情况下，其平均查找长度不仅与 表中元素个数有关， 而且与每块中元素个数有关。
第 22 题
顺序查找法适用于存储结构为顺序或链接存储的线性表。
第 23 题
折半查找法的查找速度一定比顺序查找法快 。
第 24 题
就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。
第 25 题
对大小均为 n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对 于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找 长度是不同的。
第 26 题
对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。
第 27 题
有 n 个数存放在一维数组 A[1..n]中，在进行顺序查找时， 这 n 个数的排列有序 或无序其平均查找长度不同。
第 28 题
N 个结点的二叉排序树有多种， 其中树高最小的二叉排序树查找性能是最佳的。
第 29 题
在任意一棵非空二叉排序树中，删除某结点后又将其插入， 则所得二排序叉树与 原二排序叉树相同。
第 30 题
设关键字序{45, 24, 53，45, 12, 24, 90} ，从空树出发依次读入关键字建立 二叉排序树 BT，对 BT 进行查找，其平均查找长度为 11/5。
第 31 题
二叉排序树和折半查找的判定树是一样的。
第 32 题
平均查找长度是用来衡量查找算法的时间性能的，其定义为：为了确定记录在查 找表中的位置， 需要和给定值进行比较的关键字个数的期望值。
第九章测试 排序算法
第 1 题
下列排序算法中， 其中（ ）是稳定的。
A
堆排序，冒泡排序
B
快速排序， 堆排序
C
直接选择排序， 归并排序
D
归并排序， 冒泡排序
第 2 题
若需在 O(nlog2n)的时间内完成对数组的排序， 且要求排序是稳定的， 则可选择 的排序方法是（ ）。
A
快速排序
B
堆排序
C
归并排序
D
直接插入排序
第 3 题
排序趟数与序列的原始状态有关的排序方法是（ ）排序法。
A
插入
B
选择
归并
D
冒泡
第 4 题
下列排序算法中（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。
A
快速排序
B
希尔排序
C
堆排序
D
冒泡排序
第 5 题
一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第 一个记录为基准得到的一次划分结果为（ ）。
A
(38,40,46,56,79,84)
B
(40,38,46,79,56,84)
C
(40,38,46,56,79,84)
D
(40,38,46,84,56,79)
第 6 题
在下面的排序方法中， 辅助空间为 O（n）的是（ ）。
A
希尔排序
B
堆排序
C
选择排序
D
归并排序
第 7 题
下列排序算法中， 在待排序数据已有序时，花费时间反而最多的是（ ）排序。
A
冒泡
B
希尔
C
快速
D
堆
第 8 题
就平均性能而言， 目前最好的内排序方法是（ ）排序法。
A
冒泡
B
希尔插入
C
交换
D
快速
第 9 题
如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生 颠倒， 则称该排序算法是不稳定的。（ ）就是不稳定的排序方法。
A
冒泡排序
B
归并排序
C
希尔排序
D
直接插入排序
第 10 题
在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ）。
A
直接插入排序
B
冒泡排序
C
快速排序
D
直接选择排序
第 11 题
有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划
分后数据的排序为（ ）（按递增序）。
A
下面的 B，C，D 都不对
B
9，7，8，4，-1，7，15，20
C
20，15，8，9，7，-1，4，7
D
9，4，7，8，7，-1，15，20
第 12 题
下面的排序方法中，对初态为有序的表， 则最省时间的是（ ）算法。
A
堆排序
B
快速排序
C
冒泡排序
D
归并排序
第 13 题
下面的排序方法中，对初态为有序的表， 则最费时间的是（ ）算法。
A
堆排序
B
快速排序
C
冒泡排序
D
归并排序
第 14 题
如果只想得到 1000 个元素组成的序列中第 5 个最小元素之前的部分排序的序列， 用（ ）方法最快。
A
冒泡排序
B
快速排序
C
希尔排序
D
堆排序
第 15 题
直接插入排序在最好情况下的时间复杂度为（ ）。
A
O(logn)
B
O(n)
C
O(n*logn)
D
O(n2)
第 16 题
堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是（ ）。
A
O（n2）和 O（1）
B
O（nlog2n）和 O（1）
C
O（nlog2n）和 O（n）
D
O（n2）和 O（n）
第 17 题
若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较 和记录的移动。( )
第 18 题
内排序要求数据一定要以顺序方式存储。( )
第 19 题
排序算法中的比较次数与初始元素序列的排列无关。( )
第 20 题
直接选择排序算法在最好情况下的时间复杂度为 O（N）。( )
第 21 题
直接插入排序用监视哨的作用是免去查找过程中每一步都要检测整个表是否查 找完毕，提高了查找效率。( )
第 22 题
在待排数据基本有序的情况下， 快速排序效果最好。( )
第 23 题
在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆 ”。( )
第 24 题
冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最 坏时间复杂度是 O(n*n),而快速排序算法的最坏时间复杂度是 O(nlog2n),所以快 速排序比冒泡排序算法效率更高。( )
第 25 题
堆排序是选择类排序。( )
第 26 题
中序遍历二叉排序树， 可得到排序的关键码序列。( )
快速排序总比简单排序快。( )
第 28 题
就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是: 堆排序〈 快速排序〈 归并排序。( )
课程评价
第 1 题
您在该课程上课学习效果如何?
A 基本能听懂， 新知识巩固一般
B 少有启发完全听不懂， 新知识巩固差
C 没有启发听得懂， 新知识巩固率较高
D 较有启发听得懂， 新知识巩固高
E 有启发， 对该课程有明显的了解
第 2 题
任课老师的课堂气氛是
A 非常死版
B 按部就班
C 融洽.活跃
第 3 题
教师授课示范流程， 尤其是详细到每个步骤， 对知识技能方向的掌握 A 优秀
B 良好
C 合格
D 差评
第 4 题
您觉得上课对你有帮助吗？
A 有
B 没有
C 有一点点
第 5 题
任课老师在教学组织安排方面表现如何?
A 能抓住知识主线
B 老师讲的理论太多
C 思路清晰、有讲有练、重点突出
D 知识点混乱， 重点不突出
第 6 题
给老师评分
A 差评
B 中评
C 好评
D 五星好评
第 7 题
请先 ！