一、单项选择题
1 某算法的时间复杂度是 O(n2)，表明该算法(  )。 A 问题规模是 n2                B 问题规模与 n2 成正比  C 执行时间等于 n2              D 执行时间与 n2 成正比
2、关于数据结构的描述，不正确的是(  )。 A 数据结构相同，对应的存储结构也相同。
B 数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C 数据结构操作的实现与存储结构有关。
D 定义逻辑结构时可不考虑存储结构。
3、按排序策略分来，起泡排序属于(  )。
A 插入排序 B  选择排序    C  交换排序    D  归并排序
4、利用双向链表作线性表的存储结构的优点是(  )。
A  便于进行插入和删除的操作 B 提高按关系查数据元素的速度
C  节省空间                D 便于销毁结构释放空间
5、一个队列的进队顺序为 1,2,3,4，则该队列可能的输出序列是(  ) 。  A 1,2,3,4      B 1,3,2,4      C 1,4,2,3          D  4,3,2,1
6、Dijkstra 算法是按(  )方法求出图中从某顶点到其余顶点最短路径的。 A  按长度递减的顺序求出图的某顶点到其余顶点的最短路径
B  按长度递增的顺序求出图的某顶点到其余顶点的最短路径
C 通过深度优先遍历求出图中从某顶点到其余顶点的所有路径
D 通过广度优先遍历求出图的某顶点到其余顶点的最短路径
7、字符串可定义为 n (n≥0)个字符的有限(  )。其中， n 是字符串的长度，表明字符串
中字符的个数。
A  集合         B  数列        C  序列        D 聚合
8、在二维数组 A[9][10]中，每一个数组元素占用 3 个存储单元，从首地址 SA 开始按行连续 存放。在这种情况下，元素 A[8][5]的起始地址为(  )。
A  SA+141      B  SA+144      C  SA+222      D  SA+255
9、已知广义表为 L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它 的长度是(  )。
A 2            B  3            C  4            D  5
10. 对于具有 n(n>1)个顶点的强连通图，其有向边条数至少有_____。
A. n+1     B. n      C. n-1    D. n-2
11. 一个递归算法必须包括__________。
A. 递归部份  B. 结束条件和递归部份 C. 迭代部份  D. 结束条件和迭代部份
12. 从逻辑上看可以把数据结构分为__________两大类。
A．动态结构、静态结构      B．顺序结构、链式结构
C．线性结构、非线性结构    D．初等结构、构造型结构
13、若在长度为 n 的顺序表的表尾插入一个新元素的渐进时间复杂度为(  )。
A O(n)      B O(1)      C O(n2)    D O(log n)
2
14. 采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜 索长度为__________。
A. n          B. n/2            C. (n+1)/2            D. (n-1)/2
15、非空的循环单链表 first 的链尾结点(由 p 所指向)满足(  )。
A  p->link==NULL;              B  P==NULL;

C  p->link==first;              D  p==first;
16、用 S 表示进栈操作，用 X 表示出栈操作，若元素的进栈顺序是 1234，为了得到 1342 的出栈顺序，相应的 S 和X 的操作序列为(  )。
A  SXSXSSXX            B  SSSXXSXX
C SXSSXXSX            D  SXSSXSXX
17、含有 129 个叶结点的彻底二叉树，至少有(  )个结点。
A  254          B  255          C  257          D  258
18、一个有向图G 的邻接表存储如图 (1) 所示，现按深度优先搜索方式从顶点A 出发执行 一次遍历，所得的顶点序列是(  )。
A  1,2,3,4,5        B  1,2,3,5,4        C  1,2,4,5,3        D  1,2,5,3,4
19、树最合合用来表示(  )。
A 有序数据元素      B 元素之间具有分支层次关系的数据
C数据结构与算法第二版课后题答案 无序数据元素      D 元素之间无联系的数据
20、一棵有 124 个叶结点的彻底二叉树至少有(  )个结点。    A  247          B  248          C  249          D  250
21、图(1)给出的一棵二叉搜索树，对应的二叉判定树如图(2)所示，它的搜索成功的平 均长度是(  )。
A  21/7    B  28/7        C  15/6        D  16/6
图(1)二叉搜索树    图(2)二叉判定树
23、对 5 个不同的数据元素进行直接插入排序，最大需要进行(  )次比较。 A  8        B  10          C  15          D  25
24、将一个 n×n 的对称矩阵 A 的下三角部份按行存放在一个一维数组B 中，A[0][0]存放在 B[0]中，那末第 i 行的对角元素 A[i][i]在B 中的存放位置是(  )。
A  (i+3)*i/2    B  (i+1)*i/2        C  (2n-i+1)*i/2    D (2n-i-1)*i/2
25、已知广义表为 L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则 它的深度是(  )。
A 2            B  3            C  4            D  5
26、顺序搜索法适合于存储结构为(  )的线性表。
A  散列存储    B  顺序存储或者链式存储 C 压缩存储  D 索引存储
27、采用折半搜索方式搜索一个长度为 n 的有序顺序表时，其平均搜索长度为(  )。
A O(n)    B  O(log n)    C  O(n2)        D  O(nlog n)
2                                                                        2
28、n 个结点的线索二叉树中，线索的数目是(  )。
A  n-1        B  n+1          C  2n          D  2n-1
29、若数据元素序列{11,12,13,7,8,9,23,4,5}是采用下列排序方法之一得到的第二趟排序 后的结果，则该排序方法只能是(  )。
A 插入排序 B  选择排序    C  交换排序    D  归并排序

30、为了增加内存空间的利用率和减少溢出的可能， 在两个栈共享一片连续的存储空间时， 应将两个栈的栈顶分别设在这片存储空间的两端，当(  )时才产生上溢。
A 两个栈的栈顶同时到达栈空间的中心点
B 其中一个栈的栈顶到达栈空间的中心点
C 两个栈的栈顶在栈空间的某一位置相遇
D 两个栈的栈顶相加超过了栈空间的最大容量
31、设一棵二叉树的中序序列为 badce，后序遍历为 bdeca，则该二叉树前序遍历的顺序是 (  )。
A adbec      B decab        C debac        D abcde
32、图的简单路径是指(  )不重复的路径。
A  权值    B  顶点        C  边      D  边与顶点均不重复
33、用 n 个权值构造出来的 Huffman 树共有(  )个结点。    A 2n-1        B  2n          C  2n+1        D  n+1
34、在如图(2)所示的 AVL 树中插入关键码 48，得到了一棵新的 AVL 树，在这棵新的AVL 树中，关键码 37 所在结点的摆布子女结点中保存的关键码分别是(  )。
A  13,48            B  24,48            C  24,53            D  24,90
图(1) 14 小题的邻接表            图(2) 15 小题的 AVL 树
二、填空题
1、算法效率的度量分为    事后测量  和      事前估    两种。
2、算法是一个有穷的指令集， 它为解决某一特定任务规定了一个运算序列。 它应当具有输
入、输出、确定性、      有穷性      可行性等特性。
3、一个抽象数据类型 ADT 包括      数据操作    和  对象      两个部份。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。