中南大学论坛

 找回密码
 注册(开放注册)
搜索
查看: 1599|回复: 0

北京师范大学08年考研程序设计与数据结构试题

[复制链接]
发表于 2008-8-20 11:08:01 | 显示全部楼层 |阅读模式
一、简答题(20分)
  1.数据类型和抽象数据类型的含义
  2.算法的特性与算法的时间复杂度
  3.快速排序方法最好和最坏的情况是什么?简要分析说明
  4.栈、队列的共同点与不同点,说明其属于线形表的原因
  二、方法选择(20分)
  1.一棵二叉排序树中各结点不相同,欲得到一个由大到小的结点值递减序列,你认为采用什么方法能得到要求的结果?
  2.设有1000个无序元素,仅要求找出前10个最小元素,在下列排序方法中(归并排序,基数排序,快速排序,堆排序,插入排序),那种方法最好,为什么?
  三、(40分,每题8分)
  1。已知一个循环单链表laav是可利用栈的头指针,请用3个赋值语句,完成将整个循环链表释放的功能。(即将表整个归还到可用的栈空间)
  2.给出求Nhanoi塔的函数定义如下:Hanoi int nchar xchar y char z
  { if n= =1 move x 1z
  Else{ hanoi n-1 xzy);
  Movexnz);
  Hanoin-1yxz);
  }
  }
  写出执行hanoi3abc)时递归函数的实在参变量变化,以及move的搬运过程。
  3.已知关键字序列为:(7533524112886627),哈希表长为10,哈希函数为:H(k)=kMOD7,解决冲突用线性探测再散列法,要求构造哈希表,求出等概率下查找成功查找长度。
  4.已知一棵二叉树,中序序列DBCAFGE,后序序列DCBGFEA,构造该二叉树。
  5.给定权值{8124526169},构造一个哈夫曼树,并计算其带权路径长度。
  四、编写程序(15分)
  建立线形表,(a1a2a3…。,an)的单链表存储,并实现其就地逆置为(an an-1a2.a1)。
  五、编写程序(10分)
  在中序线索树中,要找出X结点的前驱结点,请写出相关函数定义。
  Ltag Lc Data Rtag Rc
  六、编写算法(20分)
  已知有N个结点的无向图,采用邻接表结构存储,要求对每个连通子图中一个生成树中的各条边逐层输出,边的输出格式为(kikj)。
  七、编写算法(25分)
  1.写出建立二叉树,二叉链表存储结构的算法。(10分)
  2.已知二叉树采用二叉链表方式存放,要求对二叉树从1开始进行连续编号,要求每个结点的编号大于其左右孩子的编号,同一结点的左右孩子中,左孩子编号小于右孩子编号。给出在二叉树中结点的数据域部分填写,实现如上要求编号的非递归算法。(10分)
  3.已知二叉树采用二叉链表方式存放,给出判定它是否为一棵二叉排序树的算法。(5分)
您需要登录后才可以回帖 登录 | 注册(开放注册)

本版积分规则

手机访问本页请
扫描左边二维码
         本网站声明
本网站所有内容为网友上传,若存在版权问题或是相关责任请联系站长!
站长联系QQ:7123767   myubbs.com
         站长微信:7123767
请扫描右边二维码
www.myubbs.com

小黑屋|手机版|Archiver|中南大学论坛 ( 琼ICP备10001196号-2 )

GMT+8, 2024-3-28 21:06 , Processed in 0.108067 second(s), 15 queries .

Powered by 高考信息网 X3.3

© 2001-2013 大学排名

快速回复 返回顶部 返回列表