山东专升本计算机专业数据结构练习题 - 图文

济南铁道职业技术学院 专升本辅导教材 数据结构

测试一下自己的水平

一、判断题 (每小题1分，共15分)

1.非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。( ) 2.数组是一种没有插入与删除操作的线性结构。( )

3.稀疏矩阵中值为0的元素分布有规律，因此可以采用三元组方法进行压缩存储。( ) 4.空串与由空格组成的串没有区别。( )

5.将T在S中首次出现的位置作为T在S中的位置的操作称为串的模式匹配。( ) 6.深度为h的非空二叉树的第i层最多有2h-1 个结点。( ) 7.完全二叉树就是满二叉树。( )

8.已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。( ) 9.非空二叉排序树的任意一棵子树也是二叉排序树。( ) 10.有向图是一种非线性结构。( )

11.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( ) 12.AOE 网是一种带权的无环连通图。( )

13.折半查找方法适用于按值有序的线性链表的查找。( )

14.哈希表的查找效率主要取决于所选择的哈希函数与处理冲突的方法。( ) 15.选择排序过程中元素之间的比较次数与原始序列的状态无关。( ) 二、单项选择题 (每小题2分，共20分)

1.若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动_______个数据元素。( )

A.n-i B.n+i C.n-i-1 D.n-i+1

2.在单链表中，已知q指的结点是q指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行________。( ) A.link(s)←link(p)，link(p)←s B.link(q)←s，link(s)←p

C.link(p)←link(s)，link(s)←p D.link(p)←s，link(s)←q

3.在非空双向循环链表中由q所指的那个链结点前面插入一个由p指的链结点的动作对应的语句依次为:rlink(p)←q , llink(p)←llink(q) , llink←p, _________。（空白处为一条赋值语句） A.rlink(q)←p

