数据结构习题答案.doc

选择题:1-5 DAACB 6-10 CDBDC 11-15 CCABD 16-20 ABBDC 21-25 BCABB26-30 CCBAC 31-35 ACCDB 36-40BDBDC 41-45CBCCC 46-50 DBCBA51-55 ACCCA 56-60ADDBC 61-65BCDDB 66A 71A 72D 73B 74B75-80 AABDCC 81-85DCCAC 86-90DDBDA 91-95DBCCA 96-100 ADDAC 101-105BCBAA 106-110 AABBA 111-115 AADBA116-120 CB118无答案 119A 120 A 121-125DDCCA 126-130 CCBDA131-135BBCDB 136-140 BBBCC 141-145CDABB 146-150DCDBD151-160CBADC 156-160DABCD 161-165CCDAD 166-170DBBCD171-175BCAAC 176-180ACBCD 181-185DDBCB 186-190ABDBA191-195CCDAC 196-200BDCBD 201-203DAB填空题：1、 数据的逻辑结构包括（线性结构）和非线性结构。2、 线性结构中元素之间存在着（一对一 ）关系，树型结构中元素之间存在着（ 一对多）关系。3、 在单链表中设置头结点的作用是（简化插入、删除算法 ）。4、 访问单链表中的结点，必须沿着（指针域 ）依次进行。5、 在双向链表中，每个结点有两个指针域，一个指向（ 前驱结点），另一个指向（ 后继结点）。6、 在一个单链表中的p所指向结点之前插入一个s所指的结点时，可以执行如下操作：（1）s-next= p-next ;（2）p-next=s;（3）t=p-data;（4）p-data= s-data ;（5）s-data= t ;7、 栈和队列的区别在于（删除运算不同 ）。8、 通常元素进栈的顺序是（先移动栈顶指针，然后存入元素 ）。9、 通常元素出栈的顺序是（ 先取出栈顶元素，然后移动栈顶指针 ）。10、 从一个循环队列中删除一个元素，通常的操作是（ 先取出元素，然后移动队头指针 ）。11、 向一个循环队列中插入一个元素，通常的操作是（先存放元素，然后移动队尾指针 ）。K1K2K5K3K4K6K712、 设树T的度为4，其中度为1，2，3和4的结点的个数分别为4，2，1，1，则T中叶子结点的个数为（8 ）。abcdgefhi13、 针对线性链表的基本操作有很多，但其中最基本的4种操作分别为（插入 ）、删除、查找和排序。14、 树和二叉树的3个主要差别（ ）；树中的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左右之分，而二叉树的结点有左右之分。15、 从概念上说，树与二叉树是两种不同的数据结构，通过某种算法将树转化成二叉树的基本目的是（ 树可采用二叉树的存储结构并利用二叉树的已有的算法 解决树的有关问题 ）。16、 深度为k的完全二叉树至少有( 2k-1 )个结点，至多有（2k-1 ）个结点，若按自上而下，从左向右的次序编号（从1开始），则编号最小的叶子结点的编号是（ 2k-1 ）。17、 在一棵二叉树中，叶子结点的个数为n0,度为2的结点的个数为n2,则有 n0=（ n2+1 ）。18、 结点最少的树为（只有一个结点的树 ），结点最少的二叉树为（ 空的二叉树 ）。19、 现有按中序遍历二叉树的结果为abc，问有（ 5 ）种不同形态的二叉树可以得到这一遍历结果。20、 在n个记录的有序顺序表中进行二分法查找，最大的比较次数是（ log2n+1 ）。21、 设线性表（a1,a2,a500）元素的值由小到大排列，对一个给定的k值用二分法查找线性表，在查找不成功的情况下至多需比较（9 ）次。22、 二分法查找的存储结构公限于（ 顺序存储结构 ），且是有序的。23、 已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用二分法查找90时，需进行（ 2 ）次查找可确定成功；查找47时，需进行（ 4 ）次查找可确定成功；查找100时，需进行（ 3 ）次查找可确定不成功；24、 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较（ 3 ）次。25、 每次从无序子表中取出一个元素，然后把它插入到有序子表中的适当位置，此种排序方法叫做（ 插入 ）排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种方法叫做（ 删除 ）排序。26、 对有n个记录的表r1n进行直接选择排序，所需要进行的关键字间的比较次数为 n(n-1)/2 。27、 在插入和选择排序中，若初始数据基本正序，则选用（ 插入排序 ）；若初始数据基本反序，则选用（ 选择排序 ）。28、 对n个元素的序列进行冒泡排序时，最少的比较次数是（ n-1 ）。29、 设二叉树根结点的层次为0，对含有100个结点的二叉树，可能的最大树深和最小树深分别是（99 ）和（ 6）。30、 数据的基本单位是（ 数据元素 ）。31、 数据结构研究的主要内容包括（ 数据存储结构 ）、（ 数据逻辑结构 ）、数据元素之间的联系三方面。32、 从逻辑结构上讲，数据结构主要分为两大类，它们是（ 线性数据结构 ）和（ 非线性数据结构 ）。33、 一个数据结构在计算机中的表示（映象）称为 数据的存储结构 。34、 数据的逻辑结构被分为（ 集合 ）、线性结构、树型结构和图形结构四种。35、 数据的存储结构主要分为（ 顺序存储结构 ）和（ 链式存储结构 ）。36、 在线性结构和树型结构中，前驱结点和后继结点之间分别存在着（ 一对一 ）和（ 一对多 ）的联系 。37、 算法的5个重要特性是：输入、输出、可行性、确定性和（ 有穷性 ）。38、 算法的复杂度分为（ 时间复杂度 ）和（ 空间复杂度 ）两 种。39、 若一个算法中的语句频度之和为T(n)=4nlog2n,则算法的时间复杂度为 O(log2n) 。40、 逻辑结构通常可以用一个二元组B=(K,R)来表示，其中K表示（ 有限个结点所构成的集合 ），R表示（ K上的关系的有限集合 ）。41、 线性表中（ 数据元素的个数 ）称为表的长度。42、 如果向一个长度为n的顺序表中的第I个元素（1=I=n）之前插入一个元素，需向后移动（ n- I +1 ）个元素。43、 在一个长度为n的顺序表中删除表中的第I个元素（1=I=n）时，需向前移动（ n- I ）个元素。44、 栈又称为（ 后进先出 ）表，队列又称为（ 先进先出 ）表。45、 栈中元素的进出原则是（ 后进先出 ）。46、 队列中元素的进出原则是（ 先进先出 ）。47、 一个栈的输入序列是12345，则栈的输出序列43512是（ 不可能的 ）。48、 从循环队列中删除一个元素时，通常的操作是（ 先取出元素，然后移动队头指针 ）。49、 向循环队列中插入一个元素时，通常的操作是（ 先存放元素，然后移动队尾指针 ）。50、 在单链表中，要删除某一指定的结点，必须找到该结点的（前驱结点 ）。51、 在非循环的（双向 ）链表中，可以用表尾指针代替表头指针。52、 在线性表的单链接存储结构中，每个结点都包含有两个域，一个域叫做（数据 ）域，另一个叫做（ 指针 ）域。53、 在线性表的链式存储结构中，我们通常讲的头指针与头结点的根本区别是：头结点是加在线性表的（ 第一个 ）元素所在结点之前的一个附设结点，而头指针是链表中第一个结点的地址变量；头结点与首元素结点的关系是若有头结点的单链表不为空，则头结点的指针域的值就是首元素结点的地址。54、 针对线性表的基本操作有很多，但其中最基本的四种操作分别为插入、删除、查找和（排序 ）操作。55、 线性表的顺序存储结构是通过（ 数组下标 ）来直接反映数据元素之间的逻辑关系，而链式存储结构是通过（ 结点指针 ）来间接反映数据元素之间的逻辑关系。56、 若对线性表进行的操作主要不是插入和删除，则该线性表宜采用（ 顺序 ）存储结构；若频繁地对线性表进行插入和删除操作，则该线性表宜采用（ 链式 ）存储结构。57、 顺序表中逻辑上相邻的元素的物理位置（一定 ）紧邻。单链表中逻辑上相邻的元素的物理位置（ 不一定 ）相邻。58、 线性表的链式存储结构主要包括单链表、（ 双向链表）和( 循环链表 )三种形式。59、 循环单链表与非循环单链表的主要不同是循环单链表的尾结点指针（指向链表头结点 ），而非循环单链表的尾结点指针（ 指向空 ）。60、 若已知一个栈的入栈顺序是1，2，3，n，其输出序列为p1,p2,p3,pn,若p1=n，则pi(1Inext ）；若假定p为一个数组a中的下标，则其直接后继结点的下标为（ p+1 ）。63、 当用长度为N的数组顺序存储一个栈时，假定用top=N表示栈空，则表示栈满的条件为（ top=0 ）。64、 在用一维数组AN存储一个顺序循环队列时，若队列的首、尾指针分别用f和r表示，则队列长度为 (r-f+N) mod N 。65、 假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为（ b,c,e,d,a ）。66、 对于一个长度 为n的顺序存储的表 ，在表头插入元素的时间复杂度为 （ O(n) ），在表尾插入元素的时间复杂度为（O(1) ）。67、 在一个有头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为 head= p-next-next 。68、 用数组A1N顺序存储完全二叉树的各结点，则当I=(n-1)/2时，结点AI的右子女是结点（ A2i+1 ）。69、 线性表的逻辑顺序与存储顺序总是一致的，这种说法是 错误 的（填正确或错误）。70、 每种数据结构都具备3个基本操作：插入、删除、和查找，这种说法是 错误 的。（填正确或错误）71、 数据结构是相互之间存在一种 或多种 特定关系的数据元素的集合，它包括3方面的内容，分别是逻辑结构、（ 物理结构 ）和算法。72、 一棵n个结点的完全二叉树从根结点这一层开始，每一层上的结点按从左到右的顺序存储在数组A1n中，设某个结点在数组中的位置为I (1=I=n)，则它的父结点的位置是（ i/2 ）。73、 线性表L=（a1,a2,an）用一维数组表示，假定删除线性表中任一元素的概率相同（都为1/n），则删除一个元素平均需要移动元素的个数是（n-1）/2。74、 若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数 为K，则左、右子树皆非空的结点个数是（ k-1 ）。75、 在树中，一个结点的直接子结点的个数称为该结点的（ 度 ）。76、 设二叉树的深度为h,且只有度为0 和2的结点，则此二叉树中所含结点数至多为（ 2h*1 ）。77、 如果对于给定的一组权值，所构造出的二叉树的带权路径长度最小，则该树称为（ 哈夫曼树 ）。78、 设根结点的层次为1，则深度为k的二叉树的总结点数为（ 2k*1 ）。79、 顺序输入的数列25，30，8，1，27，24，26，10，21，9，28，7，13，15，假定每个结点的查找概率相同，若用顺序存储方式 组织该数列，则查找一个数成功的平均比较次数为（ 8 ）。若按二叉排序树结构组织该数列，则查找一个数成功的平均比较次数为（ 57/15 ）。80、 对n个记录的序列快速排序，所需辅助存储空间为 O(log2n) ,算法的时间复杂度为 O(nlog2n) 。81、 二分法查找方法仅适合于这样的表，表中的记录必须是（ 关键字有序 ），其存储结构必须是（ 顺序存储结构 ）。82、 每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种子排序方法叫做（ 插入 ）排序；每次从无序子表中选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做（ 选择 ）排序。83、 每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做（快速 ）排序。84、 快速排序算法在平均情况下的时间复杂性为 O(nlog2n) ，在最坏情况下的时间复杂性为 O(n2) 。85、 快速排序算法在平均情况下的空间复杂性为 O(log2n) ，在最坏情况下的空间复杂性为 O(n) 。86、 假定一组记录为（46，79，56，38，40，84），在冒泡排序的过程中进行第一趟排序后的结果为（ 46，56，38，40，79，84 ）。87、 已知关键字序列（51，28，86，70，90，7，30），用冒泡法排序对该序列进行排序，三