数据结构综合练习题1填空题1.数据结构包含三个方面的内容，分别是数据的逻辑结构、数据的存储结构和数据的运算。
2.实现数据结构的四种存储方法有顺序存储方法、链接存储方法、索引存储方法和散列存储方法。
3.数据结构的逻辑结构有线性结构和非线性结构两大类。
4.一种抽象数据类型包括抽象数据的组织和与之相关的操作两个部分。
5.算法的五个重要特性是输入、输出、确定性、可行性和有穷性。
6.栈顶的位置是随进栈和出栈操作而变化的。
7.在链队列只有一个元素的情况下，对其做删除操作时，应当把对头指针和队尾指针都置为null。
8.操作系统中先来先服务是数据结构中的队列应用的典型例子。
9.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。
该缓冲区应该是一个队列结构。
10.有一棵树如下图所示，回答下列问题。
11.有一棵树如下图所示，回答下列问题。
（1）这棵树的根结点是K1；（1）结点k3的度是 2 ；（2）这棵树的叶子结点是K2，K4，K5，K7；（2）这棵树的度为 3 ；12.有一棵树如下图所示，回答下列问题。
13有一棵树如下图所示，回答下列问题。
这棵树的深度为 4 ；（1）结点K3的子女是 K5 ，K6 ； （2）结点K3的双亲结点是 K1 。
14.在一棵二叉树中，度为零的结点个数为n0，度为2的结点的个数为n2，则有n0=n2+1。
15.n （n>0）个结点的二叉树高度最大是 n ，其深度最小是⎡log 2(n+1)⎤或⎣⎦1log 2+n 。
16.n(n>0)个结点的满二叉树深度是)1(log 2+n ，叶子结点数是(n+1)/2。
阿 17.下面二叉树的中序序列是GDHABC 。
18.n （n>0）个结点的哈夫曼树中度为2的结点共 (n-1)/2 个，叶子结点共(n+1)/2个。
19.n 个顶点的有向图最多有 n*(n-1) 条边。
20.n （n>0）个顶点的连通无向图各顶点度之和最少是 2(n-1) 。
21.有6个顶点的无向图至少应有 5 条边才能确保是一个连通图。
22. n(n>0)个顶点的连通无向图至少有 n-1 条边。
23. 恰有 n(n-1) 条边的有向图称为有向完全图。
2单项选择题1.下列说法正确的是（ B ）A.数据元素是具有独立意义的最小标识单位B.原子类型的值不可再分解C.原子类型的值由若干个数据段组成D.结构类型的值不可再分解2.一个存储结点存放一个（B ）A.数据项B.数据元素C.数据结构D.数据类型3.在数据结构中，从逻辑上可以把数据结构分成（C ）A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构是数据元素之间存在一种（D ）A.一对多关系B.多对多关系C.多对一关系D.一对一关系5.算法分析的目的是（B ）A.正确性和简明性B.时间复杂性和空间复杂性C.可读性和文档性D.数据复杂性和程序复杂性6.算法必须具备输入输出和（C ）A.计算方法B.排序方法C.解决问题的有限运算步骤D.程序设计方法7.线性表中正确的说法是（D ）A.每个元素都有一个直接前驱和一个直接后继B.线性表至少要求一个元素C.表中的元素必须按由小到大或由大到小排序D.除了第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继8.线性表是具有n个（C ）的有限序列A.整数B.字符C.数据元素D.数据项9.线性表采用链式存储结构时，结点的存储地址（C ）A.必须是不连续的B.必须是连续的C是否连续都可以D.和头结点的存储地址相连续10.在带有头结点的单链表中插入一个新结点时不可能修改（A ）A.头指针B.头结点指针域C.开始结点指针域D其它结点指针域11.相对于顺序存储结构而言，链接存储的优点是（C ）A.随机存取B.节约空间C.增、删操作方便D.结点关系简单12.设线性表有n个元素，下面算法中在顺序表上实现比在链表上实现效率更高的是（A ）A.输出第i（1≤i<≤n）个元素值B.交换第0个元素与第1个元素的值C. 顺序输出这n 个元素的值D. 输出与给定值x 相等的元素在线性表中的序号 13. 下列说法正确的是（ A ）A. 栈是一种线性表B. 栈具有先进先出特性C. 栈删除运算会引起其它元素的移动D. 栈插入运算会引起其它元素的移动14. 一个栈的入栈序列是：a,b,c,d,e, 则栈的不可能的输出序列是（ C ）A. EdcbaB.decbaC.dceabD.abcde15. 一个链栈的栈顶指针是topNode ，则执行出栈操作时（栈非空），用topElement 保存被删除结点的数据元素，则执行（ D ）A. topElement = top; top = topNode.next;B. topElement = topNode.element;C. topNode = topNode.next; topElement = topNode.element;D. topElement = topNode.element; topNode = topNode.next; 16. 一个队列的入队序列是a,b,c,d, 则队列的输出序列是（ B ）A. d,c,b,aB.a,b,c,dC.a,d,c,bD.c,b,a,d 17. 将递归过程转化为非递归过程需要用到（ A ）A.栈B.队列C.树D.图 18. 栈和队列的共同点是（ C ）A. 都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点 19. 树最适合用来表示（ D ）A. 有序数据元素B.无序数据元素C.元素之间无联系的数据D.元素之间具有分支层次关系的数据20. 一棵深度为9的满二叉树的叶结点数是（ B ）A. 255B.256C.511D.51221. n 个结点的满二叉树的高度是（ B ）A.n/2B.)1(log 2+nC.)1(log 2-nD.n 2l og 22. 按照二叉树的定义，具有3个结点的二叉树有（ C ）种A. 3B.4C.5D.623. 深度为5的二叉树至多有（ C ）个结点A. 16 B32 C.31 D.1024. 由结点A 、B 、C 构成不同的二叉树共（ D ）棵A. 6B.18C.36D.3025.下列说法正确的是（D ）A.二叉树是度为2的无序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中的一个结点最多只有两棵子树，并且有左右之分26.一棵二叉树的先序序列是ABCDEF，它可能的中序序列是（A ）A.CBDAFEB.CABDEFC.DABCEFD.FCABED27.要唯一地确定一棵二叉树，只需要知道该二叉树的（C ）A.前序序列B.中序序列C.中序和后序序列D.前序和后序序列28.任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序（A ）A.不发生改变B.发生改变C.不能确定D.以上都不对29.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B ）倍A.1/2B.1C.2D.430.用邻接矩阵存储图所需的存储空间大小仅与（A ）有关A.图的顶点数B.图的边数C.图的顶点数与边数之和D.图的各顶点度之和31.若存储图G的邻接矩阵是对称矩阵，则G（C ）A.一定是无向图B.一定是连通无向图C.可能是无向图D.一定是有向图32.下列说法正确的是（B ）A.有向图的邻接矩阵一定是非对称矩阵B.无向图的邻接矩阵一定是对称矩阵C.若图G的邻接矩阵是对称的，则G一定是无向图D.有向图的邻接矩阵一定是下三角矩阵33.已知一个图如下所示。
若从顶点a出发按深度优先搜索算法进行遍历，则可能得到的一种顶点序列为（D ）A.abecdfB.acfebdC.aebfcdD.aedfcb3.解答题1.简述数据结构的逻辑结构和存储结构的区别和联系。
它们如何影响算法的设计与实现？若用结点表示某个数据元素，则结点和结点之间的逻辑关系就称为数据的逻辑结构。
数据在计算机中的存储表示称为数据的存储结构。
可见，数据的逻辑结构是反映数据之间的固有联系，而数据的存储结构是数据在计算机中的存储表示。
尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相邻，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。
由于采用的存储结构不同，该数据结构上的操作灵活性、算法复杂度等区别较大。
2.简述数据的运算与数据逻辑结构和存储结构之间的关系。
数据的运算定义在逻辑结构上，也就是说，一旦数据的逻辑结构确定了，就可以定义在这种逻辑结构上可以进行何种运算了。
但是，数据的运算的具体实现时依赖于数据的存储结构的。
同样的逻辑结构，可能有不同的存储结构。
那么，在不同的存储结构上实现同一个数据运算的方法也不一样。
所以，要具体实现某个运算，还要根据数据的存储结构来定。
3.试举一个应用数据结构的例子，叙述其逻辑结构、存储结构、运算这三方面的内容。
要点：说明逻辑结构、存储结构的概念，同时用自然语言例子中的逻辑结构和存储结构和运算的基本规则4.何时选用顺序表、何时选用链表作为线性表的存储结构为宜？（1）基于空间的考虑：当线性表的长度变化较大，难以估计其存储规模时，采用动态链表作为存储结构为好。
当线性表的长度变化不大，易于事先确定其大小时，为了节省存储空间，采用顺序表为好。
（2）基于时间的考虑：若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为好。
反之，对于频繁进行插入和删除的线性表，采用链表为好。
5.设二叉树如下所示，试采用顺序存储方法和链接存储方法画出它的存储结构。
bcd链式存储结构如下：6.设二叉树如下所示，试采用顺序存储方法和链式存储方法画出它的存储结构。
顺序存储结构如下：链式存储结构如下:7.设树形结构如下，请画出该树的双亲孩子链表表示。
ABDEF解：0123458.现有权值：7，16，5，28，2。
试构造这组权值的哈夫曼（Huvvman ）树。
用树形表示法画出这个哈夫曼（Huvvman ）树。
289.以下面数据作为叶子结点的权值构造一棵哈夫曼（Huvvman ）树。
用树形表示法画出这个哈夫曼（Huvvman ）树。
17，3，7，8，24，10，16，9，610.设图G=（V ，E ），V={ v0，v1，v2，v3，v4}，E={<v0，v1>，<v0，v2>，<v2，v3>，<v1，v4>，<v3，v4>}。
试给出G 的邻接矩阵和邻接表。
邻接矩阵如下0 1 1 0 00 0 0 0 1 0 0 0 1 0 0 0 0 0 10 0 0 0 0邻接表如下0214311.已知一个有向图G 的顶点集合为{A,B,C,D,E}，其邻接表为01234顶点表出边表（1）画出G 的图形（2）分别给出G 从A 开始的深度优先和广度优先遍历序列 （1）（2）从A 开始的深度优先序列：ABCDE从A 开始的广度优先序列：ABDEC12.设无向图G 的顶点集合为{a,b,c,d,e,f}，其邻接表如下：01234顶点表边表5（1）画出G 的图形（2）分别给出G 从a 开始的深度优先和广度优先遍历序列 （1）该图的图形（2）从a 开始的深度优先序列：abdcfe从a 开始的广度优先序列：abcdef4.算法设计题1.设顺序表类型定义如下：public class AList implements ListInterface {private Object[] entry; // 线性表元素数组private int length; // 线性表当前元素的个数private static final int MAX_SIZE = 50; // 默认的线性表的最大长度public AList() {length = 0;entry = new Object[MAX_SIZE];}}请写出从顺序表中删除指定位置的元素的算法。