天津大学19秋《数据结构》在线作业二
天津大学19秋《数据结构》在线作业二1.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（）次线性探测。
A.n2
B.n(n+1)
C.n(n+1)/2
D.n(n1)/2
答案
2.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。
A.6
B.11
C.5
D.6.5
答案
3.设一个顺序有序表A中有14个元素，则采用二分法查找元素A的过程中比较元素的顺序为()。
A.A，A，A，A
B.A，A，A，A
C.A，A，A，A
D.A，A，A，A
答案
4.具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。
A.5
B.6
C.7
D.8
答案
5.设完全无向图中有n个顶点，则该完全无向图中有（）条边。
A.n(n1)/2
B.n(n1)
C.n(n+1)/2
D.(n1)/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=0；for(i=0；im；i++)for(j=0；jt；j++)for(k=0；kn；k++)c=c+a*b；
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，4656，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.n1
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)=4addr(38)=5addr(61)=6addr(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.N11
B.N21
C.N2+N3
D.N1+N3
答案
39.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。
A.求关键路径的方法
B.求最短路径的Dijkstra方法
C.宽度优先遍历算法
D.深度优先遍历算法
答案
40.设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。
A.ni
B.n1i
C.n+li
D.不能确定
答案
页:
[1]