《数据结构》习题与参考答案

1、杭电自动化学院软件技术基础之数据结构习题1) 选择题1. *下面关于线性表的叙述中，正确的是（ D ）A) 线性表的每个元素都有一个直接前驱和直接后继B) 线性表中至少要有一个元素C) 线性表中的元素必须按递增或递减的顺序排列D) 除第一个元素和最后一个元素外，其余每个元素有且仅有一个直接前驱和直接后继2. 下面关于线性表的叙述中，错误的是（ B ）A) 采用顺序存储的线性表必须占用一片连续的存储单元B) 采用顺序存储的线性表便于进行插入和删除操作C) 采用链接存储的线性表，不必占用一片连续的存储单元D) 采用链接存储的线性表，便于进行插入和删除操作3. 设有栈S和队列Q，初始状态皆为空，元素

2、a1、a2、a3、a4、a5、a6依次入栈，出栈的元素依次进入队列Q，若6个元素的出栈序列为： a2、 a4、a3、a6、 a5、 a1，则栈的容量至少是（ C ）第 11 页 共 11 页A) 6B) 4C) 3D) 24. 设在栈中，由顶向下已存放元素c、b、a，在第4个元素d入栈前，栈中元素可以出栈，试问d入栈后，不可能的出栈序列是（ C ）A) d c b a B) c b d aC) c a d bD) c d b a5. *在一棵二叉树的先序遍历、中序遍历、后序遍历序列中，所有叶节点的先后顺序（ B ）A) 都不相同B) 完全相同C) 先序和中序相同，后序不同D) 中序和后序相同，

3、先序不同6. 设二叉树根结点的层次为0，一棵高度为h的满二叉树的结点个数是（ C ）A) 2hB) 2h1C) 2h1D) 2h117. 已知一棵二叉树的前序序列为ABDGCFK，中序序列为DGBAFCK，则结点的后序序列为（ B ）A) ACFKDBGB) GDBFKCAC) KCFAGDBD) ABCDFKG8. 欲得到二叉搜索树（BST）各结点值的递增序列，试问应该采用何种遍历方法（ B ）A) 先序遍历B) 中序遍历C) 后序遍历D) 层次遍历9. *与数据元素本身这是存储的内容的形式、内容、相对位置、个数无关的是数据的（ C ）A) 存储结构B) 存储形式C) 逻辑结构D) 运算实现

4、10. 有一棵非空的二叉树（第0层为根结点），其第i层上至多有（ A ）个节点A) 2iB) 2i1C) 2i1D) i11. 双向链表结点结构如下：LLinkRLinkData其中：LLink是指向前趋结点的指针域，Data是存放数据元素的数据域，RLink是指向后继结点的指针域。下面给出的算法段是要把一个新结点Q作为非空双向链表的结点P的前趋，插入到此双向链表中。能正确完成要求的算法段是（ C ）A) QLLink=PLLink;QRLink= P;PLLink=Q;PLLink RLink=QB) PLLink=Q;QRLink= P;PLLink RLink=Q;QLLink=PLLi

5、nkC) QLLink=PLLink;QRLink= P;PLLink RLink=Q;PLLink=Q12. 若某线性表中最常用的操作是取第i个元素随机访问！和第i个元素的前趋元素，则采用（ A ）存储方式最节省时间A) 顺序表B) 单链表C) 双链表D) 单循环链表13. 设数组Data0m作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ D ）A) front = front + 1B) front = (front + 1) mod mC) rear= (rear + 1)mod mD) front=(front + 1)mod (m +

6、1)14. 用数组A0m-1存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为（ A ）A) (rear front + m) mod mB) (rear front + 1) mod mC) (rear front 1 + m) mod mD) (rear front) mod m15. 以下有关数据结构的叙述，正确的是（ C ）A) 线性表的线性存储结构优于链式存储结构B) 二叉树的第i层有2i1个结点，深度为k的二叉树上有2k1个结点C) 严格地讲二维数组不是线性表，但可以看成是线性表在下述含义上的扩展：二维数组是其数据元素为线性表的线性表D) 栈