B.rlink(llink(q)←p C.rlink(llink(p))←p D.rlink(rlink(p)←p

4.为了节省存储空间，将n阶对称矩阵A中包括主对角线元素在内的下三角部分的所有元素按 照行序为主序方式存放在一维数组B[1:n(n-1)/2]中，对任意下三角部分的元素aij(i≥j)在B 的下标k是 ( ) A.i(i-1)/2+j B.(i(i-1))/2+j C.i(i+1)/2+j B.(i(i+1))/2+j

5.某堆栈的输入序列为a,b,c,d,下面的四个序列中，__________不可能是它的输出序列。( )

第 1 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

A.a,c,b,d B.b,c,d,a C.d,c,a,b D.c,d,b,a

6.若非空队列采用链式存储结构，front和rear分别为队头元素与队列尾元素的指针，删除此时队列的一个元素的操作时依次执行p←front，_________________ ，call RET(P)。( )

A.front←link(rear) B.rear←link(p) C.rear←link(front) D.front←link(p)

7.中缀表达式A-(B+C)*D/E的后缀形式是_________________。( ) A.ABC+-D*E/ B.ABC+D*-E/ C.ABC+D-*E/ D.ABC+D*E/-

8.广大义表A=((),(a),(b,(c,d)))的长度为 ( ) A.2 B.3 C.4 D.5

9.在初始为空的杂凑表中依次插入关键字序列(MON，TUE，WED，THU，FRI，SAT，SUN), 杂凑函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为[0:6]，采用线性再散列法处理冲突。插入后的杂凑表应该如________________所示。( ) A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON

10.从未排序序列中选择一个元素，该元素将未排序序列分成前后两个部分，前一部分中所有元素都小于等于所选元素。后一部分中所有元素都大于等于所选元素，而所选元素处在排序的最终位置。这种排序方法称为_____________排序法。( ) A.插入 B.谢尔 C.快速 D.堆积

三、填空题 (每小题2分，共20分)

1.已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)=___________________。

2.若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为______________。 3.具有n个结点的非空二叉排序树的最小深度为_______________。

第 2 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

4.深度为h且有_______________个结点的二叉树称为满二叉树。(设根结点处在第1层)。

5.二叉树的前序遍历序列为A，B，C，E，F，D，G，H，中序遍历序列为A，E，C，F，B，G，D，H，其后序遍历序列为__________________。

6.已知序列(34，76，45，18，26，54，92，65，)，按照逐点插入法建立一棵二叉排序列树，该树的深度是__________________。

7.一个不带有权的有向图采用邻接矩阵存储方法，其邻接矩阵是一个__________________。

8.带权连通图G=，其中V={v1,v2,v3,v4,v5,},E={(v1,,v2)7,(v1,v4)6，(v1,v4)9，

(v2,v3)8，(v2,v4)4，(v2,v5)4，(v3,v4)6，(v4,v5)2，(注：顶点偶对右边的数据为边上的权值)，G的最小生成树的权值之和为__________________ 。

9.在线性表中采用折半查找法（二分查找法）查找一个数据元素，线性表中元素应该按值有序，并且采用______________存储方法。

10.若对序列(49，38，65，97，76，13，27，50)采用选择排序法排序，则第三趟结束后序列的状态是___________________。

四、问题求解题 (每小题10分，共20分) 1.已知AOE网为G=(V,E)，其中, V ={v1,v2,v3,v4,v5,v6,v7},

E = {a1,a2,a3,a4,a5,a6,a7,a8,a9,a10},

a1:(v1,v2)3,a2:(v1,v3)2,a3:(v2,v4)1,a4:(v2,v5)8,a5:(v3,v4)3, a6:(v3,v6)7,a7:(v4,v5)4,a8:(v4,v6)2,a9:(v5,v7)9,a10:(v6,v7)6；

(注：顶点偶对的右括号下方的数据表示该边上的权值)。e[i]与l[i]分别表示活动a1的最早开始时间与最晚开始时间，请分别求出e[i]与l[i](1≤i≤10),填入下面的方格中。 e[1:10] l[1:10]

2.若对序列(76，38，65，13，97，27，50，49)采用堆积排序法(按照值的大小从小到大)进行排序，请分别在下表中写出每一趟的结果：

原始序列 76 38 65 13 97 27 50 49 第1趟结果 第2趟结果 第3趟结果 第4趟结果 第5趟结果 第6趟结果 第7趟结果 第8趟结果

五、算法题 (共25分)

1.已知长度为n的线性表A采用顺序存储结构，并且元素按值大小非递减排列，下面的算法删除线性表中多余的值相同的元素。请在算法的空白处填入适当内容，使之能够正常工作。(10分) procedure DEL (A,n) i←1

while ____________ do if (A[i]≠A[i+1] then i←i+1

第 3 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

else // 查找满足条件的元素 // [ for _________ do A[j-1]←A[j]

end // 删除第i+1个元素 (满足条件的元素) //

______________ ] // 修改线性表的长度 // end end

2.已知非空线性链表的链结点的构造为| date | link |，第一个链结点的指针为list，下面的算法删除链表的第i个结点（设i>0）。请在算法的空白处填入适当内容，使之能够正常工作。 (15分)

procedure DEL (list,i,item)

_____________ // 给变量q赋初值 // if (i=1) then

list←link(q) // 删除第一个链结点 // else

[ for j←1 to ______________ do r←q

q←link (q)

if _________ then

[ call ERROR (i 超过链表的长度！’) return ]

end if // r与q分别指向第i-1个与第i个链结点 // _____________ ] // 删除第i个链结点 // call RET(q) // 删除被删除链结点的空间 end

第一章 课堂练习

1．1 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)程序与算法没有区别。 ( )

(2)程序设计框图就是一种图形化的算法。 ( )

第 4 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

(3)采用程序设计语言编写的程序也是算法。 ( ) (4)一个算法可以没有输入，但不能没有输出。 ( )

(5)顺序存储结构通过数据元素的地址直接反映数据元素间的逻辑关系。 ( ) (6)链式存储结构通过指针间接地反映数据元素之间的逻辑关系。 ( ) (7)数据的存储结构通常只有顺序存储结构与链式存储结构两种。 ( ) (8)具有相同逻辑结构的数据可以采用不同的存储结构。 ( ) (9)逻辑结构不相同的数据应该采用不同的存储结构。 ( ) (10)算法分析的前提是算法的时空效率高， ( ) 1．2 填空题。

(1)“数据结构”课程研究的主要内容包括——、——和——三个方面。 (2)一般情况下，算法独立于具体的——，与具体的程序设计语言——。 (3)一个完整的算法应该具有——、——、——、——和——五个特性。 (4)数据的逻辑结构可以分为——和——两大类。

(5)除了顺序存储结构与链式存储结构之外，数据的存储结构通常还有——和散列结构。 (6)数据的逻辑结构是指——，而存储结构是指——。

(7)逻辑上相邻的数据元素在物理位置上也相邻是——存储结构的特点之一。 (8)为了实现随机访问，线性结构应该采用——存储结构。 (9)链式存储结构的主要优点是——。

(10)算法分析主要从——和——这两个方面对算法进行分析。

1．3 通常说数据结构是一个二元组(D，R)，其中D，R分别代表什么? 1．4 何谓数据的逻辑结构?何谓数据的存储结构?两者有何联系?

历年试题 一

1．在数据结构中，数据的逻辑结构可以分成（ ）

A．内部结构和外部结构 B．线性结构和非线性结构 C．紧凑结构和非紧揍结构 D．动态结构和静态结构 2．下列说法正确的是（ ）

A．数据是数据元素的基本单位

B．数据元素是数据项中不可分割的最小标识单位 C．数据可由若干个数据元素构成 D．数据项可由若干个数据元素构成 3．数据结构的基本任务是（ ）

A．逻辑结构和存储结构的设计 B．数据结构的运算实现 C．数据结构的评价与选择 D．数据结构的设计与实现

4．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ）

2

A．O（1） B．O（n） C．O（nlog2n） D．O(n)

5.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 6、选出正确的表述

(1)顺序存储方式只能用于存储线性结构。

第 5 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

(2)顺序存储方式的优点是存储密度大, 且插入、删除运用算效率高。 (3)链表的每个结点中都恰好包含一个指针。

(4)散列法存储的基本思想是由关键码的值决定数据的存储地址。 (5)散列表的结点中只包含数据元素自身的信息, 不包含任何指针。

(6)负载因子 (装填因子) 是散列法的一个重要参数, 它反映散列表的装满程度。 (7)栈和队列的存储方式既可是顺序方式, 也可是链接方式。

(8)用二叉链表法 (llink -- rlink法) 存储包含n 个结点的二叉树, 结点的2n个指针区域中有n+1 个为空指针。

(9)用相邻矩阵法存储一个图时, 在不考虑压缩存储的情况下, ?所占用的存储空间大小只与图中结点个数有关, 而与图的边数无关。

(10)邻接表法只能用于有向图的存储,而相邻矩阵法对于有向图和无向图的存储都适用。

7．表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、_______________和散列存储方式。

8．下列程序段的时间复杂度为________________。 product = 1; for (i = n;i>0; i--)

for (j = i+1; j

9．文件上的两类主要操作为________________和________________。 10．文件的基本运算包括______________和修改两类。 11．下列程序段的时间复杂性量级是_____________。

for (i=1;i

t=t+1;

12.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为________。

第二章 课后辅导

例2．1 已知长度为n的非空线性表A采用顺序存储结构，表中数据元素按值的大小非递减排列，请写出删除该线性表中值相同的多余元素的算法。7654321 7654321

算法思想比较简单，只需从表的第一个数据元素开始到最后那个数据元素，反复做以下动作：比较相邻的两个数据元素是否相同，若相同，则删除其中一个；若不相同，则比较下一对相邻元素。算法如下： voidDELETEITEM1(ElemTypeA[]，int n)) {

int j，i=0； while(i

if (A[i]!=A[i+1]) ／x若相邻两个元素不相同。／ i++；

else{ ／*若相邻两个元素相同，则删除其中一个*／ for ( j=i++；i

n--； ／x表长减1 x／

第 6 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

} } }

2

上述算法的时间复杂度为O(n)。对算法进行改进，得到一个时间复杂度为O(n)的 算法不是很困难。这里，设置两个整型变量i与k，它们的初值分别为1与0。若在比较 过程中发现A[i]与A[k]不同，则先将k后移一个位置，然后将A[i]送到A[k]的位置上； 若A[i]与A[k]相同，只是将i后移一个位置。当表中所有元素都处理完毕时，k+1正好 是删除多余元素以后线性表的长度。 改进后的算法如下：

voidDELETEITEM2(ElemTypeA[]，int &n) {

int k，i； if(n>1) { k=0；

for(i=1；i

if(A[i]!=A[k]) ／x若A[i]与A[k]不相同时。／ A[++k]=A[i]；

n=k+1； ／。得到删除以后的表长。／ } }

14．将两个按值有序的非空线性链表合并为一个按值有序的线性链表 设lista与listb分别为两个有序链表第一个链结点的指针。将这两个有序链表合并 为一个有序链表，其第一个链结点的指针为listc。

这里，只需设置三个指针p，q和r，其中，p和q分别指向链表lista和链表listb当前待比较插入的链结点，而r指向链表listc中当前最后那个链结点。然后不断地比较p与q

所指的链结点的数据域值，若p->data < q->data，则将p指的链结点链接到r所指的链结点之后，否则将q指的链结点链接到r所指的链结点之后。当其中一个链表为空时，只 需将另一个链表中剩余的链结点都依次链接到r所指的链结点之后即可。初始时，让

listc指向lista和listb所指向的链结点中值小的那一个链结点。 LinkListMERGELIST(LinkListlista,LinkListlistb) {

LinkList listc，p，q，r； if(lista->dada<=listb->data){ listc=lista； r=lista；

p=lista->link； } else{

listc=listb； r=listb；

q=listb->link；

} ／x listc指向lista和listb所指结点中值小者x／ while(p!=NULL&&q!=NULL){

if(p->data<=q->data){／x若当前p所指结点的值不大于q所指结点的值x／

第 7 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

r->link=p； ／y将p所指结点链接到r所指结点之后x／ r=p；

p=p->link； } else{

r->link=q； ／。将q所指结点链接到r所指结点之后‘／ r=q；

q=q—>link； } }

r->link=p?p=q； ／x插人剩余链结点x／

return(listc)； ／x返回合并后的链表第一个链结点地址x／ }

若两个链表的长度分别为n与m，则上述算法的时间复杂度为O(n十m)。在合并两 个链表为一个链表时不需要另外建立新链表的链结点空间，只需将给定的两个链表中的 链结点之间的链接关系解除，重新按照元素值的非递减关系将所有链结点链接成为一个 链表即可。

例2．5 约瑟夫(Josephu)问题 已知n个人(不妨以编号1，2，3，?，n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列，他的下一个人又从1开始报数，数到m的那个人又出列，依此规则重复下去，直到圆桌周围的人全部出歹，J。

例如，当n：8，m’4，k二3时，出列的顺序依次为6，2，7，4，3，5，1，8。

解决约瑟夫问题可以利用多种数据结构，但比较简单和自然的方法是利用一个具有 n个链结点、且不带头结点的循环链表。将圆桌周围的每一个人对应着该链表中的一个链结点，某个人出列相当于从链表中删除一个链结点。下面的算法就是在该循环链表中不断地报数，不断地删除一个链结点，直到循环链表中还剩一个链结点时游戏结束。整个算法可以分为三个部分： (1)建立一个具有n个链结点且无头结点的循环链表； (2)确定第一个报数点的位置；

(3)不断地从链表中删除一个链结点，直至链表中还有一个链结点。

习 题 2．1

判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)空线性表的特征是表中数据元素都未赋值。 ( )

(2)线性表的顺序存储结构必须占用一片地址连续的存储单元。 ( )

(3)用一维数组存储线性表时，表中第i个元素存放在下标为i的数组元素中。 ( ) (4)采用顺序存储结构的线性表又称为顺序表。 ( )

(5)—个数据元素的地址是指该元素占用的若干存储单元的第一个单元的地址。 ( ) (6)线性表占用的存储单元的数量与表中数据元素的类型有关。 ( ) (7)线性表的顺序存储结构要比链式存储结构节省存储空间。 ( ) (8)线性表的链式存储结构要比顺序存储结构节省存储空间。 ( )

(9)若线性表采用顺序存储结构,线性表的长度等于表中元素的个数与每个元素所占内存单元之乘积。 ( )

第 8 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

(10)若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144则第1个数据元素的存储地址是101。 ( 100 )

(11)在长度为n的顺序表的第i个位置插入一个数据元素，i的合法值为1≤i≤N。 ( ) (12)删除长度为n的顺序表的第i个数据元素，i的合法值为1≤i≤n。 ( ) (13)在长度为n的顺序表中插入一个数据元素的时间复杂度为O(n)。 ( ) (14)线性表的链式存储结构不必占用地址连续的存储空间。 ( ) (15)链表中的每个链结点占用的存储空间不必连续。 ( )

(16)一个链结点的地址是指该链结点占用的若干存储单元的第一个单元的地址。 ( ) (17)非空线性链表的最后那个链结点的指针域不能为空，应该存放NULL。 ( ) (18)所谓空链表是指没有任何链结点的链表。 ( ) (19)任何一个链表都可以根据需要设置一个头结点。 ( ) (20)每个链表的前面都必须设置一个头结点。 ( )

(21)线性链表(单向链表)中的每个链结点只有后继结点，没有前驱结点。 ( ) (22)一个空的链表不占用任何存储空间。 ( )

(23)若指针变量list指向一个空链表，则list中什么也没有。 ( ) (24)无论出现在算法的什么地方，符号p->data表示的意思都一样。 ( ) (25)在算法中，符号p->link表示p所指的下一个链结点的地址。 ( )

(26)删除非空线性链表的第一个链结点只需执行语句list=list->link。 ( )

(27)循环链表的最后那个链结点的指针域中存放着链表最前面那个结点的地址。 ( ) (28)设置一个指针变量，它可以遍历整个循环链表。 ( )

(29)双向链表的头结点指针要比线性链表的头结点指针占用更多的存储空间。 ( ) (30)在链结点数目相同的前提下，双向链表占用的空间是线性链表的2倍。 ( ) 单项选择题。

(1)一个顺序表所占用的存储空间大小与——无关。

A．表的长度 B．元素的存放顺序 C．元素的类型 D。元素中各字段的类型

(2)设存储分配是从低地址到高地址进行的。若每个元素占用4个存储单元，则某元素的地 址是指它所占用的单元的

A．第1个单元的地址 B．第2个单元的地址 C．第3个单元的地址 n第4个单元的地址

(3)若线性表采用顺序存储结构，每个元素占用4个存储单元，第1个元素的存储地址为100， 则第12个元素的存储地址是． 。 A．112 B．144 C．148 0．412

(4)若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值 应该是——。

A．i>O B．i≤n C．1≤i≤n D．1≤i≤n+1

(5)若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该是 A．i>O B．i≤n C．1≤i≤n D。1≤i≤n十1

(6)若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表 中——个数据元素。

A．n-i B．n+i C．n-i+l D．n-i-1

(7)若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，需要移动 表中——个元素。 。

A．i B．n+i C．n-i+l D．n-i-1

(8)若频繁地对线性表进行插入和删除操作，该线性表应该采用——存储结构。

第 9 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

A．散列 B．顺序 C．链式 D．索引 (9)链表中所占用的存储单元地址一定是 。

A．无序的 B．连续的 C．不连续的 D．部分连续的 (10)链表中的每一个链结点所占用的存储单元——。

A．不必连续 B．一定连续 C．部分连续 D．连续与否无所谓 (11)与单链表相比，双向链表的优点之一是 。 A．插入、删除操作更简单 B．可以进行随机访问 C．可以省略头结点指针 D．顺序访问相邻结点更灵活

(12)若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域中存 放的是——。

A．1ist的地址 B．1ist的内容

C．1ist指的链结点的值 D．链表第一个链结点的地址

(13)若list是某带头结点的循环链表的头结点指针，当p(p与list同类型)指向链表的最后那 个链结点时，——。

A．该结点的指针域为空 B．p为空

C．p的内容与头结点的内容相同 D．该链结点指针域内容与list的内容相同

(14)若listl和list2分别为一个单链表与一个双向链表的第一个结点的指针，则——。 A．1ist2比listl占用更多的存储单元 B．1istl与list2占用相同的存储单元

C．1istl和list2应该是相同类型的指针变量D．双向链表比单链表占用更多的存储单元 (15)在表达式中，符号p->link表示——。 A．p所指的链结点的指针域(位置) B．p所指的链结点的指针域的内容

C．p所指的链结点的下一个链结点的地址

D．p所指的链结点的下一个链结点的地址(出现在表达式中)

(16)在一个具有n个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较 ——个链结点。

A．n B．n／2 C．(n+1)／2 D．(n-1)／Q

(17)从一个具有n个链结点的有序线性链表(即链结点按照数据域值有序链接)中插入一个 新的链结点，并且仍然保持链表有序的时间复杂度为——。 A．O(1) B．O(n) C．O( n(2) ) D．O( log2(n) )

(18)给定具有n个元素的顺序表，建立一个有序线性链表的时间复杂度为——。 A．O(1) B．O(n) C．O( n(2) ) D．O( log2(n) )

(19)在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执 行——。

A．q->link=p；p->link=q； B．q->link=p->link；p->link=q； C．q->link=p->link；p=q； D．p->link=q；q->link=p；

(20)若删除非空线性链表中由p所指的链结点的直接后继链结点的过程是依次执行 ________.

A．r=p->link；p->link=r；free(r)；

B．r=p->link；p->link=r->link；free(r)； C．r=p->link；p->link=r->link；free(p)； D．p->link=p->link->link；free(p)；

(21)在非空双向循环链表中由q所指的链结点后面插入一个由p所指的链结点的动作依次 为：p->llink=Q；p->rlink=q->rlink；q->rlink=p；——。(空白处为一条赋值

第 10 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

语句)

A．q->llink=p B．q->rlink->llink=p

C．p->fiink->llink=p D．p->llink->llink=p

(22)在非空双向循环链表中由q所指的那个链结点前面插入一个p所指的链结点的动作对 应的语句依次为：p->rlink=Q；p->llink=q->llink；q->[1ink=p；——。(空白 处为一条赋值语句)

A．q->rlink=p； B．q->llink->rlink=p；

C．p->rlink->rlink=p； D．p->llink->rlink=p；

(23)在包含有1000个数据元素的线性表中实现如下四个操作，所需要的执行时间最长的是 一O

A．线性表采用顺序存储结构，在第10个元素后面插入一个新的元素 B．线性表采用链式存储结构，在第10个元素后面插入一个新的元素 C．线性表采用顺序存储结构，删除第990个元素 D．线性表采用链式存储结构，删除p所指的链结点 2．3填空题。

(1)顺序表是一种——线性表。

(2)在程序设计中，描述线性表的顺序存储结构一般都用——。

(3)在——情况下，删除线性表中一个数据元素平均要移动表中近一半的元素。 (4)在顺序表的——插入一个新的数据元素不必移动任何元素。

(5)若长度为n的线性表采用顺序存储结构，在其第i个位置(1≤i≤n+1)插入一个新的数据 元素，当不溢出时，首先——，然后——，最后——。

(6)若长度为n的线性表采用顺序存储结构，删除其第i个元素(1≤i≤n)，首先——，然 后——。

(7)若长度为n的线性表采用顺序存储结构，插入或删除一个元素的时间复杂度为——。

(8)若某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第12个元素 的存储地址为——。

(9)线性表的链式存储结构主要包括——、——和——三种形式。

(10)线性表的顺序存储结构是通过——来直接反映数据元素之间的逻辑关系，而链式存 储结构则是通过——间接反映数据元素之间的逻辑关系。

(11)根据——的多少，可以将链表分为线性链表(单链表)与双向链表。

(12)若对线性表进行的操作主要不是插入和删除，则该线性表宜采用——存储结构，若 频繁地对线性表进行插入和删除操作，则该线性表宜采用——存储结构。 (13)删除由list所指的线性链表的第一个链结点是执行操作——。

(14)删除非空线性链表中由q所指的链结点(其直接前驱结点由r指出)的动作是执行语句 ——和——。

(15)在线性链表中由q所指的链结点后面插入一个地址为p的新结点的过程是依次执行操 作——和——。

(16)若p为指向循环链表中某链结点的指针变量，判断循环链表是否只有一个链结点的标志 是——。

(17)删除非空双向链表中由q所指的链结点的过程是执行语句——和——。 (18)在具有n个链结点的链表的已知位置插入一个链结点的时间复杂度为——。 (19)在具有n个链结点的链表中查找一个链结点的时间复杂度为——。 (20)一元多项式f(x)二9x1’—4x8+3x—5的线性链表表示为——。

2．4 已知长度为n的线性表A采用顺序存储结构，请写一算法，找出该线性表中值最小的数据元素。

第 11 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

2．5 已知长度为n的线性表A采用顺序存储结构，请写出逆转该线性表的算法，即由A二(al，a2，?，An-l，An)产生A'：(An-1，An，?，A1，A2)，要求在逆转过程中用最少的附加空间(即用尽可能少的辅助变量)。

2．6 已知线性表A的长度为n，并且采用顺序存储结构，请写一算法，删除该线性表中所有值为d的数据元素，并讨论算法的时间复杂度。

2．7 已知长度为n的线性表A采用顺序存储结构，并且每个数据元素均为一个无符号整数，请写一算法，删除线性表中的所有奇数。

2．8 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)的算法，该算法删除线性表中原来序号为奇数的那些数据元素。 2．9 已知长度为n的线性表A采用顺序存储结构，写一算法，删除表中重复出现的所有数据元素 要求：剩余元素的相对位置保持不变。

2．10 已知长度为n的线性表A采用顺序存储结构，并且元素按值的大小非递减排列，请写一算法，在线性表中插入一个新的数据元素让em，要求插入以后线性表中元素仍然保持按值的大小非递减排列。 2．11 已知长度为n的线性表A采用顺序存储结构，写一算法，删除所有值大于x且小于y的数据元素。

2．12 请写一算法，通过键盘输入一系列数据元素，建立一个长度为n、且不包含重复元素的线性表A。这里，设线性表A采用的存储结构为顺序存储结构，并且假设空间足够。

2。13 已知线性表A与线性表B的长度分别为n与m，并且都采用顺序存储结构，写一算法，在线性表A的第i个位置插入线性表B。约定：不考虑存储空间溢出问题。

2．14 已知非空线性链表的第一个链结点的存储地址为list，写出删除该链表第i个链结点的算法。 2．15 已知非空线性链表第一个链结点的存储地址为1ist，试写出删除链表中从第i个链结点开始的(包括第i个链结点本身)连续k个链结点的算法。

2．16 已知线性链表第一个链结点的存储地址为1ist，写一算法，把该链表中数据域值为d的所有链结点的数据域值修改为p。

2．17 已知线性链表第一个链结点指针为list，写一算法，删除链表中数据域值最大的那个链结点。 2．18 已知线性链表第一个链结点指针为list，写一算法》，j断该链表是否是有序链表(即链结点是否按照数据域大小链接)，若是，算法返回1，否则返回—1。

2．19 已知线性链表第一个链结点指针为1ist，写一算法，交换p所指链结点与其下一个链结点的位置(设p指向的不是链表最后那个链结点)。

2．20 已知非空线性链表第一个链结点由list指出，请写一算法，将链表中数据域值最小的链结点移到链表最前面。

2．21 已知非空线性链表第一个结点的指针为list，试编写一算法按递减次序打印各链结点数据域的内容(提示：在链表中打出最大值结点，打印之后将其删除。反复执行，直到链表为空时为止)。

2．22 已知一个不带头结点也无头指针变量，并且长度大于1的循环链表，试写一算法，删除p所指链结点的直接前驱结点。

2．23 已知带有头结点的循环链表中头结点的指针为list，试写出删除并释放数据域内容为x的所有结点的算法。

2．24 已知线性链表第一个链结点的指针为list，试写一算法，删除数据域值相同的多余结点，即： 若链表中有多个结点具有相同的数据域值，只保留其中一个结点，其余结点均从链表中的最后删去，使得到的链表中所有结点的数据域值都不相同。

2．25 设线性表X=(x1，x2，?，Xn)与Y=(yl，y2，?，ym)都采用链式存储结构(两个链表第一个结点的指针不妨用X与Y分9U表示)。试写一个算法归并这两个线性链表为一个线性链表，使 ((x1，Y1，x2，y2，?，xm,Ym，Xm+1，?，Xn) 当m≤n时 ((x1，Y1，x2，y2，?，xn，yn，yn+1，?，ym) 当m>n时

第 12 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

2．27 试写出将一个线性链表(第一个结点的存储地址为list)分解为两个循环链表，并将两个循环链表的长度存放在各自的头结点的数据域中的算法。

分解规则：若线性链表中某一链结点属于第一个循环链表，则下一个链结点就属于第二

个循环链表；反之，若线性链表中某一个链结点属于第二个循环链表，则下一个链结点就属于第一个循环链表。 2．28 设A与B分别为两个带有头结点的有序循环链表(所谓有序是指链结点按数据域值大小链接，这里，不妨按数据域值从小到大链接)，lista和listb分别为两个链表的头结点指针。请写出将这两个链表合并为一个带头结点的有序循环链表的算法。

2．29 已知循环链表头结点指针list，请编写一个能逆转链表方向的算法。

2．30 写一算法，先从键盘输人n个整型数，建立一个带有头结点的双向循环链表，然后按照与输入相反的次序依次输出这n个整型数。

2．31 在非空双向循环链表中由q所指的结点后面插入一个数据信息为item的新结点的算法如下： voidINSERTD(DLinkListq，datatypeitem) {

DLinkList p；

p：(DLinkList)malloc(sizeof(DNode))； ／*申请一个新的链结点*／ p->data=item； p->llink=q；

p->rlink=q->rlink； q->rlink=p；

请在算法的方框中填上必要的动作(一条语句)。

2．32 有人说线性表的顺序存储结构比链式存储结构的存储空间开销要小，也有人说线性表的链式存储结构比顺序存储结构的存储空间开销要小，你是如何看待这两种说法的?请说明你的看法。

第二章 历年试题

1．在线性表的下列存储结构中，读取元素花费时间最少的是（ ）

A．单链表 B．双链表 C．循环链表 D．顺序表 2．顺序存储的线性表（a1,a2,?,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）

A．n B．n/2 C．n+1 D．(n+1)/2

3.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) A.n-i+1 B.n- i C.i D.i-1

4．在顺序存储的线性表（a1,a2?，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动_________个元素。 一、选择题

1．在线性表的下列存储结构中，读取元素花费时间最少的是（ ）

A．单链表 B．双链表 C．循环链表 D．顺序表

2．顺序存储的线性表（a1,a2,?,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）

A．n B．n/2 C．n+1 D．(n+1)/2

3.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) A.n-i+1 B.n- i C.i D.i-1

4．在顺序存储的线性表（a1,a2?，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动

第 13 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

_________个元素。

5．在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）

A．数据元素的相邻地址表示 C．指向后继元素的指针表示

B．数据元素在表中的序号表示 D．数据元素的值表示

6．设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（ ） s -> next = p -> next; p -> next = s;

t = p -> data; p -> data = s -> data; s ->data = t;

A．结点*p与结点*s的数据域互换 B．在p所指结点的元素之前插入元素 C．在p所指结点的元素之后插入元素 D．在结点*p之前插入结点*s

7．在线性表的下列存储结构中，读取元素花费时间最少的是（ ）

A．单链表 C．循环链表

B．双链表

D．顺序表

8．将一个头指针为p的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为:

q=NULL;

while (p!=NULL) {

（ ）

} p=q;

A. r =q; q=p; p=p -> next; q -> next=r; B．q=p; r=q; p=p -> next; q -> next=r; C．r=q; p=p -> next; q=p; q -> next=r;

D．q=p; p=p -> next; r=q; q -> next=r;

9.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 10.设单链表中结点的结构为

typedef struct node { //链表结点定义 ElemType data; //数据

struct node * Link; //结点后继指针 } ListNode;

(1) 已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？ A. s->link = p; p->link = s;

B. s->link = p->link; p->link = s; C. s->link = p->link; p = s; D. p->link = s; s->link = p;

(2) 非空的循环单链表first的尾结点（由p所指向）满足： A. p->link == NULL; B. p == NULL;

C. p->link == first; D. p == first;

第 14 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

二、判断题。

(1) 线性表的逻辑顺序与物理顺序总是一致的。 (2) 线性表的顺序存储表示优于链式存储表示。

(3) 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。 (4) 二维数组是其数组元素为线性表的线性表。

(5) 每种数据结构都应具备三种基本运算：插入、删除和搜索。 三、填空题。

1．已知指针p指向单链表中某个结点，则语句p -> next =p -> next -> next的作用是________。 2．若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为________。

3．设某非空双链表，其结点形式为若要删除指针prior data next 所指向的结点，则需执行下述语句段：

q->prior->next＝q->next; __ _____________。

4．在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是________和________。

5.函数中，h是带头结点的双向循环链表的头指针。

(1) 说明程序的功能；

(2) )当链表中结点数分别为1和6(不包括头结点)时，请写出程序中while循环体的执行次数。

int f(DListNode *h) {

DListNode *p,*q; int j=1; p=h->next; q=h->prior;

while(p!=q && p->prior!=q) if(p->data==q->data) {

p=p->next; q=q->prior; }

else j=0; return j;

第 15 页 共 63 页

q

济南铁道职业技术学院 专升本辅导教材 数据结构

A．〞cdefgh〞 C．〞cdefxy〞 B．〞cdxyzw〞 D．〞cdefef〞

B．数组的元素必须从左到右顺序排列 D．数组是多维结构，内存是一维结构

2．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（ ）

A．数组的元素处在行和列两个关系中 C．数组的元素之间存在次序关系 A．tail (head (LS)) C．head (tail (LS)) A．创建和删除

3．从广义表LS＝（(p, q), r, s）中分解出原子q的运算是（ ）

B．head (tail (head (LS))) D．tail (tail (head (LS))) B．索引和修改

4．数组通常具有两种基本运算，即（ ）

C．读和写 D．排序和查找 5．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（ ）

A．116 B．118 C．120 D．122

6.为查找某一特定单词在文本中出现的位置，可应用的串运算是( ) A.插入 B.删除 C.串联接 D.子串定位

7.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到( ) A.P=″SCIENCE″ B.P=″STUDY″ C.S=″SCIENCE″ D.S=″STUDY″

8.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为( ) A.356 B.358 C.360 D.362 9.串S=″I am a worker″的长度是________。

第五章 树 二叉树 补充内容

后序遍历的非递归算法。

在对二叉树进行后序遍历的过程中，当指针p指向某一个结点时，不能马上对它进行 访问，而要先遍历它的左子树，因而要将此结点的地址进栈保存。当其左子树遍历完毕之 后，再次搜索到该结点时(该结点的地址通过退栈得到)，还不能对它进行访问，还需要遍 历它的右子树，所以，再一次将此结点的地址进栈保存。为了区别同一结点的两次进栈， 引入一个标志变量nae，有 0 表示该结点暂不访问 1 表示该结点可以访问

标志flag的值随同进栈结点的地址一起进栈和出栈。因此，算法中设置两个空间足够的堆栈，其中，STACKlCM]存放进栈结点的地址，STACK2[M]存放相应的标志n昭的值，两个堆栈使用同一栈顶指针top，top的初值为—1。 具体算法如下：

#defineH 100 ／●定义二叉树中结点最大数目。／ voidPOSTOiRDER(BTREET) {

／*T为二叉树根结点所在链结点的地址。／

第 31 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

BTREESTACKl[H]，p=T； intSTACK2[M]，flag,top=—1； if(T!=NULL) d0{

while(p!=NULL){

STACK／[++top]=p； ／●当前p所指结点的地址进栈●／ STACK2[top]= 0； ／，标志0进栈●／

p=p->lchild； ／●将p移到其左孩子结点x／ }

p=STACKl[top)； flag=STACK2[top--]； if(flag==0){

STACKl[++top]=p； ／，当前p所指结点的地址进栈。／ STACK2[toP]=1； ／●标志1进栈●／

p=p->rchild； ／x将p移到其右孩子结点o／ } else{

VISIT(p)； ／x访问当前p所指的结点x／ p=NULL； }

}while(p!=NULLtttop!=-1)； }

不难分析，上述算法的时间复杂度同样为O(n) 5．6．3 二叉树的线索化算法

对--X树的线索化，就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历序列中的直接前驱或直接后继的过程，因此，二叉树的线索化过程只能在对二叉树的遍历过程中进行。 ·

下面给出二叉树的中序线索化的递归算法。算法中设有指针pre，用来指向中序遍历过程中当前访问的结点的直接前驱结点，pre的初值为头结点的指针；T初始时指向头结点，但在算法执行过程中，T总是指向当前访问的结点。 voldINTHREAD(TBTREET) { TBTREE pre； if(T!=Null){

INTHREAD(T—>lchild)； if(T—>rchild==NULL) T—>rbit=0；

if(T—>lchild==NUll)； T—>lchild=pre； T—>lbit=0； }

if(pre—>rbitc==0) pre—>rchild=T； pre=T；

inthread(T->rchild)； } }

第 32 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

平均查找长度(AverageSearchLength)：确定一个元素在树中的位置所需要进行的比较次数的期望值。 二叉树的内路径长度(InternalPathLength)：从二叉树根结点到某结点所经过的分支数目定义为该结点的路径长度。

二叉树中所有结点的路径长度之和定义为该二叉树的内路径长度IPL。图7。25(h)给出的二叉排序树的内路径长度为

IPL：1X2+2X2+3X1+4X2=17

二叉树的外路径长度(ExternalPathLength)：为了分析查找失败时的查找长度，在二叉树中出现空子树时，增加新的空叶结点来代表这些空子树，从而得到一棵扩充后的二叉树。为了与扩充前的二叉树相区别，这些新增添的空的叶结点用小方块代表，称之为外部结点，树中原有的结点为内部结点。

下图给出了一棵扩充后的二叉树，其外路径长度EPL是二叉树中所有外部结点的路径长度之和，即

EPL=2X2+3X1+4X4+5X3十6X2=50

习 题

5.1 判断题(在你认为正确的题后的括号中打√，否则打X)。

(1)在树型结构中，每一个结点最多只有一个前驱结点，但可以有多个后继结点。 ( ) (2)在树型结构中，每—个结点不能没有前驱结点。 ( ) (3)在度为k的树中，至少有一个度为k的结点。 ( )

(4)在度为k的树中，每个结点最多有k—1个兄弟结点。 ( ) (5)度为2的树是二叉树。 ( ) (6)二叉树的度一定为2。 ( )

(7)在非空完全二叉树中，只有最下面一层的结点为叶结点。 ( ) (8)在完全-y．树中，没有左孩子的结点一定是叶结点。 ( ) (9)在完全二叉树中，没有右孩子的结点一定是叶结点。 ( )

(10)在结点数目一定的前提下，各种形态的二叉树中，完全二叉树具有最小深度。 ( ) (11)满二叉树一定是完全二叉树。 ( )

(12)满二叉树中的每个结点的度不是0就是2。 ( )

(13)在所有深度相同的二叉树中，满二叉树具有最大结点数目。 ( ) (14)具有n个结点的非空二叉树一定有n—1个分支。 ( )

(15)n个结点的二叉树采用二叉链表结构，链表中有n—1个存放NULL的指针域。 ( ) (16)“退化二叉树”不宜采用顺序存储结构的主要原因是空间浪费较大。 ( ) (17)由二叉树的前序序列和中序序列可以惟一地确定一棵二叉树。 ( ) (18)由二叉树的中序序列和后序序列可以惟一地确定一棵二叉树。 ( )

第 33 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

(19)由二叉树的前序序列和后序序列可以惟一地确定一棵二叉树。 ( ) (20)实现二叉树的按层次遍历算法时需要用到队列结构。 ( ) (21)实现二叉树的遍历算法时不需要用到堆栈结构。 ( ) (22)线索二叉树对应的二叉链表中不存在空的指针域。 ( ) (23)二叉排序树中的任何一棵子树也是二叉排序树。 ( ) (24)一个序列对应的二叉排序树是惟一的。 ( )

(25)按照“逐点插入法”建立的二叉排序树的深度与结点的插入顺序无关。 ( ) (26)在二叉排序树中进行查找的效率与二叉排序树的深度有关。 ( )

(27)在二叉排序树中查找一个结点，查找长度不会超过二叉树的深度。 ( ) (28)给定一组权值，构造出来的哈夫曼树是惟一的。 ( ) (29)哈夫曼树中不存在度为1的结点。 ( )

(30)在哈夫曼树中，权值相同的叶结点都在同一层上。 ( ) 5．2单项选择题。

(1)树型结构最适合用来描述——。

A．有序的数据元素 B．无序的数据元素

C．数据元素之间具有层次关系的数据 D．数据元素之间没有关系的数据 (2)对于一棵具有n个结点、度为4的树而言，——。 A．树的深度最多是n-4 B．树的深度最多是n-3

C．第i层上最多有4x(i-1)个结点 D．最少在某一层上正好有4个结点 (3)“二叉树为空”意味着二叉树————。

A．由一些未赋值的空结点组成 B．根结点无子树 巳不存在 D．没有结点

(4)按照二叉树的定义，具有3个结点的二叉树有——种形态(不考虑数据信息的组合情况)。 A．2 B．3 C．4 D．5

(5)若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，则该树一共有——个叶结点。

A．35 B．28 C．77 D．78

(6)若一棵二叉树有10个度为2的结点，则该二叉树的叶结点的个数是——。 A．9 B．11 C．12 D．不确定

(7)若一棵满二叉树有2047个结点，则该二叉树中叶结点的个数为——。 A．512 B．1024 C．2048 D．4096

(8)深度为h的满二叉树的第i层有——个结点。(i≤h) A．2(i)—1 B．2(i)-1 C．2(h)—1 D．2(h)-1 (9)深度为h的完全二叉树的第i层有——个结点。(i

A．n-1 B．n C．Llog2(n)』 D．Llog2(n)』+1 (11)具有2000个结点的非空二叉树的最小深度为——。 A．9 B．10 C．11 D．12

(12)若某完全二叉树的深度为h，则该完全二叉树中至少有——个结点。 A．2(h) B．2(h)-1 c．2(h)+1 D．2(h—1)

(13)若二叉树的前序序列与后序序列的次序正好相反，则该二叉树一定是——的二叉 树。

第 34 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

A．空或仅有一个结点 B．其分支结点无左子树 C．其分支结点无右子树 D．其分支结点的度都为1

(14)任何一棵非空二叉树中的叶结点在前序遍历、中序遍历与后序遍历中的相对位置——————。 A．都会发生改变 B．不会发生改变

C．有可能会发生改变 D．部分会发生改变

(15)对于一个数据元素序列，按照逐点插入方法建立一棵二叉排序树，该二叉排序树的形状取决于——。

A．该序列的存储结构 B．序列中数据元素的取值范围 C，数据元素的输人次序 D．使用的计算机的软、硬件条件

(16)对一棵二叉排序树进行——遍历，可以得到该二叉树的所有结点按值从小到大排列 的序列。 A．前序 B．中序 C．后序 D．按层次 (17)除了前序遍历(DLR)、中序遍历(LDR)与后序遍历(LRD)外，二叉树的遍历方法还可以有DRL、RDL和RLD三种。对于一棵二叉排序树，采用——遍历方法可以得到该二叉排序树的所有结点按值从大到小排列的序列。·

A．LDR B．LRD C．RLD D．RDL (18)在二叉排序树中进行查找的效率与——有关。

A。二叉排序树的深度 B．二叉排序树的结点的个数 C．被查找结点的度 D．二叉排序树的存储结构

(19)在具有n个结点的二叉排序树中查找一个结点的过程的时间复杂度约为——。 A．O(1) B．O(n) C．O(nz) D．O(10gan)

(20)下列名词术语中，与数据的存储结构有关系的仅是——。

A．完全二叉树 B．满二叉树 C．线索二叉树 D．二叉排序树 (21)平衡二叉树中任意结点的平衡因子只能是——之一。

A．0，1，2 B．0，1 C．-1，+1 D．0，-1，+1 7． 3 填空题。

(1)任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的——。 (2)树的层次定义为——。

(3)度为k的树中第i层最多有——个结点(i≥1)。 (4)深度为h的k叉树最多有——个结点。 (5)非空二叉树一共有——种基本形态。 (6)非空二叉树中第i层最多有——个结点。 (7)深度为h的二叉树最多有————个结点。 (8)具有n个结点的完全二叉树的深度h二——。

(9)若二叉树有N0个叶结点，n2个度为2的结点，则N0与n2的关系是——。

(10)若具有n个结点的非空zX．树有N0个叶结点，则该二叉树有——个度为2的结点，——个度为1的结点。

(11)对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为——，左孩子的编号为——，右孩子的编号为——。

(12)若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有——个指针域，其中有——个指针域用于链接孩子结点，l-个指针域空闲存放着NULL。

(13)二叉树的遍历方式通常有——、——、——和_____四种。

(14)已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为——。 (15)已知某完全二叉树采用顺序存储结构，结点的存放次序为A,B，C,D，E，F，G，H，I，J，该完全二叉树的后序序列为——。

第 35 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

(16)在某二叉树中，若结点A有左孩子Y和右孩子X，则在结点的前序序列、中序序列和后序序列中，结点——一定在结点——的前面。

(17)利用中序线索二叉树进行中序遍历可以不用设置——结构。

(18)对二叉排序树进行——，可以得到由该二叉树中结点组成的按值有序排列的序列。

(19)采用逐点插入法建立序列(54，28，16，34，73，62，95，60，26，43)的二叉排序树后，查找数据元素62共进行——次元素间的比较。

(20)具有N0个叶结点的哈夫曼树共有——个结点。

5.4 若结点A有三个兄弟(包括A本身)，并且B是A的双亲结点。问结点B的度是多少?

5.5 若一棵树有n1个度为1的结点，n2个度为2的结点??nm个度为m的结点，试问：该树一共有多少个叶结点(即度为0的结点个数no)?请写出推导过程。

5. 6 一棵深度为h的满m叉树具有如下性质：第h层上的结点都是叶结点，其余各层上每个结点 都有m棵非空子树。问：

(1)第k层有多少个结点?(1≤k≤h) (2)整棵树有多少个结点?

(3)若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，编号为i的结点的双亲结点的编号是什么?编号为i的结点的第j个孩子结点(若存在的话)的编号是什么?

5.7 一棵度为2的树与一棵二叉树有什么区别?

5.8 请分别画出具有3个结点的树和具有3个结点的 二叉树的所有形态。

5.9 请分别列出如图所示的二叉树的所有叶结点与分支结点，并分别指出各结点的度数以及所 在的层次数。

5.10 若一棵具有n个结点的二叉树采用二叉链表存储结构。试问：该二叉链表中共有多少个空指针域?写出推导过程。

5.11 已知某算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，请写出其前缀形式(利用二叉树的遍历序列)。

5.12 已知某二叉树的前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC，请写出后序序列。 5.13 已知某-'X树的中序遍历序列为CBGEAFHD，后序遍历序列为CGEBHFDA，请画出该二叉树的前序线索二叉树的二叉链表结构的表示。

5.14 已知按前序遍历二叉树的结果为ABC。试问，有几种不同的二叉树可以得到这一遍历结果? 5.15 请按照算法,SORTTREE画出对应于序列{15，20，15，7，9，18，61的二叉排序树。

5.16 给定一组权值W={14，15，7，3，20，4}，请构造出相应的哈夫曼树，并计算其带权的路径长度WPL。

5.17 试证明具有n2个叶结点的哈夫曼树的分支总数为2(N0-1)。

5.18 二叉树的深度采用自然语言形式可以描述为：若二叉树为空，则其深度为0，否则其深度等于左子树与右子树的最大深度加1。若二叉树采用二叉链表存储结构，请写出求该二叉树的深度的递归算法。

5.19 已知二叉树采用二叉链表存储结构，根结点的地址为T。请写出二叉树前序遍历的非递归算法。

第 36 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

5.20 已知两棵二叉树都采用二叉链表存储结构，根结点的地址分别为T1和T2。请写一算法，判断两棵二叉树是否相似(即具有相同的形态)，并给出相应信息。

5.21 已知两棵二叉树都采用二叉链表存储结构，根结点的地址分别为T1和T2。请写一算法，判断两棵二叉树是否是相同的二叉树，并给出相应信息。

5.22 已知二叉树采用二叉链表存储结构，根结点的地址为T。请写一算法，释放该二叉树中所有结点占用的空间。

5.23 已知二叉树采用二叉链表存储结构，根结点的地址为T。请写一非递归算法统计出该二叉树共有多少个度为1的结点?要求：算法中用到的堆栈采用链式存储结构。

5.24 已知非空二叉树采用二叉链表存储结构，根结点地址为T。请写出非递归算法，该算法打印数据信息为item的结点的所有祖先结点。假设数据信息为item的结点不多于一个。

5.25 已知二叉树采用二叉链表存储结构，根结点的地址为T。请写一算法，将该二叉链表结构转换为顺序存储结构。

5.26 已知某具有n个结点的二叉树的前序序列与中序序列分别存放于数组PREOD[n)与INOD [n]中，并且各结点的数据值均不相同。试写一非递归算法生成该二叉树的二叉链表结构。

5.27 已知二叉树采用二叉链表存储结构，根结点地址为了。试写一算法，判断该二叉树是否为完全二叉树，并给出相应信息。

5.28 已知二叉树采用二叉链表存储结构，根结点地址为丁。试写一算法，删去并释放数据值为key的叶结点。

5.29 已知二叉排序树采用二叉链表存储结构，根结点的地址为T。试写一算法，删去数据值小于或等于key的结点。

5.30 已知二叉树采用二叉链表存储结构，根结点的地址为T。试写一算法，算法功能是按层次从上到下，每层从右到左的顺序依次列出二叉树所有结点的数据信息。

5.31 已知二叉树采用二叉链表存储结构，根结点的地址为T。试写一算法，打印该二叉树所有左子树的根结点的数据信息。

5.32 已知二叉树采用二叉链表存储结构，根结点的地址为T。试写一算法，交换二叉树所有左、右子树的位置，即将结点的左子树变成结点的右子树，右子树变成左子树。

5.33 已知二叉树采用二叉链表存储结构，根结点的地址为丁。请写一算法，输出从根结点到某个指定结点的路径上各结点的值。

5.34 已知二叉树采用二叉链表存储结构，根结点的地址为T，请写一算法，判断该二叉树是否是二叉排序树。

5.35 将图7．43所示的树林转换为一棵二叉树。

5.36 分别写出如图7．44所示的树的前序遍历序列与后序遍历序列。

5.37 已知某树林转化为二叉树后所对应的顺序存储结构为请画出该树林。

第 37 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

历年考题

1．在具有n个叶子结点的严格二叉树中，结点总数为（ ）

A．2n+1 B．2n C．2n-1

D．2n-2

2．除根结点外，树上每个结点（ ）

A．可有任意多个孩子、任意多个双亲 B．可有任意多个孩子、一个双亲 C．可有一个孩子、任意多个双亲 D．只有一个孩子、一个双亲

3．具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（ ）个指针域为空。 A．50

B．99 C．100

D．101

4．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（ ）

A．n/2 B．n C．(n+1)/2 D．n+1

6．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（ ）

A．2，14 B．2，15 C．3，14 D．3，15 7.下列陈述中正确的是( )

A.二叉树是度为2的有序树

B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点

D.二叉树中最多只有两棵子树，并且有左右之分

9、前序遍历序列与中序遍历序列相同的二叉树为 (1) ，前序遍历序列与后序遍历序列相同的二叉树为 (2) 。

(1) A、根结点无左子树的二叉树

B、根结点无右子树的二叉树

C、只有根结点的二叉树或非叶子结点只有左子树的二叉树 D、只有根结点的二叉树或非叶子结点只有右子树的二叉树 (2) A、非叶子结点只有左子树的二叉树

B、只有根结点的二叉树

C、根结点无右子树的二叉树

D、非叶子结点只有右子树的二叉树

10、 假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为 (10) 。

(10) A、ABCDEFGHIJ B、ABDEGHJCFI C、ABDEGHJFIC D、ABDEGJHCFI

11、 设某种二叉树有如下特点；结点的子树数目不是2个，则是0个。这样的一棵二叉树中有m(m>O)个子树为0的结点时，该二叉树上的结点总数为 (34) 。

(34) A．2m+l B．2m-1 C．2(m—1) D．2(m+1)

14、二叉树＿A＿。在完全的二叉树中，若一个结点没有＿B＿，则它必定是叶结点。每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的＿C＿，而N的右子女是它在原树里对应结点的＿D＿。二叉排序树的平均检索长度为＿E＿。

供选择的答案：

A：①是特殊的树 ②不是树的特殊形式

第 38 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

③是两棵树的总称 ④是只有二个根结点的树形结构

B：①左子结点 ②右子结点

③左子结点或者没有右子结点 ④兄弟

C～D： ①最左子结点 ②最右子结点 ③最邻近的右兄弟 ④最邻近的左兄弟 ⑤最左的兄弟 ⑥最右的兄弟

E：①O(n) ②o(n) ③O(log2n) ④o(log2n)

15、每一棵树都能唯一地转换为它所对应的二叉树，树的这种二叉树表示对树的运算带来很大的好处。遍历（周游）是树形结构的一种重要运算，二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按___A___次序），后序法（即按___B___次序）和中序法（也称对称序法，即按___C___次序）。这三种方法相互这间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是___D___,而且可得该二叉树所表示的树的先根次序序列是___B___。

供选择的答案

A～C：① R L N ② R N L ③ L R N

④ L N R ⑤ N L R ⑥ N R L

D、E：① E F G H B C D ② F E G H D C B

③ B C D E F G H ④ E F B G C H D ⑤ B E F C G D H ⑥ F E G B H D C 17．若一棵满三叉树中含有121个结点，则该树的深度为________________。

18．设有k个结点，在用哈夫曼算法构造哈夫曼树的过程中，若第i次合并时已找到权最小的结点x和权次小的结点y，用T［x］.wt表示结点x的权值，已知T［x］.wt=m, T［y］.wt=n，则合并成新的二叉树后给新根结点的权值赋值的语句为_____________。 19．在下列树中，结点H的祖先为_____________。

20．设一棵二叉树中度为2的结点数为10，则该树的叶子数为________________。 21．如图所示的二叉树，若按后根遍历，则其输出序列为________________。

22.在n个结点的线索二叉链表中，有________个线索指针。

23、一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度h如何用n来表示（注意n可能为0）？ 24．画出下列二叉树的二叉链表表示图。（6分）

第 39 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

25.已知树T的先序遍历序列为ABCDEFGHJKL，后序遍历序列为CBEFDJIKLHGA。请画出树T。

27．已知树如右图所示， （1）写出该树的后序序列； （2）画出由该树转换得到的二叉树。

28．分别写出下列二叉树的先根、中根、后根遍历序列。（6分）

第六章 图

迪杰斯特拉算法如下：

SHORTEST—PATH(intcost[][n]，intv，intn，intdist[]，intpath[)) {

ihti，N，u，count，pos[n]； for(i=0;i

s[i]=0； ／x标记数组置0 x／

dist[i]=cost[V][i]； ／。将邻接矩阵第v行元素依次送dist数组x path[i][0]=v； ／x源点v到各顶点的路径置初值。／ pos[i]=0； ／。第i条路径的位置计数器置初值x／ } ／x对辅助数组进行初始化。／ s[v]=l；

count=1; ／x计数器赋初值1 x／

while(count

第 40 页 共 63 页

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