西北大学20102015年招收攻读硕士学位研究生数据结构试题
西北大学2010年招收攻读硕士学位研究生试题
科目名称：数据结构
适用专业：计算机技术、软件工程
答案请答在答题纸上，答在本试题上的答案一律无效。注编写程序可选用C语言，
算法描述采用类语言，算法应加上必要的注释；所有答案均要求写在答题纸上。
科目代码：848共2页
一、简答问题共30分，每小题6分1、简述字符串、栈属于线性表原因。2、线性结构与非线性结构的差别。3、算法定义与算法特性。4、数据类型与抽象数据类型。5、图遍历中设置访问标志数组的作用。
二、方法选择共20分，每小题10分1、说明稳定排序含义，并给出一种不稳定排序方法的名称与证明。
2、在一个连通无向图上，欲求从一点Vi到另一点Vj（ViVj）所经结点数目短路径，在深度优先搜索、广度优先搜索、从一点到其余各顶点的最短路径算法中，你认为最好选择哪种方法为基础，简述原因。
三、构造结果共40分，每小题8分1、构造10个结点的折半判定树，并计算查找成功的平均查找长度。2、已知一二叉树中序序列为BDAEC，后序序列为DBECA，给出其对应的二叉树。
3、已知
阶下三角矩阵A（即当ij时，有aij0），按照压缩存储的思想，可以主对角线以下所有元素（包括主对角线上的元素）依次存放于一维数组B中。请从第一列开始，采用行序为主序，给出在B中确定元素aij存放位置的公式。
4、二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由小到大的结点值递增序列，简述处理方法思路。
5、给出求N阶ha
oi塔的函数定义如下：ha
oii
t
，charx，chary，charz
fif
1movex，1，zelseha
oi
1，x，z，y；movex，
，z；ha
oi
1，y，x，z；
请写出执行ha
oi3，a，b，c时递归函数的实在参量变化及move的搬动过程。
四、编写程序共15分要求实现如下功能：将数组C1
中所有奇数移到偶数之前，要求时间复杂度为O
。
五、编写算法共30分，每小题15分（1）写一个建立二叉树的算法，要求二叉树按二叉链表存储。（2）已知二叉树用二叉链表存储，要求写出算法，实现该二叉树左右子树交换。
六、编写算法15分
树采用孩子兄弟存放，结点结构为
fchdata
其中fch表示指向第一个孩子，
sib表示指向下一个兄弟。

sib
编写算法，要求由根开始逐层输出树中的各条边，边输出格式为（KiKj）。例：
A
B
C
D
E
F
G
输出为：AB，AC，AD，BE，BF，CG。
西北大学2011年招收攻读硕士学位研究生试题
科目名称：r