天大17春《数据结构》在线作业二答案资料
《数据结构》在线作业二答案需求请联系QQ515224986
一、单选题：
1.设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为( )。 (满分:2.5)
A. 129
B. 219
C. 189
D. 229
2.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为( )。 (满分:2.5)
A. O(n)
B. O(nlog2n)
C. O(n2 )
D. O(1og2n)
3.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为( )。 (满分:2.5)
A. 6
B. 11
C. 5
D. 6.5
4.设顺序表的长度为n，则顺序查找的平均比较次数为( )。 (满分:2.5)
A. n
B. n/2
C.(n+1)/2
D.(n-1)/2
5.对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为( )。 (满分:2.5)
A. 从第0个元素往后查找该数据元素
B. 从第1个元素往后查找该数据元素
C. 从第n个元素往开始前查找该数据元素
D. 与查找顺序无关
6.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。 (满分:2.5)
A. 希尔排序
B. 起泡排序
C. 插入排序
D. 选择排序
7.有8个结点的无向连通图最少有( )条边。 (满分:2.5)
A. 5
B. 6
C. 7
D. 8
8.一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。 (满分:2.5)
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
9.关键路径是事件结点网络中( )。 (满分:2.5)
A. 从源点到汇点的最长路径
B. 从源点到汇点的最短路径
C. 最长的回路
D. 最短的回路
10.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。 (满分:2.5)
A. n
B. n+1
C. n-1
D. n/2
11.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是( )。 (满分:2.5)
A. head==0
B. head->next==0
C. head->next==head
D. head!=0
12.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为( )。 (满分:2.5)
A. 希尔排序
B. 归并排序
C. 插入排序
D. 选择排序
13.组成数据的基本单位是( )。 (满分:2.5)
A. 数据项
B. 数据类型
C. 数据元素
D. 数据变量
14.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的( )。 (满分:2.5)
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
15.下述几种排序方法中，平均查找长度最小的是( )。 (满分:2.5)
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
16.设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A地址与A的地址之差为( )。 (满分:2.5)
A. 10
B. 19
C. 28
D. 55
17.有8个结点的无向图最多有( )条边。 (满分:2.5)
A. 14
B. 28
C. 56
D. 112
18.采用线性探测法解决冲突问题，所产生的一系列后继散列地址( )。 (满分:2.5)
A. 必须大于等于原散列地址
B. 必须小于等于原散列地址
C. 可以大于或小于但不能等于原散列地址
D. 地址大小没有具体限制
19.用某种排序方法对线性表（ 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。则所采用的排序方法是( )。 (满分:2.5)
A. 选择排序
B. 希尔排序
C. 归并排序
D. 快速排序
20.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是( )。 (满分:2.5)
A. 逆拓朴有序的
B. 拓朴有序的
C. 无序的
D. 不确定的
21.设一组初始记录关键字的长度为8，则最多经过( )趟插入排序可以得到有序序列。 (满分:2.5)
A. 6
B. 7
C. 8
D. 9
22.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为( )。 (满分:2.5)
A. 79，46，56，38，40，80
B. 38，46,56，79，40，84，
C. 84，79，56，46，40，38
D. 84，56，79，40，46，38
23.采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。 (满分:2.5)
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
24.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )。 (满分:2.5)
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
25.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是( )。 (满分:2.5)
A. n
B.(n-1)的平方
C. n-1
D. n的平方
26.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论( )是正确的。 (满分:2.5)
A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D. 以上都不对
27.在待排序的元素序列基本有序的前提下，效率最高的排序方法是( )。 (满分:2.5)
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
28.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为( )。 (满分:2.5)
A. 8
B. 7
C. 6
D. 5
29.( )二叉排序树可以得到一个从小到大的有序序列。 (满分:2.5)
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
30.在一个图中，所有顶点的度数之和等于所有边数的( )倍。 (满分:2.5)
A. 1/2
B. 1
C. 2
D. 4
31.建立一个长度为n的有序单链表的时间复杂度为( ) (满分:2.5)
A. O(n)
B. O(1)
C. O(n2 )
D. O(log2n)
32.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有邻接表中的接点总数是( )。 (满分:2.5)
A. e/2
B. e
C. 2e
D. n+e
33.解决散列法中出现的冲突问题常采用的方法是( )。 (满分:2.5)
A. 数字分析法、除余法、平方取中法
B. 数字分析法、除余法、线性探测法
C. 数字分析法、线性探测法、多重散列法
D. 线性探测法、多重散列法、链地址法
34.堆的形状是一棵( )。 (满分:2.5)
A. 二叉排序树
B. 满二叉树
C. 完全二叉树
D. 平衡二叉树
35.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做( )次线性探测。 (满分:2.5)
A. n2
B. n(n+1)
C. n(n+1)/2
D. n(n-1)/2
36.设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是( )。 (满分:2.5)
A. 40，42，60，55，80，85
B. 42，45，55，60，85，80
C. 42，40，55，60，80，85
D. 42，40，60，85，55，80
37.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素。 (满分:2.5)
A. n-i
B. n+l -i
C. n-1-i
D. i
38.把一棵树转换为二叉树后，这棵二叉树的形态是( )。 (满分:2.5)
A. 唯一的
B. 有多种
C. 有多种，但根结点都没有左孩子
D. 有多种，但根结点都没有右孩子
39.队列是一种( )的线性表。 (满分:2.5)
A. 先进先出
B. 先进后出
C. 只能插入
D. 只能删除
40.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( ). (满分:2.5)
A. n
B. n/2
C.(n+1)/2
D.(n-1)/2
更多免费学习资料请登录www.openhelp100.com
页:
[1]