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

1、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. 将递归算法转换为对应的非递归算法时，通

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指向结点的前趋结点。五. （7分）设算术表达式由字符串

4、b表示，其中可以包括三种括号：圆括号、方括号和花括号，嵌套的顺序任意，如 ( ) ( ) 是正确的。请编写一个算法，实现判别给定表达式中所含括号是否正确配对。2007年山东省专升本考试数据结构真题答案及解析一、判断题1.【答案】【解析】顺序存储结构的特点：（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构

5、。2.【答案】【解析】考查堆栈“后进先出”的特点。第一个出栈元素是d，说明a、b、c已经入栈，因为a先于b进栈，所以必定在b之后出栈。3.【答案】×【解析】广义表的深度定义为所含括弧的重数，所以深度应为3。4.【答案】×【解析】线性表、堆栈、队列都可认为是线性结构，树和二叉树都是树形结构，而图则属于图状结构。5.【答案】【解析】如图所示：6.【答案】×【解析】第i列非零元的个数表示的是第i个结点的入度，第i行非零元的个数表示的是第i个结点的出度。7.【答案】×【解析】将递归算法转换为对应的非递归算法时，通常需要使用栈。8.【答案】×【解析】在哈

6、夫曼编码中，当两个字符出现的频率相同时，权重相同，但这两个字符的位置不同，所以其编码也不同。9.【答案】×【解析】散列法存储的基本思想是由关键字的值决定数据的存储地址，也即是把关键字的值作为自变量，通过一定的函数（称为散列函数）计算出对应的函数值，把这个函数值解释为数据的存储地址，而不是直接把关键字的值作为数据的存储地址。10.【答案】【解析】是大顶堆。二、填空题1.【答案】1100【解析】对下三角矩阵：（ i>=j ,考虑包括主对角线上的元素）行优先存储： k i(i-1)/2 + j - 1 ；所以地址为：1000+25*4=1100。2.【答案】69【解析】n n0 n1

7、 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 则有 Rmid=R7=45 > 82 第二步：由以上判断可知，如果记录中存在82，则一定在R7之后（因为R是非递减有序的）。故修改low和high如下： high值不变，仍然有high13； low的值修改：使其指向R7的后

8、一个元素，即使lowmid+1 8 ; 比较范围缩小至R8R13。 mid ë(low +high)/2û = 10 则有RmidR1077<82第三步：由以上判断可知，如果记录中存在82，则一定在R10之后（同样因为R是非递减有序的）。故修改low和high的值如下： low的值修改，使其指向R10的下一个元素，即lowmid111; high不变，仍然是13。 mid ë(low +high)/2û =12 则有RmidR1295。第四步：由以上判断可知，如果记录中存在82，则一定在R12之前（同样因为R是非递减有序的）。故修改low和high

9、的值如下： high的值修改，使其指向R12的前一个元素，即highmid-111; low不变，仍然是11。 mid ë(low +high)/2û =11 则有RmidR1182。查找成功。三、【答案】（1）构造过程如下：（2）平均查找长度为：（1+2*2+3*4+4*3）/10=2.9四、【答案】已知指向这个结点的指针是p，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向p的直接前趋，然后用后删结点法，将结点p的直接前趋结点删除即可。算法如下：void DeleteNode( ListNode *p)/删除单循环链表中指定结点的直接前趋结点Lis

10、tNode *s, *q;s=p;while( s->next->next!=p) s=s->next;/删除结点q=s->next;s->next=q->next;free(s); /释放空间注意：若单循环链表的长度等于1，则只要把表删空即可。五、【答案】算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。（1）当遇到某一个右括号时，栈

11、已空，说明到目前为止，右括号多于左括号；（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; /遇左括号入栈

