黄山学院软件工程专业大二2018-2019学年数据结构试卷含答案

1、黄山学院软件工程专业大二2018-2019学年数据结构试卷含答案1. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 单选题A.数据元素具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致(正确答案)C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等2. 对顺序存储的线性表，设其长度为n，且在任何位置上插入或删除操作都是等概率的。则插入一个元素时平均要移动表中的（）个元素。 单选题A.n/2(正确答案)B.(n+1)/2C.(n-1)/2D.n3. 数据的基本单位是（）。 单选题A.数据元素(正确答案)B.数据结构C.数据项D.数据对

2、象4. 算法在发生非法操作时可以做出处理的特性称为（）。 单选题A.健壮性(正确答案)B.确定性C.可行性D.正确性5. 在一个长度为n的顺序表中向第i个元素（0in）位置插入一个新元素时，需要从后向前依次后移（）个元素。 单选题A.n-iB.n-i+1(正确答案)C.n-i-1D.i6. 栈和队列的共同之处在于它们具有相同的（）。 单选题A.逻辑特性(正确答案)B.物理特性C.运算方法D.元素类型7. 某队列初始为空，若它的输入序列为a，b，c，d，它的输出序列应为（）。 单选题A.a，b，c，d(正确答案)B.d，c，b，a C.a，c，b，dD.d，a，c，b 8. 下列关于链栈的叙述中

