《数据结构与历年真题》由会员分享，可在线阅读，更多相关《数据结构与历年真题（18页珍藏版）》请在金锄头文库上搜索。
1、北京师范大学08年考研程序设计与数据结构试题考研_考试大 2008/11/17 来源：北京师范大学一、简答题（20分） 1.数据类型和抽象数据类型的含义 2.算法的特性与算法的时间复杂度 3.快速排序方法最好和最坏的情况是什么？简要分析说明 4.栈、队列的共同点与不同点，说明其属于线形表的原因 二、方法选择（20分） 1.一棵二叉排序树中各结点不相同，欲得到一个由大到小的结点值递减序列，你认为采用什么方法能得到要求的结果？ 2.设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序，基数排序，快速排序，堆排序，插入排序），那种方法最好，为什么？ 三、（40分，每题8分）
2、 1.已知一个循环单链表la，av是可利用栈的头指针，请用个赋值语句，完成将整个循环链表释放的功能。（即将表整个归还到可用的栈空间） 2.给出求N阶hanoi塔的函数定义如下：Hanoi（intn，charx，chary，charz） if（n=1）move（x，1，z） Elsehanoi（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，解决冲突
3、用线性探测再散列法，要求构造哈希表，求出等概率下查找成功查找长度。 4.已知一棵二叉树，中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。 5.给定权值8，12，4，5，26，16，9，构造一个哈夫曼树，并计算其带权路径长度。 四、编写程序（15分） 建立线形表，（a1，a2，a3。，an）的单链表存储，并实现其就地逆置为（an，an-1a2.，a1）。 五、编写程序（10分） 在中序线索树中，要找出结点的前驱结点，请写出相关函数定义。 LtagLcDataRtagRc 六、编写算法（20分） 已知有N个结点的无向图，采用邻接表结构存储，要求对每个连通子图中一个生成树中的各条边逐层
4、输出，边的输出格式为（ki，kj）。 七、编写算法（25分） 1.写出建立二叉树，二叉链表存储结构的算法。（10分） 2.已知二叉树采用二叉链表方式存放，要求对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，左孩子编号小于右孩子编号。给出在二叉树中结点的数据域部分填写，实现如上要求编号的非递归算法。（10分） 3.已知二叉树采用二叉链表方式存放，给出判定它是否为一。大连理工大学2008年考研数据结构试题考研_考试大 2008/11/3 来源：考研教育网一、选择题 1.线性表的运算中，顺序存储结构比例链式存储结构好。 A.插入 B.删除 C.按号查找 D
5、.按元素值查找 2.此程序的复杂度为 for（inti=0；iM； I+） for（intj=0；j50，m5时，时间复杂度最佳的为： 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
6、 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=0n-1）Aij B.（j=0n-1）Aij C.（i=0n-1）Aij+（j=0n-1）Aij D.（j=0n-1）（Aij+Aji） 二、问答题 1.（6）n阶对称阵（aij）nn，采用压缩存储存放于一维
7、数组Fm中，从F0开始存储，给出矩阵的压缩存储方式及任一矩阵元素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）什么是
8、堆？设计算法判定给定的存于数组r中的n个数据是否为堆。 2.（15）设u、v是有向图的两个顶点，设计算法判读有向图中是否存在从顶点u到v的长度为k的简单路径。要求给出图的存储形式及其类型定义。 3.（10）设二叉树以二叉链表形式存放。一颗二叉树的繁茂程度定义为各层节点数的最大值与树的高度的乘积。试设计一个高效算法，求二叉树的繁茂程度。2007年电子科技大学计算机专业基础试题考研_考试大 2007/12/9 保存本文第一部分 数据结构 （共 75分） 一、单项选择题（每题 2分，共10分） 1表头表尾均为空表的广义表是（ ）。 （） （） （），（） （） 2. 对 下列 4个序列,以第一个关键
9、字为基础进行用快速排序算法进行排序，在第一趟过程中移动记录次数最多的是 ( ) 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能有效缩短关键路径长度的方
10、法是（ ） 缩短任意一个活动的持续时间 缩短关键路径上任意一个关键活动的持续时间 缩短多条关键路径上共有的任意一个关键活动的持续时间 缩短所有关键路径上共有的任意一个关键活动的持续时间二、填空题（每空 2分，共 8 分） 1 由一棵二叉树的后序序列和 可唯一确定这棵二叉树。 2 二叉树结点数 n与边数e的关系为 。 3 在各种查找算法中，平均查找长度与关键字个数 n无关的方法是 。 4 若希望得到树高较矮的生成树，则采用图的 遍历算法。 三、判断题（用表示对，用表示错。每题 2分，共 12 分） 1 循环队列中不存在队列满的问题。（ ） 2 将一个新结点插入到二叉排序树中，该结点一定成为叶结点
11、。（ ） 3 用单链表示的有序表可以使用折半查找方法来提高查找速度。（ ） 4 若有向图中每个顶点的入度和出度均为 1，则该有向图必有回路。（ ） 5 已知二叉排序树的先序序列，能唯一确定该二叉排序树。（ ） 6 交换完全二叉树所有结点的左右子树，得到的二叉树仍是完全二叉树。（ ） 四、简答题（每题 6分，共 30 分） 1若一个有向图的邻接矩阵中主对角线以下的元素均为0，则该图一定不存在回路。该说法是否正确？为什么？ 2 在完全二叉树中，设结点数为 n， （ 1）如何断定该完全二叉树中度为1的结点数n1? （ 2）给定结点x的编号m，又如何根据该编号断定x是否为叶结点？ 3 当查找表有既能较
12、快查找又能适应动态变化的需求时，选用什么查找方法最适合？并简述其理由。4 在某个通信系统中，报文的字符集为 a,b,c,d,e,f,g,h八种，其出现频率分别为6，28,8,9,13,22,4和1,试为各字符设计二进制编码，使得报文编码长度最短。给出各字符的二进制编码和报文编码长度。 5 设 L是不带头结点单链表的头指针，P是指向链表中某个结点的指针，该结点既不是第一个结点，也不是最后一个结点，S是指向待插入新结点的指针，用下面 - 选项完成 A、B功能。 A. 在P所指结点前面插入 S所指结点的语句序列是（ ）； B. 在第一个结点前面插入 S所指结点的语句序列是（ ）； P.next ：=S； Q:= P； L:= S； P:= L； WHILE ( P.next Q ) DO P：= P.next； S.next：= P.next； S.next：= L.next； 五、算法题（共 15 分） 1 设p,q分别指向两个不带头结点的单循环链表中的某个结点，试编写一个算法，用O(1)时间将
