新学年天津大学《数据结构》在线作业二

奥鹏天津大学平时在线作业

《数据结构》在线作业二

设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（ ）次线性探测。
A:n2
B:n(n+1)
C:n(n+1)/2
D:n(n-1)/2
答案问询微信：424329

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

设一个顺序有序表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]
答案问询微信：424329

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

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

一组记录的关键码为（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
答案问询微信：424329

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

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

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

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

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

一个有n个顶点的无向连通图，它所包含的连通分量个数为（）。
A:0
B:1
C:n
D:n+1
答案问询微信：424329

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

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

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

散列表的平均查找长度（）。
A:与处理冲突方法有关而与表的长度无关
B:与处理冲突方法无关而与表的长度有关
C:与处理冲突方法有关而与表的长度有关
D:与处理冲突方法无关而与表的长度无关
答案问询微信：424329

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

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

在一个图中，所有顶点的度数之和等于所有边数的（）倍。
A:1/2
B:1
C:2
D:4
答案问询微信：424329

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

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

下列程序段的时间复杂度为（ ）。 for(i=0； im； i++) for(j=0； j奥鹏天津大学平时在线作业t； 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)
答案问询微信：424329

一组记录的排序码为（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
答案问询微信：424329

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

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

程序段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)
答案问询微信：424329

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

字符串的长度是指（ ）。
A:串中不同字符的个数
B:串中不同字母的个数
C:串中所含字符的个数
D:串中不同数字的个数
答案问询微信：424329

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

关键路径是事件结点网络中（）。
A:从源点到汇点的最长路径
B:从源点到汇点的最短路径
C:最长的回路
D:最短的回路
答案问询微信：424329

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

设哈希表长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
答案问询微信：424329

堆的形状是一棵（）。
A:二叉排序树
B:满二叉树
C:完全二叉树
D:平衡二叉树
答案问询微信：424329

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

（ ）二叉排序树可以得到一个从小到大的有序序列。
A:先序遍历
B:中序遍历
C:后序遍历
D:层次遍历
答案问询微信：424329

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

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

设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
答案问询微信：424329

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

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