19春[天津大学]《数据结构》在线作业二（100分）

admin

【奥鹏】[天津大学]《数据结构》在线作业二
试卷总分: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)=4;addr (38)=5;addr (61)=6;addr (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、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 (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(n-1)
C、n(n-1)/2
D、2n
正确资料: