武汉大学2010年攻读硕士学位研究生入学考试参考答案科目：数据结构科目代码：926一、判断题（每小题2分，共20分）1.错。这句话的前半句没有错，后半句错误，存储结构影响数据的处理效率。2.对。栈和队列都是受限的线性结构。3.对。这是链表的优点。4.错。二叉树中结点均没有左子结点的时候先序遍历与中序遍历相同。5.错。完全二叉树的叶子结点在最后两层上。6.对。7.错。邻接矩阵大小只与顶点数有关。邻接表的大小和顶点和边的个数都有关。8.对。在二叉平衡树中插入的新结点有可能不是叶子结点。9.错。N-1条弧段就可以了。10.错。当序列基本有序的时候简单排序比快速排序好。说明：本人有历年真题，答案，笔记。都是13年考研整理的，比较齐全。需要的可以加扣扣1277829363，或者在淘宝店铺中搜：为美好明天奋斗。二、选择题（每小题3分，共30分）1.D。由于每一层至少有一个结点，因此当每一层只有一个结点是能达到它的最大高度，即有多少个结点就有多少层。2.B。见课本第三章。3.D。将p的后继指针指向原来的首元结点，即头结点的后继指针，然后修改头结点的指针域指向p，即可完成插入操作。4.A。无向图中顶点的度数部分出度和入度，因此将被计算两次。5.A。由插入排序的定义可知。6.D。应先将栈顶结点的值赋给X，否则当栈顶元素被删除后将无从得到该元素的值。7.D。直接插入排序在序列基本有序的情况下进行的关键字比较的次数要小很多。快速排序时间复杂度与序列的有序情况有关，因此其关键字比较次数也不能脱离序列有序情况。起泡排序也类似。无论序列的情况怎么样，直接选择排序每一趟进行的关键字比较次数是一定的。8.B。将二叉链表中的空指针域当做叶子结点，非空指针域当做非叶子结点。由于二叉树中叶子结点的个数是非叶子结点个数＋1，因此空指针域属等于非空指针域数+1.9.D．顺序存储结构中在任意结点前插入一个元素所需移动结点数的平均次数=n*（n+1）/（2n）=（n+1）/210．A。由于这个图的邻接矩阵不对称，因此不可能是无向图，也不可能是完全图，由该矩阵对应的图可知该图不是强连通图，=1\*GB3①=2\*GB3②=3\*GB3③三、图表题（每小题4分，共40分）1.（1）=1\*GB3①=2\*GB3②=5\*GB3⑤=4\*GB3④=3\*GB3③（2）v1，v2，v4，v5，v32.（1）ABCDEFGHI（2）前序遍历序列为ABDEHCFIG3.终点I=1I=2I=3I=4I=5I=6V14(v0v1)V26(v0v2)5(v0v1v2)V36(v0v3)6(v0v3)6(v0v3)V411(v0v1v4)11(v0v1v4)11(v0v1v4)11(v0v1v4)V59(v0v1v2v5)9(v0v1v2v5)V617(v0v1v2v5v6)17(v0v1v2v5v6)ViV1V2V3V5V4V6SV0v1V0v1v2V0v1v2v3V0v1v2v3v5V0v1v2v3v4v5V0v1v2v3v4v5v64.ABCFDKGELHMIJ四、算法填空题（没空2分，共20分）1.（1）p！=NULL//while循环在p不为空的条件下进行采有意义。（2）p->link//p指向下一个结点，其地址已保存在q中（3）temp!=p->data//p指向下一个结点的条件是p不为空或者它的值和要查找的重复值不相等。（4）temp=p->data//当找到重复值时，进行删除操作（5）p=q->link;//当对某一个值的所有重复值删除结束时，对它下一个结点进行同样的操作。由于q记录的该结点的位置，因此用p指向其下一个结点的位置。2.（1）flag=0;//flag用来保存某一趟冒泡中交换元素的次数。因此在循环里应先将flag赋值为0，同时在flag可以用来判断是否还需要进行冒泡排序，即某一趟排序中没有元素进行交换时就序列就已经达到了有序，不需要再进行排序了。（2）flag++;//当有元素要交换位置时，将flag+1（3）j=I;//从前往后扫描的初始位置为i的位置（4）r.e[j]>r.e[j+1];//当前一个位置比后一个位置的值大时，需要进行元素位置的交换。（5）flag++;//理由同（2）