天津大学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
    正确答案:————
奥鹏作业答案