杭电《数据结构》习题答案

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 ）第 14 页 共 14 页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

6、 (m + 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) 严格地讲二维数组不是线性表，但可以看成是线性表在下述含义上的扩展：二维数组是其数据元素为线性表的线

7、性表d) 栈的操作方式是先进先出16. 二维数组mi,j的元素是4个字符（每个字符占用一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5。m按行存储时的元素m3,5的起始地址与m按列存储时的元素（ b ）的起始地址相同a) m2,4b) m3,4c) m3,5d) m4,4m0: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）的二叉树至多有结点（

8、c ）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

9、a22. 如果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)

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

12、) 只有左子树上的部分结点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=2m37. 设矩阵a(aij,1i,j10)的元素满足：aij 0(ij, 1i,j10)aij0(ij, 1i,j10)现将a的所有非0元素以行序存放在首地址为2000的存储区域中，每个元素占4个单元，则元素9,5的首地

13、址为（ 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. 邻接表存储结构下图的深度优先遍历算法结构类似于二叉树的（ a ）a) 先序遍历b) 中序遍历c) 后序遍历d) 按层遍历41. 若某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ d ）存储方式最节省运算时间。a) 单链表b) 双链表c) 单循环链表d

15、) 带头结点的双循环链表42. 下面关于数据结构的叙述中，正确的叙述是（ c ）a) 顺序存储方式的优点是存储密度大，且插入、删除运算效率高b) 链表中的每一个结点都包含恰好一个指针c) 将一棵树转换成为二叉树后，根结点没有右子树43. 一个nn的带状矩阵aaij如下： a11 a12 a21 a22 a23 a32 a33 a34 a an-1 n an n-1 an n 将带状区域的元素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)

16、 i+j+244. 设树t的度为4，其中度为1、2、3和4的结点的个数分别为4、2、1、1，则t中叶子结点的个数是（ d ）x+4+2+1+1=节点总数14223141x=8 a) 5b) 6c) 7d) 845. （x）对树中的一个结点x，在先根序列的序号为pre(x)，在后跟序列中的序号为post(y)。若树中结点x是结点x和结点y的祖先，下列四个条件哪个条件正确（ ）a) pre(x) pre(y) 和 post(x) post(y)b) pre(x) post(y)c) pre(x) pre(y) 和 post(x) pre(y) 和 post(x)post(y)46. 设有向图g有n

17、个顶点，它的邻接矩阵为a，g中第i个顶点vi的度为（ c ）a)b)c)d) 47. 二叉树的先序遍历和中序遍历如下：先序遍历：efhigjk中序遍历：hfiejkg该二叉树根的右子树的根是（ c ）a) eb) fc) gd) h2) 填空题1. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是 数据的逻辑结构 、 物理结构 、算法结构。2. 从逻辑关系上讲，数据结构主要分为两大类，它们是 线性结构 、 非线性结构 。3. 数据结构的四种基本的存储方法是 顺序存储 、 链式存储 、索引存储、散列存储。4. 数据的基本单位是 数据元素 。5. 在单链表中，指

18、针p所指结点为最后一个结点的条件是 !(p-next) 。6. 设一个链栈的栈顶指针为top，栈中结点两个字段分别为info和next，其中next是指示后继结点的指针，栈空的条件是 (!top) 。如果栈不空，则退栈操作为：p:=top; top:=top-next ;dispose(p);7. 设r指向单链表的最后一个结点，要在最后一个结点之后插入指针s所指的结点，需执行的三条语句是： r-next=s ; r:=s; r.next:=nil;8. 数组通常只有两种运算： 读 和写（给定下标，修改相应的元素），这决定了数组通常采用 顺序表 来实现存储。9. 多维数组的两种存储方式是 按行序

19、存储 和 按列序存储 。10. 栈和队列均可视为特殊的线性表，所不同的在于他们的 添加 和 删除 运算的限定不一样。11. 图的主要存储结构有两种，分别为 相邻矩阵 和 邻接表 。12. 将一棵树转化成二叉树的步骤是 。13. 从概念上讲，树和二叉树是两种不同的数据结构，将树转化成二叉树的基本目的是： 。14. 设n个节点的m叉树采用m叉链表（即每个结点有m个指针域，用来存放每个子树的根结点的存储地址）存储结构，请问会有 nm-（n-1） 个空指针域。15. 已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是 列的和 。16. 已知一个图的邻接矩阵表示，删除所有从第i个结点出发的弧的方法是

