《工学期末复习题》PPT课件.ppt

期末复习,1. 算法的计算量的大小称为计算的（ B ）。 A效率 B. 复杂性 C. 现实性 D. 难度 2.从逻辑上可以把数据结构分为（ c ）两大类。 A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构 3若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ a）存储方式最节省时间。 A顺序表 B双链表 C带头结点的双循环链表 D单循环链表,4线性表（ a1,a2,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ d） AO（i） BO（1） CO（n） DO（i-1） 5 .串是任意有限个（ c ） A.符号构成的序列 B.符号构成的集合 C.字符构成的序列 D.字符构成的集合 6. 如果以链表作为栈的存储结构，则退栈操作时（ c ） A必须判别栈是否满 B.对栈不作任何判别 C.必须判别栈是否空 D.判别栈元素的类型,7. 设数组Data0m作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ d ） A.front=front+1 B.front=(front+1)% m C.rear=(rear+1)%m D.front=(front+1)%(m+1) 8. 深度为6（根的层次为1）的二叉树至多有（ d ）结点。 A.64 B.32 C.31 D.63 9. 某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是 （ D ） A.bdgcefha B.gdbecfha C. bdgechfa D. gdbehfca,10. 顺序队列的人队操作应为 ( d ) A.sq.rear=sq.rear+1 sq.datasq.rear=x B.sq.datasq.rear=x sq.rear=sq.rear+1 C.sq.rear=(sq.rear+1)% maxsize; sq.datasq.rear=x D.sq.datasqrear=x sq.rear=(sq.rear+1)% maxsize 11图中有关路径的定义是（ a ）。 A由顶点和相邻顶点序偶构成的边所形成的序列 B由不同顶点所形成的序列 C由不同边所形成的序列 D上述定义都不是 12设无向图的顶点个数为n，则该图最多有（ b ）条边。 An-1 Bn(n-1)/2 C n(n+1)/2 D0 En2,1.数据的逻辑结构是指数据的各数据项之间的逻辑关系；( f ) 2. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( f ) 3.顺序存储结构的主要缺点是不利于插入或删除操作。( t ) 4.线性表的特点是每个元素都有一个前驱和一个后继。( f) 5.链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 (t ),6.在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（ f） 7.对链表进行插入和删除操作时，不必移动结点。（ t ） 8.栈可以作为实现程序设计语言过程调用时的一种数据结构。（ t ） 9.在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧。( F ) 10.对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( F),1.设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_r-next =s_；r=s; r-next=null;。 2.N个顶点的连通图的生成树有_n-1_条边。 3一个有向图G中若有弧、和, 则在图G的拓扑序列中，顶点vi,vj和vk的相对位置为_i,j,k_。,4.如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1n，则结点X无_左孩子_且无_右孩子_；否则，X的左孩子LCHILD(X)的编号为_2i_。 (3)若2i+1n，则结点X无_右孩子_；否则，X的右孩子RCHILD(X)的编号为_2i+1_。,5.具有n个结点的二叉树中,一共有_2n_个指针域,其中只有_n-1_个用来指向结点的左右孩子，其余的_n+1_个指针域为NULL。,1以下数据结构中，（ a ）是非线性数据结构 A树 B字符串 C队 D栈 2.下面关于线性表的叙述中，错误的是哪一个？（ b ） A线性表采用顺序存储，必须占用一片连续的存储单元。 B线性表采用顺序存储，便于进行插入和删除操作。 C线性表采用链接存储，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。 3.链表不具有的特点是（ b ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比,4.非空的循环单链表head的尾结点p满足（a ）。 Ap-link=head Bp-link=NIL Cp=NIL Dp= head 5设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（ c ）个 A k+1 B 2k C 2k-1 D 2k+1 6.深度为5的二叉树至多有( c)个结点。 A 16 B 32 C 31 D10,7. 如图所示二叉树的中序遍历序列是（ b ） A abcdgef B dfebagc C dbaefcg D defbagc,8. 已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（ d） A acbed B deabc C decab D cedba 9. 循环队列的队满条件为 ( c ) A (sq.rear+1) % mazsize =(sq.front+1) % maxsize; B (sq.rear+1 % maxsize =sq.front+1 C sq.(rear+1) % maxsize =sq.front D sq.rear =sq.front 10.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ c ） 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,11一个n个顶点的连通无向图，其边的个数至少为（ a ）。 An-1 Bn Cn+1 Dnlogn； 12要连通具有n个顶点的有向图，至少需要（a ）条边。 An-l Bn Cn+l D2n,1.算法的优劣与算法描述语言无关，但与所用计算机有关。( f ) 2数据的物理结构是指数据在计算机内的实际存储形式。( f ) 3.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( f ) 4.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( t ) 5.取线性表的第i个元素的时间同i的大小有关. (f ),6如果两个串含有相同的字符，则这两个串相等。 （ f ） 7数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。 （ f ） 8在顺序表中取出第i个元素所花费的时间与i成正比。 Shun you guan lian wu guan （f ） 9在栈满情况下不能作进栈运算，否则产生“上溢”。 ( t ) 10对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点.（ f ）lian tong tu,1在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：u=l- next；L-next=U-next；free(U)； 2G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是完全连通图。 3如果一个有向图中没有回路和环，则该图的全部顶点可能排成一个拓扑序列。,4将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为24。 5.若以D、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有：_dlr_、_ldr_、_lrd_三种，按这三种次序进行的遍历分别称为_先序_、_中序_、_后序_。 6.具有n个结点的二叉树中,一共有_2n_个指针域,其中只有_n-1_个用来指向结点的左右孩子，其余的_n+1_个指针域为NULL。,1. 对于栈操作数据的原则是（ b ）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ b ）。 A. 不确定 B. n-i+1 C. i D. n-i 3. 设栈的输入序列是1，2，3，4,则（ d ）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2，,4. 执行完下列语句段后，i值为：（ b ） int f(int x) return (x0) ? x* f(x-1):2); int i ; i =f(f(1); A2 B. 4 C. 8 D. 无限递归 5下面关于线性表的叙述中，错误的是哪一个？（ b ） A线性表采用顺序存储，必须占用一片连续的存储单元。 B线性表采用顺序存储，便于进行插入和删除操作。 C线性表采用链接存储，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。,6线性表是具有n个（ c ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 7若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ b） A9 B11 C15 D不确定 8在一棵高度为k的满二叉树中，结点总数为（ a ） A2k-1 B2k C2k-1 Dlog2k+1,9已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ a ）。 ACBEFDA B FEDCBA C CBEDFA D不定 10. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（d ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G,D,E,F,11.设无向图的顶点个数为n，则该图最多有（ b ）条边。 An-1 Bn(n-1)/2 C n(n+1)/2 D0 12已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=, , G的拓扑序列是（ a ）。 AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7 CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V7,1. 链表的每个结点中都恰好包含一个指针。 （ f） 2. 链表的物理存储结构具有同链表一样的顺序。（ f） 3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（ f ） 4. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（ t ） 5. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（t ）,6. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。（ f ） 7.二叉树中所有结点个数是2k-1-1，其中k是树的深度。 （ f） 8.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ f） 9.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2(i1)个结点。（ t ） 10.二叉树中每个结点的两棵子树是有序的。 （ t ）,1. 向一个长度为n的向量的第i个元素(1in+1)之前插入一个元素时，需向后移动 n-i+1 个元素。 2.在单链表中，除了首元结点外，任一结点的存储位置由 前一个节点的指针域 指示。 3. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 4. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。 5由个结点所构成的二叉树有 5 种形态。,6. 用5个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是 33 。 解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL（453）2（12）3=33 7. 图有 邻接矩阵、 领接表 等存储结构，遍历图有 广度优先 、 深度优先 等方法。 8. 向栈中压入元素的操作是先 压入元素 ，后 移动指针 。,1.将给定的图简化为最小的生成树，要求从顶点1出发。 2.已知一棵二叉树的前序遍历的结果是, 中序遍历的结果是, 试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。 3. 将下面的森林变换成二叉树 4. 某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，试设计赫夫曼编码。 5.给出下列二叉树的先序序列，中序序列，后序序列。 6. 对下图分别进行深度，广度优先遍历的结果,6.4 遍历二叉树和线索二叉树,中序遍历结果:,a+b*c-d-e/f,6.4 遍历二叉树和线索二叉树,后序遍历结果:,abcd-*+ef/-,6.4 遍历二叉树和线索