1、2011 年北师大教育技术初试真题一、选择题（12 道*5 分）。1、有几道读程序题，C 语言中的递归、数组指针、十六进制。2、用数组表示平衡二叉树，广义表表示的二叉树然后后序遍历这颗二叉树。3、计算二分查找的平均查找长度，选择正确的关于链表的程序。二、简答题。（5 道*12 分）1、平衡二叉树插入一个数后的结构。2、快速排序一个序列。3、用堆排序一个序列。4、用静态列表表示一个基数排列的分配和收集。5、读一段汉诺塔程序，写出结果，4 层递归。三、操作题（2 道*15 分）。1、构造一颗哈弗曼树，算出它的路径长度。2、一个 AOE 网，填写事件和活动的最早开始时间和最晚开始时间的表格，最后写出
2、关键路径的顶点。题型：选择题（12 道）、简答题（5 道）、操作题（ 5 道）选择题每道题 5 分，简单题每道题 6 分，操作题每道 12 分。1、选择题考察的是 C 语言的基础知识，比如数组指针；还考了数据结构中一些线性表的操作，有一个是问稀疏矩阵的稀疏因子，广义表里面考了个选择题。2、简答题考察的是（1 ）静态链表存储结构算法描述；（2 ）单链表的插入操作、删除操作；（3）KMP 算法的应用：next 数组值推导；（4）哈夫曼树；（5）快速排序。3、操作题考察的是（1 ）堆排序；（2）哈希表；（ 3）AOE 网；（4 ）B-树；（5）二分查找与直接查找的比较。线性表、树和二叉树、图、内排序
3、、查找考察的相对多一点，其余的也有考察，这是回忆的版本，故有些部分可能回忆的不是很清楚北京师范大学 2008 年程序设计与数据结构考研试题一、简答题（20 分）1数据类型和抽象数据 类型的含义2算法的特性与算法的时间复杂度3快速排序方法最好和最坏的情况是什么？简要分析说明4 栈、队列的共同点与不同点， 说明其属于线形表的原因二、方法选择（20 分）1一棵二叉排序树 中各结点不相同，欲得到一个由大到小的结点值递减序列，你认为采用什么方法能得到要求的结果？2 设有 1000 个无序元素，仅要求找出前 10 个最小元素，在下列排序方法中（归并排序，基数排序，快速排序，堆排序，插入排序），那种方法最好
4、，为什么？三、（40 分, 每题 8 分）已知一个循环单链表 la,av 是可利用栈的头指针，请用个赋值语句，完成将整个循环链表释放的功能。（即将表整个归还到可用的栈空间）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,4
5、1,12,88,66,27），哈希表长为，哈希函数为：（），解决冲突用线性探测再散列法，要求构造哈希表，求出等概率下查找成功查找长度。4已知一棵二叉树 ，中序序列 DBCAFGE，后序序列 DCBGFEA，构造该二叉树。5 给定权值8，12，4，5 ，26 ，16，9，构造一个哈夫曼树，并计算其带权路径长度。四、编写程序（15 分）建立线形表，（a1,a2,a3.,an）的单链表存储，并实现其就地逆置为（an, ,an-1a2.,a1）。五、编写程序（10 分）在中序线索树中，要找出结点的前驱结点，请写出相关函数定义。LtagLcDataRtagRc六、编写算法（20 分）已知有个结点的无向图，采用邻接表结构存储，要求对每个连通子图中一个生成树中的各条边逐层输出，边的输出格式为（ki,kj）。七、编写算法（25 分）1写出建立二叉树 ，二叉链表存储结构的算法。（10 分）2已知二叉树采用二叉 链表方式存放，要求对二叉树从开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，左孩子编号小于右孩子编号。给出在二叉树中结点的数据域部分填写，实现如上要求编号的非递归算法。（10 分）3已知二叉树采用二叉 链表方式存放，给出判定它是否为一棵二叉排序树的算法。（5 分）
