专升本数据结构5年真题和详细解析讲解.doc

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.【答案】×【解析】广义表的深度定义为所含括弧的重数，所以深度应为34.【答案】×【解析】线性表、堆栈、队列都可认为是线性结构，树和二叉树都是树形结构，而图则属于图状结构5.【答案】√【解析】如图所示：6.【答案】×【解析】第i列非零元的个数表示的是第i个结点的入度，第i行非零元的个数表示的是第i个结点的出度7.【答案】×【解析】将递归算法转换为对应的非递归算法时，通常需要使用栈8.【答案】×【解析】在哈夫曼编码中，当两个字符出现的频率相同时，权重相同，但这两个字符的位置不同，所以其编码也不同9.【答案】×【解析】散列法存储的基本思想是由关键字的值决定数据的存储地址，也即是把关键字的值作为自变量，通过一定的函数（称为散列函数）计算出对应的函数值，把这个函数值解释为数据的存储地址，而不是直接把关键字的值作为数据的存储地址10.【答案】√【解析】是大顶堆。

二、填空题1.【答案】1100【解析】对下三角矩阵：（ i>=j ,考虑包括主对角线上的元素）行优先存储： k ＝ i(i-1)/2 + j - 1 ；所以地址为：1000+25*4=11002.【答案】69【解析】n ＝ n0 ＋ n1 ＋ n2 n0 = n2 + 1 所以n= 2*n0+ n1-1=40+30-1=693.【答案】69【解析】如下图所示，所以结果为：2*（6+7+8）+3*（4+5）=694.【答案】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的值如下： low的值修改，使其指向R[10]的下一个元素，即low＝mid＋1＝11; high不变，仍然是13 mid ＝ ë(low +high)/2û =12 则有R[mid]＝R[12]＝95第四步：由以上判断可知，如果记录中存在82，则一定在R[12]之前（同样因为R是非递减有序的）故修改low和high的值如下： high的值修改，使其指向R[12]的前一个元素，即high＝mid-1＝11; low不变，仍然是11 mid ＝ ë(low +high)/2û =11 则有R[mid]＝R[11]＝82查找成功三、【答案】（1）构造过程如下：（2）平均查找长度为：（1+2*2+3*4+4*3）/10=2.9四、【答案】　　已知指向这个结点的指针是p，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向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，则只要把表删空即可五、【答案】算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号下面是解决这个问题的完整算法。

typedef char StackEntry;int Check( ){STACK S; //定义栈结构Schar ch;InitStack(&S); //初始化栈Swhile ((ch=getchar())!=’\n’) { //以字符序列的形式输入表达式 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)) retrun 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=s B、q->next=s->next;s->next=qC、p->next=s;s->next=q D、q->next=s;s->next=p2、串是（ ）A、一些符号构成的序列 B、一些字母构成的序列C、一个以上的字符构成的序列 D、任意有限个字符构成的序列3、数组A[10][10]的下标下界为1，每个元素占2个字节，存储在起始地址为100的连续内存单元，则元素A[3][8]的地址为（ ）A、138 B、154 C、111 D、1454、已知广义表L=((x,y,z),a,(u,t,w)),则从L中取出原子项y的操作是（ ）A、head(tail(head(L))) B、head(head(tail(tai。