《数据结构》2.利用直接插入排序法的思想建立一个有序线...

17春天大《数据结构》在线作业二
一、单选题：
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[5][4]地址与A[0][0]的地址之差为(    )。          (满分: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