20、 清除第i行 。17. 设f是由t1、t2、t3三棵树组成的森林，与f对应的二叉树为b，已知t1、t2、t3的结点个数分别是n1、n2、n3，则二叉树b的根结点的左子树和右子树中的结点个数分别为n11和 n2n3 。18. 用数组a1.n顺序存储完全二叉树的各结点，则当i(n-1)/2时，结点ai的右子女是结点 a2i+1 。3) 应用题1. 答：用三元组法表示稀疏矩阵可以节省存储空间。用三元组表示该稀疏矩阵： （6，6，8）（1，6，2）（2，1，1）（2，5，3）（3，4，5）（3，6，7）（4，2，8）（5，5，5）（6，4，6） 2. 答：1）插入节点66后的二叉搜索树60704058

21、75655768662）删除节点60后的二搜索叉树（1）从左子树取节点58704075576568（2）从右子树取节点657040755868573）用一维数组表达图二所示的树的存储结构（60，40，70，0，58，65，75，0，0，57，0，0，0，68，0，0）4）用一维数组表达二叉树的存储结构的缺点为容易浪费存储空间。3. 答： 1）说明每个顶点的度(degree)顶点度1323334252632）图的表示法中,相对于相邻矩阵,邻接表有下列好处 存储效率高，访问方便。 3）该图的相邻矩阵 010011101100010101011000100001100010 4）该图的邻接表表示 5

22、）根据第4小题的邻接表从顶点1开始的深度遍历为： 1、2、3、4、6、5广度优先遍历为：1、2、5、6、3、4我的大学爱情观目录：1、 大学概念2、 分析爱情健康观3、 爱情观要三思4、 大学需要对爱情要认识和理解5、 总结1、什么是大学爱情：大学是一个相对宽松，时间自由，自己支配的环境，也正因为这样，培植爱情之花最肥沃的土地。大学生恋爱一直是大学校园的热门话题，恋爱和学业也就自然成为了大学生在校期间面对的两个主要问题。恋爱关系处理得好、正确，健康，可以成为学习和事业的催化剂，使人学习努力、成绩上升；恋爱关系处理的不当，不健康，可能分散精力、浪费时间、情绪波动、成绩下降。因此，大学生的恋爱观必

23、须树立在健康之上，并且树立正确的恋爱观是十分有必要的。因此我从下面几方面谈谈自己的对大学爱情观。2、什么是健康的爱情：a、 尊重对方，不显示对爱情的占有欲，不把爱情放第一位，不痴情过分；b、 理解对方，互相关心，互相支持，互相鼓励，并以对方的幸福为自己的满足; c、 是彼此独立的前提下结合；3、什么是不健康的爱情：1)盲目的约会，忽视了学业;2)过于痴情，一味地要求对方表露爱的情怀，这种爱情常有病态的夸张;3)缺乏体贴怜爱之心，只表现自己强烈的占有欲;4)偏重于外表的追求;4、大学生处理两人的在爱情观需要三思：48. 不影响学习：大学恋爱可以说是一种必要的经历，学习是大学的基本和主要任务，这两

24、者之间有错综复杂的关系，有的学生因为爱情，过分的忽视了学习，把感情放在第一位；学习的时候就认真的去学，不要去想爱情中的事，谈恋爱的时候用心去谈，也可以交流下学习，互相鼓励，共同进步。49. 有足够的精力：大学生活，说忙也会很忙，但说轻松也是相对会轻松的！大学生恋爱必须合理安排自身的精力，忙于学习的同时不能因为感情的事情分心，不能在学习期间，放弃学习而去谈感情，把握合理的精力，分配好学习和感情。a) 有合理的时间；大学时间可以分为学习和生活时间，合理把握好学习时间和生活时间的“度”很重要；学习的时候，不能分配学习时间去安排两人的在一起的事情，应该以学习为第一；生活时间，两人可以相互谈谈恋爱，用心

25、去谈，也可以交流下学习，互相鼓励，共同进步。5、大学生对爱情需要认识与理解，主要涉及到以下几个方面：（1） 明确学生的主要任务“放弃时间的人，时间也会放弃他。”大学时代是吸纳知识、增长才干的时期。作为当代大学生，要认识到现在的任务是学习学习做人、学习知识、学习为人民服务的本领。在校大学生要集中精力，投入到学习和社会实践中，而不是因把过多的精力、时间用于谈情说爱浪费宝贵的青春年华。因此，明确自己的目标，规划自己的学习道路，合理分配好学习和恋爱的地位。（2） 树林正确的恋爱观提倡志同道合、有默契、相互喜欢的爱情：在恋人的选择上最重要的条件应该是志同道合，思想品德、事业理想和生活情趣等大体一致。摆正爱情与学习、事业的关系：大学生应该把学习、事业放在首位，摆正爱情与学习、事业的关系，不能把宝贵的大学时间，锻炼自身的时间都用于谈情说