北京师范大学08年考研程序设计与数据结构试题
考研_考试大 [ 2008/11/17 ] 来源：北京师范大学
一、简答题（20分）
1.数据类型和抽象数据类型的含义
2.算法的特性与算法的时间复杂度
3.快速排序方法最好和最坏的情况是什么？简要分析说明
4.栈、队列的共同点与不同点，说明其属于线形表的原因
二、方法选择（20分）
1.一棵二叉排序树中各结点不相同，欲得到一个由大到小的结点值递减序列，你认为采用什么方法能得到要求的结果？
2.设有1000个无序元素，仅要求出前10个最小元素，在下列排序方法中（归并排序，基数
排序，快速排序，堆排序，插入排序），那种方法最好，为什么？
三、（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.已知关键字序列为：（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分）
在中序线索树中，要出Ｘ结点的前驱结点，请写出相关函数定义。
Ltag Lc Data Rtag Rc
六、编写算法（20分）
已知有N个结点的无向图，采用邻接表结构存储，要求对每个连通子图中一个生成树中的各条边逐层输出，边的输出格式为（ki，kj）。
七、编写算法（25分）
1.写出建立二叉树，二叉链表存储结构的算法。（10分）
2.已知二叉树采用二叉链表方式存放，要求对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，左孩子编号小于右孩子编号。给出在二叉树中结点的数据域部分填写，实现如上要求编号的非递归算法。（10分）
3.已知二叉树采用二叉链表方式存放，给出判定它是否为一。
大连理工大学2008年考研数据结构试题
考研_考试大 [ 2008/11/3 ] 来源：考研教育网
一、选择题
1. 线性表的 ———— 运算中，顺序存储结构比例链式存储结构好。
A. 插入
B .删除
C .按号查
D .按元素值查
2.此程序的复杂度为 ————
for（int i=0 ； i<M；&NBSP;I++）
for（int j=0；j<N；&NBSP;J++）
A[i][j]=i*j；
A . O（m2）
B . O（n2）
C . O （m*n）
D . O （m+n）
3 .在待排数据已基本有序的情况下， ———— 效率最高。
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 . 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.|—m/2—|
B.|—m/2—|-1
C.m
D.m-1
E.|—m/2—|
F.|—m/2—|-1
9 .两个长度为 n 的递增有序表，合并成一个长度为 2n 的递增有序表，最少需要进行关键字比较 ———— 次。
A . 1
B . n-1
C . n
D . 2n
10 .有向图 G， n 个顶点，邻接矩阵存储于二维数组中，顶点 i 的度为 ———— .
A.（i=0 n-1）∑A[i][j]
B.（j=0 n-1）∑A[i][j]
C.（i=0 n-1）∑A[i][j]+（j=0 n-1）∑A[i][j]
D.（j=0 n-1）∑（A[i][j]+A[j][i]）
二、问答题
1. （ 6 ） n 阶对称阵（ aij ） n × n ，采用压缩存储存放于一维数组 F[m] 中，从 F[0] 开始存储，给出矩阵的压缩存储方式及任一矩阵元素 aij （ 0<=i，j<=n-1 ）的地址计算公式，并求算 m .
2. （ 5 ）顺序队列如何解决假溢出问题。
3. （ 8 ）已知一组关键字（ 10 ， 26 ， 14 ， 25 ， 17 ， 36 ， 37 ， 44 ， 27 ， 34 ， 60 ）设哈希函数 H （ x ） =x ，表长 m=13 ，请写出用线性探测法处理冲突构造所得的哈希表。并求出在
等概率情况下，查成功时的平均检索长度。
4. （ 6 ）给定一个由 n 个关键字不同的记录构成的序列，你能否用比 2n-3 少的比较次数出 n 个元素中的最大值和最小值？如果有，请描述你的方法。最快需要多少次比较？（无需写算法）
三 、用类 C 语言完成设计
1.（ 15 ）什么是堆？设计算法判定给定的存于数组 r[] 中的 n 个数据是否为堆。
2.（ 15 ）设 u 、 v 是有向图的两个顶点，设计算法判读有向图中是否存在从顶点 u 到 v 的长度为 k 的简单路径。要求给出图的存储形式及其类型定义。
3. （ 10 ）设二叉树以二叉链表形式存放。一颗二叉树的繁茂程度定义为各层节点数的最大值与树的高度的乘积。试设计一个高效算法，求二叉树的繁茂程度。
2007年电子科技大学计算机专业基础试题
考研_考试大 [ 2007/12/9 ] 保存本文
第一部分 数据结构 （共 75分）
一、单项选择题（每题 2分，共10分）
1．表头表尾均为空表的广义表是（ ）。
① （） ② （（）） ③ （（），（）） ④ （（（）））
2. 对 下列 4个序列,以第一个关键字为基础进行用快速排序算法进行排序，在第一趟过程中移动记录次数最多的是 ( )
① 92，96，100，110，42，35，30，88
数据结构与算法考研真题 ② 92，96，88，42，30，35，110，100
③ 100，96，92，35，30，110，88，42
④ 42，30，35，92，100，96，88，110
3． 实现图的广度优先搜索算法时，使用的数据结构是 （ ）
① 栈
② 队列
③ 十字链表
④ 三元组
4．在有向图G的邻接矩阵中，顶点Vi 的度是 （ ）。
① 邻接矩阵中第 i行元素之和
② 邻接矩阵中第 i列元素之和
③ 邻接矩阵中第 i行和第i列元素之和
④ 邻接矩阵中第 i行元素之和与第i列元素之和的最大值
5．能有效缩短关键路径长度的方法是（ ）
① 缩短任意一个活动的持续时间
② 缩短关键路径上任意一个关键活动的持续时间
③ 缩短多条关键路径上共有的任意一个关键活动的持续时间
④ 缩短所有关键路径上共有的任意一个关键活动的持续时间
二、填空题（每空 2分，共 8 分）
1． 由一棵二叉树的后序序列和 可唯一确定这棵二叉树。
2． 二叉树结点数 n与边数e的关系为 。
3． 在各种查算法中，平均查长度与关键字个数 n无关的方法是 。
4． 若希望得到树高较矮的生成树，则采用图的 遍历算法。
三、判断题（用√表示对，用×表示错。每题 2分，共 12 分）
1． 循环队列中不存在队列满的问题。（ ）
2． 将一个新结点插入到二叉排序树中，该结点一定成为叶结点。（ ）
3． 用单链表示的有序表可以使用折半查方法来提高查速度。（ ）
4． 若有向图中每个顶点的入度和出度均为 1，则该有向图必有回路。（ ）
5． 已知二叉排序树的先序序列，能唯一确定该二叉排序树。（ ）
6． 交换完全二叉树所有结点的左右子树，得到的二叉树仍是完全二叉树。（ ）
四、简答题（每题 6分，共 30 分）
1．若一个有向图的邻接矩阵中主对角线以下的元素均为0，则该图一定不存在回路。该说法是否正确？为什么？
2． 在完全二叉树中，设结点数为 n，
（ 1）如何断定该完全二叉树中度为1的结点数n1?
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论