数据结构习题集答案

数据结构习题第一章 绪论1.1数据结构是一门研究非数值计算的程序设计问题中计算机的_ 以及它们之间的_ 和运算等的学科。A.数据元素 B.计算方法 C.逻辑存储 D.数据映像A.结构 B.关系 C.运算 D.算法1.2 算法分析的目的是_ ，算法分析的两个主要方面是_ 。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率 以求该进 D.分析算法的易懂性和文档性 A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性1.3 计算机算法指的是_ ，它必须具备输入、输出和_ 等5个重要特性。 A.计算方法 B.排序方法C.解决问题的有限运算序列 D.调度方法 A.可读性、可移植性和可扩展性 B. 可读性、可移植性和有穷性C.确定性、有穷性和可行性 D.易读性、稳定性 和安全性1.4数据元素是数据处理的 基本单位；数据项是数据处理的_最小单位。1.5数据结构是研究数据的 逻辑结构_和_物理结构_，并对这种结构定义相适应的运算，设计出相应的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为_空间复杂度和时间复杂度。数据的逻辑结构是指_数据元素之间的关系_；包括线性结构、 树形结构和 图形结构 三种类型,其中树形结构和图状结构合称为_非线性结构_。1.6 线性结构中元素之间存在_一对一_ 关系，树形结构中元素之间存在_一对多_ 关系，图状结构中元素之间存在_多对多_ 关系。1.7 数据结构 在计算机中的表示称为数据的物理（或存储）结构，数据的物理结构可以采用_顺序存储和_链式存储_两种存储方法。1.8顺序存储方法是把逻辑上相邻的元素 存储在物理位置 相邻的内存单元中 ；链式存储方法中元素间的关系是由_指针来表示_的。第二章 线性表2.1 链表不具备的特点是 _ 。 A.可随机访问任一结点 B.插入删除不需移动元素C.不必事先估计存储空间 D.所需空间与其长度成正比2.2 不带头结点的单链表head 为空的判定条件是_。A. head=null B. head->next=nullC. head->next=head D. head !=null2.3带头结点的单链表head 为空的判定条件是_。A. head=null B. head->next=nullC. head->next=head D. head!=null2.4 非空的循环单链表head 的尾结点（由p所指向）满足_。A. p->next=null B. p=null C. p->next=head D. p=head2.5 在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)2.6线性链表中各个结点之间的地址 不一定 连续。2.7线性表中数据元素之间具有_一对一_，除第一个和最后一个元素外，其他数据元素有且只有_一个后继和前趋。2.8若频繁地对线性表进行插入和删除操作，该线性表采用 链式 存储结构比较合适。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.12 若线性表采用顺序存储结构，线性表的最大长度为1000，每个数据元素占3个存储单元，则要分配给该线性表_3000_存储单元，若第一个数据元素的存储地址是2000，则第11个元素的存储地址是_2030_。2.13 以head为头结点循环双链表为空时，应满足head->llink= head ，head->rlink= head 。 2.14 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是 。A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 2.15 在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行_。 A. s->next=p->next;p->next=s B. q->next=s;s->next=pC. p->next=s->next;s->next=p D.p->next=s;s->next=q2.16 用链表表示线性表的优点是（）A便于随机存储 B.便于进行插入和删除操作C. 占用的存储空间较顺序表少 D.元素的物理顺序与逻辑顺序相同2.17 下面关于线性表的叙述中，错误的是（）A. 线性表采用顺序存储必须占用一片连续的存储单元B. 线性表采用顺序存储便于进行插入和删除操作C. 线性表采用链式存储不必占用一片连续的存储单元D. 线性表采用链式存储便于进行插入和删除操作2.18 线性表是具有n个（）的有限序列A. 数据项 B. 数据元素 C. 表元素 D. 字符 2.19长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为（） A. O（1） B.O（n） C. O（n2） D.O（log2n）2.20 在长度为n的顺序表删除第i（1in）个元素，则需要向前移动元素的次数为（） A. i B. n-i C. n-i+1 D.n-i-12.21 在长度为n的顺序表中第i（1in）个位置上插入一个元素时，为留出插入位置所需要移动元素的次数为（） A. n-i B. i C. n-i-1 D. n-i+12.22 以下对单链表的叙述错误的是（）A. 单链表中的每一个结点都由存放结点值的数据域和存放直接后继结点地址信息的指针域两部分组成B.从单链表的第i 个结点出发，可以访问到链表中的任何一个结点C.在单链表结构中加入头结点可以简化结点的插入和删除操作D.单链表尾结点的指针域应置为空指针2.23 以下记叙中正确的是 （）A. 线性表的链式存储结构优先于顺序存储结构B. 线性表的存储结构不影响其各种运算的实现C. 选择线性表的存储结构就是要保证存储其各个元素的值D.顺序存储属于静态结构，链式存储属于动态结构 第三章 栈与队列一、选择题3.1 栈的特点是_B_ ，队列的特点是_A_ 。A.先进先出 B.先进后出3.2 栈和队列的共同点时_。A.都是先进后出 B.都是先进先出C.只允许在端点处插入和删除元素 D.没有共同点3.3 一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是_ 。A. edcba B. decba C. dceab D. abcde3.4 判定一个栈ST（最多元素MaxSize）为空的条件是_ 。A.ST->top!=-1 B. ST->top=-1C.ST->top!= MaxSize D. ST->top=MaxSize-13.5 判定一个栈ST（最多元素MaxSize）为栈满的条件是_ 。A.ST->top!=-1 B. ST->top=-1C.ST->top!= MaxSize D. ST->top=MaxSize-13.6 循环队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front和 rear,则当前队列中的元素个数是_。A.（rear-front+m）%m B. rear-front+1C. rear-front-1 D. 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=r->next; C. f=f->next; D. f=r->next;3.9若进栈序列为a，b，c，进栈过程中允许出栈，则以下_是不可能得到的出栈序列。A. a,b,c B. b,a,c C. c,a,b D. c,b,a3.10一个最多能容纳m个元素的顺序存储的循环队列Q，其头尾指针分别为front和rear，则判定该队列为满的条件是_A. (Q.rear+1)%m= =Q.front B. Q.front= =Q.rearC. Q.rear+1= =Q.front D. (Q.front+1)%m= =Q.rear3.11一个最多能容纳m个元素的顺序存储的循环队列Q，其头尾指针分别为front和rear，则判定该队列为空的条件是_A. (Q.rear+1)%m= =Q.front B. Q.front = = Q.rearC. Q.rear+1= =Q.front D. (Q.front+1)%m= =Q.rear3.12若进栈序列为 1，2，3，4，进栈过程中可以出栈，则以下不可能的出栈序列是（）A. 1，4，3，2 B.2，3，4，1 C. 3，1，4，2 D.3，4，2，13.13一个队列的入队序列是1，2，3，4，则队列的输出序列是_。A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,13.14 若用一个可容纳6个元素的数组来实现循环队列，且当前rear和front的值分别是0和4，当执行2次出队和1次入队操作后 ，rear和front 的值分别为（）A.1和0 B.0和2 C.2和5 D.1和5第四章 串和数组4.1串是一种特殊的线形表，其特殊性体现在_A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符4.2 串的两种最基本的存储方式是_顺序和链式_。4.3两个串相等的充分必要条件是: 长度相等_且_对应位置上的字符相等_。4.4 如下陈述中正确的是_。A串是一种特殊的线性表    B串的长度必须大于零   C串中元素只能是字母    D空串就是空白串4.5 不含任何字符的串称为_空串_,其长度为_长度等于零_。4.6 设有字符串S=“ABC123XYZ”，问该串的长度为（）A.9 B.10 C.11 D.124.7已知二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC（A00），则Aij的地址是_loc(a00)+(n*i+j)*k。4.8二维数组有两种存储方式，第一种是以_行 为主序的存储方式，第二种是以_列_为主序的存储方式。设有二维数组A1020，其中每个元素占2个字节，数组按行优先顺序存储，第一个元素的存储地址为100，那么元素A812的存储地址为_100+（20*8+12）*2 4.9对于稀疏矩阵的压缩存储，通常用一个三元组表示非零元素的信息，其中包括非零元素的值、 行、 列 。这些信息可用一个三元组 数组表示，也称此为 三元组顺序表 。4.10设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序存储，a0,0为第一个元素，其存储地址为1，每个元素占1个字节，则a8,5的地址为_。A. 13 B. 33 C. 18 D. 42第五章 树与二叉树5.1 采用二叉链表存储结构,具有n 个结点的二叉树中,一共有_2n_个指针域,其中有_n-1_个指针域指向孩子结点，有_n+1_个指针域为空.5.2 一棵非空二叉树,其第i层上最多有_2i-1_结点。5.3 满二叉树是一棵深度为k且恰有_2k-1_结点的二叉树.5.4 一棵哈夫曼树有个m叶子结点,则其结点总数为_2m-1_.5.5 三个结点的二叉树，最多有_5_种形状。5.6 将一棵完全二叉树按层次编号,对任一编号为i的结点有:如有左孩子,则其编号为_2i_; 如有右孩子,则其编号为_2i+1.5.7深度为k的非空二叉树最多有 2k-1个结点，最少有 k 个结点，其第i层最多有_2i-1 个结点。5.8 树最适合用来表示_。A. 有序数据元素 B.无序数据元素C. 数据之间具有分支层次关系的数据 D. 元素之间无联系的数据5.9 在下列存储形式中，不是树的存储形式的是_。A双亲表示法 B.孩子表示法 C.孩子双亲表示法 D.孩子兄弟表示法5.10 一棵高度为h的满二叉树中结点的个数为_。 A. 2h B. 2h-1 C. 2h-1 D.2h+15.11 已知一棵二叉树的先序遍历序列为ABCDEFG,中序遍历序列为:CBDAFEG,则该二叉树的后序遍历序列是()ACDBFGEA BCDFGBEA CCDBAFGE DCDBFEGA5.12具有100个结点的完全二叉树，其中含有_个度为1的结点。A.1 B. 0 C. 2 D. 不确定5.13 已知一棵二叉树的先序遍历序列为EFHIGJK,中序遍历序列为:HFIEJGK,则该二叉树的右子树的根是()A B C D5.14 如下左图所示二叉树的中序遍历序列是_A. abcdgef B. dfebagc C. dbaefcg D. defbagc 5.15 一棵二叉树如上右图所示，其中序遍历的序列为_Aabdgcefh Bdgbaechf Cgdbehfca Dabcdefgh5.16在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该 ( ) A.只有左子树上的所有结点 B.只有左子树上的部分结点 C.只有右子树上的所有结点 D.只有右子树上的部分结点5.17 在一非空二叉树的中序遍历序列中，根结点的右边应该_。A. 只有右子树上的所有结点 B.只有右子树上的部分结点C. 只有左子树上的部分结点 D. 只有左子树上的所有结点5.18 有一棵树如下左图所示，回答下列问题：这棵树的根结点是_k1_; 这棵树的叶子结点是_k2,k4,k5,k7_结点k3的度为_2_; 这棵树的度为_3_这棵树的深度为_4_; 结点k3的孩子结点是_ k5,k6_结点k3的双亲结点是_ k1_ 5.19 由上右图所示的二叉树，回答以下问题。 其中序遍历序列为_ 其先序遍历序列为_ 其后序遍历序列为_ (4) 该二叉树对应得森林是_5.20某二叉树的先序遍历序列为abdgcefh,中序遍历序列是dgbaechf, 请画出该二叉树并给出其后序遍历序列。gdbehfca5.21 如下左图所示 ,以数据集4，5，6，7，10，12，18为结点权值所构成的二叉树为_哈夫曼树_，其带权路径长度为_165_。 5.22对如上右图所示的树，该树的高度为_，该树的度为_，结点E的层次为_，结点H的双亲为_，结点H的兄弟为_，结点B的度为_。5.23若二叉树中度为2的结点有15个，该二叉树则有 16 个叶结点。5.24若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有 34 个结点。5.25二叉树的前序遍历序列为A，B，C，E，F，D，G，H，中序遍历序列为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个顶点的_出度_。第i列中1的个数为第i个顶点的_入度_。6.3 一个无向图有n个顶点和e条边，则所有顶点的度的和为_2e。具有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 设一个无向图为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出发进行深度优先和广度优先搜索得到的顶点序列。6.10 设一个无向图为G=(V,E),其中V=v1,v2,v3,v4，v5,v6 ，其邻接矩阵如上右图所示：(1)画出该无向图;(2)画出其邻接表和邻接矩阵;(3)写出从顶点v1出发进行深度优先和广度优先搜索得到的顶点序列;(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)画出其邻接矩阵和邻接表;(3)写出从顶点a出发进行深度优先和广度优先搜索得到的顶点序列;6.15对如下无向图，分别用Prim和Kruskal算法,分别从顶点1和顶点a出发，写出求该网的最小生成树的产生过程。62174112191010836 6.16 对下图，写出拓扑有序序列？A1a11B2D4C3E5F66.17 对下图所示的带权有向图，利用Dijstra算法求出从源点A到其余各顶点的最短路径及其长度。A11B2D4C3E5F251083167210124第七章 查找8.1用顺序查找法在具有各结点的线性表中查找一个结点所需的平均查找时间为（）。(n) B.O(nlog2n) C.O(n) D.O(log2n)8.2 使用折半查找，线性表必须（）。、一顺序方式存储、以链式方式存储，且元素已按值排好序、以链式方式存储、以顺序方式存储，且元素已按值排好序8.3 采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为_。 A. n B. n/2 C. （n+1）/2 D. (n-1)/2 8.4 顺序查找法适合于存储结构为_ 的线性表。A散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储8.5采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为_。 A. O(n2) B. O(nlog2n) C. O(n) 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. 1 B. 2 C. 4 D. 88.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，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，35，19，99）的输入顺序建立一颗二叉排序树.（1）画出该二叉排序树；（2）在（1）的基础上插入结点50后，画出对应的二叉排序树;(3) 在（2）的基础上删除结点26后，画出对应的二叉排序树。8.12 已知一组关键字序列为（75，33，52，41，12，88，66，27），请按哈希函数H(key)=key MOD 7，分别用线性探测和二次探测处理冲突方法构造一个表长为10的哈希表。8.13 已知一组关键字为（17，12，21，01，66，35，82，37），请按哈希函数H(key)=key MOD 13，分别用线性探测和二次探测处理冲突方法构造一个表长为14的哈希表。8.14 已知：哈希表长为10，哈希函数H(key)=key MOD 9，给出关键字序列为（23，45，14，17，9，29,37，18，25,41,33），采用链地址法解决冲突，请画出哈希表。第八章 排序9.1 对于给定的12个整数：23，37，7，79，29，43，73，19，31，61，23，47，分别写出用直接插入序、冒泡和直接选择、快速、归并排序的各趟结果。9.2排序可分为_和_两类；衡量排序算法的两个主要性能指标分别是:_、_。9.3假设待排序数据元素序列为 ，应用快速排序方法按递增序排序，得到第一次划分后的结果为_2_3_4_6_5_ 。9.4 排序算法的稳定性是指_相同的纪录经过排序后的_是否发生变化，不发生变化的排序算法，就是_;否则就是_。9.5 排序算法的基本操作是_和_。9.6 排序算法的_取决于关键字的比较和记录的移动等基本操作的次数。9.7排序算法的空间效率取决于算法所占用的_的大小。9.8 下面排序算法的平均时间复杂度最小的是_。A直接插入排序 B简单选择排序 C冒泡排序 D快速排序9.9以下排序方法中，稳定的排序方法是_。A. 直接插入排序和冒泡排序 B. 简单选择排序和归并排序 C. 堆排序和快速排序 D. 冒泡排序和快速排序9.11 一组纪录的关键码为（46，79，56，38，40，84）则利用快速排序的方法，以第一个记录为基准得到一次划分结果为_。 A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84 D. 40，38，46，84，56，799.12快速排序方法在_ 情况下最不利于发挥其长处。 A.要排序得数据量太大 B. 要排序得数据种含有多个相同值C.要排序的数据已基本有序 D. 要排序的数据个数为奇数9.13 已知序列53，87，12，61，98，17，87，27，63，46，画出与该序列对应的完全二叉树；判断该序列是否为堆，如果不是，请调整为大根（顶）堆。914已知序列27，10，14，55，39，19，84，68，11，23，85，画出与该序列对应的完全二叉树；判断该序列是否为堆，如果不是，请调整为大根（顶）堆。915已知序列20，15，4，18，9，6，25，12，3，22，画出与该序列对应的完全二叉树；判断该序列是否为堆，如果不是，请调整为小根（顶）堆。