计算机四级-数据结构与算法
(总分60, 做题时间90分钟)
一、选择题
(一)中文题
1. 
在有向图G的拓扑序列中，如果顶点Vi在Vi之前，则在下列情况中一定不可能出现的是(    )。
A 
G中有弧＜Vi，Vi＞
B 
G中没有弧＜Vi，V(i＞
C 
G中有一条从Vi到Vi的路径
D 
G中有一条从Vi到Vi的路径
2. 
如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的方法是 (    )。
A 分块法
B 顺序法
C 二分法
D 散列法
3. 
一个序列中有若干个元素，若只想得到其中第i个元素之前的部分排序，最好采用什么排序方法?(    )
A 起泡排序
B 堆排序
C 插入排序
D 归并排序
4. 
栈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
5. 
若待排序序列已基本有序，要使它完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是(  )。
A 归并排序
B 直接插入排序
C 直接选择排序
D 快速排序
6. 
下列排序方法中，哪一种方法的比较次数与记录的初始排列状态无关?(    )
A 直接插入排序
B 起泡排序
C 快速排序
D 直接选择排序
7. 
下面关于数据结构的叙述中，正确的叙述是(    )。
A 顺序存储方式的优点是存储密度大，且插入、删除运算效率高
B 链表中的每一个结点都包含恰好一个指针
C 
包含n个结点的二叉排序树的最大检索长度为log2n
D 将一棵树转换为二叉树后，根结点没有右子树
8. 
用快速排序法对包含n个关键字的序列进行排序，最坏情况下的执行时间为(    )。
A 
O(nlog2
B 
O(n2)
C 
O(log2
D O(
9. 
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
10. 
二叉树的先序遍历和中序遍历如下；    先序遍历：EFHIGJK    中序遍历：HFIEJKG    该二叉树根结点的右子树由哪些结点组成?(    )
A FHI
B EFH
C JKG
D EJKG
11. 
对无向图G(下图)，若从顶点V1开始，按深度优先搜索法进行遍历，则可能的访问顺序是(    )。
A 
V1V2V3V4V5V6V7V8
B 
V1V2V3V5V4V6V7V8
C 
V1V2V6V3V4V7V8V5
D 
V1V2V6V3V5V4V7V8
12. 
对包含n个元素的散列表进行检索，平均检索长度为(    )。
A 不直接依赖于n
B 
O(n2)
C O(
D 
O(log2
13. 
下面关于有向图的叙述中，哪个(些)是正确的?(    )    Ⅰ．求有向图结点的拓扑序列，其结果必定是惟一的    Ⅱ．求两个指向结点间的最短路径，其结果必定是惟一的    Ⅲ．求事件结点网络的关键路径，其结果必定是惟一的
A 只有Ⅰ
B Ⅰ和Ⅱ
C 都正确
D 都不正确
14. 
用堆排序方法，最坏情况下，所需时间为(    )。
A O(
B 
O(n2)
C 
O(log2
D 
O(n log2
15. 
以下关键码序列用快速排序法进行排序，速度最慢的是(    )。
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}
16. 
设有100个结点，用二分法查找时，最大比较次数是(    )。
A 25
B 50
C 10
D 7
17. 
一个n×n的带状矩阵A=[aij]如下        将带状区域中的元素aij(|i-j|≤1)按行序为主序存储在一维数组B[1..3n-2]中，元素aij在B中的存储位置是(    )。
A i+2j-1
B 2i+j-2
C 3i-j+1
D i+j+2
18. 
在待排序文件已基本有序的前提下，下述排序方法中效率最高的是(    )。
A 直接插入排序
B 堆排序
C 二路归并排序
D 起泡排序
19. 
设树T的度为4，其中度为1、2、3和4的结点的个数分别为4、2、1、1，则T中叶子结点的个数是(    )。
A 6
B 7
C 8
D 9
20. 
设仅包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为(    )。
A 
2k+1
B 
2k+1-1
C 
2k+1+1
D 
2k+1
21. 
设有向图G有n个顶点，它的邻接矩阵为A，G中第i个顶点Vi的度为(    )。
A  B  C  D  
22. 
设散列表的存储空间大小为19，所用散列函数为H(key)＝key mod 19，用开地址线性探查法解决碰撞。散列表的当前状态如下：              现要将关键码值75插入到该散列表中，其地址应为(    )。
A 0
B 11
C 15
D 17
23. 
A hash table with hash function is shown below.H1(k)=k mod 13    Collision is resolved using the hash function H2(k)=(k mod 11)q-1. How many key comparisons occur in searching for key 62 in the given hash table? (     )
A 1
B 2
C 3
D 4
24. 
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
25. 
图的广度优先周游类似于树的(    )。
A 先序遍历
B 中序遍历
C 按层遍历
D 后序遍历
26. 
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
27. 
用链接方式存储的队列，在进行删除运算时，下面操作正确的是(    )。
A 仅修改头指针
B 仅修改尾指针
C 头、尾指针都要修改
D 头、尾指针可能都要修改
28. 
对线性表进行二分法查找，其前提条件是(    )。
A 线性表以顺序方式存储，并且按关键码值排好序
B 线性表以顺序方式存储，并且按关键码值的检索频率排好序
C 线性表以链接方式存储，并且按关键码值排好序
D 线性表以链接方式存储，并且按关键码值的检索频率排好序
29. 
下列关于二叉树周游的叙述中，正确的是(    )。
A 若一个结点是某二叉树的后序最后一个结点，则它必是该二叉树的根结点
B 若一个结点是某二叉树的前序最后一个结点，则它必是该二叉树的中序最后一个结点
C 若一个结点是某二叉树的中序最后一个结点，则它必是该二叉树的前序最后一个结点
D 若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序最后一个结点
30. 
对关键码集合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
31. 
有关二叉树的下列说法正确的是(    )。
A 二叉树的度为2
B 一棵二叉树的度可以小于2
C 二叉树中任何一个结点的度都为2
D 任何一棵二叉树中至少有一个结点的度为2
32. 
若二叉树前序周游访问结点顺序为ABCDEFG，中序周游访问结点顺序为CBDAFGE，则其后序周游访问结点顺序为(    )。
A CDBAGFE
B CDBGFEA
C CDBFAGE
D CDGFEAB
33. 
在二叉树结点的先序序列、中序序列、后序序列中，所有叶子结点的先后顺序(    )。
A 完全相同
B 都不相同
C 先序和中序相同，而与后序不同
D 中序和后序相同，而与先序不同
34. 
二叉排序树的平均检索长度为(    )。
A O(
B 
O(n2)
C 
O(log2
D 
O(nlog2
35. 
有向图G(下图)的结点可以排成(    )个不同的拓扑序列。   
A 3
B 5
C 7
D 9
36. 
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
    试题8、9基于下面的叙述：现有关键码值分别为11、23、31、54的4个结点，按所有可能的插入顺序去构造二叉排序树。
37. 
能构造出(    )种不同的二叉排序树。
A 20
B 14
C 16
D 8
38. 
这些二叉排序树中有(    )棵是最佳二叉排序树。
A 6
B 5
C 4
D 3
39. 
以下(    )不是队列的基本运算。
A 从队尾插入一个新元素
B 从队列中删除第i个元素
C 判断一个队列是否为空
D 读取队头元素的值
40. 
下面序列是堆的是(    )。
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
41. 
下面的二叉树，(    )是完全二叉树。
   
A  B  C  D  
42. 
下面哪种情况用直接插入排序方法进行由小到大排序，元素比较次数最少?(    )
A 元素的关键码值按由小到大排列
B 元素的关键码值按由大到小排列
C 部分元素按由小到大排列
D 元素任意排放
43. 
对以下序列{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 插入排序
44. 
设栈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
45. 
如下图G，它的拓扑序列是(    )。         
A a，c，b，d
B a，d，b，c
C a，b，d，c
D b，a，d，c
二、论述题
46. 
散列表是一种重要的存储方式，在散列表里可快速进行检索。
   (1)散列表的基本思想是什么?
   (2)常用的散列函数有哪些，请举例说明(至少三个)。
   (3)怎样用拉链法和开地址法处理碰撞?
47. 
(1)试说明给定一棵二叉树结点的后序序列和中序序列，则此二叉树可构造出来。
   (2)一棵二叉树的中序序列为BFDGAEHC，后序序列为FGDBHECA，构造出此二叉树。
48. 
要在n个居民点之间铺设煤气管道。工人们面临如下问题：
   (1)设计一种付出经济代价最小的解决问题的方案。
   (2)给出解决该问题的具体方法。
   (3)图G是一个居民点的煤气管道铺设代价网，给出它的经济代价最小的图示。
答题卡