数据结构复习题及答案.doc

数据结构习题一、名词解释1.数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度 。2.线性表、顺序表、单链表 、双向链表 、循环链表 、双向循环链表 、三个概念的区别：头指针、头结点、首元结点(第1个元素结点)。3.栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。4.树、叶子结点、结点的度、树的度、树的高(深)度、二叉树、遍历、满二叉树、完全二叉树 、哈夫曼树、WPL、哈夫曼编码。5.图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、（最小）生成树、邻接矩阵、邻接表、DFS、BFS。6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。7、排序、内（外）排序、稳定性、插入（直接、希尔）， 交换（起泡、快速），选择（直接、堆），2路归并。一、 填空题1. 数据结构是研究数据的_逻辑结构_和_物理结构_，并在这种结构上定义相关的运算，设计实现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为_时间复杂度_和_空间复杂度_。学号2. 数据的基本单位是_数据元素_ ，数据的最小单位是_数据项_ 。3. 算法是对特定问题求解_步骤_的一种描述，是指令的有限序列。4. 一个算法的时间复杂度为(3n3+2n7)，其数量级表示为 O（n3） _。5. 一个算法具有5个特性： 确定性 、 可行性 、 有穷性 、输入和输出。6. 算法性能的分析和度量，可以从算法的 时间复杂度 和 空间复杂度 来评价算法的优劣。学号7. 数据的逻辑结构包括集合结构、 线性结构 、 树形结构 和 图型结构 四种类型。8. 数据结构在计算机中的表示称为数据的 物理结构 ，它可以采用_顺序存储_或_链式存储_两种存储方法。9. 线性表有两种存储结构，分别为 顺序存储 和 链式存储 。10. 链式存储的特点是利用 指针 来表示数据元素之间的逻辑关系。姓名11. 若频繁地对线性表进行插入和删除操作，该线性表宜采用_链式存储_存储结构。12. 线性表中的数据元素之间具有 一对一 的线性关系，除第一个和最后一个元素外，其他数据元素有且只有 一个 直接后继和直接前趋。13. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s-next=_p-next_和p-next=_s_的操作。14. 在一个单链表中删除p的后继结点q时，应执行以下操作p-next= q-next 。15. 对带头结点head的单链表，则判断其为空的条件为 head-next=NULL 。16. 对带头结点head的循环单链表尾结点(由p所指向)判非空的条件为 p-next=head 。17. 在栈结构中，允许插入的一端称为 栈顶 ；在队列结构中，允许插入的一端称为 队尾 。18. 队列中元素的入队和出队应遵循_先进先出 _原则，数据元素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个元素（1in），需向前移动 n-i 个元素。22. 在一个长度为n的顺序表中第i个元素前（1in），插入一个元素，需向后移动 n-i+1 个元素。23. 在顺序存储的线性表中插入或删除一个元素平均约移动表中_50%_（或一半）_的元素。24. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。25. 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。26. 一个广义表为(a,(a,b),d,e,(i,j),k)，则该广义表的长度为_5_，深度为_3_。27. 已知广义表A=(a,b,c),(d,e,f)，则运算tail (head (tail(A)=(e,f)_。28. 已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是_head(head(tail(LS)_。29. 广义表(a,b),c,d)的表头是 (a,b) 表尾是 (c,d) 。30. 广义表(a,b,c,d)的表头是 a 表尾是 (b,c,d)_。31. 两个串相等的充分必要条件是:_ 串长相等_ 且 _对应的字符相等_。32. 不含任何字符的串称为 空串 其长度为 0 。33. 对于稀疏矩阵的压缩存储，通常用一个三元组表示非零元素的信息，其中包括非零元素所在的 行 、 列 以及它的值。34. 若二叉树中有20个叶子结点，则该二叉树有 19 个度为2的结点。35. 若二叉树中度为2的结点有15个，则该二叉树有_16_个叶子结点。36. 深度为h且有_2h-1_个结点的二叉树称为满二叉树。37. 深度为k的二叉树最多有 _2k-1 个结点，最少有 k 个结点，第i 层上最多有_2(i-1)_个结点。38. 深度为5的满二叉树共有 31 个结点，其中有_16_个叶子节点。39. 若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有 34 个结点。40. 深度为15的满二叉树上，第11层有 _2(11-1)=1024 个结点。41. 一棵具有100个结点的完全二叉树，它的深度为 7 ，其中度为1的结点有 1 个。42. 某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为 dab 。43. 哈夫曼树是指对于一组带有确定权值的叶子结点构造的具有最小带权路径长度 的二叉树。44. 具有m个叶子结点的哈夫曼树共有 2m-1 个结点。45. 已知一棵哈夫曼树含有60个叶子结点，则该树中共有 59 个非叶子结点。46. 在一个具有n个顶点无向完全图中，含有 n(n-1)/2 边；在一个具有n个顶点有向完全图中，含有 n(n-1) 边。一个具有4个顶点的无向完全图有 6 条边。47. 具有n个顶点的连通图至少需有 n-1 条边。48. 一个连通图的生成树是该图的 极小 连通子图。若这个连通图有n个顶点，则它的生成树有 n-1 条边。49. 在有向图的邻接矩阵中，第i行中非零元素的个数正好是第i个顶点的 出度 ；第i列中非零元素的个数正好是第i个顶点的 入度 。50. 在一个图中，所有顶点的度数之和等于所有边数的 2 倍。51. 在无向图G的邻接矩阵A中，若Aij等于1，则Aji等于 1 。52. 对二叉排序树进行 中序 遍历，可以得到按关键字从小到大排列的结点序列。53. 一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当折半查找值为82的结点时，经过 4 次比较后查找成功。54. 在线性表中采用折半查找法查找一个数据元素，线性表中元素应该按值有序，并且采用_顺序存储_存储方法。55. 在简单选择排序、堆排序、快速排列、归并排序四种排序方法中，排序方法稳定的是_归并排序。56. 冒泡排序是一种稳定的排序方法，对n个元素的序列进行冒泡排序时，最多需进行 n-1 趟。该排序方法的时间复杂度为 O(n2) 。57. 给定序列100，86，48，73，35，39，42，57，66，21，按堆的定义，则它一定 大根 堆。58. 数据结构是指数据及其相互之间的_一种或多种关系_。当结点之间存在M对N（M：N）的联系时，称这种结构为_图状结构_。59. 队列的插入操作是在队列的_队尾_进行，删除操作是在队列的_队头_进行。60. 每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做_直接插入_排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做_简单选择(或直接选择)_排序。61. 二叉树的前序遍历序列为A，B，C，E，F，D，G，H，中序遍历序列为A，E，C，F，B，G，H，其后序遍历序列为_ E,F,C,G,H,D,B,A_。62. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(0in-1），则它的左孩子结点的编号为 2i ，右孩子结点的编号为 2i+1 ，双亲结点的编号为 i/2 。 63. 在一个具有6个顶点的无向完全图中，包含有 15 条边，在一个具有6个顶点的有向完全图中，包含有 30 条弧。64. 快速排序在平均情况下的时间复杂度为_O(nlog2n)_，在最坏情况下的时间复杂度为_ O(n2)_。65. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明_查找成功_，若元素的值小于根结点的值，则继续向_左子树_查找，若元素的大于根结点的值，则继续向_右子树_查找。66. 在循环单链表中，最后一个结点的指针域指向_首_结点。67. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J），则树中所含的结点数为_9_个，树的深度为_3_，树的度为_3_。68. 通常从四个方面评价算法的质量：_正确性_、_可读性_、_健壮性_和_效率与低存储量需求_。69. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为_499_。70. 一个算法的时间复杂度为(3n3+2n7)(5n)，其数量级表示为 O(n2) 。71. 在快速排序、堆排序和归并排序中，最坏时间复杂度为O(n2)的排序算法有_快速排序_。72. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。 73. 在归并排序中，进行每趟归并的时间复杂度为_O(n)_，整个排序过程的时间复杂度为_O(nlog2n)_，空间复杂度为_ O(n)_。74. 若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为_9_。 75. 对用邻接矩阵表示的具有n个定点和e条边的图进行任一种遍历时，其时间复杂度为 O(n2) ，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_ O(n+e) _。76. 从有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素时，其查找长度分别为_1_和_3_。77. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_2n_个，其中_ n-1_个用于指向孩子， n+1_个指针是空闲的。78. 从逻辑结构看，线性表是典型的_线性结构_，树是典型的_非线性结构_。79. 设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_p-lchild=NULL & p-rchild=NULL 。80. 栈是一种_先进后出_表。队列又称为_先进先出_表。81. 若对序列(49，38，65，97，76，13，27，50)采用直接选择排序法排序，则第三趟结束后序列的状态是_(13,27,38),97,76,49,65,50_。82. 利用关键码分别为10，20，30，40的四个结点，能构造出_14_种不同的二叉排序树.83. 设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行（按递增排序），_冒泡排序_最省时间， _快速排序_最费时间。84. 空串的长度是_0_；空格串的长度是_空格的个数_。串中所含字符个数称为该串的_长度_.85. 在n个结点的单链表中，在P指向的结点之后插入一个结点的时间复杂度为_ O(n)_。86. 设SQ为循环队列，存储在数组dm中，则SQ出队操作对其队头指针front的修改是_ front=（front+1）% m_。87. 树的度是指_树内各结点的度_的最大值。88. 已知链栈的结点结构为栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为_ _p-next=top_和_top=p_。89. 堆排序的空间复杂度_ O(1)_。90. 深度为n(n0)的二叉树最多有_2n-1_个结点。91. 设关键字序列为(Kl，K2，Kn)，则用筛选法建初始堆必须从第_ n/2_个元素开始进行筛选。92. 图有_邻接矩阵_ 、_邻接表_等存储结构，遍历图有 _深度优先搜索_ 、 _广度优先搜索_等方法。93. 在一个有向图的邻接表中，一个顶点的链表中结点的个数等于这个顶点的_出度_ ，在逆邻接表中，一个顶点的链表中结点的个数等于这个顶点的_入度_ 。94. 对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是_1，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）进行冒泡排序时，整个冒泡排序过程中需进行_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)，则用筛选法建成的初始堆为_（80，70，56，65，24，33，48）或_(24，65，33，80，70，56，48)。二、单选题1. 在数据结构中，数据的基本单位是( )A. 数据项 B. 数据元素C. 数据对象 D. 数据文件2. 数据结构是（）A一种数据类型 B数据的存储结构C一组性质相同的数据元素的集合D相互之间存在一种或多种特定关系的数据元素的集合3. 在数据结构的讨论中把数据结构从逻辑上分为（ ）. A.内部结构与外部结构 B.静态结构与动态结构 C.线性结构与非线性结构D. 紧凑结构与非紧凑结构。4. 算法指的是（ ）。A计算机程序 B解决问题的计算方法 C排序算法 D解决问题的有限运算序列5. 算法分析的目的是（）A辨别数据结构的合理性 B评价算法的效率C研究算法中输入与输出的关系 D鉴别算法的可读性6. 某程序的时间复杂度为（3n+nlog2n+n2+8）, 其数量级表示为（ ）。AO（n） BO（nlog2n） CO（n2） DO（log2n）7. for（i=0；in；i+） for（j=0；jnext=NULLC. head!=NULL D. head-next=head16. 已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）A.5，4，3，2，1，6 B.2，3，5，6，1，4C.3，2，5，4，1，6 D.1，4，6，5，2，317. 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A单链表 B.双链表 C.单向循环 D.顺序表18. 对一个算法的评价，不包括如下（ ）方面的内容。 A健壮性和可读性 B并行性 C正确性 D时空复杂度19. 队列的删除操作是在（ ）进行。A队首 B队尾 C队前 D对后20. 计算机识别、存储和加工处理的对象被统称为( )A.数据 B.数据元素C.数据结构 D.数据类型21. 串是任意有限个（ ）符号构成的序列 符号构成的集合字符构成的序列 字符构成的集合22. 如果以链表作为栈的存储结构，则退栈操作时（ ）必须判别栈是否满 对栈不作任何判别必须判别栈是否空 判别栈元素的类型23. 二分查找要求被查找的表是（ ）键值有序的链接表 链接表但键值不一定有序 键值有序的顺序表 顺序表但键值不一定有序24. 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）n2 nlog2n log2n n-125. 堆是一个键值序列k1,k2, kn,对i=1,2,|_n/2_|,满足( )kik2ik2i+1 kik2i+1next= =NULLC.head!=NULL D.headnext= =head34. 在单链表中，指针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. dceab B. decba C. edcba D. abcde36. 若进栈序列为a，b，c，进栈过程中允许出栈，则以下_是不可能得到的出栈序列。A. a,b,c B. b,a,c C. c,a,b D. c,b,a37. 若进栈序列为，进栈过程中允许出栈，则可能的出栈序列是_。A. ， B. ， C. ， D. ，38. 设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( )A.DCBA B.CDAB C.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.rear41. 设数组Datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ）.A.front=front+1 B.front=(front+1)% m C.rear=(rear+1)%m D.front=(front+1)%(m+1)42. 假设以数组An存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( )A.(rear-front-1)n B.(rear-front)nC.(front-rear+1)n D.(rear-front+n)n43. 若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队里中删除一个元素，再加入两个元素后，rear和front的值分别是（）A. 1和5 B. 5和1 C. 2和4 D. 4和244. 两个字符串相等的条件是（ ）A. 串的长度相等 B. 含有相同的字符集C. 都是非空串 D. 串的长度相等且对应的字符相同45. 如下陈述中正确的是_。A串是一种特殊的线性表 B串的长度必须大于零C串中元素只能是字母 D空串就是空格串46. 一棵含18个结点的二叉树的高度至少为_。A. 3 B. 4 C. 5 D. 647. 将一棵有40个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为_。 A. 16 B. 30 C. 31 D.3248. 在程序的执行过程中，对实现函数的递归调用应该借助于_结构。A. 线性表 B. 栈 C . 队列 D. 树49. 具有100个结点的完全二叉树的深度为_。A.6 B. 7 C. 8 D. 950. 已知二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则后序遍历序列为_。ADEBAFCBDEFBCA CDEBCFA DDEBFCA51. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是( )A. 栈 B. 队列 C. 树 D. 图52. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）A. 0 B. 1 C. 48D. 4953. 具有100个结点的完全二叉树，其中含有_个度为1的结点。A.1 B. 0 C. 2 D. 不确定54. 已知二叉树的先序遍历序列为ABCD，中序遍历序列为BCDA，则后序遍历序列为_。AABCD BBCDA CCDBA DDCBA55. 对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（ ）A.99 B.98 C.97 D.5056. 有m个叶子结点的哈夫曼树，其结点总数是（ ）A.2m-1 B.2m C.2m+1 D.2(m+1)57. 无向图的邻接矩阵是一个_。A.对称矩阵 B.零矩阵C.上三角矩阵 D.对角矩阵58. 广义表中元素分为( )A原子元素 B表元素 C原子元素和表元素 D任意元素59. 广义表A=( )，(a)，(b，(c，d)的长度为( ) .A2 B3 C4 D560. 广义表A：( )，(a)，(b，(c，d)的深度为( ) .A2 B3 C4 D561. 若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（）A图中每个顶点的入度B图中每个顶点的出度C图中弧的条数 D图中连通分量的数目62. 邻接矩阵为对称矩阵的图是( )A. 有向图 B. 带权有向图 C. 有向图或无向图 D. 无向图63. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为( )A. n/2 B. n C. n-1 D. n+164. 下面的序列中_是大根堆。A.1,2,8,5,3,9,10,4 B.1,5,10,6,7,8,9,2C.9,8,7,6,4,8,2,1 D.9,8,7,6,5,4,3,165. 一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序方法，以第一个记录为基准得到的一次划分结果为_。A.38，40，46，56，79，84 B.40，38，46，79，56，84C.40，38，46，56，79，84 D.40，38，46，84，56，7966. 对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为（）A（1，2，3，4，5，6，7，8） B（1，4，3，2，5，7，8，6）C（2，1，4，3，5，7，8，6） D（8，7，6，5，4，3，2，1）67. 使用折半查找，线性表必须_。.以顺序方式存储.以顺序方式存储，且元素已按值排好序.以链式方式存储.以链式方式存储，且元素已按值排好序68. 已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ ）A.4 B.5 C.6 D.769. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在折半查找关键字b的过程中，先后进行比较的关键字依次为（）Af,c,b Bf,d,b Cg,c,b Dg,d,b70. 在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于( )A.静态查找表B.动态查找表C.静态查找表与动态查找表D.静态查找表或动态查找表71. 有一个有序表为：(2,5,8,11,15,16,22,24,27,35,50)当折半查找值为24的结点时，经过_次比较后查找成功。A. 1 B. 2 C. 3 D. 472. 有一个有序表为：(21,32,41,45,62,75,77,82,95),当折半查找值为82的结点时，经过_次比较后查找成功。A. 1 B. 2 C. 4 D. 373. 下面排序算法的时间复杂度最小的是_。A直接插入排序 B简单选择排序 C冒泡排序 D快速排序74. 以下排序方法中，稳定的排序方法是_。A. 直接插入排序和冒泡排序 B. 简单选择排序和归并排序 C. 冒泡排序和快速排序 D. 堆排序和基数排序75. 按排序过程中依据的原则分类，快速排序属于( )A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法 D.归并类的排序方法76. 在一棵二叉排序树中，若左子树不空，左子树上所有结点的值均（ ）根结点的值。A大于 B小于 C不小于 D大于等于75. 用邻接表表示图进行深度优先遍历时，通常是采用（）来实现算法的。A栈 B. 队列 C. 树 D. 图 76. 用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。A栈 B. 队列 C. 树 D. 图 77.从一个顺序队列删除元素时，首先要（）。A前移一位队首指针 B.后移一位队首指针C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素78.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ ）条边。An B2n Cn-1 Dn+1 79.在有向图的邻接表存储表示中，顶点V在链表结点中出现的次数是（ ）。A.顶点V的入度 B.顶点V的出度C.顶点V的度 D.依附于顶点V的边的数目80.由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。A74 B23 C51 D5381.设串sl=Data Structures with ，s2=it，则子串定位函数index的值为（）。A15 B16 C17 D1882.一棵深度为6的二叉树至多有（ ）个结点。A64 B32 C31 D6383. 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1，编号为49的结点X的双亲编号为（ ）。A24 B25 C23 D无法确定84. 树的后根遍历与其转换的相应二叉树的（ ）遍历的结果序列相同。A.先序 B.中序 C.后序 D.层次遍历85. 链表适用于（ ）查找A顺序 B二分法 C顺序，也能二分法 D随机86. 折半查找有序表6,15,30,37,65,70,72,89,99,若要查找元素37，需要依次与表中元素_进行比较。A. 65，15，37 B. 68，30，37 C. 65，15，30 D. 65，15，30，3787下列排序方法中，稳定的排序方法为（）。A.希尔排序 B.堆排序 C.快速排序 D.直接插入排序88当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。Atop+; Btop=0; Ctop-; Dtop=N;89在顺序表中，只要知道_，就可在相同时间内求出任一结点的存储地址。A基地址 B结点大小 C向量大小 D基地址和结点大小90在一棵二叉树中，第4层上的结点数最多为（ ）。A31 B8 C15 D1691线性表的顺序存储结构是一种_的存储结构。A随机存取 B顺序存取 C索引存取D散列存取92.数据结构在计算机内存储器中的表示是指（ ）A.数据结构 B.数据元素之间的关系C.数据的逻辑结构 D.数据的物理存储结构93. 下述几种排序方法中，要求内存最大的是（ ）. 插入排序 .快速排序 . 归并排序 . 选择排序94.若长度为n的线性表采用顺序存储结构，则在表中第i个位置（1=i=n+1）插入一个新元素的算法的时间复杂度为（ ）A.O(0) B.O(1) C.O(n) D.O(n2)95.一个栈的输入序列为ABCDE，则不可能出现的输出序列是（ ）A.ABCDE B.EDCBA C.CABED D.BADCE96. 对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是（）A选择排序B冒泡排序 C快速排序D插入排序97.对二叉树的结点从1开始编号，要求每个结点的编号大于其左孩子（如果有的话）的编号，而小于其右(孩子如果有的话）的编号，则可以采用（ ）次序的遍历实现二叉树的结点编号A.先序 B.中序 C.后序 D.层次遍历98. _是一棵满二叉树。A二叉排序树 B深度为5有31个结点的二叉树C有15个结点的完全二叉树D哈夫曼（Huffman）树99.某二叉树结点的中序序列为BDAECF,后序序列为DBEFCA,则该二叉树对应的森林包括（ ）棵树A.1 B.2 C.3 D.4100. 下面关于图的存储的叙述中正确的是（ ）A.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关B.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关C.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关D.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关三、判断题：（对的打P，错的打O）（ O ） 1.数据元素是数据处理的最小单位。（ P ） 2.数据项是数据处理的最小单位。（ O ） 3.线性表的顺序存储结构优于链式存储结构。（ P ） 4.顺序存储的线性表可以随机访问,链式存储的线性表只能顺序访问。（ O ） 5.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上不一定相邻。（ O ） 6.线性表的顺序存储和链式存储都必须占用内存中的连续存储单元。（ P ） 7.栈和队列的存储方式,既可以顺序存储也可以链式存储。（ P ） 8.栈和队列都是操作受限制的线性表。（ P ） 9.栈的特点是先进后出,队列的特点是先进先出。（ P ） 10.空串是任意串的子串。（ O ） 11.串中任意个字符组成的子序列称为该串的子串。（ O ） 12.树型结构中每个结点都有一个直接前趋。（ O ） 13.二叉树中每个结点的度最大为2,因此二叉树是一种特殊的树。（ O ） 14.满二叉树中存在度为1的结点。（ O ） 15.完全二叉树中每个结点或者没有孩子或者有2个孩子。（ P ） 16.在任意一棵二叉树中,叶子结点的个数等于度为2结点的个数加1。（ P ） 17.由树转化为二叉树,其根结点的右子树总是空的。（ O ） 18.最小生成树是指边数最少的生成树。（ P ） 19. 一棵哈夫曼树有m 个叶子结点,则其结点总数为2m-1。（ O ） 20.树的先根遍历序列等同于该树对应的二叉树中序遍历序列。（ O ） 21. “顺序查找法”是指在顺序表上进行查找的方法。（ O ） 22.快速排序在任何情况下圴可得到最块的排序效果。（ P ） 23.在有向图中每个顶点的度等于各顶点的入度与出度之和。（ O ） 24.二叉排序树是用来进行排序的。（ P ） 25.衡量排序算法的两个主要性能指标是执行排序算法所需要的时间和执行排序算法所需要的附加空间。（ P ） 26.哈夫曼树是带权值的树,且权值较大的结点离树较近。1双链表中至多只有一个结点的后继指针为空。（P ）2在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（O ）3对链表进行插入和删除操作时，不必移动结点。（P ）4栈可以作为实现程序设计语言过程调用时的一种数据结构。（P ）5线性表的逻辑顺序与物理顺序总是一致的。（ O）6对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。(O )7边数很多的稠密图，适宜用邻接矩阵表示。（P ）8向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（ P ）9键值序列A，C，D，E，F，E，F是一个堆。（P ）10二路归并时，被归并的两个子序列中的关键字个数一定要相等。（O）11. 非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。(O ) 12. 每种数据结构都应具备三种基本运算：插入、删除和搜索。（O） 13. 当从一