数据结构自测题1一、单项选择题1.线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ D ）。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续不连续都可以2.在单链表中，增加头结点的目的是为了（ C ）A．使单链表至少有一个结点B．表示表结点中首结点的位置C．方便运算的实现D．说明单链表是线性表的链式存储实现3.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应是（ B ）A．2 B．3 C．4 D．54.树结构中，前驱结点与后继结点之间存在（ B ）关系。
A．一对一B．一对多C．多对一D．多对多5.堆栈的特性描述是（ B ）。
A．FIFO B．FILO C．FIFO和FILO D．FIFO或FILO6.队列的特性描述是（ A ）。
A．FIFO B．FILO C．FIFO和FILO D．FIFO或FILO7.下列数据结构中，是非线性结构的是（ A ）A．树B．堆栈C．队列D．循环队列8.设某个初始为空的容纳int型数据的堆栈进行了如下操作（每一步均未发生溢出）：push(1)、push(3)、pop()、push(6)、push(1)、pop()、push(3)、push(8) 后，该堆栈中从栈顶到栈底的元素依次为（ D ）A．8 1 8 3 B．1 3 1 8 C．1 6 3 8 D．8 3 6 1二、判断题1.二叉树可以为空树。
（√）2.顺序表和链表都是线性表。
（√）3.线性表的长度是线性表占用的存储空间的大小。
（√）4.队列只能采用链式存储方式。
（×）5.由二叉树的先序序列和中序序列能唯一确定一棵二叉树。
（√）6.存在有偶数个结点的满二叉树。
（×）三、填空题1.数据结构是数据在计算机内的组成形式和相互关系。
2.二叉树的三种遍历方式分别为中序遍历、先序遍历和后序遍历。
3.深度为K的满二叉树共有2k－1 个结点。
4.N个顶点的无向图是完全图的条件是其边数为n ( n－1 ) / 2 。
四、名词解释1.ADT ADT是抽象数据类型的简称，指一个数学模型以及定义在该模型上的一组操作。
2.栈栈是限定仅在表尾进行插入或删除操作的线性表，具有先进后出（FILO）的特性。
3.队列队列是只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表，具有先进先出（FIFO）的特性。
五.简答题1.分别写出下图所示二叉树的先序遍历、中序遍历和后序遍历序列中序遍历： F G C E H B D J I A L N P O Q M K 先序遍历： A B C F G E H D I J K L M N O P Q 后序遍历： G F H E C J I D B P Q O N M L K A 2.用邻接矩阵表示下图所示的拓扑（节点已标号）。
数据结构自测题2一.单项选择题1.设某个初始为空的容纳int 型数据的非循环队列进行了如下操作（每一步均未发生溢出）：inqueue(1)、inqueue (3)、dequeue()、inqueue (6)、inqueue (1)、dequeue()、inqueue (3)、inqueue (8) 后，该队列中从队尾到队首的元素依次为（ C ）A ．1 6 3 8B ．6 1 3 8C ．8 3 1 6D ．8 3 6 12.最多3个结点的二叉树共有（A ）种不同的形态（不区分结点）。
A ．5 B ．4 C ．3 D ．23.串的长度是（ D ） A ．串中不同字符的数目AB C D E F GHIJ K LMNO PQ1 0 0 1 1 0 1 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0B．串中不同字母的数目C．串中所含单词的数目D．串中所含字符的数目4.树的度规定为（D）A结点度之和B结点度的平均值C结点度的最小值D．结点度的最大值5.线性表的顺序存储结构是一种（A）存取的存储结构。
A．顺序B．随机C．索引D．散列6.在单向链表的第i个结点前插入新结点时，需预先保留的结点指针是（A ）D．无需保留A．指向i结点的指针B．指向i结点的前趋结点的指针C．指向i结点的后继结点的指针设7.一个栈的进栈序列是ABCD，在进栈过程中允许出栈，且每个元素进栈出栈均各一次，则不可能得到的出栈序列是（ D ）。
A．ABDC B．DCBA C．CDBA D．CDAB8.下列说法正确的是（B ）。
A．冒泡排序算法不是稳定的B．快速排序是对冒泡排序的一种改进C．外部排序指对数据元素序列的整个排序过程都在计算机内存中进行的排序D．衡量内部排序算法和外部排序算法效率的方法是相同的二.判断题1.树是无圈的图。
（√）2.无向图中所有顶点的度数之和等于边数的两倍。
（√）3.在一棵二叉树中，第5层上的结点数最多为10个。
（×）4.栈允许在一端进行插入在另一端进行删除。
（×）5.冒泡排序是一种稳定的排序算法。
（√）三.填空题1.图是顶点和边的集合。
3.链式存储结构中的结点包括数据域和指针域。
2.构造Hash表中，处理冲突的办法有再哈希法、开放定址法、链地址法、以及建立一个公共溢出区等方法。
四.名词解释1.串串又成为字符串，是由零个和多个字符组成的有限序列。
2.排序排序时将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。
五、简答题1.堆栈和队列都是特殊线性表，其特殊性是什么。
堆栈是只能从一边输入和输出数据的线性表，具有先进后出（FILO）的特性；队列是只能从一边输入，而从另一边输出的线性表，具有先进先出（FIFO）的特性。
2.简述与开放定址法相比，链地址法处理冲突有哪些优点。
与开放定址法相比，链地址法有如下几个优点：(1) 链地址法处理冲突简单，且无堆积现象。
(2) 由于链地址法各链表上结点空间是动态申请的，故它更适合于造表前无法确定表长的情况。
(3)开放定址法需装填因子a较小，链地址法中可取a>=1，故当结点规模较大时，链地址法比开放定址法更节省空间。
(4) 链地址法构造的散列表，删除结点的操作易于实现。
六、综合题1.（10分）已知某二叉树的前序序列为EBADCFHGI，中序序列为ABCDEFGHI，请给出二叉树的后序序列，并画出这棵树的拓扑。
后序序列为ACDBGIHFEEBA DCFH G2.（15分）已知一个无向图的顶点集为{V0,V1,…V7}，其邻接矩阵如下所示：V0 0 1 0 1 1 0 0 0V1 1 0 1 0 1 0 0 0V2 0 1 00 0 1 0 0V3 1 0 0 00 0 1 0V4 1 1 0 0 00 1 0V5 0 0 1 0 0 00 0V6 0 0 0 1 1 0 0 1V7 0 0 0 0 0 0 1 0(2)画出该图的图形(1)给出从V0出发的深度优先、广度优先遍历序列深度优先序列 V0,V1,V2,V5,V4,V6,V3,V7 广度优先序列 V0 V1 V3 V4 V2 V6 V5 V7数据结构自测题3一.单项选择题1.对二叉排序树，使用（ B ）的遍历方式，可以获得对结点序列关键字的排序。
A．先序遍历B．中序遍历C．后序遍历D．层次遍历2.用数组表示线性表的优点是（ C ）。
A．便于插入和删除操作B．可以动态地分配存储空间C．便于随机存取D．不需要占用一片相邻的存储空间3.一棵二叉树的先序遍历次序为ABDGECFH ，中序遍历次序为DGBEAFHC ，则其后序遍历次序为（ C ）。
A．ACFHBEDG B．ABCDGHEF C．GDEBHFCA D．BEFCHAGD4.从未排序序列中选出最小的元素，并将其依次放入到已排序序列的一端的排序算法称为（ C ）。
A．插入排序B．交换排序C．选择排序D．快速排序5.下列有关树的概念错误的是（ C ）。
A．一棵树中只有一个无前驱的结点B．树至少有一个结点C．一棵树的度为树中各个结点的度数之和D．树是一种非线性结构6.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ B ）。
A．都不相同B完全相同C先序和中序相同而与后序不同 D中序和后序相同，而与先序不同二.判断题1.折半查找适合于顺序存储的有序表。
（√）2.堆栈和队列是两种重要的非线性结构。
（×）3.满二叉树一定是完全二叉树。
（√）4.栈具先进先出特征。
（×）5.单链表从任何一个结点出发，都能访问到所有结点。
（×）6.一般树和二叉树的结点数目都可以为0。
（×）三.填空题1.在树结构里，有且仅有一个结点没有前驱，称为根。
非根结点有且仅有一个直接前驱，且存在一条从根到该结点的唯一路径。
2..一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个对称矩阵。
3.四种基本的存储映象方法是顺序方法、链接方法、索引方法、散列方法。
四,名词解释1.内部排序内部排序指对数据元素序列的整个排序过程都是在计算机内存中进行的排序。
2.外部排序外部排序是指待排序的数据元素太多，不能同时存放在内存中，所以排序操作不仅要使用内存，而且还要使用外部存储器存储数据的排序。
五.综合题1.（10分）对于线性表(18，25，63，50，41，32，90，66)进行散列存储时，若选用H(K)＝K％11作为散列函数，则分别计算：散列地址为0的元素的个数，散列地址为3的元素的个数，散列地址为8的元素的个数。
如果用一个长度为11的数组来存储散列后的数据，并假设采用线性探测再散列的方式进行冲突检测，试写出散列后的序列。
散列地址为0的元素有1个散列地址为3的元素有1 个散列地址为8的元素有2个散列后的序列：□66□□90□25□□□50□18□63□41□32。
