《数据结构》各章练习题

1、读书破万卷下笔如有神选择题1.算法的计算量的大小称为计算的（）A.效率 B. 复杂性 C.2.计算机算法指的是（），它必须具备（）（1）A.计算方法 B.排序方法调度方法（2）A .可执行性、可移植性、可扩充性C.确定性、有穷性、稳定性3.从逻辑上可以把数据结构分为（A.动态结构、静态结构BC.线性结构、非线性结构D二、判断题1. 数据元素是数据的最小单位。（）2. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；（）3.算法的优劣与算法描述语言无关，但与所用计算机有关。（）4 .健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（）5.程序一定是算法。（）6 .数据的物理结构是指数据在计算

2、机内的实际存储形式。（）7.数据结构的抽象操作的定义与具体实现有关。（）判断题答案：1.F 2.F 3.F 4.T 5.F 6.T 7.F三、填空1. 对于给定的 n 个元素，可以构造出的逻辑结构有 _ ,_ ,_, 四种。2._ 数据的逻辑结构是指。3._ 一个数据结构在计算机中 称为存储结构。4 .数据结构中评价算法的两个重要指标是和5._ 数据结构是研讨数据的_和,并对与这种结构定义相应的_ _，设 计出相应的_ 。6 . 一个算法具有 5 个特性： _、_ 、_ ，有零个或多个输入、有一个或多个输出。第一章练习选择题答案：1.B 2. （1） C(2) B 3.C现实性 D. 难度 这

3、三个特性。C.解决问题的步骤序列D.B.可执行性、确定性、有穷性D.易读性、稳定性、安全性）两大类。.顺序结构、链式结构.初等结构、构造型结构读书破万卷下笔如有神填空题答案： 1. 集合线性结构树形结构图状结构2. 数据及相互之间的联系3.的存储方式4.时间复杂度 空间复杂度5.逻辑结构 存储结构运算（操作） 算法读书破万卷下笔如有神第二章练习一选择题1 .下述哪一条是顺序存储结构的优点？（）A 存储密度大 B .插入运算方便 C .删除运算方便 D .可方便地用于各 种逻辑结构的存储表示2. 下面关于线性表的叙述中，错误的是哪一个？（）A 线性表采用顺序存储，必须占用一片连续的存储单元。B.

4、 线性表采用顺序存储，便于进行插入和删除操作。C. 线性表采用链接存储，不必占用一片连续的存储单元。D. 线性表采用链接存储，便于插入和删除操作。3. 线性表是具有门个（ ）的有限序列（n0）。A 表元素 B .字符 C .数据元素 D .数据项E .信息项4 .若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B .双链表 C .带头结点的双循环链表 D .单循环链表5 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。A.单链表 B .仅有头指针的单循环链表C .双链

5、表D .仅有尾指针的单循环链表6.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。A.单链表 B.单循环链表 C.带尾指针的单循环链表D.带头结点的双循环链表7. 静态链表中指针表示的是（）.A.内存地址 B .数组下标 C .下一元素地址 孩子地址8. 链表不具有的特点是（）A 插入、删除不需要移动元素 B .可随机访问任一元素C .不必事先估计存储空间 D .所需空间与线性长度成正比9. 下面的叙述不正确的是（A.线性表在链式存储时，查找第B.线性表在链式存储时，查找第C. 线性表在顺序存储时，查找第D. 线性表在顺序存储时，查找第10. （1）静态链表既有顺序存

