2007年山东省专升本考试数据结构真题
一、判断题（10分。本大题共10小题，每小题1分，在小题左面用√表示是，×表示否）
1. 线性表的顺序存储结构是一种随机存储结构。（  ）
2. 一个栈的入栈序列是a, b, c, d, e，则dceab是一个不可能的输出序列。（  ）
3. 广义表 (a, (a,b), d, e, ((i, j), k)) 的深度是2。（  ）
4. 树是一种重要的线性数据结构。（  ）
5. 按照二叉树的定义，具有三个结点的二叉树有5种。（  ）
6. 已知一个有向图的邻接矩阵表示，计算第i个结点的出度的方法是求矩阵第i列非零元的个数。（  ）
7. 将递归算法转换为对应的非递归算法时，通常需要使用队列。（  ）
8. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同。（  ）
9. 散列法存储的基本思想是由关键字的值决定数据的存储地址。（  ）
10. （101，88，46，70，34，39，45，58，66，10）是堆。（  ）
二、填空题（15分。本大题共5小题，5个空，每个空3分，将正确答案填在空格处）。
1. 将下三角矩阵A[1..8, 1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7, 5]的地址为___________。
2. 若某二叉树有20个叶结点，有30个只有一个孩子的结点，则该二叉树的总结点数为___________。
3. 如果以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是___________。
4. 在顺序存储的二叉树中，编号为i和编号为j的结点处在同一层的条件是___________。
5. 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查值为82的结点时，___________次比较后查成功。
三、（10分）已知关键字序列为{46，57，84，32，73，36，15，48，90，20}，要求：
（1）构造一棵二叉排序树；
（2）在等概率情况下，该二叉排序树查成功的平均查长度。
四、（8分）假设在长度大于1的循环链表中，既无头结点，也无头指针，p为指向该链表中某个结点的指针。设计一个算法，删除p指向结点的前趋结点。
五. （7分）设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号和花括号，嵌套的顺序任意，如{ [ ( ) ] ( ) }是正确的。请编写一个算法，实现判别给定表达式中所含括号是否正确配对。
2007年山东省专升本考试数据结构真题答案及解析
一、判断题
1.【答案】√
【解析】顺序存储结构的特点：
（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；
（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。
2.【答案】√
【解析】考查堆栈“后进先出”的特点。第一个出栈元素是d，说明a、b、c已经入栈，因为a先于b进栈，所以必定在b之后出栈。
3.【答案】×
【解析】广义表的深度定义为所含括弧的重数，所以深度应为3。
4.【答案】×
【解析】线性表、堆栈、队列都可认为是线性结构，树和二叉树都是树形结构，而图则属于
图状结构。
5.【答案】√
【解析】如图所示：
6.【答案】×
【解析】第i列非零元的个数表示的是第i个结点的入度，第i行非零元的个数表示的是第i个结点的出度。
7.【答案】×
【解析】将递归算法转换为对应的非递归算法时，通常需要使用栈。
8.【答案】×
【解析】在哈夫曼编码中，当两个字符出现的频率相同时，权重相同，但这两个字符的位置不同，所以其编码也不同。
9.【答案】×
【解析】散列法存储的基本思想是由关键字的值决定数据的存储地址，也即是把关键字的值作为自变量，通过一定的函数（称为散列函数）计算出对应的函数值，把这个函数值解释为数据的存储地址，而不是直接把关键字的值作为数据的存储地址。
10.【答案】√
【解析】是大顶堆。
二、填空题
1.【答案】1100
【解析】对下三角矩阵：（ i>=j ,考虑包括主对角线上的元素）
行优先存储：  k ＝ i(i-1)/2 + j - 1 ；
所以地址为：1000+25*4=1100。
2.【答案】69
【解析】n ＝ n0 ＋ n1 ＋ n2
            n0 = n2 + 1
        所以n= 2*n0+ n1-1=40+30-1=69
3.【答案】69
【解析】如下图所示，所以结果为：2*（6+7+8）+3*（4+5）=69
4.【答案】
5.【答案】4
【解析】               
第一步：
        设low指向首元素（赋值为1），high指向尾元素（赋值为13），计算下边中值得：
                mid ＝ (low +high)/2 = 7 二叉树公式
          则有  R[mid]=R[7]=45 > 82
第二步：由以上判断可知，如果记录中存在82，则一定在R[7]之后（因为R是非递减有序的）。故修改low和high如下：
          high值不变，仍然有high＝13；
          low的值修改：使其指向R[7]的后一个元素，即使low＝mid+1 ＝ 8 ;
          比较范围缩小至R[8]～R[13]。
      mid ＝ (low +high)/2 = 10
      则有R[mid]＝R[10]＝77<82
第三步：由以上判断可知，如果记录中存在82，则一定在R[10]之后（同样因为R是非递减有
序的）。故修改low和high的值如下：   

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。