选择题
第1题：
迪杰斯特拉(Diikstra)算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了______算法策略。
A.贪心 B.分而治之 C.动态规划 D.试探+回溯
参考答案：A
第2题：
关于算法与数据结构的关系，______是正确的。
A.算法的实现依赖于数据结构的设计 B.算法的效率与数据结构无关
C.数据结构越复杂，算法的效率越高 D.数据结构越简单，算法的效率越高
参考答案：A
第3题：
若一个问题既可以用迭代方式也可以用递归方式求解，则______方法具有更高的时空效率。
A.迭代 B.递归
C.先递归后迭代 D.先迭代后递归
参考答案：A
第4题：
若有数组声明a[0..3，0..2，1..4]，设编译时为a分配的存储空间首地址为base_a，且每个数组元素占据一个存储单元。当元素以行为序存放(即按a[0，0，1]，a[0，0，2]，a[0，0，3]，a[0，0，4]，a[0，1，1]，a[0，1，
1
2]，…，a[3，2，4]顺序存储)时，则数组元素a[2，2，2]在其存储空间中相对base_a的偏移量是______。
A.8 B.12 C.33 D.48
参考答案：C
已知一个线性表(16，25，35，43，51，62，87，93)，采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则构造的哈希表为 (5) ，在该散列表上进行等概率成功查找的平均查找长度为 (6) (为确定记录在查找表中的位置，需和给定关键字值进行比较的次数期望值称为查找算法在查找成功时的平均查找长度)。 第5题：
A. B. C. D.
参考答案：C
第6题：
A.(5*1+2+3+6)/8 B.(5*1+2+3+6)/9 C.(8*1)/8 D.(8*1)/9
2
参考答案：A
第7题：
若将某有序树丁转换为二叉树T1，则T中结点的后(根)序序列就是T1中结点的______遍历序列。例如，如图1-8(a)所示的有序树转化为二叉树后如图1-8(b)所示。
A.先序 B.中序 C.后序 D.层序
参考答案：B
设一个包含Ⅳ个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目为 (8) ，其中非零元素数目为 (9) 。 第8题：
A.E2 B.N2
C.N22-E2 D.N2+E2
参考答案：B
第9题：
A.N B.N+E C.E D.N-E
参考答案：C
3
第10题：
一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现。这句话说明算法具有______特性。
A.有穷性 B.可行性 C.确定性 D.健壮性
参考答案：B
斐波那契(Fibonacci)数列可以递归地定义为：
用递归算法求解F(5)时需要执行 (11) 次“+”运算，该方法采用的算法策略是 (12) 。 第11题：
A.5 B.6 C.7 D.8
参考答案：C
第12题：
A.动态规划 B.分治 C.回溯 D.分支限界
参考答案：B
第13题：
若总是以待排序列的第一个元素作为基准元素进行快速排序，那么在最好情况下的时间复杂度为______。
4
A.O(log2n) B.O(n)
C.O(nlog2n) D.O(n2)
参考答案：C
第14题：
表达式(a-b)*(c+5)的后缀表示是______。
A.a b c 5+*- B.a b-c+5* C.a b c-*5+ D.a b-c 5+*
参考答案：D
一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为 (15) 个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点，则 (16) 。 第15题：
A.m+2 B.m+1 C.m D.m-1
参考答案：B
第16题：
A.s-＞right指向的结点一定是s所指结点的直接后继结点 B.s-＞left指向的结点一定是s所指结点的直接前驱结点 C.从s所指结点出发的right链可能构成环
D.s所指结点的left和right指针一定指向不同的结点
参考答案：C
5
第17题：
( )的邻接矩阵是一个对称矩阵。
A.无向图 B.AOV网 C.AOE网 D.有向图
参考答案：A
第18题：
将一个无序序列中的元素依次插入到一棵______，并进行中序遍历，可得到一个有序序列。
A.完全二叉树 B.最小生成树 C.二叉排序树 D.最优二叉树
参考答案：C
第19题：
广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是______。
A.链表 B.静态数组 C.动态数组 D.散列表
参考答案：A
第20题：
某一维数组中依次存放了数据元素12，23，30，38，41，52，54，76，85，在用折半(二分)查找方法(向上取整)查找元素54时，所经历“比较”运算的数据元素依次为______。
A.41，52，54 B.41，76，54
C.41，76，52，54
6
D.41，30，76，54
参考答案：B
第21题：
具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为______。
A.O(n2) B.O(e2) C.O(n*e) D.O(n+e)
参考答案：D
第22题：
给定一组长度为n的无序序列，将其存储在一维数组a[0…n-1]中。现采用如下方法找出其中的最大元素和最小元素：比较a[0]和a[n-1]，若a[0]较大，则将二者的值进行交换；再比较a[1]和a[n-2]，若a[1]较大，则交换二者的值；然后依次比较a[2]和a[n-3]、a[3]和a[n-4]、…，使得每一对元素中的较小者被交换到低下标端。重复上述方法，在数组的前n/2个元素中查找最小元素中在后n/2个元素中查找最大元素，从而得到整个序列的最小元素和最大元素。上述方法采用的算法设计策略是______。
A.动态规划法 B.贪心法 C.分治法 D.回溯法
参考答案：C
第23题：
设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n＞0)及T(0)=1，则该算法的时间复杂度为______。
A.O(lgn) B.O(nlgn) C.O(n)
D.O(n2)
参考答案：D
7
第24题：
下面关于查找运算及查找表的叙述，错误的是______。
A.哈希表可以动态创建
B.二叉排序树属于动态查找表
C.二分查找要求查找表采用顺序存储结构或循环链表结构 D.顺序查找方法既适用于顺序存储结构，也适用于链表结构
参考答案：C
第25题：
下面关于图(网)的叙述，正确的是______。
A.连通无向网的最小生成树中，顶点数恰好比边数多1 B.若有向图是强连通的，则其边数至少是顸点数的2倍 C.可以采用AOV网估算工程的工期
D.关键路径是AOE网中源点至汇点的最短路径
参考答案：A
第26题：
下面关于二叉排序树的叙述，错误的是______。
A.对二叉排序树进行中序遍历，必定得到结点关键字的有序序列 B.依据关键字无序的序列建立二叉排序树，也可能构造出单支树
C.若构造二叉排序树时进行平衡化处理，则根结点的左子树结点数与右子树结点数的差值一定不超过1
D.若构造二叉排序树时进行平衡化处理，则根结点的左子树高度与右子树高度的值一定不超过1
参考答案：C
第27题：
下面关于栈和队列的叙述，错误的是______。
A.栈和队列都是操作受限的线性表
B.队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为O(1)
C.若队列的数据规模n可以确定，则采用顺序存储结构比链式存储结构效率
8
更高
D.利用两个栈可以模拟一个队列的操作，反之亦可
参考答案：D
第28题：
下面关于二叉树的叙述，正确的是______。
A.完全二叉树的高度h与其结点数n之间存在确定的关系
B.在二叉树的顺序存储和链式存储结构中，完全二叉树更适合采用链式存储结构
C.完全二叉树中一定不存在度为1的结点 D.完全二叉树中必定有偶数个叶子结点
参考答案：A
第29题：
设L为广义表，将head(L)定义为取非空广义表的第一个元素，tail(L)定义为取非空广义表除第一个元素外剩余元素构成的广义表。若广义表L=(x，y，z)，a，(u，t，w))，则从L中取出原子项y的运算是______。
A.head(tail(tail(L))) B.tail(head(head(L))) C.head(tail(head(L)) D.tail(tail(head(L)))
参考答案：C
第30题：
以下的算法设计方法中，______以获取问题最优解为目标。
A.回溯法 B.分治法 C.动态规划 D.递推
参考答案：C
第31题：
9
归并排序采用的算法设计方法属于______。
A.归纳法 B.分治法 C.贪心法 D.回溯法
参考答案：B
已知一个二又树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为 (32) 。对于任意一棵二叉树，叙述错误的是 (33) 。 第32题：
A.②、③、①、⑤、④ B.①、②、③、④、⑤ C.②、④、⑤、③、① D.④、⑤、③、②、①
参考答案：C
第33题：
A.由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列 B.由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列 C.由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列 D.由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列
参考答案：B
第34题：
邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有n个顶点、e条边的图，______。
A.进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关 B.进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关
C.采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e) D.采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)
参考答案：D
10
第35题：
单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是______。
A.若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1) B.在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理
C.加入头结点后，代表链表的头指针不因为链表为空而改变 D.加入头结点后，在链表中进行查找运算的时间复杂度为O(1)
参考答案：D
第36题：
对于长度为m(m＞1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是______。
A.若入栈和入队的序列相同，则出栈序列和出队序列可能相同
B.若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序
C.入队序列与出队序列关系为1:1，而入栈序列与出栈序列关系是1:n(n≥1)
D.入栈序列与出栈序列关系为1:1，而入队序列与出队序列关系是1:n(n≥1)
参考答案：D
第37题：
字符串采用链表存储方式时，每个结点存储多个字符有助于提高存储密度。若采用结点大小相同的链表存储串，则在串比较、求子串、串连接、串替换等串的基本运算中，______。
A.进行串的比较运算最不方便 B.进行求子串运算最不方便 C.进行串连接最不方便 D.进行串替换最不方便
参考答案：D
第38题：
11
某算法的时间复杂度表达式为T(n)=an2+bnlgn+cn+d，其中，n为问题的规模，a、b、c和d为常数，用O表示其渐近时间复杂度为______。
A.O(n2) B.O(n) C.O(nlgn) D.O(1)
参考答案：A
以下关于快速排序算法的描述中，错误的是 (39) 。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素(12，25，30，45，52，67，85)构成，则初始排列为 (40) 时，排序效率最高(令序列的第一个元素为基准元素)。 第39题：
A.快速排序算法是不稳定的排序算法
B.快速排序算法在最坏情况下的时间复杂度为O(nlgn) C.快速排序算法是一种分治算法
D.当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度
参考答案：B
第40题：
A.45，12，30，25，67，52，85 B.85，67，52，45，30，25，12 C.12，25，30，45，52，67，85 D.45，12，25，30，85，67，52
参考答案：A
第41题：
对n个元素的有序表A[1..n]进行二分(折半)查找(除2取商时向下取整)，查找元素A[i](1≤i≤n)时，最多与A中的______个元素进行比较。
A.n
B.[log2n]-1 C.n/2
D.[log2n]+1
参考答案：D
12
第42题：
若用n个权值构造一棵最优二叉树(哈夫曼树)，则该二叉树的结点总数为______。
A.2n B.2n-1 C.2n+1 D.2n+2
参考答案：B
第43题：
栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此，______必须用栈。
A.实现函数或过程的递归调用及返回处理时 B.将一个元素序列进行逆置时 C.链表结点的申请和释放 D.可执行程序的装入和卸载
参考答案：A
第44题：
对以下4个序列用直接插入排序方法由小到大进行排序时，元素比较次数最少的是______。
A.89，27，35，78，41，15 B.27，35，41，16，89，70 C.15，27，46，40，64，85 D.90，80，45，38，30，25
参考答案：C
第45题：
对于哈希表，如果将装填因子定义为表中装入的记录数与表的长度之比，那么向表中加入新记录时，______。
A.装填因子的值随冲突次数的增加而递减 B.装填因子越大发生冲突的可能性就越大
13
C.装填因子等于1时不会再发生冲突 D.装填因子低于0.5时不会发生冲突
参考答案：B
第46题：
用关键字序列10，20，30，40，50构造的二叉排序树(二叉查找树)为______。
A. B. C. D.
参考答案：C
第47题：
若某算法在问题规模为n时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为______。
A.O(n)
B.O(n2) C.O(logn) D.O(nlogn)
参考答案：B
第48题：
若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指
14
针的单向循环链表(不含头结点)时，______。
A.插入和删除操作的时间复杂度都为O(1) B.插入和删除操作的时间复杂度都为O(n)
C.插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(n) D.插入操作的时间复杂度为O(n)，删除操作的时间复杂度为O(1)
参考答案：C
第49题：
设循环队列Q的定义中有rear和len两个域变量，其中rear表示队尾元素的指针，len表示队列的长度，如图1-9所示(队列长度为3，队头元素为e)。设队列的存储空间容量为M，则队头元素的指针为_____。
A.(Q.rear+Q.len-1) B.(Q.rear+Q.len-1+M)%M C.(Q.rear-Q.len+1) D.(Q.rear-Q.len+1+M)%M
参考答案：D
第50题：
下面关于哈夫曼树的叙述中，正确的是______
A.哈夫曼树一定是完全二叉树 B.哈夫曼树一定是平衡二叉树
C.哈夫曼树中权值最小的两个结点互为兄弟结点
D.哈夫曼树中左孩子结点小于父结点，右孩子结点大于父结点
参考答案：C
第51题：
某一维数组中依次存放了数据元素15，23，38，47，55，62，88，95，102，123，采用折半(二分)法查找元素95时，依次与______进行了比较。
A.62，88，95 B.62，95 C.55，88，95
15
D.55，95
参考答案：D
第52题：
己知一棵度为3的树(一个结点的度是指其子树的数目，树的度是指该树中所有结点的度的最大值)中有5个度为1的结点，4个度为2的结点，2个度为3的结点，那么，该树中的叶子结点数目为______。
A.10 B.9 C.8 D.7
参考答案：B
第53题：
下面C程序段中“count++”语句执行的次数为______。 for(int i=1；i＜=11；i*=2) for(int j=1；j＜=I；j++) count++；
A.15 B.16 C.31 D.32
参考答案：A
第54题：
______不能保证求得0-1背包问题的最优解。
A.分支限界法 B.贪心算法 C.回溯法
D.动态规划策略
参考答案：B
16
第55题：
设下三角矩阵(上三角部分的元素值都为0)A[0..n，0..n]如图1-10所示，将该三角矩阵的所有非零元素(即行下标不小于列下标的元素)按行优先压缩存储在容量足够大的数组M[]中(下标从1开始)，则元素A[i,j](0≤i≤n，j≤i)存储在数组M的______中。
A. B. C. D.
参考答案：A
第56题：
对n个元素的有序表A[1..n]进行顺序查找，其成功查找的平均查找长度(即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值)为______。
A.n
B.(n+1)/2
C.log2n D.n2
参考答案：B
第57题：
17
在______中，任意一个结点的左、右子树的高度之差的绝对值不超过1。
A.完全二叉树 B.二叉排序树 C.线索二叉树 D.最优二叉树
参考答案：A
第58题：
设一个包含N个顶点、E条边的简单无向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无边)，则该矩阵中的非零元素数目为______。
A.N B.E C.2E D.N+E
参考答案：C
第59题：
对于关键字序列(26，25，72，38，8，18，59)，采用散列函数H(Key)=Key mod 13构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则关键字59所在散列表中的地址为______。
A.6 B.7 C.8 D.9
参考答案：D
第60题：
要在8×8的棋盘上摆放8个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同一行、同一列和相同的对角线上，则一般采用______来实现。
A.分治法 B.动态规划法 C.贪心法 D.回溯法
18
参考答案：D
第61题：
分治算法设计技术______。
A.一般由三个步骤组成：问题划分、递归求解、合并解 B.一定是用递归技术来实现
C.将问题划分为k个规模相等的子问题 D.划分代价很小而合并代价很大
参考答案：A
第62题：
用插入排序和归并排序算法对数组＜3，1，4，1，5，9，6，5＞进行从小到大排序，则分别需要进行______次数组元素之间的比较。
A.12，14 B.10，14 C.12，16 D.10，16
参考答案：A
19
因篇幅问题不能全部显示，请点此查看更多更全内容