数据结构习题集(答案)

1、精品数据结构习题第一章绪论0 以及它们之间的和运算等1.1 数据结构是一门研究非数值计算的程序设计问题中计算机的的学科。A.数据元素B.计算方法C.逻辑存储D.数据映像A.结构B.关系C.运算D.算法1.2 算法分析白目的是D，算法分析的两个主要方面是JD感谢下载载 A.找出数据结构的合理性C.分析算法的效率以求该进 A.空间复杂度和时间复杂度C.可读性和文档性B.研究算法中的输入和输出的关系D.分析算法的易懂性和文档性B.正确性和简明性D.数据复杂性和程序复杂性1.3计算机算法指的是,它必须具备输入、输出和等5个重要特性。A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法A.可读

2、性、可移植性和可扩展性B.可读性、可移植性和有穷性C.确定性、有穷性和可行性D.易读性、稳定性和安全性1.4 数据元素是数据处理的基本单位；数据项是数据处理的最小单位。1.5 数据结构是研究数据的逻辑结构禾口物理结构,并对这种结构定义相适应的运算，设计出相应的_空间复杂度和时间复杂度数算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为据的逻辑结构是指数据元素之间的关系包括线性结构、树形结构和图形结构三种类型，其中树形结构和图状结构合称为非线性结构。1.6 线性结构中元素之间存在_一对关系，树形结构中元素之间存在_一对多关系，图状结构中元素之间存在多对多关系。1.7 数据结构在计算

3、机中的表示称为数据的物理(或存储)结构，数据的物理结构可以采用顺序存储和垂式存储两种存储方法。1.8 顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的内存单元中；链式存储方法中元素间的关系是由_旨针来表示_的。第二章线性表2.1 链表不具备的特点是 A.可随机访问任一结点C.不必事先估计存储空间2.2 不带头结点的单链表headA. head=nullC. head->next=head2.3 带头结点的单链表 headA. head=nullC. head->next=head2.4 非空的循环单链表 headA. p->next=null2.5 在一个具有A. O(1

4、)B.插入删除不需移动元素D.所需空间与其长度成正比为空的判定条件是?B.head->next=nullD.head!=null为空的判定条件是一。B.head->next=nullD.head!=null的尾结点(由p所指向)满足B.p=nullC.p->next=headD.p=headn个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是B.O(n)C.O(n2)D.O(nlog2n)2.6 线性链表中各个结点之间的地址不一定连续。2.7 线性表中数据元素之间具有一对一,除第一个和最后一个元素外，其他数据元素有且只有一个后继和前趋。2.8 若频繁地对线性表进行

5、插入和删除操作，该线性表采用链式存储结构比较合适。2.9 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_p->next和p->next=_s的操作。2.10 已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1),那么，LOC(ai)=_LOC(a1)+(i-1)*k。2.12 若线性表采用顺序存储结构，每个数据元素占用3个存储单元，第11个数据元素的存储地址为130,则第1个数据元素的存储地址是100。2.13 若线性表采用顺序存储结构，线性表的最大长度为1000,每个数据元素占3个存储单元，则要分配

6、给该线性表_3000_存储单元，若第一个数据元素的存储地址是2000,则第11个元素的存储地址是_2030_q2.14 以head为头结点循环双链表为空时，应满足head->llink=head,head->rlink=head。2.15 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是。A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;2.16 在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点

7、，则需执行B. q->next=s;s->next=pD.p->next=s;s->next=qA.s->next=p->next;p->next=sC.p->next=s->next;s->next=p2.17 用链表表示线性表的优点是()A.便于随机存储B.便于进行插入和删除操作C.占用的存储空间较顺序表少D.元素的物理顺序与逻辑顺序相同2.18 下面关于线性表的叙述中，错误的是()A. 线性表采用顺序存储必须占用一片连续的存储单元B. 线性表采用顺序存储便于进行插入和删除操作C. 线性表采用链式存储不必占用一片连续的存储单元D.

8、 线性表采用链式存储便于进行插入和删除操作2.19 线性表是具有n个（）的有限序列A.数据项B.数据元素C.表元素D.字符2.20 长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为（）A.O（1）B.O（n）C.O（n2）D.O（log2n）2.21 在长度为n的顺序表删除第i（iwiwn）个元素，则需要向前移动元素的次数为（）A.iB.n-iC.n-i+1D.n-i-12.22 在长度为n的顺序表中第i（1<i<n）个位置上插入一个元素时，为留出插入位置所需要移动元素的次数为（）A.n-iB.iC.n-i-1D.n-i+12.23 以下对单链表的叙述错误的是（

