上海交通大学论坛|源来于此
标题:
北京师范大学08年考研程序设计与数据结构试题
[打印本页]
作者:
不那么
时间:
2008-8-20 11:08
标题:
北京师范大学08年考研程序设计与数据结构试题
一、简答题(
20
分)
1.
数据类型和抽象数据类型的含义
2.
算法的特性与算法的时间复杂度
3.
快速排序方法最好和最坏的情况是什么?简要分析说明
4.
栈、队列的共同点与不同点,说明其属于线形表的原因
二、方法选择(
20
分)
1.
一棵二叉排序树中各结点不相同,欲得到一个由大到小的结点值递减序列,你认为采用什么方法能得到要求的结果?
2.
设有
1000
个无序元素,仅要求找出前
10
个最小元素,在下列排序方法中(归并排序,基数排序,快速排序,堆排序,插入排序),那种方法最好,为什么?
三、(
40
分,每题
8
分)
1。已知一个循环单链表
la
,
av
是可利用栈的头指针,请用3个赋值语句,完成将整个循环链表释放的功能。(即将表整个归还到可用的栈空间)
2.
给出求
N
阶
hanoi
塔的函数定义如下:
Hanoi
(
int n
,
char x
,
char y
,
char z
)
{ if
(
n= =1
)
move
(
x
,
1
,
z
)
Else{ hanoi
(
n-1
,
x
,
z
,
y
);
Move
(
x
,
n
,
z
);
Hanoi
(
n-1
,
y
,
x
,
z
);
}
}
写出执行
hanoi
(
3
,
a
,
b
,
c
)时递归函数的实在参变量变化,以及
move
的搬运过程。
3.
已知关键字序列为:(
75
,
33
,
52
,
41
,
12
,
88
,
66
,
27
),哈希表长为10,哈希函数为:H(k)=kMOD7,解决冲突用线性探测再散列法,要求构造哈希表,求出等概率下查找成功查找长度。
4.
已知一棵二叉树,中序序列
DBCAFGE
,后序序列
DCBGFEA
,构造该二叉树。
5.
给定权值{
8
,
12
,
4
,
5
,
26
,
16
,
9
},构造一个哈夫曼树,并计算其带权路径长度。
四、编写程序(
15
分)
建立线形表,(
a1
,
a2
,
a3
…。,
an
)的单链表存储,并实现其就地逆置为(
an
,
,
an-1
…
a2.
,
a1
)。
五、编写程序(
10
分)
在中序线索树中,要找出X结点的前驱结点,请写出相关函数定义。
Ltag Lc Data Rtag Rc
六、编写算法(
20
分)
已知有N个结点的无向图,采用邻接表结构存储,要求对每个连通子图中一个生成树中的各条边逐层输出,边的输出格式为(
ki
,
kj
)。
七、编写算法(
25
分)
1.
写出建立二叉树,二叉链表存储结构的算法。(
10
分)
2.
已知二叉树采用二叉链表方式存放,要求对二叉树从1开始进行连续编号,要求每个结点的编号大于其左右孩子的编号,同一结点的左右孩子中,左孩子编号小于右孩子编号。给出在二叉树中结点的数据域部分填写,实现如上要求编号的非递归算法。(
10
分)
3.
已知二叉树采用二叉链表方式存放,给出判定它是否为一棵二叉排序树的算法。(
5
分)
欢迎光临 上海交通大学论坛|源来于此 (http://www.isjtu.cn/)
Powered by Discuz! X3.3