数据结构总练习题ppt课件.ppt

《数据结构总练习题ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构总练习题ppt课件.ppt（43页珍藏版）》请在三一办公上搜索。

1、1.1 什么是数据结构,1.2 基本概念和术语,1.4 算法和算法分析,第一章 绪 论,1.3 抽象数据类型的表示与实现,1. 熟悉各名词、术语的含义，掌握基本概念。,2. 理解算法五个要素的确切含义。,本章学习要点,3. 掌握计算语句频度和估算算法时间复杂度的方法。,第1章练习题,1.数据结构是研究数据的( )以及它们之间的相互关系。A. 物理结构，逻辑结构 B. 理想结构，抽象结构C. 理想结构，物理结构 D. 抽象结构，逻辑结构2.从逻辑上可以把数据结构分为（ ）两大类。A.动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构3.在发生非法操作时，

2、算法能够做出适当处理的特性称为（ ）A.正确性 B. 健壮性 C.可读性 D.可移植性4.以下（ ）不是算法的基本特性。 A.可行性 B.长度有限 C.在规定的时间内完成 D.确定性,A,C,B,B,5. 算法的时间复杂度与（ ）有关。A.问题规模 B.计算机硬件性能 C.编译程序质量 D.程序设计语言6.某算法的时间复杂度为O（n2），表明该算法的（ ）。.A.问题规模是n2 B.执行时间等于n2 C.执行时间与n2成正比 D.问题规模与n2成正比7.在下面的程序段中，对x的赋值语句的频度为（ ）。for(k=1;k=n;k+) for(j=1;j=n;j+) x=x+1;A.O(2n) B

3、.O(n) C.O(n2) D.O(log2n),A,C,C,第二章 线性表,2.1 线性表的类型定义,2.2 线性表的顺序表示和实现,2.3 线性表的链式表示和实现,2.4 一元多项式的表示及相加,本章学习要点,1.了解线性表的逻辑结构特性，在计算机中表示这种关系的两类不同的存储结构。,2.熟练掌握两类存储结构的描述方法，以及线性表的各种基本操作的实现。,3.能够从时间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。,1. 在线性表的下列存储结构中，读取指定序号的元素花费时间最少的是（ ）。 A.单链表 B.双链表 C.循环链表 D.顺序表2.在一个具有n个结点的有序单链表中插

4、入一个新结点使得仍然有序，其算法的时间复杂度为（ ）。 A.O(1) B.O(n) C.O(n2) D.O(log2n)3.线性表采用链式存储结构时，其地址（ ）。 A.必须是连续的 B.一定是不连续的 C.部分地址必须是连续的 D.连续与否均可4.带头结点的单链表h为空的判断条件是（ ）。 A. h=NULL B.h-next=h C. h-next=NULL D.h!=NULL,D,B,D,C,第2章练习题,5.对于用一维数据d1n顺序存储的线性表，其算法的时间复杂度为O(1)的操作是 （ ）。 A.将n个元素从小到大排序 B.从线性表中删除第i个元素（1in） C.查找第i个元素（1in

5、） D.向线性表中第i个元素之后插入一个元素（1in）6.在表头指针为head且表长大于1的单向循环链表中，指针p指向表中的某个结点，若p-next-next= =head,则（ ）。 A. p指向头结点 B. *p的直接后继是尾结点 C. p指向尾结点 D. *p的直接后继是头结点,C,B,7.在一个单链表中，删除*p结点之后的一个结点的操作是（ ）。 A.p-next=p B.p-next-next=p-next C.p-next-next=p D.p-next=p-next-next8.以下是结点s（data, next）插入到结点p之后的插入过程，请补充完整。 s=new LNode;

6、 / 生成新结点 if(s= =NULL) return ERROR; s-data=e; （ ）; （ ）;,D,s-next=p-next;p-next=s;,9.设单链表的结点结构为(data,next)，已知单链表的初始状态如下图所示，执行下列程序段后，画出变化后的单链表结构图。T=L;while(T-next!=NULL) if(T-datadata=T-data*2; T=T-next; ,第三章 栈和队列,3.1 栈的类型定义,3.3 栈的应用举例,3.2 栈类型的实现,3.4 队列的类型定义,3.5 队列类型的实现,1.掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们

7、。,2.熟练掌握栈类型的基本操作和实现算法。,3.熟练掌握循环队列的基本操作实现算法。,本章学习要点,4.理解使用栈实现非递归的原理。,1. 栈和队列的共同点是（ ） A.都是先进先出 B.都是先进后出 C.只允许在端点处插入和删除元素 D.没有共同点2.经过以下栈运算后，StackEmpty( s )的值是（ ） InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y); A.a B.b C.1 D.03.4个元素a、b、c和d依次入栈，入栈过程中允许元素出栈，假设某一时刻栈的状态是c（栈顶）、b、a（栈底），则不可能的出栈顺序是（ ）。 A. d

