西工大课程考试《数据结构》答案Word文件下载.docx

西工大课程考试《数据结构》答案Word文件下载.docx

《西工大课程考试《数据结构》答案Word文件下载.docx》由会员分享，可在线阅读，更多相关《西工大课程考试《数据结构》答案Word文件下载.docx（13页珍藏版）》请在冰点文库上搜索。

D.SHELL排序

4.下列陈述中正确的是（）。

A.二叉树是度为2的有序树

B.二叉树中结点只有一个孩子时无左右之分

C.二叉树中必有度为2的结点

D.二叉树中最多只有两棵子树，并且有左右之分

5.设有向图有n个顶点和e条边，进行拓扑排序时总的计算时间为（）。

A.O（loge）

B.O（en）

C.O（elogn）

D.O（n+e）

6.散列表的平均查找长度（）。

A.与处理冲突方法有关而与表的长度无关

B.与处理冲突方法无关而与表的长度有关

C.与处理冲突方法有关且与表的长度有关

D.与处理冲突方法无关且与表的长度无关

7.快速排序算法在最好情况下的时间复杂度为（）。

A.O（n）

B.O（nlog2n）

C.O（n2）

D.O（log2n）

A

8.已知广义表a=（（a,b,c）,（d,e,f））,从a中取出原子e的运算是（）。

A.tail（head（a））

B.b.head（tail（a））

C.head（tail（tail（head（a））））

D.head（tail（tail（a）））

9.关键路径是事件结点网络中（）。

A.最短的回路

B.最长的回路

C.从开始结点到完成结点的最长路径

D.从开始结点到完成结点的最短路径

B

10.一个无向连通图的生成树是含有该连通图的全部顶点的（）。

A.极小连通子图

B.极小子图

C.极大连通子图

D.极大子图

11.设有向图有n个顶点和e条边，进行拓扑排序时总的计算时间为（）。

D.O（ne）

12.下列说法中不正确的是（）。

A.图的遍历过程中每一顶点仅被访问一次

B.遍历图的基本方法有深度优先搜索和广度优先搜索两种

C.图的深度优先搜索的方法不适用于有向图

D.图的深度优先搜索是一个递归过程

13.常采用下面几种方式解决散列法中出现的冲突问题（）。

A.数字分析法、除余法、平方取中法

B.数字分析法、除余法、线性探测法

C.数字分析法、线性探测法、多重散列法

D.线性探测法、多重散列法、链地址法

14.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（）型调整以使其平衡。

A.LL

B.LR

C.RL

D.RR

15.用一维数组存放的一棵完全二叉树ABCDEFGHIJKL。

请写出后序遍历该二叉树的访问结点序列（）。

A.HIDJKEBLFGCA

B.ABCDEFGHIJKL

C.HDIBJEKALFCG

D.ABCDEGFHJIKL

16.散列表的平均查找长度（）。

17.关键路径是事件结点网络中（）。

18.数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用（）排序算法最节省时间。

B.希尔排序

D.直接选择排序

19.数据表A中有00个元素，如果仅要求求出其中最大的10个元素，则采用（）排序。

20.关键路径是事件结点网络中（）。

21.一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为（）。

A.n*n

B.n*（n+1）/2

C.（n+1）*（n+1）/2

D.（n-1）*n/2

22.数据结构中，从逻辑上可以把数据结构分成（）。

A.动态结构和静态结构

B.紧凑结构和非紧凑结构

C.线性结构和非先性结构

D.内部结构和外部结构

23.二叉树在线索化后，仍不能有效求解的问题是（）。

A.先序线索二叉树中求先序后继

B.中序线索二叉树中求中序后继

C.中序线索二叉树中求中序前趋

D.后序线索二叉树中求后序后继

24.对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（）。

25.快速排序算法在最好情况下的时间复杂度为（）。

26.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。

A.e

B.2e

C.n2-e

D.n2-2e

27.广义表运算式tail[（（a,b）,（c,d））]的结果为（）。

A.c,d

B.（c,d）

C.（（c,d））

D.d,c

28.若二叉树中度为2的结点有15个，度为1的结点有10个该树有（）个结点。

D.41

29.对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（）。

30.若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有（）个结点。

A.15

B.16

C.17

D.34

31.对于单链表形式的队列，队空的条件是（）。

A.F=R=null

B.F=R

C.F≠null且R=null

D.R-F=1

32.深度为6的二叉树至多有结点数为（）。

A.16

C.63

D.31

33.若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有（）个结点。

34.在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该（）。

A.只有左子树上的所有结点

B.只有左子树上的部分结点

C.只有右子树上的所有结点

D.只有右子树上的部分结点

35.对有序表18，20，25，34，48，62，74，85用二分查找法查找85，所需的比较次数为（）。

A.1次

B.2次

C.3次

D.4次

36.树型结构最适合用来描述（）。

A.有序的数据元素

B.无序的数据元素

C.数据元素之间的具有层次关系的数据

D.数据元素之间没有关系的数据

37.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序，A11为第一个元素，其存储地址为1，每个元素占1个地址空间，则A82的地址为（）。

A.13

C.18

D.0

38.常采用下面几种方式解决散列法中出现的冲突问题：

（）

39.有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主序，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。

B.33

D.40

40.计算机识别、存储和加工处理的对象被统称为（）。

A.数据

B.数据元素

C.数据结构

D.数据类型

41.线性表的顺序存储结构是一种（）存取结构。

A.随即存取

B.顺序存取

C.索引存取

D.散列存取

42.下述排序算法中，稳定的是（）。

A.直接选择排序

B.表插入排序

D.堆排序

43.广义表运算式tail[（（a,b）,（c,d））]的结果为（）。

C<

/p>

44.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O（log2n）的是（）。

C.直接选择排序

D.快速排序

45.对有序表18，20，25，34，48，62，74，85用二分查找法查找85，所需的比较次数为（）。

46.设有向图G中顶点数为n，图G最多有（）条边。

A.n

B.n-1

C.n*（n-1）/2

D.n*（n-1）

47.下面关于哈夫曼树的说法，不正确的是（）。

A.对应于一组权值构造出的哈夫曼树一般不是唯一的

B.哈夫曼树具有最小带权路径长度

C.哈夫曼树中没有度为1的结点

D.哈夫曼树中除了度为1的结点外，还有度为2的结点和叶结点

48.线索二叉树是一种（）结构。

A.逻辑

B.逻辑和存储

C.物理

D.线性

49.散列表的平均查找长度（）。

A.与处理冲突的方法有关而与表的长度无关

B.与处理冲突的方法无关而与表的长度有关

C.与处理冲突的方法有关且与表的长度有关

D.与处理冲突的方法无关且与表的长度无关