综合测评复习题数据结构导论Paper2

数据结构导论--综合测评 题目 一 二 三 四 五 六 七 分数 得分 一、单选题 （每题4分，共100分） 1． A．ABCDEFGH B．ABCDGFHE C．ADEHGCBF D．ADGEHFBC 2．顺序队列的入队操作应为（） A． B． C． D． 3．设F是一个森林，B是由F转换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。 A．n-1 B．n C．n+1 D．n+2 4． A．AVL树 B．BST树 C．判定树 D．堆 5．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是$n_1$，$n_2$，$n_3$，$n_4$，那么当把森林T转换成一棵二叉树后，其根结点的右子树上有（）个结点。 A．$n_1$-1 B．$n_1$ C．$n_1$+$n_2$+$n_3$ D．$n_2$+$n_3$+$n_4$ 6．将5个不同的数据进行排序，至多需要比较（）次。 A．8 B．9 C．10 D．25 7．设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。 A．5 B．6 C．7 D．8 8．当初始序列已按键值有序时，用直接插入算法进行排序，需要比较的次数为（） A．n-1 B．$log_2n$ C．$21og_2n$ D．$n^2$ 9．二维数组M[i，j]的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4，列下标j的范围从0到5。M按行存储时元素M[3，5]的起始地址与M按列存储时元素（）的起始地址相同。 A．M[2，4] B．M[3，4] C．M[3，5] D．M[4，4] 10．某二叉树结点的中序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则该二叉树结点的前序序列为（），则该二叉树对应的森林包括（）棵树。 A．EACBDGF，1 B．EACBDGF，2 C．ECBDAGF，1 D．ECBDAGF，2 11．具有10个叶结点的二叉树中有（）个度为2的结点。 A．8 B．9 C．10 D．11 12．一个栈的入栈序列是a,b,c,d,e，则栈的可能的输出序列是（） A．cdabe B．cabde C．dabec D．decba 13．向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为（） A． B． C． D． 14．若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用（）遍历方法最合适。 A．前序 B．中序 C．后序 D．按层次 15．设顺序表的长度为n，则其每个元素的平均查找长度是（） A．n B．(n-1)/2 C．n/2 D．(n+1)/2 16．排序中关键字比较次数与序列的原始状态无关的排序方法是（）排序法。 A．插入 B．希尔 C．冒泡 D．快速 17．对文件进行直接存取的根据是（） A．按逻辑记录号去存取某个记录 B．按逻辑记录的关键字去存取某个记录 C．按逻辑记录的结构去存取某个记录 D．按逻辑记录的具体内容去存取某个记录 18．设$n_0$为哈夫曼树的叶子结点数目，则该哈夫曼树共有（）个结点。 A．$n_0$+1 B．2$n_0$-1 C．2$n_0$ D．2$n_0$+1 19．下列选项中，（）为一棵AVL树。 A． B． C． D． 20．对于大文件的排序要研究在外设上的排序技术，即（） A．快速排序法 B．内排序法 C．外排序法 D．交叉排序法 21．循环队列的队空条件为（） A．(sq.rear+1)%maxsize＝＝(sq.front+1)%maxsize B．(sq.rear+1)%maxsize＝＝sq.front+1 C．(sq.rear+1)%maxsize＝＝sq.front D．sq.rear＝＝sq.front 22．二分查找法适用于存储结构为（）的，且按关键字排好序的线性表。 A．顺序存储 B．链接存储 C．顺序存储或链接存储 D．索引存储 23．对含有（）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 A．0 B．1 C．2 D．不存在这样的二叉树 24．设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少为（）个。 A．k+1 B．2k C．2k-1 D．2k+1 25．已知有向图G＝(V，E)，其中：V＝{$v_1$,$v_2$，$v_3$,$v_4$，$v_5$，$v_6$,$v_7$)E＝{<$v_1$,$v_2$>,<$v_1$,$v_3$>,<$v_1$,v>,<$v_2$,$v_5$>,<$v_3$,$v_7$>,<$v_3$,$v_6$>,<$v_4$,$v_6$>,<$v_5$，$v_7$>，<$v_6$，$v_7$>)G的拓扑序列是（） A．$v_1$，$v_3$，$v_4$，$v_6$，$v_2$，$v_5$，$v_7$ B．$v_1$，$v_3$，$v_5$，$v_6$，$v_4$，$v_2$，$v_7$ C．$v_1$，$v_3$，$v_4$，$v_5$，$v_2$，$v_6$，$v_7$ D．$v_1$，$v_2$，$v_5$，$v_3$，$v_6$，$v_4$，$v_7$ 试卷答案 一、单选题 1． A．ABCDEFGH B．ABCDGFHE C．ADEHGCBF D．ADGEHFBC 答案： b 答案要点： 2．顺序队列的入队操作应为（） A． B． C． D． 答案： a 答案要点： 3．设F是一个森林，B是由F转换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。 A．n-1 B．n C．n+1 D．n+2 答案： c 答案要点： 本题主要考查的知识点为森林与二叉树的转换。根据森林与二叉树的转换规则，森林中的每个非终端结点必定在二叉树中有一个左分支，其左分支必定有且仅有最右边的叶子结点的右指针域为空。如果森林中有n个域为空的。因而总共的右指针域为空的结点有n+l个。正确答案为C。 4． A．AVL树 B．BST树 C．判定树 D．堆 答案： b 答案要点： 本题主要考查的知识点为二叉排序树。从结点平衡因子绝对值是否小于1，就非常容易排除该树不是AVL树。从二叉树中结点值的排列也可以排除它既不是大根堆，也不是小根堆。判定树一般是从小到大(或从大到小)有顺序规律的分段构造二叉树，而图4-7中的二叉树显然不符合这个规律。而它正好符合二叉排序树的规律，因此它是一棵二叉排序树。正确答案为B。 5．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是$n_1$，$n_2$，$n_3$，$n_4$，那么当把森林T转换成一棵二叉树后，其根结点的右子树上有（）个结点。 A．$n_1$-1 B．$n_1$ C．$n_1$+$n_2$+$n_3$ D．$n_2$+$n_3$+$n_4$ 答案： d 答案要点： 6．将5个不同的数据进行排序，至多需要比较（）次。 A．8 B．9 C．10 D．25 答案： c 答案要点： 本题主要考查的知识点为数据进行排序时的比较次数。从算法的时间复杂度考虑，比较次数最多的是简单选择排序，对于具有n个关键字的有序序列，其关键字总的比较次数是n(n-1)2/次，因此，将5个不同数据进行排序，其关键字的比较次数至多为10次，即C为正确答案。 7．设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。 A．5 B．6 C．7 D．8 答案： a 答案要点： 8．当初始序列已按键值有序时，用直接插入算法进行排序，需要比较的次数为（） A．n-1 B．$log_2n$ C．$21og_2n$ D．$n^2$ 答案： a 答案要点： 9．二维数组M[i，j]的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4，列下标j的范围从0到5。M按行存储时元素M[3，5]的起始地址与M按列存储时元素（）的起始地址相同。 A．M[2，4] B．M[3，4] C．M[3，5] D．M[4，4] 答案： b 答案要点： 10．某二叉树结点的中序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则该二叉树结点的前序序列为（），则该二叉树对应的森林包括（）棵树。 A．EACBDGF，1 B．EACBDGF，2 C．ECBDAGF，1 D．ECBDAGF，2 答案： b 答案要点： 11．具有10个叶结点的二叉树中有（）个度为2的结点。 A．8 B．9 C．10 D．11 答案： b 答案要点： 本题主要考查的知识点为二叉树的性质。由二叉树的性质3可知，其度为2的结点数为：$n_2$＝$n_0$-1＝10-1＝9。 12．一个栈的入栈序列是a,b,c,d,e，则栈的可能的输出序列是（） A．cdabe B．cabde C．dabec D．decba 答案： d 答案要点： 本题主要考查的知识点为栈的概念。栈的数据存取原则是后进先出。下面对于每个选项作出其存取过程的分析。A错误。由于c排在输出序列的最前面，它是最先出栈的元素，由入栈序列的顺序可知，a，b已入栈，且在栈中尚未出栈。紧接着，d完成入栈、出栈。而此时可能是e入栈、出栈，也可能是原来在栈顶的b出栈，但绝不可能是a出栈。也就是说输出序列的前3个字符可能是cde或cdb，但绝不能是cda。B错误。同A一样，c排在输出序列的最前面，它是最先出栈的元素，由入栈序列的顺序可知，a，b已入栈，紧接着，可能是d，e中的某个元素入栈、出栈，也可能是原来栈的元素b出栈，因此，输出序列的前两个元素可能是cb，cd，ce，绝不可能是ca。C错误。同理，可知输出序列的第2个元素不可能是a。D正确。其数据操作过程是：a，b，c，d按顺序入栈，然后栈顶的d元素出栈，元素e入栈、出栈，栈顶c出栈，栈顶b出栈，栈顶a出栈：输出序列为decba。 13．向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为（） A． B． C． D． 答案： c 答案要点： 14．若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用（）遍历方法最合适。 A．前序 B．中序 C．后序 D．按层次 答案： a 答案要点： 本题主要考查的知识点为二叉树的遍历。其交换左右子树的过程可用递归方法完成，第1步将根结点的左右子树交换，第2步在左子树中递归调用交换函数，第3步在右子树中递归调用交换函数。因此，采用前序遍历的方法最合适。正确答案为A。 15．设顺序表的长度为n，则其每个元素的平均查找长度是（） A．n B．(n-1)/2 C．n/2 D．(n+1)/2 答案： d 答案要点： 16．排序中关键字比较次数与序列的原始状态无关的排序方法是（）排序法。 A．插入 B．希尔 C．冒泡 D．快速 答案： b 答案要点： 本题主要考查的知识点为希尔排序法。插入排序在关键字初始状态成正序的情况下，其总的比较次数为n-1，而在无序的情况下，其总的比较次数为n(n-1)/2次。冒泡排序情况与插入排序是一样的。而快速排序在关键字有序或基本有序的情况下，比较次数达到最大值n(n-1)/2，而无序的情况下，比较次数少于该值。故正确答案为B。 17．对文件进行直接存取的根据是（） A．按逻辑记录号去存取某个记录 B．按逻辑记录的关键字去存取某个记录 C．按逻辑记录的结构去存取某个记录 D．按逻辑记录的具体内容去存取某个记录 答案： b 答案要点： 18．设$n_0$为哈夫曼树的叶子结点数目，则该哈夫曼树共有（）个结点。 A．$n_0$+1 B．2$n_0$-1 C．2$n_0$ D．2$n_0$+1 答案： b 答案要点： 本题主要考查的知识点为哈夫曼树。哈夫曼树虽然带有权值，但其构形仍然是一棵普通的二叉树，二叉树的性质仍然适用于它。不过哈夫曼树中没有单分支结点，它只有双分支结点和叶结点，因此，由二叉树的性质3可得出一个推论：n＝2$n_0$-1。其中，n表示哈夫曼树的结点总数，$n_0$表示哈夫曼树中的叶结点数。因此正确答案为B。 19．下列选项中，（）为一棵AVL树。 A． B． C． D． 答案： d 答案要点： 本题主要考查的知识点为AVL树。判断AVL树的标准是看二叉排序树中所有结点的平衡因子的绝对值是否都小于等于1，若小于等于1，则为AVL树，否则就不是AVL树。依据上述方法，可知正确答案是D。 20．对于大文件的排序要研究在外设上的排序技术，即（） A．快速排序法 B．内排序法 C．外排序法 D．交叉排序法 答案： c 答案要点： 21．循环队列的队空条件为（） A．(sq.rear+1)%maxsize＝＝(sq.front+1)%maxsize B．(sq.rear+1)%maxsize＝＝sq.front+1 C．(sq.rear+1)%maxsize＝＝sq.front D．sq.rear＝＝sq.front 答案： d 答案要点： 22．二分查找法适用于存储结构为（）的，且按关键字排好序的线性表。 A．顺序存储 B．链接存储 C．顺序存储或链接存储 D．索引存储 答案： a 答案要点： 23．对含有（）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 A．0 B．1 C．2 D．不存在这样的二叉树 答案： b 答案要点： 24．设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少为（）个。 A．k+1 B．2k C．2k-1 D．2k+1 答案： c 答案要点： 25．已知有向图G＝(V，E)，其中：V＝{$v_1$,$v_2$，$v_3$,$v_4$，$v_5$，$v_6$,$v_7$)E＝{<$v_1$,$v_2$>,<$v_1$,$v_3$>,<$v_1$,v>,<$v_2$,$v_5$>,<$v_3$,$v_7$>,<$v_3$,$v_6$>,<$v_4$,$v_6$>,<$v_5$，$v_7$>，<$v_6$，$v_7$>)G的拓扑序列是（） A．$v_1$，$v_3$，$v_4$，$v_6$，$v_2$，$v_5$，$v_7$ B．$v_1$，$v_3$，$v_5$，$v_6$，$v_4$，$v_2$，$v_7$ C．$v_1$，$v_3$，$v_4$，$v_5$，$v_2$，$v_6$，$v_7$ D．$v_1$，$v_2$，$v_5$，$v_3$，$v_6$，$v_4$，$v_7$ 答案： a 答案要点：