数据结构复习题及答-数据结构“”

1、数据结构习题一、名词解释1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度。2. 线性表、顺序表、单链表 、双向链表、循环链表 、双向循环链表、三个概念的区别：头指针、头结点、首元结点（第1个元素结点 ）。3. 栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。4. 树、叶子结点、结点的度、树的度、树的高（深）度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL哈夫曼编码。5. 图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、（最小）生成树、邻接矩阵、邻接

2、表、DFS BFS6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。7. 排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2 路归并。填空题1. 数据结构是研究数据的 _逻辑结构_和物理结构_，并在这种结构上定义相关的运算，设计实现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为时间复杂度 和空间复杂度。2. 数据的基本单位是数据元素，数据的最小单位是数据项 。3. 算法是对特定问题求解 步骤_的一种描述，是指令的有限序列。4. 一个算法的时间复杂度为 （3n3+2n 7），其数量级表示为

3、_0 （ n3）_。5. 一个算法具有5个特性：_确定性、可行性_、_有穷性_、输入和输出。6. 算法性能的分析和度量，可以从算法的时间复杂度一和空间复杂度来评价算法的优劣。7. 数据的逻辑结构包括集合结构、_线性结构 _、树形结构_和_图型结构四种类型。8. 数据结构在计算机中的表示称为数据的物理结构，它可以采用_顺序存储_ 或_链式存储_两种存储方法。9. 线性表有两种存储结构，分别为_顺序存储 _ 和 链式存储_。10. 链式存储的特点是利用指针来表示数据元素之间的逻辑关系。11. 若频繁地对线性表进行插入和删除操作，该线性表宜采用链式存储存储结构。12. 线性表中的数据元素之间具有_一

4、对一_的线性关系，除第一个和最后一个元素外，其他数据元素有且只有一个_直接后继和直接前趋。13. 在一个单链表中 p所指结点之后插入一个s所指结点时，应执行 s-next=_ p-next和p-next=_ s的操作。14. 在一个单链表中删除 p的后继结点q时，应执行以下操作 p-next=q-next。head-next=NULL15. 对带头结点head的单链表，则判断其为空的条件为16. 对带头结点head的循环单链表尾结点(由p所指向)判非空的条件为 _p-next=head 。17. 在栈结构中，允许插入的一端称为 _栈顶;在队列结构中，允许插入的一端称为_队尾。18. 队列中元素

