东北师范大学生物学《加试Python程序语言及应用之数据结构》考研复试仿真模拟5套卷.pdf

灵博阅考研专业课资料学长一对一诚招加盟目录【复试】2023年东北师范大学071000生物学加试:Pyth on程序语言及应用之数据结构考研复试仿真模拟5套卷（一）.4【复试】2023年东北师范大学071000生物学加试:Pyth on程序语言及应用之数据结构考研复试仿真模拟5套卷（二）.14【复试】2023年东北师范大学071000生物学加试:Pyth on程序语言及应用之数据结构考研复试仿真模拟5套卷（三）.24【复试】2023年东北师范大学071000生物学加试:Pyth on程序语言及应用之数据结构考研复试仿真模拟5套卷（四）.37【复试】2023年东北师范大学071000生物学加试:Pyth on程序语言及应用之数据结构考研复试仿真模拟5套卷（五）.49第3页，共60页灵博阅考研专业课资料学长一对一诚招加盟【复试】2023年东北师范大学071000生物学加试:Python程序语言及应用之数据结构考研复试仿真模拟5套卷(一)，。一、单项选择题1.线性链表中各链接点之间的地址_A.必须连续B.部分地址必须连续C.不一定连续D.和头结点的存储地址相连续【答案】C【解析】线性链表结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是 连续的，也可以是不连续的。所以线性链表中各链接点之间的地址不一定连续。2.对10TB的数据文件进行排序，应使用的方法是_。A.希尔排序B推排序C.快速排序D.归并排序【答案】D3.对给定的关健字序列U0,119,007,911,114,120,122进行基数排序，则第二趟分配收集后得到的关键 序列是_A.007,110,119,114,911,120,122B.007,110,119,114,911,122,120C.007,110,911,114,119,120,122D.110,120,911,122,114,007,119【答案】C【解析】基数排序的第一趟排序是按照个位数字来排序的，第二趟排序是按照十位数字的大小进行排 序的。4.以下序列不是堆的是_oA.Q00,85,98,77,80,60,82,40,20,10,B.(100,98,85,82,80,77,66,60,40,20,C.(10，20,40,60,66,77,80,82,85,98,D.(100,85,40,77,80,60,66,98,82,10,【答案】D5.用不带头结点的单链表存储队列时，其头指针指向队头结点，其尾指针指向队尾结点，则在进行删除 操作时_O的00)20A.仅修改头指针B.仅修改尾指针第4页，共60页圉V簟心博阅”handebooksm 考研专业课资料学长一对一诚招加盟C.头、尾指针都要修改D.头、尾指针可能都要修改【答案】D【解析】当链表中不止一个元素时，只需要修改头指针；当链表中只有一个元素时，就需要将头指针 和尾指针都赋值为空。6.一棵度为4的树T中，若有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个度为1 的节点，则树T的叶子节点个数是_0A.41B.82C.113D.122【答案】B【解析】树T中只能有度为0、1、2、3、4的节点。n fo+m+n z+n j+M,度之和,又有度之和=lxn 1+2xn 2+3xn 3+4xn 4=lx 0+2xl+3x10+4x20=122,贝(Jn=l 22+1=123,n o=n-n i-n 2-n3-n 4=123-41=82O 本题答 案为B7.关于计算机算法特性的描述正确的是_o(1)算法至少有一个输入和一个输出算法至少有一个输出但是可以没有输入算法永远可以运行下去A.(l)B。)53)D.和(3)【答案】B【解析】一个算法可以有输入，也可以没有输入，但必须有输出。算法的特性之一为有穷性，所以算 法不允许无限制地运行下去。8.以下程序段的输出是_。#include void fun()(static int a=5;a+;printf(a=%dn,a);)main()(for(int i=0;i9398455306208179859配分271收集306 208第三次分配和收集后：99|-33 859 271 f 179 f 984 f 93 06379M e分2 e984网9 C,JLT司 61 仃收集9 旧 33 E 55 T 93 T 179 T 208 306 f 859配 分AA图基数排序全过程17.假设二叉树以二叉链存储结构存储，设计一个算法，判断一棵二叉树是否为完全二叉树。【答案】根据完全二叉树的定义，对完全二叉树进行层次遍历时应该满足以下条件。若某节点没有左孩子，则一定无右孩子。若某节点缺左或右孩子，则其所有后继一定无孩子。若不满足上述任何一条,均不为完全二叉树。对应的算法如下。i n t CompBTNod e(BTNod e*b)BTNod e*Qu MaxSi ze,*p;/定义一个循环队列，用于层次遍历第7页，共60页i n t fron t=Cr rear=0;i n t c m=l;i n t bj=l;i f(b!=NULL)rear=(rear+1)%MaxSi ze;Qurear=b;wh i le(fron t!=rear)fron t=(fron t+1)%MaxSi ze;p=Qufron t;i f(p-lc h i lc=NULL)bj=O;考研专业课资料学长一对一诚招加盟循环队列首尾指针/c m=l表示二叉树为完全二叉树/bj=l表示到目前为止所有节点均有左右孩子/队列不空/出队/*p节点没有左孩子(p-rc h i Id!=NULL)c m=0;/没有左孩子但有右孩子，违反（1）else i f(bj=l)节点有左孩子迄今为止,所有节点均有左右孩子rear=(rear+1)%MaxSi ze;/左孩子进队Qurear=p-lc h i ld;i f(p-rc h i ld=NULL)*p有左孩子但没有右孩子，则bj=0bj=0;else/*p有右孩子，则继续判断 rear=(rear+1)%MaxS i ze;Qurear=p-rc h i ld;)/右孩子进队elsec m=0;/bj=0:迄今为止，已有节点缺左或右孩子 此时*p节点有左孩子，违反（2）return c m;)return 1;空树当成特殊的完全二叉树若采用顺序存储结构，判断一棵二叉树是完全二叉树十分简单，只须判断第一个节点到最后一个节点之间没有空节点即可。对应的算法如下。i n t CompBTNod el(SBTree b)i n t i,j;for(i=l;i MaxSi ze;i+)找到第一个空节点i f(bi =#)break;for(j=i+l;jdata);_O)_return(p);)void print(NODE*head)i f(h ead!=NULL)pinrtf(,%5d,z head-data);_(2)NODE exchange(NODE*head)NODE*pz*qz*h=NULL,*r=NULL;int t;if(head!=NULL&head-link!=NULL)/if A begint=head-data;p=head;while(p-link!=NULL)if(p-link-datali n k;(3);if(h=NULL)h=q;else(4);r=q;else(5J;/i f B else en dif(h!=NULL)_(6)_；head=h;)/if A endreturn(head);【答案】(1)p-li n k=c reate(n-1)(2)pri n t(h ead-li n k)(3)p-li n k=q-li n k(4)r-li n k=q(5)p=p-Ii n k(6)r-li n k=h ead25,已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插 入前一个数组序列中，完成后两个数组中的数分别有序(非降序)并且第一数组中所有的数都不大于第二个 数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如，第一个数组为：4,12,28第二个数组为：1,7,9,29,45输出结果为：1,4,7第一个数组9,12,28,29,45-第二个数组【答案】设两个数组分别是A和B,各有m和n个元素。结果要求第一个数组的最后一个数由，并-1不 大于第二个数组的第一个数用0。由于要求将第二个数组的数插入第一个数组中。因此比较可出-1和用0,第11页，共60页圉V簟心博阅”handebooksm 考研专业课资料学长一对一诚招加盟如山L，则交换。交换后仍保持A和B有序。重复以上步骤，直到加?-14例0为止。核心语句段 如下：wh i le(A m-l B 0)(x=A m-l；A m-l 0;交换 A i n-1和 B 0在O.m-2间折半查找的插入位置,并插入在间折聿&强x的祎入位置，并插入)26.请给出求二叉树的最大枝长的递归算法。【答案】最大枝长的递归定义为：(1)对于空二叉树，最大枝长为0;(2)否则为其左子树枝长和右子树枝长的最大者加1。递归函数定义如下：i n t maxlen gth(btree*t)Ii n t max,maxi,max2;i f(t=NULL)return 0;elsemaxi=maxlen gth(t-left);max2=maxlen gth(t-ri gh t);Ii f(maxi max2)max=maxi+1;else max=max2+1;return max;I27.假设稀疏矩阵A和B(具有相同的大小mxn)都采用三元组表示，设计一个算法计算C=A+B,要求C也 采用三元组表示。【答案】依次扫描A和B的行号和列号若A的当前项的行号等于B的当前项的行号，则比较其列号,将较小列的项存入C中，如果列号也相等，则将对应的元素值相加后存入C中(只存储相加结果为非零的 元素)；若A的当前项的行号小于B的当前项的行号，则将A的项存入C中；若A的当前项的行号大于B 的当前项的行号，则将B的项存入C中。这样产生了 C。对应算法如下。voi d MatAd d(TSMatri x A,TSMac r.i x B,TSMatri x&C)i n t i=0,j=0,k=0;wh i le(i A.n ums&jB.n ums)i f(A.d ata i .r=B.d ata j.r)/若A的当前项的行号等于B的当前项的行号 i f(A.d atai.c B.d ataj c)C.d atak.r=B.d ataj.r;C.d atak.c=B.d ataj.c;C.d atak.d=B.d ataj.d;k+;j+；)else/A.d atai.c=B.d ataj.c C.d atak.r=B.d ataj.r;第12页，共60页V簟心博阅V handebook8m 考研专业课资料学长一对一诚招加盟C d atak.c=B,d ataj.c;C.d atak.d=A.d ata1.d+B.d ataj.d;i f(C.d atak.d!=0)只存储非零元素k+;i+;j+;)else i f(A.d atai .rB.d ataj.r)若A的当前项的行号小于B的当前项的行号，则将A的项存入C中 C.d atak.r=A.d atai.r;C.d atak.c=A.d atai.c;C.d atak.d=A.d atai.d;k+;i+；)else 若A的当前项的行号大于B的当前项的行号，则将B的项存入C中 C.d atakj.r=B.d ataj.r;C.d atak.c=B.d ata j.c;C.d atak.d=B.d ataj.d;k+;j+；C.rows=A.rows;C.c ols=A,c ols;C.n ums-k;28.请编写直接插入排序算法.【答案】假定第1个元素有序，从第2个元素起，依次插入前面有序子文件中。核心语句如下:for(i=2；i=n；i+)R0=Ri ；j=i-l；wh i le(R0.keyn ext!=p)q=q-n c xt;确定 p 及 p 的前驱 q 的位置 i f!(p-n ext)r=p-n ext;引入临时变量r,用于保存p的后继q-n ext=r;修改p的前驱p-n ext=r-n ext;/修改p 的后继 r-n ext=p；修改r的后继/i f/Reverse_P第13页，共60页圉V簟心博阅”handebooksm 考研专业课资料学长一对一诚招加盟【复试】2023年东北师范大学071000生物学加试:Python程序语言及应用之数据结构 考研复试仿真模拟5套卷(二)，。一、单项选择题1.若元素a,b,c,d,e,f依次迸栈，允许进栈、退栈操作交替迸行，但不允许连续三次迸行退栈操作，则不 可能得到的出栈序列是_。A.d,c,e,b,f,aB.c,b,d,a,e,fC.b,c,a,e,f,dD.a,f,e,d,c,b【答案】D2.用不带头结点的单链表存储队列，其队首指针指向队首结点，队尾指针指向队尾结点，则在进行入队操作时_0A.仅修改队首指针B.仅修改队尾指针。C队首、队尾指针都要修改D.队首、队尾指针都可能要修改【答案】B3.以下函数中时间复杂度最小的是_。A.Ti(n)=10001og2nB.Tsh n-lOOOlognC.T3(n)=n2_l OOOlog2nD.T4(n)=2n log2n-l 0001og2n【答案】A【解析】T(n)=O(log2n),T2(n O(n10B；n),T3(n)=O(n2),T4(n)=O(n log2n)o4.具有n个顶点的有向图最多有 条边。A.nB.n(n-l)C.n(n+1)D.n2【答案】B5.对包含n个关犍字的散列表进行查找，平均查找长度是_oA.O(log2 n)B.O(rt)C.O(log2 ri D.不直接依赖于n【答案】D【解析】哈希表的平均查找长度是装填因子的函数，而不是n的函数。第14页，共60页灵博阅考研专业课资料学长一对一诚招加盟6.设散列表长为14,散列函数是H(key)=key%ll,表中已有数据的关健字为15,38,61,84共4个，现要将关健字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是一A.8B.3C.5D.9【答案】D7.一棵二叉树的先序遍历序列为ABCDEFG,它的中序遍历序列可能是_0A.CABDEFGB.ABCDEFG C.DACEFBG D.ADCFEG【答案】B【解析】当该二叉树所有节点的左子树为空时，先序遍历序列和中序遍历序列相同。先序序列和中序 序列可以确定一棵二叉树，这里由选项A、C和D的中序序列无法确定一棵二叉树。8.一棵高度为8的完全二叉树至多有 个叶子节点。A.63B.64C.127D.128【答案】D【解析】设完全二叉树的高度为h,其节点个数为n,有n f+m+n 2f+2刖-1,则。=(叶1-m)/2,结合上 例有：2h,n 2h-l,要使加最大，n应取最大值2k1,此时n为奇数，内应取0,这样n o=n/2=2h/2=2h“。这 里h=8,所以刖的最小值为27=128。9.执行_操作时，需要使用队列做辅助存储空间。A.查找散列(Hash)表B.广度优先搜索图C.先序(根)遍历二叉树D.深度优先搜索图【答案】B【解析】查找散列表和先序遍历二叉树不需要用到额外的空间(辅助存储空间)；深度优先搜索图可以 利用递归的方法，使用栈，而不使用队列做辅助空间;只有广度优先搜索图需要用到队列做辅助存储空间。二、填空题10.按增长率由小到大的顺序排列下列各函数(3/2)n.5,2,log2 n?log2 n,n,；i 2,log2(log2 n)为:o【答案】2100,Iog2(log,;?),log2 w,?I0-5,?,log2n,n3/2,(3/2),2,nn11.对于变量说明varx,y；flag:boolean;c:c h ar；f下列程序段if x then falg:=FALSE else if y then flag:二TRUE else flag:二FALSE;for c:=to 2,d o第15页，共60页圉V簟心博阅”handebooksm 考研专业课资料学长一对一诚招加盟i f fa)g th en wri te(ord(c):4);等价于：if(A)thenfor c:=*2*downto 冒 write(B):4);【答案】(A)(n otx)an d y、(B)ord Ca+ord Cz)-ord(c)12.数据结构由数据的 和 三部分组成。【答案】逻辑结构、存储结构、运算13.B+树适用于组织 的索引结构,m阶B+树每个结点至多有 个儿子，除根结点外每个结点至少有 个儿子,根结点至少有 个儿子，有k个儿子的结点必有 个关犍字。【答案】随机组织、m、加/2、2、k14.对n个记录的表进行简单选择排序，所需的关键字间的比较次数为 最坏情况下所需的记录移动次数为 0【答案】n(w-l)/2、3(1)【解析】简单选择排序的基本思想是，每一趟在正一2+1(=L2,4-1)个记录中选取关键字最小的记录作为第i个记录，所以第i趟排序需要进行n-i次比较。所以总的比较次数为-，)=应-1)/2。f=l对于移动次数，最好的情况是不用进行交换，所以移动次数是“。二在最坏情况下，每次都进行对换，要进 行次对换，一次对换需要三次移动，所以最坏情况下，所需的记录移动次数为3(n-l)o15.设一棵后序线索树的高度是50,结点x是树中的一个结点，其双亲是结点y,y的右子树高度是31,x 是y的左孩子，则确定x的后继最多需经过_中间结点(不含后继及x本身)。【答案】31三、应用题16.用置换-选择排序法，产生文件F(长度为n)的初始归并段。设内存缓冲区的长度为m，问：(1)平均情况下，初始归并段的长度为多少？为什么？初始归并段的长度最长与最短时，其长度分别为多少？在何种情况下出现，简单解释一下。【答案】平均情况下，初始归并段的长度为2m。这个证明是E.F.Moorc在1961年从置换-选择排序 和扫雪机的类比中得出的。假设一台扫雪机在环形路上匀速行进扫雪，下雪的速度也是均匀的(即每小时落到地面上的雪量相等)，雪均匀地落在扫雪机的前、后路面上，边下雪边扫雪。显然，在某个时刻之后，整个系统达到平衡状态，路面上的积雪总量不变。且在任何时刻，整个路面上的积雪都形成一个均匀的斜面，紧靠扫雪机前端的积 雪最厚，其深度为力,而在扫雪机刚扫过的路面上的积雪深度为零。若将环形路伸展开来，假设此刻路面 积雪的总体积为W,环形路一圈的长度为/,由于扫雪机在任何时刻扫走的雪的深度均为方，则扫雪机在 环形路上走一圈扫掉的积雪体积为/,即2也把置换-选择排序和此类比，工作区中的记录好比路面的积雪，输出的MINIMAX记录好比扫走的雪，重新输入的记录好比新下的雪，当关键字为随机数的时候，新记录的关键字比MINIMAX大或小的概率相 等。若大，则属于当前的归并段(好比落在扫雪机前面的积雪，在这一圈中将被扫走)；若小，则属于下一 第16页，共60页灵博阅考研专业课资料学长一对一诚招加盟归并段(好比落在扫雪机后面的积雪，在下一圈中不能扫走)。所以，得到一个初始归并段好比扫雪机走了 一圈。假设工作区的容量为W,那么置换置换一选择排序所得到的初始归并段长度的期望值便为2w。(2)当置换-选择排序的缓冲区容量W有一定宽度，使得初始顺串形成时，若其输入文件为基本有序(如 递增次序)，即置换进入W中的记录关键字大于刚选出的，则可获得最长的初始顺串。此时，最长初始顺串 长度为输入文件的长度值，即应若输入文件为基本逆序时，即置换进入W中的记录关键字小于刚选出的，则可使得初始顺串最短。其 初始顺串长度为W宽度值。17.以图1为例，按Di jkstra算法计算从顶点A到其他各个顶点的最短路径和最短路径长度。图1【答案】该有向网的邻接矩阵如图2所示。0 10 18 00 00oo 0 oo 5 0000 5 0 00 0Doo co 2 0 2co oo 2 oo 0图2说明：(l)foun d表示是否找到最短路径，“1”表示已找到A到对应顶点的最短路径。(2)d i stan c e表示A到对应顶点的当前最短路径值。第一步:由邻接矩阵求解A和直接邻接的所有顶点之间具有最短路径的顶点及路径。顶点BCDEfoun d1000d i stan c e1018oo8结果:A到B的路径最短，故选择路径.作为A到B的最短路径。该路径为:A-A;A-B;A-C;A无法到D、Eo第二步:由于B的加入，修正所有路径。顶点BcDEfoun d1010d i stan c e1018158结果:通过B,A到D可达，其中A到D的路径最短，故选择路径作为A到D的最短路径。第三步:由于D的加入，修正所有路径。顶点BcDEfoun d1010d i stan c e10171517第17页，共60页灵博阅考研专业课资料学长一对一诚招加盟结果:通过B、D,A到C的路径更短A,B,D,C,A至1E可达，选择A到C的路径为较短路径。第四步:A到E的最短路径A,B,D,E|殳有改变，长度为17o顶点BcDEfoun d1.111d i stan c e10171517综上：A到B的最短路径为A,B、最短距离为10o(2)A到C的最短路径为A,B,D,O,最短距离为15o(3)A到D的最短路径为A,B,D,最短距离为llo(4)A到E的最短路径为A,B,D,E,最短距离为17o18.设某文件经内部排序后获得初始盛串为100个。试问：(1)若要使多赂归并三趟完成排序，则应取归并的路数至少为多少？若操作系统宴求一个程序赖亲隹可使用的DO文件数不超过13个，则依多路归并法至少需几趟完成排 序？如果限定这个趟数，则可取的最低归并路数是多少？【答案】当文件的初始归并段加=10。个时，其k路归并的趟数s可由下式决定,即s=log00现若限定归并趟数s=3,则有*2i oo若取上4,则43=64;取仁5,则53=125o因此，至少取5路进行归并排序。(2)若每次可取12路进行归并(因操作系统同时可用的I/O文件为13个，用12个文件作输入文件，1个作 输出文件),则S=logi 2 10。=2归并排序至少需用2趟完成。如果限定这个趟数，设可取的归并路数至少为大，则由d Ni oo得七210,所以可取的最低归并路数是10。19.广义表，A(B(E,F),C,)表示一棵树，请画出该树并给出其中序遍历序列。【答案】广义表(八(坎E,F)CD(G)对应的树如图所示。其中序遍历的序列为EFBCGDA。20.设某磁盘上存有一文件FI,共有3600个记录，43600),页块长为150个记录，供排序使用 的内存缓冲区宽度为600个记录，现要对该文件进行排序(3-路归并)。试描述其归并排序的过程。【答案】将4个页块(共600个记录)由外存读入内存，进行内排序,整个文件FI总共获得6个初始归并 E殳(顺串)6,且把它们写回到磁盘去，如下图1所示。第18页，共60页V簟心博阅V handebook8m 考研专业课资料学长一对一诚招加盟Ri R2 R3&R5%1-600 601 1200 1201 1800 1801 2400 2401 3000 3001 3600图I(2)将内存缓冲区分成4块，即每块可容纳150个记录，其中的3块作为输入缓冲区，另1块作为输出缓冲 区。实施3-路归并，对6个初始顺串的归并过程，如下图2所示。.Ri.R?Rj&-Rf.&Rl6图21.在排序连续顺序文件中采用折半直找方法查找记录存在与否的过程可以借助于一棵平衡二叉树来模 拟，树中结点的值为记录在文件中的位置序号。若文件中有19个记录，画出这棵判定树。(2)当文件中有n个记录时，求出该判定树的深度。【答案】判定楸口图所示。图(2)判定树的深度为Llog2 n j+lo四、算法设计题22,已知顺序表中有n个记录，表中记录不依关健字有序排序，编写一算法，为该顺序表建立一个有序的 索引表(依关健字递增排列)，索引表中的每一项应含有记录的关健字和该记录在顺序表中的序号。要求算法的时间复杂度在最好的情况下能达到【答案】typed ef struc t i n d ex/索引类型Key type key；/关键字i n t n o；/在主表中的序号i n d extype；typed ef struc t ElemType d ata；KeyType key;表结点类型/表中元素/表中元素关键字第19页，共60页灵博阅考研专业课资料学长一对一诚招加盟Rec tTypo；voi d c reatei n d ex(Rec tType r ,i n d exc ype&i d x ,i n t n)/为主表 r 建立一个索引表 i d x i n t i,j;for(i=l；i O&ai d xk.key)/把大于 ri .key 的所有 i d x j .key 后移i d xj+l=i d xj;j-;)i d xj+l.key=r i .key；/把 r i J.key 插入到 i d x 中，并记录卜其序号 ii d xj+1.n o=i;23.假设循环单链表不空，且既无表头结点亦无表头指针，指针P指向链表中某结点。i青设计一个算法，将P所指结点的前驱结点变为P所指结点的后继结点。【答案】要将P的前驱变为P的后继，在这个循环单链表中，除了 P指针所指结点，其他结点都需要 通过P所指结点的n ext域来寻找。将p所指结点的前驱变为p所指结点的后继结点，其实就是将P的前驱 的前驱的n ext域改为p,p的前驱的n ext域为p的后继，p的n ext域为p的前驱。为此需要借助n ext域找 到P的前驱的前驱及P的前驱，然后再对其n ext域进行改变。算法实现如下：void pre2subseq(p)i f(p-n ext-n ext!=p)q=p；wh i le(q-n ext!=p)q=q-n ext;s=q;wh i le(s-n ext!=q)s=s-n ext;s-n ext=p;q-n ext=p-n ext;p-n ext=q;)在前驱、后继不一样的情况下进行调整/找到p的前驱结点，用q指针指向它找到q的前驱结点，用s指针指向它/s的后继为p/q的后继为p的后继/p的后继为q/en d i f/en d pre2subseq24.设有n个待排序元素存放在式刈中，设计一个算法，对其进行二路归并排序，并分析算法的时间复杂 度和空间复杂度。【答案】二路归并排序算法如下。voi d Merge(SeqLi sl R,i n t low,mt ra.i n t h i gh)将两人有序的序列R：lowm)和Rm+1.h i gh 归并成一个有序的子序列Ri low.h i gh i n t i=low.j=m+p=0；/置初妗值Rec Type*R1；/RI是局部向黄，若P定义为此类型指针速度更快RI=(ReeType*)malloc(h i gh-low 4-1)*si zeof(Rec Type)；i f(!RD 申请空间失败ErrorCln suffi c i en t memory avai lable!)；wh i 2e(i =h i gh)/两子文件非空时取其小者埔出到也、上Rlp+=(R-i lkey=.key)?Ri+：Rj+;Mh i lc(i =m)若第1个子文件非空，则复制剩余汜录到R1中RlpT 4 =Ri+；wh i le(j=h i gh)若第2个子文件非空.则复制剩余记录到RI 41Rlp+=Rj+;for(p=0,i=low；i =h i gh；p+i+)Ri =Rlp；归并完成后将结果复制回RCow.h i gh 第20页，共60页圉V簟心博阅”handebooksm 考研专业课资料学长一对一诚招加盟/Mergevoi d MergePass(SeqLi st R,i n t len gth)对做一-越归并排序i n t i；ford=1；i+2*len gth-1=n；i=i+2*len gth.)Mergc(R,i,i+len gth 1 i+2*len gth-1)；归并长度为len gth的两个相邻子序歹！i f(i+len gth-l/MergePassvoi d MergeSort(SeqLi st R)/采相自底向上的方法，对RLl.n进行二路归并排序i n t len gth；for(len gth=1；len gth en；len gth*=2)/做,Ign趟归并MergePass(R,len gth)；有序段长度)11时终止对长度为n的文件，需进行log2n趟二路归并，每趟归并的时间为。(加，故其时间复杂度无论是在最 好情况下还是在最坏情况下均是。敢叱由于二路归并排序需要一个辅助向量来暂存两有序子序列归并 的结果，故其辅助空间复杂度为。()。25.若x和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。【答案】两串相等指长度相等且对应位置的字符相同。i f(x.len gth!=y.len gth)return(0)；判断两个串 x 和 y 是否相等p=x.str；q=y.str；wh i le(p&q&*p=*q)p+；q+;对应字符相等，指针后移 i f(!p&!q)return(1)；else return(0);26.设计一个算法Ch an ge(g,x,y),将一介广义表g中所有原子x替换成yc例如，若g广义表为(a,(a),执 行 Ch an ge(g,a,b)后广义表 g 变为(b,(b)。【答案】对于广义表gl,替换过程是，对于表的每个元素进行循环:若为子表，递归替换该子表;否则，如果该原子节点的d ata域值为x,则替换为yo对应的算法如下。voi d Ch an ge(GLNod e*gl,ElemType xfElemType y)wh i le(gllNULL)i f(gl-tag-=l)Ch an ge(gl-val subli st,x,y);else i f(gl-val.d ata-=x)gl-val d ara=y;gl=gl-li n k;/对每个元素进行循环处理为子表时递归将子表中的X改为y/为原子且d ata域值为x时/处理后继元素)27.优化下面的递归算法，减少进栈、出栈次数。PROCEDURE bfi n d(p：bptr;k：keytype);I在指针P指的二叉排序树上查找关键字等于给定值k的记录，当查找成功时返回所找结点的指针BEGINIFp!=NILTHEN IF pkey=kTHEN retum(p)查找成功|ELSE IF k p.keyTHEN bfi n d(pA.Ic,k);ELSE bfi n d.(p*.rc,k)ELSE retum(p)I查找失败，返回空指针1END;第21页，共60页V簟心博阅V handebook8m 考研专业课资料学长一对一诚招加盟其中二叉排序树结点结构为:lckeyrc【答案PROCEDURE bfi n d(p：bptr；k：keytype);在指针P指的二叉排序树上查找关键字等于给定值k的记录，当杳找成功时返回所找结点的指针 BEGINIF pA.key=kTHEN retum(p)查找成功 IELSE IF kp-.keyTHEN IFpMc NILTHEN bfi n d(pMc,k);ELSE retum(NIL);ELSE IF p.rc NILTHEN bfi n d(prc,k);ELSE return(NIL);END；28.函数voi d i n sert(c h ar*s,c h ar*t,i n t pos)将字符串t插入字符串s中，插入位置为poso请用C语言实现该函数。假设分配给字符串s的空间足够让字符串t插入。【答案】首先应查找字符串S的pos位置，将第pos个字符到字符串S尾的子串向后移动字符串t的长 度，然后将字符串t复制到字符串S的第pos位置后。对插入位置pos要验证其合法性，题目假设给字符 串S的空间足够大，故对插入不必判溢出。wh i le(*p!=0&i pos)p+；i+；/查 pos 位置i f(*p=1 0 1)c outpos 位置大于字符串 s 的长度=pos;j-)*(p+x)=*p；p-;q-;/指针q回退到串t的最后一个字符 for(j=l；j0时写出求尸(的递归算法；(2)写出求他加)的非递归算法。【答案】递归算法如下：voi d rec urse(i n t m,i n t&s)i f(m0)return ERROR；i f(m=-0)s=l;else rec urse(m/2,r);s=m*r;)非递归算法如下：voi d n on rec ure(i n t m,i n t&s)(typed ef struc ti n t a,b;n od e;n od e sa 100;if(m0)return；i f(m=0)s=l；else(wh i le(m!=0)/初始化 top=0top+；saftop.a=m；satop.b=m/2；m=satop.b；S=1；wh i le(top)s=s*satop-l.a；第22页，共60页考研专业课资料学长一对一诚招加盟/else 第23页，共60页圉V簟心博阅”handebooksm 考研专业课资料学长一对一诚招加盟【复试】2023年东北师范大学071000生物学加试:Python程序语言及应用之数据结构 考研复试仿真模拟5套卷（三），。一、单项选择题1.下列排序方法中 在待排序的数据为有序时，花费时间反而最多。A.快速排序B.插入排序C推排序D眉泡排序【答案】A【解析】当待排序列有序时，快速排序退化为冒泡排序，时间复杂度为0（/）。2.将森林F转换为对应的二叉树T,F中叶结点的个数等于。A.T中叶结点的个数B.T中度为1的结点个数C.T中左孩子指针为空的结点个数D.T中右孩子指针为空的结点个数【答案】C【解析】将森林转化为二叉树相当于用孩子兄弟表示法表示森林。在变化过程中，原森林某结点的第 一个孩子结点作为它的左子树，它的兄弟作为它的右子树。那么森林中的叶结点由于没有孩子结点，那么 转化为二叉树时，该结点就没有左结点，所以F中叶结点的个数就等于T中左孩子指针为空的结点个数。3.已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是A.39B.52C.111D.119【答案】C【解析】本题问“完全二叉树的结点个数最多是多少”。完全二叉树的叶子至多只能在最下面两层上。本题告诉第6层有8个叶子，还会有24个分支结点，其在第7层最多有48个叶子，故选Co若说第6层 只有8个叶子，则应选Ao4.对数据序列（8,%10,4,5,6,20,b 2）采用（由后向前次序的）冒泡排序，需要进行的趟数（遍数）至少是A.3B.4C.5D.8【答案】C第24页，共60页灵博阅考研专业课资料学长一对一诚招加盟【解析】冒泡排序的方法是，扫描一遍待排序列，把其中最大或最小元素放在序列的最后面，然后再 对剩余的元素进行冒泡排序，结束的标志是，如果一次扫描没有移动过数据，表明已经是有序序列。根据 此描述得出结论5.已知关健字序列5,8,12,19,28,20,15,22是小根堆，插入关键字3,调整好后得到的小根堆是一A.3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,19【答案】A6.计算机中算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、A.可行性、可移植性和可扩充性B.可行性、有穷性和确定性C.确定性、有穷性和稳定性D.易读性、稳定性和确定性【答案】B7.在单链表中查找指定值的节点的时间复杂度是 _oA.O(log?n)B.Od)C.O(n