北师08考研程序设计与数据结构试题

本主题由大英雄曹操于 2008-8-7 14:00 审核通过

碧水无忧

中级会员

Rank: 3 Rank: 3

1^# 大中小发表于 2008-8-7 11:51 只看该作者

北师08考研程序设计与数据结构试题

一、简答题（20分）
　　1.数据类型和抽象数据类型的含义清泽论坛-太原理工大学网络家园' k9 U- x  A# r% J( E# Q1 _
　　2.算法的特性与算法的时间复杂度
　　3.快速排序方法最好和最坏的情况是什么？简要分析说明
　　4.栈、队列的共同点与不同点，说明其属于线形表的原因太原理工大学,太原理工大学论坛* e, m: i* N% n3 b. t
　　二、方法选择（20分）太原理工大学|太原理工大学论坛|太原理工大学BBS6 v9 J, j5 r4 b' P; a0 S$ o- r
　　1.一棵二叉排序树中各结点不相同，欲得到一个由大到小的结点值递减序列，你认为采用什么方法能得到要求的结果？
　　2.设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序，基数排序，快速排序，堆排序，插入排序），那种方法最好，为什么？太原理工大学论坛[龙城水秀]2 S6 A4 Z( z3 U  q
　　三、（40分，每题8分）太原理工大学论坛[龙城水秀]0 \- E/ N1 s0 V! M  }/ |
　　１。已知一个循环单链表la，av是可利用栈的头指针，请用３个赋值语句，完成将整个循环链表释放的功能。（即将表整个归还到可用的栈空间）
　　2.给出求N阶hanoi塔的函数定义如下：Hanoi （ int n，char x，char y ，char z ）太原理工大学论坛[龙城水秀]. E& C5 N$ y1 ]5 a9 \
　　{ if （ n= =1） move （ x ，1，z）太原理工大学论坛[龙城水秀]* h: V/ f$ j6 ?6 \) {
　　Else{ hanoi（ n-1， x，z，y）；
　　Move（x，n，z）；太原理工大学,太原理工大学论坛$ q4 B  h6 P# R  j; S
　　Hanoi（n-1，y，x，z）；
　　}
　　}
　　写出执行hanoi（3，a，b，c）时递归函数的实在参变量变化，以及move的搬运过程。
　　3.已知关键字序列为：（75，33，52，41，12，88，66，27），哈希表长为１０，哈希函数为：Ｈ（ｋ）＝ｋＭＯＤ７，解决冲突用线性探测再散列法，要求构造哈希表，求出等概率下查找成功查找长度。
　　4.已知一棵二叉树，中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。
　　5.给定权值｛8，12，4，5，26，16，9｝，构造一个哈夫曼树，并计算其带权路径长度。www.tyutbbs.com# I" r4 d, D2 s
　　四、编写程序（15分）太原理工大学|太原理工大学论坛|太原理工大学BBS+ \6 V7 Z0 Q/ ]- _; Z! G
　　建立线形表，（a1，a2，a3…。，an）的单链表存储，并实现其就地逆置为（an，，an-1…a2.，a1）。清泽论坛-太原理工大学网络家园1 `6 f) Q8 B6 B7 u* m$ f; Y
　　五、编写程序（10分）
　　在中序线索树中，要找出Ｘ结点的前驱结点，请写出相关函数定义。www.tyutbbs.com7 t3 H, D' B6 y) u( g; l- ]% f- o
　　Ltag Lc Data Rtag Rc3 q) l+ g8 f$ d! o+ A
　　六、编写算法（20分）
　　已知有Ｎ个结点的无向图，采用邻接表结构存储，要求对每个连通子图中一个生成树中的各条边逐层输出，边的输出格式为（ki，kj）。
　　七、编写算法（25分）
　　1.写出建立二叉树，二叉链表存储结构的算法。（10分）) d2 ?0 x3 ~5 y4 p% q
　　2.已知二叉树采用二叉链表方式存放，要求对二叉树从１开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，左孩子编号小于右孩子编号。给出在二叉树中结点的数据域部分填写，实现如上要求编号的非递归算法。（10分）
　　3.已知二叉树采用二叉链表方式存放，给出判定它是否为一棵二叉排序树的算法。（5分）太原理工大学|太原理工大学论坛|太原理工大学BBS! n! M8 R8 I' P& A
海文专业课 http://www.VIPkaoyan.com/

TOP

‹‹ 上一主题 | 下一主题 ››

Processed in 0.072184 second(s), 7 queries, Gzip enabled.