数据结构自测试题及答案.doc

数据结构自测题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 ）A2 B3 C4 D54.树结构中，前驱结点与后继结点之间存在（ B ）关系。A一对一 B一对多 C多对一 D多对多5.堆栈的特性描述是（ B ）。AFIFO BFILO CFIFO和FILO DFIFO或FILO6.队列的特性描述是（ A ）。AFIFO BFILO CFIFO和FILO DFIFO或FILO7.下列数据结构中，是非线性结构的是（ A ）A树 B堆栈 C队列 D循环队列8.设某个初始为空的容纳int型数据的堆栈进行了如下操作（每一步均未发生溢出）：push(1)、push(3)、pop()、push(6)、push(1)、pop()、push(3)、push(8) 后，该堆栈中从栈顶到栈底的元素依次为（ D ）A8 1 8 3 B1 3 1 8 C1 6 3 8 D8 3 6 1二、 判断题1.二叉树可以为空树。（ ） 2.顺序表和链表都是线性表。（ ）3.线性表的长度是线性表占用的存储空间的大小。（）4.队列只能采用链式存储方式。（）5.由二叉树的先序序列和中序序列能唯一确定一棵二叉树。（）6.存在有偶数个结点的满二叉树。（）三、 填空题1.数据结构是数据在计算机内的 组成形式 和 相互关系 。2.二叉树的三种遍历方式分别为 中序遍历 、 先序遍历 和 后序遍历 。3.深度为K的满二叉树共有 2k1 个结点。4.N个顶点的无向图是完全图的条件是其边数为 n ( n1 ) / 2 。四、 名词解释1.ADT ADT是抽象数据类型的简称，指一个数学模型以及定义在该模型上的一组操作。2.栈 栈是限定仅在表尾进行插入或删除操作的线性表，具有先进后出（FILO）的特性。3.队列 队列是只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表，具有先进先出（FIFO）的特性。五.简答题1.分别写出下图所示二叉树的先序遍历、中序遍历和后序遍历序列ABCDEFGHIJKLMNOPQ中序遍历： 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 A2.用邻接矩阵表示下图所示的拓扑（节点已标号）。124350100110110010010100010100数据结构自测题2一.单项选择题1.设某个初始为空的容纳int型数据的非循环队列进行了如下操作（每一步均未发生溢出）：inqueue(1)、inqueue (3)、dequeue()、inqueue (6)、inqueue (1)、dequeue()、inqueue (3)、inqueue (8) 后，该队列中从队尾到队首的元素依次为（ C ）A1 6 3 8 B6 1 3 8 C8 3 1 6 D8 3 6 12.最多3个结点的二叉树共有（A）种不同的形态（不区分结点）。A5 B4 C3 D23.串的长度是（ D ） A串中不同字符的数目B串中不同字母的数目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 ）。AABDC BDCBA CCDBA DCDAB8.下列说法正确的是（ 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，请给出二叉树的后序序列，并画出这棵树的拓扑。后序序列为ACDBGIHFEEBADCFHGI2.（15分）已知一个无向图的顶点集为V0,V1,V7，其邻接矩阵如下所示：V0 0 1 0 1 1 0 0 0V1 1 0 1 0 1 0 0 0V2 0 1 0 0 0 1 0 0V3 1 0 0 0 0 0 1 0V4 1 1 0 0 0 0 1 0V5 0 0 1 0 0 0 0 0V6 0 0 0 1 1 0 0 1V7 0 0 0 0 0 0 1 0(2)画出该图的图形23104756(1) 给出从V0出发的深度优先、广度优先遍历序列深度优先序列V0,V1,V2,V5,V4,V6,V3,V7 广度优先序列V0V1V3V4V2V6V5V7数据结构自测题3一.单项选择题1.对二叉排序树，使用（ B ）的遍历方式，可以获得对结点序列关键字的排序。A先序遍历 B中序遍历 C后序遍历 D层次遍历2.用数组表示线性表的优点是（ C ）。A便于插入和删除操作 B可以动态地分配存储空间 C便于随机存取 D不需要占用一片相邻的存储空间3.一棵二叉树的先序遍历次序为 ABDGECFH ， 中序遍历次序为 DGBEAFHC ， 则其后序遍历次序为（ C ）。AACFHBEDG BABCDGHEF CGDEBHFCA DBEFCHAGD4.从未排序序列中选出最小的元素，并将其依次放入到已排序序列的一端的排序算法称为（ 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分）对于线性