天大19春《数据结构》在线作业二（含答案）

奥鹏作业答案

19春[天津大学]《数据结构》在线作业二（100分）
【奥鹏】[天津大学]《数据结构》在线作业二
奥鹏作业答案
奥鹏天津大学作业

试卷总分100得分100
第1题对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为（）。
A、从第0个元素往后查找该数据元素
B、从第1个元素往后查找该数据元素
C、从第n个元素往开始前查找该数据元素
D、与查找顺序无关
正确答案
第2题数组的逻辑结构不同于下列（??）的逻辑结构。
A、线性表
B、栈
C、队列
D、树
正确答案
第3题设哈希表长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
正确答案
第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、2i1
D、2i1
正确答案
第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、2n1
D、2n+l
正确答案
第12题对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（）。
A、静态查找表
B、动态查找表
C、静态查找表与动态查找表
D、两种表都不适合
正确答案
第13题散列表的平均查找长度（）。
A、与处理冲突方法有关而与表的长度无关
B、与处理冲突方法无关而与表的长度有关
C、与处理冲突方法有关而与表的长度有关
D、与处理冲突方法无关而与表的长度无关
正确答案
第14题设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。
A、top=top+1
B、top=top1
C、topnext=top
D、top=topnext
正确答案
第15题任何一个无向连通图的最小生成树（）。
A、只有一棵
B、有一棵或多棵
C、一定有多棵
D、可能不存在
正确答案
第16题设顺序表的长度为n，则顺序查找的平均比较次数为（）。
A、n
B、n/2
C、(n+1)/2
D、(n1)/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、k1k2
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、2i1
正确答案
第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、N11
B、N21
C、N2+N3
D、N1+N3
正确答案
第32题设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。
A、ni
B、n+li
C、n1i
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(sn){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(n1)
C、n(n1)/2
D、2n
正确答案

奥鹏作业答案
奥鹏天津大学作业