6、储的优点，又有动态链表的优点。所以，它存取表 中第 i 个元素的时间与 i 无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能 增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是()D .左、右）i 个元素的时间同 i个元素的时间同 i个元素的时间同 i个元素的时间同i 的值成正比i 的值无关i 的值成正比i 的值无关读书破万卷下笔如有神A (1), (2) B . (1) C . (1), (2) ,(3) D.(2)11. 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为()(1=ili

7、nk=headB . p-link=NILC . p=NIL D . p= head15. 在双向链表指针 p 的结点前插入一个指针 q 的结点操作是()A. p-Lli nk=q;q-Rli nk=p;p-Lli nk-Rli nk=q;q-Lli nk=q；B. p-Lli nk=q;p-Lli nk-Rli nk=q;q-Rli nk=p;q-Lli nk=p-Lli nk;C. q-Rli nk=p;q-Lli nk=p-Lli nk;p-Lli nk-Rli nk=q;p-Lli nk=q;D. q-Lli nk=p-Lli nk;q-Rli nk=q;p-Lli nk=q;p-Ll

8、i nk=q;16. 在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是：()。A. p-next=s;s-next=p-next; B. s-next=p-next;p-next=s;C. p-next=s;p-next=s-next; D. p-next=s-next;p-next=s;17. 对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是( )A . head=NULL B . head next=NULL C . head next=head D. head!=NULL选择题答案1.A2.B3.C4.A 5.D6.D7.C8.B9.B,C10.B

9、11.C12.C13.C14.A15.C :16.B17.B二、填空1 .当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快 的速度存取线性表中的元素时，应采用 _储结构。2. 线性表 L= (a1,a2,an )用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 _ 。3._ 设单链表的结点结构为(data,next) ，next 为指针域，已知指针 px 指向单链 表中 data 为 x 的结点，指针 py 指向 data 为 y 的新结点,若将结点 y 插入结点 x 之后，则需要执行以下语句：_; _ ;4 .在一个长度为 n 的顺序表中第

10、 i 个元素(1=inext=px-next; px-next=py4 . n-i+15. 主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一 个结点不必另作判断。另外，不论链表是否为空，链表指针不变。6.0(1)，0(n)7. 单链表，多重链表，(动态)链表，静态链表8. f-next=p-next; f-prior=p; p-next-prior=f; p-next=f;9.pdprior sA.priorA.next10.指针11.物理上相邻指针12. 4213. 从任一结点出发都可访问到链表中每一个元素。14. u=p-next; p-next=u-next; free(

11、u);15. L-next-next=L16. p-next!=null二、判断1. 链表中的头结点仅起到标识的作用。()2.顺序存储结构的主要缺点是不利于插入或删除操作。()3. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()4顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（）5.对任何数据结构链式存储结构一定优于顺序存储结构。（）读书破万卷下笔如有神6 顺序存储方式只能用于存储线性结构。（）7 集合与线性表的区别在于是否按关键字排序。（）8.所谓静态链表就是一直不发生变化的链表。（）9.线性表的特点是每个元素都有一个前驱和一个后继。（）10. 取线性表的第

12、 i 个元素的时间同 i 的大小有关（）11. 循环链表不是线性表.（）12. 线性表只能用顺序存储结构实现。（）13. 线性表就是顺序存储的表。（）14为了很方便的插入和删除数据，可以使用双向链表存放数据。（）15.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）16. 链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在 顺序存储结构中效率咼。（）判断题答案1.X2.V3.V4.X5.X6.X7.X8.X9.X10.X11.X12.X13.X14.V15.X16.V部分答案解释如下。1、头结点并不“仅起”标识作用，并且使操作统一。另外，头结点数据域可写入链表长度，

13、或作监视哨。4 两种存储结构各有优缺点，应根据实际情况选用，不能笼统说哪一个好。 7集合中元素无逻辑关系。9 非空线性表第一个元素无前驱，最后一个元素无后继。13线性表是逻辑结构，可以顺序存储，也可链式存储。第三章练习一选择题1.有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表示该矩阵时，所需的字节数是（）。A. 60B. 66C. 18000D. 332.对稀疏矩阵进行压缩存储目的是（）。A.便于进行矩阵运算 B 便于输入和输出C 节省存储空间D 降低读书破万卷下笔如有神运算的时间复杂度3.广义表（a,b,c,d ）的表头是（），表尾是（）。

14、A. aB.（）C.（a,b,c,d ） D. （b,c,d ）4.广义表(a,(b,c),d,e)的表头为( )。A. a B. a,(b,c) C. (a,(b,c)D.（a）5.设广义表 L= （a,b,c ）,则 L 的长度和深度分别为（）A. 1和 1B. 1和 3C. 1和 2D. 2和 36.F 面说法不正确的是（)表A. 广义表的表头总是个广义表B.广义表的表尾总是一个广义C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构选择题答案1.B2.C3.C4.A5.C6.A、填空1. 所谓稀疏矩阵指的是_。2. 当广义表中的每个元素都是原子时，广义表便成了 _ 。3. 广义

15、表的表尾是指除第一个兀素之外，_。4. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于（1）。为了区分原子和表，一般用表示表，用（3）_ 表示原子。一个表的长度是指，而表的深度是指5. 广义表的_定义为广义表中括弧的重数。填空答案：1. 非零元很少（tm*n）且分布没有规律2. 线性表3. 其余元素组成的表4.（1）原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而 表带结构，本质就是广义表，因作为广义表的元素故称为子表。（2）大写字母（3）小写字母（4）表中元素的个数（5）表展开后所含括号 的层数5. 深度二、判断1. 稀疏矩阵压缩存储后，必会失去随机存

16、取功能。（）2. 一个稀疏矩阵 Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把 m 和 n 的值互换，则就完成了 Am*n的转置运算。（）3. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（）读书破万卷下笔如有神4. 若一个广义表的表头为空表，则此广义表亦为空表。（）5. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（ ）6.所谓取广义表的表尾就是返回广义表中最后一个元素。（）7.广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（）8.对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（）9.一个广义表可以

17、为其它广义表所共享。（）判断题答案1.V 12.x3.x4.x5.x6.x7.V8.V J9.V部分答案解释如下。6. 错误。稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转 置后在新三元组中的位置。8.错误。广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的 表，不可能是原子。9.错误。广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头10. 错误。广义表中元素可以是原子，也可以是表（包括空表和非空表） 。11. 错误。广义表的表尾，指去掉表头元素后，剩余元素所组成的表。第四章练习一、填空1 栈是_ 的线性表，其运算遵循 _ 的原则。2._限定仅在表尾进行插入

18、或删除操作的线性表。3.一个栈的输入序列是：1，2，3 则不可能的栈输出序列是 _ 。4用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为1234，为了得到1342 出栈顺序，相应的 S 和 X 的操作串为_。5. 顺序栈用 datan存储数据，栈顶指针是 top,则值为 x 的元素入栈的操作是。6 .表达式 23+（12*3-2）/4+34*5/7）+108/9_ 的后缀表达式是。7.循环队列的引入，目的是为了克服 _ 。8._称作先进先出表。9.队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_ 。10. 设循环队列用数组 AM表示，队首、队尾指针分别是 FR

19、ON 和 TAIL，判定队满的条件为_ 。11._表达式求值是用的一个典型例子。12. 循环队列用数组 Am存放其元素值，已知其头尾指针分别是 front 和 rear ，则当前队列的元素个数是_ 。读书破万卷下笔如有神填空题答案：1、操作受限（或限定仅在表尾进行插入和删除操作）后进先出2、栈3、读书破万卷下笔如有神3124、 SxSSxSXX5、data+top=x;6、23.12.3*2-4/34.5*7/+108.9/+(注：表达式中的点(.)表示将数隔开，如23.12.3 是三个数)10、（TAIL+1） MOD M=FRONT、栈 13二、判断1. 栈是实现过程和函数等子程序所必需的

20、结构。2. 栈与队列是一种特殊操作的线性表。（）3. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出 型结构。（4. 通常使用队列来处理函数或过程的调用。（）5. 循环队列也存在空间溢出问题。（6. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（）判断题答案：1.V，2.V，3.X4.X5.V，6.V第五、六章练习选择题1. 设树 T 的度为 4,其中度为 1, 2, 3 和 4 的结点个数分别为 4, 2，1，1 则T 中的叶子数为（）（提示：结点总数=度总数+1）A. 5 B . 6 C . 7 D . 82. 在下述结论中，正确的是（）只有一个结点的二叉树

21、的度为 0;二叉树的度为 2;二叉树的左右子树可任意交换；深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。A. B . C . D .3. 设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 p,p 的右子树结点个数为 n,森林 F 中第一棵树的结点个数是（）A. m-n B . m-n-1 C . n+1 D .条件不足，无法确定4 .若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点 个数是（）A. 9 B . 11 C . 15 D .不确定5.设森林 F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2 和M3 与

22、森林 F 对应的二叉树根结点的右子树上的结点个数是（）。A. M1 B . M1+M2 C . M3 D . M2+M36. 棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（）A. 250 B . 501 C . 254 D . 5057、假溢出时大量移动数据元素。 8、队列 9、先进先出、(rear-front+m ) % m( )读书破万卷下笔如有神7. 设给定权值总数有 n 个，其哈夫曼树的结点总数为（）A.不确定 B . 2n C . 2n+1D . 2n-18. 有 n 个叶子的哈夫曼树的结点总数为（）。A.不确定 B . 2n C . 2n+1 D . 2n-1读书破万卷

23、下笔如有神9. 有关二叉树下列说法正确的是（）A.二叉树的度为 2B.一棵二叉树的度可以小于 2C.二叉树中至少有一个结点的度为 2 D .二叉树中任何一个结点的度都为210.二叉树的第 I 层上最多含有结点数为（）A. 21B . 21-1-1 C . 21-1D . 21-111. 一个具有 1025 个结点的二叉树的高 h 为（ ）A. 11 B . 10 C . 11 至 1025 之间 D . 10 至 1024 之 间12 .一棵二叉树高度为 h,所有结点的度或为 0,或为 2,则这棵二叉树最少有（）结点A. 2h B . 2h-1 C . 2h+1 D . h+113 .对于有

24、n 个结点的二叉树，其高度为（）A. nlog2n B . log2nC .og2n |+1 D .不确定14. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（）A.og2n +1 B . log2n+1C .og2n D . log2n-115 .深度为 h 的满 m 叉树的第 k 层有（）个结点。（1=k=1)11. 完全二叉树的存储结构通常采用顺序存储结构。12. 度为二的树就是二叉树。13. 霍夫曼树的结点个数不能是偶数。14. 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。15. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。、判断题答案1.X2.X

25、3.X4.V5.X6.X7.V8.V9.X10.X11.V ：12.X13. V：14.X15.V三、填空题1.二叉树由(1)，三个基本单元组成。2 .中缀式 a+b*3+4* (c-d )对应的前缀式为 _(1)_，若 a=1，b=2，c=3，d=4， 则后缀式db/cc*a-b*+的运算结果为。3.具有 256 个结点的完全二叉树的深度为 _ 。4 .已知一棵度为 3 的树有 2 个度为 1 的结点，3 个度为 2 的结点，4 个度为 3的结点，则该树有_叶子结点。5 .深度为 k 的完全二叉树至少有_(1)_个结点，至多有丄 2)_个结点。6._ 假设根结点的层数为1,具有n个结点的二叉

