数据结构习题集答案

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

2、C确定性、有穷性和可行性D易读性、稳定性和安全性数据元素是数据处理的基本单位；数据项是数据处理的最小单位。数据结构是研究数据的逻辑结构和物理结构,并对这种结构定义相适应的运算，设计出相应的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为一空间复杂度和时间复杂度。数据的逻辑结构是指数据元素之间的关系;包括线性结构、树形结构和图形结构三种类型，其中树形结构和图状结构合称为非线性结构。线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图状结构中元素之间存在多对多关系。数据结构在计算机中的表示称为数据的物理(或存储)结构，数据的物理结构可以采用顺序存储和链式存储一两种

3、存储方法。顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的内存单元中；链式存储方法中元素间的关系是由指针来表示的。第二章线性表链表不具备的特点是。A.可随机访问任一结点B.插入删除不需移动元素C不必事先估计存储空间D.所需空间与其长度成正比不带头结点白单链表head为空的判定条件是一。A.head=nullB.head->next=nullC.head->next=headD.head!=null带头结点的单链表head为空的判定条件是。A.head=nullB.head->next=nullC.head->next=headD.head!=null非空的循环单链表

4、head的尾结点(由p所指向)满足。A.p->next=nullB.p=nullC.p->next=headD.p=head在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是一。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)线性链表中各个结点之间的地址不一定连续。线性表中数据元素之间具有一对一，除第一个和最后一个元素外，其他数据元素有且只有一个后继和前趋。若频繁地对线性表进行插入和删除操作，该线性表采用链式存储结构比较合适。在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=p->next和p->next=

5、_s_的操作。已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1),那么，LOC(ai)=_LOC(a1)+(i-1)*k_。若线性表采用顺序存储结构，每个数据元素占用3个存储单元，第11个数据元素的存储地址为130,则第1个数据元素的存储地址是100。若线性表采用顺序存储结构，线性表的最大长度为1000,每个数据元素占3个存储单元，则要分配给该线性表_3000存储单元,若第一个数据元素的存储地址是2000,则第11个元素的存储地址是_2030_O以head为头结点循环双链表为空时，应满足head->llink=head,head->

6、rlink=head。在单链表中，指针p指向元素为x的结点，实现删除x的后继”的语句是。=p->next;>next=p->next->next;>next=p;=p->next->next;在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间才1人一个由s指的结点，贝U需执行OB.q->next=s;s->next=p>next=s;s->next=qB.便于进行插入和删除操作D.元素的物理顺序与逻辑顺序相同A.s->next=p->next;p->next=sC.p->next

7、=s->next;s->next=p用链表表示线性表的优点是()A.便于随机存储C.占用的存储空间较顺序表少下面关于线性表的叙述中，错误的是()A.线性表采用顺序存储必须占用一片连续的存储单元B.线性表采用顺序存储便于进行插入和删除操作C.线性表采用链式存储不必占用一片连续的存储单元D.线性表采用链式存储便于进行插入和删除操作线性表是具有n个()的有限序列A.数据项B.数据元素C.表元素D.字符长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为()A.O(1)(n)C.O(n2)(logzn)在长度为n的顺序表删除第i(1wiwn)个元素，则需要向前移动元素的次数

8、为()A.iB.n-iC.n-i+1在长度为n的顺序表中第i(1wiwn)个位置上插入一个元素时，为留出插入位置所需要移动元素的次数为()A.n-iB.iC.n-i-1D.n-i+1以下对单链表的叙述错误的是()A.单链表中的每一个结点都由存放结点值的数据域和存放直接后继结点地址信息的指针域两部分组B.从单链表的第i个结点出发，可以访问到链表中的任何一个结点C在单链表结构中加入头结点可以简化结点的插入和删除操作D.单链表尾结点的指针域应置为空指针以下记叙中正确的是()A.线性表的链式存储结构优先于顺序存储结构B,线性表的存储结构不影响其各种运算的实现C.选择线性表的存储结构就是要保证存储其各个

