数据结构习题集答案

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

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

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

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

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

6、ead-llink= head , head-rlink= head 。在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是 。=p-next;next=p-next-next;next=p;=p-next-next;在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点,贝U需执行 OA. s-next=p-next;p-next=sB. q-next=s;s-next=pC. p-next=s-next;s-next=pnext=s;s-next=q用链表表示线性表的优点是()A.便于随机存储B.便于进行插入和删除操作C.占用的存储空

7、间较顺序表少D.元素的物理顺序与逻辑顺序相同下面关于线性表的叙述中，错误的是()A.线性表采用顺序存储必须占用一片连续的存储单元B.线性表采用顺序存储便于进行插入和删除操作C.线性表采用链式存储不必占用一片连续的存储单元D.线性表采用链式存储便于进行插入和删除操作线性表是具有n个()的有限序列A.数据项 B.数据元素C. 表元素 D. 字符长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为()A. O (1)(n) C. O(n2)(log 2n)在长度为n的顺序表删除第i (1Wi wn)个元素，则需要向前移动元素的次数为()A. iB. n-iC. n-i+1在长度为n的

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

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

10、-1top!= MaxSizeD. ST-top=MaxSize-1循环队列用数组 A0, m-1存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是 。A. (rear-front+m ) %m B. rear-front+1C. rear-front-1 D. 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分别是队头和队尾指针，则删除一个结点的运算时 。A

11、. r=f-next; B. r=r-next;C. f=f-next; D. f=r-next;若进栈序列为a, b, c,进栈过程中允许出栈，则以下 是不可能得到的出栈序列。A. a,b,c B. b,a,cC. c,a,b D. 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， 1 C. 3， 1， 4， 2， 4， 2 ， 1一个队列的入队序列是1, 2, 3, 4,则队列的输出序列是 。A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1若用一个可容纳6个元素的数组来实现循环队列，且当前 rear和front的值分别是0和4,当执行2次 出队和1次入队操作后，rear和front的值分别为()和0 和2C.2和5 和5第四章串和数组串是一种特殊的线形表，其特殊性体现在 A.可以顺序存储B.数据元素

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

14、，第一种是以_行 为主序的存储方式,第二种是以人为主序的存储方式。设有二维数组A1020,其中每个元素占2个字节，数组按行优先顺序存储，第一个元素的存储地址为100,那么元素 A812的存储地址为100+ (20*8+12) *2对于稀疏矩阵的压缩存储，通常用一个三元组表示非零元素的信息，其中包括非零元素的 值、行、列。这些信息可用一个三元组数组表示,也称此为三元组顺序表。设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主序存储， 的0为第一个元素，其存储地址为 1,每个元素占1个字节，则a8,5的地址为 。A. 13 B. 33 C. 18 D. 42第五章树与二叉树采用二叉链表存储结

15、构，具有n个结点的二叉树中，一共有匹个指针域，其中有_n1_个指针域指向孩子结点，有_n+1_个指针域为空.一棵非空二叉树，其第i层上最多有_2_结点。满二叉树是一棵深度为 k且恰有_23结点的二叉树.一棵哈夫曼树有个 m叶子结点,则其结点总数为_2m-1_.三个结点的二叉树，最多有 _5_种形状。将一棵完全二叉树按层次编号 ，对任一编号为i的结点有：如有左孩子，则其编号为_2i_;如有右孩子，则其编号为_2i+1 .深度为k的非空二叉树最多有2k-1个结点，最少有k个结点，其第i层最多有2i-1个结点。树最适合用来表示 。A.有序数据元素B.无序数据元素C.数据之间具有分支层次关系的数据D.

16、元素之间无联系的数据在下列存储形式中，不是树的存储形式的是 。A.双亲表示法B.孩子表示法C.孩子双亲表示法D.孩子兄弟表示法一棵高度为h的满二叉树中结点的个数为 。A. 2 h B. 2 h-1 C. 2h-1+1已知一棵二叉树的先序遍历序列为ABCDEF曲序遍历序歹U为：CBDAFEG则该二叉树的后序遍历序列是().CDBFGEA B . CDFGBEA C . CDBAFGE D . CDBFEGA具有100个结点的完全二叉树，其中含有 个度为1的结点。0 C. 2 D.不确定已知一棵二叉树的先序遍历序列为EFHIGJK,中序遍历序列为：HFIEJGK,则该二叉树的右子树的根是 ().A

