数据结构例题.

各章例题Contents第1章例题1第4章例题2第4-1章例题3第4-2章例题4第7章例题6第5章例题5第8章例题7第9章例题8第1章例题选择题A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构【答案】C在数据结构中，从逻辑上可以把数据结构分成：（）判断题：1、每种数据结构的逻辑结构与物理结构总是一致的（）2、数据元素是数据的最小单位（）3、数据项是具有独立含义的数据最小单位（）4、数据结构就是指数据在计算机中的存储结构（）【答案】1、错误2、错误3、正确4、错误第1章例题填空题：1、存储结构的基本类型是（）。2、在算法正确的前提下，评价一个算法的两个标准是（）3、数据结构的研究内容包括的三个方面是（)4、若各数据元素之间的逻辑关系可以用一个线性序列简单的表示出来，则称之为（），否则称之为（）。顺序存储、链式存储、索引存储、散列存储时间复杂度、空间复杂度逻辑结构、存储结构、算法线性结构非线性结构第1章例题分析题：设n为正整数，确定下列划线语句的执行频度。for(i=0;in;i++)for(j=0;ji;j++)for(k=0;kj;k++)x=x+1;【分析】语句的执行频度是该语句重复执行的次数。计算循环语句段中某一语句的执行次数，要得到语句执行与循环变量之间的关系。【解答】这是一个三层嵌套循环，最内层的循环次数由j决定，次内层的循环次数由i决定，而i从1变化到n。所以划线语句的执行频度为：niijj11第1章例题概念题1、描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。【解答】头指针是指向链表中第一个结点（头结点或首元结点）的指针；在首元结点之前附设的一个结点称为头结点；首元结点是指链表中存储线性表中第一个数据元素结点。若链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。第4章例题2、简述线性表的两种存储结构的主要优缺点及各自适用的场合。【分析】【解答】顺序存储可以按位置直接存取数据元素，方便灵活，效率高，但插入、删除操作是将引起元素移动，降低了效率；链式存储元素存储采用动态分配，利用率高，但需增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素的动态插入或删除操作的场合。线性表的两种主要存储结构各有其优点和缺点，不能简单地说哪个好哪个差，要根据实际问题和其适用的场合使用。第4章例题3、下面关于线性表的叙述中，错误的是()A）线性表采用顺序存储，必顺占用一片连续的存储单元。B）线性表采用顺序存储，便于进行插入和删除操作。C）线性表采用链接存储，不必占用一片连续的存储单元D）线性表采用链接存储，便于插入和删除操作。4、下面关于串的叙述中，哪一个是不正确的?()A)串是字符的有限序列B)空串是由空格构成的串C)模式匹配是串的一种重要运算D)串既可以采用顺序存储，也可以采用链式存储【答案】3、B4、B第4章例题5、下述哪一条是顺序存储方式的优点?()A)存储密度大B)插入运算方便C)删除运算方便D)可方便地用于各种逻辑结构的存储表示【答案】5、A6、C第4章例题6、以下关于链式存储结构的叙述中哪一条是不正确的?A)结点除自身信息外还包括指针域,因此存储密度小于顺序存储结构B)逻辑上相邻的结点物理上不必邻接C)可以通过计算直接确定第i个结点的存储地址D)插入、删除运算操作方便,不必移动结点7、单链表的每个结点中包括一个指针link，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针p指向的单链表结点之后，下面的操作序列中哪一个是正确的？()A）q=p-link;p-link=q-linkB）p-link=q-link;q=P-linkC）q-link=p-link;p-link=q;D）p-link=q;q-link=p-link【答案】7、C第4章例题第4-1章例题1、有６个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列:()A)5,4,3,6,2,1B)4,5,3,1,2,6C)3,4,6,5,2,1D)2,3,4,1,5,62、以下哪一个不是栈的基本运算?()A)删除栈顶元素B)删除栈底元素C)判断栈是否为空D)将栈置为空栈3、以下哪一个不是队列的基本运算？()A）从队尾插入一个新元素B）读取队头元素的值C）判断一个队列是否为空D）从队列中删除第i个元素【答案】1、C2、B3、D4、设栈S的初始状态为空，队列Q的初始状态为________________a1a2a3a4________________↑↑队头队尾对栈S和队列Q进行下列两步操作：1)、删除Q中的元素，将删除的元素插入S，直至Q为空。2)、依次将S中的元素插入Q,直至S为空。在上述两步操作后，队列Q的状态是________。第4-1章例题【答案】a4a3a2a15、判断一个循环队列Q（元素最多为n）为空的条件是（）A）Q-rear=Q-frontB）Q-rearQ-frontC）Q-front==（Q-rear+1）MODnD）Q-front(Q-rear+1）MODn6、判断一个循环队列Q（元素最多为n）为满的条件是（）A）Q-rear==Q-frontB）Q-rearQ-frontC）Q-front==（Q-rear+1）MODnD）Q-front（Q-rear+1）MODn7、设有一个单端受限的双端队列Q，元素入队序列为：ABCD,问不可能的输出序列有哪些？第4-1章例题【答案】5、A7、输入受限：DBCA6、C输出受限：DBCA第4-2章例题1、设有二维数组A[0..9，0..19]，其每个元素占2个字节，数组按列优先顺序存储，第一个元素的存储地址为100,那么元素A[6,6]的存储地址为______.2、以下关于广义表的叙述中,正确的是A)广义表是0个或多个单元素或子表组成的有限序列B)广义表至少有一个元素是子表C)广义表不可以是自身的子表D)广义表不能为空表3、广义表（（a））的表头是（），表尾是（）A、aB、（a）C、（）D、（（a））【答案】1、2322、A3、B，C4、求下列广义表的操作结果Head（((a，b)，(c，d))）Tail（((a，b)，(c，d))）Head(Tail(((a，b)，(c，d))))Tail(Head(((a，b)，(c，d))))Head(Tail(Head(((a，b)，(c，d)))))【答案】Head（((a，b)，(c，d))）=(a，b)Tail（((a，b)，(c，d))）=((c，d))Head(Tail(((a，b)，(c，d))))=(c，d)Tail(Head(((a，b)，(c，d))))=(b)Head(Tail(Head(((a，b)，(c，d)))))=b第4-2章例题1、在结点个数为n(n1)的各棵树中，（1）高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？（2）高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？【答案】（1）结点个数为n时，高度最小的树的高度为2，有2层；它有n-1个叶结点，1个分支结点；（2）高度最大的树的高度为n，有n层；它有1个叶结点，n-1个分支结点。第5章例题2、试分别找出满足以下条件的所有二叉树：(1)二叉树的前序序列与中序序列相同;(2)二叉树的中序序列与后序序列相同;(3)二叉树的前序序列与后序序列相同。【解答】(1)二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；(2)二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；(3)二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。第5章例题3、深度为k（根的层次为1）的完全二叉树至少有多少个结点？至多有多少个结点？k与结点数目n之间的关系是什么？【分析】由完全二叉树的定义可知，对于k层的完全二叉树，其上的k-1层是一棵深度为k-1的满二叉树。所以对于所有深度为k的完全二叉树，它们之间的结点数目之差等于各树最后一层的结点数目之差。【解答】深度为k的完全二叉树，其最少的结点数=深度为k-1的满二叉树的结点数+1=；其最多的结点数=深度为k的满二叉树的结点数=。k与结点数目n之间的关系可以根据二叉树的性质4得出：112112kk12knk2log1第5章例题4、对于深度为k，且只有度为0或2的结点的二叉树，结点数至少有多少？至多有多少？(分析)【解答】结点数至多有：2k-1结点数至少有：2k-1【分析】对于结点数至多为多少的问题比较好回答，我们知道满二叉树中只有度为0或2的结点，所以结点数至多为同等深度的满二叉树的结点数。对于结点数至少为多少的问题，由于树中只存在度为0或2的结点，即对一个结点而言，要么它没有子结点，要么就有两个子结点，所以在这样的树中，除第一层（根所在的层）外，每一层至少有两个结点。第5章例题5、已知一棵二叉树的中序序列为BDCEAFHG，后序序列为DECBHGFA，求对应的二叉树。【分析】根据各种遍历方法的定义，可知：二叉树先序序列=根+左子树先序序列+右子树先序序列；二叉树中序序列=左子树中序序列+根+右子树中序序列；二叉树后序序列=左子树后序序列+右子树后序序列+根；从先序和后序序列中可以很容易的知道那一个结点是根，而在中序序列中，可以根据根得到左、右子树的中序序列，相应的也就知道左、右子树的结点集合了。可以根据集合中的结点划分先序或后序序列中除根以外的结点序列，从而得到左、右子树的先序或后序序列。依次类推，便可以递归得到整棵二叉树。中序序列左子树中序序列根右子树中序序列前序序列根左子树前序序列右子树前序序列第5章例题【解答】构造这棵二叉树的过程如下所示：中序序列：BDCE[A]FHG后序序列：DECBHGF[A]中序：[B]DCE后序：DEC[B]中序：[F]HG后序：HG[F]中序：D[C]E后序：DE[C]中序：H[G]后序：H[G]中序：[D]后序：[D]中序：[E]后序：[E]中序：[H]后序：[H]AFGHEDCB可以画出这棵二叉树为：第5章例题与上题有关的往届考题：1、二叉树的先序遍历和中序遍历为：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是（）A）EB）FC）GD）H2、某二叉树结点的对称序（中序）序列为ABCDEFG，后序序列为BDCAFGE。该二叉树结点的前序序列为（）A）EGFACDBB）EACBDGFC）EAGCFBDD）EGACDFB3、如果一棵二叉树结点的前序序列是ABC，后序序列是CBA，则该二叉树结点的对称序序列A)必为ABCB)必为ACBC)必为BCAD)不能确定【答案】1、C2、B3、D第5章例题6、分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。并判断下列论述是否正确，为什么？（1）二叉树是一种特殊的树；（2）度为2的树是一棵二叉树；（3）度为2的有序树是一棵二叉树。【解答】具有3个结点的树有两种形态，如图1所示；而具有3个结点的二叉树有5种形态，如图2所示。图1图2具有3个结点的二叉树的5种形态（1）错误（2）错误（3）错误第5章例题7、在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序A）都不相同B）先序和中序相同，而与后序不同C）完全相同D）中序和后序相同，而与先序不同8、在完全二叉树中，若一个结点只有一个叶结点，则它没A）左子结点B）左子结点和右子结点C）右子结点D）左子结点、右子结点和兄弟结点9、在下列存储形式中，哪一个不是树的存储形式A）双亲表示法B）孩子链表表示法B）孩子兄弟示法D）顺序存储表示法【答案】7、C8、C9、D第5章例题填空：10、在树中，一个结点的直接子结点的个数称为该结点的_____。11、如果