数据结构各章习题.doc

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

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

3、将正确的答案填在相应的空中）1. 数据逻辑结构包括 、 、 和 四种类型 2. 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。3. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个直接前驱结点，叶子结点没有 结点，其余每个结点的直接后续结点可以 。4. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。5. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。6. 算法的五个重要特性是_ _ , _ _ , _ _ , _ _ , _ 2_。四、分析下列算法的时

4、间复杂度: 1sum=0;for (i=1;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 之间插入

5、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-n

6、ext-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.

7、O(n) C. O (n2) D. O (n*log2n)15.在 n 个结点的线性表的数组实现中，算法的时间复杂度是 O（1）的操作是 。A访问第 i（1next!=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 个结点的单链表，在已知

8、p 所指结点后插入一个新结点的时间复杂度是_ _；在给定值为 x 的结点后插入一个新结点的时间复杂度是_ _。三、简答 1. 算法分析的目的是什么？2. 什么是算法的最坏和平均时间复杂性？3. 什么是线性表？线性表的主要运算有哪些？4. 试比较顺序表与链表的优缺点。5. 写出在单链表 L 中的 p 所指结点之前插入一个 s 所指结点的操作。 四、算法题 1. 设顺序表 La 中的数据元数递增有序。试写一算法，将 x 插入到顺序表的适当位置上，以保持该表的有序性。2、写算法：在顺序表 L 中找到最小的元素，并将其与原来第一个元素换位置，显示改变后的顺序表。3、写算法：在单链表 L 中找到最小的元

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

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

11、 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）为空

12、的条件是 _ _,为满的条件是_ _。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. 向量（数组） 、栈和队列都是_ _结构，可以在向量的_ _位置插入和删除元素；对于栈只能在_ _插入和删除元素；对于队列只能在_ _插入元素和

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

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

15、15 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，中序遍历的结点访问顺序是 dgb

16、aechf，则其后序遍历的结点访问顺序是_ _。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca9. 在一非空二叉树的中序遍历序列中，根结点的右边_。A. 只有右子树上的所有结点 B. 只有右子树上的部分结点C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 10. 一棵二叉树如图 6.1 所示，其中序遍历的序列为 _。7iaedb chHf图 6.3 一棵二叉树giagedb chf图 6.1A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh11设 a,b 为一棵二叉树上的两个结点，在中序遍历时

17、，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. 2 C. 3 D. 414. 如图 6.2 所示的 4 棵二叉树，_不是完全二叉树。二、 填空题（将正确的答案填在相应的空中） 1. 将树转化为二叉树的基本目的是_ _。 2. 深度为 k 的完全二叉树至少有_ _个结点。至

18、多有_ _个结点，若按自上而下，从左到右次序给结点编号（从 1 开始） ，则编号最小的叶子结点的编号是 _。3. 在一棵二叉树中，度为零的结点的个数为 n0，度为 2 的结点的个数为 n2，则有 n0=_ _。4. 一棵二叉树的第 i（i1）层最多有_ _个结点；一棵有 n（n0）个结点的满二叉树共有_ _个叶子和_ _个非终端结点。5. 哈夫曼树是指_的二叉树6. 有如图 6.3 所示的二叉树，回答以下问题： 其中序遍历序列为_； 其前序遍历序列为_； 其后序遍历序列为_；(A) (B) (C) (D)图 6.28三、应用题1.分别写出下图所示二叉树的前序、中序和后序遍历序列。 2. 若二叉

19、树中各结点值均不相同。 1)已知一个二叉树的中序和后序遍历序列分别为 GDHBAECIF 和 GHDBEIFCA，请画出此二叉树。 2)已知一个二叉树的前序和中序分别为 ABCDEFGH 和 BDCEAFHG，请画出此二叉树。 3. 一个二叉树如图所示,将其转换为树。4画出该森林对应的二叉树。5有一份电文中共使用 5 个字符：a、b、c、d、e，它们的出现频率依次为5、2、1、6、4；试画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。 ABD E FCGHJIKN OML图 6.5 森林iaedb chHf图 6.4 一棵二叉树gi9四、算法设计题 1. 一个二叉树以链式结构存储，分别给出求二

20、叉树结点总数和叶子结点总数和高度的算法。 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

21、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-

22、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,bbae cd f1011已知一有向图的邻接表存储结构如图 6.2 所示。 根据有向图的深度优先遍历算法，从 v1 出发，所得到的顶点序列是

23、_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在图

24、 6.3 所示的拓朴排列的结果序列为 。A.125634 B.516234 C.123456 D.52163416一个有 n 个顶点的无向连通图，它所包含的连通分量个数为 。A.0 B.1 C.n D.n+117对于一个有向图，若一个顶点的入度为 k1,、出度为 k2，则对应邻接表中该顶点单链表中的结点数为 。A.k1 B.k2 C.k1-k2 D.k1+k218对于一个有向图，若一个顶点的入度为 k1,、出度为 k2，则对应逆邻接表中该顶点单链表中的结点数为 。A.k1 B.k2 C.k1-k2 D.k1+k2二、基本知识题 1. 图的逻辑结构特点是什么？什么是无向图和有向图？什么是子图？什么是网络？ 什么是完全图，生成树？图 6.2 一个有向图的邻接表存储结构图 6.1 一个无向图123453 24 52 4图 6.3 有向图