奥鹏13春天津大学《数据结构》在线作业二

谋学网

一、单选题（共 20 道试题，共 100 分。）V 1.  采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）.
A. n
B. n/2
C. (n+1)/2
D. (n-1)/2
      满分：5  分
2.  在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
      满分：5  分
3.  采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
      满分：5  分
4.  在一个图中，所有顶点的度数之和等于所有边数的（）倍。
A. 1/2
B. 1
C. 2
D. 4
      满分：5  分
5.  对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有邻接表中的接点总数是（）。
A. e/2
B. e
C. 2e
D. n+e
      满分：5  分
6.  对线性表进行二分查找时，要求线性表必须（）。
A. 以顺序方式存储
B. 以链接方式存储
C. 以顺序方式存储，且结点按关键字有序排序
D. 以链接方式存储，且结点按关键字有序排序
      满分：5  分
7.  一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。
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
      满分：5  分
8.  解决散列法中出现的冲突问题常采用的方法是（）。
A. 数字分析法、除余法、平方取中法
B. 数字分析法、除余法、线性探测法
C. 数字分析法、线性探测法、多重散列法
D. 线性探测法、多重散列法、链地址法
      满分：5  分
9.  散列表的平均查找长度（）。
A. 与处理冲突方法有关而与表的长度无关
B. 与处理冲突方法无关而与表的长度有关
C. 与处理冲突方法有关而与表的长度有关
D. 与处理冲突方法无关而与表的长度无关
      满分：5  分
10.  设哈希表长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
      满分：5  分
11.  用某种排序方法对线性表（ 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. 快速排序
      满分：5  分
12.  用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是（）。
A. 逆拓朴有序的
B. 拓朴有序的
C. 无序的
D. 不确定的
      满分：5  分
13.  下述几种排序方法中，平均查找长度最小的是（）。
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
      满分：5  分
14.  对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。
A. n
B. (n-1)的平方
C. n-1
D. n的平方
      满分：5  分
15.  有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。
A. 35/12
B. 37/12
C. 39/12
D. 43/12
      满分：5  分
16.  具有4个顶点的无向完全图有（）条边。
A. 6
B. 12
C. 16
D. 20
      满分：5  分
17.  任何一个无向连通图的最小生成树（）。
A. 只有一棵
B. 有一棵或多棵
C. 一定有多棵
D. 可能不存在
      满分：5  分
18.  树最适合用来表示（）。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
      满分：5  分
19.  下述几种排序方法中，要求内存量最大的是（）。
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
      满分：5  分
20.  树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论（）是正确的。
A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D. 以上都不对
      满分：5  分