试卷详情
-
计算机四级-数据结构与算法
-
[单项选择]栈S最多能容纳4个元素。现有6个元素按1,2,3,4,5,6的顺序进栈,则下列哪一个序列是可能的出栈序列( )
A. 5,4,3,2,1,6
B. 2,3,5,6,1,4
C. 3,2,5,4,1,6
D. 1,4,6,5,2,3
-
[单项选择]设有100个结点,用二分法查找时,最大比较次数是( )。
A. 25
B. 50
C. 10
D. 7
-
[单项选择]对关键码集合K={53,30,37,12,45,24,96},从空二叉树开始逐个插入每个关键码,建立与集合K相对应的二叉排序树,若希望得到最佳二叉排序树,应选择下列( )输入序列。
A. 45,24,53,12,37,96,30
B. 30,24,12,37,45,96,53
C. 12,24,30,37,45,53,96
D. 37,24,12,30,53,45,96
-
[单项选择]The sorting method described by the following code is called( ). FOR i:=1 TO n—1 do BEGIN k: =i; FOR j: =i+1 TO n DO IF A[j]<A[K] THEN k:=j; IF k<>i THEN BEGIN x:=A[k]; A[k]: = A[i]; A[i]:=x END END;
A. insertion sort
B. selection sort
C. radix sort
D. merge sort
-
[简答题](1)试说明给定一棵二叉树结点的后序序列和中序序列,则此二叉树可构造出来。
(2)一棵二叉树的中序序列为BFDGAEHC,后序序列为FGDBHECA,构造出此二叉树。
-
[单项选择]下面序列是堆的是( )。
A. 97,56,38,66,23,42,12
B. 23,86,48,3,35,39,42
C. 05,56,20,23,40,38,29
D. 05,23,16,68,94,72,71,73
-
[单项选择]下面关于有向图的叙述中,哪个(些)是正确的( ) Ⅰ.求有向图结点的拓扑序列,其结果必定是惟一的 Ⅱ.求两个指向结点间的最短路径,其结果必定是惟一的 Ⅲ.求事件结点网络的关键路径,其结果必定是惟一的
A. 只有Ⅰ
B. Ⅰ和Ⅱ
C. 都正确
D. 都不正确
-
[单项选择]如果要求一个线性表既能较快地查找,又能适应动态变化的要求,则可采用的方法是 ( )。
A. 分块法
B. 顺序法
C. 二分法
D. 散列法
-
[单项选择]设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5和e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的顺序是e2、e4、e3、e6、e5、e1,则栈S的容量至少应该是(
)。
A. 3
B. 4
C. 5
D. 2
-
[单项选择]下面哪种情况用直接插入排序方法进行由小到大排序,元素比较次数最少( )
A. 元素的关键码值按由小到大排列
B. 元素的关键码值按由大到小排列
C. 部分元素按由小到大排列
D. 元素任意排放
-
[简答题]散列表是一种重要的存储方式,在散列表里可快速进行检索。
(1)散列表的基本思想是什么
(2)常用的散列函数有哪些,请举例说明(至少三个)。
(3)怎样用拉链法和开地址法处理碰撞
-
[单项选择]设树T的度为4,其中度为1、2、3和4的结点的个数分别为4、2、1、1,则T中叶子结点的个数是( )。
A. 6
B. 7
C. 8
D. 9
-
[单项选择]以下关键码序列用快速排序法进行排序,速度最慢的是( )。
A. {23,27,7,19,11,25,32}
B. {23,11,19,32,27,25,7}
C. {7,11,19,23,25,27,32}
D. {27,25,32,19,23,7,11}
-
[单项选择]下列关于二叉树周游的叙述中,正确的是( )。
A. 若一个结点是某二叉树的后序最后一个结点,则它必是该二叉树的根结点
B. 若一个结点是某二叉树的前序最后一个结点,则它必是该二叉树的中序最后一个结点
C. 若一个结点是某二叉树的中序最后一个结点,则它必是该二叉树的前序最后一个结点
D. 若一个树叶是某二叉树的前序最后一个结点,则它必是该二叉树的中序最后一个结点
-
[单项选择]二叉排序树的平均检索长度为( )。
A. O(
B. O(n2)
C. O(log2
D. O(nlog2
-
[单项选择]若二叉树前序周游访问结点顺序为ABCDEFG,中序周游访问结点顺序为CBDAFGE,则其后序周游访问结点顺序为( )。
A. CDBAGFE
B. CDBGFEA
C. CDBFAGE
D. CDGFEAB
-
[单项选择]在有向图G的拓扑序列中,如果顶点Vi在Vi之前,则在下列情况中一定不可能出现的是( )。
A. G中有弧<Vi,Vi>
B. G中没有弧<Vi,V(i>
C. G中有一条从Vi到Vi的路径
D. G中有一条从Vi到Vi的路径
-
[单项选择]对线性表进行二分法查找,其前提条件是( )。
A. 线性表以顺序方式存储,并且按关键码值排好序
B. 线性表以顺序方式存储,并且按关键码值的检索频率排好序
C. 线性表以链接方式存储,并且按关键码值排好序
D. 线性表以链接方式存储,并且按关键码值的检索频率排好序
-
[单项选择]有关二叉树的下列说法正确的是( )。
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C. 二叉树中任何一个结点的度都为2
D. 任何一棵二叉树中至少有一个结点的度为2
-
[单项选择]用快速排序法对包含n个关键字的序列进行排序,最坏情况下的执行时间为( )。
A. O(nlog2
B. O(n2)
C. O(log2
D. O(
-
[单项选择]用堆排序方法,最坏情况下,所需时间为( )。
A. O(
B. O(n2)
C. O(log2
D. O(n log2
-
[单项选择]下列排序方法中,哪一种方法的比较次数与记录的初始排列状态无关( )
A. 直接插入排序
B. 起泡排序
C. 快速排序
D. 直接选择排序
-
[单项选择]When the adjacency list method is used to store a graph,Which of the statements is(are) true( ) Ⅰ.The space required depends on the number of vertices Ⅱ.The space required depends on the number of edges
A. ⅠandⅡ
B. Ⅰ only
C. Ⅱonly
D. None
-
[单项选择]对以下序列{22,86,19,49,12,30,65,35,18}进行排序,排序过程如下: (1) {22,86,19,49,12,30,65,35,18} (2) {18,12,19,22,49,30,65,35,86} (3) {12,18,19,22,35,30,49,65,86} (4) {12,18,19,22,30,35,49,65,86} 则可以认为使用了( )排序方法。
A. 选择排序
B. 起泡排序
C. 快速排序
D. 插入排序
-
[单项选择]下面关于数据结构的叙述中,正确的叙述是( )。
A. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高
B. 链表中的每一个结点都包含恰好一个指针
C. 包含n个结点的二叉排序树的最大检索长度为log2n
D. 将一棵树转换为二叉树后,根结点没有右子树
-
[单项选择]设仅包含根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为( )。
A. 2k+1
B. 2k+1-1
C. 2k+1+1
D. 2k+1
-
[单项选择]用链接方式存储的队列,在进行删除运算时,下面操作正确的是( )。
A. 仅修改头指针
B. 仅修改尾指针
C. 头、尾指针都要修改
D. 头、尾指针可能都要修改
-
[单项选择]若待排序序列已基本有序,要使它完全有序,从关键码比较次数和移动次数考虑,应当使用的排序方法是( )。
A. 归并排序
B. 直接插入排序
C. 直接选择排序
D. 快速排序
-
[单项选择]在二叉树结点的先序序列、中序序列、后序序列中,所有叶子结点的先后顺序( )。
A. 完全相同
B. 都不相同
C. 先序和中序相同,而与后序不同
D. 中序和后序相同,而与先序不同
-
[单项选择]在待排序文件已基本有序的前提下,下述排序方法中效率最高的是( )。
A. 直接插入排序
B. 堆排序
C. 二路归并排序
D. 起泡排序
-
[单项选择]The figure below Shows a record used for recording information about a named event. Which of the following statement is incorrect ( ) VAR r: RECORD event: ARRAY[1.. 10] of Char; place: ARRAY[1.. 20] of RECORD plname: ARRAY[1.. 15]of Char; date: ARRAY[1.. 5] of RECORD mo: 1.. 12; day: 1..31; year: Integer END END END;
A. This is a one—dimensional array of records, also called a table
B. The event can occur in up to 20 places and on up to 5 different dates in each place
C. This is so called record of arrays
D. A reference to place, date, mo will access the month of the jth occurrence, in the ith place, of the event named in event
-
[单项选择]对包含n个元素的散列表进行检索,平均检索长度为( )。
A. 不直接依赖于n
B. O(n2)
C. O(
D. O(log2
-
[单项选择]图的广度优先周游类似于树的( )。
A. 先序遍历
B. 中序遍历
C. 按层遍历
D. 后序遍历
-
[单项选择]以下( )不是队列的基本运算。
A. 从队尾插入一个新元素
B. 从队列中删除第i个元素
C. 判断一个队列是否为空
D. 读取队头元素的值
-
[单项选择]对无向图G(下图),若从顶点V1开始,按深度优先搜索法进行遍历,则可能的访问顺序是( )。
A. V1V2V3V4V5V6V7V8
B. V1V2V3V5V4V6V7V8
C. V1V2V6V3V4V7V8V5
D. V1V2V6V3V5V4V7V8
-
[单项选择]一个序列中有若干个元素,若只想得到其中第i个元素之前的部分排序,最好采用什么排序方法( )
A. 起泡排序
B. 堆排序
C. 插入排序
D. 归并排序
-
[单项选择]能构造出( )种不同的二叉排序树。
试题8、9基于下面的叙述:现有关键码值分别为11、23、31、54的4个结点,按所有可能的插入顺序去构造二叉排序树。
A. 20
B. 14
C. 16
D. 8
-
[单项选择]二叉树的先序遍历和中序遍历如下; 先序遍历:EFHIGJK 中序遍历:HFIEJKG 该二叉树根结点的右子树由哪些结点组成( )
A. FHI
B. EFH
C. JKG
D. EJKG
-
[单项选择]An algorithm to solve a given problem has time complexity
T(n) =
nlog2n-(n-1) Given that the algorithm takes 0.8 second
for a problem in which n=1024, how long should it take for a problem in which
n=4096 ( )
A. 39 seconds
B. 0.8 seconds
C. 3.9 minutes
D. 3.9 seconds