9、元素的值D.顺序存储属于静态结构，链式存储属于动态结构第三章栈与队列一、选择题栈的特点是B_,队列的特点是A_。A.先进先出B.先进后出栈和队列的共同点时。A.都是先进后出B.都是先进先出C只允许在端点处插入和删除元素D.没有共同点一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是。A.edcbaB.decbaC.dceabD.abcde判定一个栈ST（最多元素MaxSize）为空的条件是。> top!=-1B.ST->top=-1> top!=MaxSizeD.ST->top=MaxSize-1判定一个栈ST（最多元素MaxSize）为栈满白条件是。>

10、; top!=-1B.ST->top=-1> top!=MaxSizeD.ST->top=MaxSize-1循环队列用数组A0,m-1存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front在一个链队中，假设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;在一个链队中，假设f和r分别

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

12、m=若进栈序列为1,2,3,4,进栈过程中可以出栈，则以下不可能的出栈序列是()A.1,4,3,2,3,4,1C.3,1,4,2,4,2,1一个队列的入队序列是1,2,3,4,则队列的输出序列是。A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1若用一个可容纳6个元素的数组来实现循环队列，且当前rear和front的值分别是0和4,当执行2次出队和1次入队操作后，rear和front的值分别为()和0和2C.2和5和5第四章串和数组串是一种特殊的线形表，其特殊性体现在A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符串的两种最基本的存储方式是

13、_顺序和链式。两个串相等的充分必要条件是：长度相等且对应位置上的字符相等。如下陈述中正确的是。A.串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串不含任何字符的串称为空苴，其长度为长度等于零。设有字符串S="ABC123XY乙问该串的长度为().10C已知二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A00),则Aij的地址是_loc(a00)+(n*i+j)*k。二维数组有两种存储方式，第一种是以行为主序的存储方式,第二种是以_a_为主序的存储方式。设有二维数组A1020,其中每个元素占2个字节，数组

14、按行优先顺序存储，第一个元素的存储地址为100,那么元素A812的存储地址为100+(20*8+12)*2对于稀疏矩阵的压缩存储，通常用一个三元组表示非零元素的信息，其中包括非零元素的值、行、列这些信息可用一个三元组数组表示,也称此为三元组顺序表。设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主序存储，a。,。为第一个元素，其存储地址为1,每个元素占1个字节，则a8,5的地址为。A.13B.33C.18D.42第五章树与二叉树采用二叉链表存储结构，具有n个结点的二叉树中，一共有_2n_个指针域，其中有n1_个指针域指向孩子结点，有n+1个指针域为空.一棵非空二叉树，其第i层上最多有_2

15、2_结点。满二叉树是一棵深度为k且恰有2-1结点的二叉树.一棵哈夫曼树有个m叶子结点，则其结点总数为2m-1.三个结点的二叉树，最多有5种形状。将一棵完全二叉科材$层次编号，对任一编号为i的结点有：如有左孩子，则其编号为2i;如有右孩子，则其编号为_2i+1.深度为k的非空二叉树最多有2k-1个结点,最少有k个结点，其第i层最多有2i-1个结点。树最适合用来表示A.有序数据元素C.数据之间具有分支层次关系的数据在下列存储形式中，不是树的存储形式的是B.无序数据元素D.元素之间无联系的数据A.双亲表示法B.孩子表示法C.孩子双亲表示法D.孩子兄弟表示法一棵高度为h的满二叉树中结点的个数为A.2h

16、B.2h-1C.2h-1+1已知一棵二叉树的先序遍历序列为()A.CDBFGEAB.CDFGBEAC.CDBAFGED.CDBFEGA具有100个结点的完全二叉树，其中含有B.0C.2已知一棵二叉树的先序遍历序列为个度为1的结点。D.不确定EFHIGJ曲序遍历序列为：HFIEJGKffl该二叉树的右子树的根是().A.EB.FC.GD.JABCDEFGf序遍历序歹U为：CBDAFEU该二叉树的后序遍历序列是如下左图所示二叉树白中序遍历序列是A.abcdgefB.dfebagcC.dbaefcgD.defbagc一棵二叉树如上右图所示，其中序遍历的序列为A.abdgcefhB.dgbaechfC