9、）A.单链表中的每一个结点都由存放结点值的数据域和存放直接后继结点地址信息的指针域两部分组成B.从单链表的第i个结点出发，可以访问到链表中的任何一个结点C.在单链表结构中加入头结点可以简化结点的插入和删除操作D.单链表尾结点的指针域应置为空指针2.24 以下记叙中正确的是（）A. 线性表的链式存储结构优先于顺序存储结构B. 线性表的存储结构不影响其各种运算的实现C. 选择线性表的存储结构就是要保证存储其各个元素的值D.顺序存储属于静态结构，链式存储属于动态结构第三章栈与队列一、选择题3.1 栈的特点是B_,队列的特点是A_。A.先进先出B.先进后出3.2 栈和队列的共同点时?A.都是先进后出B

10、.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点3.3 一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是A.edcbaB.decbaC.dceabD.abcde3.4 判定一个栈ST（最多元素MaxSize）为空的条件是A.ST->top!=-1B.ST->top=-1C.ST->top!=MaxSizeD.ST->top=MaxSize-13.5 判定一个栈ST（最多元素MaxSize）为栈满的条件是A.ST->top!=-1B.ST->top=-1C.ST->top!= MaxSizeD. ST->top=MaxSi

11、ze-13.6 循环队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是A. ( rear-front+m ) %mB. rear-front+1C.rear-front-1D.rear-front3.7 在一个链队中，假设f和r分别是队头和队尾指针，则插入一个s结点的运算时A.f->next=s;f=s;B.r->next=s;r=s;C. s->next=r; r=s;D. s->next=f; f=s;3.8 在一个链队中，假设f和r分别是队头和队尾指针，则删除一个结点的运算时A.r=f->next;B.r=

12、r->next;C.f=f->next;D.f=r->next;3.9 若进栈序列为a,b,c,进栈过程中允许出栈，则以下是不可能得到的出栈序歹U。A.a,b,cB.b,a,cC.c,a,bD.c,b,a3.10 一个最多能容纳m个元素的顺序存储的循环队列Q，其头尾指针分别为front和rear，则判定该队列为满的条件是A.(Q.rear+1)%m=Q.frontB.Q.front=Q.rearC.Q.rear+1=Q.frontD.(Q.front+1)%m=Q.rear3.11一个最多能容纳m个元素的顺序存储的循环队列Q，其头尾指针分别为front和rear，则判定该队列

13、为空的条件是A.(Q.rear+1)%m=Q.frontB.Q.front=Q.rearC.Q.rear+1=Q.frontD.(Q.front+1)%m=Q.rear3.12 若进栈序列为1，2，3，4，进栈过程中可以出栈，则以下不可能的出栈序列是()A.1，4，3，2B.2，3，4，1C.3，1，4，2D.3，4，2，13.13 一个队列的入队序列是1,2,3,4,则队列的输出序列是A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,13.14 若用一个可容纳6个元素的数组来实现循环队列，且当前rear和front的值分别是0和4,当执行2次出队和1次入队操作后，rear

14、和front的值分别为()A.1和0B.0和2C.2和5D.1和5第四章串和数组4.1串是一种特殊的线形表，其特殊性体现在A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符4.2 串的两种最基本的存储方式是4.3 两个串相等的充分必要条件是4.4 如下陈述中正确的是A.串是一种特殊的线性表C.串中元素只能是字母4.5 不含任何字符的串称为空串4.6 设有字符串 S= "ABC123XYZ_啊序和链式。:长度相等_且_对应位置上的字符相等B.串的长度必须大于零D.空串就是空白串一其长度为长度等于零。A.9B.10C.11D.12”，问该串的长度为()4.7

15、 已知二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A00),则Aij的地址是_Joc(a00)+(n*i+j)*k。4.8 二维数组有两种存储方式，第一种是以行为主序的存储方式,第二种是以_1_为主序的存储方式。设有二维数组A1020,其中每个元素占2个字节，数组按行优先顺序存储，第一个元素的存储地址为100,那么元素A812的存储地址为_100+(20*8+12)*24.9 对于稀疏矩阵的压缩存储，通常用一个三元组表示非零元素的信息，其中包括非零元素的值、_列。这些信息可用一个三元组数组表示,也称此为三元组顺序表。4.10 设有一个10阶的对

16、称矩阵A,采用压缩存储方式，以行序为主序存储，a0,0为第一个元素，其存储地址为1,每个元素占1个字节，则a8,5的地址为A.13B.33C.18D.42第五章树与二叉树5.1 采用二叉链表存储结构，具有n个结点的二叉树中，一共有_2n个指针域，其中有_个指针域指向孩子结点，有n+1个指针域为空.5.2 一棵非空二叉树，其第i层上最多有_2-1_结点。5.3 满二叉树是一棵深度为k且恰有_2k-1结点的二叉树.5.4 一棵哈夫曼树有个m叶子结点，则其结点总数为2m-1.5.5 三个结点的二叉树，最多有_5_种形状。5.6 将一棵完全二叉科材$层次编号，对任一编号为i的结点有：如有左孩子则其编号

17、为2i;如有右孩子，则其编号为2i+1.5.7 深度为k的非空二叉树最多有2k-1个结点，最少有一个结点，其第i层最多有2i-1个结点。5.8 树最适合用来表示?A.有序数据元素B.无序数据元素C.数据之间具有分支层次关系的数据D.元素之间无联系的数据5.9 在下列存储形式中，不是树的存储形式的是A.双亲表示法B.孩子表示法C.孩子双亲表示法D.孩子兄弟表示法5.10 一棵高度为h的满二叉树中结点的个数为A. 2 hB. 2h-1C.2 h-1D.2h+15.11 已知一棵二叉树的先序遍历序列为ABCDEFG,中序遍历序列为：CBDAFEG,则该二叉树的后序遍历序列是（）.A.CDBFGEAB

18、.CDFGBEAC.CDBAFGED.CDBFEGA5.12 具有100个结点的完全二叉树，其中含有个度为1的结点。A.1B.0C.2D.不确定5.13 已知一棵二叉树的先序遍历序列为EFHIGJK,中序遍历序列为：HFIEJGK,则该二叉树的右子树的根是（）.A.EB.FC.GD.J5.14 如下左图所示二叉树的中序遍历序列是A. abcdgef B. dfebagc C. dbaefcg D. defbagc5.15 一棵二叉树如上右图所示，其中序遍历的序列为A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh5.16 在非空二叉树的中序遍历序列中，二叉树的根结

19、点的左边应该（）A.只有左子树上的所有结点B.只有左子树上的部分结点C.只有右子树上的所有结点D.只有右子树上的部分结点5.17 在一非空二叉树的中序遍历序列中，根结点的右边应该?A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点5.18 有一棵树如下左图所示，回答下列问题：这棵树的根结点是_k£这棵树的叶子结点是k2,k4,k5,k7结点k3的度为_2;这棵树的度为3这棵树的深度为_4_;结点k3的孩子结点是_k5,k6结点k3的双亲结点是k15.19 由上右图所示的二叉树，回答以下问题。其中序遍历序列为其先序遍历序列为其后序遍

20、历序列为(4)该二叉树对应得森林是5.20 某二叉树的先序遍历序列为abdgcefh,中序遍历序列是dgbaechf,请画出该二叉树并给出其后序遍历序列。gdbehfca5.21 如下左图所示，以数据集4,5,6,7,10,12,18为结点权值所构成的二叉树为哈夫曼树其带权路径长度为_165q5.22对如上右图所示的树，该树的高度为2该树的度为结点E的层次为结点H的双亲为结点H的兄弟为结点B的度为5.23若二叉树中度为2的结点有15个，该二叉树则有16 个叶结点。5.24若深度为6的完全二叉树的第 6层有3个叶结点,则该二叉树一共有34个结点。5.25二叉树的前序遍历序列为A,B,C,E,F,

21、D,GH,中序遍历序列为A, E, C, F, B, G, D, H,其后序遍历序列为5.26一个深度为k的二叉树，当具有2k-1个结点时称之为"二叉树。5.27卜面关于哈夫曼树的说法，不正确的是（）A.对应于一组权值构造出的哈夫曼树一般不是唯一的B.哈夫曼树具有最小带权路径长度C.哈夫曼树中没有度为1的结点D.哈夫曼树中除了度为1的结点外，还有度为2的结点和叶结点5.28在如图所示的表达式二叉树中，按中序遍历得到的序列为第六章图6.1 一个具有n个顶点的无向连通图至少有_n-1条边,所有顶点的度数之和等于所有边数的2_倍。6.2 在有向图的邻接矩阵中，第i行中1的个数为第i个顶点的

22、出度_。第i列中1的个数为第i个顶点的入度_。6.3 一个无向图有n个顶点和e条边，则所有顶点的度的和为二£。具有n个顶点的无向完全图的边数为n(n-1)/2。具有n个顶点的有向完全图的弧个数为n(n-1)。6.4 设连通图G的顶点数为n,则G的生成树的边数为_n-1。6.5 若无向图中有e条边，则表示该无向图的邻接表中就有匹个结点。6.6 Dijkstra算法是按路径长序依次递增的次序产生一点到其余各顶点最短路径的算法。6.7 可以进行拓扑排序的有向图一定是_无环的在拓扑排序序列中第一个顶点一定是入度为零的顶点。6.8 设一个无向图为如下左图所示，画出该图的邻接表和邻接矩阵；写出从

23、顶点A出发进行深度优先和广度优先搜索得到的顶点序列。112 223232312323133j6.9 设一个无向图为G=(V,E),其中V=v1,v2,v3,v4,v5,v6,v7,画出该无向图，画出其邻接E=(v1,v2),(v1,v3),(v2,v4),(v2,v5),(v3,v6),(v3,v7),(v6,v7),表和邻接矩阵，写出从顶点v1出发进行深度优先和广度优先搜索得到的顶点序歹U。6.10 设一个无向图为G=(V,E),其中V=v1,v2,v3,v4,v5,v6,其邻接矩阵如上右图所示：(1)画出该无向图；(2)画出其邻接表和邻接矩阵；写出从顶点v1出发进行深度优先和广度优先搜索得

24、到的顶点序列；(4)分别用Prim和Kruskal算法，从顶点v1顶点出发，写出求该网的最小生成树的产生过程。6.11 设一个图为G=(V,E),其中V=a,b,c,d,e,f,E=<a,b>,<a,d>,<a,e>,<d,e>,<e,b>,<c,b>,<c,e>,<c,f>,<f,e>(1)画出该图；(2)画出其邻接矩阵和邻接表；写出从顶点a出发进行深度优先和广度优先搜索得到的顶点序列；6.15对如下无向图，分别用Prim和Kruskal算法，分别从顶点1和顶点a出发，写出求该网的最小

25、生成树的产生过程。6.16对下图，写出拓扑有序序列？6.17对下图所示的带权有向图，利用Dijstra算法求出从源点A到其余各顶点的最短路径及1其长度。第七章查找8.1 用顺序查找法在具有n各结点的线性表中查找一个结点所需的平均查找时间为()。AO(n)B.O(nlog2n)C.O(n)D.O(log2n)8.2 使用折半查找，线性表必须()。A、一顺序方式存储B、以链式方式存储，且元素已按值排好序C、以链式方式存储D、以顺序方式存储，且元素已按值排好序8.3 采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为A.nB.n/2C.(n+1)/2D.(n-1)/28.4 顺序查找法适

26、合于存储结构为的线性表。A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储8.5 采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为?A.O(n2)B.O(nlog2n)C.。D.O(log2n)8.6 采用顺序查找法检索长度为n的线性表，则检索每个元素的平均比较次数为n-i+1。8.7 有一个有序表为：(1,3,9,12,32,41,45,62,75,77,82,95,100),当折半查找值82的结点时，经过次比较后查找成功。A.1B.2C.4D.88.8 折半查找有序表6,15,30,37,65,70,72,89,99,若要查找元素37,需要依次与表中元素进行比较。A.

27、65,15,37B.68,30,37C.65,15,30D.65,15,30,378.9 已有序表为(20,18,24,35,47,50,62,83,90,115,134),当用折半法查找90时，需要进行_2_次查找可确定成功。查找47时需进行_4_次查找可确定成功，查找100时，需进行_4_次查找才能确定不成功。8.10 按序列60,17,38,40,7,32,73,65,85的输入顺序建立一颗二叉排序.(1)画出该二叉排序树；(2)在(1)的基础上插入结点80后，画出对应的二叉排序;(3)在(2)的基础上删除结点38后，画出对应的二叉排序树。8.11 按序列(53,49,26,78,63,

28、35,19,99)的输入顺序建立一颗二叉排序机L(1)画出该二叉排序树；(2)在(1)的基础上插入结点50后，画出对应的二叉排序机；(3)在(2)的基础上删除结点26后，画出对应的二叉排序树。8.12 已知一组关键字序列为(75,33,52,41,12,88,66,27),请按哈希函数H(key尸keyMOD7,分别用线性探测和二次探测处理冲突方法构造一个表长为10的哈希表。8.13 已知一组关键字为(17,12,21,01,66,35,82,37),请按哈希函数H(key尸keyMOD13,分别用线性探测和二次探测处理冲突方法构造一个表长为14的哈希表。8.14 已知：哈希表长为10,哈希函数H(key尸keyMOD9,给出关键字序列为(23,45,14,17,9,29.