数据结构各章习题.doc

数据结构各章习题第1章 绪论一、名词解释 数据数据项数据元素数据结构 数据逻辑结构数据物理结构算法 算法的时间复杂性二、单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的 、数据信息在计算机中的 以及一组相关的运算等的课程。 A操作对象计算方法逻辑结构数据映象 A存储结构 关系 运算 算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是 的有限集合，R是D上的 有限集合。 A算法 数据元素 数据操作 数据对象 A操作 映象 存储 关系3. 在数据结构中，从逻辑上可以把数据结构分成 。A动态结构和静态结构 紧凑结构和非紧凑结构 线性结构和非线性结构 内部结构和外部结构4. 算法分析的目的是 ，算法分析的两个主要方面是 。 A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性 D. 数据复杂性和程序复杂性5.算法指的是 。A. 计算方法 B. 排序方法C. 解决问题的有限运算序列 D. 调度方法6. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。A.存储结构B.逻辑结构 C.链式存储结构D.顺序存储结构三、 填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括 、 、 和 四种类型 2. 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。3. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个直接前驱结点，叶子结点没有 结点，其余每个结点的直接后续结点可以 。4. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。5. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。6. 算法的五个重要特性是_ _ , _ _ , _ _ , _ _ , _ _。四、分析下列算法的时间复杂度: 1sum=0; for (i=1;i=n;i+) sum=sum+i; 2i=1; while(i=n) i=i*10;3sum=0; for(i=0;in;i+) for(j=0;jn;j+) sum=sum+Arrayij;4 s =0;for( I =0; in; i+) for(j=0;jn;j+)s +=Bij;sum = s ;5 for( i =0; in; i+) for(j=0;jm;j+)Aij 0;6 i 0；while（inext= =NULLC. head-next= =head D. head!=NULL7. 带头结点的单链表head为空的判定条件是_。A. head= =NULL B. head-next= =NULLC. head-next= =head D. head!=NULL8. 非空的循环单链表head的尾结点（由p所指向）满足_。A. p-next= =NULL B. p= =NULLC. p-next= =head D. p= =head 9. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_。A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p;B. q-next=s; s-next=p; C. p-next=s; s-next=q;10. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_。A. s-next=p; p-next=s; B. s-next=p-next; p-next=s;C. s-next=p-next; p=s; C. p-next=s; s-next=p;11. 在一个单链表中，若删除p所指结点的后续结点，则执行_。A. p-next= p-next-next； B. p= p-next; p-next= p-next-next；C. p-next= p-next; D. p= p-next-next；12. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_个结点。A. n B. n/2 C. (n-1)/2 D. (n+1)/213. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_ _。A. O(1) B. O(n) C. O (n2) D. O (nlog2n)14. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是_ _。A. O(1)） B. O(n) C. O (n2) D. O (n*log2n)15.在n个结点的线性表的数组实现中，算法的时间复杂度是O（1）的操作是 。A访问第i（1=i=n）个结点和求第i个结点的直接前驱（1i=n）B在第i（1=i=n）个结点后插入一个新结点C删除第i（1=inext!=p) q=q-next;s= new Node; s-data=e;q-next= ; /填空s-next= ; /填空4. 在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q= p-next;p-next= _ _; /填空delete ; /填空5. 在一个单链表p所指结点之后插入一个s所指结点，应执行s-next=_ _和p-next=_ _的操作。6. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是_ _；在给定值为x的结点后插入一个新结点的时间复杂度是_ _。三、简答 1. 算法分析的目的是什么？2. 什么是算法的最坏和平均时间复杂性？3. 什么是线性表？线性表的主要运算有哪些？4. 试比较顺序表与链表的优缺点。5. 写出在单链表L中的p所指结点之前插入一个s所指结点的操作。 四、算法题 1. 设顺序表La中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。2、写算法：在顺序表L中找到最小的元素，并将其与原来第一个元素换位置，显示改变后的顺序表。3、写算法：在单链表L中找到最小的元素，并将其与原来第一个元素换位置，显示改变后的单链表。4. 设计一个函数，查找单链表中数值为x的结点。 5. 已知一个单链表，编写一个删除其值为x的结点的算法。 6. 已知一个递增有序的单链表，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然递增有序。7. 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1, a2,. an）逆置为(an, an-1,., a1)。8. 试写一算法，实现单链表的就地逆置(要求在原链表上进行)。*9. 已知一个单链表，编写一个函数从此单链表中删除自第i个元素起的中k个元素*10. 有一个共10个结点的单链表，试设计一个函数将此单链表分为两个结点数相等的单链表。 *11. 已知一个指针p指向单循环链表中的一个结点，编写一个对此单循环链表进行遍历的算法。 *12. 一个顺序表中的元素为全部为正或者负整数，试设计一算法，在尽可能少的时间内重排该表，将正、负整数分开，使顺序表中所有负整数在正整数前面。 *13. 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。第3章 栈和队列一 单项选择题1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是_ _。A. edcba B. decba C. dceab D. abcde 2. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为_ _。 A. i B. n=i C. n-i+1 D. 不确定3. 栈结构通常采用的两种存储结构是_ _。4. 判定一个顺序栈ST（最多元素为m）为空的条件是_ _。5. 判定一个顺序栈ST（最多元素为m）为栈满的条件是_ _。6. 栈的特点是_，队列的特点是_。 A. 先进先出 B. 先进后出 7. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是_ _ 。 8. 判定一个循环队列Q（最多元素为m）为空的条件是 _ _,为满的条件是_ _。9. 循环队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_。A. (rear-front+m)%m B. rear-front+1C. rear-front-1 D. rear-front10. 栈和队列的共同点是_ _。A. 都是先进后出 B. 都是先进先出C. 只允许在端点处插入和删除元素 D. 没有共同点二 填空题（将正确的答案填在相应的空中）1. 向量（数组）、栈和队列都是_ _结构，可以在向量的_ _位置插入和删除元素；对于栈只能在_ _插入和删除元素；对于队列只能在_ _插入元素和_ _删除元素。2. 向栈中压入元素的操作是_ _。对栈进行退栈时的操作是_ _。（写涵数调用语句）3. 在一个循环队列中，队首指针指向队首元素的_ _。4. 从循环队列中删除一个元素时，其操作是_ _。（写涵数调用语句）三、简答题 1. 什么是栈？什么是队列？它们各自的特点是什么？ 2. 线性表、栈、队列有什么异同？ 3. 简述栈的入栈、出栈操作的过程。（用文字描述） 4. 在循环队列中简述入队、出队操作的过程。（用文字描述） 5. 在什么情况下，会选择使用栈或队列数据结构？ 6. 顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？四、读栈队相关的程序，写出程序的运行结果五、算法设计题 1. 输入一个任意的非负十进制整数,输出与其等值的八进值数。2. 试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。 3. 设计一算法能判断一个算术表达式中的圆括号配对是否正确。（提示：对表达式进行扫描，凡遇到“（”就进栈，遇到“）”就退出栈顶的“（”，表达式扫描完毕时栈若为空则圆括号配对正确。 第5章 树与二叉树一、 单项选择题1.树最适合用来表示_ _。A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据2.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。 A15 B16 C17 D473. 按照二叉树的定义，具有3个结点的不同形状的二叉树有_ _种。A. 3 B. 4 C. 5 D. 65. 深度为5的二叉树至多有_ _个结点。A. 16 B. 32 C. 31 D. 106. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_ _。 A. uwvts B. vwuts C. wuvts D. wutsv7. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_ _。 A. 正确 B. 错误8. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_ _。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca9. 在一非空二叉树的中序遍历序列中，根结点的右边_。A. 只有右子树上的所有结点 B. 只有右子树上的部分结点C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 10. 一棵二叉树如图6.1所示，其中序遍历的序列为 _。agedbchf图6.1A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh11设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。Aa在b的右方Ba在b的左方 Ca是b的祖先 Da是b的子孙12. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_ _。 A. acbed B. decab C. deabc D. cedba13.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为 。A. 1 B. 2C. 3D. 414. 如图6.2所示的4棵二叉树，_不是完全二叉树。(A) (B) (C) (D)图6.2二、 填空题（将正确的答案填在相应的空中） 1. 将树转化为二叉树的基本目的是_ _。 2. 深度为k的完全二叉树至少有_ _个结点。至多有_ _个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是 _。3. 在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为 n2，则有n0=_ _。4. 一棵二叉树的第i（i1）层最多有_ _个结点；一棵有n（n0）个结点的满二叉树共有_ _个叶子和_ _个非终端结点。iaedbchHf图6.3 一棵二叉树gi5. 哈夫曼树是指_的二叉树6. 有如图6.3所示的二叉树，回答以下问题： 其中序遍历序列为_； 其前序遍历序列为_； 其后序遍历序列为_；三、应用题1.分别写出下图所示二叉树的前序、中序和后序遍历序列。 2. 若二叉树中各结点值均不相同。 1)已知一个二叉树的中序和后序遍历序列分别为GDHBAECIF和GHDBEIFCA，请画出此二叉树。 2)已知一个二叉树的前序和中序分别为ABCDEFGH和BDCEAFHG，请画出此二叉树。 3. 一个二叉树如图所示,将其转换为树。iaedbchHf图6.4 一棵二叉树gi 4画出该森林对应的二叉树。ABDEFCGHJIKNOML图6.5 森林5有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为5、2、1、6、4；试画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。 四、算法设计题 1. 一个二叉树以链式结构存储，分别给出求二叉树结点总数和叶子结点总数和高度的算法。 2. 一个二叉树以链式结构存储，写出在二叉树中查找值为x的结点的算法。 3. 设计算法将一个以链式存储结构的二叉树进行各种遍历第6章 图 一、单项选择题1在一个图中，所有顶点的度数之和等于所有边数的_倍。A. 1/2 B. 1 C. 2 D. 4 2任何一个无向连通图的最小生成树 。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_倍。A. 1/2 B. 1 C. 2 D. 44一个有n个顶点的无向图最多有_条边。A. n B. n(n-1) C. n(n-1)/2 D. 2n5具有4个顶点的无向完全图有_条边。A. 6 B. 12 C. 16 D. 206具有6个顶点的无向图至少应有_条边才能确保是一个连通图。A. 5 B. 6 C. 7 D. 87在一个具有n个顶点的无向图中，要连通全部顶点至少需要_条边。A. n B. n+1 C. n-1 D. n/28对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_ _ 。 A. n B. (n-1)2 C. n-1 D. n*n9对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_；所有邻接表中的接点总数是_。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C.2e D. n+e 10已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为_；按宽度搜索法进行遍历，则可能得到的一种顶点序列为_。 A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,bbaecdf图 6.1 一个无向图11已知一有向图的邻接表存储结构如图6.2所示。12345324524图6.2 一个有向图的邻接表存储结构 根据有向图的深度优先遍历算法，从v1出发，所得到的顶点序列是_A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 根据有向图的宽度优先遍历算法，从v1出发，所得到的顶点序列是_。A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v212采用邻接表存储的图的深度优先遍历算法类似于二叉树的_。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历13采用邻接表存储的图的宽度优先遍历算法类似于二叉树的_。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历15在图6.3所示的拓朴排列的结果序列为 。A.125634B.516234C.123456D.521634图6.3有向图16一个有n个顶点的无向连通图，它所包含的连通分量个数为 。A.0B.1C.nD.n+117对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为 。A.k1B.k2C.k1-k2D.k1+k218对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 。A.k1B.k2C.k1-k2D.k1+k2二、基本知识题 1. 图的逻辑结构特点是什么？什么是无向图和有向图？什么是子图？什么是网络？ 什么是完全图，生成树？2. 什么是顶点的度？什么是路径？什么是连通图和非连通图？什么是非连通图的连通分量？ 3. 给出图所示的无向图G的邻接矩阵和邻接表两种存储结构。 4. 假设图的顶点是A、B请根据下面的邻接矩阵画出相应的无向图或有向图。5. 分别给出图所示G图的深度优先搜索和广度优先搜索得到的顶点访问序列。 6. 应用prim算法求图所示带权连通图的最小生成树。 7. 写出图所示有向图的拓朴排序序列。 8在无权图G的邻接矩阵A中，若(vi,vj)或vi,vj属于图G的边集合，则对应元素Aij等于_，否则等于_。9在无向图G的邻接矩阵A中，若Aij等于1，则Aji 等于_。 10已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是_ _。11已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是_ _。12如果含n个顶点的图形成一个环，则它有 棵生成树。三、算法设计题 1. 如图1所示图G，建立其对应的邻接表存储，并写出深度优先算法。 2. 如图1所示图G，建立其对应的的邻接矩阵存储，并写出广度优先算法。 图13. 编写一个函数 建立一个有向图的邻接表。 4. 编写一个无向图的邻接矩阵转换成邻接表的算法。第7章 查找一、基础知识题 1. 解释下列名词 (1) 查找 (2) 树型查找(3) 平衡因子 (4) 散列函数(5) 冲突 2. 设有序表为a,b,c,d,e,f,g，请分别画出对给定值f,g和h进行拆半查找的过程。 3. 试述顺序查找法、二分查找法和分块查找法对被查找表中元素的要求，每种查找法对长度为n的表的等概率查找长度是多少？4.顺序查找法的平均查找长度为_ _；折半查找法的平均查找长度为_ _；哈希表查找法采用链接法处理冲突时的平均查找长度为_ _。5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_。6.折半查找的存储结构仅限于_ _，且是_ _。7.假设在有序线性表A1.20上进行折半查找 ，则比较一次查找成功的结点数为_，则比较二次查找成功的结点数为_，则比较三次查找成功的结点数为_，则比较四次查找成功的结点数为_，则比较五次查找成功的结点数为_，平均查找长度为_。8. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为_；若采用折半法查找，则时间复杂度为_；9已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行_ _次查找可确定成功；查找47时，需进行_ _次查找成功；查找100时，需进行_ _次查找才能确定不成功。10二叉排序树的查找长度不仅与_ _有关，也与二叉排序树的_ _有关。11一个无序序列可以通过构造一棵_ _树而变成一个有序树，构造树的过程即为对无序序列进行排序的过程。12平衡二叉排序树上任一结点的平衡因子只可能是 、 或 。二、算法设计题 1. 一个链表的元素是从小到大排列的，试写出对此链表的查找算法，并说明是否可以采用折半查找2. 假设二叉排序树t的各元素值均不相同，设计一个算法按递增次序打印各元素值。第8章 排序一、 解释下列概念 (1) 排序 (2) 内部排序 (3) 堆 (4) 稳定排序 二、选择题1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是_。A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用_排序法。A. 起泡排序 B. 快速排序 C. 堆排序 D. 基数排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是_。A. 直接插入排序 B. 选择排序 C. 快速排序 D. 归并排序4. 一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始大顶堆为_。A. 79，46，56，38，40，80 B. 38，46, 56，79， 40，84，C. 84，79，56，38，40，46 D. 84，56，79，40，46，385. 一组记录的关键码为（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，796. 一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为_ _。A. 16，25，35，48，23，40，79，82，36，72 B. 16，25，35，48，79，82，23，36，40，72C. 16，25，48，35，79，82，23，36，40，72D. 16，25，35，48，79，23，36，40，72，827. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_。A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序