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

admin

【奥鹏】[天津大学]《数据结构》在线作业二
试卷总分:100    得分:100
第1题,对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（）。
A、静态查找表
B、动态查找表
C、静态查找表与动态查找表
D、两种表都不适合
正确资料:


第2题,设有向无环图G中的有向边集合E={1，2，2，3，3，4，1，4}，则下列属于该有向图G的一种拓扑排序序列的是（  ）。
A、1，2，3，4
B、2，3，4，1
C、1，4，2，3
D、1，2，4，3
正确资料:


第3题,（  ）二叉排序树可以得到一个从小到大的有序序列。
A、先序遍历
B、中序遍历
C、后序遍历
D、层次遍历
正确资料:


第4题,二叉树是非线性数据结构，所以（）。
A、它不能用顺序存储结构存储
B、它不能用链式存储结构存储
C、顺序存储结构和链式存储结构都能存储
D、顺序存储结构和链式存储结构都不能使用
正确资料:


第5题,设完全无向图中有n个顶点，则该完全无向图中有（  ）条边。
A、n(n-1)/2
B、n(n-1)
C、n(n+1)/2
D、(n-1)/2
正确资料:


第6题,在二叉排序树中插入一个关键字值的平均时间复杂度为（  ）。
A、O(n)
B、O(1og2n)
C、O(nlog2n)
D、O(n2 )
正确资料:


第7题,对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为（）。
A、从第0个元素往后查找该数据元素
B、从第1个元素往后查找该数据元素
C、从第n个元素往开始前查找该数据元素
D、与查找顺序无关
正确资料:


第8题,设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（  ）。
A、129
B、219
C、189
D、229
正确资料:


第9题,采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。
A、O（n2）
B、O(nlog2n)
C、O(n)
D、O(log2n)
正确资料:


第10题,设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（  ）个元素。
A、n-i
B、n+l -i
C、n-1-i
D、i
正确资料:


第11题,排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。
A、希尔排序
B、归并排序
C、插入排序
D、选择排序
正确资料:


第12题,设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
正确资料:


第13题,利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（  ）。
A、O(n)
B、O(nlog2n)
C、O(n2 )
D、O(1og2n)
正确资料:


第14题,顺序查找法适合于存储结构为（）的线性表。
A、散列存储
B、顺序存储或链接存储
C、压缩存储
D、索引存储
正确资料:


第15题,设输入序列1、2、3、"、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（  ）。
A、n-i
B、n-1-i
C、n+l -i
D、不能确定
正确资料:


第16题,用某种排序方法对线性表（ 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、快速排序
正确资料:


第17题,采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）.
A、n
B、n/2
C、(n+1)/2
D、(n-1)/2
正确资料:


第18题,下列程序段的时间复杂度为（  ）。  for(i=0； im； i++) for(j=0； jt； 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)
正确资料:


第19题,对线性表进行二分查找时，要求线性表必须（）。
A、以顺序方式存储
B、以链接方式存储
C、以顺序方式存储，且结点按关键字有序排序
D、以链接方式存储，且结点按关键字有序排序
正确资料:


第20题,二叉排序树中左子树上所有结点的值均（  ）根结点的值。
A、
B、
C、=
D、!=
正确资料:


第21题,设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}， 则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（  ）。
A、aedfcb
B、acfebd
C、aebcfd
D、aedfbc
正确资料:


第22题,快速排序方法在（）情况下最不利于发挥其长处。
A、要排序的数据量太大
B、要排序的数据中含有多个相同值
C、要排序的数据已基本有序
D、要排序的数据个数为奇数
正确资料:


第23题,一个有n个顶点的无向图最多有（）条边。
A、n
B、n(n-1)
C、n(n-1)/2
D、2n
正确资料:


第24题,设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（  ）次比较。
A、1
B、2
C、3
D、4
正确资料:


第25题,设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（  ）次线性探测。
A、n2
B、n(n+1)
C、n(n+1)/2
D、n(n-1)/2
正确资料:


第26题,采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。
A、先序遍历
B、中序遍历
C、后序遍历
D、按层遍历
正确资料:


第27题,树最适合用来表示（）。
A、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据
正确资料:


第28题,树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论（）是正确的。
A、树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B、树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C、树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D、以上都不对
正确资料:


第29题,对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有邻接表中的接点总数是（）。
A、e/2
B、e
C、2e
D、n+e
正确资料:


第30题,设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（  ）。
A、p-right=s； s-left=p； p-right-left=s； s-right=p-right；
B、s-left=p；s-right=p-right；p-right=s； p-right-left=s；
C、p-right=s； p-right-left=s； s-left=p； s-right=p-right；
D、s-left=p；s-right=p-right；p-right-left=s； p-right=s；
正确资料:


第31题,判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。
A、求关键路径的方法
B、求最短路径的Dijkstra方法
C、宽度优先遍历算法
D、深度优先遍历算法
正确资料:


第32题,把一棵树转换为二叉树后，这棵二叉树的形态是（）。
A、唯一的
B、有多种
C、有多种，但根结点都没有左孩子
D、有多种，但根结点都没有右孩子
正确资料:


第33题,关键路径是事件结点网络中（）。
A、从源点到汇点的最长路径
B、从源点到汇点的最短路径
C、最长的回路
D、最短的回路
正确资料:


第34题,有8个结点的无向连通图最少有（）条边。
A、5
B、6
C、7
D、8
正确资料:


第35题,在一个图中，所有顶点的度数之和等于所有边数的（）倍。
A、1/2
B、1
C、2
D、4
正确资料:


第36题,采用线性探测法解决冲突问题，所产生的一系列后继散列地址（）。
A、必须大于等于原散列地址
B、必须小于等于原散列地址
C、可以大于或小于但不能等于原散列地址
D、地址大小没有具体限制
正确资料:


第37题,散列表的平均查找长度（）。
A、与处理冲突方法有关而与表的长度无关
B、与处理冲突方法无关而与表的长度有关
C、与处理冲突方法有关而与表的长度有关
D、与处理冲突方法无关而与表的长度无关
正确资料:


第38题,在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。
A、希尔排序
B、起泡排序
C、插入排序
D、选择排序
正确资料:


第39题,一个有n个顶点的无向连通图，它所包含的连通分量个数为（）。
A、0
B、1
C、n
D、n+1
正确资料:


第40题,设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（   ）。
A、F，H，C，D，P，A，M，Q，R，S，Y，X
B、P，A，C，S，Q，D，F，X，R，H，M，Y
C、A，D，C，R，F，Q，M，S，Y，P，H，X
D、H，C，Q，P，A，M，S，R，D，F，X，Y
正确资料: