数据结构各习题

1、数据结构各章习题第1章绪论一、名词解释数据逻辑结构数据,数据元素的、数据信数据 数据项数据元素数据结构物理结构算法算法的时间复杂性二、单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中息在计算机中的 以及一组相关的运算等的课程。D.数据映象D算法 A 操作对象E.计算方法C.逻辑结构 A 存储结构E.关系C.运算2. 数据结构DS(Data Struct)可以被形式地定义为 DS=(D, R),其中D是 的有限集合，R是D上的有限集合。A 算法E.数据元素C.数据操作D.数据对象15A 操作E.映象C存储D关系3. 在数据结构中，从逻辑上可以把数据结构分成。A. 动态结构和静态结构E

2、.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4. 算法分析的目的是 ，算法分析的两个主要方面是研究算法中的输入和输出的关系 分析算法的易懂性和文档性 正确性和简明性数据复杂性和程序复杂性 A.找出数据结构的合理性B.C.分析算法的效率以求改进D. A.空间复杂性和时间复杂性B.C.可读性和文档性D.5. 算法指的是A. 计算方法B.排序方法C.解决冋题的有限运算序列D.调度方法6. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为()A. 存储结构B.逻辑结构C.链式存储结构D.顺序存储结构三、填空题(将正确的答案填在相应的空中)1. 数据逻辑结构包括 、

3、和 四种类型2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。4. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。6. 算法的五个重要特性是 , , o四、分析下列算法的时间复杂度：1 sum=O;for (i=1;i<=n ;i+) sum=sum+i;2. i=1; while(i&l

4、t;=n) i=i*10;3. sum=0;for(i=0;i< n;i+) for(j=0;j <n ;j+) sum=sum+Arrayij;4. s =0;for( I =0; i<n; i+) for(j=0;j <n ;j+) s +=Bij;sum = s ;5. for( i =0; i<n; i+)for(j=0;j<m;j+)Aij二 0;6. i = 0 ;while (i<=n)i = i * 3第2章线性表一、单项选择题100，每1. 一个向量（即一批地址连续的存储单元）第一个元素的存储地址是个元素的长度为2,则第5个元素的地址

5、是 。A. 110 B. 108 C. 100 D. 1202. 线性表的逻辑顺序与存储顺序总是一致的，这种说法 。A.正确B.不正确3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址A.必须是连续的B.部分地址必须是连续的C. 一定是不连续的 D.连续或不连续都可以4. 在以下的叙述中，正确的是 。A. 线性表的顺序存储结构优于链表存储结构B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况D. 线性表的链表存储结构优于顺序存储结构5. 在等概率情况下，顺序表的插入操作要移动 吉点。A.全部B. 半C.三分之一D

6、.四分之一6. 不带头结点的单链表head为空的判定条件是。A. head= =NULLB. head-> next= =NULLC. head-> next= =head D. head!=NULL7. 带头结点的单链表head为空的判定条件是。A. head= =NULLB. head-> next= =NULLC. head-> next= =head D. head!=NULL8. 非空的循环单链表head的尾结点(由p所指向)满足。A. p-> next= =NULL B. p= =NULLC. p->n ext= =headD. p= =head

7、9. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行。A. s->n ext=p->n ext; p->n ext=s; B. p->n ext=s->n ext; s->n ext=p;B. q->n ext=s; s->n ext=p;C. p->n ext=s; s->n ext=q;10. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行。A. s->n ext=p; p->n ext=s;B. s->n ext=p->n ext; p-&

8、gt;n ext=s;C. s->n ext=p->n ext; p=s;C. p->n ext=s; s->n ext=p;11. 在一个单链表中，若删除p所指结点的后续结点，则执行 。A. p->next= p->next->next ； B. p= p->next; p->next=p->next->next ；C. p->n ext= p->n ext;D. p= p->n ext- >n ext；12. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较结点。A.

9、n B. n/2 C. (n -1)/2D. (n+1)/213. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是。A. 0(1) B. 0( n) C. O (n2)D. O (nl og2 n)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个结点的直接前驱(1<i<=n)B. 在第i (1<=i<=n)个结点后插入

