）的最短简单路径，应采用深度优先遍历还是广度优先遍历？简述原因。3、分析冒泡排序的性能（最好情况、最坏情况）。
三、构造结果每小题6分，共30分1、已知一棵二叉树的前序遍历的结果是ABDCEGF，中序遍历的结果是BDAEGCF，试画出这课二叉树，并将其转换为相应的森林。2、假设T是一棵高度为5的二叉树，T中只有度为0和度为2的结点，给出：（1）T树可能的最大结点数，并画出这样的一棵二叉树。（2）T树可能的最小结点数，并画出这样的一棵二叉树。3、依次输入（26，30，15，10，28，19，18，22），构造二叉排序树，并计算等概率情况下的查找成功的平均查找长度。4、画出10个元素的折半判定树，并计算等概率情况下查找成功的平均查找长度。5、已知关键字集合：50，52，85，22，96，17，36，55，以第一个关键字中轴元素，写出一趟快速排序的结果。
四、编写算法每小题10分，共30分
1、编写算法voidAdjustLi
kListL，其功能是：以第一个元素为基准，将小于该元素的结点全部放到前面，大于该元素的结点全部放到其后。
2、要求循环队列不损失一个空间全部都能得到利用，设置一个标志域tag，以tag为0或1来区分头尾指针相同时的列状态的空与满，请编写与此结构相应的出队算法。
3、二叉树采用二叉链表结构存储，编写算法实现统计二叉树中的结点个数。
f五、编写算法共15分二叉树采用二叉链表结构存储，编写实现二叉树后序线索化的算法。
六、编写算法共15分编写算法，由依次输入的顶点数、弧数和各顶点信息、弧信息建立有向图的邻接表存储结构。
西北大学2015年招收攻读硕士学位研究生试题
科目名称：数据结构适用专业：计算机技术、软件工程答案请答在答题纸上，答在本试题上的答案一律无效。
科目代码：851共2页
一、简答每小题6分，共30分1、简述四类基本的数据逻辑关系，并用图表示。2、简述数组、广义表属于线性表原因。3、算法的定义及特性。4、什么是平衡二叉排序树？平衡因子的取值范围是什么？5、简述稳定排序含义，给出两种稳定排序方法以及两种不稳定排序方法名称并证明。
二、分析与方法选择每小题10分，共30分1、折半查找法对待查找的列表哪两个要求？2、分析快速排序的性能（最好情况、最坏情况）。3、关于二叉树结点度数的计算。（牢记二叉树的5条性质，会计算二叉树及K叉树相关的计算。）
三、构造结果每小题8分，共40分1、已知一棵二叉树的前序序列及后序序列，给出其对应的二叉树。2、图的两种存储结构及表示、r