数据结构精选考研试题

[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[20分] 1、 算法的定义和性质

2、 为什么说数组与广义表是线性表的推广？ 3、 什么是结构化程序设计？

4、 哈希方法的基本思想

5、 给出一不稳定排序方法名称与实例

二、 构造结果：[24分]

（1） 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do

for j:=1 to I do

for k:=1 to j do x:=x+1

（2） 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。

（3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．

（4） 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．

（5） 在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec），H(x)=[i/2] ，其中i为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。

（6） 构造有7个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。 三、 写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。[15分]

四、 编写一非递归算法，对一棵二叉排序树实现中序遍历。[15分]

五、 编写程序，完成下列功能：[15分]

1． 读入整数序列，以整数0作为序列的结束标志（0不作为序列元素），建立一个单链表。 2． 实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，可使用临时工作单元。

例：输入序列为：1，8，4，3，0

六、 给出有向图G的邻接表表示。找出其一棵最小生成树。[11分]

[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[20分] 1、 算法的定义和性质

2、 为什么说数组与广义表是线性表的推广？ 3、 什么是结构化程序设计？

4、 哈希方法的基本思想

5、 给出一不稳定排序方法名称与实例

二、 构造结果：[24分]

（1） 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do

for j:=1 to I do

for k:=1 to j do x:=x+1

（2） 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。

（3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．

（4） 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．

（5） 在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec），H(x)=[i/2] ，其中i为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。

（6） 构造有7个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。 三、 写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。[15分]

四、 编写一非递归算法，对一棵二叉排序树实现中序遍历。[15分]

五、 编写程序，完成下列功能：[15分]

1． 读入整数序列，以整数0作为序列的结束标志（0不作为序列元素），建立一个单链表。 2． 实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，可使用临时工作单元。

例：输入序列为：1，8，4，3，0

六、 给出有向图G的邻接表表示。找出其一棵最小生成树。[11分]

[注] 编写程序可选用PASCAL 或 C 语言

算法描述采用类语言，应加上必要的注释 所有答案均要求写在答题纸上

一、 回答问题 [15分]

1．结构化程序设计

2．面向对象开发方法与面向过程开发方法的不同之处 3．数据类型含义与作用 4．稳定排序与不稳定排序

二、简述方法与原因 [20分]

1．分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递增序列的表按递增顺序排序，给出最省时间与最费时间的算法名称，简述原因。

2．实现有向图的拓扑排序能否用图的深度搜索模式来查找？若能请简述方法，若不能，请简述原因。

3.有n个非零的数，仅要求将负数排列在正数的前面，但并不要求对其排序，简述处理方法。

4．说明在图的遍历中，设置访问标志数组的作用。

5.在一个连通无向图上，欲求从一点VI到另一点VJ（VI≠VJ）所经结点数目最少的路径，在深度优先搜索、广度优先搜索、从一点到其余各顶点的最短路径或图的其它算法中，你认为最好选择那种方法为基础，简述原因。

三、构造结果 [25分]

1. 二叉树按二叉链表方式存放，其中的data域为char类型，已

有按前序方式构造二叉树的算法，若输入序列为AB□CD□□ED□G□□□，请给出构造的相应二叉树。

2.已知Ackerman函数定义如下：

n+1 当m=0时

akm(m,n) = akm(m-1,1) 当m≠0,n=0时

akm(m-1, akm(m,n-1)) 当m≠0,n≠0时

写出akm(2,1)时调用时变化过程与执行结果。

3. 对于正整数A、B，说明下面程序段定义了什么函数功能，要求重写程序段，使之完成原函数功能，且执行时间仅可能短。 Unsigned int f(a,b) int a,b;

{if (a*b==0) return (a+b)

else return(f(b-(b/a)*a,a); (注：b/a相当整除) }

4. 写出在中序线索树BT中找结点X的后继结点的函数过程。

5.对以下关键字序列建立哈希表（jan,feb,mar,apr,may,jun,jul），哈希函数为H（K）=关键字中第一个字母在字母表中的序号）MOD 7，用线性探测再散列法或链地址法之一处理冲突，要求构造一个装填因子为0.7的哈希表，并求出等概率情况下查找成功与不成功的平均查找长度。

四、有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲

得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。[10分]

1． 一棵树采用孩子-兄弟方式存放，结点结构为

fch dansleta ib vel

其中fch 表示指向第一个孩子，nisib表示指向下一个兄弟, level表示结点层次。

设根结点层次为1，其它以此类推，编写一算法，将树中所有结点层次值置入相应level域。[10分]

六、以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重

复子串及其位置并分析算法的时间复杂度. [10分]

七、 编写程序，要求完成：

建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。

在此链表上实现对二进制数加1的运算，并输出运算结果。

分]

[10[注]：编写程序可用PASCAL或C语言；算法描述可采用类语言，加上必要注释； 一、解释和简答下列问题：（20分）

1） 算法的定义和特性 2） 抽象数据类型

3） 广义表与字符串属于线性表的理由

4） 封装

5） 排序算法的稳定性 6） 结构化程序设计 二、写出要求结果：（30分）

1．已知一二叉树中序序列为DBGEAFC，后序序列为DGEBFCA，给出其对应的二叉树。 2．给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。

1． 有一线性表，要求重新排列，使所有的正数均在非正数之前，要求用最小交换次数

实现，你认为应采用什么方法？

4．只想得到N个元素序列中第K个最大元素之前的部分递减有序序列（K<

5．在地址空间为0~12的散列区中，对以下关键字序列建哈希表：（Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct）。用线性探测法处理冲突，求出在等概率的情况下查找成功与不成功的平均查找长度。

6．下面给出求N价hanoi塔的过程：

PROCEDURE hanoi(n：integer；x,y,z：char)；

begin

if n=1 then move(x,1,z) else [hanoi(n-1,x,z,y)；

move(x,n,z)；

hanoi(n-1,y,x,z)] end

请写出执行hanoi(3,a,b,c)时递归过程的实在参量变化过程及move的搬动过程。

三、数学归纳法证明非空满K叉树的叶子结点数目为(K-1)N+1，其中N为分支结点数目。

（10分） 四、编写程序，判断一带头结点的双向链表是否对称，对称是指表中各元素满足ai=an-i+1 结点结构为如下：(10分) next dada prior

五、有一个由英文书目构成的文件（书名不定长度，以“；”为分割符）；读入该文件，对这一书目单按字典排序，将结果以文件方式存储。编程实现之。（10分）

六、二叉树按链表方式存放，且树中结点的关键字均不同。写一个判别给定二叉树是否为

二叉排序树的非递归算法。（10分）

写一个算法，确定一个N个顶点的无向图是否包含回路，此算法的时间代价应为O（N） （10分）

[注]：编写程序可选用盘Pascal 或C语言，算法描述可选用类语言，必要时加上注释

一、简答下列问题：

1． 结构化程序设计

2． 参数传递的常用方式及含义

3． 数据类型

4． 几种基本数据结构的名称及特征 5． 算法定义与性质 6． 二、写出要求结果

1． PROGRAM PF(OUTPUT);

VER T,M:INTEGER;

FUNCTION F(N:INTEGER):INTEGER; BEGIN M:=N+M;F:=M END

BEGIN

M:=10;T:=(M+1)*F(10);WRITELN(T); M:=10;T:=F(10)*(M+1); WRITELN(T); M:=10;T:=M*F(10)+F(10); WRITELN(T);

END.

写出程序输出结果，说明为什么T的树出结果不同。

2． 有过程定义如下：

PROCEDURE PRIT(N:INTEGER); BEGIN

VAR N1:INTEGER;

N1:=TRUNC(N/10);{TRUNC(x)表示取x的整数部分} S:=S*10+(N MOD 10);

IF N1<>0 THEN PRIT(N1); WRITELN(N MOD 10)

END;

问：置S初值为0，用PRIT（12345）调用此过程，写出打印结果；当执行完此次调用后，S值是多少？

3． 给定一组权值（7，18，3，32，5，26，12，8），构造

一棵哈夫曼树，并计算带权路径长度。

4． 将树转换成二叉树

5． 对给定以下关键字序列（Jan,Feb,Mar,Apr,May,

Jun,Jul,Aug），哈希函数H（Key）为Key的第一字母

表中序号MOD 7，采用线性探测再散列方法处理冲突， 要求：①构造一个装填因子为0.8的哈希表

②求出等概率情况下查找成功与查找不成功的平均查找长度 6． 在m行n列的稀疏矩阵中，有七个非零元素，若用十字链 表表示，共需要多少个结点？

三、编写一程序，要求打印以下的杨辉三角形（n可设为10） [10分]

1

1 1

1 2 1

n行 1 3 3 1

1 4 6 4 1 1 5 10 10 5 1

2 1 6 15 20 15 1 :

四、一个数组中元素为正数或负数，编写一程序，完成在O[n]时间内原地重排数组，不要求整个排序，只要求负数排在正数之前。 [10分]

五、二叉树按二叉链表方式存放：

①编写统计任一二叉树中非终端结点数目的非递归算法 [10分]

②编写求一二叉树高度的递归算法。 [5分]

六、设有向图以邻接表方式存储，请利用队列技术编写一个判别图中是否存在由顶点Vi到顶点Vj路径的算法。（其中i≠j） [12分] 七、已知有如下单链表（a1,a2,??,an）,n为偶数。

要求写出一个时间复杂度为O[n]，辅助空间为O(1)的算法，将上述链表转换成：

即（an,an-2,??a2,a1,a3,??an-1）

[注]：编写程序可选用任一种高级语言（C或PASCAL等） 一、简答问题：[15分]

1. 结构化程序设计；

2. 简述面向对象开发方法的特点；

3. 何谓程序中的千年虫问题，简述一种解决问题的方法；

4. 给出抽象数据类型和特征，并举例说明； 5. 简述广义表属于线性结构的理由。

二、写出要求结果[45分]

1. 有函数定义如下：

FUNCTION GC(M,N:INTEGER);INTEGER BEGIN

IF N=0 THEN GC:=M

ELSE GC:=GC(N，M MOD N)

END

写出此函数功能，并改写它，使其执行速度仅可能地短。 2. 设T、M为全程量，有函数定义如下：

FUNCTION FA(N:INTEGER)：INTEGER

BEGIN

M:=N+M;FA:=M;

END

在主程序段中，有如下语句：

M:=10;T:=(M+2)*FA(10);WRITELN(T); M:=10;T:=FA(10)*(M+2);WRITELN(T);

写出程序输出结果，说明为什么T的输出结果不同的原因。

3. 对以下关键字序列建立哈希表：（SUN,MON,TUE,WED,THU,FRI,SAT）,哈希函数为

H(K)=（关键字中第一个字母在字母表中的序号）MOD 7。用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并分别计算出在等概率情况下查找成功与不成功的平均查找长度。

4. 在数轴上有N个彼此相邻不交的区间，每个区间的下界和上界都是整数。N个区间

顺序为1~N。要查找给定的X落入的区间号，你认为应怎样组织数据结构，选择什么方法最快，并简述原因

5. 对N个元素组成的线性表进行快速排序时，所需进行的比较次数依赖于这N个元素

的初始排列，对N=7，给出快速排序的一个最好情况的初始排列实例（7个元素可取自集合{1，2，3，4，5，6，7}）。

6. 在前序线索树上，要找出结点P的直接后继结点，请写出相关语句。

ltag lc data rtag rc 7. 给出循环队列中元素个数的计算式（设队列的最大长度为N，队首指针FRONT，队

尾指针为REAR）。

8. 有向图的拓扑排序能否用图的深度搜索模式来查找？若能，请简述方法，若不能，请简述原因。

9. 写出三个形如A:=B的语句，完成将单链表LA整表释放的功能，可利用链栈指针

AV（即将LA表归还到可利用栈）。

三、编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A~Z这26个字母和0~9这10个数字）[10分]

四、已知两个线性表A、B，均以带头结点的单链表作存储结构，且表中元素按值递增有序

排列。设计算法，求出A与B的交集C，要求C另开辟存储空间，要求C同样以元素值的递增有序的单链表形式存贮。[8分] 五、要求二叉树按二叉链表形式存储。

（1） 写一个建立二叉树的算法。

答案请答在答题纸上，答在本试题上的答案一律无效

[注] 编写程序可选用PASCAL 或 C 语言

算法描述采用类语言，算法应加上必要的注释，所有答案均要求写在答题纸上

一、简答问题：[30分]

1．结构化程序设计

2．面向对象程序设计与面向过程程序设计各自的特点与区别 3．简述队列与广义表属于线性表的理由

4．简述不稳定排序含义、并给出证明某一种排序方法是不稳定的排序方法 5．函数的副作用

二、选择题： [20分]

1．下面 方法可以判断出一个有向图中是否有环（回路） A．深度优先遍历 B. 拓扑排序 C.最短路径 D.关键路径

2. 已知一算术表达式的中缀形式为A＋B *C-D/E，后缀形式为ABC *+DE/-，其前缀形式为 。

A. –A+B*C/DE B. –A+B*CD/E C. -+*ABC/DE D.-+A*BC/DE

3. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用 遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次

4. 排序趟数与序列的原始状态有关的排序方法是 排序法。 A. 插入 B．选择 C. 冒泡 D．快速

5.下面给出的四种排序法中 排序法是不稳定性排序法。 A．插入 B．冒泡 C．二路归并 D．堆

6. 若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是 :

A．快速排序 B. 堆排序 C.归并排序 D.直接插入排序

7. 下述二叉树中， 满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序

A. 二叉排序树 B. 哈夫曼树 C. AVL树 D.堆

8．下列排序算法中， 算法可能会出现下面情况：初始数据有序时，花费时间反而最多。

A、堆排序 B、冒泡排序 C、快速排序 D、SHELL 排序

9．设循环队列中数组的下标范围是1~n，其头尾指针分别为f，r，若队列中元素个数为 。

A、r-f B 、r-f+1 C、（r-f+1）mod n D、（r-f+n）mod n

10.若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列

A、存在 B、不存在

三、写出要求结果：[50分]

1． 下列C与PASCAL函数的功能相同

有如下C函数定义： 有如下PASCAL过程定义：

void bin(int b[ ], int n) PROCEDURE bin（VAR b：array，n：integer）

{ BEGIN

if (n==1) {b[1]=1; b[2]=1;} if (n==1) {b[1]=1; b[2]=1;} else { bin(b, n-1); else { bin(b, n-1);

b[n+1]=1; b[n+1]=1;

For (i=n; i>=2; i--) For i=n downto 2 do

b[i]= b[i]+ b[i-1] b[i]= b[i]+ b[i-1] } } END

若调用bin(A, 5), 给出A数组中第1个至第6个数组元素的输出结果。

2．给出求N阶hanoi塔的函数定义如下：

hanoi(int n，char x, char y, char z)；

{ if (n==1) move(x,1,z)

else { hanoi(n-1,x,z,y)；

move(x,n,z)； hanoi(n-1,y,x,z) } }

请写出执行hanoi(3,a,b,c)时递归函数的实在参量变化及move的搬动过程。

3．已知一个循环单链表la,av是可利用栈的头指针，请用3个赋值语句，完成将整个循环单链表释放的功能（即将la表整个归还到可用空间栈）。

4.在地址空间为0-12的散列区中，对以下关键字序列：（Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct）建哈希表，设哈希函数为H（X）=i/2，其中i为关键字中的第一个字母在字母表中的序号，处理冲突可选用线性探测法或链地址法之一，要求构造哈希表，并求出在等概率的情况下查找成功与不成功的平均查找长度。

5．在排序连续顺序文件中采用折半查找方法查找记录存在与否的过程可以借助

于一棵折半判定树来模拟，树中结点的值为记录在文件中的位置序号。

① 若文件中有l 7个记录，请画出这棵折半判定树； ② 当文件中有n个记录时，给出该判定树的深度。

6．设某城市有N个车站，并有M条公交线路连接这些车站，设这些公交车都是

单向的，这N个车站顺序编号为0至N-1，要求输入该城市的公交线路数、车站个数以及各公交线路上各站编号，要求从站0出发乘公交车至站N-1的最少换车次数，简述应如何设置数据结构、应当采用的基本处理方法。

[注] 编写程序可选用PASCAL 或 C 语言（2002年）

算法描述采用类语言，应加上必要的注释 所有答案均要求写在答题纸上

一、 回答问题 [15分] 1．结构化程序设计

2．面向对象开发方法与面向过程开发方法的不同之处 3．数据类型含义与作用 4．稳定排序与不稳定排序 二、简述方法与原因 [20分]

1． 分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递增序列的表

按递增顺序排序，给出最省时间与最费时间的算法名称，简述原因。

2．实现有向图的拓扑排序能否用图的深度搜索模式来查找？若能请简述方法，若不能，请简述原因。

3.有n个非零的数，仅要求将负数排列在正数的前面，但并不要求对其排序，简述处理方法。

4．说明在图的遍历中，设置访问标志数组的作用。

5.在一个连通无向图上，欲求从一点VI到另一点VJ（VI≠VJ）所经结点数目最少的路径，在深度优先搜索、广度优先搜索、从一点到其余各顶点的最短路径或图的其它算法中，你认为最好选择那种方法为基础，简述原因。

三、构造结果 [25分]

1. 二叉树按二叉链表方式存放，其中的data域为char类型，已

有按前序方式构造二叉树的算法，若输入序列为AB□CD□□ED□G□□□，请给出构造的相应二叉树。

2.已知Ackerman函数定义如下：

n+1 当m=0时

akm(m,n) = akm(m-1,1) 当m≠0,n=0时

akm(m-1, akm(m,n-1)) 当m≠0,n≠0时

写出akm(2,1)时调用时变化过程与执行结果。

3. 对于正整数A、B，说明下面程序段定义了什么函数功能，要求重写程序段，使之完成原函数功能，且执行时间仅可能短。 Unsigned int f(a,b) int a,b;

{if (a*b==0)

return (a+b)

else return(f(b-(b/a)*a,a); (注：b/a相当整除) }

4. 写出在中序线索树BT中找结点X的后继结点的函数过程。

5.对以下关键字序列建立哈希表（jan,feb,mar,apr,may,jun,jul），哈希函数为H（K）=关键字中第一个字母在字母表中的序号）MOD 7，用线性探测再散列法或链地址法之一处理冲突，要求构造一个装填因子为0.7的哈希表，并求出等概率情况下查找成功与不成功的平均查找长度。

四、有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。[10分]

五、 一棵树采用孩子-兄弟方式存放，结点结构为

fch data nsib level

其中fch 表示指向第一个孩子，nisib表示指向下一个兄弟, level表示结点层次。 设根结点层次为1，其它以此类推，编写一算法，将树中所有结点层次值置入相应level域。[10分]

六、 以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重复子串及其位置并分

析算法的时间复杂度. [10分] 七、 编写程序，要求完成：

建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。

在此链表上实现对二进制数加1的运算，并输出运算结果。[10分]

[注]编写程序可选用Pascal或C语言，算法描述采用类语言(1997年) 一、 简答下列问题：[15分]

1． 结构化程序设计目的、结构、方法 2． 面向对象程序设计语言的特征

3． 程序测试目的及程序可能存在的错误类型

4． 常用的参数传递方式的名称与作用

5． 为什么说数组和广义表是线性表的推广

二、 写出要求结果[38分]

1． 给定权值{7，3，6，12，8，15}，构造相应哈夫曼树，并计算其带权路径长度。

2． 有一组关键码49，38，65，97，76，13，27，43，采用堆排序方法，请写出每趟排

序结果。

3． 在后序线索树中，要找出结点P的前趋结点，请写出有关语句

Ltag Lc data Rtag Rc 4． 快速排序方法中，能否用队列代替栈，请简要说明理由。

5． 设有关键字序列{32，53，78，12，25，62，43}，哈希函数H(K)=K mod 7，用线

性探测再散列方法处理冲突，要求构造一个装填因子为0.7的哈希表，并分别计算出在等概率情况下查找成功与查找不成功的平均查找长度。

6． 有一棵二叉排序树，树中结点各不相同，欲得到一个由大到小的结点值递减序列，

你认为应当采用什么方法，便可得到要求结果。

7． 给出右边有向图G的邻接表表示，按Dijkstra算法，给出由V0到其余各顶点的最

短路径。（要求按算法步骤次序，产生各个最短路）

100 60 30 4 10 10 20

5 50

8． 对于正整数a,b,使说明下面的过程定义了什么函数功能，并要求把它重写，使得

能完成原来功能，且执行时间尽可能短。

Unsigned int f(a,b)

Unsigned int a,b;

{if (a*b==0) （ 注：==是相等） return (a+b); else

return(f(b-(b/a)*a,a)); （ 注：b/a相当整除） }

三、 编写一程序：

（1） 输入m个1-n之间正整数（m>n），统计其中1-n中各个数值个数到C数组 （2） 将数组C[1:n]中所有奇数移到偶数之前，要求时间复杂度为O(n)。[8分]

四、 编写一程序，将一个循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅含奇次项或偶数项，并要求利用原链表中的结点空间来构成这两个链表。[8分]

五、 棵树采用孩子-兄弟方式存放，结点结构为

fch data nsib level

其中fch 表示指向第一个孩子，nisib表示指向下一个兄弟, level表示结点层次。 设根结点层次为1，其它以此类推，编写一算法，将树中所有结点层次值置入相应level域。[8分]

六、 一棵二叉树的内部路径长度等于从树根到每个结点路径长度之和，二叉树用二叉链表存放，请用递归算法，编写一个二叉树内部路径长度算法。[8分]

七、 一棵二叉树用二叉链表存放，且二叉树中结点各不相同。编写一算法，查找数据域为x的结点，并打印输出值为x结点的所有祖先。[8分]

八、 有N×N个元素（N=2m）构成的二维阵列，将其转换成一个四叉树表示，转换原则如下： 将阵列4等分为四个子区域，做为四叉树的四个分支，若该子区域所有元素值均为0或均为1，则对应的四叉树为叶子结点，填值为1或0；若该子区域值不一致，则对该区域可再划分，形成下一层的子树，递归重复，直到每个子区域对应相应叶结点或到达元素这一级为止。 要求：写出从二维阵列转换生成四叉树的算法基本思路，再给出从二维阵列转换生成四叉树的算法。[7分]

本文来源：https://www.bwwdw.com/article/xclg.html