17、.gdbehfcaD.abcdefgh在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该A.只有左子树上的所有结点C只有右子树上的所有结点B.只有左子树上的部分结点D.只有右子树上的部分结点在一非空二叉树的中序遍历序列中，根结点的右边应该A.只有右子树上的所有结点C.只有左子树上的部分结点有一棵树如下左图所示，回答下列问题:B.只有右子树上的部分结点D.只有左子树上的所有结点这棵树的根结点是结点k3的度为2k1这棵树的深度为_4_;结点k3的双亲结点是Js1这棵树的叶子结点是这棵树的度为3结点k3的孩子结点是k2,k4,k5,k7k5,k6由上右图所示的二叉树，回答以下问题。其中序遍历序列

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

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

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

21、G=(V,E),其中V=v1,v2,v3,v41231 232 212233 23133J，v5,v6,v7,E=(v1,v2),(v1,v3),(v2,v4),(v2,v5),(v3,v6),(v3,v7),(v6,v7),画出该无向图，画出其邻接表和邻接矩阵，写出从顶点v1出发进行深度优先和广度优先搜索得到的顶点序列。6.10 设一个无向图为G=(V,E),其中V=v1,v2,v3,v4,v5,v6,其邻接矩阵如上右图所示：(1)画出该无向图；(2)画出其邻接表和邻接矩阵；写出从顶点v1出发进行深度优先和广度优先搜索得到的顶点序列；(4)分别用Prim和Kruskal算法，从顶点v1顶点出

22、发，写出求该网的最小生成树的产生过程。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出发进行深度优先和广度优先搜索得到的顶点序列；对如下无向图，分别用Prim和Kruskal算法，分别从顶点1和顶点a出发，写出求该网的最小生成树的产生过程。11对下图，写出拓扑有序序列利用Dijstra算法求出从源点A

23、到其余各顶点的最短路径及其长对下图所示的带权有向图，度。第七章查找用顺序查找法在具有n各结点的线性表中查找一个结点所需的平均查找时间为()。AO(n)(nlog2n)(n)(log2n)使用折半查找，线性表必须()。A、一顺序方式存储B、以链式方式存储，且元素已按值排好序C、以链式方式存储D、以顺序方式存储，且元素已按值排好序采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为。A.nB.n/2C.(n+1)/2D.(n-1)/2顺序查找法适合于存储结构为的线性表。A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为

24、。A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)采用顺序查找法检索长度为n的线性表，则检索每个元素的平均比较次数为_n-i+1_o有一个有序表为：(1,3,9,12,32,41,45,62,75,77,82,95,100),当折半查找值82的结点时，经过次比较后查找成功。A.1B.2C.4D.8折半查找有序表6,15,30,37,65,70,72,89,99,若要查找元素37,需要依次与表中元素进行比较。A.65,15,37B.68,30,37C.65,15,30D.65,15,30,37已有序表为(20,18,24,35,47,50,62,83,90,115,134),

25、当用折半法查找90时，需要进行_2_次查找可确定成功。查找47时需进行_4_次查找可确定成功，查找100时，需进行_4_次查找才能确定不成功。按序列60,17,38,40,7,32,73,65,85的输入顺序建立一颗二叉排序.(1)画出该二叉排序树；(2)在(1)的基础上插入结点80后，画出对应的二叉排序;(3)在(2)的基础上删除结点38后，画出对应的二叉排序树。按序列(53,49,26,78,63,35,19,99)的输入顺序建立一颗二叉排序机L(1)画出该二叉排序树；(2)在(1)的基础上插入结点50后，画出对应的二叉排序;(3)在(2)的基础上删除结点26后，画出对应的二叉排序树。已知一组关键字序列为(75,33,52,41,12,88,66,27),请按哈希函数H(key尸keyMOD7,分别用线性探测和二次探测处理冲突方法构造一个表长为10的哈希表。已知一组关键字为(17,12,21,01,66,35,82,37),请按哈希函数H(key尸keyMOD13,分别用线性探测和二次探测处理冲突方法构造一个表长为14的哈希表。已知：哈希表长为10,哈希函数H(key)=keyMOD9,给出关键字序列为(23,45,14,17,9,29,37