数据结构精选考研试题

1、数据结构精选考研试题注:编写程序可选用任一种高语言,算法描述可采用类语言,必要时加上注释一、答复以下问题：20分1、算法的定义和性质2、为什么说数组与广义表是线性表的推广？3、 什么是结构化程序设计？4、哈希方法的根本思想5、给出一不稳定排序方法名称与实例二、构造结果：24分确定x:=x+1语句在下面程序段中的频率,要求写出分析过程.fori:=1tondoforj:=1的判定树,并求其在等概率时查找成功的平均查找长度.一棵二叉树如右图,给出对这棵二叉树进行前序、中序、后序遍历的结果序个字母组成,字母在电文中出现的频率toIdo画出对长度为fork:=1tojdox:=x+1的有序表进行折半查

2、找列假设用于通讯的电文仅输入序列为:1,8,4,3,0六、分别为2,3,5,7,11,4,13,15,码.在地址空间为015的散列区中,对以下关键字序列构G造哈希表,关键字序列为,H(x尸i/2,其中i为关键字中第一字母在字母表中的序号.要求用线性探测开放定址法处理冲突,并求出在等概率情况下查找成功的平均查找长度.构造有7个元素组成的线性表一实例,是进行快速排序时比拟次数最少的初始排序.三、写一算法,完成对这棵二叉树的左右子树的交换,设二叉树以二叉链表作存储结构.15分四、编写一非递归算法,对一棵二叉排序树实现中序遍历.15分五、编写程序,完成以下功能：15分1.读入整数序列,以整数0作为序列

3、的结束标志,建立一个单链表.2.实现单链表原地逆转,即单链表中结点指针方向反转,反转操作不使用额外的链表结点,可使用临时工作单元.例:试为这个字母设计哈夫曼编给出有向图G的邻接表表示.找出其一棵最小生成树.11分注:编写程序可选用任一种高语言,算法描述可采用类语言,必要时加上注释一、 答复以下问题：20分1、算法的定义和性质2、为什么说数组与广义表是线性表的推广？3、什么是结构化程序设计？4、哈希方法的根本思想5、给出一不稳定排序方法名称与实例二、构造结果：24分 确定x:=x+1语句在下面程序段中的频率,要求写出分析过程.fo门:=1tondoforfork:=1tojdox:=x+1的有序

4、表进行折半查找的判定树,并求其在等概率时查找成功的平均查找长度.一棵二叉树如右图,给出对这棵二叉树进行前序、中序、后序遍历的结果序个字母组成,字母在电文中出现的频率j:=1toIdo画出对长度为列假设用于通讯的电文仅分别为2,3,5,7,11,4,13,15,试为这个字母设计哈夫曼编码.在地址空间为015的散列区中,对以下关键字序列构G造哈希表,关键字序列为,H(x尸i/2,其中i为关键字中第一字母在字母表中的序号.要求用线性探测开放定址法处理冲突,并求出在等概率情况下查找成功的平均查找长度.构造有7个元素组成的线性表一实例,是进行快速排序时比拟次数最少的初始排序.三、写一算法,完成对这棵二叉

5、树的左右子树的交换,设二叉树以二叉链表作存储结构.15分四、编写一非递归算法,对一棵二叉排序树实现中序遍历.15分五、编写程序,完成以下功能：15分1.读入整数序列,以整数0作为序列的结束标志,建立一个单链表.2.实现单链表原地逆转,即单链表中结点指针方向反转,反转操作不使用额外的链表结点,可使用临时工作单元.例:给出有向图G的邻接表表示.找出其一输入序列为:1,8,4,3,0六、棵最小生成树.11分注编写程序可选用PASCAL或C语言算法描述采用类语言,应加上必要的注释所有答案均要求写在做题纸上一、答复以下问题15分1.结构化程序设计2.面向对象开发方法与面向过程开发方法的不同之处3.数据类

6、型含义与作用4.稳定排序与不稳定排序二、简述方法与原因20分1.分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递增序列的表按递增顺序排序,给出最省时间与最费时间的算法名称,简述原因.2.实现有向图的拓扑排序能否用图的深度搜索模式来查找？假设能请简述方法,假设不能,请简述原因.3.有n个非零的数,仅要求将负数排列在正数的前面,但并不要求对其排序,简述处理方法.4.说明在图的遍历中,设置访问标志数组的作用.5.在一个连通无向图上,欲求从一点VI到另一点VJ所经结点数目最少的路径,在深度优先搜索、广度优先搜索、从一精选公文范文,治理类,工作总结类,工作方案类文档,感谢阅读下载5点到

7、其余各顶点的最短路径或图的其它算法中,你认为最好选择那种方法为基础,简述原因.三、构造结果25分1.二叉树按二叉链表方式存放,其中的data域为char类型,已有按前序方式构造二叉树的算法,假设输入序列为ABOCEEDEDZGDC,Di青给出构造的相应二叉树.2.Ackerman函数定义如下：n+1当m=0时akm(m,n)=akm(m-1,1)当 廿0,n=0时akm(m-1,akm(m,n-1)当0,n#时写出akm(2,1)时调用时变化过程与执行结果.3.对于正整数A、B,说明下面程序段定义了什么函数功能,要求重写程序段,使之完成原函数功能,且执行时间仅可能短.Unsignedintf(

8、a,b)inta,b;if(a*b=0)return(a+b)elsereturn(f(b-(b/a)*a,a);(注：b/a相当整除)4.写出在中序线索树BT中找结点X的精选公文范文,治理类,工作总结类,工作方案类文档,感谢阅读下载6后继结点的函数过程.5.对以下关键字序列建立哈希表,哈希函数为H=关键字中第一个字母在字母表中的序号MOD7,用线性探测再散列法或链地址法之一处理冲突,要求构造一个装填因子为的哈希表,并求出等概率情况下查找成功与不成功的平均查找长度.四、有二叉排序树采用二叉链表方式存放,树中结点值各不相同,欲得到一个大到小的结点值递减序列,简述处理方法思路,用非递归形式写出算法

9、.10分1.一棵树采用孩子-兄弟方式存放,结点结构为fchdansletaibvel其中fch表示指向第一个孩子,nisib表示指向下一个兄弟,level表示结点层次.设根结点层次为1,其它以此类推,编写一算法,将树中所有结点层次值置入相应level域.10分六、以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度.10分七、编写程序,要求精选公文范文,治理类,工作总结类,工作方案类文档,感谢阅读下载7完成：建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位.在此链表上实现对二进制数加1的运算,并输出运算结果

10、.分10注:编写程序可用PASCAL或C语言；算法描述可采用类语言,加上必要注释；一、解释和简答以下问题：1算法的定义和特性2抽象数据类型3广义表与字符串属于线性表的理4封装5排序算法的稳定性6结构化程序设计二、写出要求结果：1.一二叉树中序序列为DBGEAFC,后序序列为DGEBFCA,给出其对应的二叉树.2.给造一棵带权路径长度最短的二叉树,并性表,要求重新排列,使所有的正数均在非正数之前,要求用最小交换次数实现,你认为应采用什么方法？定权值8,12,4,5,26,16,9,构计算其带权路径长度4.只想得到N个元素序列中第K个最大元素之前的局部递减有序序列,列出3种速度快的方法名称与原因.

11、5.在地址空间为012的散列区中,对以下关键字序列建哈希表：.用线性探测法处理冲突,求出在等概率的情况下查找成功与不成功的平均查找长度.6.下面给出求N价hanoi塔的过程：PROCEDUREhanoi(n：integer；x,y,z：char);beginifn=1thenmove(x,1,z)elsehanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z)end请写由执行hanoi(3,a,b,c)0寸递归过程的实在参量变化过程及move的搬动过程.三、数学归纳法证实非空满K叉树的叶子结点数目为(K-1)N+1,其中N为分支结点数目.四、 编写程序,判断一

12、带头结点的双向链表是否对称,对称是指表中各元素满足ai=an-i+1结点结构为如下：(10分)nextdadaprior五、有一个英文书目构成的文件；读入该文件,对这一书目单按字典排序,将结果以文件方式存储.编程实现之.六、二叉树按链表方式存放,且树中结点的关键字均不同.写一个判别给定二叉树是否为二叉排序树的非递归算法.写一个算法,确定一个N个顶点的无向图是否包含回路,此算法的时间代价应为O注:编写程序可选用盘Pascal或C语言,算法描述可选用类语言,必要时加上注释一、简答以下问题：1.结构化程序设计2.参数传递的常用方式及含义3.数据类型4.几种根本数据结构的名称及特征5.算法定义与性质6

13、.二、写出要求结果1.PROGRAMPF(OUTPUT);VERT,M:INTEGER;FUNCTIONF(N:INTEGER):INTEGER;BEGINM:=N+M;F:=MENDBEGINM:=10;T:=(M+1)*F(10);WRITELN(T);M:=10;T:=F(10)*(M+1);WRITELN(T);M:=10;T:=M*F(10)+F(10);WRITELN(T);END.写出程序输出结果,说明为什么T的树出结果不同.2.有过程定义如下：PROCEDUREPRIT(N:INTEGER);BEGINVARN1:INTEGER;N1:=TRUNC(N/10);TRUNC(x)

14、表示取x的整数局部 S:=S*10+(NMOD10);IFN10THENPRIT(N1);WRITELN(NMOD10)END;问：置S初值为0,用PRIT调用此过程,写出打印结果； 当执行完此次调用后,S值是多少？3.给定一组权值,构造一棵哈夫曼树,并计算带权路径长度.4.将树转换成 二叉 树5.对给 定以 下关键 字序列(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug),哈希函数H为Key的第一字母表中序号MOD7,采用线性探测再散列方法处理冲突,要求：构造一个装填因子为的哈希表求出等概率情况下查找成功与查找不成功的平均查找长度6.在m行n列的稀疏矩阵中,有七个非零元素,假

15、设用十字链表表示,共需要多少个结点？精选公文范文,治理类,工作总结类,工作方案类文档,感谢阅读下载11三、编写一程序,要求打印以下的杨辉三角形10分111121n行133114641151010512161520151:四、一个数组中元素为正数或负数,编写一程序,完成在On时间内原地重排数组,不要求整个排序,只要求负数排在正数之前.10分五、二叉树按二叉链表方式存放：编写统计任一二叉树中非终端结点数目的非递归算法10分编写求一二叉树高度的递归算法.5分六、设有向图以邻接表方式存储,请利用队列技术编写一个判别图中是否存在顶点Vi到顶点Vj路径的算法.12分七、有如下单链表,n为偶数.要求写出一个

16、时间复杂度为On,辅助空间为0(1)的算法,将上述链表转换成：即注:编写程序可选用任一种高级语言一、简答问题：15分1.结构化程序设计；2.简述面向对象开发方法的特点；3.何谓程序中的千年虫问题,简述一种解决问题的方法；4.给出抽象数据类型和特征,并举例说明；5.简述广义表属于线性结构的理.二、写出要求结果45分1.有函数定义如下：FUNCTIONGC(M,N:INTEGER);INTEGERBEGINIFN=0THENGC:=MELSEGC:=GC(N,MMODN)END写出此函数功能,并改写它,使其执行速度仅可能地短.2.设T、M为全程量,有函数定义如下：FUNCTIONFA(N:INTE

17、GER):INTEGERBEGINM:=N+M;FA:=M;END在主程序段中,有如下语句：M:=10;T:=(M+2)*FA(10);WRITELN(T);M:=10;T尸FA(10)*(M+2);WRITELN(T);写出程序输出结果,说明为什么T的输出结果不同的原因.3.对以下关键字序列建立哈希表： ,哈希函数为H(K尸MOD7.用线性探测法处理冲突,要求构造一个装填因子为的哈希表,并分别计算出在等概率情况下查找成功与不成功的平均查找长度.4.在数轴上有N个彼此相邻不交的区间,每个区间的下界和上界都是整数.N个区间顺序为1No要查找给定的X落入的区间号,你认为应怎样组织数据结构,选择什么

18、方法最快,并简述原因5.对N个元素组成的线性表进行快速排序时,所需进行的比拟次数依赖于这N个元素的初始排列,对N=7,给出快速排序的一个最好情况的初始排列实例.6.在前序线索树上,要找出结点P的 直 接 后 继 结 点 , 请 写 出 相 关 语句.ltaglcdatartagrc7.给出循环队列中元素个数的计算式.8.有向图的拓扑排序能否用图的深度搜索模式来查找？假设能,请简述方法,假设不能,请简述原因.9.写出三个形如A:=B的语句,完成将单链表LA整表释放的功能,可利用链栈指针AVo三、编写程序,统计在输入字符串中各个不同字符出现的频度并将结果存入文件10分四、两个线性表A、B,均以带头

19、结点的单链表作存储结构,且表中元素按值递增有序排列.设计算法,求出A与B的交集C,要求C另开辟存储空间,要求C同样以元素值的递增有序的树按二叉链表形式存储.写一个建立二叉树的算法.答案请答在做题纸上,答在本试题上的答案一律无效注编写程序可选用PASCAL或C语言算法描述采用类语言,算法应加上必要的注释,所有答案均要求写在答题纸上一、简答问题：30分1.结构化程序设计2.面向对象程序设计与面向过程程序设计各自的特点与区别3.简述队列与广义表属于线性表的理4.简述不稳定排序含义、并给出证实某一种排序方法是不稳定的排序方法5.函数的副作用二、选择题：20分1.下面方法可以判断出一个有向图中是否有环A

20、.深度优先遍历B.拓扑排序C.最短路径D.关键路径2.一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为.A.小+B*C/DEB.八+B*CD/EC.-+*ABC/DED.-+A*BC/DE3.假设二叉树采用二叉链表存储结构,要交换其所有分支结点左右子树的位置,利用遍历方法最适宜.A.前序B.中序C.后序D.按层次4.排序趟数与序列的原始状态有关的排序方法是排序法.A.插入B.选择C.冒泡D.快速5.下面给出的四种排序法中排序法是不稳定性排序法.A.插入B.冒泡C.二路归并D.堆6.假设需在O的时间内完成对数组的排序,且要求排序是稳定的,那么可选择的排序方法

21、是：A.快速排序B.堆排序C.归并排序D.直接插入排序7.下述二叉树中,满足性质： 从任一结点出发到根的路径上所经过的结点序列按其关键字有序A.二叉排序树B.哈夫曼树C.AVL树D.堆8.以下排序算法中,算法可能会出现下面情况：初始数据有序时,花费时间反而最多.A、堆排序B、冒泡排序C、快速排序D、SHELL排序9.设循环队列中数组的下标范围是1n,其头尾指针分别为f,r,假设队列中元素个数为.A、r-fB、r-f+1C、modnD、modn10.假设一个有向图的邻接矩阵中,主对角线以下的元素均为零,那么该图的拓扑有序序列A、存在B、不存在三、写出要求结果：50分1.以下C与PASCAL函数的

22、功能相同有如下C函数定义：有如下PASCAL过程定义：voidbin(intb,intn)PROCEDUREbinBEGINif(n=1)b1=1;b2=1;if(n=1)b1=1;b2=1;elsebin(b,n-1);elsebin(b,n-1);bn+1=1;bn+1=1;For(i=n;i=2;i-)Fori=ndownto2dobi=bi+bi-1bi=bi+bi-1END假设调用bin(A,5),给出A数组中第1个至第6个数组元素的输出结果.2.给出求N阶hanoi塔的函数定义如下：hanoi(intn,charx,chary,charz);if(n=1)move(x,1,z)el

23、sehanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z)请写出执行hanoi(3,a,b,c对递归函数的实在参量变化及move的搬动过程.3.已知一个循环单链表la,av是可利用栈的头指针,请用3个赋值语句,完成将整个循环单链表释放的功能.4.在地址空间为0-12的散列区中,对以下关键字序列：建哈希表,设哈希函数为H=i/2,其中i为关键字中的第一个字母在字母表中的序号,处理冲突可选用线性探测法或链地址法之一,要求构造哈希表,并求出在等概率的情况下查找成功与不成功的平均查找长度.5.在排序连续顺序文件中采用折半查找方法查找记录存在与否的过程可以借助于一棵折

24、半判定树来模拟,树中结点的值为记录在文件中的位置序号.假设文件中有l7个记录,请画出这棵折半判定树；当文件中有n个记录时,给出该判定树的深度.6.设某城市有N个车站,并有M条公交线路连接这些车站,设这些公交车都是单向的,这N个车站顺序编号为0至N-1,要求输入该城市的公交线路数、车站个数以及各公交线路上各站编号,要求从站0出发乘公交车至站N-1的最少换车次数,简述应如何设置数据结构、应当采用的根本处理方法.注编写程序可选用PASCAL或C语言算法描述采用类语言,应加上必要的注释所有答案均要求写在做题纸上一、答复问题15分1.结构化程序设计2.面向对象开发方法与面向过程开发方法的不同之处3.数据

25、类型含义与作用4.稳定排序与不稳定排序二、简述方法与原因20分1.分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递增序列的表按递精选公文范文,治理类,工作总结类,工作方案类文档,感谢阅读下载19增顺序排序,给出最省时间与最费时间的算法名称,简述原因.2.实现有向图的拓扑排序能否用图的深度搜索模式来查找？假设能请简述方法,假设不能,请简述原因.3.有n个非零的数,仅要求将负数排列在正数的前面,但并不要求对其排序,简述处理方法.4.说明在图的遍历中,设置访问标志数组的作用.5.在一个连通无向图上,欲求从一点VI到另一点VJ所经结点数目最少的路径,在深度优先搜索、广度优先搜索、从一

26、点到其余各顶点的最短路径或图的其它算法中,你认为最好选择那种方法为根底,简述原因.三、构造结果25分1.二叉树按二叉链表方式存放,其中的data域为char类型,已有按前序方式构造二叉树的算法,假设输入序列为ABDCDEEDDG口诵给出构造的相应二叉树.2.Ackerman函数定义如下：n+1当m=0时akm(m,n)=akm(m-1,1)当廿0,n=0时精选公文范文,治理类,工作总结类,工作方案类文档,感谢阅读下载20akm(m-1,akm(m,n-1)当m0,nw 田寸写出akm(2,1)时调用时变化过程与执行结果.3.对于正整数A、B,说明下面程序段定义了什么函数功能,要求重写程序段,使

27、之完成原函数功能,且执行时间仅可能短.Unsignedintf(a,b)inta,b;if(a*b=0)return(a+b)elsereturn(f(b-(b/a)*a,a);(注：b/a相当整除)4.写出在中序线索树BT中找结点X的后继结点的函数过程.5.对以下关键字序列建立哈希表,哈希函数为H=关键字中第一个字母在字母表中的序号)MOD7,用线性探测再散列法或链地址法之一处理冲突,要求构造一个装填因子为的哈希表,并求出等概率情况下查找成功与不成功的平均查找长度.四、有二叉排序树采用二叉链表方式存放,树中结点值各不相同,欲得到一个大到小的结点值递减序列,简述处理方法思路,用非递归形式写出算

28、法.10分五、一棵树采用孩子-兄弟方式存放,结点结构为fchdatansiblevel其中fch表示指向第一个孩子,nisib表示指向下一个兄弟,level表示结点层次.设根结点层次为1,其它以此类推,编写一算法,将树中所有结点层次值置入相应level域.10分六、以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度.10分七、编写程序,要求完成：建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位.在此链表上实现对二进制数加1的运算,并输出运算结果.10分注编写程序可选用Pascal或C语言,算法描述采用类语言1997年 一、简答以下问题：15分1.结构化程序设计目的、结构、方法2.面向对象程序设计语言的特征3.程序测试目的及程序可能存在的错误类型4.常用的参数传递方式的名称与作用5.为什么说数组和广义表是线性表的推广二、写出要计算其带权路径长度.2.有一组43,采用堆排序方法,请写出每趟排序结果.3.在后序线索树中,要找出结点P的前趋结点,请写出有关语句LtagLcdataRtagRc4.快速排序方法中,能否用队列代替栈,请简要说明理.5.设有关键字序列函数H(K尸Kmod7,用线性探测再散列方法处理冲突,要求构造一个装填因子为的哈希表,并分别计算出在等概率情况下查找成功与查找不成功的平均查找