天津大学19春《数据结构》在线作业二（含答案）
《数据结构》在线作业二奥鹏作业答案
奥鹏天津大学作业
一、单选题：
1.[单选题]对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为（）。
A.从第0个元素往后查找该数据元素
B.从第1个元素往后查找该数据元素
C.从第n个元素往开始前查找该数据元素
D.与查找顺序无关
正确答案:——C——
2.[单选题]数组的逻辑结构不同于下列（??）的逻辑结构。
A.线性表
B.栈
C.队列
D.树
正确答案:——D——
3.[单选题]设哈希表长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
正确答案:——D——
4.[单选题]排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。
A.希尔排序
B.归并排序
C.插入排序
D.选择排序
正确答案:————
5.[单选题]字符串的长度是指（ ）。 奥鹏作业答案
A.串中不同字符的个数
B.串中不同字母的个数
C.串中所含字符的个数
D.串中不同数字的个数
正确答案:————
6.[单选题]设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。
A.129
B.219
C.189
D.229
正确答案:————
7.[单选题]对线性表进行二分查找时，要求线性表必须（）。
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储，且结点按关键字有序排序
D.以链接方式存储，且结点按关键字有序排序
正确答案:————
8.[单选题]二叉树中第i(i≥1)层上的结点数最多有（??）个。
A.2i
B.2i
C.2i-1
D.2i-1
正确答案:————
9.[单选题]采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。
A.O（n2）
B.O(nlog2n)
C.O(n)
D.O(log2n)
正确答案:————
10.[单选题]不含任何结点的空树（）。
A.是一棵树
B.是一棵二叉树
C.是一棵树也是一棵二叉树
D.既不是树也不是二叉树
正确答案:————
11.[单选题]设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。
A.2n
B.n+l
C.2n-1
D.2n+l
正确答案:————
12.[单选题]对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（）。
A.静态查找表
B.动态查找表
C.静态查找表与动态查找表
D.两种表都不适合
正确答案:————
13.[单选题]散列表的平均查找长度（）。
A.与处理冲突方法有关而与表的长度无关
B.与处理冲突方法无关而与表的长度有关
C.与处理冲突方法有关而与表的长度有关
D.与处理冲突方法无关而与表的长度无关
正确答案:————
14.[单选题]设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。
A.top=top+1;
B.top=top-1;
C.top-＞next=top;
D.top=top-＞next;
正确答案:————
15.[单选题]任何一个无向连通图的最小生成树（）。
A.只有一棵
B.有一棵或多棵
C.一定有多棵
D.可能不存在
正确答案:————
16.[单选题]设顺序表的长度为n，则顺序查找的平均比较次数为（）。
A.n
B.n/2
C.(n+1)/2
D.(n-1)/2
正确答案:————
17.[单选题]一组记录的关键码为（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
正确答案:————
18.[单选题]有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。
A.35/12
B.37/12
C.39/12
D.43/12
正确答案:————
19.[单选题]设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。
A.单向链表
B.单向循环链表
C.双向链表
D.双向循环链表
正确答案:————
20.[单选题]关键路径是事件结点网络中（）。
A.从源点到汇点的最长路径
B.从源点到汇点的最短路径
C.最长的回路
D.最短的回路
正确答案:————
21.[单选题]下面不正确的说法是（）。
A.在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小
B.AOE网工程工期为关键活动上的权之和
C.在关键路径上的活动都是关键活动，而关键活动也必在关键路径上
D.以上都不对
正确答案:————
22.[单选题]对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为（）。
A.k1
B.k2
C.k1-k2
D.k1+k2
正确答案:————
23.[单选题]一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（）。
A.16，25，35，48，23，40，79，82，36，72
B.16，25，35，48，79，82，23，36，40，72
C.16，25，48，35，79，82，23，36，40，72
D.16，25，35，48，79，23，36，40，72，82
正确答案:————
24.[单选题]具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。
A.5
B.6
C.7
D.8
正确答案:————
25.[单选题]采用线性探测法解决冲突问题，所产生的一系列后继散列地址（）。
A.必须大于等于原散列地址
B.必须小于等于原散列地址
C.可以大于或小于但不能等于原散列地址
D.地址大小没有具体限制
正确答案:————
26.[单选题]设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。
A.2i+1
B.2i
C.i/2
D.2i-1
正确答案:————
27.[单选题]二叉树是非线性数据结构，所以（）。
A.它不能用顺序存储结构存储
B.它不能用链式存储结构存储
C.顺序存储结构和链式存储结构都能存储
D.顺序存储结构和链式存储结构都不能使用
正确答案:————
28.[单选题]建立一个长度为n的有序单链表的时间复杂度为（）
A.O(n)
B.O(1)
C.O(n2 )
D.O(log2n)
正确答案:————
29.[单选题]队列是一种（）的线性表。
A.先进先出
B.先进后出
C.只能插入
D.只能删除
正确答案:————
30.[单选题]判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。
A.求关键路径的方法
B.求最短路径的Dijkstra方法
C.宽度优先遍历算法
D.深度优先遍历算法
正确答案:————
31.[单选题]设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
正确答案:————
32.[单选题]设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。
A.n-i
B.n+l -i
C.n-1-i
D.i
正确答案:————
33.[单选题]采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。
A.先序遍历
B.中序遍历
C.后序遍历
D.按层遍历
正确答案:————
34.[单选题]（）二叉排序树可以得到一个从小到大的有序序列。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
正确答案:————
35.[单选题]设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（）个。
A.4
B.5
C.6
D.7
正确答案:————
36.[单选题]用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：⑴ 25，84，21，47，15，27，68，35，20；⑵ 20，15，21，25，47，27，68，35，84；⑶ 15，20，21，25，35，27，47，68，84；⑷ 15，20，21，25，27，35，47，68，84。则所采用的排序方法是（）。
A.选择排序
B.希尔排序
C.归并排序
D.快速排序
正确答案:————
37.[单选题]下列程序段的时间复杂度为（）。i=0，s=0； while (s＜n) {s=s+i；i++；}
A.O(n1/2)
B.O(n1/3)
C.O(n)
D.O(n2 )
正确答案:————
38.[单选题]设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。
A.5，3，4，6，1，2
B.3，2，5，6，4，1
C.3，1，2，5，4，6
D.1，5，4，6，2，3
正确答案:————
39.[单选题]采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。
A.先序遍历
B.中序遍历
C.后序遍历
D.按层遍历
正确答案:————
40.[单选题]一个有n个顶点的无向图最多有（）条边。
A.n
B.n(n-1)
C.n(n-1)/2
D.2n
正确答案:————
奥鹏作业答案
页:
[1]