20.10月西工大《数据结构》机考作业答案

1、试卷总分:100 得分:98一、 单选题 (共 50 道试题,共 100 分)1.对有14个数据元素的有序表R14进行折半搜索，搜索到R3的关键码等于给定值，此时元素比较顺序依次为( )。A.R0，R1，R2，R3B.R0，R13，R2，R3C.R6，R2，R4，R3D.R6，R4，R2，R3正确答案:C2.若二叉树中度为2的结点有15个，度为1的结点有10个该树有 ( )个叶结点。A.25B.30C.31D.16正确答案:D3.下列排序算法中，( )算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。A.堆排序B.冒泡排C.快速排序D.SHELL排序正确答案:C4. 下列陈述中正确的

2、是（ ）。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分正确答案:D5.设有向图有n个顶点和e条边，进行拓扑排序时总的计算时间为（ ）。A.O(loge)B.O(en)C.O(elogn)D.O(n+e)正确答案:D6.散列表的平均查找长度( )。A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关且与表的长度有关D.与处理冲突方法无关且与表的长度无关正确答案:C7.快速排序算法在最好情况下的时间复杂度为( ) 。A.O(n)B.O(nlog2n)C.O(n

3、2)D.O(log2n)正确答案:A8.28已知广义表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)正确答案:D9. 关键路径是事件结点网络中（ ）。A.最短的回路B.最长的回路C.从开始结点到完成结点的最长路径D.从开始结点到完成结点的最短路径正确答案:B10.一个无向连通图的生成树是含有该连通图的全部顶点的（ ）。A.极小连通子图B.极小子图C.极大连通子图D.极大子图正确答案:A11. 设有向图有n个顶点和e条边，进行拓扑

4、排序时总的计算时间为（ ）。A.O(loge)B.O(en)C.O(elogn)D.O(n+e)正确答案:D12.下列说法中不正确的是（ ）。A.图的遍历过程中每一顶点仅被访问一次B.遍历图的基本方法有深度优先搜索和广度优先搜索两种C.图的深度优先搜索的方法不适用于有向图D.图的深度优先搜索是一个递归过程正确答案:C13.常采用下面几种方式解决散列法中出现的冲突问题（ ）。A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法正确答案:D14.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A

5、，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作( )型调整以使其平衡。A.LLB.LRC.RLD.RR正确答案:B15.用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列（ ）。A.H I D J K E B L F G C AB.A B C D E F G H I J K LC.H D I B J E K A L F C GD.A B C D E G F H J I K L正确答案:A16. 散列表的平均查找长度（ ）。A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关且与表的长度有

6、关D.与处理冲突方法无关且与表的长度无关正确答案:C17.关键路径是事件结点网络中（ ）。A.最短的回路B.最长的回路C.从开始结点到完成结点的最长路径D.从开始结点到完成结点的最短路径正确答案:C18.数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )排序算法最节省时间。A.堆排序B.希尔排序C.快速排序D.直接选择排序正确答案:A19. 数据表A中有00个元素，如果仅要求求出其中最大的10个元素，则采用（ ）排序A.堆排序B.希尔排序C.快速排序D.直接选择排序正确答案:A20.18关键路径是事件结点网络中（ ）。A.最短的回路B.最长的回路C.从开始结点到完成

7、结点的最长路径D.从开始结点到完成结点的最短路径正确答案:C21. 一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为（ ）。A.n*nB.n*(n+1)/2C.(n+1)*(n+1)/2D.(n-1）*n/2正确答案:B22. 数据结构中，从逻辑上可以把数据结构分成（ ）。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非先性结构D.内部结构和外部结构正确答案:C23. 二叉树在线索化后，仍不能有效求解的问题是（ ）。A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前趋D.后序线索二叉树中求后序后继正确答案:D24.对有14个数据元

8、素的有序表R14进行折半搜索，搜索到R3的关键码等于给定值，此时元素比较顺序依次为( )。A.R0，R1，R2，R3B.R0，R13，R2，R3C.R6，R2，R4，R3D.R6，R4，R2，R3正确答案:C25. 快速排序算法在最好情况下的时间复杂度为（ ）。A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n)正确答案:A26. 在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ）。A.eB.2eC.n2eD.n22e正确答案:D27. 广义表运算式tail(a,b),(c,d)的结果为（ ）。A.c,dB.(c,d)C.(c,d)D.d,c正确答案:C28.若二叉

9、树中度为2的结点有15个，度为1的结点有10个该树有( )个结点。A.25B.30C.31D.41正确答案:D29. 对有14个数据元素的有序表R14进行折半搜索，搜索到R3的关键码等于给定值，此时元素比较顺序依次为（ ）。A.R0，R1，R2，R3B.R0，R13，R2，R3C.R6，R2，R4，R3D.R6，R4，R2，R3正确答案:C30. 若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有（ ）个结点。A.15B.16C.17D.34正确答案:D31.对于单链表形式的队列，队空的条件是（ ）。A.FRnil   &

10、emsp;B.FR    C.Fnil且Rnil    D.RF1正确答案:B32. 深度为6的二叉树至多有结点数为（ ）。A.16B.30C.63D.31正确答案:D33.若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有( )个结点。A.15B.16C.17D.34正确答案:D34. 在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该（ ）。A.只有左子树上的所有结点B.只有左子树上的部分结点C.只有右子树上的所有结点D.只有右子树上

11、的部分结点正确答案:A35.对有序表(18，20，25，34，48，62，74，85)用二分查找法查找85，所需的比较次数为( )。A.1次B.2次C.3次D.4次正确答案:D36.树型结构最适合用来描述 ( )。A.有序的数据元素B.无序的数据元素C.数据元素之间的具有层次关系的数据D.数据元素之间没有关系的数据正确答案:C37. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序，A11为第一个元素， 其存储地址为1，每个元素占1个地址空间，则A82的地址为（ ）。 A.13B.30C.18D.0正确答案:B38. 常采用下面几种方式解决散列法中出现的冲突问题（ ）。A.数字分析法

12、、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法正确答案:D39.有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主序，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（ ）。A.13B.33C.18D.40正确答案:B40. 计算机识别、存储和加工处理的对象被统称为（ ）。A.数据B.数据元素C.数据结构D.数据类型正确答案:A41.线性表的顺序存储结构是一种（ ）存取结构。A.随即存取B.顺序存取C.索引存取D.散列存取正确答案:A42. 下述排序算法中，稳定的是（ ）。A.直接

13、选择排序B.表插入排序C.快速排序D.堆排序正确答案:B43.29广义表运算式tail(a,b),(c,d)的结果为（ ）A.c,dB.(c,d)C.(c,d)D.d,c正确答案:C44.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(log2n)的是( )。A.堆排序B.冒泡排C.直接选择排序D.快速排序正确答案:A45. 对有序表(18，20，25，34，48，62，74，85)用二分查找法查找85，所需的比较次数为（ ）。A.1次B.2次C.3次D.4次正确答案:D46.设有向图G中顶点数为n，图G最多有（ ）条边。A.nB. n-1 C.n*(n-1)/2D.n*(n-1)正确答案:D47. 下面关于哈夫曼树的说法，不正确的是（ ）。A.对应于一组权值构造出的哈夫曼树一般不是唯一的B.哈夫曼树具有最小带权路径长度C.哈夫曼树中没有度为1的结点D.哈夫曼树中除了度为1的结点外，还有度为2的结点和叶结点正确答案:D48. 线索二叉