3、正确的是（）。 单选题A.链栈和顺序栈相比，缺点是不能随机访问栈中的元素B.链栈在进栈操作时一般不需要考虑上溢出(正确答案)C.链栈在出栈操作时一般不需要考虑下溢出D.以上都不对9. 设串s1abcdefg，s2pqrst，函数CON(X，Y)返回X和Y的连接串，SUB(S，I，J)返回串S的从序号I的字符开始的J个字符组成的子串，LEN(S)返回串S的长度，则CON(SUB(s1,2，LEN(s),SUB(s1,LEN(s,）的结果串是( )。 单选题A.bcdef B.bcdefgC.bcpqrstD.bcdefef(正确答案)10. 深度为6的二叉树最多有（）个结点。 单选题A.64B.

4、63(正确答案)C.32D.3111. 设有5个元素的进栈序列为a、b、c、d、e，1，其输出序列是c、e、d、b、a，则该栈的容量至少是（）。 单选题A. 1B. 2C. 3D. 4(正确答案)12. 当4个元素的进栈序列给定以后，由这4个元素组成的可能的出栈序列应该有（）。 单选题A.24种B.17种C.16种D.14种(正确答案)13. 以下说法错误的是（）。 单选题A.二叉树可以是空集B.二叉树的任一结点都有两棵子树(正确答案)C.二叉树与树具有相同的树形结构D.二叉树中任一结点的两棵子树有次序之分14. 设二叉树有n个结点，则其深度为（）。 单选题A.n-1B.nC.1D.无法确定(

5、正确答案)15. 设深度为k的二叉树上只有度为0和度为0的节点，则这类二叉树上所含结点总数最少（）个 单选题A.k+1B.2kC.2k-1(正确答案)D.2k+116. 某二叉树的先序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是( )。 单选题A.bdgcefha B.gdbecfhaC. bdgechfa D. gdbehfca(正确答案)17. 对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（）。 单选题A. n+1B. nC. n-1D. n(n-1)/2(正确答案)18. 若一组记录的排序码为（46, 79,

6、 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为( )。 单选题A. 79, 46, 56, 38, 40, 84B. 84, 79, 56, 38, 40, 46 (正确答案)C. 84, 79, 56, 46, 40, 38 D. 84, 56, 79, 40, 46, 3819. 堆的形状是一棵（）。 单选题A.二叉排序树B.满二叉树C.完全二叉树(正确答案)D.平衡二叉树20. 下述几种排序方法中，平均查找长度（ASL）最小的是（）。 单选题A.插入排序B.快速排序(正确答案)C.归并排序D.选择排序21. 已知某二叉树的后续遍历序列是dabec，中序遍历序列是dea

7、bc，它的先序遍历序列是( )。 单选题A.acbed B.deabc C.decab D.cedba(正确答案)22. 将5个不同的数据进行排序，至多需要比较（）次。 单选题A. 8B. 9C. 10(正确答案)D. 2523. 若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。 单选题A.38, 40, 46, 56, 79, 84 B.40, 38, 46 , 79, 56, 84 C.40, 38，46, 56, 79, 84(正确答案)D.40, 38, 46, 84, 56, 7924. 下列关

8、键字序列中，（）是堆。 单选题A. 16,72,31,23,94,53B. 94,23, 31, 72, 16, 53C. 16, 53, 23,94,31, 72D. 16, 23, 53,31, 94, 72(正确答案)25. 具有32个结点的完全二叉树的深度为（）。 单选题A. 5B.6(正确答案)C.7D.826. 对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是( )排序。 单选题A.选择B.快速C.希尔 (正确答案)D.冒泡27. 下列陈述正确的是（）。 单选题A.二叉树是度为2的有序树B.二叉树中最

9、多只有二棵树,且有左右子树之分(正确答案)C.二叉树必有度为2的结点D. 二叉树中结点只有一个孩子时无左右之分28. 由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。 单选题A.23B.37C.46D.44(正确答案)29. 任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序（）。 单选题A.不发生变化(正确答案)B.发生变化C.不能确定D.以上都不对30. 设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。(注意C和D中h为指数) 单选题A.2h-1(正确答案)B.2(h-1)C.2*h-1D.2*h31. 在顺

10、序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找关键码12需做（）次关键码比较。 单选题A.2B.3C.4(正确答案)D.532. 树最适合用来表示（）。 单选题A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据(正确答案)D.元素之间无联系的数据33. 某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是（）的二叉树。 单选题A.空或只有一个结点B.高度等于其结点数(正确答案)C.任一结点无左孩子D.任一结点无右孩子34. 关于二叉树的三种遍历，下列说法正确的是（）。 单选题A.任意两种遍历序列都不可以唯一决定该二叉树B.任意两种遍历序列都可

11、以唯一决定该二叉树C.先序遍历序列和后序遍历序列可以唯一决定该二叉树D.先序遍历序列和中序遍历序列可以唯一决定该二叉树(正确答案)35. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（）。 单选题A. a是b祖先C. a在b左方(正确答案)D. a在b右方36. 设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是（）。 单选题A.6B.5C.4(正确答案)D.337. 有m个叶子结点的Huffman树所具有的结点总数为（）。 单选题A.m+1B.2m-1(正确答案)C.2mD.2m+138. 设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的

12、元素,最好采用（）排序法。 单选题A.冒泡排序B.快速排序C.堆排序(正确答案)D.插入排序39. 设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成二叉树后，根结点的左子树上有( )个结点。 单选题A.n1-1(正确答案)B.n1C.n1+n2+n3D.n2+n3+n440. 若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（）。 单选题A.n/2B.n(正确答案)C.(n+1)/2D.n+141. 下列排序算法的时间复杂度最小的是（）。 单选题A.冒泡排序B.希尔排序C.简单选择排序D.归并排序(正确答案)42. 有一个按元素值排好序的顺序表（长度大

13、于，分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找不成功的情况下，s和b的关系是( )。 单选题A.s=bB.s>b(正确答案)C.sD.不一定43. 3个结点可构成（）个不同形态的二叉树。 单选题A. 2B. 3C. 4D. 5(正确答案)44. 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。 判断题对(正确答案)错45. 在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。 判断题对错(正确答案)46. 没有元素的栈称为空栈，空栈用不着栈顶指针。 判断题对错(正确答案)47. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。 判断

14、题对错(正确答案)48. 直接选择排序是一种稳定的排序方法。 判断题对错(正确答案)49. 在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0。 判断题对(正确答案)错50. 任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。 判断题对(正确答案)错51. 若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。 判断题对错(正确答案)52. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。 判断题对(正确答案)错53. 折半查找所对应的判定树，既是一棵二叉查找树，又是一棵理想平衡二叉树。 判断题对(正确答案)错54. 链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。 判断题对(正确答案)错55. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相?同的结果。 判断题对错(正确答案)56. 完全二叉树的某结点若无左孩