894程序设计

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