2022年数据结构与历年真题知识 .pdf
《2022年数据结构与历年真题知识 .pdf》由会员分享,可在线阅读,更多相关《2022年数据结构与历年真题知识 .pdf(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(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,解决
3、冲突用线性探测再散列法,要求构造哈希表,求出等概率下查找成功查找长度。4.已知一棵二叉树,中序序列 DBCAFGE,后序序列 DCBGFEA,构造该二叉树。5.给定权值 8,12,4,5,26,16,9,构造一个哈夫曼树,并计算其带权路径长度。四、编写程序(15 分)建立线形表,(a1,a2,a3。,an)的单链表存储,并实现其就地逆置为(an,an-1a2.,a1)。五、编写程序(10 分)在中序线索树中,要找出结点的前驱结点,请写出相关函数定义。Ltag Lc Data Rtag Rc 六、编写算法(20 分)已知有 N个结点的无向图,采用邻接表结构存储,要求对每个连通子图中一个生成树中的
4、各条边逐层输出,边的输出格式为(ki,kj)。七、编写算法(25 分)名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页,共 18 页 -1.写出建立二叉树,二叉链表存储结构的算法。(10 分)2.已知二叉树采用二叉链表方式存放,要求对二叉树从1 开始进行连续编号,要求每个结点的编号大于其左右孩子的编号,同一结点的左右孩子中,左孩子编号小于右孩子编号。给出在二叉树中结点的数据域部分填写,实现如上要求编号的非递归算法。(10 分)3.已知二叉树采用二叉链表方式存放,给出判定它是否为一。大连理工大学2008 年考研数据结构试题考研_考试大 2008/11/3 来源:考研教育网一、选择题1.线
5、性表的运算中,顺序存储结构比例链式存储结构好。A.插入B.删除C.按号查找D.按元素值查找2.此程序的复杂度为for(int i=0;iM; I+)for(int j=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,后序为 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页,共 18 页 -A.CDBGFEA B.CDBFGEA C.
6、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-
7、1)Aij B.(j=0 n-1)Aij C.(i=0 n-1)Aij+(j=0 n-1)Aij D.(j=0 n-1)(Aij+Aji)二、问答题1.(6)n 阶对称阵(aij)n n,采用压缩存储存放于一维数组 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,请写出用线性探测法处理冲突构造所得的哈希表。并求出在等概率情况下,
8、查找成功时的平均检索长度。4.(6)给定一个由 n 个关键字不同的记录构成的序列,你能否用比 2n-3 少的比较次数找出 n 个元素中的最大值和最小值?如果有,请描述你的方法。最快需要多少次比较?(无需写算法)三、用类 C 语言完成设计1.(15)什么是堆?设计算法判定给定的存于数组 r 中的 n 个数据是名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页,共 18 页 -否为堆。2.(15)设 u、v 是有向图的两个顶点,设计算法判读有向图中是否存在从顶点 u 到 v 的长度为 k 的简单路径。要求给出图的存储形式及其类型定义。3.(10)设二叉树以二叉链表形式存放。一颗二叉树的繁茂程
9、度定义为各层节点数的最大值与树的高度的乘积。试设计一个高效算法,求二叉树的繁茂程度。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,
10、96,88,110 3 实现图的广度优先搜索算法时,使用的数据结构是()栈 队列 十字链表 三元组4在有向图 G的邻接矩阵中,顶点Vi 的度是()。邻接矩阵中第 i 行元素之和 邻接矩阵中第 i 列元素之和 邻接矩阵中第 i 行和第 i 列元素之和 邻接矩阵中第 i 行元素之和与第i 列元素之和的最大值5能有效缩短关键路径长度的方法是()缩短任意一个活动的持续时间 缩短关键路径上任意一个关键活动的持续时间 缩短多条关键路径上共有的任意一个关键活动的持续时间 缩短所有关键路径上共有的任意一个关键活动的持续时间名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页,共 18 页 -二、填空题(每
11、空 2 分,共 8 分)1 由一棵二叉树的后序序列和可唯一确定这棵二叉树。2 二叉树结点数 n 与边数 e 的关系为。3 在各种查找算法中,平均查找长度与关键字个数 n 无关的方法是。4 若希望得到树高较矮的生成树,则采用图的遍历算法。三、判断题(用表示对,用表示错。每题 2 分,共 12 分)1 循环队列中不存在队列满的问题。()2 将一个新结点插入到二叉排序树中,该结点一定成为叶结点。()3 用单链表示的有序表可以使用折半查找方法来提高查找速度。()4 若有向图中每个顶点的入度和出度均为 1,则该有向图必有回路。()5 已知二叉排序树的先序序列,能唯一确定该二叉排序树。()6 交换完全二叉
12、树所有结点的左右子树,得到的二叉树仍是完全二叉树。()四、简答题(每题 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,试为各字符设计二进制编码,使
13、得报文编码长度最短。给出各字符的二进制编码和报文编码长度。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;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页,共 18 页 -五、算法题(共
14、 15 分)1 设 p,q 分别指向两个不带头结点的单循环链表中的某个结点,试编写一个算法,用 O(1)时间将这两个单链表合并为一个,并令p 指向 p 和 q 两者 data域值较小的结点。(5 分)PROC xyz(p,q);p,q分别指向两个不带头结点的单循环链表中的某个结点,结点结构为数据域 data 和指针域 next ENDP;2 设二叉树采用二叉链表存储,结点结构为 lchild、data 和 rchild,试编写输出二叉树中从根结点到每个叶结点的路径的算法。设二叉树最长路径结点个数小于 m,可以使用队列 S1:m,初始时 S.rear=S.front=1。(10 分)PROC R
15、ootToLeaf(bt:bitreptr);bt为二叉树根指针,S1:m为队列,初始时 S.rear=S.front=1 ENDP;RootToLeaf 南京林业大学2003 年 C 程序设计考研试题考研推荐给好友收藏本页2006/11/21 保存本文一.选择题(40 分)1.当 c 的值不为 0 时,在下列选项中能正确将c 的值赋给变量a、b 的是 _ A c=b=a;B(a=c)(b=c);C(a=c)&(b=c);D a=c=b;2.在 C 语言中,不正确的int类型的常数是_ A 32768 B 0 C 037 D 0 xAF 3.以下程序的输出结果是_ main()int a=-1
16、,b=1,k;if(+a0)&!(b-100)break;B.for(;);C.int k=0;do+k;while(k=0);D.int s=36;while(s);-s;14.下列表达式中,错误的是 _.A.21?a:b B.i+j C.4.0%2.0 D.x*=y+8 15.a,b为整数且b!=0,则表达式(a/b)*b+a%b的值为_的值.A.a B.b C.a被b除的余数部分 Da被b除商的整数部分16.若以数组元素作为函数的实参,则实参向形参传送的是_.A.数组元素的地址 B.数组元素的值 C.数组的首地址 B.数组名17.设有如下的共用体定义:union data int i;名
17、师资料总结-精品资料欢迎下载-名师精心整理-第 7 页,共 18 页 -long b;float f;a;则 a 所占的内存单元为_个字节.A.4 B.6 C.8 D.10 18.语句:printf(%d,(a=2)&(b=-2);的输出结果是_ A 无输出 B 结果不确定 C-1 D 1 19.下列选项中不是C语言main函数正确表达形式的是_?A.main(int argc,char*argv);B.main(ac,av)int ac;char*av;B.main(c,v)int c;char*v;D.main(argc,argv)int argc;char argv;20.执行 for(
18、j=1;j+4;);语句后变量j 的值是 _ A.3 B.4 C.5 D.不定二.填充(20 分)1.C 语言的数据类型中,构造类型包括:数组,_和_.2.设 x,y,z,t 均为 int 型变量,则执行以下语句后,t 的值为 _ x=y=z=1;t=+x|+y&+z;3.C 语言的运算符要确定的两个方面分别是_和_.4.在函数内使用static是_,在函数外使用static是_。5.对于语句:scanf(%3d%3d,&a,&b);,若输入 123456,则 a和 b 的值分别为 _和_.6.?设有二维数组 int?a22,*p;,则 aIj 三种其他表示是_,_,_。7.字符串的长度是_,
19、它的存储空间大小是_。8.静态变量赋初值是_赋值,动态变量赋初值是_赋值。9.链表中每个结点至少应包括二个部分,它们是_和_.10.用数组名作函数参数时,形参和实参的结合是采用_,?因为数组名是数组的 _.三.程序分析题(20 分)1.阅读下面程序,给出输出结果。main()int i,j,k;for(i=1;i10;i+)printf(“n”);if(i=5)for(j=1;j=i;j+)名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页,共 18 页 -for(k=1;k=5-i;k+)printf(“”);printf(“*“);else for(j=1;j=10-i;j+)for
20、(k=1;k=i-5;k+)printf(“”);printf(“*”);2.阅读下面程序,指出函数所实现的功能。void ins(char s,int start,char t)int m,n,i,k;n=0;m=0;for(i=0;si!=?0?;i+)m+;for(i=0;ti!=?0?;i+)n+;for(k=1;k for(k=start;k sk=tk-start;sm+n=?0?;3.阅读下面程序,指出下面程序所完成的功能void st(char*a ,int n)int i,j,k;char*m;for(i=1;i m=ai;k=i;for(j=i+1;j0),k=j;)m=a
21、i;ai=ak;ak=m;for(i=1;i=n;i+)printf(“%s”,ai);4.分析以下程序:#include“string.h”;main()char c,string81;int i,a=0,b=0;gets(string);for(i=0;(c=stringi)!=?0?;i+)名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页,共 18 页 -if(c=?)a=0;else if(a=0)a=1;b+;printf(%dn,b);该程序的作用是_.若输入:a b c,则程序运行后,?输出结果为 _,且c的值为_,a的值为_.5.阅读下面程序,指出函数所实现的功能。vo
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年数据结构与历年真题知识 2022 数据结构 历年 知识
限制150内