19秋天大《数据结构》在线作业二(100分)

admin

试卷名称:《数据结构》在线作业二
1.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（  ）次线性探测。
A.n2
B.n(n+1)
C.n(n+1)/2
D.n(n-1)/2
答案:-

2.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（  ）。
A.6
B.11
C.5
D.6.5
答案:-

3.设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较 元素的顺序为(  )。
A.A[1]，A[2]，A[3]，A[4]
B.A[1]，A[14]，A[7]，A[4]
C.A[7]，A[3]，A[5]，A[4]
D.A[7]，A[5] ，A[3]，A[4]
答案:-

4.具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。
A.5
B.6
C.7
D.8
答案:-

5.设完全无向图中有n个顶点，则该完全无向图中有（  ）条边。
A.n(n-1)/2
B.n(n-1)
C.n(n+1)/2
D.(n-1)/2
答案:-

6.一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。
A.38，40，46，56，79，84
B.40，38，46，79，56，84
C.40，38，46，56，79，84
D.40，38，46，84，56，79
答案:-

7.下述几种排序方法中，要求内存量最大的是（）。
A.插入排序
B.选择排序
C.快速排序
D.归并排序
答案:-

8.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。
A.先序遍历
B.中序遍历
C.后序遍历
D.按层遍历
答案:-

9.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。
A.希尔排序
B.起泡排序
C.插入排序
D.选择排序
答案:-

10.设一组初始记录关键字的长度为8，则最多经过（  ）趟插入排序可以得到有序序列。
A.6
B.7
C.8
D.9
答案:-

11.对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（）。
A.静态查找表
B.动态查找表
C.静态查找表与动态查找表
D.两种表都不适合
答案:-

12.一个有n个顶点的无向连通图，它所包含的连通分量个数为（）。
A.0
B.1
C.n
D.n+1
答案:-

13.解决散列法中出现的冲突问题常采用的方法是（）。
A.数字分析法、除余法、平方取中法
B.数字分析法、除余法、线性探测法
C.数字分析法、线性探测法、多重散列法
D.线性探测法、多重散列法、链地址法
答案:-

14.对线性表进行二分查找时，要求线性表必须（）。
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储，且结点按关键字有序排序
D.以链接方式存储，且结点按关键字有序排序
答案:-

15.设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（  ）。
A.1
B.2
C.3
D.4
答案:-

16.散列表的平均查找长度（）。
A.与处理冲突方法有关而与表的长度无关
B.与处理冲突方法无关而与表的长度有关
C.与处理冲突方法有关而与表的长度有关
D.与处理冲突方法无关而与表的长度无关
答案:-

17.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，（）次比较后查找成功。
A.1
B.2
C.4
D.8
答案:-

18.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（）排序法。
A.起泡排序
B.快速排序
C.堆排序
D.基数排序
答案:-

19.在一个图中，所有顶点的度数之和等于所有边数的（）倍。
A.1/2
B.1
C.2
D.4
答案:-

20.下列程序段的时间复杂度为（  ）。  i=0，s=0； while (sn) {s=s+i；i++；}
A.O(n1/2)
B.O(n1/3)
C.O(n)
D.O(n2 )
答案:-

21.设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={1，2，2，3，3，4，4，1}，则数据结构A是（???）。
A.线性结构
B.树型结构
C.图型结构
D.集合
答案:-

22.下列程序段的时间复杂度为（  ）。  for(i=0； im； i++) for(j=0； jt； j++) c[i][j]=0； for(i=0； im； i++) for(j=0； jt； j++) for(k=0； kn； k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]；
A.O(m*n*t)
B.O(m+n+t)
C.O(m+n*t)
D.O(m*t+n)
答案:-

23.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。
A.79，46，56，38，40，80
B.38，46,56，79，40，84，
C.84，79，56，46，40，38
D.84，56，79，40，46，38
答案:-

24.设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（  ）。
A.129
B.219
C.189
D.229
答案:-

25.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。
A.n
B.n+1
C.n-1
D.n/2
答案:-

26.程序段s=i=0；do {i=i+1； s=s+i；}while(i=n)；的时间复杂度为（  ）。
A.O(n)
B.O(nlog2n)
C.O(n2)
D.O(n3 /2)
答案:-

27.在二叉排序树中插入一个关键字值的平均时间复杂度为（  ）。
A.O(n)
B.O(1og2n)
C.O(nlog2n)
D.O(n2 )
答案:-

28.字符串的长度是指（   ）。
A.串中不同字符的个数
B.串中不同字母的个数
C.串中所含字符的个数
D.串中不同数字的个数
答案:-

29.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。
A.希尔排序
B.起泡排序
C.插入排序
D.选择排序
答案:-

30.关键路径是事件结点网络中（）。
A.从源点到汇点的最长路径
B.从源点到汇点的最短路径
C.最长的回路
D.最短的回路
答案:-

31.下述几种排序方法中，平均查找长度最小的是（）。
A.插入排序
B.选择排序
C.快速排序
D.归并排序
答案:-

32.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr (15)=4;addr (38)=5;addr (61)=6;addr (84)=7，如用二次探测再散列处理冲突，关键字为49的结点的地址是（）。
A.8
B.3
C.5
D.9
答案:-

33.堆的形状是一棵（）。
A.二叉排序树
B.满二叉树
C.完全二叉树
D.平衡二叉树
答案:-

34.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。
A.35/12
B.37/12
C.39/12
D.43/12
答案:-

35.（  ）二叉排序树可以得到一个从小到大的有序序列。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
答案:-

36.下面不正确的说法是（）。
A.在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小
B.AOE网工程工期为关键活动上的权之和
C.在关键路径上的活动都是关键活动，而关键活动也必在关键路径上
D.以上都不对
答案:-

37.把一棵树转换为二叉树后，这棵二叉树的形态是（）。
A.唯一的
B.有多种
C.有多种，但根结点都没有左孩子
D.有多种，但根结点都没有右孩子
答案:-

38.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（   ）。
A.N1-1
B.N2-1
C.N2+N3
D.N1+N3
答案:-

39.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。
A.求关键路径的方法
B.求最短路径的Dijkstra方法
C.宽度优先遍历算法
D.深度优先遍历算法
答案:-

40.设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（  ）。
A.n-i
B.n-1-i
C.n+l -i
D.不能确定
答案:-