《数据结构》习题
一、单项选择题
1．对矩阵进行压缩存储是为了（ A ）
A．节省存储空间 B．提高运算速度 C．便于运算 D．方便存储 2．链式栈与顺序栈相比，一个比较明显的优点是（ B ） A．插入操作更加方便 B．通常不会出现栈满的情况 C．不会出现栈空的情况 D．删除操作更加方便
3．设输入序列为1，2，3，4，5，则借助一个队列可以得到的输出序列是（ C ）[先进先出] A．3，4，1，2，5 B．1，2，3，4，5 C．2，3，4，1，5 D．5，4，3，2，1 4.一个栈的输入序列是6,5,4,3,2,1,可能的输出序列是（ C ）[先进后出] A．4,3,2,1,5,6 B．3,6,2,1,5,4 C．1,2,3,5,4,6 D．5,4,1,3,2,6 5．设输入序列为A，B，C，D。借助一个栈可以得到的输出序列是（A ） A．A，C，D，B B．C，A，D，B C．D，C，A，B D．D，A，B，C
6．将含100个结点的完全二叉树从根开始，每层从左到右依次对结点编号，根结点的编号为1，则编号为71的结点的双亲结点的编号为（ A ）
A．34 B．35 C．36 D．无法确定 7．已知完全二叉树有80个结点，则该二叉树有 （ B ） 个度为1的结点。 A．0 B．1 C．2 D．不确定 8．任何一个无向连通图的最小生成树（ A ）
A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在
9．设图G用邻接表存储，对该图进行深度优先搜索遍历，则算法的时间复杂度为 （ ） A． O(n) B． O(n+e) C． O(n2) D． O(n3) 10．用n个键值构造一棵二叉排序树，最低高度为（ ）
A．n/2 B．n C．[㏒2n] D．[㏒2n]+1 11．如果以链表作为栈的存储结构，则执行出栈操作时（ ） A．必须判断栈是否满 B．必须判断栈是否空 C．判断栈元素的类型 D．对栈不作任何判断 12．设数组Data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为 （ ） A．front=front+1 B．front=(front+1)%m
C．rear=(rear+1)%m D．front=(front+1)%(m+1) 13．线性表的长度是指（ ）
A．顺序存储方式下数组所占用的元素个数 B．链表存储方式下的结点个数 C．表中的元素个数 D．所能存储的最大的结点个数 14．设有一个无向图G＝(V，E)和G’=(V’，E’)，如果G’是G的生成树，则下面不正确的说法是（ ） A．G’为G的子图 B．G’为G的连通分量
C．G’为G的极小连通子图且V’=V D．G’是G的一个无环子图
15．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（ ）
A．一定都是同义词 B．一定都不是同义词 C．都相同 D．不一定都是同义词
16．在有序表A[20]中按二分查找方法查找A[13]依次比较的元素的下标是（ ） A．9，14，12，13 B．9，15，12，13 C．9，14，11，12，13 D．10，15，12，13 17．栈和队列都是（ ）
A．顺序存储的线性表 B．链式存储的线性表 C．限制的线性表 D．限制存储点的非线性结构 18．向顺序栈中压入新元素时，应当（ ）
A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针
C． 先后次序无关紧要 D．同时进行
19．若树的先序序列和中序序列正好相同，则一定是一棵 （ ） 的二叉树。
A．结点个数可能大于1且该树无左子树 B．结点个数可能大于1且根结点无左孩子 C．结点个数可能大于1且各结点均无左孩子 D．其中任意一个结点的度不为2
20．下列算法中，在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的算法是( )
A．归并排序 B．直接插入排序 C．快速排序 D．冒泡排序
21．当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较元素的次数为 （ ）
A．n2 B．n㏒2n C．㏒2n D．n-1 22．下列排序算法中，在最好情况下，时间复杂度为O(n)的算法是（ ）
A．直接选择排序 B．归并排序 C．快速排序 D．冒泡排序 23．下列排序方法中，排序所花费时间不受数据初始排列特性影响的算法是（ ） A．直接插入排序 B．冒泡排序 C．直接选择排序 D．快速排序
24．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ ）
A．直接选择排序 B．直接插入排序 C．快速排序 D．起泡排序 25．对5个不同的数据元素进行直接插入排序，最多需要进行（ ）次比较。 A．8 B．10 C．15 D．25
26．在一个具有n个结点的双链表中插入一个新结点,则该操作的时间复杂性的量级为（ ） A．O(1) B．O(n) C．O(nlog2n) D．O(n2) 27．二分查找法要求被查找的表是 （ ）
A．顺序表 B．分块有序表 C．顺序表且是按键值递增或递减次序排列 D．不受上述任何限制
28．若某线性表中最常用的操作是在最后一个元素之后插人一个元素和删除第1个元素，则采用（ ）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．仅有尾指针的单循环链表 D．双链表 29．在一个顺序存储的循环队列中，队头指针指向队头元素的（ ）
A．前一个位置 B．后一个位置 C．队头元素位置 D．队尾元素的前一个位置
30．设循环队列用数组A[n]存储，头尾指针为front和rear,求解当前队列中元素个数的公式 ( )
A．rear-front B．front-rear C．n-(front-rear) D．(n+rear-front)％n 31．已知完全二叉树有100个结点，则该完全二叉树共有（ ）个叶子结点。
A． 37 B． 49 C． 50 D．不确定 32．下列存储形式中，（ ）不是树的存储形式。
A．双亲表示法 B．左子女右兄弟表示法 C．广义表表示法 D．顺序表示法 33．在一棵具有5层的满二叉树中结点总数为（ ） A．31 B．32 C．33 D．16 34．设有100个数据元素，采用折半搜索时，最大比较次数为（ ） A．6 B．7 C．8 D．10
35．在顺序存储的线性表(a1,a2,...,an)中,删除任意一个结点时所需移动结点的平均次数为（ ） A．n B．n/2 C．(n-1)/2 D．(n+1)/2 36．下列说法不正确的是（ ）
A．数据元素是数据的基本单位 B．数据项是数据中不可分割的最小标识单位 C．数据可由若干个数据元素构成 D．数据项可由若干个数据元素构成
37．为了方便在线性结构的数据中插入一个数据元素,则其数据结构宜采用（ ）方式 A．顺序存储 B．链式存储 C．索引存储 D．散列存储
38．矩阵A5×6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5][5]的地址为 （ ）
A．1120 B．1125 C．1140 D．1145
39．设矩阵A(aij，0≤i,j≤9)的元素满足：aij≠0 (i≥j,0≤i,j≤9) aij =0 (i A．2384 B．2380 C．2204 D．2200 40．若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ ）。 A．上三解矩阵 B．稀疏矩阵 C．对角矩阵 D．对称矩阵 41．设n阶方阵A是对称矩阵，为节省存储空间,将其下三角(包括对角线)以行序为主序存储在一维数组B[1..n(n+1)/2]中,则对任一上三角元素aij(i A．i(i-1)/2+j B．j(j-1)/2+i C．i(j-1)/2+i D．j(i-1)/2+i 42．对于静态表顺序查找算法，若在表头设置岗哨，则正确的查找方式为（ ） A．从第0个元素往后查找该数据元素 B．从第1个元素往后查找该数据元素 C．从第n个元素开始往前查找该数据元素 D．与查找顺序无关 43．常采用下面几种方式解决散列法中出现的冲突问题（ ） A．数字分析法、除余法、平方取中法 B．数字分析法、除余法、线性探测法 C．数字分析法、线性探测法、多重散列法 D．线性探测法、多重散列法、链地址法 44．若待排序列已基本有序，要使它们完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是（ ） A．归并排序 B．直接插入排序 C．直接选择排序 D．快速排序 45.中序遍历与后序遍历结果相同的二叉树为（ ） A．根节点无左孩子的二叉树 B．根节点无右孩子的二叉树 C．所有结点只有左子树的二叉树 D．所有结点只有右子树的二叉树 46.下列关于广义表的叙述中错误的是（ ） A．广义表是线性表的推广 B．广义表至少有一个元素是子表 C．广义表可以是自身的子表 D．广义表可以是空表 47.用快速排序算法对线性表排序,若选择表中第一个元素作为分界元素,则表中按（ ）分布时排序效率最高. A．已经有序 B．部分有序 C．完全有序 D．逆序 48．若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（ ） A．S1的栈底位置为0，S2的栈底位置为n+1 B．S1的栈底位置为0，S2的栈底位置为n/2 C．S1的栈底位置为1，S2的栈底位置为n D．S1的栈底位置为1，S2的栈底位置为n/2 49．在有n个结点的二叉链表中，值为非空的链域的个数为（ ） A．n-1 B．2n-1 C．n+1 D．2n+1 50．带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（ ） A．第i行非∞的元素之和 B．第i列非∞的元素之和 C．第i行非∞且非0的元素个数 D．第i列非∞且非0的元素个数 51．在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（ ） A．0(n) B．0(log2n) C．0(nlog2n) D．0(n2) 52．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（ ）存储方式节省时间。 A．单链表 B．双链表 C．单循环链表 D．顺序表 53．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ ）遍历实现编号。 A．先序 B．中序 C．后序 D．从根开始的层次遍历 54．下列排序算法中，（ ）算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。 A．堆排序 B．冒泡排序 C．快速排序 D．SHELL排序 55．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为（ ） A．0 B．1 C．2 D．不确定 56．在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移（ ）个元素。 A． n-i B． n-i+1 C． n-i-1 D． i 57．假定一个顺序队列的队首和队尾指针分别为1和r，则判断队空的条件为（ ） A． f+1==r B． r＋1==f C． f==0 D． f==r 58．哈夫曼树的带权路径长度WPL等于（ ） A．除根以外的所有结点的权植之和 B．所有结点权值之和 C．各叶子结点的带权路径长度之和 D．根结点的值 59．一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ） A．{38，46，79，56，40，84} B．{38，79，56，46，40，84} C．{40，38，46，56，79，84} D．{38，46，56，79，40，84} 60．线性链表不具有的特点是（ ） A． 随机访问 B．不必事先估计所需存储空间大小 C． 插入与删除时不必移动元素 D．所需空间与线性表长度成正比 61．设有一个l0阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[n]中，A[0][0]存入B[0]中，则A[8][5]在B[n]中（ ）位置。 A．32 B．33 C．41 D．65 62．设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶子结点，则B中右指针域为空的结点有（ ）个。 A．n-1 B．n C．n+l D．n+2 63．对有14个数据元素的有序表R[0-13]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为( )。 A．R[0]，R[1]，R[2]，R[3] B．R[0]，R[13]，R[2]，R[3] C．R[6]，R[2]，R[4]，R[3] D．R[6]，R[4]，R[2]，R[3] 64.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用( )方式。 A．顺序存储 B．链式存储 C．索引存储 D．散列存储 65.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为( ) A．s->t1->r1=s->t1;s->r1->t1=s->r1; B．s->t1->r1=s->r1;s->r1->t1=s->t1; C．s->r1=s->t1->r1;s->t1=s->r->t1; D．s->t1=s->t1->r1;s->r1=s->r->t1; 66.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( ) A．q->right=s; s->left=q; q->right->left=s; s->right=q->right; B．s->left=q; q->right=s; q->right->left=s; s->right=q->right; C．s->left=q; s->right=q->right; q->right->left=s; q->right=s; D．以上都不对 67.已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-3)，则其转置矩阵的三元组表中第3个三元组为( ) A．(2，1，3) B．(3，1，5) C．(3，2，-1) D．(2，3，-1) 68.顺序查找法与二分查找法对存储结构的要求是( ) A. 顺序查找与二分查找均只适用于顺序表 B．顺序查找只适用于顺序表 C．顺序查找与二分查找既适用于顺序表，也适用于链表 D．二分查找只适用于顺序表 69.程序段for (i=0;i 70.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是 ( ) A．p=p->next; B．p->next=p->next->next; C．p->next=p; D．p=p->next->next; 71.在头指针为head且表长大于1的单循环链表中，若指针p->next->next=head,则( ) A．p指向头结点 B．p指向尾结点 C．*p的直接后继是头结点 D．*P的直接后继是尾结点 72.广义表A=(a,(b),(),(c,d,e))的长度为( ) A．4 B．5 C．6 D．7 73.无向图中一个顶点的度是指图中( ) A．通过该顶点的简单路径数 B．与该顶点相邻接的顶点数 C．通过该顶点的回路数 D．与该顶点连通的顶点数 74.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( ) A．a c e f b d B．a c b d f e C．a c b d e f D．a c d b f e 75.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( ) A．21 B．23 C．41 D．62 76.下面的二叉树中，( )不是完全二叉树。 77.下列说法错误的是( )。 A．一个图的邻接矩阵表示是唯一的 B．一个图的邻接表表示是不唯一的 C．一个图的生成树必为该图的极小连通子图 D．一个无环有向图的拓扑排序序列必唯一 78.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A．5 B．6 C．7 D．8 79.二叉树在线索化后，仍不能有效求解的问题是( ) A．先序线索二叉树中求先序后继 B．中序线索二叉树中求中序后继 C．中序线索二叉树中求中序前趋 D．后序线索二叉树中求后序后继 80.数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )排序算法最节省时间。 A．堆排序 B．希尔排序 C．快速排序 D．直接选择排序 81．若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是( ) A．O(1) B．O(n) C．O(n2) D．O(nlog2n) 82．在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均比较( )个结点。 A．n B．n／2 C．(n-1)／2 D．(n+1)／2 83．研究数据结构就是研究( ) A．数据的逻辑结构 B．数据的存储结构 C．数据的逻辑结构和存储结构 D．数据的逻辑结构、存储结构及其数据在运算上的实现 84．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有( )个结点。 A．13 B．12 C．26 D．25 85.下列四种排序方法中，不稳定的方法是（ ） A．直接插入排序 B．冒泡排序 C．归并排序 D．直接选择排序 86．下列说法中不正确的是( ) A．无向图中的极大连通子图称为连通分量 B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索方法 87．下列说法中不正确的是（ ） A．图的遍历过程中每一顶点仅被访问一次 B．遍历图的基本方法有深度优先搜索和广度优先搜索两种 C．图的深度优先搜索的方法不适用于有向图 D．图的深度优先搜索是一个递归过程 88．对有序表(18，20，25，34，48，62，74，85)用二分查找法查找85，所需的比较次数为( ) A．1次 B．2次 C．3次 D．4次 89．散列表的平均查找长度( ) A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关且与表的长度有关 D．与处理冲突方法无关且与表的长度无关 90.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构 91.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( ) A．4 B．5 C．6 D．7 92.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为( ) A．356 B．358 C．360 D．362 93.下列陈述中正确的是( ) A．二叉树是度为2的有序树 B．二叉树中结点只有一个孩子时无左右之分 C．二叉树中必有度为2的结点 D．二叉树中最多只有两棵子树，并且有左右之分 94.n个顶点的有向完全图中含有向边的数目最多为( ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 95.设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳（ ）个表项。（设搜索成功的平均搜索长度为Snl=(1+1/(1-a))/2,其中a 为装填因子） A．400 B．526 C．624 D．676 96.在有向图中每个顶点的度等于该顶点的（ ） A．入度 B．出度 C．入度与出度之和 D．入度与出度之差 97.一个二叉树按顺序方式存储在一维数组中，如图则结点E在二叉树的第（ ）层。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H I J A．1 B．2 C．3 D．4 98．设某线性链表的头结点指针为L, L->data表示该链表的结点个数，L->next指向该链表的第一个结点，p指向新建立的结点，其类型与L相同。在建立该链表的过程中，若希望L->next始终指向新输入的结点，可采用如下的C语言语句实现：（ ） A. p->next=L->next, L->next=p，L->data++; B. p->next=NULL, L->next=p, L->data++; C. L->data++, L->next=p->next, p->next=L; D.以上都不是。 99.以数组Q[0..m-1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ） A．rear - qulen B．rear - qulen + m C．m - qulen D．1 +（rear + m - qulen）% m 100.设结点x和结点y是二叉树T中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是（ ） A．x是y的左兄弟 B．x是y的右兄弟 C．x是y的祖先 D．x是y的后代 101.对线性表进行二分查找时，要求线性表必须( )。 A．以顺序方式存储 B．以链接方式存储 C．以顺序方式存储，且结点按关键字有序排序 D．以链接方式存储，且结点按关键字有序排序 二、判断题(若正确在( )内打√，否则打×。) ( ) 1．对链表执行插入和删除操作时，不必移动结点。 ( ) 2．双链表中只有一个结点的后继指针为空。 ( ) 3．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。 ( ) 4．线性表的逻辑顺序与物理顺序总是一致的。 ( ) 5．线性表的顺序存储表示优于链式存储表示。 ( ) 6．栈是实现函数调用的必不可少的数据结构。 ( ) 7．线性表的长度是线性表所占用的存储空间的大小。 ( ) 8．在带头结点的单链表中插入元素结点不会改变头指针的值。 ( ) 9．对链队列执行出队操作不会改变尾指针的值。 ( )10．树(或森林)转化为对应的二叉树后，两者的分支数相等。 ( )11．由给定的n个权值所构造的哈夫曼树可能不唯一，其结点个数也可能不确定。 ( )12．图中一个顶点i的出度等于其邻接矩阵中第i列的非0元素个数。 ( )13．二叉树是树的特殊情形。 ( )14．所谓冲突即是两个关键字的值不同的元素，其散列地址相同。 ( )15．二叉树的先序序列和后序序列正好相反。 ( )16．在循环队列中，若尾指针rear大于头指针front，则其元素总数为rear-front ( )17．一个有向图的邻接表和逆邻接表中的结点个数一定相等。 ( )18．在编号的完全二叉树中(根结点的编号为1)，编号为100的结点一定在其左子树中。 ( )19．在索引顺序表的查找中，对索引表的查找既可采用顺序查找法，也可采用二分查找法。 ( )20．对同一组键值的不同顺序的输入序列，所构造的二叉排序树一定不同。 ( )21．稀疏矩阵只能用三元组表压缩存储。 ( )22．在一个大根堆中，关键字最大的两个元素一定在数据表的前三个元素中。 ( )23．线性表采用链表存储后，线性表的长度等于链表中的结点个数 ( )24．双循环链表中，任一结点的前趋指针均指向其逻辑前趋。 ( )25．如果一棵二叉树的中序序列是递增有序序列，则一定是一棵二叉排序树。 ( )26．对一个有序表作二分查找，查找每个元素所需的查找次数均比用顺序查找所需的查找次数要少。 ( )27．对有n个元素的数据表用直接选择排序方法进行排序，最好情况下所需的时间复杂度是O(n)。 ( )28．快速排序算法是所有排序算法中时间复杂度最好的一种排序算法。 ( )29．顺序表用一维数组作为存储结构，因此顺序表是一维数组。 ( )30．通常使用两个类来协同表示单链表，即链表的结点类和链表类。 ( )31．具有n个结点的完全二叉树的高度为[log2(n+1)]。（n>=0，根结点在第0层） ( )32．闭散列法通常比开散列法时间效率更高。 ( )33．已知指针P指向单链表L中的某结点，执行语句P=P->next不会删除该链表中的结点。 ( )34．在链队列中，即使不设置尾指针也能进行入队操作。 ( )35．如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。 ( )36．数据的逻辑结构与数据元素本身的内容和形式无关。 ( )37．从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。 ( )38．由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。 ( )39．数据的基本单位是数据项。 ( )40．带权的无向连通图的最小生成树是唯一的。 ( )41．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。 ( )42．在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应当特殊处理。 ( )43. 线性表采用顺序存储表示时，必须占用一片连续的存储单元。 ( )44. 装载因子是散列表的一个重要参数，它反映了散列表的装满程度。 ( )45．算法和程序没有区别，所以在数据结构中二者是通用的。 ( )46．在顺序表中无需为表示结点间的逻辑关系而增加存储空间。 ( )47．单链表中的头结点就是单链表的第一个结点。 ( )48．队列和栈都是运算受限的线性表。 ( )49．任何一棵二叉树中至少有一个结点的度为2。 ( )50．对于n个记录的集合进行冒泡排序，所需要的平均时间是0(n)。 ( )51．一棵哈夫曼树中不存在度为1的结点。 ( )52．二叉树中的叶子结点就是二叉树中没有左右子树的结点。 ( )53．一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。 ( )54．由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。 ( )55．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 ( )56．一个广义表的表尾总是一个广义表。 ( )57．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序的遍历的时间复杂度为O(h)。 ( )58．数据结构是数据对象与对象中数据元素之间关系的集合。 ( )59．所谓数据的逻辑结构是指数据元素之间的逻辑关系。 ( )60．二维数组是其数组元素为一维数组的线性表，因此它是线性结构。 ( )61．若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。 ( )62．用直接选择排序方法分别对序列S1=（1，2，3，4，5，6）和序列S2=（5，3，2，4，1，6） 进行排序，两者的比 较次数不相同。 ( )63．用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。 ( )64．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整， 直到调整到合适位置为止。 ( )65．同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。 ( )66．若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果的最后 一个结点。 ( )67．如果二叉树中每个结点的值都大于其左孩子结点的值、小于其右孩子结点的值，则可断定它是二叉排序树。 ( )68．在循环队列中，front指向队列中第1个元素的前一位置，rear指向实际的队尾元素，则队列为满的条件是 front==rear。 ( )69．在用线性探测法解决冲突所构造的闭散列表中，每组同义词中至少有一个元素的地址正好等于其散列地址。 ( )70．设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。 ( )71．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是有向完全图。 ( )72．若一个栈的输入序列为123?n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足 ai=n-i+1(i=1,2...,n) 三、填空题 1．双循环链表中，在指针P所指结点前插入指针S所指的结点，应执行下列语句： S－>next＝P；S—>prior＝ ； P－>prior＝S； ； 2．在有n个叶子结点的哈夫曼树中，结点总数是 3．已知完全二叉树的第六层有5个结点，则其叶子结点的个数是 4．栈的特性是 ，队列的特性是 5．有n个顶点的有向图最多有 条弧。 6．在有n个元素的待排序序列已经有序的情况下，用冒泡排序算法进行排序，所作的比较元素的次数为 ， 交换元素的次数为 7．单循环链表L为空的条件是 8．带头结点的双循环链表为空表的条件是 9．设指针r指向单链表的最后一个结点，要在最后一个结点之后插入指针s所指的结点，需执行的三条语句是 ；r=s；r->next=NULL； 10．在单链表中，若要删除指针P所指结点的后继结点，则需执行下列三条语句： U=P－＞next； ；free(U) ； 11．设链队列的队头指针为front，队尾指针为rear，队列为空的条件是 12．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有 个叶子结点。 13．已知一棵二叉树中有10个叶子结点，有15个结点仅有左孩子结点，20个结点仅有右孩子结点，则整个二叉树有 个结点。 14．有n个顶点的连通图的生成树有 条边。 15．设有一个链栈，结点中有data和next两个字段，栈顶指针Ls不空，则结点*S入栈操作的语句为：Ls->next=S； Ls= ； 16．一棵二叉树的先序序列和后序序列正好相反的条件是 17．一棵二叉排序树中若有14个结点的查找长度≤4，则有 个结点的查找长度≤3。 18．在对有12个元素的有序表做二分查找时，有 个结点的查找长度是4。 19．栈可看成是一种运算受限制的线性表,其中可以进行插入和删除的一端称为 20．设链队列1q中结点的格式为data next, 头指针为1q->front，尾指针为 1q->rear,队列为空的条件是 。 21．无向图中的极大连通子图称为该无向图的 22．闭散列表中通常采用 构造后继散列以减少堆积。 23．算法的时间复杂度取决于_ __ 24．设一棵二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG，则二叉树中叶子结点是________ 25．n个顶点的无向连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素. 26．取出广义表A=(x,(a,b,c,d))中原子a的函数是 27．在线性表的单链表达式存储中，若一个元素所在结点的地址为p，则其后继结点的地址为 ，若假定p为一个数组a中的下标，则其后继结点的下标的 。 28．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为 和 。 29．二分查找过程所对应的判定树既是一棵 ，又是一棵 。 30．若长度n=10000的线性表进行二级索引存储：每级索引表中的索引项是下一级20个记录的索引，则一级索引表的长度为 ，二级索引表的长度为 。 31．设数组B[1..4,1..5]中的任一元素均占3个单元，从首地址sb开始把数组B按行优先存储， 则元素B[3,4]的地址为______ _____。 32．在n个结点的线索二叉链表中，有________个线索指针。 33．在对有10个数据的有序表作二分查找时，有___________个结点的查找长度是4。 34．在开散列表上查找键值等于K的结点，首先必须计算该键值的_ ,然后再通过指针查找该结点。 35．对静态表顺序查找算法采用设置岗哨方式与普通的设置循环控制变量相比，进行一次查找所花费的平均时间大约减少__ ___。 36．若要对某二叉排序树进行遍历，保证输出的所有结点键值序列按递增次序排列，应对该二叉树采用______ 遍历法。 37．设需将一组数据按升序排序。在无序区中依次比较相邻两个元素ai和ai+1的值，若ai的值大于ai+1的值，则交换ai和ai+1。如此反复，直到某一趟中没有记录需要交换为止，该排序方法被称为_________。 38．在队列中，允许进行插入操作的一端称为____________，允许进行删除操作的一端称为____________。 39．如图两个栈共享一个向量空间，top1和top分别为指向两个栈顶元素的指针，则“栈满”的判定条件是__ 。 40．如果在排序前，关键字序列已接近正序，则在堆排序和快速排序两者之中，选用________较为适当。 41．通常从四个方面评价算法的质量：_________、_________、_________和_________。 42．在具有n个单元的循环队列中，队满时共有_________个元素。 43．矩阵压缩存储的基本思想是： _的多个元素只分配一个存储空间，_______不分配空间。 44．深度为K的完全二叉树至少有_________个结点，至多有_________个结点。 45．图的主要存储结构有两种，分别为：____ _____ 和 _______ __。 46．直接插入排序需要_________个记录的辅助空间。 47．在插入和选择排序中，若初始数据基本正序，则选用________；若初始数据基本反序，则选用_ _ 48．一棵树采用二叉链表存储，如果树中某结点为叶子结点，则在二叉链表BT中所对应的结点一定是 49．在有n个结点的无向图中，其边数最多为_______。 50．对广义表A=(x,((a,b),c,d))的运算head (head (tail (A)))的结果是______。 51．假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为__ 。 52．判断线索二叉树中某结点指针P所指结点有左孩子的条件是 53．设链栈的栈顶指针为ls，栈不空的条件为 _ 54．遍历图的基本方法有深度优先搜索和广度优先搜索。其中，____________是一个递归过程。 55．对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的_______上继续查找。 56．采用二次探测法解决冲突问题，对于键值为K、容量为m的闭散列表，若散列地址为d0，则发生冲突后，其第三个后继散列地址d3为___________。 57．对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较________次。 58．一棵哈夫曼树有19个结点，则其叶子结点的个数是____________。 59．假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为________。 60．假设一个10阶的下三角矩阵A按列优先顺序压缩存储在一维数组C中，则C数组的大小应为___ _ 61．若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为 _ 62．对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为 63．由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到_ __ ?81?0A???3??00000000064．已知某稀疏矩阵为：，可用三元组的形式表示该稀疏矩阵为： 65．已知某二叉树的叶子结点的个数为10个，度为1的结点个数为8个，则该二叉树的结点总数为 个。具有这种特点的所有二叉树中，其最大深度为： ，其最小深度： 。 66．已知某二叉树先序遍历的结果为：ABDEFGCHIJ，其中序遍历的结果为：DBFGEAHCJI，则其后序遍历的结果为： 。 67．线性表L=（a1，a2，...，an）采用顺序存储，假定在不同的n + 1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是____________。 68．设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即 进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳_____个元素。 69．两个序列：L1={25，57，48，37，92，86，12，33} L2={25，37，33，12，48，57，86，92} 用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列____________。 四、解答下列各题 1．采用直接插入排序算法，对关键字序列（46,32,55,81,65,11,25,43）按从小到大的次序进行排序，写出每趟排序的结果。 2．设待排序序列为{10，18，4，3，6，12，1，9，15，8}，请给出用希尔排序每一趟的结果。增量序列取为5，3，2，1。 3．对数据表(25，50，70，21，4，18，100，43，7，12)采用快速排序算法进行排序，写出每趟的结果。 4．已知序列{15,18,60,41,6,32,83,75,95},请给出采用冒泡排序法对该序列作升序排序时每一趟的结果。 5．对数据列(50，72，31，80，60，20，96，14)写出采用直接选择排序算法排序的每一趟排序的结果。 6．已知二叉树的先序、中序序列分别如下，构造出该二叉树。 先序序列： ABCDEFGHIJK 中序序列： CBEDAHIGFJK 7．已知一棵二叉树的中序序列和后序序列如下，构造出该二叉树。 中序序列：HDIBJEAFCG 后序序列：HIDJEBFGCA 8．已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清。请构造出该二叉树 先序序列： * BC* E* GH 中序序列： C* DA*GHF 后序序列： * DB**FEA 9．已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，构造出该二叉树 0???2?0??0? 先序序列 _BC_EF__ 中序序列 BDE_AG_H 后序序列 _DC_GH_A 10．以{3，4，5，8，12，18，20，30}为叶子结点的权值，构造一棵哈夫曼树，并计算其带权路径长度。 11．求出满足下列条件的所有二叉树。 a．其先序序列为ABCDE。 b．高度为5，而与其对应的树(森林)的高度为4。 12．某二叉树的结点数据采用顺序存储表示如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 E A F D H C G I B (1)试画出此二叉树的图形表示。 (2)写出结点D的双亲结点及左右子女。 (3) 将此二叉树看作森林的二叉树表示，试将它还原为森林。 13．对下面的带权无向图从顶点①开始采用prim算法和kruskal算法构造最小生成树。 14．设散列函数H(K)=K%7，采用拉链法处理冲突，对下面输入序列；要求：构造出该散列表，并求出在等概率情况下成功的平均查找长度。 输入序列：100，90，120，60，78，35，42，31，15，20，22，12，16，24 15．设散列表为HT[17]，待插入关键码序列为{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}，散列函数为H(key)=i/2向下取整，其中i是关键码第一个字母在字母表中的序号，现采用线性探查法解决冲突. 16．设散列表长度为11，散列函数H(K)=K，采用线性探测法处理冲突，若输入序列为(100，90，120，60，78，35，42，31，15)，要求构造出散列表，并求出在等概率情况下查找成功的平均查找长度。 17．设散列表的长度为13，散列函数为H（k）= k，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。 18．已知一组关键字为[70,46,18,25,9,16,65,8,19,34],散列函数为H(K)=K. (1) 分别画出采用线性探测法和链接地址法解决冲突时得到的散列表. (2) 在记录查找概率相同的情况下,分别求出其平均查找长度. 19．已知线性表的关键字集合{87, 25, 310, 08, 27, 132, 68, 95, 187, 123, 70, 63, 47}，已知散列函数为H(k)=k ，采用拉链法处理冲突，设计出该散列表的结构。 20．请画出下图所示的二叉树所对应的树。 21．若只知道上图所示的二叉排序树的各结点的值依次为1-9，则请具体的标出该二叉树各结点的值。 22．一棵二叉树的顺序存储结构为 1 2 3 4 5 0 0 0 0 6 7 (1) 画出该二叉树,并把该二叉树转换为森林; (2) 中序线索该二叉树. 23．已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储在一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34，56，58，63，94时的比较次数。 24．从一棵空的二叉排序树开始，将以下关键码值依次插入：25,13,15,31,7,20,37，请画出插入全部完成后的二叉排序树。 25．从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。 (1)画出该二叉排序树 (2)画出删去该树中元素值为90的结点之后的二叉排序树。 26．假定一棵二叉树的广义表表示为：a（b（d,e），c（f（h，i(j，g）)))；分别写出先根、后根、按层遍历的序列。 27．己知一个带权图的顶点集V和边集E分别为：V={0，1，2，3，4，5，6，7}； E={（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20；则求出该图的最小生成树的权。 28．将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二搜索树中，画出该二叉搜索树。 29．假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。 30．请简述散列函数在散列法存储中的作用。 31．请简述装填因子的定义，为什么说装填因子是散列法存储的一个重要参数？ 32．已知一个图如下所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中，请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd，进行广度优先遍历时得到的顶点序列为acbdfe。 33．已知两个4×5的稀疏矩阵的三元组表分别如下,请画出这两个稀疏矩阵之和的三元组表。 0 1 2 3 1 2 3 4 4 2 4 2 16 18 -25 28 0 1 2 3 4 1 2 2 3 4 1 2 5 4 2 32 -22 69 25 51 34. 求出下图的一棵最小生成树。 35．已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树及对应的二叉树。 下标 data parent 1 2 A 0 B 1 3 4 C D 1 1 5 6 E F 2 2 7 8 G H 3 3 9 10 11 12 13 14 15 I J 4 4 K 5 L 6 M 6 N 7 O 8 36．如图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F能否在栈的输出端得到序列DCFEBA及EDBFCA ? 若能，给出栈操作的过程，若不能，简述其理由。 五、算法设计题 1．编写算法，判断带头结点的单循环链表L中从第3项起的各结点的值是否是其前面两项之差的绝对值。已知链表L的结点数不少于3，且各结点有data和next两个字段。 2．设二叉树采用二叉链表存储，各结点有Lchild、data和Rchild三个字段，设计算法仅打印出其中所有叶子结点的值。 3．设图G用邻接矩阵A[n，n]表示，设计算法判断G是否是无向图。 4．设计算法，将单链表L1复制到单链表L2中(即建立一个和L1有完全相同数据的单链表L2)。 5．已知二叉树t，以二叉链表存储，设计算法求二叉树t中的结点个数。 6．编写完整程序，采用链式存储结构，实现两稀疏矩阵的加法运算。 7．设计算法按递减次序输出二叉排序树中所有结点的值。 8．编写算法，求出单循环链表L中值为最大的结点的指针。已知各结点中有data和next两个字段。 9．设二叉树采用二叉链表存储，其中各结点中有Lhild、data和Rchild三个字段，其中data为整型字段。设计算法打印出值为偶数的结点的值，并要求打印次序满足:每个结点不能比其孩子结点先打印。 10．设计算法将顺序表L的所有元素倒置。 11．设计算法将整型数组A[n]中的元素调整为满足如下条件：其中所有的3的倍数的元素集中在左边，其余元素放在右边。 12．设一棵二叉树以二叉链表为存储结构，结点包含lchild、data和rchild三个字段。设计算法，求出在先序序列中处于第k个位置的结点。 13．设某单链表L的结点包含data和next两个字段，试画出该链表的结构图，并编写算法判断该链表的元素值是否是递增的(假设链表中至少有一个元素)。 14．设计一个非递归的算法以求出二叉树的先序序列的最后一个结点。 15．已知一棵完全二叉树存放于一个一维数组T[n]中，T[n]中存放的是各结点的值。试设计一个算法，从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。 16．设某带头结点的单链表结构说明如下：typedef struct node1{int data;struct node1 * next;}node; 试设计一个算法int count(node *head)计算该单链表中数据域data的值为m的结点个数。设单链表的头指针为head。 17．写出在递增有序表A[1,n]中采用二分查找法查找值为x的元素的非递归算法。 18．设二叉树采用二叉链表表示，data为整数型字段。设计算法判别一棵二叉树是否是二叉排序树。 19．设有两个按升序排列的单链表X和Y，其头指针分别为p,q结点结构说明如下： typedef struct nodel{ int data;struct nodel * next; }node; 试设计一个算法void concat(node *p,*q)将它们合并成一个以p为头指针的单链表Z，使其仍然有序。 20．编写完整程序，采用非递归算法建立二叉树，并求该二叉树的深度。 附：算法设计部分习题解答 第1题算法: #include {node *p=L->next;while(p!=L){cout< while(x!=-1000){s=new node;s->data=x;r->next=s;r=s;cin>>x;}r->next=L; cout<<\已知单链表为：\ if (ok==1)cout<<\单循环链表L中从第3项起的各结点的值均是其前面两项之差的绝对值!\\n\else cout<<\ 第2题算法:struct bitree{char data;bitree * lchild,*rchild;}; void preorder(bitree *t) {if(t){ if((t->lchild==NULL)&&(t->rchild==NULL))cout< void f03(inta[N][N]){inti,j,ok=1;for(i=0;i if(ok==0)cout<<\图G不是无向图\\n\图G是无向图\\n\第4题算法:struct node{int data;node * next;}; node * copyf(node *head){node *L2,*s1=head->next,*s2,*r;L2=new node;r=L2; while(s1){s2=new node;s2->data=s1->data;r->next=s2;r=s2;s1=s1->next;} r->next=NULL;return L2;} 第5题算法:struct bitree{char data;bitree * lchild,*rchild;};int N=0; void countf(bitree *t){if(t){N=N+1;countf(t->lchild);countf(t->rchild);}} 第7题算法:struct bitree{int data;bitree * lchild,*rchild;}; void list(bitree *p){ if(p){ list(p->rchild);cout< cout<<\单循环链表L中值最大的结点的值为：\第9题算法:struct bitree{int data;bitree * lchild,*rchild;}; void found(bitree *t){if(t){ found(t->lchild);found(t->rchild); if((t->data)%2==0)cout< 第10题算法:struct sequenlist{int data[64];int last;};sequenlist L; void fgf(){int i,temp;for(i=0;i<=int(L.last/2);i++) {temp=L.data[i];L.data[i]=L.data[L.last-i];L.data[L.last-i]=temp;} } 第11题算法:#define N 6 int a[N]; void fg3(){int s=0,t=N-1,temp;for(t=N-1;s {while(a[s]%3==0&&s struct bitree{char data;bitree * lchild,*rchild;};int N=0; void dispk(bitree *t){if(t){N=N+1;if(N==K)cout< 第13题算法:struct node{int data;node * next;};node *L=NULL; int qzh(){int k=1;node *p1=L->next,*p2=p1->next; while(p2){if(p2->data void main(){node *r,*s;L=new node;r=L;int x;cin>>x; while(x!=-1000){s=new node;s->data=x;r->next=s;r=s;cin>>x;}r->next=NULL; cout<<\已知单链表为：\ if (ok==1)cout<<\单链表L中的元素值是递增的!\\n\单链表L中的元素值不是递增的!\\n\第14题算法:struct bitree{char data;bitree * lchild,*rchild;}; void dispk(bitree *t) {if(t){bitree *p=t;while(p->rchild!=NULL)p=p->rchild;cout< 第15题算法:#include bitree * Q[MAXSIZE];int T[N]={1,2,3,4,5,6,7,8,9,10};void disp();bitree *creatree(); void main(){bitree *p=creatree();{cout<<\二叉树的结点按层次自左至右分别为：\你建立的二叉树根结点的地址为：\void disp(){int i=0; for(i=0;i<=N;i++)if(Q[i]!=NULL)cout< for(i=0;i rear++;Q[rear]=s;if(rear==1)root=s;else{if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s;else Q[front]->rchild=s; if(rear%2==1)front++;}}return root;} 第16题算法:struct node{int data;node * next;};node *head=NULL; void countm(){int m,n=0;cout<<\请输入欲查找的数值：\cin>>m;node *p=head->next; while(p){if(p->data==m)n++;p=p->next;} cout<<\该单链表中数据域data的值为\的结点个数为：\第17题算法:#include while(low<=high){mid=(low+high)/2;if(A[mid]==x)return mid; if(A[mid]>x)high=mid-1;else low=mid+1;}return -1;} void main(){int i,k,x;for(i=1;i<=N;i++)A[i]=i;cout<<\请输入欲查找的数值：\k=binsearch(x);if(k==-1)cout<<\查无此数！\\n\该数已找到！\\n\第19题算法:#include struct bitree{int data;bitree * lchild,*rchild;};bitree * Q[64]; int A[64],N=0; bitree *creatree(){ bitree *root=NULL,*s;int front=1,rear=0, x;cin>>x; while(x!=-1000){s=NULL; if(x!=0){s=new bitree;s->data=x;s->lchild=NULL;s->rchild=NULL; } rear++;Q[rear]=s;if(rear==1)root=s;else {if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s;else Q[front]->rchild=s; if(rear%2==1)front++;}cin>>x;} return root;} void list(bitree *p) {if(p){ list(p->lchild);cout< {int i,ok=1;for(i=0;i list(t);cout< 第21题算法:#include head=new node;r=head;int temp;cin>>temp; while(temp!=-1000){s=new node;s->data=temp;r->next=s;r=s;cin>>temp;} r->next=NULL;return head;} void disp(node *head)//显示 {node *p=head;while(p->next!=NULL){p=p->next;cout< {node *p=createlist(); if (p==NULL)cout<<\你建立的是一个空链表!\else {cout<<\建立的单链表为：\node *q=createlist(); if (q==NULL)cout<<\你建立的是一个空链表!\else {cout<<\建立的单链表为：\ node *s=q->next;while(s){insert(p,s->data);s=s->next;} cout<<\合并成的新单链表为：\ 第22题算法:#include struct bitree{char data;bitree * lchild,*rchild;};bitree * Q[64]; int N=0; bitree *creatree()//二叉树的建立 { bitree *root=NULL,*s;int front=1,rear=0;char ch;ch=getchar(); while(ch!='#'){N++;s=NULL; if(ch!='@'){s=new bitree;s->data=ch;s->lchild=NULL;s->rchild=NULL;} rear++;Q[rear]=s;if(rear==1)root=s;else {if(s&&Q[front])if(rear%2==0)Q[front]->lchild=s;else Q[front]->rchild=s; if(rear%2==1)front++;} ch=getchar();} return root;} void disp()//二叉树的结点按层次自左至右依次显示 {int i=0;for(i=0;i<64;i++)if(Q[i]!=NULL)cout< {bitree *p=creatree(); {cout<<\二叉树的结点按层次自左至右分别为：\ cout<<\你建立的二叉树的深度为：\