7、的操作方式是先进先出16. 二维数组Mi,j的元素是4个字符（每个字符占用一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5。M按行存储时的元素M3,5的起始地址与M按列存储时的元素（ B ）的起始地址相同A) M2,4B) M3,4C) M3,5D) M4,4提示：M0:4, 0:5A +i*6+j=A+3*6+5A+j*5+i3*6+5= j*5+i i,jN,17. 设计一个判别表达式中左右括号是否配对出现的算法，采用（ B ）数据结构最佳A) 线性表的顺序存储结构B) 栈C) 队列D) 线性表的链式存储结构18. 深度为6（根的层次为1）的二叉树至多有结点（ C ）

8、A) 31B) 32C) 63D) 6419. 将含有100个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为1。编号为71的双亲的编号为（ B ）A) 34B) 35C) 36D) 无法确定20. 如图所示二叉树的中序遍历序列是（ B ）A) a b c d g e fB) d f e b a g cC) d b a e f c gD) d e f b a g c21. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列为（ D ）A) a c b e d B) d e c a bC) d e a b cD) c e d b a22

9、. 如果T2是由树T转换而来的二叉树，那么T中结点的前序就是T2中结点（ A ）A) 前序B) 中序C) 后序D) 层次序23. 如果T2是由树T转换而来的二叉树，那么T中结点的后序就是T2中结点（ B ）A) 前序B) 中序C) 后序D) 层次序24. 若某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是bgdaechf，则其后序遍历的结点访问顺序是（ D ）A) bdgcefhaB) gdbecfhaC) bdgechfaD) gdbehfca25. *在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（ A ）数据结构A) 栈B) 树C) 双向队列D) 广

10、义表26. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面。这种说法（ A ）A) 正确B) 错误27. 由于二叉树中每个结点的度最大为2，所以二叉树时一种特殊的树。这种说法（ B ）A) 正确B) 错误28. *二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值，小于其右孩子的值。这种说法（ B ）A) 正确B) 错误29. 设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是（ D ）A) 2hB) 2h-1C) 2h-1D) 2h+1-130. 含N个顶点的联通图中任意一条简单路径，其长度不可能超过（ C ）A) 1B) N/2C) N1D) N31

11、. *实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（ C ）存储结构A) 二叉链表B) 广义表存储结构C) 三叉链表D) 顺序存储结构 32. 具有65个结点的完全二叉树深度为（ B ）（根的层次号为1）A) 8B) 7C) 6D) 533. 以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n>0），空链域的个数为（ C =2N-(N-1) =N+1 ）A) 2n-1B) n-1C) n+1D) 2n+134. 在一非空二叉树的中序遍历序列中，根结点的右边（ A ）A) 只有右子树上的所有结点B) 只有右子树上的部分结点C) 只有左子树上的所有结点

12、D) 只有左子树上的部分结点35. 已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（ A ）A) CBEFDAB) FEDCBAC) CBEDFAD) 不定36. 一棵满二叉树共有n个结点，其中m个为树叶，则（ B ）N=2h-1=2h-1 2-1=m2-1, m=2h-1A) n=m+1B) m=(n+1)/2C) n=2mD) n=2×m37. 设矩阵A(aij,1i,j10)的元素满足：aij 0(ij, 1i,j10)aij0(i<j, 1i,j10)现将A的所有非0元素以行序存放在首地址为2000的存储区域中，每个元素占4个单

13、元，则元素9,5的首地址为（ AOrd(i,j)=i(i-1)/2+j-1 ）A) 2160B) 2164C) 2336D) 234038. 设高度为h的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（ B ），至多为（ E ）A) 2hB) 2h-1C) 2h+1D) h-1E) 2h-1F) 2h-1G) 2(h+1)-1H) 2h+139. 已知一有向图的邻接表出表存储结构如下：（1）、根据有向图的深度优先遍历算法，从顶点V1出发，所得到的顶点序列是（ B ）a) V1V2V3V5V4b) V1V3V4V5V2c) V1V3V2V4V5d) V1V4V3V5V2（2）、根

