C．BDFECA D．BDEFAC 37、循环队列的出队操作为 (A )
A.sq.front=(sq.ftont+1)% maxsize B.sq.front=sq.front+1
C.sq.rear=(sq.rear+)% maxsize D.sq.rear=sq.rear+1 38、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ C ）个。
A．n-1 B．n C．n+1 D．n+2
39、设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( B )
A.都不相同 B.完全相同 C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同
40、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为 (B )
A.R-F B. (n+R-F)mod n C.(R-F+1)mod n D. n+R-F 41、以下说法错误的是 (A )
A.树形结构的特点是一个结点可以有多个直接前趋 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达(组织)更复杂的数据 D.树(及一切树形结构)是一种\分支层次\结构 42、以下说法错误的是(B ) 。
A.二叉树可以是空集
B.二叉树的任一结点都有两棵子树 C.二叉树与树具有相同的树形结构 D.二叉树中任一结点的两棵子树有次序之分
43、在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ C ） A．n B．n-1 C．n+1 D．2*n 44、下列说法中正确的是（ A ）。 A.一棵二叉树的度可以小于2 B.二叉树中任何一个结点的度都为2 C.二叉树的度为2 D.任何一棵二叉树中至少有一个结点的度为2 45、在一棵具有5层的满二叉树中结点数为（ A ） A 31 B 32 C 33 D 16
46、一个二叉树按顺序方式存储在一个维数组中，如图
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 则结点E在二叉树的第（ C ）层。 A.1 B.2 C.3 D.4
47、在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的（D） A.先根遍历 B.中根遍历 C.后根遍历 D.按层次遍历
48、任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置 (C ) A.肯定发生变化 B.有时发生变化 C.肯定不发生变化 D.无法确定
49、在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于( B )。
h+1h-1hh
A. 2 B. 2 C. 2-1 D. 2
50、树若用双亲链表表示，则(A) A.可容易地实现求双亲及子孙的运算 B.求双亲及子孙的运算均较困难
C.可容易地实现求双亲运算，但求子孙运算较困难 D.可容易地实现求子孙运算，但求双亲运算较困难 51、任何一个带权的无向连通图的最小生成树（B）
A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在
52、设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ B ）。
A．O（nlog2e） B．O（n+e） C．O(ne) D．O(n2) 53、以下说法正确的是 （ A ）
A.连通图的生成树，是该连通图的一个极小连通子图。
B.无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 C.任何一个有向图，其全部顶点可以排成一个拓扑序列。 D.有回路的图不能进行拓扑排序。 54、以下说法错误的是 ( D )
A.一般在哈夫曼树中，权值越大的叶子离根结点越近 B.哈夫曼树中没有度数为1的分支结点
C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点
D.若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树 55、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则
该图一定是( B )
A.完全图 B.连通图 C.有回路 D.一棵树
56、将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点(B ) A.无左、右孩子 B.有左孩子，无右孩子 C.有右孩子，无左孩子 D.有左、右孩子
57、深度为6的二叉树最多有(B )个结点 A.64 B.63 C.32 D.31
58、一个有序顺表有255个对象，采用顺序搜索法查表，搜索长度为（ A ）。 A、128 B、127 C、126 D、255
59、在有向图中每个顶点的度等于该顶点的（ C ）。
A. 入度 B. 出度
C. 入度与出度之和 D. 入度与出度之差
60、具有n个顶点的有向无环图最多可包含( D )条有向边。 A．n-1 B．n C．n(n-1)/2 D．n(n-1)
61、用邻接表作为有向图G的存储结构。设有n个顶点、e条弧，则拓扑排序的时间复杂度为(B ) A. O(n) B. O(n+e) C. O(e) D. O(n*e)
62、一个有序顺表有255个对象，采用顺序搜索法查表，搜索长度为（A）。 A、128 B、127 C、126 D、255
63、在有向图中，所有顶点的入度之和是所有顶点出度之和的（B）倍。 A.0.5 B. 1 C. 2 D.4 64、以下说法错误的是（B）
A.用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
B.邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。
C.存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了
D.用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第 i行第j列的元素是否为0即可。
65、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（ A ） A.先根遍历 B. 中根遍历 C. 后根遍历 D按层次遍历 66、在一个无向图中，所有顶点的度数之和等于所有边数的（ B ）倍。 A．3 B．2 C．1 D．1/2
67、在无向图中，所有顶点的度数之和是所有边数的（ C ）倍。 A.0.5 B.1 C.2 D.4
68、设有6个结点的无向图，该图至少应有（B）条边能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 69、以下说法正确的是（ D ）
A.连通分量是无向图中的极小连通子图。 B.强连通分量是有向图中的极大强连通子图。
C.在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。 D.对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。
70、对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（ C ）。
A．R[0]，R[1]，R[2]，R[3] B．R[0]，R[13]，R[2]，R[3] C．R[6]，R[2]，R[4]，R[3] D．R[6]，R[4]，R[2]，R[3]
71、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为99的结点时，经（ C ）次比较后查找成功。 A.2 B. 3 C.4 C. 12
72、设有100个数据元素，采用折半搜索时，最大比较次数为（B） A 6 B 7 C 8 D 10
73、对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（ B）
A．n/2 B．(n+1)/2 C．(n –1)/2 D．n/4
74、对采用二分查找法进行查找运算的查找表，要求按（C）方式进行存储。 A顺序存储 B 链式存储
C顺序存储且结点按关键字有序 D 链式存储且结点按关键字有序 75、二分查找法适用于存储结构为（A）的，且按关键字排序的线性表 A.顺序存储 B. 链接存储 C. 顺序存储或链接存储 D.索引存储
76、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（B ） A. O(n) B. O(n/2) C. O(1) D. O(n2)
77、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于(C )
A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D.两种表都不适合
78、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ B ）
2
A．O (n) B．O (1) C．O (n) D．O (log2 n)
79、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（ C ）次比较后查找成功。 A2 B 3 C 4 D 12
80、静态查找表与动态查找表两者的根本差别在于（ C ）
A逻辑结构不同 B 存储实现不同
C施加的操作不同 D 数据元素的类型不同
2
81、以下时间复杂性不是O(n)的排序方法是 （ B ） A.直接插入排序 B.二路归并排序 C.冒泡排序 D.直接选择排序
82、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ C）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84} C．{40，38，46，56，79，84} D．{38，46，56，79，40，84} 83、用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为（C） A.O（n2） B. O(nlog2n) C. O（n） D O(log2n)
84、用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下：
25 84 21 47 15 27 68 35 20 15 20 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则采取的排序方法是 （ C ）
A.直接选择排序 B.冒泡排序 C.快速排序 D.二路归并排序
85、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ C ）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84} C．{40，38，46，56，79，84} D．{38，46，56，79，40，84} 86、顺序查找法适合于（ D ）存储结构的查找表。
A.压缩 B. 散列 C.索引 D.顺序或链式 87、以下说法错误的是 （C ）
A.直接插入排序的空间复杂度为O(1)。 B.快速排序附加存储开销为O(log2n)。 C.堆排序的空间复杂度为O(n)。
D.二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。 88、对于大文件的排序要研究在外设上的排序技术，即（ C）
A.快速排序法 B. 内排序法 C.外排序法 D.交叉排序法
89、对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ C ）的值除以9。
A. 20 B. 18 C. 25 D. 22
90、具有24个记录的序列，采用冒泡排序至少的比较次数是 （ B ） A.1 B.23 C. 24 D. 529
91、当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（ A） A.n-1 B.log2n C. 2log2n D.n2
92、排序的目的是为了以后对已排序的数据元数进行（D）操作。 A.打印输出 B.分类 C. 合并 D.查找 93、以下稳定的排序方法是 （ B）
A.快速排序 B.冒泡排序 C.直接选择排序 D. 堆排序 94、（ B ）方法是从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。
A.归并排序 B. 插入排序 C.快速排序 D.选择排序
95、在文件局部有序或文件长度较小的情况下，最佳的排序方法是 （A） A.直接插入排序 B. 冒泡排序 C. 直接选择排序 D.归并排序
96、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（ C ）方法最快。 A．起泡排序 B．快速排序 C．堆排序 D．直接选择排序
97、对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（ C ）方法。
A.归并排序 B.直接插入排序 C.直接选择排序 D.快速排序
98、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ C ） A 直接选择排序 B 直接插入排序 C 快速排序 D 起泡排序 99、以下不稳定的排序方法是 （ C ）
A.直接插入排序 B.冒泡排序 C.直接选择排序 D.二路归并排
100、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（B ） A. O(n) B. O(n/2) C. O(1) D. O(n2)
三、填空题
1、有一个算法由3个部分的线性代码连接组成，每部分的时间复杂度分别为O（n）、O（n2）、O（ n4 ）,该算法的时间复杂度为(O（ n4 ）)。
2、数据的基本单位是(数据元素) 。
3、计算机中的算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、可行性、(确定性)和(有穷性)等5个特征
4、所有结点按1对1的邻接关系构成的整体就是(线性) 结构 5、数据元素之间的关联方式或称“邻接关系”称为(逻辑)关系。
6、有一个算法由3个部分的代码嵌套连接组成，每部分的时间复杂度分别为O（n）、O（n2）、O（ n4 ）,该算法的时间复杂度为( O（ n7 ） )。
7、数据元素之间逻辑关系的整体称为(逻辑结构) 。
8、对一个算法要作出全面的分析可分成两用人才个阶段进行，即事先分析和(事后测试)。 9、算法的复杂度分为(时间复杂度) 和(空间复杂度) 两种。
10、数据在计算机中的存储表示（机内表示）称为数据的( 存储结构 )。 11、文件的检索有顺序存取、直接存取和( 按关键字存取)三种方式。 12、文件的检索有顺序存取、直接存取和(按关键字存取)三种方式。 13、在顺序表中插入或删除一个元素，需要平均移动((n+1)/2 )元素，具体移动的元素个数与( ) 有关。
14、VSAM文件结构由三部分组成：索引集、(顺序集)和数据集。
15、ISAM文件是由多级主索引、柱面索引、磁道索引和(主文件索引)组成。
16、已知：s1=〃I’m a teacher〃，s2=〃teacher〃，s3=〃student〃，则REPLACE(s1,s2, s3) 等于(I’m a teacher )。
17、如果文件中的每个记录都有一个索引项，则这样的索引称为(稠密索引) 。 18、如果文件中多个记录只有一个索引项，则这样的索引称为(非稠密索引)。
19、在双链表中，每个结点有两个指针域，一个指向(前驱)， 另一个指向(后继)。
20、当且仅当两个串的(长度)相等并且各个对应位置上的字符都相同时，这两个串相等。一个串中任意个