5、的入队和出队应遵循一先进先出_ _原则，数据元素1，2, 3, 4，5按照次序入队后，第一个出队的是 _1。19. 在循环队列中，存储空间为0n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front ，队满标志为_(rear+1)% n=front_。20. 设顺序表有19个元素，第一个元素的地址为200,且每个元素占3个字节，则第14个元素的存储地址为_239。21. 在一个长度为n的顺序表中删除第i个元素(K i n),需向前移动n-i 个元素。22. 在一个长度为 n的顺序表中第i个元素前(K i lchild=NULL & p-

6、rchild=NULL 。80. 栈是一种 _先进后出表。队列又称为先进先出 表。81. 若对序列(49 , 38, 65, 97, 76, 13, 27, 50)采用直接选择排序法排序，则第三趟结束后序列的82. 利用关键码分别为 10,20,30,40的四个结点，能构造出 _14_种不同的二叉排序树.83. 设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行(按递增排序)，冒泡排序最省时间，快速排序最费时间。84. 空串的长度是_0_；空格串的长度是_空格的个数_。串中所含字符个数称为该串的_长度_.85. 在n个结点的单链表中，在 P指向的结点之后

7、插入一个结点的时间复杂度为_ O(n) _。86. 设SQ为循环队列，存储在数组dm中，贝U SQ出队操作对其队头指针front的修改是 _front=(front+1 ) % m=。87. 树的度是指树内各结点的度 的最大值。88. 已知链栈的结点结构为栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为_p_next=top _ 和 _top=p _ o89. 堆排序的空间复杂度_ O(1) _o90. 深度为n(n0)的二叉树最多有25-1个结点。91. 设关键字序列为(K, K2,，Kn)，则用筛选法建初始堆必须从第_n/2个元素开始进行筛选。92. 图有_邻接矩阵 、邻接表_

8、等存储结构，遍历图有_深度优先搜索 _、广度优先搜索_等方法。93. 在一个有向图的邻接表中，一个顶点的链表中结点的个数等于这个顶点的_出度_，在逆邻接表中，一个顶点的链表中结点的个数等于这个顶点的入度 。94. 对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是 ，3, 6, 9一 。95. 折半查找有序表(4, 6, 12, 20, 28, 38, 50, 70, 88, 100),若查找表中元素20,它将依次与表中元素比较大小。96. 在对一组记录关键字(54, 38, 96, 23, 15, 72, 60, 45, 83)进行冒泡排序

9、时，整个冒泡排序 过程中需进行_8_趟才能完成。97. 对关键字序列(52 , 80 , 63, 44, 48, 91)进行一趟快速排序之后得到的结果为48 , 44, 52, 63,80, 91。98. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ;若初始记录基本无序，则最好选用快速排序。99. 在对一组记录(54,38,96,23,15,72, 60,45,83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较_3次。100. 设一组记录关键字序列为(80, 70, 33, 65, 24, 56, 48)，则用筛选法建成的初始堆为_ ( 8

10、0,70, 56, 65, 24, 33, 48)或 _(24 , 65, 33, 80, 70, 56, 48)。1.2.3.4.5.6.7.8.9.10.11.二、单选题在数据结构中，数据的基本单位是 （ ）A. 数据项 B. 数据元素 C. 数据对象 D. 数据文件 数据结构是（ ）A. 种数据类型B数据的存储结构C. 一组性质相同的数据元素的集合D.相互之间存在一种或多种特定关系的数据元素的集合在数据结构的讨论中把数据结构从逻辑上分为（）.A. 内部结构与外部结构B. 静态结构与动态结构C. 线性结构与非线性结构D. 紧凑结构与非紧凑结构。算法指的是（）。A.计算机程序B .解决问题的

11、计算方法C .排序算法D .解决问题的有限运算序列算法分析的目的是（A.辨别数据结构的合理性B .评价算法的效率C.研究算法中输入与输出的关系.鉴别算法的可读性某程序的时间复杂度为（ 3n+nlog2n+n2+8） , 其数量级表示为（）。A. O（ n）B . O（ nlog 2n）C . O（ n ）D . O（ log 2n）for （ i=0 ； in ； i+ ）for （ j=0 ； jnext=NULLC. head!=NULLD. head-next=head16. 已知栈的最大容量为4。若进栈序列为1，2， 3，4，5，6，且进栈和出栈可以穿插进行, 则可能出现的出栈序列为(

12、A.5， 4， 3， 2， 1， 6B.2， 3，5，6，1，C.3， 2， 5， 4， 1， 6D.1， 4，6，5，2，17. 若某线性表中最常用的操作是取第个元素和找第 i 个元素的前趋元素， 则采用(存储方式最节省时间。A.单链表B. 双链表C.单向循环D. 顺序表18. 对一个算法的评价，不包括如下(方面的内容。A .健壮性和可读性B .并行性C .正确性D .时空复杂度19. 队列的删除操作是在()进行。A队首 B 队尾 C 队前.对后20. 计算机识别、存储和加工处理的对象被统称为A. 数据B.数据元素C.数据结构D.数据类型21. 串是任意有限个( 符号构成的序列 符号构成的集

13、合 字符构成的序列 字符构成的集合22. 如果以链表作为栈的存储结构，则退栈操作时( 必须判别栈是否满 对栈不作任何判别 必须判别栈是否空 判别栈元素的类型23. 二分查找要求被查找的表是( 键值有序的链接表链接表但键值不一定有序 键值有序的顺序表顺序表但键值不一定有序24. 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为( ) n2 nlog2n log2n n-125.堆是一个键值序列k1,k2,kn,对i=1,2. ,|_n/2_|,满足 () ki k2i w k2i+1 kik2i+1next= =NULLD.head - next= =head34.在单链表

14、中,指针p指向值为x的结点，能实现“删除 x的后继”的语句是A. p=p-next ;B. p=p-next-next ;C. p-next=p ;D. p-next=p-next-next;35.一个栈的入栈序列是a, b, c, d, e,则栈的输出序列不可能是 ()A. dceabB. decbaC. edcbaD. abcde36. 若进栈序列为a, b, c,进栈过程中允许出栈，则以下 是不可能得到的出栈序列。A. a,b,c B. b,a,cC. c,a,bD. c,b,a37. 若进栈序列为1 ,2,3, 4,进栈过程中允许出栈，则可能的出栈序列是。C. 3,4,1,2D. 1,

15、2,3,438. 设有一个栈，按A、B C D的顺序进栈，则可能为出栈序列的是A. DCBA B.CDABC.DBAC D.DCAB39. 一个队列的入队序列是1， 2， 3， 4，则队列的输出序列是 ()A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,140. 个最多能容纳m个元素的顺序存储循环队列Q其头尾指针分别为front和rear ,则判定该队列为满的条件是 A. (Q.rear+1)%m= =Q.front B. Q.front= =Q.rearC. Q.rear+1= =Q.front D. (Q.front+1)%m= =Q.rearA.fro

16、nt=front+141. 设数组Datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出 队操作的语句为().B. front=(front+1)% mC.rear=(rear+1)%mD.front=(front+1)%(m+1)42. 假设以数组 An 存放循环队列的元素，其头、尾指针分别为front 和 rear 。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为 ( )A.(rear-front-1)n B.(rear-front)nC.(front-rear+1)nD.(rear-front+n)n

17、43. 若用一个大小为6 的一维数组来实现循环队列，且当前rear 和 front 的值分别为 0 和 3。当从队里中删除一个元素，再加入两个元素后，rear 和 front的值分别是(44.45.A. 1 和 5 B. 5 和 1两个字符串相等的条件是(A. 串的长度相等C. 都是非空串如下陈述中正确的是B.C. 2和4D. 4 和 2D.含有相同的字符集串的长度相等且对应的字符相同A.串是一种特殊的线性表B. 串的长度必须大于零C. 串中元素只能是字母D 空串就是空格串46.一棵含 18 个结点的二叉树的高度至少为A. 3 B. 4C. 5D. 647. 将一棵有 40 个结点的完全二叉树

18、从上到下， 从左到右依次对结点进行编号， 根结点 的编号为 1， 则编号为 15 的结点的左孩子的编号为。A. 16B. 30 C. 31D.3248. 在程序的执行过程中，对实现函数的递归调用应该借助于 结构。49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.A. 线性表 B. 栈 C . 队列 D. 树 具有 100 个结点的完全二叉树的深度为 。A.6B. 7 C. 8 D. 9已知二叉树的先序遍历序列为 ABDEC，F 中序遍历序列为DBEAFC则后序遍历序列为ADEBAFCBDEFBCAC DEBCFADDEBFCA如果在数据结构中每个数

19、据元素只可能有一个直接前驱，但可以有多个直接后继， 则该结构是 ( )A. 栈B. 队列C. 树 D. 图已知一棵含 50 个结点的二叉树中只有一个叶子结点，则该树中度为 1 的结点个数为 ()A. 0 B. 1 C. 48D. 49具有 100 个结点的完全二叉树，其中含有个度为 1 的结点。A.1B. 0 C. 2 D.不确定已知二叉树的先序遍历序列为ABCD中序遍历序列为BCD A则后序遍历序列为AABCDBBCDACCDBADDCBA对一棵有 100 个结点的完全二叉树按层序编号，则编号为A.99B.98C.97D.5049 的结点，它的左孩子的编号为(有m个叶子结点的哈夫曼树，其结点

20、总数是()A.2m-1 B.2mC.2m+1D.2(m+1)无向图的邻接矩阵是一个A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵广义表中元素分为 ()A.原子元素 B 表元素C 原子元素和表元素D 任意元素广义表 A=( ) ， (a) ， (b， (c ， d) 的长度为 () .A. 2B. 3C.4 D . 5广义表A：( )， (a)， (b ， (c ， d)的深度为 ()A. 2B. 3C 4 D 5若用邻接矩阵表示一个有向图，则其中每一列包含的1 的个数为(A图中每个顶点的入度C. 图中弧的条数D邻接矩阵为对称矩阵的图是 ()A. 有向图 B. 带权有向图B. 图中每个顶点的出

21、度图中连通分量的数目C. 有向图或无向图 D. 无向图在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要的边数为 ()A. n/2B. nC. n-1 D. n+1面的序列中 是大根堆。C.9,8,7,6,4,8,2,1D. 9,8,7,6,5,4,3,165. 一组记录的关键码为 (46 ，79，56，38，40，84) ，则利用快速排序方法，以第一个记录为基准得到的一次划分结果为A.38 ，40，46，56，79，84B.40 ， 38， 46， 79， 56， 84C.40，38，46，56，79，84D.40， 38，46， 84，56， 7966. 对关键字序列5，1，4，3，

22、7，2，8，6)进行快速排序时，以第一个元素 5 为基准的一次划分的结果为(A(1，2，3，4，5，6，7，8)B1，4，3，2，5，7，8，6)C(2，1，4，3，5，7， 8，6)D8，7，6，5，4，3，2，1)67. 使用折半查找，线性表必须A .以顺序方式存储B .以顺序方式存储，且元素已按值排好序C .以链式方式存储D .以链式方式存储,且元素已按值排好序68. 已知 8 个元素( 34， 76 ，45， 18， 26， 54， 92，65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为(A.4B.5C.6D.769. 若有序表的关键字序列为(b,c,d,e,f,g,q

23、,r,s,t)，则在折半查找关键字 b 的过程中，先后进行比较的关键字依次为(A f,c,bB f,d,b g,c,bD g,d,b70. 在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于 ()B. 动态查找表A. 静态查找表C.静态查找表与动态查找表D. 静态查找表或动态查找表71. 有一个有序表为： (2,5,8,11,15,16,22,24,27,35,50) 当折半查找值为 24 的结点时，经过次比较后查找成功。A. 1 B. 2 C. 3D. 472. 有一个有序表为： (21,32,41,45,62,75,77,82,95), 当折半

24、查找值为 82 的结点时，经过 次比较后查找成功。A. 1 B. 2 C. 4D. 373. 下面排序算法的时间复杂度最小的是 。A.直接插入排序B.简单选择排序C .冒泡排序D.快速排序74. 以下排序方法中，稳定的排序方法是 。A. 直接插入排序和冒泡排序 B. 简单选择排序和归并排序C. 冒泡排序和快速排序 D. 堆排序和基数排序 按排序过程中依据的原则分类，快速排序属于 （ ）A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法在一棵二叉排序树中，若左子树不空，左子树上所有结点的值均（A.大于B 小于 C 不小于 D大于等于）根结点的值。用邻接表表示图进行深

25、度优先遍历时，通常是采用（A.栈B. 队列C.树）来实现算法的。D.图用邻接表表示图进行广度优先遍历时，通常是采用（A.栈B.队列C.树）来实现算法的。D.图从一个顺序队列删除元素时，首先要（）。A.前移一位队首指针B. 后移一位队首指针C. 取出队首指针所指位置上的元素D. 取出队尾指针所指位置上的元素在一个具有 n 个顶点的无向图中，要连通所有顶点则至少需要（）条边。A. n B . 2n C. n-1 D . n+1在有向图的邻接表存储表示中，顶点V在链表结点中出现的次数是（）。A.顶点V的入度B. 顶点V的出度C.顶点V的度D.依附于顶点 V的边的数目由权值分别为 3,6,7,2,5的

26、叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。75.76.75.76.77.78.79.80.81.82.83.84.85.86.A. 74 B . 23C . 51 D . 53,s2= it，则子串定位函数index的值为（）。17D . 18）个结点。. 31D. 63每层上从左到右依次对结点编号， 根结点的编号）。D.无法确定）遍历的结果序列相同。D. 层次遍历设串 sl= Data Structures withA. 15 B . 16 C一棵深度为 6 的二叉树至多有（A. 64B. 32C.将含 100 个结点的完全二叉树从根这一层开始， 为 1，编号为 49 的结点 X 的双亲编号为（A. 24B. 25C. 23树的后根遍历与其转换的相应二叉树的（A. 先序B. 中序C. 后序链表适用于（）查找A.顺序 B.二分法C .顺序，也能二分法 D .随机折半查找有序 表6,15,30,37,65,70,72,89,9