东大23年9月《数据结构Ⅱ》复习题及答案
发布时间：2023-09-19 00:09:48浏览次数：41 1 / 13东 北 大 学 继 续 教 育 学 院数据结构 II 复习题 一、 单选题．表达式 的后缀表达式是．．．．．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是空或只有一个结点 高度等于其结点数 任一结点无左孩子 任一结点无右孩子．下面的说法中正确的是任何一棵二叉树的叶子结点在三种遍历中的相对次序不变。按二叉树定义，具有三个结点的二叉树共有 种。．，．．．，都错．树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的说法正确的是．树的后序遍历与其对应的二叉树的先序遍历相同 ．树的后序遍历与其对应的二叉树的中序遍历相同．树的先序序遍历与其对应的二叉树的中序遍历相同 ．以上都不对．下列说法正确的是课程名称: 数据结构 II
10 /K, 在新表中查询是否存在和 2(!(=68相同的元素F++LLK& +表明当前考察的是第一个元素2(!(=68+2(!(=68,G F"'2!(#*?+, 修改表长G %I'#(DJ-此算法的时间复杂度为 O 2!(#*?。六、 算法设计题（本题 10 分）设计算法从图的邻接表结构转换成邻接矩阵结构的算法。参考答案：C"K2.*M"KN*')K2.*#!$KN*')#=E 将图的邻接表表示转换为邻接矩阵表示。F"'+,4+, 设图有 个顶点，邻接矩阵初始化。F"'K+,K4+,K#=686K8+,F"'+,4+,E%+#!68O'.*', 取第一个邻接点。>?!(%E 下一个邻接点#=686%&KC()8+,%+%&()*,G >?!(G F"'G K2.*M"KN*')七、 综合题、阅读算法，在横线处填入语句或注释。C"()?#(D22!.*@2，*=E 本算法实现带头结点的单链表中前 = 个结点和后 个结点的整体互换课程名称: 数据结构 II
11 /F=@@2&()*E 链表非空%+2&()*,（ ） >?!(4=@@%E （ ） %+%&()*,,G >?!(F%@@（ ） E?+2&()*, 记 结点的位置 2&()*+%&()*, 将 结点链接在头结点之后%&()*+（ ） ,-+2&()*, 令 -指向 结点 >?!(-&()*-+-&()*, 查找 结点 -&()*+（ ） G F%G F=G ()?#(D2参考答案（）+,（）查找第 =个结点（）%&()*（）7H22（）?,．一个仅包含二元运算符的算术表达式，以二叉链表形式存储在二叉树 M 中，设计算法 P课程名称: 数据结构 II
12 /实现求值，并指出遍历的方式。参考答案：（）算法实现。+,*PM'(MEFAM'(*I',FAMQ!?!@@AMQ'?! 判断是否为叶子结点'(*I'MQ*,2C+PMQ!?!,:C+PMQ'?!,.>*?MQ*E 求值运算.(RRS+2C:C,'(,.(RRS+2C:C,'(,.(RRS+2C:C,'(,.(R RS+!C :C,'(,G .>*?'(*I', 返回值G P（）后序遍历二叉树求值。．设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。逆邻接表存储结构定义如下：顶点结构 表结点结构参考答案：算法实现**"%"."'*2'%?$**%C68E 以逆邻接表为存储结构的有向图的拓扑排序*"%+,F"'+,4C()I=,F"'%+K!.*68O'.*(#(,%,%Q()*课程名称: 数据结构 II C()* O'.*KC() F" O'.*'
13 /O"I*(#'(($"I*(#'((, 对各顶点求出度"I*(#'((6%QKC()8,1*J*@J, 初始化栈F"'+,4()I=,F"I*(#'((68++9I.?@J$, 出度为零的顶点入栈>?!(AJ*JE9"%@J$,%'*FK!.*68C()*(),*%C6*"%8+,F"'%+K!.*68O'.*(#(,%,%Q()*EK+%QKC(),"I*(#'((6K8,FA"I*(#'((6K89I.?@J$K, 出度为零的顶点入栈G F"'G >?!(F*"%4C()I='(*I', 无环(!.(E 输出顶点拓扑排序序列F"'+,K+*"%,4C()I= ,$KE 置逆输出*(=%+*%C68,*%C68+*%C6K8,*%C6K8+*(=%,G F"''(*I',G (!.(G *"%"."'*课程名称: 数据结构 II
2 / 13二又树按某种方式线索化后，任一结点均有指向前趋和后继的线索二叉树的先序遍历序列中，任意一个结点均处于在子孙结点前二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值．．．．都不对二叉树的第 层的结点数最多为．．以下说法不正确的是．无向图中的极大连通子图称为连通分量．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点．有向图的遍历不可采用广度优先搜索．有向图 用邻接矩阵 存储，则顶点 的入度等于 中第 行 的元素之和 第 列 的元素之和第 行 的元素个数 第 列非 的元素个数设有 个结点的无向图，该图至少应有多少条边才能确保是一个连通图？．下图的邻接表中，从顶点 出发采用深度优先搜索法遍历该图，则可能的顶点序列是 课程名称: 数据结构 II
3 / 13．抽象数据类型的三个组成部分分别为．数据对象、数据关系和基本操作．数据元素、逻辑结构和存储结构．数据项、数据元素和数据类型．数据元素、数据结构和数据类型．要求相同逻辑结构的数据元素具有相同的特性，其含义为数据元素具有同一的特点不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致每个数据元素都一样仅需要数据元素包含的数据项的个数相同．下列各式中，按增长率由小至大的顺序正确排列的是．√n，！，， ． ，，!"#，．，!"#，!"#， ．，!"#$$在下列哪种情况下，线性表应当采用链表表示为宜经常需要随机地存取元素 课程名称: 数据结构 II
4 / 13经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间 表中元素的个数不变．设指针 % 指向双链表的某一结点，则双链表结构的对称性可表示为%&%'"'&()*+%&()*&()*,%&%'"'&%'"'+%&()*&%'"',%&%'"'&()*+%&()*&%'"',%&()*&()*+%&%'"'&%'"',已知指针 % 和 - 分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针. 指向另一个单链表中某个结点，则在 . 所指结点之后插入上述链表应执行的语句为.&()*+-；%&()*+.&()*； .&()*+%；-&()*+.&()*；%&()*+.&()*；.&()*+-；-&()*+.&()*；.&()*+%；栈和队列的共同特点是只允许在端点处插入和删除元素都是先进后出 都是先进先出没有共同点 对于链队列，在进行插入运算时仅修改头指针 头、尾指针都要修改仅修改尾指针 头、尾指针可能都要修改．设有一个顺序栈的入栈序列是 、、，则 个元素都出栈的不同排列个数为．．．设一个栈的输入序列为 ，，，，则借助一个栈所得到的输出序列不可能是课程名称: 数据结构 II
5 / 13．，，，．，，，，，，，，，参考答案：题号 答案 题号 答案 二、 填空题下面程序段中带下划线的语句的执行次数的数量级是。+； /01234+,．假设带头结点的非空单循环链表中仅设尾指针 2，则在第 个结点之前插入指针 . 所指结点的语句依次是（ ）。．无表头结点的链队列 5 为空的条件是（ ）。．设 5678为循环队列，其头、尾指针分别为 9 和 :，则队 5 中当前所含元素个数为（ ）。．一棵含 个结点的完全二叉树的深度为（ ）。．在 ; 网 中，存在环意味着某项活动以自己为先决条件；对程序的数据流图来说，它表明存在（ ）。有向图 可拓扑排序的判别条件是。．如果结点 有 个兄弟，而且 是 的双亲，则 的度是（ ）。．应用回溯与分支限界法解决实际问题时，在搜索过程中利用判定函数，也称为（ 课程名称: 数据结构 II
6 / 13 ）。若以 作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是。 参考答案：1. log2n 2 ． s->nest=L->next->next ； L->next->next =S 3 ． Q->real==Q->front=NULL 4．（ R-P+N）% N 5．10 6．死循环 7. 不存在环8．4 9.限界函数 10. 4231三、 应用题．比较线性表和栈的基本操作的不同点。．有一个二叉树按层次顺序存放在一维数组中，如下图所示：试求：（1）该树的后序遍历序列。 （2）画出该树的后序线索树。 3 ．分析顺序查找算法的“监视哨”设置作用．对 n 个整数的序列进行直接选择排序。（）算法描述。（）并给出实例（）的排序过程。参考答案：．主要区别是对插入和删除操作的限制。如线性表允许在表内任一位置进行插入和删除；而队列只允许在表尾一端进行插入，在课程名称: 数据结构 II
ABEDC 7 / 13表头一端进行删除；所以也称队列为受限的线性表。表头为队列头；表尾为队列尾。插 入 删 除线性表 1.('*2$$) (!(*(2$ << <<队列 1.('*2$$) (!(*(2$．（）后序遍历序列 C E D B A （2）后序线索树．为了考虑查找不成功的情况$在每次进行关键字的比较前，首先要判断循环变量 是否数组越界，这对算法来说是必要的。如果每步省略数组下标是否越界的判断，则可以大大提高算法运行的效率。为此，可以利用预留的 号单元，作为所设的“监视哨”控制循环变量 的出界。假设数据从后向前比较，监视哨设在数组低端 2(!(=68+将算法中的判断语句>?!(4+2!(#*?@@2(!(=68A+,改为 >?!(2(!(=68A+,这样，当在查找表中不存在其关键字等于给定值的数据元素时， 必等于 $并且这样的处理并不影响查找成功的情况。 ．（）直接选择算法描述：课程名称: 数据结构 II
8 / 1368第 趟，从 个记录中，经过比较选出关键字值为最小的记录，并与第 个记录交换位置。68第 趟，从余下的 个记录中选择出当前关键字最小的排序，并与第 个记录交换位置。68第 趟，在无序的第 个到第 个的 个记录中选出关键字最小的记录，与第 个记录进行互换。68以此类推，直至第 趟排序结束。（）初始状态 52 49 80 36 14 58 61 23 +68+68+68+68+68+68+68排序结果 68四、 算法阅读题设计算法实现以链表作存储结构，将线性表中前 m 个元素和后 n 个元素进行整体互换，即$B$=$$B$改变成$B$$$B$=。阅读算法，在横线处填入语句或注释。C"()?#(D22!.*@2，*=E 本算法实现单链表中前 = 个结点和后 个结点的整体互换F=@@2&()*E 链表不空且%+2&()*,（ ） >?!(4=@@%E （ ） %+%&()*,,G >?!(课程名称: 数据结构 II
9 / 13F%@@（ ） E A+时才需要修改指针?+2&()*, 以指针 ?记 结点的位置 （ ） +%&()*, 将 结点链接在头结点之后%&()*+7H22, 设 =的后继为空-+2&()*, 令 -指向 结点 >?!(-&()*-+-&()*, 查找 结点 -&()*+?, （ ） G F%G F=G ()?#(D2参考答案（）+,（）查找第 =个结点（）%&()*（）2&()*（）将第 结点链接到 结点之后五、 算法设计题设计算法 %I'#(DJ- 实现删除顺序表 J-2.* 中重复元素，指出其算法的时间复杂度。参考答案：C"%I'#(DJ-J-2.*@2E 删除顺序表 2 中的重复元素+, 指示新表的表尾F"'+,42!(#*?,E 顺序考察表中每个元素 K+,>?!(K4+@@2(!(=6K8A+2(!(=68课程名称: 数据结构 II