26、树的最大高度是 _ 。7.在一棵二叉树中，度为零的结点的个数为 N0,度为 2 的结点的个数为 N2,则有N0 =_读书破万卷下笔如有神8 .高度为 8 的完全二叉树至少有 _ 叶子结点。9 .已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少是读书破万卷下笔如有神10完全二叉树中，结点个数为 n,则编号最大的分支结点的编号为 _。11 具有 N 个结点的二叉树，采用二叉链表存储，共有_个空链域。12._哈夫曼树是 。13若以4 , 5, 6, 7, 8作为叶子结点的权值构造哈夫曼树，贝 U 其带权路径长 度是_ 。14.有一份电文中共使用 6 个字符：a,b,c,d,e,f, 它们的出

27、现频率依次为 2,3,4,7,8,9 ，试构造一棵哈夫曼树，则其加权路径长度WPL 为_(1)_，字符 c的编码是_J2)_。15.设 n为哈夫曼树的叶子结点数目，则该哈夫曼树共有个结点。三. 填空题答案1. (1)根结点 左子树 右子树2. (1) +a*b3*4-cd (2)183. 94. 125. (1)2k-1(2)2k-16. n7. N2+18. 649. 9910.Hn/211. N+112. 带权路径长度最小的二叉树，又称最优二叉树13.6914.(1)80 (2)001 (不唯一)15.2 n(r1第七章练习读书破万卷下笔如有神A. 0B6 .在一个无向图中， 所有顶点的度

28、数之和等于所有边数(A . n-1B. nC.n+1D.nlogn ；3.要连通具有n 个顶点的有向图，至少需要 ( :)条边。A . n-1B.nC.n+lD.2nl )个连通.n-1D. n倍，在一个有2.O一个有 n 个结点的图,最少有()个连通分量，最多有).0 E、选择题设无向图的顶点个数为 n,则该图最多有()条边A. n-1 B . n(n-1)/2 C . n(n+1)/2 一个 n 个顶点的连通无向图，其边的个数至少为(5.分量。读书破万卷下笔如有神向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A. 1/2 B . 2C . 1D. 47无 向 图G=(V,E),V

29、=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d) 进行深度优先遍历，得到的顶点序列正确的是()A . a,b,e,c,d,fB . a,c,f,e,b,dD. a,e,d,f,c,b8.已知有向图 G=(V,E)，其中 V=Vi,V2,V3,V4,V5,V6,V7,E=VVI,V2,VVI,V3,VVI,V4,VV2,V5,VV3,V5,VV3,V6,VV4,V6,VV5,V7,VV6,V7,G 的拓扑序列是（）0A. V1,V3,V4,V6,V2,V5,V7B. V1,V3,V2,V6,V4,V5,V7C. V1,V3,V4,V

