数据结构与历年真题

《数据结构与历年真题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京师范大学08年考研程序设计与数据结构试题考研_考试大     [2008/11/17]     来源：北京师范大学一、简答题（20分） 　　1.数据类型和抽象数据类型的含义　　2.算法的特性与算法的时间复杂度　　3.快速排序方法最好和最坏的情况是什么？简要分析说明　　4.栈、队列的共同点与不同点，说明其属于线形表的原因　　二、方法选择（20分）　　1.一棵二叉排序树中各结点不相同，欲得到一个由大到小的结点值递减序列，你认为采用什么方法能得到要求的结果？　　2.设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序，基数排序，快速排序，堆排序，插入排序）

2、，那种方法最好，为什么？　　三、（40分，每题8分）　　1.已知一个循环单链表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、过程。　　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分）　　在中序线索树中，要找出Ｘ结

4、点的前驱结点，请写出相关函数定义。　　Ltag Lc Data Rtag Rc　　六、编写算法（20分）　　已知有N个结点的无向图，采用邻接表结构存储，要求对每个连通子图中一个生成树中的各条边逐层输出，边的输出格式为（ki，kj）。　　七、编写算法（25分）　　1.写出建立二叉树，二叉链表存储结构的算法。（10分）　　2.已知二叉树采用二叉链表方式存放，要求对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，左孩子编号小于右孩子编号。给出在二叉树中结点的数据域部分填写，实现如上要求编号的非递归算法。（10分）　　3.已知二叉树采用二叉链表方

5、式存放，给出判定它是否为一。大连理工大学2008年考研数据结构试题考研_考试大     [2008/11/3]     来源：考研教育网　　一、选择题 　　1. 线性表的 ———— 运算中，顺序存储结构比例链式存储结构好。　　A. 插入　　B .删除　　C .按号查找　　D .按元素值查找　　2.此程序的复杂度为 ————　　for（int i=0 ； i

6、基本有序的情况下， ———— 效率最高。　　A . 直接选择排序　　B . 直接插入排序　　C . 快速排序　　D . 归并排序　　4 . n 个英文单词，每个单词长度基本相等，为 m ，当 n>>50，m<5 时，时间复杂度最佳的为 ———— ：　　A . 快速排序　　B .归并排序　　C .基数排序　　D.直接插入排序　　5 .顺序查找长度为 n 的顺序表，查找成功的平均检索长度为 ———— ：　　A . n　　B . n/2　　C.（n-1）/2　　D . （n+1）/2　　6 .一颗二叉树，头序序列为 ABCDEFG ，中序序列为 CBDAEGF ，后序为 ————　　A

7、 . CDBGFEA　　B . CDBFGEA　　C . CDBAGFE　　D . BCDAGFE　　7 .一颗度为 3 的树，度为 3 的节点为三个，度为 2 的节点为 1 个，度为 1 的节点 1 个，度为 0 的节点 ———— 个（考试大）。　　A . 6　　B . 7　　C . 8　　D . 9　　8 .m 阶 B— 树中，某一节点插入一个新关键字引起破裂，则该节点原有关键字 ———— 个。　　A.

8、—m/2—

9、　　B.

10、—m/2—

11、-1　　C.m　　D.m-1　　E.

12、