2016 年江南大学招收硕士研究生入学考试试题847计算机程序设计

（考生注意：全部答案必须写在答题纸上否则后果自负！）

考试科目代码：847 考试科目：计算机程序设计

一、

循环双链表，节点包括 previous、data、next 和访问频度域 freq，初始为 0，每当链表进行一次 Locate(L,x)运算时，令 x 节点 freq 域的值加 1，并使其链表节点频度按递减顺序排列，实现 Locate(L,x)。

二、

$f(m,n)= \begin{cases} n+1 & m=0 \\ f(m-1,1) & m\neq0 且 n=0 \\ f(m-1,(m,n-1)) & m\neq0 且 n\neq0 \end{cases}$ 求出递归算法

三、

以二叉链表为存储结构，编写非递归的后序遍历

四、

对下图用 prim 和 kruskal 算法构造最小生成树

五、

试写出对长度为 20 的有序表进行二分查找的算法，并画出它的判定树，并求等概率情况下的平均查找长度。（折中查找）

判定树如下图所示：

六、

编写双向起泡的排序算法，即在排序过程中交替改变扫描方向

七、

在二叉排序树中，指定节点所在的层数

八、

有 1、2、3、4 这些数字，求这些数字能组成多少个互不相同且无重复数字的三位数

九、

序列 $\frac{2}{1}$ , $\frac{3}{2}$ , $\frac{5}{3}$ , $\frac{8}{5}$ , $\frac{13}{8}$ , $\frac{21}{13}$ ----,求前 20 项和。