版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构历年高频考题带答案难题附详解(图片大小可自由调整)第1卷一.历年考点试题黑钻版(共50题)1.下面关于线性表的叙述中,错误的是哪一个?
A.线性表采用顺序存储,必须占用一片连续的存储单元B.线性表采用顺序存储,便于进行插入和删除操作C.线性表采用链接存储,不必占用一片连续的存储单元D.线性表采用链接存储,便于插入和删除操作2.在n×n(n≥3)阶的稀疏矩阵A中,只有下标满足1<i<n和n-i≤j≤n-i+2的元素A[i][j]不等于0,若这些非0元素按行优先的顺序存储在一维数组B中,编写一个算法通过B求A[i][j]之值。也就是说,在存在B的情况下已知i、j,求A[i][j]。3.______的遍历仍需要栈的支持。A.前序线索树B.中序线索树C.后序线索树D.中序线索树和前序线索树4.对于具有n(n>1)个顶点的强连通图,其有向边的条数至少是______。A.n+1B.nC.n-1D.n-25.给定一个关键字集合{25,18,34,9,14,27,42,51,38},假定查找各关键字的概率相同,请画出其最佳二叉排序树。6.一棵124个叶结点的完全二叉树,最多有______个结点。A.247B.248C.249D.250E.2517.对一个由n个关键字不同的记录构成的序列,能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?8.多维数组实际上是由______实现的。A.一维数组B.多项式C.三元组表D.简单变量9.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为
。A.(38,40,46,56,79,84)B.(40,38,46,79,56,84)C.(40,38,46,56,79,84)D.(40,38,46,84,56,79)10.编写一个在顺序表上执行顺序查找的递归算法,在算法的参数表中增加一个整数形参loe,指明查找的开始位置。函数的首部为:
intseqSearch1(seqList&L,DataTypex,intloc);其中,DataType是顺序表中每个元素的数据类型,假设已经定义可直接使用。11.证明:具有n个顶点和多于n-1条边的无向连通图G一定不是树。12.在下列关于线性表的叙述中,正确的是______。A.线性表的逻辑顺序与物理顺序总是一致的B.线性表的顺序存储表示优于链式存储表示C.线性表若采用链式存储表示时,所有存储单元的地址可连续也可不连续D.每种数据结构都应具备三种基本运算:插入、删除和查找13.用S表示进栈操作,用X表示出栈操作,若元素的进栈顺序是1,2,3,4,为了得到出栈顺序1,3,4,2,相应的S和X的操作序列为______。A.SXSXSSXXB.SSSXXSXXC.SXSSXXSXD.SXSSXSXX14.设计一个算法指出一个无序数序中的任意一个元素是第几大元素(从小到大数),要求比较的次数最少。15.在图采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为
。A.O(n)B.O(n+e)C.O(n2)D.O(n3)16.试设计一个实现下述要求的Locate运算的函数。设有一个带表头结点的双向链表L,每个结点有4个数据成员:指向前驱结点的指针lLink、指向后继结点的指针rLink、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Loeate(L,x)操作时,令元素值为x的结点的访问频度freq加1,并将该结点前移,链接到与它的访问频度相等的结点后面,使得链表中所有结点保存按访问频度递减的顺序排列,以使频繁访问的结点总是靠近表头。17.设图有n个顶点和e条边,在采用邻接矩阵时,遍历图的顶点所需时间为______;在采用邻接表时,遍历图的顶点所需时间为O(n+e)。A.O(n)B.O(n2)C.O(e)D.O(n×e)18.关于图(Graph)的一些问题:
(1)有n个顶点的有向强连通图最多有多少条边?最少有多少条边?
(2)表示有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?19.折半查找的时间复杂性为______。A.O(n2)B.O(n)C.O(nlog2n)D.O(log2n)20.设森林F对应的二叉树为B,它有m个结点。B的根为p,p的右子树中结点个数为n,则森林F中第一棵树的结点个数是______。A.m-nB.m-n-1C.n+1D.无法确定21.表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时,对象栈和算符栈为,其中^为乘幂(
)。A.3,2,4,1,1;*^(+*-B.3.2,8;*^-C.3,2,4,2,2;*^(-D.3,2,8;*^(-22.将递归算法转换成对应的非递归算法时,除了单向递归和尾递归的情况外,通常用来保存中间结果的是______。A.链表B.栈C.队列D.顺序表23.在下列指定的排序算法中,______使用的附加空间与输入序列的长度及初始排列无关。A.锦标赛排序B.快速排序C.基数排序D.归并排序24.线性表的每一个表元素是否必须类型相同?为什么?25.树是结点的有限集合,一棵树中有______根结点。A.有0个或1个B.有0个或多个C.有且只有一个D.有1个或1个以上26.设如图所示,在下面的5个序列中,符合深度优先遍历的序列有
个。
aebdfcacfdebaedfcbaefdcbaefdbc
A.5
B.4
C.3
D.2
27.假定从空树开始建立一棵有n个关键字的m阶B树,最终得到有p(p>2)个非失败结点的B树,那么这p个结点最多经过______次分裂得来。A.pB.p-1C.p-2D.p-328.假设在二叉树中值为x的结点不多于一个,试编写算法输出值为x的结点的所有祖先。29.在开地址法中散列到同一个地址而引起的“堆积”问题是由于______引起的。A.同义词直接发生冲突B.非同义词直接发生冲突C.同义词之间或非同义词之间发生冲突D.散列表“溢出”30.解决散列法中出现的冲突问题常采用的方法是______。A.数字分析法、除留余数法、平方取中法B.数字分析法、除留余数法、线性探测法C.数字分析法、线性探测法、双散列法D.线性探测法、双散列法、链地址法31.在有n个结点且为完全二叉树的二叉排序树中查找一个键值,其平均比较次数的数量级为______。A.O(n)B.O(log2/n)C.O(nlog2n)D.O(n2)32.用S表示进栈操作,用X表示出栈操作,若元素的进栈顺序是1234,为了得到1342的出栈顺序,相应的S和X的操作序列为______。A.SXSXSSXXB.SSSXXSXXC.SXSSXXSXD.SXSSXSXX33.设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。
设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。34.具有6个顶点的无向图至少应有______条边才能确保是一个连通图。A.5B.6C.7D.835.分别以下列序列构造二叉排序树,与用其他三个序列所构造的结果不同的是
。A.(100,80,90,60,120,110,130)B.(100,120,110,130,80,60,90)C.(100,60,80,90,120,110,130)D.(100,80,60,90,120,130,110)36.自由树(即无环连通图)T=(V,E)的直径是树中所有点对点之间最短路径长度的最大值,即T的直径定义为d(u,v)的最大值(其中u,v∈V)。这里d(u,v)表示顶点u到顶点v的最短路径长度(路径长度为路径中包含的边数)。如图所示为一棵自由树,其直径为18。试写算法求T的直径,并分析算法的时间复杂度。
37.设计快速排序的递归和非递归算法。38.编写一个算法,将一个非负的十进制整数N转换为一个二进制数。39.当采用分块查找时,数据的组织方式为______。A.数据分成若干块,每块内数据有序B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块C.数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块D.数据分成若干块,每块(除最后一块外)中数据个数需相同40.设一个循环队列Q[maxSize]的队头指针为front,队尾指针为rear,队列最大容量为maxSize。除此之外,该队列再没有其他数据成员,则该队列的队满条件是______。A.Q.front==Q.rearB.front+Q.rear>=maxSizeC.Q.fron==(Q.rear+1)%maxSizeD.Q.rear==(Q.front+1)%maxSize41.一个二部图的邻接矩阵A是一个______类型的矩阵。A.n×n矩阵B.分块对称矩阵C.上三角矩阵D.下三角矩阵42.败者树中的“败者”指的是什么?若利用败者树求m个排序码中的最大者,在某次比较中得到a>b,那么谁是败者?43.假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)44.给出折半查找的递归算法,并给出算法时间复杂度分析。45.以下有关排序的说法中,正确的是______。A.使用链表可以实现简单选择排序,但很难实现堆排序B.当待排序元素序列的初始排列完全有序时,快速排序的排序速度显著提高C.简单选择排序是一个稳定的排序方法D.在最坏情况下,快速排序的时间性能也好于堆排序的时间性能46.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为______。A.1和5B.2和4C.4和2D.5和147.图的D-搜索类似于BFS(广度优先搜索),不同之处在于用栈代替BFS中的队列,入、出队列的操作改为入、出栈的操作,即当一个顶点的所有邻接点被搜索之后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。请用邻接表作为存储结构,写一个D-搜索算法。48.假设有n(n>1)个线性表顺序地存放在顺序表S[1,…,m]中,令F[i]和R[i]指示第i个(1≤i≤n)表的第1个元素和最后1个元素在S中的位置,并设定R[i]<F[i+1],F[n+1]=m+1,如图所示。试写出实现下列要求的算法。
(1)在第i个表中的第j项后面插入1个元素,仅当整个顺序表空间填满时,不允许进行插入操作。
(2)删除第i个表中的第j个元素,要求在删除第j个元素后,该表仍为顺序存储的线性表。49.在一个无向图中,所有顶点的度之和等于边数的______倍。A.1/2B.1C.2D.450.有一个n×n的对称矩阵A,将其上三角部分按列压缩存放于一个一维数组B中,A[0][0]存放于B[0]中。
B=[A00,A01,A11,A02,A12,A22,…,A0(n-1),A1(n-1),A2(n-1),…,A(n-1)(n-1)]
同时有两个函数:max(i,j)和min(i,j),分别计算下标i和j中的大者与小者。试利用它们给出求任意一个A[i][j]在B中存放位置的公式。第1卷参考答案一.历年考点试题黑钻版1.参考答案:B线性表采用顺序存储,并不便于进行插入和删除操作。2.参考答案:依题意,稀疏矩阵A按行优先顺序存放这些非0元素,可得到如下序列:
a2,n-2a2,n-1a2,na3,n-3a3,n-2a3,n-1...an-1,1an-1,2an-1,3
把它们顺序存放在一维数组B中,前j-1行共有非0元素3x(i-2)个,在非0的ai,j前,本行还有非0元素的个数为j-(n-i)个,则ai,j在B中的位置为1+3×(i-2)+(i+j-n),也就是说,A[i][j]存放在B[1+3×(i-2)+(i+j-n)]元素中。
本题实现代码如下:
intvalue(inta[],inti,intj)
//已知i,j返回A[i][j]之值
{
intadd;
if(i>1&&i<n&&j>=n-i&&j<=n-i+2)
//非0元素的条件
{
add=1+3*(i-2)+(i+j-n);
//在B中的下标
returna[add];
}
elsereturn0;
}
voiddisp(inta[])
{
inti,j;
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
cout<<setw(3)<<value(a,i,j);
cout<<endl;
}
}3.参考答案:C由于后序遍历先访问子树后访问根结点,从本质上要求运行栈中存放祖先的信息,即使对二叉树进行后序线索化,仍然不能脱离栈的支持对此二叉树进行遍历。4.参考答案:B[解析]对于有向强连通图,当n等于1时,边为0,否则至少需要n条边才能形成强连通图。此时所有n个顶点都在某一个有向环上,如下图所示。在此情况下,当有向边的条数少于n时,不能构成环,不再是强连通图。
5.参考答案:当各关键字的查找概率相等时,最佳二叉排序树应是高度最小的二叉排序树。构造过程分两步走:首先对各关键字值从小到大排序,然后仿照折半查找的判定树的构造方法构造二叉排序树。这样得到的就是最佳二叉排序树,如下图所示。
6.参考答案:B[解析]2的6次方是64,2的7次方是128,因此得到:此完全二叉树不是满二叉树,此完全二叉树有8层,除去最底层,此二叉树有127个结点。
设n为最底层结点的个数。则:
1)当n为偶数时,n+64-n/2=124,解得n=120,则此树共有127+120=247个结点。
2)当n为奇数时,n+64-(n+1)/2=124,解得n=121,则此树共有127+121=248个结点。综上本题选B。7.参考答案:将n个元素对称比较,即第一个元素与最后一个元素比较,第二个元素与倒数第二个元素比较……比较中的小者放前半部,大者放后半部,用了n/2次比较。再在前后两部分中分别简单选择最小和最大元素,各用(n/2)-1次比较。总共用了(3n/2)-2次比较。显然,当n≥3时,(2n-3)>(3n/2)-2。
用分治法求解再给出另一参考答案。
对于两个数x和y,经一次比较可得到最大值和最小值;对于三个数x,y,z,最多经3次比较可得最大值和最小值;对于n个数(n>3),将分成长为,n-2和2的前后两部分A和B,分别找出最大者和最小者:MaxA,MinA,MaxB,MinB,最后Max={MaxA,MaxB}和Min={MinA,MinB}。对A使用同样的方法求出最大值和最小值,直到元素个数不超过3。
设C(n)是所需的最多比较次数,根据上述原则,当n>3时有如下关系式:
通过逐步递推,可以得到:C(n)=(3n/2)-2。显然,当n>3时,2n-3>(3n/2)-2。事实上(3n/2)-2是解决这一问题的比较次数的下限。8.参考答案:A[解析]多维数组本质上是一维数组,是由一维数组实现的,是数组元素为一维数组的一维数组。9.参考答案:C快速排序是对冒泡排序的一种改进,其基本思想是:通过一趟排序将待排序的记录分成独立的两部分,其中一部分记录的关键字比另一部分的关键字小。然后对这两部分再继续排序,一直达到整个序列有序。
设待排序序列为{L.r[1],L.r[2],…,L.r[n]),首先任意选取一个记录(通常选择第一个记录L.r[1])作为支点(pivot),然后按照下述原则排列其余记录:将所有关键字比L.r[1].key小的记录都安排在它的位置之前,将所有关键字比L.r[1].key大的记录都安排在它的位置之后。可以发现,在安置的过程中,L.r[1]的确切位置将被最终确定。设该支点(pivot)最后确定的位置为i,则将序列分割为左右两部分。这个过程称为一趟快速排序。
设待排序序列用数组e[low..high]保存。设置两个指针low和high,分别指向数组的开始位置和终止位置。设支点记录为e[low],并将之暂存于t。
首先,从high的位置向前搜索,找到第一个小于t的记录,将这个记录和e[low]的值交换;然后,从low所指向的位置向后搜索,找到第一个值大于t的记录,将这个记录和e[high]的值交换。重复以上步骤,直到low=high。完成一趟排序,low(或者high)指向的位置就是第一个元素的确切位置(从两边向中间“夹挤”)。
第一趟完成后,确定了第一个元素的确切位置,同时生成了两个子序列,然后再对这两个序列使用同样的办法,最终实现整个序列的有序。
举例:利用快速排序法对以下序列进行排序:
(49,38,65,97,76,13,27,49)
过程如下:
初始状态:
high向左移动(high——),直到找到小于t(49)的关键字27,将27的值赋给e[low],如下:
接着low开始向右移动(low++),直到找到大于t(49)的关键字65,将65的值赋给e[high],如下:
high继续左移(high——),直到找到一个小于t的数13,将之赋给e[low],如下:
low继续右移(low++),直到找到大于t(49)的关键字97,将之赋给e[high],如下:
high继续左移(high——),没有找到比t(49)还小的数,但是由于出现了high==low的情况,结束左移。如下:
此时low(或者high)指向的位置就是第一个元素的确定位置:e[low]=t;
经过以上一趟快速排序,可将原序列分为两个序列,同时确定关键字49的确切位置,如下:
{27,38,13}
49
{76,97,65,[49]}
下面再分别对两个子类进行快速排序,得最终结果:
{13)27{38}
49
{49,
65}
76
{97}
49
{65}
则最终得到有序序列:(13,27,38,49,49,6576,97)
说明:在一趟排序中,支点最后才确定位置,故只需最后一步赋值即可,中间不必交换。即,虽然快速排序是交换排序的一种,但是可以不用交换操作即可实现。该算法由于有不相邻元素交换,故是不稳定排序,其时间复杂度为O(nlogn2),是内排序中最好的方法之一。10.参考答案:使用递归算法实现顺序查找的基本思想是:先判断是否检测到表尾,是则返回L.n,表示查找失败,次数loc(0≤loc≤L.n-1)停留在L.n位置,函数返回-1。不是则再判断位于loc位置的元素的关键字是否等于x,是则查找成功,返回元素的位置。否则算法递归检测下一个位置loc+1。该递归算法的调用语句形式为:
intPos=seqSearch1(L,x,0);
intseqSearchl(seqList&L,DataTypex,intloc){
if(loc>=L.n)return-1;
//查找不成功
elseif(L.data[loc]==x)returnloc;
//查找成功
elsereturnseqSearchl(L,x,loc+1);
//继续递归查找
}
每次递归,查找区间的左端点向待查找元素所在位置逼近一个位置,直到递归到达待查找元素所在位置,查找成功。如果递归下去,直到查找区间为空(loc==L.n),查找失败。函数返回找到的位置。算法的递归深度与待查找元素在表中的位置有关,最好情形是一开始就找到待查找元素,递归深度为l;最坏情形是递归深度等于表的长度O(n)。11.参考答案:此题考查的知识点是图的定义。具有n个顶点n-1条边的无向连通图是自由树,即没有确定根结点的树,每个结点均可当根。若边数多于n-1条,因一条边要连接两个结点,则必因加上这一条边而使两个结点多了一条通路,即形成回路。形成回路的连通图不再是树(在图论中树定义为无回路的连通图)。12.参考答案:D[解析]本题主要考查线性结构的特点和线性表的定义。线性表的顺序存储与链式存储在不同的情况下各有利弊,无优劣之分。
链式存储表示要求结点内的存储单元一定连续。13.参考答案:D[解析]此题可以用排除法来解决。由选项A、B、C所得出的栈序列分别为(1,2,4,3)、(3,2,4,1)、(1,3,2,4),可以看出都是错误的。选项D得到的出栈序列为1,3,4,2。14.参考答案:对于给定的数k,将所有小于它的元素排到其前面,所有大于它的元素排到其后面,该数的位置即为有序中的序号(从0开始数),这样最大的比较次数为n-1次。
实现本题功能的程序如下:
intdatai(intr[],intn,intk)
{
inti=0,j=n-1;
inttemp;
while(i<=j)
{
while(i<n&&r[i]<=k)
++i;
while(j>=0&&r[j]>k)
--j;
if(i<j)
{
temp=r[i];r[i]=r[j];r[j]=temp;
++i;
--j;
}
}
returnj;
}15.参考答案:B设N一{V,{E}}是连通网,TE是最小生成树中边的集合,初始为空。
定义一个仅含一个顶点的集合U={u0),u0∈V(u0可从顶点集合V中任意选取),
则将N中的所有顶点分成了两个集合:U,V—U。
重复执行以下操作:在所有的u∈U,v∈V决定的边(u,v)∈{E)中寻找一条代价最小的边(u0,v0),将该边并入TE集合,同时v0并入U,直到U=V为止。
以上操作,通俗地讲,实际上是从两大阵营(两个图的顶点的集合)中寻找一条最短的路。Prim算法中,最小代价生成树的顶点和边都是逐步生成的,开始的时候顶点集合中有一个顶点,边的集合为空。16.参考答案:
boolLocate(DblList&L,Typex){
//在双向链表中查找值为x的结点,找到后该结点被搬到适当位置,函数返回true,
//否则函数返回false。
DblNode*p=L->rLink,*q;
while(p!=NULL&&p->data!=x)p=p->rLink;
if(p!=NULL){
//链表中存在x
p->freq++;q=p;
//该结点的访问频度加1
q->iLink->rLink=q->rLink;
//从链表中摘下这个结点
q->rLink->ILink=q->iLink;
p=q->lLink;
//寻找重新插入的位置
while(p!=L&&q->freq>p->freq)p=p->lLink;
q->rLink=p->rlink;q->llink=p;
//插入在p之后
p->rLink->lLink=q;p->rLink=q;
returntrue;
}
elsereturnfalse;
//没找到17.参考答案:B[解析]存储结构为邻接矩阵的图的遍历算法要对所有顶点都访问一次,每次访问时为确定下一次要访问哪个顶点,需遍历该顶点的行向量,寻找该顶点的所有邻接顶点,所以遍历的时间复杂度为O(n2)。而对于存储结构为邻接表的图的遍历算法也要对所有顶点访问一次,每次访问时为确定下一次要访问哪个顶点,需遍历该顶点的边链表,所以时间复杂度为O(n+e)。18.参考答案:(1)n(n-1),n
(2)106,不一定是稀疏矩阵此题考查的知识点是图的相关术语。
(1)在有向图G中,如果对于每一对vi,vj属于V,vi不等于vj,从vi到vj和从vj到vi都存在路径,则称G是强连通图。最多边是所有的顶点每对之间都有边,边数为n(n-1);最少只有一个方向有边,为n。
(2)元素个数为矩阵的大小,即106,稀疏矩阵的定义是非零个数远小于该矩阵元素个数,且分布无规律,不一定稀疏。19.参考答案:D此题考查的知识点是折半查找的效率。其查找效率与比较次数有关,折半查找成功时,关键字比较次数最多不超过[log2n]+1,所以其效率为O(log2n),应选D。20.参考答案:A[解析]将森林F转化为二叉树表示B,则B的根是第一棵树的根,根的左子树是第一棵树的根的子树森林,根的右子树是森林中除去第一棵树外其他树构成的森林。根据题意,B的根是p,p的右子树中的结点个数为n,则森林F的第一棵树中结点个数为m-n。21.参考答案:D经过入栈后:
开始出栈,遇到6之前:
22.参考答案:B[解析]栈的一个典型应用就是在实现递归程序时作递归工作栈,用于开辟每一层递归程序调用时需要的局部变量空间、实际参数的副本空间和记录返回上一层调用的返回地址等。23.参考答案:C[解析]基数排序是一种分配排序,或称为桶排序。它根据排序码每一位的取值范围(基数),设置若干个桶,通过“分配”和“收集”完成排序。它的附加存储与基数有关。如果不考虑可能需要的链接指针,它需要的附加存储与待排序的元素个数和初始排列无关。当待排序元素个数为n时,锦标赛排序需要n-1个附加结点以构成胜者树;快速排序平均需要log2n个递归工作栈结点空间;归并排序需要n个元素空间。24.参考答案:线性表每一个表元素的数据空间要求相同,但如果对每一个元素的数据类型要求不同时可以用等价类型(union)变量来定义可能的数据元素的类型。如
Typedefunion{
//联合
intintegerInfo;
//整型
charcharInfo;
//字符型
floatfloatInfo;
//浮点型
}info;
利用等价类型,可以在同一空间(空间大小相同)indo中存放不同数据类型的元素。但要求用什么数据类型的变量存,就必须以同样的数据类型来取。25.参考答案:C根据树的基本定义可知,每个树只能有且只有一个根结点。26.参考答案:D解析见7。可知aebdfc,aefdbc符合深度优先搜索条件。27.参考答案:B[解析]从空树开始,最初建立的是根结点,又是叶结点。以后分裂成p个结点,经过了p-1次分裂。28.参考答案:后序遍历最后访问根结点,当访问到值为X的结点时,栈中所有元素均为该结点的祖先,所以此题采用后序遍历进行访问。
typedefstruct
{
BiTteet:
inttag;
}stack;∥tag=0表示左子女被访问,tag=1表示右子女被访问voidSearch(BiTreebt,ElemTypex)
∥在二叉树bt中,查找值为X的结点,并打印其所有祖先
{
stacks[];
∥栈容量足够大
top=0;
while(bt!=null‖top>0)
{
while(bt!=null&&bt—>data!=x)
∥结点入栈
{
s[++top]0t=bt;
S[top].tag=0;
bt=bt—>lchild:
}
∥沿左分枝向下
if(bt—>data==x)
{
printf(“所查结点的所有祖先结点的值为:\n”);
∥找到x
for(i=1;i<=top;i++)
printf(s[i].t—>data);
return;
}
/输出祖先值后结束
while(top!=0&&s[top].tag==1)
top——;∥退栈(空遍历)
if(top!=0)
{
s[top].tag=1;
bt=s[top].t—>rchild:
}
∥沿右分枝向下遍历
}
}29.参考答案:C[解析]在开地址法中散列到同一个地址而引起的“堆积”问题是由于解决同义词冲突的探测序列和非同义词之间不同的探测序列交织在一起,导致关键字就位需要经过较长的探测距离,降低了散列的效率。所以必须选择好的解决冲突的方法以避免“堆积”。30.参考答案:D[解析]常用的解决冲突的方法有两大类:开地址法和链地址法。开地址法中寻找下一个可存放元素的空位不超出表的范围,它又有线性探测、二次探测或双散列之分。链地址法采用链表方式,在表的范围之外分配空间存放发生冲突的元素。31.参考答案:B有n个结点且为完全二叉树的二叉排序树的高度为log2n。32.参考答案:D[解析]用排除法选择答案。选项A、B、C得到的出栈序列分别为1243、3241、1324,都不是正确答案。选项D得到的出栈序列为1342。33.参考答案:利用二叉排序树的性质,从根结点开始查找,若根结点的值小于等于x,则根结点及其左子树均应删除,然后以右子树的根结点为树根,重新开始查找。若根结点的值大于x,则顺左子树向下查找,直到某结点的值小于等于x,则该结点及其左子树均应删除。下面设计一查找算法,确定被删除子树的根结点,再设计一删除算法,删除以被删结点为根的子树。
typedefstructnode{
intdata;
structnode*left,*right;
}BiTNode,*BSTree;
voidDelTree(BSTreer){
//非递归删除以r为根的二叉排序树
BSTreeS[];
//栈,容量足够大,栈中元素是二叉排序树结点的指针
BSTreep;
inttop=0;
while(r!=null||top>0){
while(r!=null){S[++top]=r;r=r->left;}
//沿左分支向下
if(top>0)
//退栈,沿栈顶结点的右子树向下删除,释放被删除结点空间
{p=S[top--];r=p->fight;free(p);}
}
}//DelTree
voidDeleteAllx(BSTreeT,intx){
//在二叉排序树T中,删除所有小于等于x的结点
BSTreep=T,q;
while(T&&T->data<=x){
//根结点的值小于等于x
p=T;T=T->fight;p->fight=null;
DelTree(p);}
//删除二叉树P,删除持续到“根”结点值大于x或T为空树为止
if(T){
q=T;p=T->left;
while(p&&p->data>x){
//沿根结点左分支向下,查小于等于x的结点
while(p&&p->data>x){q=p;p=p->left;}
//q记p的双亲
if(p)
//p结点的值小于等于x
{q->left=p->fight;p->fight=null;DelTree(p);}
p=q->left;
//再查原p的右子树中小于等于x的结点
}
}34.参考答案:A[解析]有n个顶点的连通图,至少需要n-1条边才能保持图的连通。多一条边将形成回路,少一条边将变成非连通图。当n=6时,n-1=5。35.参考答案:C1.二叉排序树定义:二叉排序树是一棵二叉树,它或者为空,或者具有如下性质:1>任一非终端结点若有左孩子,则该结点的关键字值大于其左孩子结点的关键字值;2>任一非终端结点若有右孩子,则该结点的关键字值小于其右孩子结点的关键字值。是一种常用的动态查找表,上面首先给出了它的非递归形式。
二叉排序树也可以用递归的形式定义,即二叉排序树是一棵树,它或者为空,或者具有如下性质:1>若它的左子树非空,则其左子树所有结点的关键字值均小于其根结点的关键字值;2>若它的右子树非空,则其右子树所有结点的关键字值均大于其根结点的关键字值;3>它的左右子树都是二叉排序树。
2.构造二叉排序树:一个无序序列可以通过构造一棵二叉排序树,然后再对这棵二叉树进行中序遍历,即可以变成有序序列。构造树的过程即为对无序序列进行排序的过程。例如:
设查找的关键字的序列为{45,24,53,45,12,90},则生成二叉排序树的过程为:
特别说明:结点个数和取值都相同的表构成的二叉排序树树形可能不相同。其树形由结点的输入顺序决定。36.参考答案:利用深度优先遍历求出一个根结点v到每个叶子结点的距离,这是由diameter(v)函数实现的。该函数的时间复杂度为O(n+e),n为顶点个数,e为边数。然后,以每个顶点作为根结点调用diameter()函数,其中最大值即为T的直径,本算法的时间复杂度为O(n(n+e))。
实现本题功能的程序代码如下:
voiddfs(intparent,intchild,int&len)
//函数执行结束后,len中存放从根结点到child结点所在子树的叶子结点的最大距离
//cost是带权邻接矩阵,visited是已经初始化的访问标记数组
//N是已定义的常量,即顶点个数
{
intclen,v=0,maxlen;
clen=len;
maxlen=len;
while(v<N&&cost[child][v]==0)
//找与child相邻的第一个顶点v
v++;
while(v<N)
//存在邻接顶点时循环
{
if(v!=parent)
{
len=len+cost[child][v];
dfs(child,v,len);
if(len>maxlen)
maxlen=len;
}
v++;
while(v<N&&cost[child][v]==0)
//找与child相邻的下一个顶点v
v++;
len=clen;
}
len=maxlen;
}
intdiameter(intv)
{
intmaxlen1=0;
//存放到目前为止所找到的根v到叶子结点的最大值
intmaxlen2=0;
//存放到目前为止所找到的根v到叶子结点的次大值
intlen=0;
//记录深度优先遍历中到某个叶子结点的距离
intw=0;
//存放v的邻接顶点
while(w<N&&cost[v][w]==0)
//找与v相邻的第一个顶点w
w++;
while(w<N)
//存在邻接顶点时循环
{
len=cost[v][w];
dfs(v,w,len);
if(len>maxlen1)
{
maxlen2=maxlen1;
maxlen1=len;
}
elseif(len>maxlen2)
maxlen2=len;
w++;
while(w<N&&cost[v][w]==0)
//找与v相邻的第一个顶点w
w++;
}
returnmaxlen1+maxlen2;
}
for(i=1;i<N;i++)
//找出从所有顶点出发直径的最大值
{
d=diameter(i);
if(diam<d)
diam=d;
}[说明]本题提到最短路径,拿到题目后,考生容易将其归类为最短路径问题,而去想相应的算法。但由于本题限定图为自由树,所以只需用深度优先搜索的方法即可得到每两点的最短路径。这种在题目中设置干扰因素的情况在正式考题中是常见的,因此考生必须注意区分,以提高做题效率。37.参考答案:本题非递归算法容易实现,在《数据结构高分笔记》一书中已经讲过,核心算法即为序列的划分,然后递归处理划分好的子序列。非递归算法需要自己申请栈空间以代替系统栈。
划分函数代码如下:
voidsplit(intA[],intlow,inthigh,int&i)
{
intj;
intx;
i=low;j=high;x=A[i];
//初始化
while(i<j)
{
while(A[j]>=x&&i<j)
//从右向左遍历
--j;
if(i<j)
{
A[i]=A[j];++i;
//相当于交换A[i]与A[j]
}
while(A[i]<=x&&i<j)
//从左向右遍历
++i;
if(i<j)
{
A[j]=A[i];--j;
//相当于交换A[i]与A[j]
}
}
A[i]=x;
//x定位在位置i处
}
递归算法代码如下:
voidquicksort(intA[],ints,intt)
{
inti;
if(s<t)
{
split(A,s,t,i);
quicksort(A,s,i-1);
quicksort(A,i+1,t);
}
}
非递归算法代码如下:
voidquicksort2(intA[],intn)
{
inti,l,h;
intstack[maxSize][2],top=-1;
//maxSize是已定义的常量
i=0;h=n-1;
++top;
//入栈
stack[top][0]=1;stack[top][1]=h;
while(top>=0)
{
l=stack[top][0];h=stack[top][1];
//出栈
--top;
split(A,l,h,i);
if(l<h)
{
++top;
//入栈
stack[top][0]=1;stack[top][1]=i-1;
++top;
//入栈
stack[top][0]=i+1;stack[top][1]=h;
}
}
}38.参考答案:可以利用栈解决数制转换问题。例如,4910=1·25+1·24+1·20=1100012,其转换规则是:
式中,bi表示二进制数的第i位上的数字。这样,十进制数N可以用长度为位的二
进制数表示为。若令,则有
N=bj2j+bj-12j-1+…+b121+b020
=(bj2j-1+bj-12j-2+…+b1)×2+b0
=(N/2)×2+N%2('/'表示整除运算)
因此,可以先通过N%2求出b0,然后令N=N/2,再对新的N做除2求模运算可求出b1……如此重复直到某个N等于零结束。这个计算过程是从低位到高位逐个进行的,但输出过程是从高位到低位逐个打印的,为此需要利用栈来实现。代码如下:
intBaseTrans(intN)
{
inti,result=0;
intstack[maxSize],top=-1;
//定义并初始化栈,其中maxSize是已定义的常量,其大小足够处理本题中数据
while(N!=0)
{
i=N%2;
N=N/2;
stack[++top]=i;
}
while(top!=-1)
{
i=stack[top];
--top;
result=result*10+i;
}
returnresult;
}39.参考答案:B[解析]本题主要考查分块查找的相关概念。40.参考答案:C[解析]在不能附加其他任何数据成员的前提下,只能用牺牲一个队列元素的整除取余的方式来区分队空和队满的条件。因此,选项C正确。选项A是判断队列是否为空的条件,选项B和D则是干扰项。41.参考答案:B此题考查的知识点是二部图的定义与存储。二部图定义为:若能将无向图G=<V,E>的顶点集V划分成两个子集V1和V2(V1∩V2)=使得G中任何一条边的两个端点一个属于V1,另一个属于V2,则称G为二部图。由于其特点,其存储矩阵必为分块对称的,所以选B。42.参考答案:如果最终胜者是指具有最小排序码的记录,那么“败者”指的是两个归并段当前参加归并的记录中排序码较大的记录;反之,如果最终胜者是指具有最大排序码的记录,那么“败者”指的是两个归并段当前参加归并的记录中排序码较小的记录。
若利用败者树求m个排序码中的最大者,在某次比较中得到a>b,那么败者是b。43.参考答案:用邻接矩阵存储时,可用以下方法实现:
voidPrint(intv,intstart){//输出从顶点start开始的回路
for(i=1;i<=n;i++)
if(g[v][i]!=0&&visited[i]==1){
//若存在边(v,i),且顶点i的状态为1
printf("%d",v);
if(i==start)printf("\n");
elsePrint(i,start);
break;
}//if
voiddfs(intv){
visited[v]=1;
for(j=1;j<=n;j++)
if(g[v][j]!=0)
//存在边(v,j)
if(visited[j]!=1){if(!visited[j])das(j);}//if
else{cycle=1;Print(j,j);}
visited[vj=2;
}
voidfind_cycle(){
//判断是否有回路,有则输出邻接矩阵。visited数组为全局变量
for(i=1;i<=n;i++)visited[i]=0;
for(i=1;i<=n;i++)if(!visited[i])dfs(i);
}此题考查的知识点是图的遍历。有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问,已访问但其邻接点未访问完,已访问且其邻接点已访问完。下面用0、1、2表示这三种状态。前面已提到,若dfs(v)结束前出现顶点u到v的回边,则图中必有包含顶点v和u的回路。对应程序中v的状态为1,而u是正访问的顶点,若找出u的下一邻接点的状态为1,就可以输出回路了。44.参考
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2023-2024学年江苏省九年级(上)第一次月考数学试卷
- 沪科版八年级数学上册第11章平面直角坐标系11-1平面内点的坐标第1课时平面直角坐标系课件
- 鲁教版八年级数学上册专项素养综合练(九)构造平行四边形解决三类问题课件
- 北师大版八年级生物上册第6单元生命的延续第19章生物的生殖和发育第1节第2课时青春期课件
- 苏教版八年级生物上册第6单元第一节动物行为的主要类型课件
- 全国赛课一等奖英语七年级上册(人教2024年新编)《Unit 2 SectionB 1a-2b》课件
- 统编版五年级语文上册第二单元知识要点
- SZSD 0058-2024政务区块链服务平台应用规范
- 北师大版七年级数学上册《5.2一元一次方程的解法》同步测试题及答案
- 内蒙古鄂托克旗重点达标名校2023-2024学年初中数学毕业考试模拟冲刺卷含解析
- 学校矛盾纠纷排查处理情况登记表
- 家庭教育中的矛盾与冲突处理
- 2024年春江苏开放大学机械CADCAM第一次线下过程性考核操作作业答案
- 集装化与集合包装超炫资料课件
- 人员落水应急演练专项方案
- 2023年浙江省宁波市高中生物竞赛试题(解析版)
- 《价格法概述》课件
- 中医活动文案策划方案
- 初中物理电学全能突破秘籍
- 电容器的充放电过程与应用研究
- 《研究生英语》(第二版)练习答案及译文
评论
0/150
提交评论