发布时间 : 星期日 文章专升本数据结构5年真题和详细解析更新完毕开始阅读f84d4f54b52acfc789ebc9da
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、评价算法好坏的五个方面_______________,_______________,正确性，可读性，健壮性。
四、操作计算题（10分，每题5分）
1、有一组关键字序列（24，19，56，13，97，59，41，85，1，87），写出用堆排序法进行升序排序的初始堆序列及第一趟排序后的堆序列。
1 2、给定如下图所示的带权无向图G1。
9 10 （1）画出该图的邻接矩阵
7 （2）给出采用普里姆算法从顶点3出发构造最小生成树的的过程。 2 3
5 6 7
4 5 8 11
五、算法设计题（10分）
给定二叉树，采用链式结构存储，编写算法void count(BitTree bt),实现功能：统计二叉树中度为1的结点数目。
6 2008年山东省专升本考试数据结构真题答
案及解析
一、单项选择题 1.【答案】C
【解析】p->next表示结点中存放的指针,该指针用来指向某个结点，原来的连接关系是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 = ?a1a2…an? (n>=0) 。零个字符的串称为空串，n为串的长度。串的元素ai可以是字母、数字或其他字符。 3.【答案】B
【解析】数组元素A[i,j]的地址为：Loc(A[i,j]) = L1 + (i-1)×U2 ×d ＋ （j－1）×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 n＝n1 +2n2＋1
n=80，为完全二叉树，说明度为1的结点只有1个，所以n2=39。 6.【答案】A
【解析】构造Huffman树的步骤：
① 对给定的n个权值按照非递减顺序排列，构造n棵只有一个结点的二叉树的集合F＝｛T1,T2,…Tn｝；
② 在F中选定两棵根结点的权值最小的两个二叉树作为左右子树，构造一棵新的二叉树，新的二叉树的根结点的权值设为其左右子树根结点的权值之和；
③ 从F中删除原来的两棵二叉树，同时将新二叉树插入其中； ④ 重复执行（2）和（3），直到F中剩余一棵二叉树，这棵树就是所求的Huffman树，结束。
根据构造步骤可知，Huffman树中只有度为0的叶子结点和度为2的新生成结点。 7.【答案】B
【解析】有向图G中弧数目的取值范围：0<= e <= n(n-1)。有n(n-1)条弧的有向图称为有向完全图。 8.【答案】A
【解析】折半查找（二分查找法）要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或降序）排列，也就是说折半查找只适用于对有序顺序表进行查找。有序顺序表
也称为有序表。 9.【答案】D 【解析】起泡排序是交换排序中一种简单的排序方法。它的基本思想是对所有相邻记录的关键字值进行比效，如果是逆序（a[j]>a[j+1]），则将其交换，最终达到有序化。其处理过程为：
1> 将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。
2> 对无序区从前向后依次将相邻记录的关键字进行比较，若逆序则将其交换，从而使得关键字值小的记录向上“飘浮”（左移），关键字值大的记录好像石块，向下“堕落”（右移）。每经过一趟冒泡排序，都使无序区中关键字值最大的记录进入有序区，对于由n个记录组成的记录序列，最多经过n-1趟冒泡排序，就可以将这n个记录重新按关键字顺序排列。 10.【答案】B
【解析】一个无环的有向图称做有向无环图（directed acycline praph）。简称DAG图。有向无环图是描述含有公共子式的表达式的有效工具。有向无环图的拓扑序列至少一个。 二、正误判断题 1.【答案】×
【解析】存储密度=数据域占的存储空间/整个结点占的存储空间。 2.【答案】×
【解析】单链表在保存时，一般在第一个结点之前辅设一个结点，称为头结点。头结点的数据域可以不存任何信息，也可以存储线性表的长度等附加信息，其指针域中存储指向第一个结点的指针（即第一个元素结点的存储位置）。故单链表的头指针指向头结点，如果头结点的指针域为空，则说明是空表。为了在第一个数据元素前面加入新元素或者删除第一个节点时头指针的值不变，在第一个数据元素前面要加一个所谓的头节点。 3.【答案】√
【解析】两个串相等的充要条件：两个串的长度相等，并且各个对应位置的字符都相等。 4.【答案】×
【解析】上、下三角矩阵元素个数为：1＋2＋3＋…＋n ＝ n(n+1)/2。因为取值为0的元素不必保存，则可用一个B[n(n+1)/2]的一维数组来保存上、下三角矩阵的非零值。
n阶对称方阵A中的元素满足下述条件：aij＝aji（1<=i,j<=n）。对称矩阵（方阵）中的每一对数据元素可以共用一个存储空间，因此可以将n2个元素压缩存储到n(n+1)/2个元的空间中，所以存储空间相同。
5.【答案】√
【解析】① 满二叉树：一棵深度为k，结点个数为2k-1的二叉树称为满二叉树。满二叉树是深度为k的结点数目最多的二叉树。
② 完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树一一对应时，称为完全二叉树。深度为k的完全二叉树结点个数范围：最小结点数：2k-1，最大结点数2k-1。
满二叉树一定是完全二叉树。 6.【答案】√
【解析】将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。一棵树转换成二叉树后，根结点没有右孩子。 7.【答案】×
【解析】二叉树的二叉链表表示法有n+1个空链。同时，二叉链表（或三叉链表）虽然能方便的找到当前结点的双亲结点或左、右子结点，但如果要求寻找当前结点的前驱结点或者后继结点（按照某种遍历方法），则上述方法就不方便了，只能在遍历过程中动态得到。如将二叉链表法中的n+1个空链利用起来，让其指向当前结点的前驱结点（如果指向左子树的指针域为空）或后继结点（如果指向右子树的指针域为空），则可解决以上问题，这就是线索二叉树提出的原因。 指向孩子的指针个数为n-1。
8.【答案】×
【解析】邻接矩阵法是图的一种顺序存储结构。设G有n个顶点，则可用n*n矩阵A（称为G的邻接矩阵，行标从1..n，列标从1..n）保存该有向图。
对无向图：如果vi，vj之间有边，则A的元素aij＝aji＝1，否则aij＝aji＝0；A为对称矩阵。
对有向图：如果vi有指向vj的弧，则A的元素aij＝1，否则aij＝0。 对带权图：如果vi，vj之间有边或者弧（vi指向vj），则A的元素aij＝wij，否则aij＝INFINITY。
利用邻接矩阵，可以判断任意两顶点之间是否有边（弧），并可方便求各顶点的度，图的边数等。例如：
对无向图：顶点vi的度TD(vi)是A中第i行（或者第i列）的元素之和。
对有向图：顶点vi的出度OD(vi)是第i行的的元素之和，入度ID(vi)第i列的元素之和。 对带权图：顶点vi的度的求法同上类似，但不再是求和，而是求行、列中不为零的元素个数。
9.【答案】√
【解析】矩阵主对角线以下的元素全部为0，即满足如下条件的矩阵。
aij = 0 , i >=j
如下图：
0000100011001110
该图为有向无环图，所以拓扑有序序列存在。 10.【答案】× 【解析】