数据结构与历年真题

北京师范大学08年考研程序设计与数据结构试题考研_考试大[2008/11/17]来源：北京师范大学一、简答题（20分）1.数据类型和抽象数据类型的含义2.算法的特性与算法的时间复杂度3.快速排序方法最好和最坏的情况是什么？简要分析说明4.栈、队列的共同点与不同点，说明其属于线形表的原因二、方法选择（20分）1.一棵二叉排序树中各结点不相同，欲得到一个由大到小的结点值递减序列，你认为采用什么方法能得到要求的结果？2.设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序，基数排序，快速排序，堆排序，插入排序），那种方法最好，为什么？三、（40分，每题8分）1.已知一个循环单链表la，av是可利用栈的头指针，请用３个赋值语句，完成将整个循环链表释放的功能。（即将表整个归还到可用的栈空间）2.给出求N阶hanoi塔的函数定义如下：Hanoi（intn，charx，chary，charz）{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分）在中序线索树中，要找出Ｘ结点的前驱结点，请写出相关函数定义。LtagLcDataRtagRc六、编写算法（20分）已知有N个结点的无向图，采用邻接表结构存储，要求对每个连通子图中一个生成树中的各条边逐层输出，边的输出格式为（ki，kj）。七、编写算法（25分）1.写出建立二叉树，二叉链表存储结构的算法。（10分）2.已知二叉树采用二叉链表方式存放，要求对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，左孩子编号小于右孩子编号。给出在二叉树中结点的数据域部分填写，实现如上要求编号的非递归算法。（10分）3.已知二叉树采用二叉链表方式存放，给出判定它是否为一。大连理工大学2008年考研数据结构试题考研_考试大[2008/11/3]来源：考研教育网一、选择题1.线性表的————运算中，顺序存储结构比例链式存储结构好。A.插入B.删除C.按号查找D.按元素值查找2.此程序的复杂度为————for（inti=0；iM； I++）for（intj=0；jN； 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，当n50，m5时，时间复杂度最佳的为————：A.快速排序B.归并排序C.基数排序D.直接插入排序5.顺序查找长度为n的顺序表，查找成功的平均检索长度为————：A.nB.n/2C.（n-1）/2D.（n+1）/26.一颗二叉树，头序序列为ABCDEFG，中序序列为CBDAEGF，后序为————A.CDBGFEAB.CDBFGEAC.CDBAGFED.BCDAGFE7.一颗度为3的树，度为3的节点为三个，度为2的节点为1个，度为1的节点1个，度为0的节点————个（考试大）。A.6B.7C.8D.98.m阶B—树中，某一节点插入一个新关键字引起破裂，则该节点原有关键字————个。A.|—m/2—|B.|—m/2—|-1C.mD.m-1E.|—m/2—|F.|—m/2—|-19.两个长度为n的递增有序表，合并成一个长度为2n的递增有序表，最少需要进行关键字比较————次。A.1B.n-1C.nD.2n10.有向图G，n个顶点，邻接矩阵存储于二维数组中，顶点i的度为————.A.（i=0n-1）∑A[i][j]B.（j=0n-1）∑A[i][j]C.（i=0n-1）∑A[i][j]+（j=0n-1）∑A[i][j]D.（j=0n-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，1103．实现图的广度优先搜索算法时，使用的数据结构是（）①栈②队列③十字链表④三元组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?（2）给定结点x的编号m，又如何根据该编号断定x是否为叶结点？3．当查找表有既能较快查找又能适应动态变化的需求时，选用什么查找方法最适合？并简述其理由。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↑.nextQ)DOP：=P↑.next；⑥S↑.next：=P↑.next；⑦S↑.next：=L↑.next；五、算法题（共15分）1．设p,q分别指向两个不带头结点的单循环链表中的某个结点，试编写一个算法，用O(1)时间将这两个单链表合并为一个，并令p指向p和q两者data域值较小的结点。（5分）PROCxyz(p,q)；{p,q分别指向两个不带头结点的单循环链表中的某个结点,结点结构为数据域data和指针域next}ENDP；2．设二叉树采用二叉链表存储，结点结构为lchild、data和rchild，试编写输出二叉树中从根结点到每个叶结点的路径的算法。设二叉树最长路径结点个数小于m，可以使用队列S[1：m]，初始时S.rear=S.front=1。（10分）PROCRootToLeaf(bt：bitreptr)；{bt为二叉树根指针，S[1：m]为队列,初始时S.rear=S.front=1}ENDP；{RootToLeaf}南京林业大学2003年C程序设计考研试题考研推荐给好友收藏本页2006/11/21保存本文一.选择题(40分)1..当c的值不为0时，在下列选项中能正确将c的值赋给变量a、b的是______Ac=b=a；B(a=c)‖(b=c)；C(a=c)&&(b=c)；Da=c=b；2.在C语言中，不正确的int类型的常数是________A32768B0C037D0xAF3.以下程序的输出结果是________main(){inta=-1，b=1，k；if((++a0)&&!(b--=0))printf(%d%d\n，a，b)；elseprintf(%d%d\n，b，a)；}A-11B01C10D004.在C语言类型中,int,char,short等类型的长度是_________A.固定的B.由用户自己定义C.任意的D.与机器字长有关5.设a=1,b=2,c=3,d=4,则表达式:aA4B3C2D16.下列说法错误的是______________A.结构体变量可以被整体赋值.B.可以取结构体变量的地址C.可以取结构体变量成员的地址D.结构体类型的成员可以定义成该结构体类型的指针类型7.设有如下定义：intx=l，y=-1；，则语句：printf(%d\n，(x--&++y))；的输出结果是____A1B0C-1D28..设有程序段:t=6;a=7;b=8;if(a=b)t=a;,这段程序执行后,t的结果是______A.6B.7C.8D.09.下列描述中不正确的是________A)字符型数组中可以存放字符串B)可以对字符型数组进行整体输入、输出C)可以对整型数组进行整体输入、输出D)不能在赋值语句中通过赋值运算符=对字符型数组进行整体赋值10.若a为二维数组,它有m列,则a[i][j]在数组中的位置是_________A.i*m+jB.j*m+iC.i*m+j-1D.i*m+j+111.下列语句中符合C语言语法的赋值语句是__________Aa=7+b+c=a+7;Ba=7+b++=a