10、一个新结点C. 删除第i (1<=i<=n)个结点D. 以上都不对二、填空题1. 单链表可以做 的链接存储表示。2. 在双链表中，每个结点有两个指针域，一个指向，另一个指向3. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如 下操作：q=head;while (q->n ext!=p) q=q->n ext;s= new Node; s->data=e;q->n ext=;/填空s->n ext= ;/4.在一个单链表中删除填空p所指结点的后继结点时，应执行以下操作:q= p->n ext;填空填空p->n ext=

11、/delete ;/5. 在一个单链表p所指结点之后插入一个s所指结点，应执行s->next=_ 和p->next=的操作。6. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时 间复杂度是_ _ ;在给定值为x的结点后插入一个新结点的时间复杂度是三、简答1. 算法分析的目的是什么？2. 什么是算法的最坏和平均时间复杂性？3. 什么是线性表？线性表的主要运算有哪些？4试比较顺序表与链表的优缺点。5. 写出在单链表L中的p所指结点之前插入一个s所指结点的操作四、算法题1. 设顺序表La中的数据元数递增有序。试写一算法，将x插入到顺序表的适当 位置上，以保持该表的有序

12、性。2. 写算法：在顺序表L中找到最小的元素，并将其与原来第一个元素换位置， 显示改变后的顺序表。3. 写算法：在单链表L中找到最小的元素，并将其与原来第一个元素换位置， 显示改变后的单链表。4. 设计一个函数，查找单链表中数值为 x的结点。5. 已知一个单链表，编写一个删除其值为 x的结点的算法。6. 已知一个递增有序的单链表，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然递增有序。7. 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1, a2,.an )逆置为(an, an- 1,.,a1)。8. 试写一算法，实现单链表的就地逆置(要求在原链表上进行

13、)。*9.已知一个单链表，编写一个函数从此单链表中删除自第i个元素起的中k个元素*10.有一个共10个结点的单链表，试设计一个函数将此单链表分为两个结点数 相等的单链表。*11.已知一个指针p指向单循环链表中的一个结点，编写一个对此单循环链表 进行遍历的算法。*12. 一个顺序表中的元素为全部为正或者负整数，试设计一算法，在尽可能少 的时间内重排该表，将正、负整数分开，使顺序表中所有负整数在正整数前面。*13.已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一 算法，删除表中所有大于x且小于y的元素(若表中存在这样的元素)同时释放 被删除结点空间。第3章栈和队列一单项选择题1.

14、一个栈的入栈序列a, b, c, d, e,贝U栈的不可能的输出序列是 。A. edcba B.decba C.dceab D.abcde2. 若已知一个栈的入栈序列是1,2, 3,，n,其输出序列为p1, p2, p3,pn,若 p1= n,贝U 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，则队列的出队时输出序列

15、是 。8. 判定一个循环队列q （最多元素为m为空的条件是 _,为满的条件是_。9. 循环队列用数组A0 , m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是 。A. （rear-fro nt+m）%mB. rear-fr on t+1C. rear-fr on t-1D. rear-fr ont10. 栈和队列的共同点是。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D. 没有共同点二 填空题（将正确的答案填在相应的空中）1. 向量（数组）、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在 插入和删除元素；对于队列只能在

16、插入元素和删除元素。2. 向栈中压入元素的操作是 。对栈进行退栈时的操作是 。（写涵数调用语句）3. 在一个循环队列中，队首指针指向队首元素的_ _ 。4. 从循环队列中删除一个元素时，其操作是 。（写涵数调用语句）三、简答题1. 什么是栈？什么是队列？它们各自的特点是什么？2. 线性表、栈、队列有什么异同？3. 简述栈的入栈、出栈操作的过程。（用文字描述）4. 在循环队列中简述入队、出队操作的过程。（用文字描述）5. 在什么情况下，会选择使用栈或队列数据结构？6. 顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？四、读栈队相关的程序，写出程序的运行结果五、算法设计题1. 输入一个

17、任意的非负十进制整数，输出与其等值的八进值数。2试写一个算法判别读入的一个以 为结束符的字符序列是否是“回文” 00 3.设计一算法能判断一个算术表达式中的圆括号配对是否正确。（提示：对表达式进行扫描，凡遇到“（”就进栈，遇到“）”就退出栈顶的“（”，表达式扫 描完毕时栈若为空则圆括号配对正确。第5章树与二叉树一、单项选择题1. 树最适合用来表示0无序数据元素D.元素之间无联系的数据15,单分支结点数为30个，则叶子结A.有序数据元素B.C.元素之间具有分支层次关系的数据2假定在一棵二叉树中，双分支结点数为 点数为个。A. 15B. 16 C . 17 D . 473.按照二叉树的定义，具有3

