数据结构习答案.doc

《数据结构习答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、选择题:1-5DAACB6-10CDBDC11-15CCABD16-20ABBDC21-25BCABB26-30CCBAC31-35ACCDB36-40BDBDC41-45CBCCC46-50DBCBA51-55ACCCA56-60ADDBC61-65BCDDB66A71A72D73B74B75-80AABDCC81-85DCCAC86-90DDBDA91-95DBCCA96-100ADDAC101-105BCBAA106-110AABBA111-115AADBA116-120CB118无答案119A120A121-1

2、25DDCCA126-130CCBDA131-135BBCDB136-140BBBCC141-145CDABB146-150DCDBD151-160CBADC156-160DABCD161-165CCDAD166-170DBBCD171-175BCAAC176-180ACBCD181-185DDBCB186-190ABDBA191-195CCDAC196-200BDCBD201-203DAB填空题：1、数据的逻辑结构包括（线性结构）和非线性结构。2、线性结构中元素之间存在着（一对一）关系，树型结构中元素之间存在着（一对

3、多）关系。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、通常元素进栈的顺序是（先移动栈顶指针，然后存

4、入元素）。9、通常元素出栈的顺序是（先取出栈顶元素，然后移动栈顶指针）。10、从一个循环队列中删除一个元素，通常的操作是（先取出元素，然后移动队头指针）。11、向一个循环队列中插入一个元素，通常的操作是（先存放元素，然后移动队尾指针）。K1K2K5K3K4K6K712、设树T的度为4，其中度为1，2，3和4的结点的个数分别为4，2，1，1，则T中叶子结点的个数为（8）。abcdgefhi13、针对线性链表的基本操作有很多，但其中最基本的4种操作分别为（插入）、删除、查找和排序。14、树和二叉树的3个主要差别（）；树中的

5、最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左右之分，而二叉树的结点有左右之分。15、从概念上说，树与二叉树是两种不同的数据结构，通过某种算法将树转化成二叉树的基本目的是（树可采用二叉树的存储结构并利用二叉树的已有的算法解决树的有关问题）。1、深度为k的完全二叉树至少有(2k-1)个结点，至多有（2k-1）个结点，若按自上而下，从左向右的次序编号（从1开始），则编号最小的叶子结点的编号是（2k-1）。2、在一棵二叉树中，叶子结点的个数为n0,度为2的结点的个数为n2,则有n0=（n2+1）。3、结点最少的树

6、为（只有一个结点的树），结点最少的二叉树为（空的二叉树）。4、现有按中序遍历二叉树的结果为abc，问有（5）种不同形态的二叉树可以得到这一遍历结果。5、在n个记录的有序顺序表中进行二分法查找，最大的比较次数是（[log2n]+1）。6、设线性表（a1,a2,……,a500）元素的值由小到大排列，对一个给定的k值用二分法查找线性表，在查找不成功的情况下至多需比较（9）次。7、二分法查找的存储结构公限于（顺序存储结构），且是有序的。8、已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当

7、用二分法查找90时，需进行（2）次查找可确定成功；查找47时，需进行（4）次查找可确定成功；查找100时，需进行（3）次查找可确定不成功；9、在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较（3）次。10、每次从无序子表中取出一个元素，然后把它插入到有序子表中的适当位置，此种排序方法叫做（插入）排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种方法叫做（删除）排序。11、对有n个记录的表r[1……n]

8、进行直接选择排序，所需要进行的关键字间的比较次数为n(n-1)/2。12、在插入和选择排序中，若初始数据基本正序，则选用（插入排序）；若初始数据基本反序，则选用（选择排序）。13、对n个元素的序列进行冒泡排序时，最少的比较次数是（n-1）。14、设二叉树根结点的层次为0，对含有100个结点的二叉树，可能的最大树深和最小树深分别是（