您的位置:考研教育网> >历年试题>考研专业课> 正文

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

北京师范大学   2008-02-26 16:59 【 】【我要纠错

  一、简答题(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分)

  点击查看更多北京师范大学相关信息>>>

◇ 编辑推荐
·2015年考研复习:政治 英语 数学  专业课 · 2014年考研真题及答案汇总   历年考研真题
· 考研网上辅导热招!  ·2015年考研报考指南   ·历年考研国家分数线汇总   复试信息
考研网上辅导课程 特色班 精品班 实验班
学费 购买 学费 购买 学费 购买
公共课 政 治 800元 购买 1500元 购买 3500元 购买
英 语 800元 购买 1500元 购买 3500元 购买
数 学 800元 购买 1500元 购买 3500元 购买

专业课

视频

《管理类联考综合》、《会计学》、《中医综合》、《西医综合》、《法硕联考综合(法学)》、
《法硕联考综合(法学)》、《法硕联考专业基础(法学)》、《法硕联考专业基础(非法学)》

专业课

资料

952所考研院校、57300个招生专业、245000份考研辅导课件、核心纲要、考研笔记、内部题库现正热卖!

说明 专业课请到考研开放平台上注册及缴费----帮助