17、. E B.FC.GD.J如下左图所示二叉树的中序遍历序列是A. abcdgef B. dfebagc C. dbaefcg D. defbagcA. abdgcefh B. dgbaechf C . gdbehfca D . abcdefgh在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该（）A,只有左子树上的所有结点B,只有左子树上的部分结点C.只有右子树上的所有结点D.只有右子树上的部分结点在一非空二叉树的中序遍历序列中，根结点的右边应该 。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点有一棵树如下左图所示，回答下列问题：这

18、棵树的根结点是 _色;这棵树的叶子结点是 _k2,k4,k5,k7 结点k3的度为 2;这棵树的度为 了一这棵树的深度为_4_;结点k3的孩子结点是 k5,k6 结点k3的双亲结点是k1由上右图所示的二叉树，回答以下问题。其中序遍历序列为其先序遍历序列为其后序遍历序列为(4)该二叉树对应得森林是某二叉树的先序遍历序列为abdgcefh,中序遍历序列是dgbaechf,请画出该二叉树并给出其后序遍历序歹U。gdbehfca如下左图所示,以数据集4, 5, 6, 7, 10,12,18）为结点权值所构成的二叉树为哈夫曼树 ,其带权路径长度为 165O,结点E的层次为对如上右图所示的树，该树的高度为

19、，该树的度为结点H的双亲为H的兄弟为,结点B的度为若二叉树中度为2的结点有15个,该二叉树则有16个叶结点。若深度为6的完全二叉树的第6层有3个叶结点,则该二叉树一共有34个结点。二叉树的前序遍历序列为A, B, C, E, F, D, G,H,中序遍历序列为A, E, C, F, B, G, D, H,其后序遍历序列为 一个深度为k的二叉树，当具有 2k-1个结点时称之为 满二叉树。卜面关于哈夫曼树的说法， 不正确的是（）A.对应于一组权值构造出的哈夫曼树一般不是唯一的B.哈夫曼树具有最小带权路径长度C.哈夫曼树中没有度为1的结点D.哈夫曼树中除了度为 1的结点外，还有度为 2的结点和叶结点

20、在如图所示的表达式二叉树中，按中序遍历得到的序列为第六章 图一个具有n个顶点的无向连通图至少有坦条边，所有顶点的度数之和等于所有边数的2_倍。在有向图的邻接矩阵中，第 i行中1的个数为第i个顶点的 出度第i列中1的个数为第i个顶 点的 入度。一个无向图有n个顶点和e条边，则所有顶点的度的和为必。具有n个顶点的无向完全图的边数为 n(n-1)/2 o具有n个顶点的有向完全图的弧个数为_ n(n-1) _。设连通图G的顶点数为n,则G的生成树的边数为 _n-1 。若无向图中有e条边，则表示该无向图的邻接表中就有2e个结点。Dijkstra算法是按路径长序依次递增的次序产生一点到其余各顶点最短路径的

21、算法。可以进行拓扑排序的有向图一定是无环的。在拓扑排序序列中第一个顶点一定是入度为零 的顶点6.8设一个无向图为如下左图所示，画出该图的邻接表和邻接矩阵；度优先和广度优先搜索得到的顶点序列。2232写出从顶点A出发进行深312 36.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出发进行深度优先和广度优先搜索得到的顶点序 列。设一个无向图为G=(V,E),其中V=v1,v2,v3,v4, v5,v6

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

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

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

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

26、立一颗二叉排序 .(1)画出该二叉排序树；(2)在(1)的基础上插入结点50后，画出对应的二叉排序 ;(3) 在(2)的基础上删除结点26后，画出对应的二叉排序树。已知一组关键字序列为(75,33,52,41 ,12,88, 66,27),请按哈希函数H(key尸key MOD 7 ,分别用线性探测和二次探测处理冲突方法构造一个表长为10的哈希表。已知一组关键字为(17,12,21, 01 , 66,35,82,37),请按哈希函数H(key尸keyMODI3,分别用线性探测和二次探测处理冲突方法构造一个表长为14的哈希表。已知：哈希表长为 10,哈希函数 H(key)=key MOD 9,给出关键字序列为(23, 45, 14, 17, 9, 29,37, 18, 25,41,33 ),采用链地址法解决冲突，请画出哈希表。第八章 排序对于给定的12个整数：23, 37, 7, 79, 29 , 43, 73,