重庆邮电大学2020《数据结构》随堂考试一答案解析

在重庆邮电大学2020春季学期《数据结构与算法A》随课考试试卷I中，这是一份关于数据结构基础概念和算法设计的测试。考试包含单项选择题和综合应用题两部分。 **单项选择题** 1. 问题涉及栈的输出顺序，尽管输入序列为1到n，但栈的输出并非确定的，因为元素的出栈顺序依赖于栈的内部操作，如元素的添加和删除策略。正确答案是D，表示第j个输出元素是不确定的。 2. 循环队列的管理中，队尾和队首指针的移动遵循模运算规则。出队一个元素后front指针加1，再入队两个元素后rear指针加2。初始值front=5, rear=1，经过调整后front变为0, rear变为3，选B。 3. 二维数组按行优先存储到一维数组中，计算元素A[8][5]的地址时，考虑行数和列数，以及每个元素占用3个存储单元。A[8][5]位于第9行第6列，对应地址为SA+(9*10+6-1)*3=SA+255，选D。 4. 二叉树的结点数最少情况是形成满二叉树，其中度为0的结点（叶结点）数和度为2的结点数相等。已知总结点数为2011，最小结点数为116，那么度为2的结点数也是116，所以结点总数至少为2*116+1=233，选B。 5. 题目询问的是二叉树中无右孩子的结点个数。前115个结点都有右孩子，剩下的结点都是无右孩子的，因此答案是1896，选D。 **综合应用题** 1. 度为m的树中，叶子结点（度为0的结点）的数量可以通过递归或数学公式计算得出。设总结点数为N，则N = ni(0) + n1(1) + ... + nm(m)，由于所有非叶子结点的子树之和等于所有结点数减去叶子结点数，即N - n0 = n1 + 2n2 + ... + m*ni，将这两个等式联立，可得n0 = N - (n1 + 2n2 + ... + m*ni)。 2. 第二题未给出具体题目，但可能是考察二叉树的性质，例如计算度数分布的树的结点总数，或者根据特定条件构造二叉树等。 通过这份试卷，学生能够检验对数据结构基础知识的理解，包括栈、队列、数组、二叉树的特性，以及如何利用这些知识解决实际问题。解答这些问题需要对数据结构的逻辑思维、算法设计以及对底层存储机制的理解。