14、据有向图的广度优先遍历算法，从顶点V1出发，所得到的顶点序列是（ C ）a) V1V2V3V4V5b) V1V2V3V5V4c) V1V3V2V4V5d) V1V4V3V2V5（3）、能否根据邻接表画出该有向图？为什么？答：能，因为该邻接表已经表明了该图的所有节点以及所有节点之间的关系，即G（V，E）中的集合V和E都表达清楚了。40. 某图是一个非连通图，以下说否正确的是（ D ）A) 该图一定不存在连通分量B) 该图能用深度遍历来遍历到每个顶点C) 该图不存在回路D) 该图至少有两个顶点之间是不连通的41. 邻接表存储结构下图的深度优先遍历算法结构类似于二叉树的（ A ）A) 先序遍历B)

15、中序遍历C) 后序遍历D) 按层遍历42. 若某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ D ）存储方式最节省运算时间。A) 单链表B) 双链表C) 单循环链表D) 带头结点的双循环链表43. 下面关于数据结构的叙述中，正确的叙述是（ C ）A) 顺序存储方式的优点是存储密度大，且插入、删除运算效率高B) 链表中的每一个结点都包含恰好一个指针C) 将一棵树转换成为二叉树后，根结点没有右子树44. 一个n×n的带状矩阵Aaij如下： a11 a12 a21 a22 a23 a32 a33 a34 A an-1 n an n-1 an n 将带状区域

16、的元素aij（|ij|1）按行序为主序存储在一维数组B1.3n-2中，元素aij在B中的存储位置是（ B ）Ord(i,j)=3(i-1)-1+2+j-iA) i+2j-1B) 2i+j-2C) 3i-j+1D) i+j+245. 设树T的度为4，其中度为1、2、3和4的结点的个数分别为4、2、1、1，则T中叶子结点的个数是（ D ）X+4+2+1+1=节点总数1×42×23×14×1X=8 A) 5B) 6C) 7D) 846. 设有向图G有n个顶点，它的邻接矩阵为A，G中第i个顶点Vi的度为（ C ）A)B)C)D) 47. 二叉树的先序遍历和中序遍

17、历如下：先序遍历：EFHIGJK中序遍历：HFIEJKG该二叉树根的右子树的根是（ C ）A) EB) FC) GD) H2) 填空题1. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是 数据的逻辑结构 、 物理结构 、算法结构。2. 从逻辑关系上讲，数据结构主要分为两大类，它们是 线性结构 、 非线性结构 。3. 数据结构的四种基本的存储方法是 顺序存储 、 链式存储 、索引存储、散列存储。4. 数据的基本单位是 数据元素 。5. 在单链表中，指针P所指结点为最后一个结点的条件是 !(P->Next) 。6. 设一个链栈的栈顶指针为Top，栈中结点

18、两个字段分别为info和next，其中next是指示后继结点的指针，栈空的条件是 (!TOP) 。如果栈不空，则退栈操作为：p:=Top; Top:=Top->Next ;dispose(p);7. 设r指向单链表的最后一个结点，要在最后一个结点之后插入指针s所指的结点，需执行的三条语句是： r->Next=s ; r:=s; r.next:=nil;8. 数组通常只有两种运算： 读 和写（给定下标，修改相应的元素），这决定了数组通常采用 顺序表 来实现存储。9. 多维数组的两种存储方式是 按行序存储 和 按列序存储 。10. 栈和队列均可视为特殊的线性表，所不同的在于他们的 添加 和 删除 运算的限定不一样。11. 图的主要存储结构有两种，分别为 相邻矩阵 和 邻接表 。12. 将一棵树转化成二叉树的步骤是 。13. 从概念上讲，树和二叉树是两种不同的数据结构，将树转化成二叉树的基本目的是： 。14. 设n个节点的m叉树采用m叉链表（即每个结点有m个指针域，用来存放每个子树的根结点的存储地址）存储结构，请问会有 nm-（n-1） 个空指针域。15. 已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是 列的和 。16. 已知一个图的邻接矩阵表示，删除所有从第i个结点出发的弧的方法是 清除第i行 。17. 设F是由T1、T2、T3