30、5,V2,V6,V7D. V1,V2,V5,V3,V4,V6,V79. 一个有向无环图的拓扑排序序列（）是唯一的。A. 一定B .不一定10. 在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是（0。A. G 中有弧B. G 中有一条从 Vi 到 Vj 的路径C. G 中没有弧D. G 中有一条从 Vj 到 Vi 的路径三、填空题1. 判断一个无向图是一棵树的条件是 _o2._有向图 G 的强连通分量是指o3._一个连通图的一个极小连通子图。4._ 具有 10 个顶点的无向图，边的总数最多为 _o5._若用 n 表示图中顶点数目，则有边的无向图成为完全图。6

31、. 在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，贝 U 至少需要条弧。7._ 在有 n个顶点的有向图中，每个顶点的度最大可达 _o8. 设 G 为具有 N 个顶点的无向连通图，贝 U G 中至少有_ 边。9 . N 个顶点的连通图的生成树含有 _ 条边。10 .有 N 个顶点的有向图，至少需要量 _ 弧才能保证是连通的。11 .右图中的强连通分量的个数为（0个12 .在图 G 的邻接表表示中，每个顶点邻接表中所含的结点数， 对于无向图来说 等于该顶点的 _ ；对于有向图来说等于该顶点的 _o13. 在有向图的邻接矩阵表示中，计算第 I 个顶点入度的方法是 _o其 中 ：，对该图C

