《专升本数据结构5年真题和详细解析》由会员分享，可在线阅读，更多相关《专升本数据结构5年真题和详细解析（44页珍藏版）》请在金锄头文库上搜索。
1、2007 年山东省专升本考试数据结构真题一、判断题（10分。本大题共10小题，每小题1分，在小题左面用“表示是，X表示否）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. 将递归算法转换为对应的非递归算法时，通常需要使
2、用队列。（ ）8. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同。（ ）9. 散列法存储的基本思想是由关键字的值决定数据的存储地址。（ ）10. （101，88，46，70，34，39，45，58，66，10）是堆。（）二、填空题（15分。本大题共5小题， 5个空，每个空3分，将正确答案填在空格处） 。1. 将下三角矩阵 A1.8, 1.8的下三角部分逐行地存储到起始地址为1000 的内存单元中，已知每个元素占4个单元，则A7, 5的地址为。2. 若某二叉树有 20 个叶结点，有 30 个只有一个孩子的结点，则该二叉树的总结点数为。3. 如果以4，5，6，7，8作为叶子结点的权值构
3、造哈夫曼树，则其带权路径长度是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指向结点的前趋结点。五. (
4、7分)设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号和花括号，嵌套的顺序任意，如 ( ) ( ) 是正确的。请编写一个算法，实现判别给定表达式中 所含括号是否正确配对。2007 年山东省专升本考试数据结构真题答案及解析一、判断题1. 【答案】V【解析】顺序存储结构的特点：（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表 的逻辑结构与存储结构（物理结构）一致；（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元 素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存 取元素的方法被称为随机存取法，使用
5、这种存取方法的存储结构被称为随机存储结构。2. 【答案】V【解析】考查堆栈“后进先出”的特点。第一个出栈元素是d,说明a、b、c已经入栈，因 为a先于b进栈，所以必定在b之后出栈。3. 【答案】X【解析】广义表的深度定义为所含括弧的重数，所以深度应为3。4. 【答案】X【解析】线性表、堆栈、队列都可认为是线性结构，树和二叉树都是树形结构，而图则属于图状结构。5. 【答案】V【解析】如图所示：6. 【答案】X【解析】第i列非零元的个数表示的是第i个结点的入度，第i行非零元的个数表示的是 第i个结点的出度。7. 【答案】X【解析】将递归算法转换为对应的非递归算法时，通常需要使用栈。8. 【答案】X
6、【解析】在哈夫曼编码中，当两个字符出现的频率相同时，权重相同，但这两个字符的位 置不同，所以其编码也不同。9. 【答案】X解析】散列法存储的基本思想是由关键字的值决定数据的存储地址，也即是把关键字的值作为自变量，通过一定的函数（称为散列函数）计算出对应的函数值，把这个函数值解释为数据的存储地址，而不是直接把关键字的值作为数据的存储地址。10.【答案】V解析】是大顶堆。二、填空题1.【答案】1100【解析】对下三角矩阵：（ i=j ,考虑包括主对角线上的元素）行优先存储：k = i（i-l）/2 + j - 1 ；所以地址为：1000+25*4=1100。2.【答案】69【解析】n = n0 +
7、 n1 + n2n0 = n2+ 1所以 n= 2*n0+ n1-1=40+30-1=693.【答案】69+3*（4+5）=692 k -1 j 82第二步：由以上判断可知，如果记录中存在82，则一定在R7之后(因为R是非递减 有序的)。故修改low和high如下：high值不变，仍然有high=13；low的值修改：使其指向R7的后一个元素，即使low=mid+l = 8 ; 比较范围缩小至R8R13。兀素下标12345678910 11121313912324145627595100元素关键字/ 82tif1low=8miid=10high=13mid=L(low+high)/2 = 10
8、则有 Rmid=R10=7782第三步：由以上判断可知，如果记录中存在82,则一定在R10之后(同样因为R是非 递减有序的)。故修改low和high的值如下：元素下标12345678910111213元素关键字139123241456275778295100low的值修改，使其指向R10的下一个元素，即low=mid+1 = 11; high不变，仍然是13。mid = L(low +high)/2=12则有 Rmid=R12=95。第四步：由以上判断可知，如果记录中存在82,则一定在R12之前(同样因为R是非递减有序的)。故修改low和high的值如下:元素下标1元素关键字 13456791
9、232414589627510111277829513100high=llhigh的值修改，使其指向R12的前一个元素，即high=mid-1 = 11; low不变，仍然是11。mid= L(low +high)/2 =11则有Rmid=R11=82。查找成功。三、【答案】(1)构造过程如下:464646575757327346464657573232573215157373734646573257843648847373(2)平均查找长度为：(1+2*2+3*4+4*3)/10=2.9四、【答案】已知指向这个结点的指针是p,那么要删除这个结点的直接前趋结点，就只要找到一个 结点，它的指针域
10、是指向p的直接前趋，然后用后删结点法，将结点p的直接前趋结点删除 即可。算法如下：void DeleteNode( ListNode *p)/删除单循环链表中指定结点的直接前趋结点ListNode *s, *q;s=p;while( s-next-next!=p)s=s-next;/删除结点q=s-next;s-next=q-next;free(s); /释放空间注意：若单循环链表的长度等于1，则只要把表删空即可。五、【答案】算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且 每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左 括号，当遇
11、到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几 种情况之一，就可以得出括号不匹配的结论。(1)当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；(2)从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；(3) 算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。 下面是解决这个问题的完整算法。typedef char StackEntry;int Check( )STACK S;定义栈结构Schar ch;InitStack(&S);/初始化栈 Swhile (ch=getchar()!=n) /以字符序列的形式输入表达
12、式switch (ch) case (ch=(|ch= |ch= ): Push(&S,ch);break; /遇左括号入栈/在遇到右括号时，分别检测匹配情况case (ch= ): if (StackEmpty(S) retrun FALSE;else Pop(&S,&ch);if (ch!= () return FALSE; break;case (ch= ): if (StackEmpty(S) retrun FALSE;else Pop(&S,&ch);if (ch!= ) return FALSE; break;case (ch= ): if (StackEmpty(S) retru
13、n FALSE;else Pop(&S,&ch);if (ch!= ) return FALSE; break;default:break;if (StackEmpty(S) return TRUE;else return FALSE;2008 年山东省专升本考试数据结构真题一、单项选择题（10分、每题1分）1、在一个单链表，已知p所指向的是q所指向结点的前驱结点，若在q和p之间插入 s 所指向的结点，则执行（ ）A、s-next=q-next;q-next=sC、 p-next=s;s-next=q2、串是( )A、一些符号构成的序列B、q-next=s-next;s-next=qD、 q-next=s;s-next=pB、一些字母构成的序列C、一个以上的字符构成的序列D、任意有限个字符构成的序列3、数组A1010的下标下界为1,每个元素占2个字节，存储在起始地址为100的连 续内存单元，则元素A3的地址为（）A、138 B、 154 C、 111 D、 145
