数据结构练习题
一．单选题
1．下面关于线性表的的描述中，错误的是( )
A.线性表采用顺序存储，则存取第i个元素的T(n)=O(1) B.线性表采用单链存储，则存取第i个元素的T(n)=O(1)
C.线性表采用顺序存储，则在第i个前插入一个元素的T(n)=O(n) D.线性表采用单链存储，则在第i个前插入一个元素的T(n)=O(n) 2．顺序表的长度是指( )
A.存储空间数 B.数据元素的个数
C.存储空间数减数据元素的个数 D.存储空间数加数据元素的个数 3．栈和队列是特殊的线性表，其共同特点是( )
A.都是先进后出 B.都是先进先出 C.只允许在一端插入和删除 D.以上都不对 4．具有100个结点的完全二叉树采用顺序存储结构，从根开始自左到到右按找层顺序编号为1—100，则编号为49的结点的左孩子的编号为( )
A.48 B.50 C.98 D.99 5．若某二叉树上的前序为STUWV，中序为UWTVS，则后序为( ) A.UWVTS B.VWUTS C.WUVTS D.WUTSV
6．设m，n为二叉树上的两个结点，在中序遍历时，m在n前的条件是( ) A.m在n的左面 B.m在n的右面 C.m是n的祖先 D.m是n的子孙 7．关于线索二叉树的描述中，错误的是( )
A.线索使得查找中序的前驱方便 B.线索使得查找中序的后继方便 C.线索使得查找前序的后继方便 D.线索使得查找后序的后继方便 8．采用邻接表存储的图的深度优先搜索算法类似于二叉树的( ) A.前序遍历 B.中序遍历 C.后序遍历 D.按层遍历
9．对于一个具有n个顶点e条边的无向图，若采用邻接表表示，则邻接表中的结点总数为( ) A.e/2 B.e C.2e D.n+e 10 一组记录的关键字为（46，79，56，38，40，84），利用快速排序，以第一个关键字为基准得到的一次划分结果为( )
A.38，40，46，56，79，84 B.40，38，46，79，56，84 C.40，38，46，56，79，84 D.40，38，46，84，56，79
11 下面的排序方法中，关键字的比较次数与记录的初始排列次序无关的是( ) A.插入排序 B.选择排序 C.起泡排序 D.希尔排序 12 在待排序的记录基本有序的前提下，效率最高的排序方法是( ) A.插入排序 B.选择排序 C.快速排序 D.归并排序 13 顺序查找适合存储结构为( )的线性表
A.顺序存储或链式存储 B.散列存储 C.索引存储 D.压缩存储
二.填空题
1.在n个结点的顺序表中插入一个结点，表中结点平均移动次数为______________。 2.队列的操作方式是：______________原则。
3.在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算是 ______________和______________操作。
4.二叉树的前序序列和__________________可以唯一确定一棵二叉树。
5.一棵严格的二叉树(无度为1的结点)有999个结点，则该树中有______________
个叶子结点。
6.具有n个结点的二叉链表有______________个空指针域。
7.具有n个顶点的有向图其边数最多是____________个，最少是_____________个。 8.用迪杰斯特拉算法求所有顶点之间的最短路径，其时间复杂度为______________。 9.对n个记录进行起泡排序，最好情况下的比较次数是______________。 10 m阶B树，每个结点至多有______________个孩子结点。
11平均查找长度与结点个数无关的查找方法是____________________。
12根据(35,24,56)建立的二叉排序树，中序遍历的结果是____________________。
三.判断题
1.顺序存储方式只能用于存储线性结构。( )
2.循环队列主要是解决队列中的假溢出问题。( )
3.一般情况下，将递归算法转换为非递归算法将借助栈来完成。( ) 4.一个有向图的邻接表和逆邻接表中的结点数可能不等。( ) 5.n个结点的二叉排序树有多种，其中树高最小的是最佳的。( )
四．应用题
1．拓扑排序算法采用什么样的存储结构较为合适？简述拓扑排序算法的基本步骤。 2．二叉树采用顺序存储结构如下，画出该二叉树。这种存储的优缺点是什么？ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A b c d e F g h i 3．假设用于通信的电文仅由5个字母组成L={a,b,c,d,e}，出现的频率为F={10,20,5,30,35}，试为这5个字母设计哈夫曼编码，并求出平均码长。
4．给定的一组关键字:(32,25,06,68,43,11,28,62,10)写出基数排序各趟的排序结果。
5．对长度为11的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均查找长度ASL。
6．给定的关键字序列为(18,12,5,20,19,22,17)，设散列表的长度为10，散列函数为H(K)=K%7，试画出用拉链法解决冲突时所构造的散列表，并求出在等概率情况下查找成功和查找不成功的平均查找长度ASL。
五．算法题
1．一个递增有序单链表，设计一个算法删除该链表中多余的元素值相同的结点。其结点结构为如下，结构名为linklist。
data next 2．顺序表R[n+1],试设计一个算法，使得在尽可能少的时间内重排记录，将所有关键字小于60的记录放在所有关键字大于等于60的记录之前。
3．二叉树采用二叉链表存储，设计一个算法拷贝一棵给定二叉树。其结点结构为如下，结构名为bitree。
lchild data rchild 数据结构练习题的参考答案
一．单选题
01--05. B B C C C 06—10. A D A C C 11—13. B A A 二．填空题 1．n/2
2．先进先出
3．r->next=s;r=s;
4．中序 5．500 6．n+1
7．n*(n-1),0 8．T(n)=O(n3) 9．n-1 10.m 11.散列 12.24,35,56 三．判断题 1．X 2．V 3．V 4．V 5．V 四．应用题
1．AOV网采用邻接表+入度域存储较为合适。基本步骤： ①从网中选择一个入度为0的顶点且输出之。 ②从网中删掉此顶点及其所有的出边。
③反复执行前两步，直至所有顶点都已输出，拓扑排序完成。否则，网中不存在入度为0的顶点，存在回路，拓扑排序不能进行。 2． a
╱ ╲ b c ╲ ╲ d e ╱ ╲ ╱ ╲ f g h i
优缺点：简单但可能浪费空间，并且插入删除不方便。 3． 100 1 0
35 65 1 0 e
30 35
d 0 1
15 20 1 b 0
5 10
c a a编码：1 1 0 1 b编码：1 1 1 c编码：1 1 0 0 d编码：1 0 e编码：0
平均码长：WPL=0.1*4+0.2*3+0.05*4+0.3*2+0.35*1=2.15 4．32,25,06,68,43,11,28,62,10 箱号 0 1 2 3 4 5 6 7 8 9 一次 10 11 32,62 43 25 06 68,28 二次 06 10,11 25,28 32 43 68 5． 6 ╱ ╲ 3 9 ╱ ╲ ╱ ╲ 1 4 7 10 ╲ ╲ ╲ ╲
2 5 8 11 ASL=(1*1+2*2+3*4+4*4)/11=33/11=3
6．关键字：(18,12,5,20,19,22,17)。散列表的长度为7，散列函数H(K)=K%7。 地址 0
1 ->22 2
3 ->17 4 ->18
5 ->12 ->19 ->5 6 ->20
ASL(成功)=(1+1+1+1+2+3+1)/7=10/7 ASL(不成功)=(0+1+0+1+1+3+1)/7=7/7 五．算法题 1．(8分)
linklist *del(linklist * head) {
linklist *p=head,*q; if (head!=NULL)
while(p->next!=NULL) {
if (p->data!=p->next->data) p=p->next;
else { q=p->next; p->next=q->next; free(q);} }
return head; } 2．
void cpjl(rectype R[]) {
int i=1;j=n; while(i while((r[i].key<=60)&&(i { R[0]=R[i];R[i]=R[j];R[j]=R[0]; } i++;j--; } 3． bitree *copy(bitree *t) { bitree *b; if (t!=NULL) { b=(bitree *)malloc(sizeof(bitree)); b->data=t->data; b->lchild=copy(t->lchild); b->rchild=copy(t->rchild); return (b); } else return NULL; } 《数据结构与算法》练习题 及参考答案 一、 选择题 1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ ）。 A．存储结构 B．逻辑结构 C．顺序存储结构 D．链式存储结构 2．在一个单链表中，若删除ｐ所指结点的直接后继结点，则执行（ ）。 A．p－＞next＝p－＞next－＞next； B．p＝p－＞next；p－＞next＝p－＞next－＞next； C．p－＞next＝p； D．p＝p－＞next－＞next； 3．在ｎ个结点的顺序表中，算法的时间复杂度是Ｏ（1）的操作是（ ）。 A．访问第i个结点（1＜＝i＜＝n）和求第i个结点的直接前趋。 B．在第i个结点后插入一个新结点（1＜＝i＜＝n）。 C．删除第i个结点（1＜＝i＜＝n）。 D．将n个结点从小到大排序。 4．若已知一个栈的入栈序列是1，2，3．．．．．．，n，其输出序列是p1，p2，p3．．．．．．，pn，若p1＝n，则pi为（ ）。 A．i B．n-i C．n-i+1 D．不确定 5．串的长度是指（ ） A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 6. 若广义表A满足Head(A)=Tail(A),则A为（ ） A. ( ) B. (( )) C.(( ),( )) D.(( ),( ),( )) 7．二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行优先存储，元素A[8,5]的起始地址与当A按列优先存储时的元素（ ）的起始地址相同。 A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9] 8．在一棵三叉树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个 A．4 B．5 C．6 D．7 9．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A． 250 B． 500 C．254 D．505 10．n个结点的有向完全图含有边的数目（ ）。 A．n*n B．n（n＋１） C．n／2 D．n*（n－l） 11．用基于邻接表的深度优先搜索遍历算法对含有n个顶点e条边的连通图进行遍历，其时间复杂度为 。 2 A.. O(log2 n) B. O(n) C. O(n) D. O(n + e) E. O(nlog2 n) 12．下面关于m阶B－树说法正确的是( ) ①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字; ③所有叶子在同一层上; ④当插入一个数据项引起B－树结点分裂后，树长高一层。 A． ①②③ B. ②③ C. ②③④ D. ③ 13．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用 查找方法。( ) A. 分块 B.顺序 C. 二分法 D. 基于属性 答：1、C 2、A 3、A 4、B 5、B 6、B 7、B 8、C 9、B 10、B 11、D 12、B 13、A 二、 填空题 1．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为 ,在给定值为x的结点后插入一个新结点的时间复杂度为 。 2. 设循环队列用数组A[m]表示，队头、队尾指针分别是F和T。F指向真正的队列头结点，T指向真正队尾结点的下一个结点，则判定队满的条件为 ，队空的条件为 。 3．设S为一个长度为n的字符串，其中的字符各不相同，则S中互异的非平凡子串（非空且不等于S）本身的个数是 。 4．对矩阵压缩存储是为了______ 。 5．有n 个结点的二叉树进行后序遍历，若在算法中使用栈， 则栈中最多时 有 项。 6．具有n个结点m 棵树的森林中边的个数是 。 7．哈夫曼树中有n个叶结点，则结点总数是 。 8．在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。 9．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______ 趟。 10．高度为6的平衡二叉树的结点数至少有______ 个。 11．如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，比较成功时平均比较次数为______ 。 12．快速排序在最坏情况下的时间复杂度是 。 答：1．(1) O(1) (2) O(n) 2. F=(T+1) % m F=T 3．ｎ×（ｎ＋１）/2－１ 4．节省内存 5.n 6.n-m 7.2n-1 8.n 9. 3 10．20 11．（n＋1）/2 12. O(n2) 三、 判断题 1．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（ ） 2．栈和队列都是线性表，只是在插入和删除时受到了一些限制。（ ） 3．完全二叉树中，若一个结点没有左孩子，则它必是树叶。( ) 4. 设G是n个顶点的无向连通图，若G中每个顶点的度都大于等于2，则G中一定有环。 （ ） 5. 堆排序算法在最坏情况下的时间复杂度是O(nlog2n)。 （ ） 答：1.ⅹ 2. √ 3. √ 4.√ 5. √ 四、应用题 1．线性表有两种存储结构：一是顺序表，二是链表。试问： （1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？ （2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ 2．设一棵二叉树的先序、中序遍历序列分别为 先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。（2分） （2）画出这棵二叉树的后序线索二叉树。 3.给定权集W={2,3,4,7,8,9}，试构造关于W的一棵哈夫曼树，并求出其加权路径长度WPL。 4．设带权连通图G(V,E)的边集为｛（1,2,8），（1,3,10），(1,4,11),(2,3,3), (2,5,13),(3,4,4),(4,5,7)｝。 注：其中的（i,j,w）表示顶点Vi到顶点Vj有边，边权是w。 （1）请画出该图。 （2）请按prim方法求出该图的最小生成树。要求给出过程。 5．设记录的关键字集合K={23，9，39，5，68，12，62，48，33}，给定的增量序列D={4，2，1}，请写出对K按希尔排序时各趟排序结束时的结果。 6．已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。 答：1．（1）应采用链式存储结构，因为采用链式存储结构在进行插入和删除运算时不移动数据元素 只改变指针。 （2）应采用顺序存储结构，因为是随机存取，所以查找效率高。 2．（1）二叉树如下所示： A B C D E F G H (2)后序线索树如下： B的左线索为D；C的右线索为A；D的右线索为B；F的左线索为NULL， 右线索为D；G的左线索为B，右线索为H；H的左线索为G，右线索为 E。 3.对应的哈夫曼树为： 24 0 1 9 15 0 1 0 1 4 5 7 8 0 1 2 3 其加权路径长度WPL=7*2 + 8*2 + 9*2 + 4*3 + 2*4 + 3*4=80 4. (1) v1 v2 13 11 10 v5 37 v3 v4 (2) v1○ v1○ ○v2 v1○ ○v2 v3○ v1○ ○v2 v1○ ○v2 ○v5 v3○ ○v4 v3○ ○v4 8 5．解：排序的各趟结果如下： 第一趟结果：23,9,39,5,68,12,62,48,33 第二趟结果：23,5,33,9,39,12,62,48,68 第三趟结果：5,9,12,25,33,39,48,62,68 6．(1)构造的散列表如下： 下标 0 1 值 231 89 比较次数 1 1 2 79 1 3 25 1 4 47 2 5 16 1 6 38 2 7 82 3 8 51 2 9 39 4 10 11 151 3 (2)查找成功时的平均比较次数为（1+1+1+1+2+1+2+3+2+4+3）/11=21/11 五、 算法设计题 1．已知有两个带头结点的单链表A和B，其头指针分别为Ha和Hb，编写一个函数从单链表A中删除从第i个元素开始的共len个元素，然后将它们插入到单链表B的第j个元素之前。 2．设二叉树以二叉链表为存储结构，试给出判断一棵二叉树是否为完全二叉树的算法。 3．假设有向图以邻接表存储，试编写算法删除弧 第一次作业——第一章、第二章 一．判断题： 1． 数据元素是数据的最小单位。 2． 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。 3． 在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。 4． 顺序存储的线性表可以随机存取。 5． 在单链表中，要访问某个结点，只要知道该结点的指针即可。因此，单链表是一种随机存储结构。 6． 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。 7． 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。 答案：错误 错误 错误 正确 错误 正确 错误 二．填空题： 1．在一个循环单链表中，表尾结点的指针域和头指针的值 。 2．对于双向链表，在两个结点之间插入一个新结点时需修改或建立的指针共有 个，单链表为 个。 3．求顺序表和单链表长度的时间复杂性分别为 和 。 4．在一个不带头结点的单链表中，在表头插入或删除与其他位置插入或删除其操作过程 。 5．在线性表的顺序存储中，元素之间的逻辑关系是通过 决定的；在线性表的链式存储中，元素之间的 逻辑关系是通过 决定的。 6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为 ，在给定值为x 的结点后插入一个新结点的时间复杂度为 。 1．相等 2．4，2 3．O(1)和O(n) 4．不一致 5．物理位置的邻接关系；指针域（或链域） 6．O(1)，O(n) 三．选择题： 1．在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时需向后移动 个元素。 a. n-i b. n-i+1 c. n-i-1 d. i 2．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 。 a. n b. 2n-1 c. 2n d. n-1 3．以下说法正确的是 。 a. 顺序存储方式的优点是存储密度大且插入、删除运算效率高 b. 链表的每个结点中都恰好包含一个指针 c. 线性表的顺序存储结构优于链式存储 d. 顺序存储结构属于静态结构而链式存储结构属于动态结构 4．以下说法错误的是 。 a. 对于循环链表来说，从表中任意结点出发都能通过前后移操作扫描整个循环链表 b. 对于单链表来说，只有从头指针开始才能扫描表中全部结点 c. 双链式的特点是找结点的前趋和后继都很容易 d. 对双链式来说，结点*p的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针 域中 5．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为 。 a．存储结构 b．逻辑结构 c．顺序存储结构 d．链式存储结构 6．在一个单链表中，若删除ｐ所指结点的直接后继结点，则执行 。 a．p－＞next＝p－＞next－＞next； b．p＝p－＞next；p－＞next＝p－＞next－＞next； c．p－＞next＝p； d．p＝p－＞next－＞next； 7．在n个结点的顺序表中，算法的时间复杂度是Ｏ（1）的操作是 。 a．访问第i个结点（1?i?n）和求第i个结点的直接前趋。 b．在第i个结点后插入一个新结点（1?i?n）。 c．删除第i个结点（1?i?n）。 d．将n个结点从小到大排序。 1． b. n-i+1 2． a. n 3． d. 顺序存储结构属于静态结构而链式存储结构属于动态结构 4． a. 对于循环链表来说，从表中任意结点出发都能通过前后移操作扫描整个循环链表 5． c．顺序存储结构 6． a．p－＞next＝p－＞next－＞next； 7． a．访问第i个结点（1?i?n）和求第i个结点的直接前趋。 四．应用题： 1．设在等概率的情况下，对有127个数据元素的顺序表进行插入，平均需要移动多少个元素？ 答：n/2=63.5个 元素。 删除一个元素，又平均需要移动多少个元素？ 答： 11(126?1)?126126(126?125???1?0)????63 127127222．线性表有两种存储结构：一是顺序表，二是链表。试问： ⑴ 如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？ 答：链表。链表。因为：存储规模不能确定，无法静态分配存储空间 ⑵ 若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ 答：顺序表。因为：顺序表是随机存取结构，而且很少做插入和删除操作 五．设计算法题： 1.假定顺序表中有多个零元素，试写出一个算法，将所有的非零元素依次移到顺序表的前端。 2.设计算法，实现统计单链表中具有给定值x的所有元素的个数。 3.设计算法，实现在非递减有序的单链表中删除值相同的多于结点。 答案：1.假定顺序表中有多个零元素，写出一个算法，将所有的非零元素依次移到顺序表的前端。 基本思想：用i从左往右扫描顺序表，找零元素；用j从右往左扫描顺序表，找非零元素；每找到一对零元素与非零元素，都交换它们的位置。重复这个过程，直到i和j“擦肩而过”为止。 算法： //类型定义 typedef int datatype; #define maxsize 1024 typedef {datatype data[maxsize]; int last; }sequenlist; //算法 void quickmove(sequenlist *L) {int i, j; datatype temp; i=0; j=L->last; while( i {while( (L->data[i]!=0) && (i {temp=L->data[i]; L->data[i]=L->data[j]; L->data[j]=temp; } } } 2.设计算法，实现统计单链表中具有给定值x的所有元素的个数。 基本思想：从左往右扫描带头结点的单向链表，每见到一个值为x的元素，都使计数器增1。 算法： //结点类型定义 typedef int datatype; typedef struct node {datatype data; struct node *next; }linklist; //算法 int countx( linklist *head，datatype x ) {int n=0; head=head->next; //跳过头结点 while( head!=NULL ) {if( head->data==x ) n++; head=head->next; } return n; } 3.设计算法，实现在非递减有序的单链表中删除值相同的多于结点。 基本思想：用指针变量head从左往右扫描带头结点的单向链表。对每个当前结点*head，都检查它与后继结点的值是否相等：若相等，则删除后继结点，head不动；否则，移动head。 算法： //结点类型定义 typedef int datatype; typedef struct node {datatype data; struct node *next; }linklist; //算法 void deletedyys( linklist *head) {linklist *p; head=head->next; //指向第一个结点 if( head!=NULL ) {p=head->next; while( p!=NULL ) if( head->data==p->data ) {head->next=p->next; free(p); p=head->next; } else {head=p; p=head->next; } } } 第二次作业——第三章 一．判断题 1． 消除递归不一定需要使用栈。 2． 栈的输入序列为123…n，输出序列，为a1a2?an若ai?n（1?i?n?1，则 。 3． 栈和队列都是线性表，只是在插入和删除时受到了一些限制。 答案：1.正确 2．正确 3．正确 二．填空题 1．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S和X操作串 为 。 2．表达式求值是 应用的一个典型例子。 3．用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是 和 。 4．有n个数顺序（依次）进栈，出栈序列有 种。（答案：卡特兰(Catalan)数Cn?1nn） C2n,其中C2n为组合数。 n?15．设循环队列用数组A[m]表示，队头、队尾指针分别是F和T。F指向真正的队列头结点，T指向真正队尾结点的 下一个结点，则判定队满的条件为 ，队空的条件为 。 答案：1．SXSSXSXX 2．栈 3．O(1)和O(n) 4． 11nnn其中C为组合数（，称） C2C?C22nnnn为卡特兰(Catalan)数。 n?1n?15．(T+1) %m=F，F=T 三．单选题 1．在解决计算机主机与打印机之间速度不匹配问题时通常设置一打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区取出数据打印。该缓冲区应该是一个 结构。 a. 堆栈 b. 队列 c. 数组 d. 线性表 2．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素， 再加入两个元素后，rear和front的值分别为 ？ a. 1和5 b. 2和4 c. 4和2 d. 5和1 3．设栈的输入序列是1234，则 不可能是其出栈序列。 a. 1243 b. 2134 c. 1432 d. 4312 4．设栈S和队列Q的初始状态为空，元素e1e2?e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队 的序列是e2e4e3e6e5e1，则栈S的容量至少应该是 。 a. 6 b. 4 c. 3 d. 2 5．设栈的输入序列是12…n，若输出序列的第一个元素是n，则第i个输出元素是 。 a. 不确定 b. n-i+1 c. i d. n-i 6．假设一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是 。 a. front+1==rear b. front==rear+1 c. front==0 d. front==rear 7．一般情况下，将递归算法转换成等价的非递归算法应该设置 。 a. 堆栈 b. 队列 c. 堆栈或队列 d. 数组 8．若已知一个栈的入栈序列是1，2，3，┅，n，其输出序列是p1,p2,?,pn，若p1?n，则pi为 。 a．i b．n-i c．n-i+1 d．不确定 答案：1．b. 队列 2．b. 2和4 3．d. 4312 4．c. 3 5．b. n-i+1 6．d. front==rear 7．a. 堆栈 8．c．n-i+1 四．算法题 1．编写一个算法，利用栈将一个非负的十进制整数N转换为一个二进制整数。 2．建议：查找其他教科书（如清华严蔚敏的书、北大许卓群的书），了解计算机计算表达式的过程——①利用栈将中缀表达式转换成后缀表达式（或称逆波兰式）；②利用栈计算后缀表达式的值，掌握相应的算法。 答案：1．编写一个算法，利用栈将一个非负的十进制整数N转换为一个二进制整数。 基本思想：十进制整数N化为二进制整数的方法是，首先将N反复除以2，直到整数商为0，然后逆取余。因为“逆取余”正好符合“后进先出”原则，所以用栈保存运算过程中得到的各个余数。 算法（在顺序栈上的实现）： //顺序栈的类型定义 typedef int datatype; #define maxsize 1024 typedef struct {datatype data[maxsize]; int top; }seqstack; //算法 void tran(seqstack *s, int n) {s->top= -1; //置空栈 while( n!=0 ) //当n不为0时反复“除基逆取余” {s->top++; s->data[s->top]=n % 2; //余数进栈 n=n/2; //计算整数商 } } 第三次作业——第四章 一． 判断题 1.串是由有限个字符构成的连续序列，串长度为串中字符的个数。子串是主串中字符构成的有限序列。 2.子串定位函数的时间复杂度在最坏情况下为O(n×m)，因此子串定位函数没有实际使用的价值。 3.设模式串的长度为m，目标串的长度为n。当n?m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价也可能会更为节省。 4.设有两个串P和Q，其中Q是P的子串，把Q在P中首次出现的位置作为子串Q在P中的位置算法称为模式匹配。 答案：错误 错误 正确 正确 二．填空题 1．空格串是指 ，其长度等于 。 2．一个字符串中 称为该串的子串。 3．空串与空格串的区别在于： 。 4．串相等的充分必要条件是 。 5．串的链式存储有两种方法：一种是每个结点只存一个字符，称为 格式；另一种是每个结点存放多个 字符，称为 格式； 答案：1．由若干个空格符组成的串，空格符的个数 2．任意个连续的字符组成的子序列 3．空串是不包含任何字符的、长度为零的串，而空格串是由若干个空格符组成的、长度大于等于1的串。 4．两个串长度相等，而且各个对应位置上的字符也相等。 5．非压缩（或非紧凑），压缩（或紧凑） 三．单选题 1．若串S=＂software＂，其子串数目是 。 a. ８ b. ３７ c. ３６ d. ９ 2．设Ｓ为一个长度为ｎ的字符串，其中的字符各不相同，则Ｓ中互异的非平凡子串（非空且不同于本身）的个数 为 。 a. 2n?1n2nn2n? d. ??1 e. b. n c. 222221．b. ３７ n2n??1 2．d. 22四．算法题 1．S=＂s1s2…sn＂是一个长为ｎ的字符串，采用顺序存储方式，编写一个算法，将Ｓ进行如下改造： ⑴将Ｓ的所有第偶数个字符按照其原来的下标从大到小的次序放在Ｓ的后半部分； ⑵将Ｓ的所有第奇数个字符按照其原来的下标从小到大的次序放在Ｓ的前半部分； 例如：Ｓ＝＂ＡＢＣＤＥＦＧＨＩＪＫＬ＂，则改造后为： Ｓ＝＂ＡＣＥＧＩＫＬＪＨＦＤＢ＂ 2．设计一函数atoi(x)，其中x为字符串，由0，1，…，9十个数字符和表示正负数的“-”组成，返回值为整型数值（即该函数的功能是将字符串转换为十进制整型数）。 答案：1．S=＂s1s2…sn＂是一个长为ｎ的字符串，采用顺序存储方式，编写一个算法，将Ｓ进行如下改造： ⑴将Ｓ的所有第偶数个字符按照其原来的下标从大到小的次序放在Ｓ的后半部分； ⑵将Ｓ的所有第奇数个字符按照其原来的下标从小到大的次序放在Ｓ的前半部分； 例如：Ｓ＝＂ＡＢＣＤＥＦＧＨＩＪＫＬ＂，则改造后为： Ｓ＝＂ＡＣＥＧＩＫＬＪＨＦＤＢ＂ 基本思想：自首至尾扫描字符数组。对偶数位序的字符，将它们逐个入栈保存；对奇数位序的字符，直接前移至适当位置。最后将栈中的字符顺序地置入数组的后面。 算法： //顺序栈的类型定义 typedef int datatype; #define maxsize 1024 typedef struct {datatype data[maxsize]; int top; }seqstack; //算法 void redressal(char *x) {int i, j; seqstack s; s->top=-1; i=0; j=0; while( x[i]!='\\0' ) {x[j++]=x[i++]; if( x[i]!='\\0' ) s.data[++s.top]=x[i++]; } while( s.top>-1 ) x[j++]=s.data[s.top--]; } 2．设计一函数atoi(x)，其中x为字符串，由0，1，…，9十个数字符和表示正负数的“-”组成，返回值为整型数值（即该函数的功能是将字符串转换为十进制整型数）。 基本思想：将取出的数字字符减去字符零（即'0'）的ASCII值，变成数；先前取出的数乘以10加上本次转换的数形成部分中间结果。 算法： long atoi(char x[]) {long num=0; int i=1; if( x[0]!='-' ) num=x[0]-'0'; while( x[i]!='\\0' ) num=10*num+(x[i++]-'0'); if( x[0]=='-' ) return (-num); else return (num); } 五．问答题 S1和S2为串，使strcat(S1,S2)=strcat(S2,S1)成立的所有可能的条件都有哪些？ 答案：所有可能的条件如下： ⑴S1和S2都为空格串； ⑵S1和S2中至少有一个为空串； ⑶S1和S2为相同的串； ⑷若两串长度不等，则长串（假定为S1）由整个短串S2重复多遍组成。 第四次作业——第五章 一．判断题 4． 稀疏矩阵压缩存储后，必会失去随机存取功能。 5． 若一个广义表的表头为空表，则此广义表亦为空表。 6． 广义表是线性表的推广，是一类线性数据结构。 7． 任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。 8． 广义表中原子个数即为广义表的长度。 9． 一个稀疏矩阵Am?n采用三元组形式表示。若把三元组中有关行下标与列下标的值互换，并把m和n的值互换， 则就完成了Am?n的转置运算。 二．填空题 1．设广义表L=(()，())，则Head(L)是 ，Tail(L)是 ，L的长度等于 ，深度 是 。 2．设有一个10阶对称矩阵A采用压缩存储（将其下三角部分以行为主顺序存储，每个元素占4个字节，矩阵元素 的下标从1开始，LOC(a11)=100），则a85的地址为 。 3．设有一个n阶的三对角矩阵A，将带状区域中的元素aij(i?j?1)放到一维数组sa中，则sa的长度大小 为 。元素aij在sa中的位置是 （下标均从0开始计，按行优先顺序）。 4．一维数组的逻辑结构是 ，存储结构是 ；对二维数组或多维数组，它的逻辑结构是 ，其常采用 和 两种不同的顺序存储方式。 5．广义表 ((a))的表头是 ，表尾是 。 6．需要压缩存储的矩阵可分为 矩阵和 矩阵两种。 7．广义表 （（）） 的表头和表尾均是空表（）。 三．单选题 1．稀疏矩阵一般的压缩存储方法有 两种。 a. 二维数组和三维数组 b. 三元组和散列表 c. 三元组和十字链表 d. 散列表和十字链表 2．已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中元素e的运算是 。 a.head(tail(LS)) b. tail(head(LS)) c. head(tail(head(tail(LS)))) d. head(tail(tail(head(LS)))) 3．二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行优先存储， 元素A[8,5]的起始地址与当A按列优先存储时的元素（ ）的起始地址相同。 a. A[8,5] b. A[3,10] c. A[5,8] d. A[0,9] 四．算法题 下三角型方程组的系数矩阵采用行优先顺序压缩存储，设计求解这个方程组的算法。 ?a00?a10 ?????an?1,0a11?an?1,1??x0??b0?????b?x1?????1? ??????????????an?1,n?1??xn?1??bn?1?五．建议题 1．建议同学们试着设计两个稀疏矩阵的加、减和乘法在十字链表上实现的算法，或查找资料阅读这方面的内容。 2．建议同学们了解广义表的存储结构。 第四次作业——第五章 一．判断题 正确 错误 错误 正确 错误 错误 二．填空题 1．（），（（）），2，2 2．228（注：LOC(aij)?LOC(a11)?[i(i?1)?(j?1)]?d 23．3n-2，k=(3i-1)+(j-i+1)=2i+j 4．线性的，顺序的；非线性的，行优先顺序，列优先顺序 5．(a)，() 6．特殊矩阵，稀疏矩阵 7．（（）） 三．单选题 1．c. 三元组和十字链表 2．c. head(tail(head(tail(LS)))) 3．b. A[3,10] 四．算法题 下三角型方程组的系数矩阵采用行优先顺序压缩存储，设计求解这个方程组的算法。 ?a00?a10 ?????an?1,0a11?an?1,1??x0??b0?????b?x1?????1? ??????????????an?1,n?1??xn?1??bn?1?i?1基本思想：求解下三角型方程组的公式为： xi?(bi??aijxj)aii，当aii?0时(i?0,1,?,n?1) j?0元素aij对应于行优先顺序中的sa[k]，且对应关系为 k?i(i?1)2?j（i?j,0?k?n(n?1)2） 算法： #include \ #define N 4 //方程组的阶 #define M N*(N+1)/2 //下三角阵中总元素的个数 int solution(float sa[], float b[], float x[]) {int i, j; for( i=0; i {if( sa[i*(i+1)/2+i]==0 ) //对角线上的元素aii为0，方程组无解 return 0; x[i]=b[i]; for(j=0; j x[i]=x[i]-sa[i*(i+1)/2+j]*x[j]; //i行j列元素aij的引用为sa[i*(i+1)/2+j] x[i]=x[i]/sa[i*(i+1)/2+i]; } return 1; } 下面是供参考的主程序： void main( void ) {float sa[M], b[N], x[N]; int i, j; printf(\以行为主顺序地读入下三角阵中的各元素：\\n\ for(i=0; i printf(\顺序地读入右端项：\\n\ for(i=0; i printf(\要求解的方程组的增广矩阵为：\\n\ for(i=0; i {for(j=0; j<=i; j++) printf(\ for(j=1; j<=(N-i-1)*7; j++) printf(\ printf(\ printf(\ } if( solution(sa, b, x)==1 ) {printf(\方程组的解为：\\n\ for(i=0; i printf(\ } else printf(\方程组无解！\\n\} 第五次作业——第六章 一．判断题 1．存在这样的二叉树，对它采用任何次序的遍历，结果相同。 2．二叉树就是度为2的树。 3．将一棵树转换成二叉树后，根结点没有左子女。 4．一棵树转换成二叉树后，根结点没有右子女。 5．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。 6．哈夫曼(Huffman)树是带权路径长度最短的二叉树，路径上权值较大的结点离根较近。 7．若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结 点。 8． 中序线索二叉树的优点之一是便于在中序下查找前趋结点和后继结点。 9． 先根遍历森林和前序遍历与该森林对应的二叉树其结果不同。 10．后根遍历森林和中序遍历与该森林对应的二叉树其结果不同。 11．完全二叉树的某结点若无左孩子，则它必是叶结点。 12．若有一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个 结点。 13．若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结 果序列的最后一个结点。 14．若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结 果序列的最后一个结点。 15．若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序 列的最后一个结点。 1、正确 2、错误 3、错误 4、正确 5、正确 6、正确 7、正确 8、正确 9、错误 10、错误 11、正确 12、错误 13、错误 14、正确 15、错误 二．填空题 1．8层完全二叉树至少有 个结点，拥有100个结点的完全二叉树的最大层数为 (注：根结点的层数为1，其余结点的层数等于其双亲结点的层数加1)。 2．设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B。已知T1、T2、T3的结点数分别为 n1、n2、n3，则二叉树B的左子树中有 个结点，右子树中有 个结点。 3．对于一棵完全二叉树，设一结点的编号为i，若它的右孩子结点存在，则其编号为 ；若它的双亲结点存在，则其编号为 。 4．对于一棵具有n个结点的二叉树，对应二叉链表中共有2n个指针，其中 个用于指向孩子结点， 个指针空闲着。 5．哈夫曼(Huffman)树是带权路径长度 的二叉树，通常权值较大的结点离根 。 6．对于一棵具有n个结点的树，该树中所有结点的度数之和为 。 7．在一棵二叉树中，假定度数为2的结点有5个，度数为1的结点有6个，则叶子结点有 个。 8．在哈夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对 个字符编码。 9．有n 个结点的二叉树进行后序遍历，若在算法中使用栈， 则栈中最多时 有 项。 10．具有n个结点m 棵树的森林中边的个数是 。 11．哈夫曼树中有n个叶结点，则结点总数是 。 ?i?1、128，7 2、n1-1，n2+n3 3、2i+1，?? 4、n-1，n+1 ?2?5、最短，较近 6、n-1 7、6 8、4 9、n 10、n-m 11、2n-1 三．单选题 1．在n个结点的线索二叉树中，线索的数目为( )。 ⑴ n-1 ⑵ n ⑶ n+1 ⑷ 2n 2．设深度为k(根结点的层数为1，其余结点的层数等于其双亲结点的层数加1)的二叉树上只有度为0和度为2的结点，则这类二叉树上至多含有 ( )个结点。 k ⑴ 2-1 ⑵ 2k ⑶ 2k-1 ⑷ 2k+1 3．设深度为k(根结点的层数为1，其余结点的层数等于其双亲结点的层数加1)的二叉树上只有度为0和度为2的结点，则这类二叉树上至少含有 ( )个结点。 k ⑴ 2-1 ⑵ 2k ⑶ 2k-1 ⑷ 2k+1 4．在一棵具有n个结点的完全二叉数中，分支结点的最大编号为( )。 ⑴ ?(n?1)/2? ⑵ ?(n?1)/2? ⑶ ?n/2? ⑷ ?n/2? 5． 设有13个权值，用它们组成一棵哈夫曼(Huffman)树，则该哈夫曼树共有( )个结点。 ⑴ 13 ⑵ 12 ⑶ 26 ⑷ 25 6．以下说法错误的是( )。 ⑴ 一般在哈夫曼(Huffman)树中，权值越大的叶子离根结点越近 ⑵ 哈夫曼树中没有度数为1的分支结点 ⑶ 若初始森林中共有n棵二叉树，最终求得的哈夫曼树中共有2n-1个结点 ⑷ 若初始森林中共有n棵二叉树，经过2n-1次合并后才能剩下最终的哈夫曼树 7．下面几个符号串编码集合中，不是前缀编码的是( )。 ⑴ {0，10，110，1111} ⑵ {11，10，001，101，0001} ⑶ {00，010，0110，1000} ⑷ {B，C，AA，AC，ABA，ABB，ABC} 8．设F是一树林，B是由F变换得到的二叉树。若F中有n个非终端结点，则B中无右子女的结点有( )个。（答案为⑶） ⑴ n-1 ⑵ n ⑶ n+1 ⑷ n+2 9．设F是一树林，B是由F变换得到的二叉树。若F中有n个终端结点，则B中无左子女的结点有( )个。（答案为⑵） ⑴ n-1 ⑵ n ⑶ n+1 ⑷ n+2 10．在一棵三叉树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个 ⑴ 4 ⑵ 5 ⑶ 6 ⑷ 7 11．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） ⑴ 250 ⑵ 500 ⑶ 501 ⑷ 505 1、3 2、1 3、3 4、4 5、4 6、4 7、2 8、3 9、2 10、3 11、3 四．算法题 1．设计算法：统计一棵二叉树中度为2、度为1和度为0的结点的数目（递归的和非递归的）。 2．设计算法：求一棵二叉树的高度（递归的和非递归的）。 3．设计算法：求一棵二叉树的各结点中的最大元素的值（递归的和非递归的）。 4．设二叉树以二叉链表为存储结构，试给出判断一棵二叉树是否为完全二叉树的算法。 答案： 1．设计算法：统计一棵二叉树中度为2、度为1和度为0的结点的数目（递归的和非递归的）。 ⑴递归算法 //类型定义 typedef int datatype; typedef struct node {datatype data; struct node *lchild, *rchild; }bitree; //求一棵二叉树中各种结点个数的递归算法 void number(bitree *t) {static int n0=0, n1=0, n2=0;//静态局部变量占用的存储单元在函数调用结束后不释放，其值不 消失而被保留。 if( t ) //基于后序遍历实现 {number(t->lchild); number(t->rchild); if( t->lchild && t->rchild ) n2++; else if( t->lchild || t->rchild ) n1++; else n0++; } } ⑵非递归算法 基本思想：采用中序遍历二叉树的非递归算法，只是“访问”为判断当前结点的度等于0、1，还是等于2，并且将相应的计数器增1。 算法： #define MAXSIZE 128 typedef char datatype; /*二叉链表中的结点类型*/ typedef struct tnode {datatype data; struct tnode *lchild,*rchild; }bitree; /*顺序栈的类型*/ typedef struct snode {bitree *data[MAXSIZE]; int top; }seqstack; /*基于中序遍历二叉树的非递归算法*/ void INTRACOUNT(bitree *t, int *n0,int *n1 int *n2) {seqstack s; s.top=-1; /*定义栈并置空*/ while( t||s.top>-1 ) {if( t ) {s.top++; s.data[s.top]=t; /*根指针进栈，去遍历左子树*/ t=t->lchild; } else /*出栈，从左子树返回*/ {t=s.data[s.top]; s.top--; if(t->lchild && t->rchild) /*访问根结点——分情况计数*/ n2++; else if( !t->lchild && !t->rchild) n0++; else n1++; t=t->rchild; /*去遍历右子树*/ } } } 2．设计算法：求一棵二叉树的高度（递归的和非递归的）。 ⑴递归算法 若一棵二叉树为空，则其深度为0，否则其深度等于左子树或右子树的最大深度加1，即有如下递归模型： 若b?NULL;?0 depth(b)??max{depth(b??lchild),depth(b??rchild)}?1其他。?因此，求二叉树深度的递归函数如下： //类型定义 typedef int datatype; typedef struct node {datatype data; struct node *lchild, *rchild; }bitree; //求二叉树深度的递归算法 int depth(bitree *b) {int dep1, dep2; if( !b ) return 0; else //采用后序遍历的思路实现 {dep1=depth(b->lchild); dep2=depth(b->rchild); return ( dep1>dep2 ) ? dep1+1 : dep2+1; } } ⑵非递归算法 基本思想：采用分层遍历二叉树的方法，每遍历完一层计数器均增1。在二叉链表上遍历二叉树要使用队列。 算法： //类型定义 typedef int datatype; typedef struct node {datatype data; struct node *lchild, *rchild; }bitree; #define MAXNUM 32 //求二叉树深度的非递归算法 int HeightorDepth(bitree *root) {int hp,tp,lc,h=0; bitree *que[MAXNUM]; /*存放二叉树结点地址的循环队列*/ if( root ) {hp=0; /*队头指针(前置)，队头元素指向当前搜索结点*/ tp=1; /*队尾指针(指向实元素)*/ lc=1; /*lc指向搜索过程中某一层中最右边结点在队列中的位置*/ que[tp]=root; do {hp=(hp+1) % MAXNUM; root=que[hp]; if(root->lchild) {tp=(tp+1) % MAXNUM; que[tp]=root->lchild; } if(root->rlink) {tp=(tp+1) % MAXNUM; que[tp]=root->rchild; } if(hp==lc) /*当前层遍历完了，高度计数器h增1*/ {h++; lc=tp; /*lc指向下一层中最右边结点在队列中的位置*/ } }while(hp!=tp); /*当hp=tp(即队列为空)时退出循环*/ } return( h ); } 3．设计算法：求一棵二叉树的各结点中的最大元素的值（递归的和非递归的）。 ⑴递归算法 //类型定义 typedef int datatype; typedef struct node {datatype data; struct node *lchild, *rchild; }bitree; //求一棵二叉树各结点中最大元素值的递归算法 datatype maximun(bitree *t) {static datatype max=0;//静态局部变量占用的存储单元在函数调用结束后不释放，其值不消失而 被保留。 datatype k1, k2; if( t ) //采用后序遍历的思路实现 {k1=maximun(t->lchild); k2=maximun(t->rchild); if( k1>max ) max=k1; if( k2>max ) max=k2; if( t->data>max ) max=t->data; } return max; } 或： //类型定义 typedef int datatype; typedef struct node {datatype data; struct node *lchild, *rchild; }bitree; //求一棵二叉树各结点中最大元素值的递归算法 datatype maxvalue (bitree *t, datatype max) {if( t ) //基于前序遍历的实现 {if( t->data>max ) max=t->data; max=maxvalue (t->lchild, max); max=maxvalue (t->rchild, max); } return max; } ⑵非递归算法 基本思想：采用前序遍历二叉树的非递归算法，只是“访问”为判断当前结点的值t->data是否大于当前得到的最大值max，若t->data > max，则用t->data替换max。 算法： #define MAXSIZE 128 typedef char datatype; /*二叉链表中的结点类型*/ typedef struct tnode {datatype data; struct tnode *lchild,*rchild; }bitree; /*基于前序遍历二叉树的非递归算法*/ datatype PRERAMAX(bitree *t) {bitree *st[MAXSIZE]; int top=-1; /*定义顺序栈并置空*/ datatype max=0; /*假设二叉树中存储的元素值均大于0*/ if( t ) {top++; st[top]=t; /*根指针进栈*/ while( top>-1 ) {t=st[top]; /*根结点出栈*/ top--; if( t->data > max ) /*访问根结点——比较*/ max=t->data; if( t->rchild ) /*非空的右子树的根指针进栈*/ {top++; st[top]=t-rchild; } if( t->lchild ) /*非空的左子树的根指针进栈*/ {top++; st[top]=t-lrchild; } t=t->rchild; } } return max; } 4．设二叉树以二叉链表为存储结构，试给出判断一棵二叉树是否为完全二叉树的算法。 方法一 基本思想：先采用分层遍历的方法，将二叉树的二叉链表存储结构转换为顺序存储结构，然后再检查中间 是否有空的结点。 算法： //类型定义 typedef char datatype; typedef struct node {datatype data; struct node *lchild, *rchild; }bitree; #define maxsize 32 //判断二叉树是否为完全二叉树的算法 void tran(bitree *root, datatype sqtree[maxsize]) {int i,rear=0,front=0,level[maxsize]; bitree *que[maxsize]; /*que是存放二叉树结点地址的循环队列*/ for(i=0; i rear=(rear+1) % maxsize; /*队头指针(前置)，队头元素指向当前搜索结点*/ que[rear]=root; /*队尾指针(指向实元素)*/ level[rear]=1; while( front!=rear ) /*队列不空时循环*/ {front=(front+1) % maxsize; root=que[front]; i=level[front]; sqtree[i]=root->data; if(root->lchild) {rear=(rear+1) % maxsize; que[rear]=root->lchild; level[rear]=2*i; } if(root->rlink) {rear=(rear+1) % maxsize; que[rear]=root->rchild; level[rear]=2*i+1; } } } int judge(datatype sqtree[], int n) {int i=0,j; while(sqtree[i]!='') i++; for(j=i+1; j<=n; j++) if(sqtree[j]!='') return 0; //不是完全二叉树 return 1; //是完全二叉树 } 方法二 基本思想：根据完全二叉树的性质，按层次排列二叉树的结点时结点是连续存放的。设一个辅助队列que存放二叉树结点的指针，另设标志变量tag表示按层次逐层从左到右扫描结点过程中是否出现过空结点。 基本步骤：1）若存在根结点，其指针入队。 2）队列不空时循环 ①若队列指针p为NULL，置tag=1； ②若p!=NULL，此时，如果tag=1，则判定为非完全二叉树，算法结束；否则，将其左右子女的指针入队。 3）循环正常结束后，可判定为完全二叉树，结束算法。 算法： //类型定义 typedef char datatype; typedef struct node {datatype data; struct node *lchild, *rchild; }bitree; #define maxsize 32 //判断二叉树是否为完全二叉树的算法 int completeree(bitree *root) {bitree *que[maxsize]; /*que是存放二叉树结点地址的循环队列*/ int rear=0, front=-1, tag=0; que[rear]=root; /*队尾指针(指向实元素)，队头指针(前置)，队头元素指向当前搜索结点*/ while( front!=rear ) /*队列不空时循环*/ {front=(front+1) % maxsize; root=que[front]; if( !rear ) tag=1; else {if( tag ) return 0; else {rear=(rear+1) % maxsize; que[rear]=root->lchild; rear=(rear+1) % maxsize; que[rear]=root->rchild; } } } return 1; } 五．简答题 1．一个树林具有n个结点、k条边 (n>k)，求它所含有的树的个数。 2．已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和 DECBHGFA。画出这棵二叉树。 3．具有n个结点的满二叉树，其叶结点的个数和度为2的结点个数分别是多少？ 答案：1．解：设共有m棵树。因为对于每一棵树，边数都等于结点个数减1，即ei?ni?1，所以有 k??ei??(ni?1)??ni?m?n?m，于是m?n?k。 i?1i?1i?1mmm2．（略） 3．解：方法1 由于满二叉树中没有度为1的结点，则有n?n0?n2，而根据二叉树的性质有n0?n2?1，所以 n0?(n?1)2，n2?(n?1)2。 方法2 由于满二叉树一定是完全二叉树，则根据完全二叉树的性质可知最后一个分支结点的编号为 ?n??(n?1)2 （满二叉树的结点个数为奇数），而满二叉树中没有度为1的结点，所以度为2的结点个数就是???2??n??n?n2?(n?1)2。而且，叶结点有n0?n?n2?(n?1)2（或n0?n??????）。（或：而且，叶结点有 22????n0?n2?1?(n?1)2?1?(n?1)2） 六．应用题 1．设一棵二叉树的先序、中序遍历序列分别为 先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。 （2）画出这棵二叉树的后序线索二叉树。 2．给定权集W={2,3,4,7,8,9}，试构造关于W的一棵哈夫曼树，并求出其加权路径长度WPL、各叶结点的编码。 答案：略 七．建议题 1．建立二叉链表的算法很多，它们依赖于输入二叉树逻辑结构信息的具体形式。常见的算法有： ⑴按完全二叉树的层次顺序，依次输入结点信息建立二叉链表的算法（教材中介绍的算法——非递归的，还有递归的）； ⑵按扩充的二叉树的先序遍历顺序，依次输入结点信息建立二叉链表的算法（设计递归算法较易）； 注：对一个二叉树进行“扩充”，可得到扩充的二叉树。扩充的方法是：把原二叉树的结点都变为度数为2的 分支结点。也就是说，如果原结点的度数为2，则不变，度数为1，则增加一个分支，度数为0即树叶，则增加两个分支。另外请注意，单独根据二叉树的一种遍历序列是不能惟一确定二叉树的，但通过在遍历序列中加适当信息就可惟一地确定二叉树了。这里，将二叉树扩充的目的就是如此。 ⑶由双遍历结果转化二叉树（可由中序遍历结果与前序遍历结果，或者中序遍历结果与后遍历结果惟一地确定一棵二叉树。但是，由前序遍历结果与后序遍历结果不能惟一确定二叉树。）； ⑷由二叉树的广义表表示创建二叉链表； ⑸将树（或森林）的孩子链表表示转换为二叉树的二叉链表表示（教材中有此算法）。 建议同学们试着设计②、③和④的算法，或查找资料阅读一下。 2．遍历二叉树的非递归算法，一般用栈实现，但也可不用栈实现，如有： ⑴采用三叉链表（即带双亲指针的二叉链表，或称三指针表示法）的方法； ⑵采用逆转链的方法； ⑶采用线索链表的方法（教材中给出按中序遍历中序线索二叉树的算法）。 请同学们试着设计遍历二叉树的非递归算法（使用栈的或不使用栈的），或查找资料阅读。希望同学们一定掌握利用栈遍历二叉树的非递归算法。 第六次作业——第七章 一．判断题 1．在n个结点的无向图(这里的图是指无环无重边的单图，其中的环是指顶点到自身的边)中，若边数≥n-1，则该图必是连通图。 2．若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。 3．有回路的有向图不能进行拓扑排序。 4．对于一个有向图，除了拓扑排序方法外，还可以通过对有向图进行深度优先搜索遍历的方法来判断有向图中是否有环存在。 5．若连通图上各边权值均不相同，则该图的最小生成树是惟一的。 6．若连通网络中存在相同权值的边，则它的最小生成树可能不惟一。 7．用邻接矩阵存储一个图时，所占用的存储空间大小只与图中结点的个数有关，而与图的边数无关。 8．用邻接矩阵表示图时，矩阵元素的非零个数与图的边数有关。 9．有n(n≥1)个顶点的有向强连通图最少有n条弧。 10．设G是n个顶点的无向连通图，若G中每个顶点的度都大于等于2，则G中一定有环。 11. 所有的关键活动都提前完成，那么整个工程将会提前完成。 12．任何一个关键活动提前完成，那么整个工程将会提前完成。 13．任何一个关键活动延迟，那么整个工程将会延迟。 14．关键活动不按期完成就会影响整个工程的完成时间。 答案：1．错误 2．正确 3．正确 4．正确 5．正确 6．正确 7．正确 8．正确 9．正确 10．正确 11. 正确 12．错误 13．正确 14．正确 二．填空题 1．图的深度优先搜索遍历类似于树的 遍历，广度优先搜索遍历类似于树的 遍历。 2．一个图的 表示法是惟一的，而 表示法是不惟一的。 3．图的深度优先搜索遍历算法用到的数据结构是 ，广度优先搜索遍历算法用到的数据结构是 。 4．n个顶点的无向完全图共含有 条边，所有顶点的度数和是 。 5．若无向图G 的顶点度数最小值大于等于 时，G至少有一条回路。 6．图中的顶点前趋后继关系的特征是 。 7．一个非连通无向图，共有28条边，则该图至少有 个顶点。 8．在有n个顶点的有向图中，每个顶点的度最大可达 。 9．在有向图的逆邻接表表示中，每个顶点的边链表中链接着该顶点所有 结点。 10. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要 条边。 11．在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。 答案：1．前序，层次2．邻接距阵，邻接表3．栈，队列 4．n(n?1)2，n(n?1) 5．2 6．每个顶点都有多个前趋和多个后继（不限制前趋的个数，亦不限制后继的个数） 7．9 8．2n-2 9．入边（或邻接于的） 10. n-1 11． n 三．单选题 1．关键路径是AOE网(即边表示活动的带权有向图)中( )。 ⑴ 从源点(即开始顶点)到汇点(即完成顶点)的最长路径 ⑵ 从源点到汇点的最短路径 ⑶ 最长的回路 ⑷ 最短的回路 2．下面不正确的说法是( )。 ㈠ 在AOE网中，减小任意一个关键活动上的权值后，整个工期也就相应减小。 ㈡ AOE网工程工期为关键活动上的权之和。 ㈢ 在关键路径上的活动都是关键活动。 ⑴ ㈠ ⑵ ㈡ ⑶ ㈢ ⑷ ㈠、㈡ 3．设无向图的顶点个数为n，则该无向图最多有( )条边。 ⑴ n-1 ⑵ n(n-1)/2 ⑶ n(n-1) ⑷ n(n+1)/2 4．设有向图的顶点个数为n，则该有向图最多有( )条弧。 ⑴ n-1 ⑵ n(n-1)/2 ⑶ n(n-1) ⑷ n(n+1) 5．在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为( )。 ⑴ s ⑵ s-1 ⑶ s+1 ⑷ 2s 6．在一个具有n个顶点的有向图中，若所有顶点的入度之和为s，则所有顶点的出度之和为( )。 ⑴ s ⑵ s-1 ⑶ s+1 ⑷ 2s 7．对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表中该顶点边表中的结点数 为( )。 ⑴ k1 ⑵ k2 ⑶ k1-k2 ⑷ k1+k2 8．对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应逆邻接表中该顶点边表中的结点数为( )。 ⑴ k1 ⑵ k2 ⑶ k1-k2 ⑷ k1+k2 9．一个图中包含有ｋ个连通分量，若按深度优先搜索(DFS)方法访问所有结点，则必须外部调用( )次深度优先遍历算法。 ⑴ k ⑵ 1 ⑶ k-1 ⑷ k+1 10. 判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用( )。 ⑴ 求关键路径的方法 ⑵ 求最短路径的Dijkstra方法 ⑶ 深度优先遍历算法 ⑷ 广度优先遍历算法 11．用基于邻接表的深度优先搜索遍历算法对含有n个顶点e条边的连通图进行遍历，其时间复 杂度为 （ ） 。 ⑴O(nlog2n) ⑵O(n) ⑶O(n2) ⑷ O(n + e) 答案：1．⑴ 从源点(即开始顶点)到汇点(即完成顶点)的最长路径 2．⑷ ㈠、㈡ 3．⑵ n(n-1)/2 4．⑶ n(n-1) 5．⑴ s 6．⑴ s 7．⑵ k2 8．⑴ k1 9．⑴ k 10. ⑶ 深度优先遍历算法 11．⑷ O(n + e) 四．应用题 1．设带权连通图G(V,E)的边集为｛（1,2,8），（1,3,10），(1,4,11),(2,3,3), (2,5,13),(3,4,4),(4,5,7)｝。注：其中的（i,j,w）表示顶点vi和顶点vj有边，边权是w。 ⑴请画出该图。 ⑵请按prim方法求出该图的最小生成树。要求给出过程。 五．算法题 1．设计算法：在无向图的邻接矩阵(或邻接表)表示上实现边的插入与删除。 第七次作业——第八章 一．判断题 1．快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。 2．内部排序的快速排序方法，在任何情况下均可得到最快的排序效果。 3．用希尔(Shell)方法排序时，若关键字的初始顺序杂乱无序，则排序效果就低。 4．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。 5．对一个堆，按二叉树层次进行遍历可以得到一个有序序列。 6．有一小根堆，堆中任意结点的关键字均小于它的左、右孩子关键字。则其具有最大关键字的结点一定是一个叶结点并可能在堆的最后两层中。 7．如果某种排序算法是不稳定的，则该方法没有实际应用价值。 8．归并排序要求的附加空间最多。 9. 堆排序算法在最坏情况下的时间复杂度是O(nlog2n)。 答案：1．错误 2．错误 3．错误 4．正确 5．错误 6．正确 7．错误 8．正确 9．正确 二．填空题 1．每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做 排序；每次从无序子表中挑选出一个关键字最小或最大的元素，把它交换到有序子表的一端，此种排序方法叫做 排序。 2．每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 排序。 3．对n个记录的表R[n]进行简单选择排序，所需进行的关键字间的比较次数为 。 4．对于关键字序列(12,13,11,18,60,15,7,20,25,100)，用筛选法建堆，必须从键值为 的关键字开始。 5．对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较 次(从后往前与有序表中的元素进行比较)。 6．在基于比较的内部排序中，平均比较次数最少的是 ，要求附加存储空间最大的是 ，排序时不稳定的有 、 、 和 。 7．对n个元素进行冒泡排序时，最少的比较次数是 。 8．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟。 9．快速排序在最坏情况下的时间复杂度是 。 答案：1．插入，选择 2．交换，归并 3．n?(n?1) 4．60 5．3 26．快速排序（注：虽然快速排序、堆排序和归并排序的时间复杂度都是O(nlog2n)，但是，快速排 序nlog2n的系数最小，所以快速排序是目前基于比较的内部排序中被认为是最好的方法，特别是，当待排序的关键字是随机分布时，快速排序的平均时间最短）；归并排序；Shell排序，快速排序，直接选择排序，堆排序 7．n-1 8．3 9．O(n2) 三．单选题 1．下列序列不是堆的是( )。 ⑴ 100,85,98,77,80,60,82,40,20,10,66 ⑵ 100,98,85,82,80,77,66,60,40,20,10 ⑶ 10,20,40,60,66,77,80,82,85,98,100 ⑷ 100,85,40,77,80,60,66,98,82,10,20 2．一组记录的关键字的集合为{25,50,15,35,80,85,20,40,36,70}，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为( )。 ⑴ 15,25,35,50,20,40,80,85,36,70 ⑵ 15,25,35,50,80,20,85,40,70,36 ⑶ 15,25,50,35,80,85,20,36,40,70 ⑷ 15,25,35,50,80,20,36,40,70,85 3．一组记录的关键字的集合为{45,80,55,40,42,85}，则利用快速排序方法并以第一个记录为基准得到一次划分结果是( )。 ⑴ 40,42,45,55,80,85 ⑵ 42,40,45,80,55,85 ⑶ 42,40,45,55,80,85 ⑷ 42,40,45,85,55,80 4．若对n个记录进行直接插入排序，则进行第i趟排序过程前，有序表中的记录个数为( )。 ⑴ i ⑵ i+1 ⑶ i-1 ⑷ 不确定 5．在对n个记录进行直接选择排序过程中，第i趟排序需从( )个记录中选择出关键字最小的记录。 ⑴ n-i+1 ⑵ n-i ⑶ i ⑷ i+1 6．在待排序的元素序列基本有序的前提下，效果最高的排序方法是( )。 ⑴ 插入排序 ⑵ 选择排序 ⑶ 快速排序 ⑷ 归并排序 7． 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是( )。 ⑴ n ⑵ 2n-1 ⑶ 2n ⑷ n-1 8．从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置 上的方法，称为( )。 ⑴ 希尔排序 ⑵ 冒泡排序 ⑶ 插入排序 ⑷ 选择排序 9．从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)一端的方法，称为( )。 ⑴ 希尔排序 ⑵ 归并排序 ⑶ 插入排序 ⑷ 选择排序 1．⑷ 100,85,40,77,80,60,66,98,82,10,20 2．⑴ 15,25,35,50,20,40,80,85,36,70 3．⑶ 42,40,45,55,80,85 4．⑴ i 5．⑴ n-i+1 6．⑴ 插入排序 7．⑴ n 8．⑶ 插入排序 9．⑷ 选择排序 四．应用题 1．设记录的关键字集合K={23，9，39，5，68，12，62，48，33}，给定的增量序列D={4，2，1}，请写出对K按希尔排序时各趟排序结束时的结果。 答案：1．解：排序的各趟结果如下： 第一趟结果：23,9,39,5,33,12,62,48,68 第二趟结果：23,5,33,9,39,12,62,48,68 第三趟结果：5,9,12,25,33,39,48,62,68 第八次作业——第九章 一．判断题 1．在二叉排序树中插入一个新结点，它一定成为叶结点。 2．在任意一棵非空的二叉排序树中，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉 排序树相同。 3．用向量(即数组)和单链表表示的有序表均可使用折半查找方法来提高查找效率。 4．若散列表的负载因子?<1，则可避免碰撞的发生。 5．负载因子(装填因子)?是散列表的一个重要参数，它反映散列表的装满程度。 6．有n个数存放在一维数组R中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。 7．二叉排序树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。 8．对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列顺序是一样的。 9．在采用线性探测法处理冲突的散列表中，所有同一词在表中一定相邻。 10．哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法。（注：决定哈希表查找的ASL的因素：⑴选用的哈希函数；⑵选用的处理冲突的方法；⑶哈希表饱和的程度，装载因子??nm值的大小（散列表的平均查找长度是装填因子?的函数）。一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。因此，哈希表的ASL是处理冲突方法和装载因子的函数。） 11．在9阶B_树中，除根以外的任何一个非叶结点中的关键字个数均在5~9之间。 12．理想情况下，在散列表中搜索一个记录的时间复杂度为O(1)。 13．在散列表中，一个可用的散列函数必须保证绝对不产生冲突。 14．AVL树是一棵二叉树，该二叉树上任一结点的平衡因子的绝对值不大于1。 15．虽然关键字序列的顺序不一样，但依次生成的二叉排序树是一样的。 答案：1．正确 2．错误 3．错误 4．错误 5．正确 6．错误 7．正确 8．正确 9．错误 10．错误 11．错误 12．正确 13．错误 14．正确 15．错误 二．填空题 1．已知有序表为(12，18，24，35，47，50，62，83，90，115，134)，当用二分法查找90时，需进行 次查找可确定成功；查找100时，需进行 次查找才能确定失败。 2．分块查找(或索引顺序查找)的过程是：首先在索引表中进行 查找或顺序查找，然后在块中进行 查找。 3．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为 次；当使用监视哨(或哨兵)时，若查找失败，则比较关键字的次数为 次。 4．二分查找要求线性表是 表，并且要用 作为表的存储结构。 5．对二叉排序树进行 遍历就会得到一个所有元素按关键字 的序列。 6．在散列存储中，装填因子?又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则?等于 。 7．二叉排序树的查找效率与二叉树的形态有关，当二叉排序树退化为单分支时，查找算法退化为 n?1查找，其平均查找长度上升为。 28．对于17个元素的有序表R[1..17]作为二分查找，在查找其等于A[8]的元素时，被比较的元素下标依次是 。 9．已知一棵3阶B_树中含有30个关键字，则该树的最小高度为 ，最大高度为 。 10．在向m阶B_树插入记录的过程中，每向一个结点插入一个关键字后，若该结点的关键字个数等于 个，则必须把它分裂为 个结点。 11．在从m阶B_树删除记录的过程中，当从一个结点中删除一个关键字后，该结点所含关键字个数等于 个，并且它的左、右兄弟结点中的关键字个数均等于 ，则必须进行结点合并。 12．在向一棵m阶B_树插入关键字的过程中，若最终引起树根结点的分裂，则新树比原树的高 度 。 13．从一棵m阶B_树删除关键字的过程中，若最终引起树根结点的合并，则新树比原树的高度 。 14．高度为6的平衡二叉树的结点数至少有______个。（公式： Nh?Nh?1?Nh?2?1,h?2,3,?;N0?0,N1?1） 15．如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，查找成功时平均比较次数为______。 答案：1．2；3 2．二分法，顺序 3．n；n+1 4．有序，数组（或向量、顺序表） 5．中序、递增 6．nm 7．顺序 8．9，4，6，7，8 9．4，5 ?m??m?10． m，二 11．???2，???1 12．增1（或高1、大1） 13．减1（或低1、小1） ?2??2?14．20 15．(n?1)2 三．选择题 1．若在线性表中采用折半查找法查找数据元素，该线性表应该( )。 ⑴ 数据元素按关键字有序 ⑵ 采用顺序存储结构 ⑶ 数据元素按关键字有序，且采用顺序存储结构 ⑷ 数据元素按关键字有序，且采用链式存储结构 2．设散列地址空间0～m-1，key为关键字，用p去除key，将余数作为key的散列地址，即h(key)=key % p，为了减少发生冲突(或碰撞)的可能性，一般取p为( )。 ⑴ 小于m的最大奇数 ⑵ 小于m的最大素数 ⑶ 小于m的最大偶数 ⑷ 小于m的任意正整数 3．以下说法错误的是( )。 ⑴ 散列法存储的基本思想是由关键字值决定数据元素的存储地址 ⑵ 散列表的结点中只包含数据元素自身的信息，不包含任何指针 （注：拉链法解决冲突时，散列表被定义为指针数组。） ⑶ 装填因子是散列法的一个重要参数，它反映了散列表的装满程度 ⑷ 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突(或碰撞)的方法 （注：决定哈希表查找的ASL的因素：⑴选用的哈希函数；⑵选用的处理冲突的方法；⑶哈希表饱和的程度，装载因子??nm值的大小（散列表的平均查找长度是装填因子?的函数）。一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。因此，哈希表的ASL是处理冲突方法和装载因子的函数。） 4．有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度(或深度)最小，则应选择下面序列( )输入。 ⑴ 45,24,53,12,37,96,30 ⑵ 37,24,12,30,53,45,96 ⑶ 12,24,30,37,45,53,96 ⑷ 30,24,12,37,45,96,53 5．利用逐点插入法建立序列{50,72,43,85,75,20,35,45,65,30}对应的二叉排序树后，查找数据元素35要进行( )次比较。 ⑴ 4 ⑵ 5 ⑶ 7 ⑷ 10 6．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有( )个结点。（答案：⑴，即为满二叉树） ⑴ 2k?1 ⑵ 2k?1 ⑶ 2k ⑷ 2k?1 7．具有5层结点的AVL树至少有( )个结点。 ⑴ 10 ⑵ 12 ⑶ 15 ⑷ 17 （公式：Nh?Nh?1?Nh?2?1,h?2,3,?;N0?0,N1?1） 8．设有一个用线性探测法处理冲突得到的散列表如图所示： 0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 散列函数为H(k)=k % 11，若要查找元素14，探测的次数是( )。 ⑴ 8 ⑵ 9 ⑶ 7 ⑷ 6 9．设散列表的长度m=14，散列函数为H(k)=k % 11，表中已有4个记录（如图所示），如果用二次探测再散列来处理冲突，则关键字为49的记录其存储地址是( )。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 38 61 84 ⑴ 8 ⑵ 3 ⑶ 5 ⑷ 9 10．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字( )。 ⑴ 一定都是同义词 ⑵ 一定都不是同义词 ⑶ 都相同 ⑷ 不一定都是同义词 11．在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均查找长度ASL=( )。 ⑴ n ⑵ n/2 ⑶ (n-1)/2 ⑷ (n+1)/2 12．下面关于m阶B－树说法正确的是( ) ①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字; ③所有叶子在同一层上; ④当插入一个数据项引起B－树结点分裂后，树长高一层。 ⑴ ①②③ ⑵ ②③ ⑶ ②③④ ⑷ ③ 答案：1．⑶ 2．⑵ 3．⑵ ⑷ 4．⑵ 5．⑴ 6．⑴ 7．⑵ 8．⑷ 9．⑷ 10．⑷ 11．⑷ 12．⑵ 四．应用题 1．已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度及查找失败时的平均查找长度。 答案：1．(1)建立散列表如下： 散列地址 0 1 关键字 231 89 比较次数 1 1 2 79 1 3 25 1 4 47 2 5 16 1 6 38 2 7 82 3 8 51 2 9 39 4 10 11 151 3 (2)查找成功时的平均比较次数为（1+1+1+1+2+1+2+3+2+4+3）/11=21/11 查找失败时的平均比较次数为（12+11+10+9+8+7+6+5+4+3+2）/11=77/11
数据结构练习题 - 图文
