《数据结构》练习测试题一.选择题在数据结构中，从逻辑上可以把数据结构分成（C）o动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和非内部结构若频繁地对线性表进行插入和删除操作，该线性表应该采用（C）存储结构。散列B.顺序C.链式D.任意若删除非空线性链表中由p所指链结点的直接后继结点的过程是依次执行（B）r=p->next;p->next=r;callRET（i）i-p->next;p->next=r->next;callRET（r）i-p->next;p->next=r->next;callRET（p）p->next=p->next->next;callRET（p）下面的说法中，不正确的是（D）o只须存放对称矩阵中包括主对角线元素在内的下（或上）三角部分的元素即可只须存放对角矩阵中的非零元素即可稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储串的长度是（D）。串中不同字母的个数串中不同字符的个数串中所含字符的个数，且大于0串中所含字符的个数一个栈的人栈序列是a,b,c,d,e,则栈的不可能的输出序列是（C）°edcbaB.decbaC.dceabD.abcde广义表的长度是指（A）A,广义表中元素的个数B。广义表中原子元素的个数C.广义表中表元素的个数D.广义表中括号嵌套的层数某非空二叉树的前序序列和后序序列正好相反，则二叉树-定是（B）的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（A）。A.nB.n+1C.n-1D.n十e在计算递归函数时，若不用递归则应借助数据结构（D）。A.数组B.队列C.链表D.栈算法分析的目的是（C）：A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性在一个长度为n的顺序表中，向第1个元素（1WiWn+1）之前插入一个新元素时,需要向后移动（C）个元素。A.n-iB.n-i-1C.n-i+1D.i在一个双链表中结点p之后插入一个结点s的操作是（C）。A.s->riglit=p;s->left=p->right;p->iight->left=s;p->nght=ss->nght=p->nght;p->right->left=s;s->iight=p;p->left=ss->nght=p->nght;s->left=p:p->left->left=s;p->right=ss->right=p;p->left->left=s;p->right=s;s->iight=p->nght若将n阶对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，则该对称矩阵在B中占用了(C)个数组元素。A.11/2B.n*(n-l)C.n*(n+l)/2D.n*(n-l)设串s=”ABUBG”,len(s)返回串s的长度，则len⑸是(C)。A.2B.4C.5D.6向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行(C)A.HS->next=S：C.S->next=HS:HS=S：广义表的深度是指(D)A.广义表中元素的个数C.广义表中表元素的个数B・S->next=HS->next:HS->next=S；D・S->next=HS：HS=HS->next；广义表中原子元素甜个数广义表中括号嵌套的层数非空二叉树在线索化后，仍不能有效求解的问题是(D)。A.前序线索二叉树中求前序后继B,中序线索二叉树中求中序后继中序线索二叉树中求中序前趋D.后序线索二叉树中求后序后继一个具有n个顶点的有向图最多有(B)条边。A.iix(n-l)/2B.iix(n-l)C.iix(n+l)/2D.11X1120-依次将待排序膨0中的元素和有序子序列合并为一个新的有序子序列的是(A)。A.插入排序B.冒泡排序C.快速排序D.堆排序算法分析的两个主要方面是(B)。A.空间复杂度和时间复杂度B.正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性若长度为n的线性表采用顺序存储结构，在表的第1个位置插入一个元素的算法的时间复杂度是(A)A.O(n)B.O(n*n)C.O(nlog2n)D.O(log2n)非空的循环单链表head的尾结点(由p所指向)满足(C)。A.p->next=NULL;B.p=NULL;C.p->next=head;D.p=head;若将对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，那么，A中某元素ai(i<0)在B中的位置是(C)。A./2+jB.1))/2与c.U*(j-l))/2+iD.0*(J-l))/2-i设串si瑚ABCDEFG”,s2=”PQRST”^数con(x,y)返回x和y串的连接串,subs(s,山)返回串S的从序号1的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,1en(s2)),subs(sl,len(s2),2))的结果串是(D)。A.BCDEFB.BCDEFGC.BCPQRSTiuBCDEFEF中缀表达式A-(B+C/D)*E的后缀形式是(B)。A.ABC+D/*E-B.ABCD/+E*-C.AB-C+D/E*D.ABC.+D'E*广义表A：«),(a),
luik;deletes;B.ieai-rear->liiik;deleterear;C.rear=rear->liiik->liiik;deleterear;D.s=iear->liiik->-link;reai->luik->liiik=s->luik;deletes;稀疏矩阵一般的压缩存储方法有两种，即(C)。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D,散列和十字链表设串sI=”ABCDEFG”,s2=”PQRST”,函数con(x,y)返回x和y串的连接串,subs(s,山)返回串s的从序号1的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,1en(s2)),subs(sl,len(s2),2))的结果串是(D)。A.BCDEFB.BCDEFGC.BCPQRSTn。BCDEFEF判定一个循环队列QU(最多元素为mO)为满队列的条件是(C)A.QU->fiont==QU->rearB.QU->fiont!=QU->rearC.QU->fiont==(QU->ieai-i-1)%mOD.QU->fiont!=(QU->reai+1)%mO广义表A=(0,(a),(b,(c,d)))的深度为(B)A.2B.3C.4D.5己知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是(D)。A.acbedB.decabC.deabcD.cedba任何一个带权无向连通图的最小生成树(B)oA.是唯一的B.是不唯一的C.有可能不惟一D.有可能不存在快速排序在最好的情况下的时间复杂度是(B)。A.O(n)B.0(nlog2n)C.O(n2)D.0(10g2n)二.判断题线性表的逻辑顺序与存储顺序总是一致的。(F)当字符集中的各字符使用频率不均匀时，等长编码是最优的前缀码。(F)一个栈的输人序列是1,2,3,4,5,则栈的输出序列有可能式4,3,5,1,2。(F)存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。(T)顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。(F)邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。(F)在二叉树中插入结点则该二叉树便不再是二叉树。(F)线性表中的数据元素必须具有相同的特性，即属于同一个数据对象，这种线性表称为同质的线性表。(T)对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得的结点序列称为二叉树的层次序列。(T)任何一个关键活动提前完成，那么整个工程将会提前完成。(F)线性表中的数据元素必须具有相同的特性，即属于同一个数据对象，这种线性表称为同质的线性表。(T)在选择排序中，关键字比较的次数与
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
的初始排列次序无关。(T)用循环链表作为存储结构的队列就是循环队列，这种说法是错误的。(T)任何一棵二叉树中至少有一个结点的度为2。(F)在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。(F)任何有向网络(AOV-网络)拓扑排序的结果是唯一的。(F)队列和栈都是运算受限的线性表。(T)循环链表判断表尾结点用的条件是该结点的后继指针是看它是否为空指针。(F)哈夫曼树是访问叶子结点的外部路径长最长的二叉树。(F)外部排序是指在排序的整个过程中，全部数据在计算机的外存储器中完成的排序。(F)一个直接调用自己或通过一系到的调用语句间接地调用自己的函数，称做递归函数。每个递归函数必须有一个递归出「I。(T)顺序文件是指文件中的物理记录按其在文件中的逻辑记录顺序依次存入存储介质而建立的。(F)广义表的深度是指广义表中元素的个数。(F)要访问单链表中的第1个结点，必须从表头开始依次访问过该结点之前的所有结点后才能够实现，即只能够采用顺序存取，而不能够随机存取任一个结点。(T)在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。(F)任何有向网络(AOV-网络)拓扑排序的结果是唯一的。(T)存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。(F)最先进入队列的数据元素最先推出队列。(T)11个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。(T)快速排序是不稳定的排序算法，希尔排序是稳定的排序算法。(F)n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。(T)在一个无向图中，所有顶点的度数之和等于所有边数的2倍。(T)顺序文件是指文件中的物理记录按其在文件中的逻辑记录顺序依次存入存储介质而建立的。(F)若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。(T)图的最小生成树的形状可能不唯一。(T)缩短关键路径上活动的工期一定能够缩短整个工程的工期。(T)如果某种排序算法是不稳定的，则该方法没有实际的应用价值。(F)一颗非空树中，有旦仅有一个结点没有前驱。(T)图的广度优先搜索算法类似于二叉树的前序遍历。键树是一棵度大于2的树。(F)二、填空题对于顺序表，当随机插入或删除一处元素时，约需要平均移动表长的一半元素。稀疏的三元组有-连续_列。堆栈的插入与删除操作都是在—栈顶―位置进行的，而队列的插入在_队尾_进行,删除在_队头_进行。TOC\o"1-5"\h\z具有100个结点的完全二叉树的深度为7°试写出如下所示的无前驱顶点优先算法求得的拓扑序列为VOV1V5V2V3V6V4无后继顶点优先算法求得的拓扑序列为—>根据形成探查序列的不同，可以将开放地址法区分为：_线性探查法二次探查法_和__双重探查法一。一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为_11*。/在一个小根堆中，堆顶结点的值是所有结点中的最小值，在一个大根堆中，堆顶结点的值是所有结点中的最大值。栈又称为表,队列又称为先进先出表。己知一棵二叉树有50个叶子结点，则该二叉树总的结点个数至少是99,。删除由list所指的非空线性链表的第一个结点的操作是将list改为指向第二个结点，然后释放第一个结点的空间稀疏的三元组中，第2列存储的是稀疏数组中非零元素所在的—列数在栈顶指针为HS的链栈中，判定栈空的条件是_HS==NULL己知一棵二叉树有50个叶子结点，则该二叉树总的结点个数至少是_99在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有向完全图中，包含有n(n-l)条边。键树的存储结构为一双链树一和_Tire树°对于一个长度为n的顺序存储的线性表，在表头插入元素的时间堂杂度为0(1)在表尾插入元素的时间复杂度为_O(n)-快速排序在平均情况下的时间复杂度为,在最坏情况下的时间复杂度为OQF)。一棵深度为5的满二叉树中的结点数为25-1个,一棵深度为3的满四叉树中的结点数为4七1个。树的存储结构分为—双亲链表表示法，孩子链表表示法,_孩子兄弟链表表示法而二叉树的存储结构分为_顺序存储_，_健式存储一在双链表中，每个结点有两个指针域，一个指向项驱结点另一个指向—后续结点。二维数组A[10H20]采用列序为主方式存储，每个元素占一个存储单元，并旦A[0][0]的存储地址是200,则A「61⑵的地址是—332堆栈和队列都是特殊的线性表，其特殊性是—操作仅是一般线性表操作的子集，并且操作的位置受到限制一。在顺序存储的二叉树中,编号为1和J的两个结点处于同一层的条件是「Iog2i=log2il。表示图的三种存储结构为—邻接矩阡_、_邻接表—和_邻接多重表°直接存取文件是用_哈希_的方法组织的。构成抽象数据类型的三个要素为：—数据对象、一数据结构和_数据操作_o假设带头结点的单循环链表中头指针L指向链表中最后一个结点，则在第一个结点之前插入指针s所指结点的语句组是s->next=L->next;L->next=s。栈又称为先进后出表,队列又称为先进先出表。键树的存储结构为一双链树和_Tire树°己知一个图的邻接矩阵表示，计算第1个结点的人度的方法是_求矩阵第1列非零元素之和_。在散列技术中，处理冲突的方法有：_开放定址法_和_拉链法根据形成探查序列的不同，可以将开放地址法区分为：_线性探查法一.—二次探查这一和—双重探查法中缀形式的算术表达式A+(B-C/D)XE的后缀形式是ABCD/-EX+_。若某线性表采用顺序存储结构，每个数据元素占用k个存储单元，第一个数据元素的存储地址为LOC(al)，则第I个数据元素的存储地址LOC(ai)=一LOC(al)+(I-l)*k。判定一个双链表的结点p为第一个结点的条件是p->leH=NULL。二维数组A[10H20]采用列序为主方式存储，每个元素占一个存储单元，并旦A[0][0]的存储地址是200,则A「61⑵的地址是—332_。具有100个结点的完全二叉树的深度为盘有向图进行拓扑排序的两种方法是无前趋的顶点优先_和_无后继的顶点优先。已知一个待排序的序列己基本有序，则在直接选择排序、堆排序、快速排序和直接插入排序中最省时间的是—直接插入排电。四、简答题请分别简答顺序存储结构与链式存储结构的构造原理以及它们的特点。答：线性表的顺序存储结构是在存储器中用一片地址连续的存储单元依次存放线性表中的数据元素，数据元素之间的逻辑关系通过数据元素的存储地址直接反映。在这种存储结构中，逻辑上相邻的两个数据元素在物理位置上也一定相邻。对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现己知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出该二叉树。【解答】己知无向图G=(V,E),其中，顶点集合为V=(vl,v2,v3,v4,v5,v6,v7),,边的集合为((vl,v2),(vl,v3),(v2,vl),(v2,v4),(v2,v6),(v3,vl),(v4,v2),(v4,v7),(v5,v4),(v5,v6),(v6,v2)Xv6,v2),(v7,v4)),请先给出邻接表结构，然后分别给出根据该邻接表从顶点vl出发进行深度优先搜索与广度优先搜索后的顶点序列。【解答】邻接表结构：深度优先搜索序列为:vl,v2,v4,v5,v6,v7,v3广度优先搜索序列为：vl,v2,v3,v4,v6,v5,v7用宽度优先搜索和深度优先搜索对如图所示的无向图G进行遍历(从顶点1出发)，给出【解答】搜索本题图的宽度优先搜索的序列为：12,,4,3,6,5,8,7,深度优先搜索的序列为：1，2,6,4,5,7,8,30指出卜冽算法的时间复杂度。suml(intn){iiitp=I,sum=0,JL;fbr(i=l;i<=n;i-H-)(p*=I;sum+=p;)return(sum);}【解答】sum1()的嵌套最深层语句：p*=I;sum+=p;它的频度为n次，所以其时间复杂度是O(n)°对于一个栈，给出输入项A.B,C。如果输入项序列由A,B,C所组成，试给出全部可能的输出序列。【解答】ABC,ACB,BAC,BCA,CBA有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。【解答】n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。例如：请分别叙述在一个连续顺序文件中采用顺序查找法、折半查找法和分块查找法查找一个记录，该文件记录应该满足什么要求？【解答】采用顺序查找法：文件中记录可以任意次序存放。采用折半查找法：文件中的记录必须按照关键字值从小到大或从大到小有序存放。采用分块查找法：将文件分成若干段，每一块中的记录可以任意存放，但块与块之间必须按照关键字从小到大或从大到小的次序存放，即前一块中的所有记录的关键字值必须小于后一块中所有记录的关键字值。试对右图所示的AOE网络：这个工程最早可能在什么时间结束。求每个活动的最早开始时间e()和最退开始时间1()。确定哪些活动是关键活动。【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间VI。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间1,根据1-e=0^来确定关键活动，从而确定关键路径。此工程最早完成时间为43。关键路径为VI,3X3,2><2,5><5,6>何为数据的逻辑结构？何为数据的存储结构？一般情况下，两者之间有什么联系？这种联系是如何反映的？【解答】数据的逻辑结构是指数据元素之间在客观世界中所具有的逻辑关系。数据的存储结构是指数据在计算机存储器中的存储方式。在数据的顺序存储与链式存储结构中，通常要能够反映数据所具有的逻辑结构。在顺序存储结构中，通过数据元素的存储地址来直接反映数据元素之间的逻辑关系，而链式存储结构则是通过指针来间接反映数据元素之间的逻辑关系。分别写出如图所示各二叉树的前序、中序和后序序列【解答】：前序12357864124735689中序17583624472153869后序78563421742589631画出卜图所示的AOV网的所有拓扑有序序列。【解答】ADBECFADBEFCADEBCFADEBFCDABECFDABEFCDAEBCFDAEBFC何为数据的逻辑结构？何为数据的存储结构？一般情况下，两者之间有什么联系？这种联系是如何反映的？【解答】数据的逻辑结构是指数据元素之间在客观世界中所具有的逻辑关系。数据的存储结构是指数据在计算机存储器中的存储方式。在数据的顺序存储与链式存储结构中，通常要能够反映数据所具有的逻辑结构。在顺序存储结构中，通过数据元素的存储地址来直接反映数据元素之间的逻辑关系，而链式存储结构则是通过指针来间接反映数据元素之间的逻辑关系已知序列(35,70,12,26,90,41,66,58),请写出对该序列采用泡排序方法进行升序排序时各趟的结果。【解答】原始序列：35,78,12,26,90,41,66,58第一趟后：35,12,26,78,41,66,58,90第二趟后:12,26,35,41,66,58,78,90第三趟后：12,26,35,41,58,66,78,90第四趟后:12,26,35,41,58,66,78,90何为数据的逻辑结构？何为数据的存储结构？一般情况下，两者之间有什么联系？这种联系是如何反映的？【解答】数据的逻辑结构是指数据元素之间在客观世界中所具有的逻辑关系。数据的存储结构是指数据在计算机存储器中的存储方式。在数据的顺序存储与链式存储结构中，通常要能够反映数据所具有的逻辑结构。在顺序存储结构中，通过数据元素的存储地址来直接反映数据元素之间的逻辑关系，而链式存储结构则是通过指针来间接反映数据元素之间的逻辑关系。给定一组权值:23,15,66,07,11,45,33,52,39,26,58,试构造一棵具有最小带权外部路径长度的扩充4叉树，要求该4叉树中所有内部结点的度都是4,所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少？【解答】仿照霍夫曼树的构造方法来构造扩充4叉树，每次合并4个结点。0H□回回回国回回回回囱回己知序列(35,78,12,26,66,41,66,58)，请写出对该序列采用选择排序方法进行升序排序时各趟的结果。【解答】原始序列：35,78,12,26,90,41,66,58第一趟后：12,78,35,26,90,41,66,58第二趟后：12,26,35,78,90,41,66,58第三趟后：12,26,35,78,90,41,66,58第四趟后：12,26,35,41,90,78,66,58第五趟后：12,26,35,41,58,78,66,90第六趟后：12,26,35,41,58,66,78,90第七趟后：12,26,35,41,58,66,78,90数据逻辑结构包括哪三种类型？树形结构和图形结构合称为什么？【解答】包括线性结构、树形结构和图形结构。树形结构和图形结构合称为非线性结构19.请分别叙述在一个连续顺序文件中采用顺序查找法、折半查找法和分块查找法查找一个记录，该文件记录应该满足什么要求？【解答】采用顺序查找法：文件中记录可以任意次序存放。采用折半查找法：文件中的记录必须按照关键字值从小到大或从大到小有序存放。采用分块查找法：将文件分成若干段，每一块中的记录可以任意存放，但块与块之间必须按照关键字从小到大或从大到小的次序存放，即前一块中的所有记录的关键字值必须小于后一块中所有记录的关键字值。20.有向图的邻接表如F试给出至少两个拓扑序列。【解答】VIV2V3V4V5V6VIV3V2V4V5V6五、算法题巳知非空双向循环链表最左边那个链结点的指针为list,请写一逆置该双向循环链表的算法【解答】procedureINVERT(list)pVI-listrepeatq~linXp)rlink(p)-Uink(p)llink(p)until(p=Est)end借助栈将输入任意一个非负的十进制数，打印输出与其等值的八进制。【解答】conversion()(InitStack(s);scanf(H%d,\n);wliile(n){Push(S,n%8);n=n/8;}wlule(?StackEnipty(s)){Pop(s,X);priintf(”％d”,X)}}设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。解答1】templatevoidList::Inverse(){if(fust=NULL)remin;ListNode*p=firstslink;,*pr=NULL;wliile(p!=NULL)(first-*link=pr;〃逆转fiist指针pr=fiist;first=p;p=pflink;〃指针前移))【解答2】templatevoidList::Inverse(){ListNode*head=newListNode();wliile(fiist!=NULL)(p=fiist;fust=first—link;//摘卜fiist链头结点pflink=head-*link;head-*link=p;〃插入head链前端)first=headlink;deletehead;〃重置fiist)有一个循环双链表，每个结点由两个指针(light和left)以及关键字(key)构成，p指向其中某一结点，编写一个函数从该循环双链表中删除p所指向的结点。【解答】本题的关键是找出p所指结点的前后结点，这可以循环指针找到。实现本题功能的函数如下：structdlist(intkey；structdlist*left,*right;voiddehiode(p)structdlist*p;(structdlist*q,*r;q=p；while(q->iight!=p)q=q->iight;r=p;while(r->left!=p)r=i•->left;q->nght=i;r->left=q;fiee(p);while(r->left!=p)r=i•->left;q->nght=i;r->left=q;fiee(p);已知一个顺序表A中的元素按值非递减有序，编写一个函数插入一个元素X后保持该顺序表是有序的【解答】#defineMAX100typedefintvector[MAX]voidinsert(vectorA.iiitn,x)(mtJ;if(x>=A[n])A[n+1]=x;else{1=1;while(x>=A[i])i++;for(j=nj>=ij-)A[j+l]=A|j];A[i]=x;n++；}}试写出后序遍历二叉树的递归算法。【解答】设t为指针，且其存储结构为二叉链表，则可将算法描述为:postorder(t)/*后序遍历二叉树*/bitreet;/设其类型为bitree*/(if(t)/*二叉树t非空〃{postoider(t->lchild);/*后序遍历二叉树t的左子树*/postordei(t->rcluld);/*后序遍历二叉树t的右子树*/pnntf(”\t%c\iT,t->data);/*访问结点*/}}/postorder*/7.
浙公网安备 33021202002483