《数据结构》练习测试题.doc

数据结构练习测试题一选择题1在数据结构中，从逻辑上可以把数据结构分成（ C ）。A 动态结构和静态结构 B 紧凑结构和非紧凑结构C 线性结构和非线性结构 D 内部结构和非内部结构2若频繁地对线性表进行插入和删除操作，该线性表应该采用（C ）存储结构。 A散列 B.顺序 C.链式 D.任意 3若删除非空线性链表中由p所指链结点的直接后继结点的过程是依次执行(B )Ar=p-next; p-next=r; call RET(r)Br=p-next; p-next=r-next; call RET(r)Cr=p-next; p-next=r-next; call RET(p)Dp-next=p-next-next; call RET(p)4下面的说法中，不正确的是（ D ）。 A只须存放对称矩阵中包括主对角线元素在内的下(或上)三角部分的元素即可 B只须存放对角矩阵中的非零元素即可 C稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储 D稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储5串的长度是( D )。 A串中不同字母的个数 B串中不同字符的个数 C串中所含字符的个数，且大于0 D串中所含字符的个数6一个栈的人栈序列是a，b，c，d，e，则栈的不可能的输出序列是( C )。 Aedcba Bdecba Cdceab Dabcde7广义表的长度是指（ A） A，广义表中元素的个数 B。广义表中原子元素的个数 C广义表中表元素的个数 D广义表中括号嵌套的层数8某非空二叉树的前序序列和后序序列正好相反，则二叉树-定是( B )的二叉树。A.空或只有一个结点 B高度等于其结点数C.任一结点无左孩子 D任一结点无右孩子9. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为( A )。An Bn+1 Cn-l Dn十e10在计算递归函数时，若不用递归则应借助数据结构( D )。 A. 数组 B. 队列 C. 链表 D. 栈11算法分析的目的是（ C ）；. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性12在一个长度为n 的顺序表中，向第i个元素（1 i n）之前插入一个新元素时，需要向后移动（C ）个元素。 A.n-i B.n-i-1 C.n-i+1 D.i13在一个双链表中结点p之后插入一个结点s的操作是( C )。 A. s-right=p;s-left=p-right;p-right-left=s;p-right=s B. s-right=p-right;p-right-left=s;s-right=p;p-left=s C. s-right=p-right;s-left=p;p-left-left=s;p-right=s D. s-right=p;p-left-left=s;p-right=s;s-right=p-right14若将n阶对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，则该对称矩阵在B中占用了( C )个数组元素。 An/2 Bn*(n-1) Cn*(n+1)2 Dn*(n-1)15设串s=ABUBG,len(s)返回串s的长度，则len(s)是( C )。 A2 B4 C5 D616向一个栈顶指针为HS的链栈中插入个s所指结点时，则执行( C ) AHS-next=S； BS-next=HS-next；HS-next=S； CS-next=HS；HS=S； DS-next=HS；HS=HS-next；17广义表的深度是指 ( D ) A广义表中元素的个数 B广义表中原子元素甜个数 C. 广义表中表元素的个数 D广义表中括号嵌套的层数18非空二叉树在线索化后，仍不能有效求解的问题是(D )。A前序线索二叉树中求前序后继 B中序线索二叉树中求中序后继C.中序线索二叉树中求中序前趋 D后序线索二叉树中求后序后继19. 一个具有n个顶点的有向图最多有( B )条边。Anx(n-1)2 Bnx(n-1)Cnx(n+1)2 Dnxn20依次将待排序膨0中的元素和有序子序列合并为一个新的有序子序列的是( A )。A插入排序 B冒泡排序 C.快速排序 D堆排序21算法分析的两个主要方面是（ B ）。A. 空间复杂度和时间复杂度 B. 正确性和简单性 C可读性和文档性 D. 数据复杂性和程序复杂性22若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个元素的算法的时间复杂度是（ A）.O(n) B.O(n*n) C.O(nlog2n) D.O(log2n)23非空的循环单链表head的尾结点（由p所指向）满足（ C ）。A.p-next=NULL; B.p=NULL;C.p-next=head; D.p=head;24若将对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，那么，A中某元素ai(i0)在B中的位置是( C )。 A(i*(i-1)2+j B(i*(i-1)2-j C(j*(j-1)2+i D(j*(j-1)/ 2-i25设串sI=ABCDEFG,s2=PQRST,函数con(x,y)返回x和y串的连接串,subs(s，山)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,1en(s2)，subs(sl,len(s2)，2)的结果串是( D )。 ABCDEF BBCDEFG CBCPQRST n。BCDEFEF26中缀表达式A-(B+CD)*E的后缀形式是( B )。 AABC+D*E- BABCD+E*- CAB-C+DE* DABC-+D/E*27广义表A：)，(a)，b，link;delete s; B.rear=rear-link;delete rear;C.rear=rear-link-link;delete rear; D. s=rear-link-link;rear-link-link=s-link;delete s;34稀疏矩阵一般的压缩存储方法有两种，即 ( C )。A二维数组和三维数组 B三元组和散列C. 三元组和十字链表 D散列和十字链表35设串sI=ABCDEFG,s2=PQRST,函数con(x,y)返回x和y串的连接串,subs(s，山)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,1en(s2)，subs(sl,len(s2)，2)的结果串是( D )。 ABCDEF BBCDEFG CBCPQRST n。BCDEFEF36判定一个循环队列QU(最多元素为m0)为满队列的条件是( C ) AQU-front=QU-rear BQU-front!=QU-rear CQU-front=(QU-rear+1)m0 DQU-front!=(QU-rear+1)m037广义表A=()，(a)，(b，(c，d)的深度为( B ) A2 B3 C4 D538已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是( D )。 Aacbed Bdecab Cdeabc Dcedba39. 任何一个带权无向连通图的最小生成树( B )。 A是唯一的 B是不唯一的 C有可能不惟一 D有可能不存在40快速排序在最好的情况下的时间复杂度是( B )。AO(n) B0(nlog2n) CO(n2) D0(10g2n)二判断题1. 线性表的逻辑顺序与存储顺序总是一致的。 ( F )2. 当字符集中的各字符使用频率不均匀时，等长编码是最优的前缀码。 ( F )3. 一个栈的输人序列是1，2，3，4，5，则栈的输出序列有可能式4,3,5,1,2。 ( F )4. 存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。 ( T )5. 顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 （ F ）6. 邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 ( F )7. 在二叉树中插入结点则该二叉树便不再是二叉树。 ( F )8. 线性表中的数据元素必须具有相同的特性，即属于同一个数据对象，这种线性表称为同质的线性表。 （ T ）9. 对二叉树中的结点进行按层次顺序（每一层自左至右）的访问操作称为二叉树的层次遍历，遍历所得的结点序列称为二叉树的层次序列。 （T ）10. 任何一个关键活动提前完成，那么整个工程将会提前完成。 （ F ）11. 线性表中的数据元素必须具有相同的特性，即属于同一个数据对象，这种线性表称为同质的线性表。 ( T )12. 在选择排序中，关键字比较的次数与记录的初始排列次序无关。 ( T )13. 用循环链表作为存储结构的队列就是循环队列，这种说法是错误的。 ( T )14. 任何一棵二叉树中至少有一个结点的度为2。 ( F )15. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 （ F ）16. 任何有向网络（AOV-网络）拓扑排序的结果是唯一的。 ( F )17. 队列和栈都是运算受限的线性表。 ( T )18. 循环链表判断表尾结点用的条件是该结点的后继指针是看它是否为空指针。 （ F ）19. 哈夫曼树是访问叶子结点的外部路径长最长的二叉树。 （ F ）20. 外部排序是指在排序的整个过程中，全部数据在计算机的外存储器中完成的排序。 （F ）21. 一个直接调用自己或通过一系到的调用语句间接地调用自己的函数，称做递归函数。每个递归函数必须有一个递归出口。 ( T )22. 顺序文件是指文件中的物理记录按其在文件中的逻辑记录顺序依次存入存储介质而建立的。 ( F )23. 广义表的深度是指广义表中元素的个数。 ( F )24. 要访问单链表中的第i个结点，必须从表头开始依次访问过该结点之前的所有结点后才能够实现，即只能够采用顺序存取，而不能够随机存取任一个结点。 ( T )25. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 （F ）26. 任何有向网络（AOV-网络）拓扑排序的结果是唯一的。 (T )27. 存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。 ( F )28. 最先进入队列的数据元素最先推出队列。 （ T ）29. n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。 （ T ）30. 快速排序是不稳定的排序算法，希尔排序是稳定的排序算法。 （ F ）31. n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。 ( T ) 32. 在一个无向图中，所有顶点的度数之和等于所有边数的2倍。 ( T )33. 顺序文件是指文件中的物理记录按其在文件中的逻辑记录顺序依次存入存储介质而建立的。 ( F )34. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。 （ T ） 35. 图的最小生成树的形状可能不唯一。 （ T ）36. 缩短关键路径上活动的工期一定能够缩短整个工程的工期。 ( T )37. 如果某种排序算法是不稳定的，则该方法没有实际的应用价值。 ( F )38. 一颗非空树中，有且仅有一个结点没有前驱。 （ T ）39. 图的广度优先搜索算法类似于二叉树的前序遍历。 （ F ）40. 键树是一棵度大于2的树。 （F ） 三、填空题1. 对于顺序表，当随机插入或删除一处元素时，约需要平均移动表长的 一半 元素。2. 稀疏的三元组有_ 连续 _列。3. 堆栈的插入与删除操作都是在_栈顶 _位置进行的，而队列的插入在_队尾 _进行，删除在_队头 _ 进行。4. 具有100个结点的完全二叉树的深度为_7 _。5. 试写出如下所示的无前驱顶点优先算法求得的拓扑序列为 V0 V1V5V2V3V6V4 _，无后继顶点优先算法求得的拓扑序列为_ V4 V6 V3 V2 V5 V1 V0_ _。6. 根据形成探查序列的不同，可以将开放地址法区分为：_线性探查法_,_二次探查法 _和_双重探查法_。7. 一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为_ n*n _。8. 在一个小根堆中，堆顶结点的值是所有结点中的 最小值 ，在一个大根堆中，堆顶结点的值是所有结点中的 最大值 。9.栈又称为 先进后出 表，队列又称为 先进先出 表。10. 已知一棵二叉树有50个叶子结点，则该二叉树总的结点个数至少是_ 99 _。11. 删除由list所指的非空线性链表的第一个结点的操作是 将list改为指向第二个结点，然后释放第一个结点的空间 12. 稀疏的三元组中,第2列存储的是稀疏数组中非零元素所在的_列数 _。13. 在栈顶指针为HS的链栈中，判定栈空的条件是_ HS=NULL _。14. 已知一棵二叉树有50个叶子结点，则该二叉树总的结点个数至少是_ 99 _。15. 在一个具有n个顶点的无向完全图中，包含有_ n(n-1)/2 _条边，在一个具有n个顶点的有向完全图中，包含有 n(n-1) 条边。16. 键树的存储结构为_ 双链树 _和_ Tire树 。17. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_ O(1) _，在表尾插入元素的时间复杂度为_ O(n) _。18. 快速排序在平均情况下的时间复杂度为 O(nlog(n) ，在最坏情况下的时间复杂度为 O(n2) 。19.一棵深度为5的满二叉树中的结点数为 25-1 个，一棵深度为3的满四叉树中的结点数为 43-1 个。20. 树的存储结构分为_双亲链表表示法 ，孩子链表表示法，_孩子兄弟链表表示法 _，而二叉树的存储结构分为_ 顺序存储_，_链式存储 _。21. 在双链表中，每个结点有两个指针域，一个指向_前驱结点 _，另一个指向_后续结点。22. 二维数组A1020采用列序为主方式存储，每个元素占一个存储单元，并且A00的存储地址是200,则A62的地址是_ 332 _。23. 堆栈和队列都是特殊的线性表，其特殊性是_操作仅是一般线性表操作的子集，并且操作的位置受到限制 _。24. 在顺序存储的二叉树中，编号为i和j的两个结点处于同一层的条件是_ log2i=log2j 。25. 表示图的三种存储结构为_邻接矩阵_、_邻接表_和_ 邻接多重表 。26. 直接存取文件是用_ 哈希 _的方法组织的。27. 构成抽象数据类型的三个要素为：_数据对象、_数据结构和_ 数据操作 _。28. 假设带头结点的单循环链表中头指针L指向链表中最后一个结点，则在第一个结点之前插入指针 s 所指结点的语句组是 s-next=L-next; L-next=s 。29.栈又称为先进后出 表，队列又称为先进先出 表。30. 键树的存储结构为_ 双链树 和_ Tire树 。31. 己知一个图的邻接矩阵表示，计算第i个结点的人度的方法是_ 求矩阵第i 列非零元素之和_。32. 在散列技术中，处理冲突的方法有：_开放定址法_和_ 拉链法_。33. 根据形成探查序列的不同，可以将开放地址法区分为：_线性探查法_,_二次探查法_和_双重探查法34. 中缀形式的算术表达式A+(B-CD)XE的后缀形式是 ABCD-EX+ _。35. 若某线性表采用顺序存储结构，每个数据元素占用k个存储单元，第一个数据元素的存储地址为LOC（a1）,则第I 个数据元素的存储地址LOC（ai）=_ LOC(a1)+(I-1)*k。36. 判定一个双链表的结点p为第一个结点的条件是_ p-left=NULL_ _。37. 二维数组A1020采用列序为主方式存储，每个元素占一个存储单元，并且A00的存储地址是200,则A62的地址是_ 332_。38. 具有100个结点的完全二叉树的深度为_ 7 _。39.有向图进行拓扑排序的两种方法是无前趋的顶点优先_和_无后继的顶点优先。40. 已知一个待排序的序列已基本有序，则在直接选择排序、堆排序、快速排序和直接插入排序中最省时间的是_直接插入排序_。四、简答题1. 请分别简答顺序存储结构与链式存储结构的构造原理以及它们的特点。答：线性表的顺序存储结构是在存储器中用一片地址连续的存储单元依次存放线性表中的数据元素，数据元素之间的逻辑关系通过数据元素的存储地址直接反映。在这种存储结构中，逻辑上相邻的两个数据元素在物理位置上也一定相邻。2. 对二叉树中的结点进行按层次顺序（每一层自左至右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树。【解答】3. 已知无向图G=(V,E)，其中，顶点集合为V=v1,v2,v3,v4,v5,v6,v7,，边的集合为(v1,v2),(v1,v3),(v2,v1),(v2,v4),(v2,v6),(v3,v1),(v4,v2),(v4,v7),(v5,v4),(v5,v6),(v6,v2),(v6,v2),(v7,v4),请先给出邻接表结构，然后分别给出根据该邻接表从顶点v1出发进行深度优先搜索与广度优先搜索后的顶点序列。【解答】邻接表结构：深度优先搜索序列为： v1，v2，v4，v5，v6，v7，v3 广度优先搜索序列为： v1，v2，v3，v4，v6，v5，v74. 用宽度优先搜索和深度优先搜索对如图所示的无向图G进行遍历(从顶点1出发)， 给出遍历序列【解答】搜索本题图的宽度优先搜索的序列为：12，4，3，6，5，8，7，深度优先搜索的序列 为：1，2，6，4，5，7，8，305. 指出下列算法的时间复杂度。 sum1(int n) int p=1,sum=0,1; for(i=1;i=n;i+) p*=I; sum+=p; return(sum); 【解答】 sum1()的嵌套最深层语句：p*=I; sum+=p;它的频度为n次，所以其时间复杂度是O(n)。6. 对于一个栈，给出输入项A,B,C。如果输入项序列由A,B,C所组成，试给出全部可能的输出序列。【解答】ABC，ACB，BAC，BCA，CBA7. 有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。【解答】n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。例如：8. 请分别叙述在一个连续顺序文件中采用顺序查找法、折半查找法和分块查找法查找一个记录，该文件记录应该满足什么要求？【解答】采用顺序查找法：文件中记录可以任意次序存放。采用折半查找法：文件中的记录必须按照关键字值从小到大或从大到小有序存放。采用分块查找法：将文件分成若干段，每一块中的记录可以任意存放，但块与块之间必须按照关键字从小到大或从大到小的次序存放，即前一块中的所有记录的关键字值必须小于后一块中所有记录的关键字值。9. 试对右图所示的AOE网络:(1) 这个工程最早可能在什么时间结束。(2) 求每个活动的最早开始时间e( )和最迟开始时间l( )。(3) 确定哪些活动是关键活动。【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。此工程最早完成时间为43。关键路径为10. 何为数据的逻辑结构？何为数据的存储结构？一般情况下，两者之间有什么联系？这种联系是如何反映的？【解答】数据的逻辑结构是指数据元素之间在客观世界中所具有的逻辑关系。数据的存储结构是指数据在计算机存储器中的存储方式。在数据的顺序存储与链式存储结构中，通常要能够反映数据所具有的逻辑结构。在顺序存储结构中，通过数据元素的存储地址来直接反映数据元素之间的逻辑关系，而链式存储结构则是通过指针来间接反映数据元素之间的逻辑关系。11分别写出如图所示各二叉树的前序、中序和后序序列【解答】：（1）前序（a） （b） （2）中序 (a ) (b) （3）后序 (a ) (b) 12. 画出下图所示的AOV网的所有拓扑有序序列。【解答】ADBECF ADBEFCADEBCFADEBFCDABECFDABEFCDAEBCFDAEBFC13. 何为数据的逻辑结构？何为数据的存储结构？一般情况下，两者之间有什么联系？这种联系是如何反映的？【解答】数据的逻辑结构是指数据元素之间在客观世界中所具有的逻辑关系。数据的存储结构是指数据在计算机存储器中的存储方式。在数据的顺序存储与链式存储结构中，通常要能够反映数据所具有的逻辑结构。在顺序存储结构中，通过数据元素的存储地址来直接反映数据元素之间的逻辑关系，而链式存储结构则是通过指针来间接反映数据元素之间的逻辑关系14 . 已知序列(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，9015. 何为数据的逻辑结构？何为数据的存储结构？一般情况下，两者之间有什么联系？这种联系是如何反映的？【解答】数据的逻辑结构是指数据元素之间在客观世界中所具有的逻辑关系。数据的存储结构是指数据在计算机存储器中的存储方式。在数据的顺序存储与链式存储结构中，通常要能够反映数据所具有的逻辑结构。在顺序存储结构中，通过数据元素的存储地址来直接反映数据元素之间的逻辑关系，而链式存储结构则是通过指针来间接反映数据元素之间的逻辑关系。16给定一组权值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外部路径长度的扩充4叉树, 要求该4叉树中所有内部结点的度都是4, 所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少?【解答】仿照霍夫曼树的构造方法来构造扩充4叉树，每次合并4个结点。 17. 已知序列(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，9018. 数据逻辑结构包括哪三种类型？树形结构和图形结构合称为什么？【解答】 包括线性结构、树形结构和图形结构。 树形结构和图形结构合称为非线性结构19 . 请分别叙述在一个连续顺序文件中采用顺序查找法、折半查找法和分块查找法查找一个记录，该文件记录应该满足什么要求？【解答】采用顺序查找法：文件中记录可以任意次序存放。采用折半查找法：文件中的记录必须按照关键字值从小到大或从大到小有序存放。采用分块查找法：将文件分成若干段，每一块中的记录可以任意存放，但块与块之间必须按照关键字从小到大或从大到小的次序存放，即前一块中的所有记录的关键字值必须小于后一块中所有记录的关键字值。20. 有向图的邻接表如下试给出至少两个拓扑序列。【解答】V1 V2 V3 V4 V5 V6V1 V3 V2 V4 V5 V6五、算法题1. 已知非空双向循环链表最左边那个链结点的指针为list,请写一逆置该双向循环链表的算法【解答】2. 借助栈将输入任意一个非负的十进制数,打印输出与其等值的八进制。【解答】conversion( )InitStack(s); scanf(%d,n);while(n)Push(S,n%8); n=n/8; while(!StackEmpty(s) Pop(s,X); priintf(%d,X) 3. 设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。解答1】template void List : Inverse ( ) if ( first = NULL ) return;ListNode