数据结构章节练习题.docx

第1章 绪论一、选择题1. 算法的计算量的大小称为计算的（ ）。 A效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（ ） A问题的规模 B. 待处理数据的初态 C. A和B3一个算法应该是（ ）。 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C. 4从逻辑上可以把数据结构分为（ C ）两大类。 A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构二、判断题 1-5：FFFFT 6-10：FFTFT1. 数据元素是数据的最小单位。( ) 数据元素2. 记录是数据处理的最小单位。 ( ) 结构体类型3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( ) 4算法的优劣与算法描述语言无关，但与所用计算机有关。( ) 5健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( ) 6算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( ) 7程序一定是算法。( ) 8数据的物理结构是指数据在计算机内的实际存储形式。( )9. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。( ) 10. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 三、填空1数据的物理结构包括的表示和的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有，四种。3数据的逻辑结构是指。 4一个数据结构在计算机中称为存储结构。 5. 数据结构是研讨数据的和，以及它们之间的相互关系，并对与这种结构定义相应的，设计出相应的。 6 一个算法具有5个特性:、，有零个或多个输入、有一个或多个输出。第2章 线性表一 选择题1下述哪一条是顺序存储结构的优点？（ A ） A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示2下面关于线性表的叙述中，错误的是哪一个？（ B ） A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3线性表是具有n个（ C ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 E信息项4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A顺序表 B双链表 C带头结点的双循环链表 D单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表6设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 n n B.单循环链表 C. 带尾指针的单循环链表 1 n D.带头结点的双循环链表 1 17若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A单链表 B双链表 C单循环链表 D带头结点的双循环链表8. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1=i=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 9. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)10对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL 二、判断 1-5：FTTFF6-10：FFFFT1. 链表中的头结点仅起到标识的作用。( ) 2. 顺序存储结构的主要缺点是不利于插入或删除操作。( ) 3线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 4顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 5. 对任何数据结构链式存储结构一定优于顺序存储结构。( ) 6顺序存储方式只能用于存储线性结构。( ) 7. 循环链表不是线性表. ( ) 8. 线性表只能用顺序存储结构实现。( ) 9. 线性表就是顺序存储的表。( ) 10. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( ) 三、填空1当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 顺序存储存储结构。 2线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 （N-1）/2 。 3设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_ ; _; 4在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动_个元素。 5在单链表中设置头结点的作用是操作统一，另外无论链表是否为空，链表指针不变 。6 在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_、_、_、_。 7链接存储的特点是利用_来表示数据元素之间的逻辑关系。 8. 循环单链表的最大优点是：从任一结点出发都可访问到链表中每一个元素。 9. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_ 、。10.在单链表L中，指针p所指结点有后继结点的条件是： 。第3章 栈和队列一 选择题1. 对于栈操作数据的原则是（ ）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序2. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ ）。A. 不确定 B. n-i+1 C.i D. n-i3. 若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的4. 若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3，pN,若pN是n，则pi是( )。 A. i B. n-i C. n-i+1 D. 不确定5. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 6. 设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4，7. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 8. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ ）。A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 49. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 10. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ ）。Afedcba B. bcafed C. dcefbaD.cabdef11. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。AXYZ B. YZX C. ZXY D. ZYX12. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ） A. push,pop,push,pop,push,popB.push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop13. 若一个栈以向量V1.n存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。Atop:=top+1; V top:=x B. V top:=x; top:=top+1 C. top:=top-1; V top:=x D. V top:=x; top:=top-114. 若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是（ ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top215. 栈在（ ）中应用。 A. 递归调用 B. 子程序调用 C. 表达式求值 D. ABC16. 一个递归算法必须包括（ ）。 A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分17. 表达式a*(b+c)-d的后缀表达式是( )。 Aabcd*+- B. abc+*d- C. abc*+d- D. -+*abcd18. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈19. 用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改20. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。A队列 B多维数组 C栈 D. 线性表 21. 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。 A(rear-front+m)%mBrear-front+1 C(front-rear+m)%mD(rear-front)%m22. 循环队列存储在数组A0.m中，则入队时的操作为（ ）。 A. rear=rear+1B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod mD. rear=(rear+1)mod(m+1) 23. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )A. 1和 5 B. 2和4 C. 4和2 D. 5和1 24. 栈和队列的共同点是（ ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点25. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。A 6 B. 4 C. 3 D. 2 二 判断题1. 栈是实现过程和函数等子程序所必需的结构。（ T ） 2两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（ T ） 3. 栈与队列是一种特殊操作的线性表。（ T ） 4. 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1. （ T ） 5. 栈和队列都是限制存取点的线性结构。（ T ） 6. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ F ） 7. 通常使用队列来处理函数或过程的调用。（ F ） 8. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ T ） 9. 循环队列也存在空间溢出问题。（ T ） 10. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ T ） 三 填空题 1栈是_的线性表，其运算遵循_的原则。 2_是限定仅在表尾进行插入或删除操作的线性表。 3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_。4. 多个栈共存时，最好用 链式存储结构作为存储结构。 5. 循环队列的引入，目的是为了克服假溢出时大量移动数据元素。6_又称作先进先出表。 7. 队列的特点是_。 8队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_。 9. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_。 10表达式求值是_应用的一个典型例子。 第五章 树和二叉树一、选择题1算术表达式a+b*（c+d/e）转为后缀表达式后为（ ） Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+2. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）A5 B6 C7 D83. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）Am-n Bm-n-1 Cn+1 D条件不足，无法确定 4若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定 5在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个A4 B5 C6 D7 6设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。 AM1 BM1+M2 CM3 DM2+M37具有10个叶结点的二叉树中有（ ）个度为2的结点， A8 B9 C10 Dll8一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A 250 B 500 C254 D505 E以上答案都不对 9. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A不确定 B2n C2n+1 D2n-110. 有n个叶子的哈夫曼树的结点总数为（ ）。 A不确定 B2n C2n+1 D2n-111若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。*An-1 Bn/m-1 C(n-1)/(m-1) D n/(m-1)-1 E(n+1)/(m+1)-112. 有关二叉树下列说法正确的是（ ） A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为213二叉树的第I层上最多含有结点数为（ ） A2I B 2I-1-1 C 2I-1 D2I -114. 一个具有1025个结点的二叉树的高h为（ ） A11 B10 C11至1025之间 D10至1024之间15一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A2h B2h-1 C2h+1 Dh+1 16对于有n 个结点的二叉树, 其高度为（ ） Anlog2n Blog2n Clog2n|+1 D不确定17. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ） Alogn+1 Blogn+1 Clogn Dlogn-118深度为h的满m叉树的第k层有（ ）个结点。(1=k=h) Amk-1 Bmk-1 Cmh-1 Dmh-119在一棵高度为k的满二叉树中，结点总数为（ ） A2k-1 B2k C2k-1 Dlog2k+123. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）A4 B5 C6 D7 24. 利用二叉链表存储树，则根结点的右指针是（ ）。 A指向最左孩子 B指向最右孩子 C空 D非空25对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 A先序 B. 中序 C. 后序 D. 从根开始按层次遍历26若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。A前序 B中序 C后序 D按层次 27在下列存储形式中，哪一个不是树的存储形式？（ ） A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法28一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ） ACABDEFG BABCDEFG CDACEFBG DADCFEG 29已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。ACBEFDA B FEDCBA C CBEDFA D不定 30已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。 Aacbed Bdecab CdeabcDcedba31二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： A、 E B、 F C、 G D、 H 32将一棵树t 转换为孩子兄弟链表表示的二叉树h，则t的后根序遍历是h 的A前序遍历 B中序遍历 C后序遍历（ ） 33下面的说法中正确的是（ ）.（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；（2）按二叉树定义，具有三个结点的二叉树共有6种。A(1)(2) B(1) C(2) D(1)、(2)都错 34一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）A所有的结点均无左孩子B所有的结点均无右孩子C只有一个叶子结点D是任意一棵二叉树35在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）A都不相同B完全相同 C先序和中序相同，而与后序不同D中序和后序相同，而与先序不同 36某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A空或只有一个结点B任一结点无左子树 C高度等于其结点数D任一结点无右子树37在完全二叉树中，若一个结点是叶结点，则它没（ ）。 A左子结点B右子结点 C左子结点和右子结点 D左子结点，右子结点和兄弟结点38在下列情况中，可称为二叉树的是（ ）A每个结点至多有两棵子树的树 B. 哈夫曼树 C每个结点至多有两棵子树的有序树D. 每个结点只有一棵右子树 E以上答案都不对 39. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( )A不确定 B. 0 C. 1 D. 2 40. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。A. 0 B. 1 C. 2 D. 不确定 41n个结点的线索二叉树上含有的线索数为（ ）A2n Bnl Cnl Dn 42. 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。A n-1 Bn C n+1 D n+2 43由3 个结点可以构造出多少种不同的二叉树？（ ）A2 B3 C4 D5 44下述编码中哪一个不是前缀码（ ）。 A（00，01，10，11）B（0，1，00，11） C（0，10，110，111）D（