18、个结点的不同形状的二叉树有 种A. 3 B. 4 C. 5 D. 65深度为5的二叉树至多有个结点。A. 16 B. 32 C. 31 D. 106. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为0A. uwvts B. vwuts C. wuvts D. wutsv7. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法0 A. 正确 B. 错误8. 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是。A. bdgcefha B. gdbecfha C. bdg

19、aechf D. gdbehfca9. 在一非空二叉树的中序遍历序列中，根结点的右边 0A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点10. 一棵二叉树如图6.1所示，其中序遍历的序列为_0A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh11. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件A. a在b的右方 B. a在b的左方 C . a是b的祖先 D . a是b的子孙12. 已知某二叉树的后序遍历序列是 dabec，中序遍历序列是debac，它的前序 遍历序歹寸是_ _

20、0A. acbed B. decab C. deabc D. cedba13. 已知一棵完全二叉树的结点总数为 9个，则最后一层的结点数为 A. 1B. 2C. 3D. 414. 如图6.2所示的4棵二叉树，不是完全二叉树。图6.2的二叉树abcdehi二、填空题(将正确的答案填在相应的空中)1. 将树转化为二叉树的基本目的是_2. 深度为k的完全二叉树至少有个结点。至多有个结点，若按自上而下，从左到右次序给结点编号(从1开始)，则编号最小的叶子结点的编P.日 号是 _。3. 在一棵二叉树中，度为零的结点的个数为n0,度为2的结点的个数为n2，贝卩有n0=。4. 一棵二叉树的第i (i >

21、; 1)层最多有个结点；一棵有n (n>0)个结点的满二叉树共有个叶子和个非终端结点。5. 哈夫曼树是指6. 有如图6.3所示的二叉树，回答以下问题:其中序遍历序列为;其前序遍历序列为;其后序遍历序列为;图6.3 一棵二叉树三、应用题1. 分别写出下图所示二叉树的前序、中序和后序遍历序列。2. 若二叉树中各结点值均不相同1) 已知一个二叉树的中序和后序遍历序列分别为 GDHBAECI和GHDBEIFC，请画 出此二叉树。2) 已知一个二叉树的前序和中序分别为 ABCDEFG和 BDCEAFH请画出此二叉树。3.一个二叉树如图所示，将其转换为树4.画出该森林对应的二叉树5. 有一份电文中共

22、使用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. 42. 任何一个无向连通图的最小生成树。A.只有一棵B.有一棵或多棵C. 一定有多棵D.可能不存在3. 在一个有向图中，所有

23、顶点的入度之和等于所有顶点的出度之和的 倍A. 1/2 B. 1 C. 2 D. 44. 一个有n个顶点的无向图最多有边。A. n B. n(n-1) C. n(n-1)/2D. 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

24、*n9. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量 的大小为_$_;所有邻接表中的接点总数是。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C.2e D. n+e10. 已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为 序列为_。 A. a,b,e,c,d,f B. A. a,b,c,e,d,f B.一;按宽度搜索法进行遍历，则可能得到的一种顶点e,c,f,e,b,d C.a,e,b,c,f,d D. a,e,d,f,c,ba,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d

25、,e,b11. 已知一有向图的邻接表存储结构如图6.2所示图6.2 一个有向图的邻接表存储 根据有向图的深度优先遍历算法，从v1出发，所得到的顶点序列是A. v1,v2,v3,v5,v4B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2D. 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.按层遍历1

26、3.米用邻接表存储的图的宽度优先遍历算法类似于二叉树的 oA.先序遍历B.中序遍历C.后序遍历D.按层遍历15. 在图6.3所示的拓朴排列的结果序列为。A.125634B.516234C.123456D.52163421A、0 11110 11110 1B-请根据下面的邻接矩阵画出相应的无向图或有向16. 一个有n个顶点的无向连通图，它所包含的连通分量个数为。A.OB.1C.nD.n+117. 对于一个有向图，若一个顶点的入度为k1,、出度为k2,则对应邻接表中该顶点单链表中的结点数为。A.k1B.k2C.k1-k2D.k1+k218. 对于一个有向图，若一个顶点的入度为k1,、出度为k2,则