32、 . a,e,b,c,f,d读书破万卷下笔如有神14. 对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示，则表头向量大小为_，邻接表的边结点个数为_o15.已知一无向图 G= （ V， E ），其中 V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点 a 开始遍历图，得到的序列为 abecd，贝 U 采用的是_遍历方法。16. 一无向图 G( V, E),其中 V( G) =123,4,5,6,7,E(G)=( 1,2 ) ,(1,3 ),(2,4 ), (2,5 ), (3,6 ), (3,7 ), (6,7 ) (5,1

33、 ) ,对该图从顶点 3 开始进行遍历，去掉遍历中未走过的边，得一生成树 G (V ,E),V( G)=V( G),E( G)=( 1,3 ), (3,6 ),(7,3 ), (1,2 ), (1,5 ), (2,4 ) ，则采用的遍历方法是 _ 。17. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_放被访问的结点以实现遍历。18 构造连通网最小生成树的两个典型算法是。19. 有一个用于 n 个顶点连通带权无向图的算法描述如下:(1) .设集合 T1 与 T2,初始均为空；(2) .在连通图上任选一点加入 T1;(3) .以下步骤重复 n-1 次：a. 在 i 属于 T1, j 不属于 T1 的边中选最小权的边；b. 该边加入 T2。上述算法完成后，T2 中共有_边，该算法称 _ 法，T2 中的边构成图的_ 。20 . AOV 网中，结点表示_,边表示_ 。21.当一个 AOV 网用邻接表表示时，可按下列方法进行拓扑排序。(1) .查邻接表中入度为 _的顶点，并进栈；(2)_.若栈不空，则输出栈顶元素 Vj，并退栈；查Vj 的直接后继 Vk,对 Vk 入度处理，处理方法是；(3)_.若栈空时，输出顶点数小于图的顶点数，说明有 _ ，否则拓扑排序 完成。二、判断题1 .在 n 个