8、,c,b,a B. c,b,d,a C. c,a,d,b D. c,d,b,a 4.向一个栈顶指针为Top的链栈中插入一个p所指结点时，其操作步骤为（ ） A.Top-next=p; B.p-next=Top-next;Top-next=p; C.p-next=Top;Top=p; D.p-next=Top;Top=Top-next;,第3章练习题,C,C,C,C,5. 设有一顺序栈S，元素a，b，c，d，e，f依次进栈，如果6个元素出栈的顺序是b，d，c，f，e，a，则栈的容量至少应该是（ ） A.2 B.3 C.5 D.66.若用一个大小为6的数组来实现循环队列，且当前rear和front

9、的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。 A. 1和5 B. 2和4 C. 4和2 D. 5和17.判定一个循环队列Q（存放元素位置0MaxSize-1）队满的条件是（ ）A.Q.front=Q.rear B. Q.rear=(Q.front+1)%MaxSizeC.Q.front=(Q.rear+1)%MaxSize D.Q.front+1=Q.rear,B,B,C,8. 设循环队列中数组的下标是0N-1，其头尾指针分别为f和r，则其元素个数为（ ） A. r-f B.r-f-1 C.(r-f)%N+1 D.(r-f+N)%N9.设有

10、编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。答案：至少有14种。 全进之后再出情况，只有1种：4,3,2,1 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,3,1,4 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1,2,3,4 1,2,4,3,D,10.以下代码段是最大长度为N的循环队列Q的入队操作，请补充完整。Status EnQueue(SqQueue ,(Q.rea

11、r+1)%N=Q.front;Q.rear=(Q.rear+1)%N;,11.利用算符优先算法对表达式8/(31)求值，写出求值过程中操作数栈（OPND）和算符栈（OPTR）的变化情况。,第四章 串,4.1 串类型的定义,4.2 串的表示和实现,1.熟悉串的基本操作。,2.熟练掌握在不同的存储结构下，串的特点。,本章学习要点,1.串是一种特殊的线性表，其特殊性体现在（ ） A.可以顺序存储 B.数据元素是一个字符 C.可以链式存储 D.数据元素可以是多个字符2.若串S=“software”，其子串数目是（ ） A.8 B.37 C.36 D.9 3.设s= 数据结构A，则StrLength(s

12、)=（ ）。,B,B,9,第五章 数组和广义表,5.1 数组的类型定义,5.2 数组的顺序表示和实现,5.4 广义表的类型定义,本章学习要点,1.掌握二维数组以行为主序和以列为主的存储结构中的地址计算方法。,2.掌握广义表的定义。,1. 数组A05,06的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素a55的地址为（ ） A.1175 B.1180 C.1205 D.12102.空的广义表，是指广义表（ ）A.深度为0 B.尚未赋值 C.不含任何原子 D.不含任何元素3.对于广义表(a,b),(),(a,(b)来说，其（ ） A.长度为4 B.深度为4 C

13、.有3个元素 D.有2个元素4.在广义表(a,b),c,(d),e),(f,j,(g),(h)中，第4个元素的第3个元素是（ ） A.原子g B.子表(g) C.原子e D.子表(d),e),A,D,C,B,5.广义表A=(a,b,(c,d),(e,(f,g)，则下面式子的值是（ ） Headtailheadtailtail(A) A. (g) B. (d) C. (c) D. d6.已知广义表L=(x,y,z),a,(u,t,w)，从L表中取出原子项t的运算是（ ）A. Head(Tail(Tail(L)B. Tail(Head(Head(Tail(L)C. Head(Tail(Head(T

14、ail(L)D. Head(Tail(Head(Tail(Tail(L),D,D,第六章 树和二叉树,6.1 树的类型定义,6.2 二叉树的类型定义和实现,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.5 Huffman树与Huffman编码,本章学习要点,1.熟练掌握二叉树的性质，了解相关性质证明。2.熟悉二叉链表的存储结构的特点。3.掌握各种二叉树遍历策略的递归和非递归算法，灵活运用遍历算法实现其它操作。4.理解线索二叉树以及二叉树的线索化过程。5.熟悉树的存储结构及其基本操作。6.掌握树和森林与二叉树的转换方法。7.了解最优二叉树的特性，掌握建立最优二叉树和Huffman编码的方

15、法。,1.对于一颗具有n个结点，度为4的树来说，（ ） A.树的高度至多是n-3 B.至少在某一层上正好有4个结点C.树的高度至多是n-4 D.第i层上至多有4*(i-1)个结点 2.用双亲存储结构表示树，其优点之一是比较方便（ ）A.找指定结点的双亲结点 B.找指定结点的孩子结点C.找指定结点的兄弟结点 D.判断某结点是不是叶子结点3.用孩子链存储结构表示树，其优点之一是比较方便（）A.判断两个指定结点是不是兄弟 B.找指定结点的双亲C.判断指定结点在第几层 D.计算指定结点的度数4.如果在树的孩子兄弟链存储结构中有6个空的左指针域，7个空的右指针域，则该树中树叶的个数为（ ）A.7个 B.

16、6个 C.13个 D.不能确定,A,A,D,B,5.设森林F中有3棵树，第一，第二，和第三棵树的结点个数分别为m1，m2和m3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ） A.m1 B.m1+m2 C.m3 D.m2+m36.如果T1是由树T转换而来的二叉树，那么T中结点的后根序列就是T1中结点的（ ）序列 A.先序 B.中序 C.后序 D.层次7.二叉树和度为2的树的相同之处包括（ ） A.每个结点都有一个或两个孩子结点 B.至少有一个根结点 C.至少有一个度为2的结点 D.每个结点至多只有一个双亲结点,D,B,D,8.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为

17、0的结点个数是（ ） A.9 B.11 C.15 D.不确定9.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A.500 B.501 C.254 D.50510.一棵有124个叶子结点的完全二叉树，最多有（ ）个结点。 A.247 B.248 C.249 D.25011.在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ ） A. (n+1)/2 B. (n-1)/2 C. n/2 D. n/2,B,B,B,D,12.如果一棵二叉树的先序序列是ab，中序序列是ba，则（ ） A.结点a和结点b分别在某结点的左子树和右子树中 B.结点b在结点a的右子树中 C.结点b在结点a

18、的左子树中 D.结点a和结点b分别在某结点的两棵非空子树中13.设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（ ）个结点。 A. 13 B.12 C.26 D.2514.根据使用频率为5个字符设计的哈夫曼编码不可能的是（ ） A.111,110,10,01,00 B.000,001,010,011,1 C.100,11,10,1,0 D.001,000,01,11,10,C,D,C,15.若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，采用（ ）遍历方法最合适。 A.先序 B.中序 C.后序 D.层次16.若二叉树的中序序列是abcdef，且c为根结点，则（ ） A

19、.结点c有两个孩子 B.二叉树有两个度为0的结点 C.二叉树的高度为5 D.以上都不对17.在任何一棵二叉树中，如果结点a有左孩子b，右孩子c，则在结点的先序序列、中序序列、后序序列中，（ ）A.结点b一定在结点a的前面 B.结点a一定在结点c的前面C.结点b一定在结点c的前面 D.结点a一定在结点b的前面,C,A,C,第七章 图,7.1 图的类型定义,7.2 图的存储结构,7.3 图的遍历,7.4 最小生成树,7.5 有向无环图及关键路径,7.6 最短路径,2.熟悉图的各种存储结构，解实际问题的求解效率与采用何种存储结构有密切联系。,本章学习要点,3.熟练掌握图的两种搜索路径的遍历：深度优先

20、搜索和广度优先搜索的算法。,4.掌握图的最小生成树、拓扑排序、关键路径和最短路径的求解方法,1.熟练掌握图的各相关定义。,1. 在一个有向图中，所有顶点的度数之和等于图的弧数的（ ）倍。 A1/2 B. 1 C. 2 D. 4 2. 无向图的邻接矩阵是一个（）。 A. 对称矩阵 B. 零矩阵 C. 上三角矩阵 D. 对角矩阵3.一个有n个结点的有向完全图有（）条弧。 A. n B. n(n-1) C. n(n-1)/2 D. 2n4.具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 85.G是一个非连通无向图，共有28条边，则该图至少有（） 个顶点

21、。 A. 6 B. 7 C. 8 D. 9,C,A,B,A,D,第7章练习题,练习题,6. 下面结构中最适于表示稀疏无向图的是（）。A. 邻接矩阵 B. 邻接表 C. 邻接多重表 D. 十字链表7.任何一个无向连通图有（）最小生成树。 A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 8. n条边的无向图的邻接表的存储中，边结点的个数有 （）个。 A. n B. 2n C. n/2 D. nn9.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。 A.完全图 B.连通图 C.有回路 D.一棵树,C,B,B,B,练习题,10.采用邻接表存储的

22、图的深度优先遍历算法类似于二叉树的（）算法。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历11.对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个（）。 A. 由n-1条权值最小的边构成的子图 B. 由n-1条权值之和最小的边构成的子图 C.由n-1条权值之和最小的边构成的连通子图 D. 由n个顶点构成的边的权值之和最小的连通子图,A,D,练习题,12.判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（）。 A. 求关键路径的方法 B. 求最短路径的方法 C.广度优先遍历算法 D. 深度优先遍历算法13.若图的邻接矩阵中主对角线上的元素全是0，其余元素全是1，

23、则可以断定该图一定是（）。 A. 无向图 B. 不是带权图 C. 有向图 D. 完全图14.关键路径是AOV网中（）。 A.从源点到汇点的最长路径 B.最长的回路 C.从源点到汇点的最短路径 D.最短的回路15.最短路径的生成算法可用（）。 A. Prim算法 B. Kruskal算法 C. Dijkstra算法 D. Huffman算法,D,D,A,C,练习题,填空题1.一个图的 示法是唯一的，而 表示法是不唯一的。2.用一个邻接矩阵存储有向图G，其第i行的所有元素之和等于顶点i的 。3.图的逆邻接表存储结构只适用于 图。4.连通分量是无向图的 连通子图。5.一个连通图的 是一个极小连通子图

24、。6. Prim算法适用于求 网的最小生成树； 7. Kruskal适用于求 网的最小生成树。8.如果n个顶点的图是一个环，则它有 棵生成树。9.拓扑排序算法是通过重复选择具有 个前驱顶点的过程来完成的。,邻接矩阵,邻接表,出度,有向,极大,生成树,边稠密,边稀疏,n,0,第九章 查 找,9.1 静态查找表,9.2 动态查找表,9.3 哈希表,1.顺序表和有序表的查找方法及其平均查找长度的计算方法。2.熟练掌握折半查找和判定树的构造。3.熟练掌握二叉排序树的构造和查找方法。4.熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。5.掌握按定义计算各种查找方法在等概率情况下查找

25、成功时的平均查找长度。,本章学习要点,填空题1.在数据的存放无规律而言的线性表中进行查找的最佳方法是（）。2.线性有序表（a1，a2，a3，a256）是从小到大排列的，对一个给定的值k，用折半查找法查找表中与k相等的元素，在查找不成功的情况下，最多需要比较（）次。设有100个结点，用折半查找法查找时，最大比较次数是（）。3.假设在有序线性表a20上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为（）；比较四次查找成功的结点数为（）；平均查找长度为（）。,顺序查找,2，8，3.7,9，7,（1122438455）/20 =74/20=3.7,第9章练习题,4.折半查找有序

26、表4，6，12，20，28，38，50，70，88，100，若查找表中元素20，它将依次与表中元素（ ）比较大小。5.对二叉排序数进行（）遍历，可以得到按关键字从小到大排列的结点序列。6.评价哈希函数好坏的标准是（）。7.哈希表存储的基本思想是由（）决定数据的存储地址。选择题1. 静态查找表与动态查找表的根本区别在于（）。A. 逻辑结构不一样 B. 施加在其上的操作不一样 C. 所包含的数据元素类型不一样 D. 存储实现不一样,28，6，12，20,中序,哈希函数取值是否均匀,B,关键字的值,2. 在表长为n的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为（）。 A. n B. 1

27、C. n+1 D. n-13.顺序查找适用于存储结构为（）的线性表。 A. 哈希存储B.压缩存储C. 顺序或链式存储D.索引存储4.适于折半查找的表的存储方式及元素排列要求为（）A. 链式,无序 B.链式,有序 C. 顺序,无序 D.顺序,有序5.对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。A3 B4 C5 D 6,A,C,D,B,6.二叉排序树中，键值最小的结点一定（）A.左指针为空 B.右指针为空C.左右指针均为空 D.左右指针均非空7. 在有序表1，3，9，12，32，41，62，75，77，82，95，100上进行折半查找关键字为82的数据元素需要比较（）次

28、。 A. 1 B. 2 C. 4 D. 5 8. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应分（）个结点最佳。 A. 10 B. 25 C. 6 D. 625,A,C,B,9.设哈希表长为14，哈希函数为H(key)=key mod 11，当前表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7。如用二次探测再散列处理冲突，则关键字为49的结点的地址是（）。 A. 8 B.3 C. 5 D.910. 假设有K个关键字互为同义词，若用线性探测法把这K个关键字存入哈希表中，至少要进行（）次探测。AK-1 BK CK+1 D K(K-1)/2,D,D,0+1+2+(k-1)=k(k-1)/2,