27、对应逆邻接表中该顶点单链表中的结点数为。A.k1B.k2C.k1-k2D.k1+k2二、基本知识题1. 图的逻辑结构特点是什么？什么是无向图和有向图？什么是子图？什么是网 络？什么是完全图，生成树？2. 什么是顶点的度？什么是路径？什么是连通图和非连通图？什么是非连通图 的连通分量？3. 给出图所示的无向图G的邻接矩阵和邻接表两种存储结构0 110 00 0 0 101 0 0 0 1100C 00 10 105.分别给出图所示G图的深度优先搜索和广度优先搜索得到的顶点访问序列6. 应用prim算法求图所示带权连通图的最小生成树。7. 写出图所示有向图的拓朴排序序列8 在无权图G的邻接矩阵A中

28、，若(vi,vj)或v vi,vj 属于图G的边集合，则 对应元素Aij 等于，否则等于。9在无向图G的邻接矩阵A中，若Aij 等于1则Aji 等于。10已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是O11 已知一个图的邻接矩阵表示，删除所有从第 i个结点出发的边的方法是O12如果含n个顶点的图形成一个环，则它有棵生成树 二、算法设计题1. 如图1所示图G,建立其对应的邻接表存储，并写出深度优先算法。2. 如图1所示图G,建立其对应的的邻接矩阵存储，并写出广度优先算法图13. 编写一个函数 建立一个有向图的邻接表。4. 编写一个无向图的邻接矩阵转换成邻接表的算法 第7章查找一、基础

29、知识题1. 解释下列名词查找(2)树型查找(3)平衡因子散列函数(5)冲突2. 设有序表为a,b,c,d,e,f,g，请分别画出对给定值f,g和h进行拆半查找的过程。3. 试述顺序查找法、二分查找法和分块查找法对被查找表中元素的要求，每种 查找法对长度为n的表的等概率查找长度是多少？4顺序查找法的平均查找长度为;折半查找法的平均查找长度为;哈希表查找法采用链接法处理冲突时的平均查找长度为 。5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。6. 折半查找的存储结构仅限于，且是。7假设在有序线性表A1.2O上进行折半查找，则比较一次查找成功的结点数 为 ，则比较二次查找成功的结

30、点数为 ，则比较三次查找成功的结点数为 ，则比较四次查找成功的结点数为 ，则比较五次查找成功的结点数为 ，平均查找长度为 。8. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为_;若采用折半法查找，则时间复杂度为 ；9. 已知有序表为(12，18, 24，35, 47，50, 62，83, 90，115，134)，当用折半查找90时，需进行次查找可确定成功；查找47时，需进行次查找成功；查找100时，需进行次查找才能确定不成功。10. 二叉排序树的查找长度不仅与 有关，也与二叉排序树的 有关。11. 一个无序序列可以通过构造一棵树而变成一个有序树，构造树的过 程即为对无序序列进行排序的过

31、程。12. 平衡二叉排序树上任一结点的平衡因子只可能是、 或 。二、算法设计题1. 一个链表的元素是从小到大排列的，试写出对此链表的查找算法，并说明是 否可以采用折半查找2. 假设二叉排序树t的各元素值均不相同，设计一个算法按递增次序打印各元 素值。第8章排序一、解释下列概念(1)排序(2)内部排序堆(4)稳定排序二、选择题1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 CA.希尔排序B.起泡排序 C.插入排序 D.选择排序2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用卡序法。A.起泡排序B.快速排序 C. 堆排序 D.基数排序3.

32、 在待排序的兀素序列基本有序的前提下，效率最咼的排序方法是 。A.直接插入排序 B.选择排序 C. 快速排序 D.归并排序4. 一组记录的排序码为(46, 79, 56，38, 40，84)，则利用堆排序的方法建立 的初始大顶堆为。A. 79，46，56，38，40，80B. 38，46, 56 ，79，40，84，C. 84，79，56，38，40，46D. 84，56，79，40，46，385. 一组记录的关键码为(46, 79，56, 38, 40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。A. 38 , 40, 46,56,79, 84B. 40, 38,

33、46,79,56, 84C. 40 , 38, 46,56,79, 84D. 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,72B.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.排序方法中，从未排序'序列中依匚次取出元素与已排序序列(初始