12、 /在遇到右括号时，分别检测匹配情况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 (

13、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-&g

14、t;next=p2、串是（ ）A、一些符号构成的序列 B、一些字母构成的序列C、一个以上的字符构成的序列 D、任意有限个字符构成的序列3、数组A1010的下标下界为1，每个元素占2个字节，存储在起始地址为100的连续内存单元，则元素A38的地址为（ ）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(tail(tail(L)C、head(tail(tail(tail(tail(L) D、head(tail(tail(head(tail(L

15、)5、已知完全二叉树有80个结点，则整个二叉树有_个度为2的结点。（ ）A、39 B、41 C、40 D、386、赫夫曼树中度为1的结点个数为（ ）A、0 B、1 C、2 D、不确定7、具有n个顶点的有向完全图，边的总数为（ ）A、n B、n(n-1) C、n-1 D、n(n-1)/28、二分查找法适用于存储结构为_的，且按关键字排好序的线性表。（ ）A、顺序存储 B、链接存储 C、顺序存储或链接存储 D、索引存储9、下列排序算法中，第一趟排序结束后，其最大或最小元素一定在其最终位置上的算法是（ ）A、归并排序 B、直接插入排序 C、快速排序 D、起泡排序10、一个有向无环图的拓扑序列个数是（

16、 ）A、1个 B、1个或多个 C、0个 D、多个二、正误判断题（10分，正确打，错误打×，每小题1分）1、链表中结点数据域占的存储空间越多，存储密度越小。（ ）2、带头结点和不带头结点的单链表在查找、删除、求长度等操作上无区别。（ ）3、如果两个串串长相等且对应字符也相同，则这两个串相等。（ ）4、压缩存储的三角矩阵和对称矩阵的存储空间不相同。（ ）5、满二叉树是完全二叉树。（ ）6、对于给定的树，与其对应的二叉树是唯一的。（ ）7、线索二叉树的指针域中，指向前驱或后继的个数少于指向孩子的个数。（ ）8、给定图的邻接矩阵存储不一定唯一。（ ）9、若一个有向图的邻接矩阵主对角线以下的元

17、素均为0，则该图拓扑有序序列存在。（ ）10、对n个记录进行直接插入排序，其平均时间复杂度为O(nlog2n）。（ ）三、填空题（10分，1题每空2分，其他题每空1分）1、下列函数的功能是实现带头结点的单链表逆置。void turn(slink *L)slink *p,*q; p=_;L->next=NULL;while(_)q=p;p=_;q->next=L->next;L->next=q; 2、“算法”（Algorithm）就是对求解问题步骤的一种描述，也称为算法设计。它具有以下五个特征有穷性，_,_，输入和输出。3、评价算法好坏的五个方面_,_,正确性，可读性，健

18、壮性。四、操作计算题（10分，每题5分）1、有一组关键字序列（24，19，56，13，97，59，41，85，1，87），写出用堆排序法进行升序排序的初始堆序列及第一趟排序后的堆序列。2、给定如下图所示的带权无向图G1。（1）画出该图的邻接矩阵（2）给出采用普里姆算法从顶点3出发构造最小生成树的的过程。五、算法设计题（10分）给定二叉树，采用链式结构存储，编写算法void count(BitTree bt),实现功能：统计二叉树中度为1的结点数目。2008年山东省专升本考试数据结构真题答案及解析一、单项选择题1.【答案】C【解析】p->next表示结点中存放的指针,该指针用来指向某个结点

19、，原来的连接关系是p->next=q，意思是p中存放的指针的值是q，即p指向q。插入的意思,打个比方，原来排队q在p的后面,现在要插一个s在他们中间，需要做的事就是把原来p，q二人的联系转化为p，s，q三人的联系，先让p指向s，即p->next=s；然后让s指向q，即s->next=q。2.【答案】D【解析】串是由零个或多个字符组成的有限序列，一般记为：s = a1a2an (n>=0) 。零个字符的串称为空串，n为串的长度。串的元素ai可以是字母、数字或其他字符。3.【答案】B【解析】数组元素Ai,j的地址为：Loc(Ai,j) = L1 + (i-1)×U

20、2 ×d （j1）×d。4.【答案】A【解析】L=(x,y,z),a,(u,t,w)，head(L)= (x,y,z)，tail(head(L)= (y,z)，head(tail(head(L)=y。5.【答案】A【解析】n n0 n1 n2 n0 = n2 + 1 nn1 +2n21 n=80，为完全二叉树，说明度为1的结点只有1个，所以n2=39。6.【答案】A【解析】构造Huffman树的步骤： 对给定的n个权值按照非递减顺序排列，构造n棵只有一个结点的二叉树的集合FT1,T2,Tn； 在F中选定两棵根结点的权值最小的两个二叉树作为左右子树，构造一棵新的二叉树，新的二

21、叉树的根结点的权值设为其左右子树根结点的权值之和； 从F中删除原来的两棵二叉树，同时将新二叉树插入其中； 重复执行（2）和（3），直到F中剩余一棵二叉树，这棵树就是所求的Huffman树，结束。 根据构造步骤可知，Huffman树中只有度为0的叶子结点和度为2的新生成结点。7.【答案】B【解析】有向图G中弧数目的取值范围：0<= e <= n(n-1)。有n(n-1)条弧的有向图称为有向完全图。8.【答案】A【解析】折半查找（二分查找法）要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或降序）排列，也就是说折半查找只适用于对有序顺序表进行查找。有序顺序表也称为有序表。9.

22、【答案】D【解析】起泡排序是交换排序中一种简单的排序方法。它的基本思想是对所有相邻记录的关键字值进行比效，如果是逆序（aj>aj+1），则将其交换，最终达到有序化。其处理过程为：1> 将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。2> 对无序区从前向后依次将相邻记录的关键字进行比较，若逆序则将其交换，从而使得关键字值小的记录向上“飘浮”（左移），关键字值大的记录好像石块，向下“堕落”（右移）。每经过一趟冒泡排序，都使无序区中关键字值最大的记录进入有序区，对于由n个记录组成的记录序列，最多经过n-1趟冒泡排序，就可以将这n个记录重新

23、按关键字顺序排列。10.【答案】B【解析】一个无环的有向图称做有向无环图（directed acycline praph）。简称DAG图。有向无环图是描述含有公共子式的表达式的有效工具。有向无环图的拓扑序列至少一个。二、正误判断题1.【答案】×【解析】存储密度=数据域占的存储空间/整个结点占的存储空间。2.【答案】×【解析】单链表在保存时，一般在第一个结点之前辅设一个结点，称为头结点。头结点的数据域可以不存任何信息，也可以存储线性表的长度等附加信息，其指针域中存储指向第一个结点的指针（即第一个元素结点的存储位置）。故单链表的头指针指向头结点，如果头结点的指针域为空，则说明是

24、空表。为了在第一个数据元素前面加入新元素或者删除第一个节点时头指针的值不变，在第一个数据元素前面要加一个所谓的头节点。3.【答案】【解析】两个串相等的充要条件：两个串的长度相等，并且各个对应位置的字符都相等。4.【答案】×【解析】上、下三角矩阵元素个数为：123n n(n+1)/2。因为取值为0的元素不必保存，则可用一个Bn(n+1)/2的一维数组来保存上、下三角矩阵的非零值。n阶对称方阵A中的元素满足下述条件：aijaji（1<=i,j<=n）。对称矩阵（方阵）中的每一对数据元素可以共用一个存储空间，因此可以将n2个元素压缩存储到n(n+1)/2个元的空间中，所以存储空

25、间相同。5.【答案】【解析】 满二叉树：一棵深度为k，结点个数为2k-1的二叉树称为满二叉树。满二叉树是深度为k的结点数目最多的二叉树。 完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树一一对应时，称为完全二叉树。深度为k的完全二叉树结点个数范围：最小结点数：2k-1，最大结点数2k-1。满二叉树一定是完全二叉树。6.【答案】【解析】将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了

26、。一棵树转换成二叉树后，根结点没有右孩子。7.【答案】×【解析】二叉树的二叉链表表示法有n+1个空链。同时，二叉链表（或三叉链表）虽然能方便的找到当前结点的双亲结点或左、右子结点，但如果要求寻找当前结点的前驱结点或者后继结点（按照某种遍历方法），则上述方法就不方便了，只能在遍历过程中动态得到。如将二叉链表法中的n+1个空链利用起来，让其指向当前结点的前驱结点（如果指向左子树的指针域为空）或后继结点（如果指向右子树的指针域为空），则可解决以上问题，这就是线索二叉树提出的原因。 指向孩子的指针个数为n-1。8.【答案】×【解析】邻接矩阵法是图的一种顺序存储结构。设G有n个顶点，

27、则可用n*n矩阵A（称为G的邻接矩阵，行标从1.n，列标从1.n）保存该有向图。对无向图：如果vi，vj之间有边，则A的元素aijaji1，否则aijaji0；A为对称矩阵。对有向图：如果vi有指向vj的弧，则A的元素aij1，否则aij0。对带权图：如果vi，vj之间有边或者弧（vi指向vj），则A的元素aijwij，否则aijINFINITY。利用邻接矩阵，可以判断任意两顶点之间是否有边（弧），并可方便求各顶点的度，图的边数等。例如：对无向图：顶点vi的度TD(vi)是A中第i行（或者第i列）的元素之和。对有向图：顶点vi的出度OD(vi)是第i行的的元素之和，入度ID(vi)第i列的元素

28、之和。对带权图：顶点vi的度的求法同上类似，但不再是求和，而是求行、列中不为零的元素个数。9.【答案】【解析】矩阵主对角线以下的元素全部为0，即满足如下条件的矩阵。aij = 0 , i >=j 如下图： 该图为有向无环图，所以拓扑有序序列存在。10.【答案】×【解析】排序方法平均时间稳定性直接插入排序O（n2）稳定折半插入排序O（n2）稳定起泡排序O（n2）稳定直接选择排序O（n2）不稳定希尔排序O（n1.3）不稳定快速排序O（nlog2n）不稳定堆排序O（nlog2n）不稳定2-路归并排序O（nlog2n）稳定基数排序O(d*(rd+n)稳定三、填空题1.【答案】p=L-&

29、gt;next p!=null p=p->next【解析】逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。2.【答案】确定性 可行性3.【答案】时间效率 空间效率四、操作计算题1.【答案】(1)建小堆 所以初始堆序列为：（1，13，41，19，87，59，56，85，61，97） (2)第一趟排序后的堆序列  第一趟排序后的堆序列为：（1，13，19，41，61，87，59，56，85，97）2.【答案】(1) (2)说明：第三步答案不唯一。五、算法设计题void count(BitTree bt) int i=0; if(bt=NULL) b

30、reak; else if(bt->lchild=0&& bt->rchild!=0| bt->lchild!=0&& bt->rchild=0) i+; else i+=count(bt->lchild); i+=count(bt->rchild);printf(“%d”,i);2009年山东省专升本考试数据结构真题一、填空题（10分，每空0.5分）1、根据数据元素之间关系的不同，数据的逻辑结构划分为_、_、_、_。2、栈是一种特殊的线性表，它允许在表的一端进行_操作，栈中元素的进出原则为_。3、 深度为k的二叉树其结点数最

31、多有_个结点。4、通常象交通、道路问题的数学模型是一种称为_的数据结构。5、算法的五个重要的特征是_、_、_、_、_。6、两个字符串相等的充分必要条件是_。7、在一棵二叉树中，度为零的结点个数为，度为2的结点个数为，则有=_。8、树的度是指_的最大值。9、在一个有向图中，某个结点的度是指该结点的_和_之和。10、在线性表的二分查找法中要求线性表的存储结构必须是采用_，且表中的元素必须是_。二、选择题（10分，每题1分）1. 一个具有10个顶点的无向完全图应有_条边。 ( )A. 9B. 45C. 55D. 902. 长度为n（1n）的顺序循环队列中，front和rear分别指示队首和对尾，判断

32、队列为满队列的条件是 ( )A. rear=frontB. (rear+1)%n=frontC. rear=0 D. front=03. 由_组成的集合是一个数据对象。 ( )A. 不同类型的数据项B. 不同类型的数据元素C. 相同类型的数据项D. 相同类型的数据元素4. _是表示线性数据结构的。 ( )A. 循环链表B. 邻接多重表C. 孩子链表D. 单链表5. 设一个栈的入栈元素序列为a，b，c，d，e，则不可得到出栈的元素序列有( )。A. edcbaB. decbaC. dceabD. abcde6. _又是一棵满二叉树。( )A. 二叉排序树B. 深度为5有31个结点的二叉树C. 有

33、15个结点的完全二叉树D. 哈夫曼（Huffman）树7. 折半查找有序表（2，5，8，20，25，36，40，60），若查找元素60，需依次与表中元素_进行比较。( )A. 20，36，40，60B. 25，40C. 25，40，60D. 20，36，408. 查找哈希（Hash）表，解决冲突的方法有( )。A. 链地址法B. 线性探测再散列法C. 直接地址法D. 除留余数法9. 一个排序算法时间复杂度的大小_有关。( )A. 不与所需移动记录的数目B. 与该算法的稳定性C. 与所需比较关键字的次数D. 与所需辅助存储空间的大小10. 数据的基本单位是 。( )A. 结点B. 数据元素C.

34、数据类型D. 数据项三、求解下列问题（10分，每题5分）1. 将下面的一个普通书转换成一棵二叉树，并写出它先序、中序、后序三种遍历的遍历序列。转换后的二叉树：先序遍历序列：中序遍历序列：后序遍历序列：2. 用克鲁斯卡尔算法将下面的图构造成最小生成树，画出生成过程。四、程序填空（10分，每空1分）1.将下面折半查找算法补充完整算法说明：已知r1n是n个记录的递增有序表，用折半查找法查找关键字为k的记录，若查找失败返回零；否则返回该记录的序号值。查找表顺序存储结构定义如下：#define MAXSIZE100typedefstructkeytypekey;Nodetype;typedefNodet

35、ype SqlistMAXSIZE;算法（C函数）：intbinsearch (Sqlist r, datatype k, int n)int low = 1, high = n, mid;while (_)_;if (rmid.key= =k)_;else if (rmid.key>k)_else_return (0);2. 将下面单链表的插入算法补充完整。算法说明：在带有头结点的单链线性表中第i个位置之前插入元素x :typedef _DataType data;struct node *next;LNode, *LinkList;int listinsert (LinkList h

36、ead, int i, DataType x)LinkList p = head.sint j = 0;while (p!=NULL&&j<i-1)_;j+;if (p= = NULL) return (0);s = _malloc (sizeof (LNode) );s->data = x;_;_;return (1);五、算法设计（10分）已知S为顺序栈。写出S的存储结构类型描述。编写算法实现将元素x入栈操作Push (S, x)，入栈成功返回1，否则返回0和删除栈顶元素的出栈操作Pop (S) 出栈成功返回1，否则返回0。2009年山东省专升本考试数据结构真题

37、答案及解析一、填空题1.【答案】集合、线性结构、树形结构、图状结构或网状结构【解析】根据数据元素之间的关系，有四类基本的结构： 集合（元素之间无密切关系）； 线性结构（元素之间有一个对一个的关系（1:1）； 树形结构（元素之间有一个对多个（1:n）的关系； 图状结构或网状结构（元素之间有多个对多个（n:m）的关系） (b) 线性结构 (c) 树形结构 (d) 图状结构 (a) 集合其中数据元素之间的关系见下图所示。2.【答案】插入或删除 后进先出【解析】堆栈是一种特殊的线性表，它的操作被限制在某一端，即栈顶。若有一个栈S=（a1, a2 , an）称a1为栈底结点，an为栈顶结点。习惯上称插入

38、结点为入栈(压栈，进栈)，删除结点成为出栈（弹栈）。最先进栈的结点必定最后出栈，最后进栈的结点必定最先出栈，因此，栈是一种具有后进先出特性的数据结构。3.【答案】2 k-1【解析】深度为k的二叉树至多有2 k-1(k>=1)个结点。证明： 从第1层到第k层，二叉树每层的最大结点数分别为：1、2、22、23、2k-1,该数列为等比数列，第一项为a11，公比q2，项数为k，利用等比数列求和公式得：4.【答案】图状或网状5.【答案】有穷性；确定性；可行性；输入；输出。6.【答案】两个串的长度相等，并且各个对应位置的字符都相等。7.【答案】n2 +1【解析】假设二叉树中度为1的结点个数为n1，结

39、点总数为n。因为二叉树中任何结点的度最大不超过2，因此有：n n0 n1 n2 （1）从另一个角度看，我们来研究二叉树的分支数。对所有结点来说，除了根结点，任何其余结点都有一个分支进入（指向）。不妨设B（Branch）为二叉树的分支数，则有： Bn1 （分支数比结点数少1） （2）而分支是由度为1的结点和度为2的结点贡献的：每个度为1的结点贡献1个分支，每个度为2的结点贡献2个分支。则有：Bn1×1n2×2n1 +2n2。 （3）由（2）、（3）得nn1 +2n21 （4）由（1）、（4）得n0 = n2 + 1 由此得出结论：二叉树叶子结点个数总是比度为2的结点个数多1。

40、8.【答案】树中所有结点度9.【答案】出度 入度10.【答案】顺序 关键字有序（升序或降序）排列【解析】折半查找（二分查找法）要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或降序）排列，也就是说折半查找只适用于对有序顺序表进行查找。有序顺序表也称为有序表。二、选择题1.【答案】B【解析】无向图G中边数目的取值范围：0<=e<=n(n-1)/2。有n(n-1)/2条边的无向图称为完全图。n(n-1)/2=10*9/2=45。2.【答案】B3.【答案】D【解析】线性表是由相同类型的结点组成的有限序列。如：由n个结点组成的（ a1, a2, , an）a1是最前结点，an是最

41、后结点。结点也称为数据元素或者记录。4.【答案】D【解析】线性表、堆栈、队列都可认为是线性结构。5.【答案】C【解析】考查堆栈“后进先出”的特点。对选项C来说，第一个出栈元素是d，则必有c、b、a三个元素依次在3后面出栈，但是选项C中的顺序是dceab,这是不符合要求的，因此答案选C。6.【答案】B【解析】一棵深度为k，结点个数为2k-1的二叉树称为满二叉树。7.【答案】A【解析】第一步： 设low指向首元素（赋值为1），high指向尾元素（赋值为8），计算下边中值得： mid ë(low +high)/2û = 4 则有 Rmid=R4=20 > 60 第二步：由以

42、上判断可知，如果记录中存在60，则一定在R4之后（因为R是非递减有序的）。故修改low和high如下： high值不变，仍然有high8； low的值修改：使其指向R4的后一个元素，即使lowmid+1 5 ; 比较范围缩小至R5R8。 mid ë(low +high)/2û = 6 则有RmidR636<60第三步：由以上判断可知，如果记录中存在60，则一定在R6之后（同样因为R是非递减有序的）。故修改low和high的值如下： low的值修改，使其指向R6的下一个元素，即lowmid17; high不变，仍然是8。 mid ë(low +high)/2&

43、#251; =7 则有RmidR740。第四步：由以上判断可知，如果记录中存在60，则一定在R7之后（同样因为R是非递减有序的）。故修改low和high的值如下： low的值修改，使其指向R7的下一个元素，即lowmid18; high不变，仍然是8。 mid ë(low +high)/2û =8 则有RmidR860。查找成功。8.【答案】A【解析】处理冲突的方法 开放定址法：从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生了冲突的待插入元素存到该单元中。重新确定地址的方法为： Hi （H(key) + di）% m i=1,2,.k

44、(k<=m-1)其中：H(key)为哈希函数；m为哈希表的长度；di为增量序列，可有三种取法，对应三种方法： 1> 线性探测再散列：di 1,2,3,.m-1；（容易产生“二次聚集”） 2> 二次探测再散列：di 12 ，12，22，22，32，32，.，±k2（k<=m/2）； 3> 伪随机探测再散列：di伪随机数序列。 再哈希法：Hi RHi（key） ， i=1,2,3,.k，RHi都是不同的哈希函数，即在同义词发生地址冲突时利用另一个哈希函数计算地址，直到冲突不再发生。这种方法不易产生“二次聚集”，但增加了计算时间。 链地址法：将所有关键字为同义

45、词的记录存储在同一线性链表中。 建立一个公共溢出区。9.【答案】C【解析】评价排序算法的效率主要有两点：一是在数据量规模一定的条件下，算法执行所消耗的平均时间，对于排序操作，时间主要消耗在关键字之间的比较和数据元素的移动上，因此我们认为，高效率的排序算法应该是尽可能少的比较次数和尽可能少的数据元素移动次数；二是执行算法所需要的辅助存储空间，辅助存储空间是指在数据量规模一定的条件下，除了存放待排序数据元素占用的存储空间之外，执行算法所需要的其他存储空间，理想的空间效率是算法执行期间所需要的辅助空间与待排序的数据量无关。10.【答案】B【解析】数据元素：是数据集合中的一个实体，是计算机程序中加工处

46、理的基本单位。数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。三、求解下列问题1. 【答案】（1）转换后的二叉树：（2）先序遍历序列：A B C D F E G H I J K L M（3）中序遍历序列：C F D E B J I L K M H G A（4）后序遍历序列：F E D C J M L K I H G B A2. 【答案】四、程序填空1.【答案】low <= high mid = (low + high)/2; return mi

47、d ; high = mid -1 ; low = mid + 1 ;【解析】折半查找的基本思想是：首先以整个查找表作为查找范围，用查找条件中给定值k与中间位置结点的关键字比较，若相等，则查找成功;否则，根据比较结果缩小查找范围，如果k的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；若k的值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在右半部分子表中，所以应该继续对右子表进行折半查找。每进行一次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围

48、缩小为空即查找失败为止。2.【答案】struct LNode p=p->next; (LinkList) s->next=p->next; p->next=s;五、算法设计#define MAX_STACK 10 /栈的最大数据元素数目typedef struct stackStackEntry itemMAX_STACK; /存放栈中数据元素的存储单元int top; /栈顶指针STACK;入栈 int Push(STACK *S,StackEntry x) flag=1; if (S->top=MAX_STACK-1) flag=0; else S->i

49、tem+S->top=x; return flag;出栈 void Pop(STACK *S) flag=1; StackEntry x;if (StackEmpty(*S) flag=0; else x=S->itemS->top-;return flag;2010年山东省专升本考试数据结构真题一、判断题（每小题1分，共5分）1.算法的执行时间和所需的存储空间都是问题规模的函数，进行算法分析就是要找出这种函数关系。（ ）2.完全二叉树只能采用顺序存储方法，不能采用链表存储方法。（ ）3.在顺序循环队列的第i个元素之后插入一个元素是顺序循环队列的基本运算。（ ）4.若一个叶子

50、是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历的最后一个结点。（ ）5.直接插入排序的关键码比较次数与初始排列有关。（ ）二、单项选择题（每小题2分，共10分）1.以下数据结构中哪一个是线性结构（ ） A.栈 B.线索二叉树 C.AOV网 D.二叉排序树2.若有a，b，c三个字符的字符序列执行入栈操作，则其所有可能的输出排列共有（ ） A.4种 B.5种 C.6种 D.其它3.一棵树的广义表表示为a(b,c(e,f(g),d)，当用左孩子右兄弟链表表示时，右指针域非空的节点个数为（ ） A.1 B.2 C.3 D.44.下面关于图的存储的叙述中正确的是（ ）A.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关B.用邻接矩阵法存