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

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

测试一下自己的水平

一、判断题 (每小题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 页

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

}

6．下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。 void union (LinkList La, LinkList Lb) {

{ } if (pb) }

四、程序设计

1、设某头指针为head的单链表的结点结构说明如下：（6分） typedef struct node1 {

int data; struct node1*next

(3) ; if (pa -> data data) { pre = pa; pa = pa -> next;} else if (pa -> data > pb ->data) { (1) ; } else

{q = pb; pb = pb -> next; free (q); }

pre = pb; pb = pb -> next; (2) ;

//本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中 LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pd)

}node;

试设计一个算法void change (node*head),将该单链表中的元素按原单链表相反的次序重新存放，即第一个结点变成最后一个结点，第二个结点变为倒数第二个结点，如此等等。 2．设某带头结头的单链表的结点结构说明如下： typedef struct nodel {

int data;

struct nodel*next;

第 16 页 共 63 页

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

}node;

试设计一个算法：void copy(node*head l, node*head 2)，将以head 1为头指针的单链表复制到一个不带有头结点且以head2为头指针的单链表中。（6分） 3、、设带表头结点的双向链表的定义为 typedef int ElemType;

typedef struct dnode { //双向链表结点定义 ElemType data; //数据

struct dnode * lLink, * rLink; //结点前驱与后继指针 } DblNode;

typedef DblNode * DblList; //双向链表 试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。

4、阅读以下程序说明和C程序，将应填入程序中（n） 处的字句，写在答卷的对应栏内。

[程序说明]

本子程序利用递归法判别用链表表示的两个非递归链表是否相等. 程序中的非递归列表定义为: ⑴无元素的空列表;

⑵由元素序列组成的一个列表,其中的元素可以是一个字符,?或者是满足本定义的一个列表. 这种列表的一个例子是: Ｓ

┌───┐ ┌─┬─┬─┐ ┌─┬─┬─┐ │ ├→┤0 │ａ│ ├-→┤１│││＾│ └───┘ └─┴─┴─┘ └─┴┼┴─┘

┌──────┘

│ ┌─┬─┬─┐ ┌─┬─┬─┐ └→┤0 │ｂ│ ├→┤０│c │＾│ └─┴─┴─┘ └─┴─┴─┘

列表S由两个元素组成：第一个元素是字符a (标志为0)；第二个元素是另一个列*表(标志为1),该元素又有两个元素组成(标志为0),分别为字符b和字符c.

在两个列表中,若它们的元素个数相等,且表中元素依次相同,则两个列表相等(子程序回答1),否则不相等(子程序回答0).

[程序]

typedef struct lnode

{ int tag; union

{ char data;

struct lnode *dlink; } un;

struct lnode *link; } listnode;

int equal(s,t) listnode *s,*t; { int x,res; if(s==t) __(1)__ ;

else if( __(2)__ )

第 17 页 共 63 页

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

if( __(3)__ ) { if(!s->tag) x= __(4)__ ; else

x= __(5)__ ;

if(x) return (__(6)__); }

return(0);

}

5、阅读下列函数说明和Ｃ代码，将应填入其中__(n)__处的字句写在答卷的对应栏内。 【函数1.1说明】 设链表结点的类型为

typedef struct elem{ int val；

struct elem *next； }intNode；

函数merge(int *a，int *b)是将两个升序链表a和b合并成一个升序链表。 【函数1.1】

intNode *merge(intNode *a，intNode *b) { intNode *h=a，*p，*q； while(b)

{ for (p=h；p && p→val< b→val；q=p，p = p→next)； if (p = = h) __(1)__；else __(2)__； q=b；b=b→next； __(3)__； }

return h； }

【函数1.2说明】

递归函数dec(int a[]，int n)判断数组a[]的前n个元素是否是不递增的。不递增返回１，否则返回0。 【函数1.2】

int dec(int a[]，int n) { if (n<=1) __(4)__；

if (a[0]

}

第三章 栈和队列 习题

4．1 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)堆栈和队列都是特殊的线性表。 ( )

(2)堆栈和队列都将插入和删除操作限制在表的端点处进行。 ( ) (3)只允许在表的一端进行插入和删除操作的线性表称为堆栈。 ( )

第 18 页 共 63 页

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

(4)没有元素的堆栈称为空栈，空栈用不着栈顶指针。 ( ) (5)只要堆栈不空，就能任意删除堆栈的元素。 ( )

(6)堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。 ( ) (7)n个元素进栈的顺序一定与它们出栈的顺序相反。 ( ) (8)对采用链式存储结构的堆栈进行操作不必判断溢出。 ( )

(9)给出顺序堆栈的栈顶元素位置的指针是一个指针类型的变量。 ( )

(10)判断顺序堆栈是否为空的标志是top是否等于0(top为栈顶指针)。 ( ) (11)插入和删除操作比较简单是链接堆栈和链接队列的优点之一。 ( ) (12)n个元素进队的顺序与它们出队的顺序一定是相同的。 ( )

(13)没有任何元素的队列称为空队。空队用不着队头指针与队尾指针。 ( ) (14)元素进出队列一定满足“先进先出”的规律。 ( ) (15)链接队列不存在溢出问题。 ( )

(16)在链接队列中删除一个元素是在链表的最前端进行的。 ( ) (17)采用循环链表作为存储结构的队列称为循环队列。 ( ) (18)堆栈和队列都可以用来解决递归问题。 ( ) (19)堆栈和队列都不适合采用散列存储方法。 ( )

(20)无论是顺序队列还是链接队列，插入、删除操作的时间复杂度都是O(1)。 ( ) 4．2单项选择题。

(1)堆栈和队列的共同之处在于它们具有相同的——。

A．逻辑特性 B．物理特性 C．运算方法 D．元素类型 (2)堆栈和队列都是特殊的线性表，其特殊性在于_______。 A．它们具有一般线性表所没有的逻辑特性 B．它们的存储结构比较特殊 C．对它们的使用方法做了限制 D．它们比一般线性表更简单

(3)若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是——。

A．2，4，3，1，5 B．2，3，1，5，4 C．3，1，4，2，5 D．3，1，2，5，4 (4)某队列初始为空，若它的输入序列为a，b，c，d，它的输出序列应为——。 A．a，b，c，d B．d，c，b，a C．a，c，b，d D．d，a，c，b

(5)当4个元素的进栈序列给定以后，由这4个元素组成的可能的出栈序列应该有——。 A．24种 B．17种 C．16种 D．14种

(6)设n个元素的进栈序列为1，2，3，?，n，出栈序列为p1，p2，p3，?，pn，若Pi=n，则B(1≤i

A．为i B．为n-i C．为n-i+l D．有多种可能

(7)设n个元素的进栈序列为p1，p2，p3，?，pn，出栈序列为1，2，3，?，n，若Pn=l，则n(1≤i< n)的值——。

A．为i B．为n-i C．为n-i+l D．有多种可能

(8)若堆栈采用顺序存储结构，正常情况下，往堆栈中插入一个元素，栈顶指针top的变化是 ______. A．不变 B．top=0 C．top-- D．top++

(9)若堆栈采用顺序存储结构，正常情况下，删除堆栈中一个元素，栈顶指针top的变化是 ______. A．不变 B．top=0 C．top-- D．top++

(10)若队列采用顺序存储结构，元素的排列顺序——。 A．与元素的值的大小有关

B．由元素进入队列的先后顺序决定

第 19 页 共 63 页

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

C．与队头指针和队尾指针的取值有关 n与作为顺序存储结构的数组的大小有关 (11)“链接队列”这一概念不涉及——。

A．数据的存储结构 B．数据的逻辑结构 C.对数据进行的操作 D．链表的种类

(12)若堆栈采用链式存储结构，栈顶指针为top，向堆栈插入一个由p所指的新结点的过程是依次执行：——，top=p。

A．p=top B．top=p C．p->link=top D．top->link=p

(13)若非空堆栈采用链式存储结构，栈顶指针为top，删除堆栈的一个元素的过程是依次执行：p=top，——，free(p)。

A．top=p B．top=p->link C．p=top->link D．p=p->link

(14)若队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，向队列中插入一个由p所指的新结点的过程是依次执行：——，rear=p。

A．rear=p B．front=p C．rear->link=p D．front->link=p

(15)若非空队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，删除队列的一个元素的过程是依次执行：p=front，——，free(p)。

A．rear=p B．rear=p->link C．rear=p->link D．front=p->link

(16)在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列队空的条件是——。

A．front=rear+1 B。rear=front+1 C．front--rear D．b叭t：0

(17)若描述某循环队列的数组为ClUELIE[M]，当循环队列满时，队列中有——个元素。 A．M B．M-1 C．M十1 D．M+2

(18)在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓 冲区应该是一个——结构。

A．线性表 B．数组 C．堆栈 D．队列

(19)设计一个递归问题的非递归算法通常需要设置——结构。 A．线性表 B．数组 C．堆栈 D．队列 (20)中缀表达式A-(B+C／D)*E的后缀形式是——。

A．ABC+D／*E— B．ABCD／+E*— C．AB-C十D／E* D．ABC-+D／E* 4．3 填空题。

(1)堆栈和队列的逻辑结构都是——结构。

(2)堆栈的插入和删除操作都是在——位置进行，而队列的插入操作在——进行，删除操作在——进行。 (3)对某堆栈执行删除操作时，只有在——情况下，才会将栈底元素删除。

(4)在具体的程序设计过程中，堆栈的顺序存储结构一般是利用一个——描述的，同时还要定义一个整型变量来——。

(5)若堆栈采用顺序存储结构，在不产生溢出的情况下往堆栈中插人一个新元素，首先——，然后——。 (6)若队列采用顺序存储结构，未溢出时插入一个元素首先——，然后再——。 (7)当堆栈的最大长度难以估计时，堆栈最好采用——存储结构。 (8)递归算法都可以通过设置——机制改写成等价的非递归算法。 (9)中缀形式的算术表达式A+(B-C)／D*E的后缀形式为——。

(10)后缀形式的算术表达式ABCD/-E*+的中缀形式为——。

4．4 已知堆栈采用链式存储结构，初始时为空，请画出a，b，c，d四个元素依次进栈以后该堆栈的状态，

然后再画出此时的那个栈顶元素出栈后堆栈的状态。

第 20 页 共 63 页

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

4．5 若按从左到右的顺序依次读人已知序列{a，b，c，d，e，f，g1中的元素，然后结合堆栈操作，能得

到下列序列中的哪些序列(每个元素进栈一次，下列序列表示出栈的次序)? {d，e，c，f，b，g，a} {f，e，g，d，a，c，b}

{e，f，d，g，b，c，a} {c，d，b，e，f，a，g}

4．6 设有编号1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，请写出这四辆列车开出车站的

所有可能的顺序。

4．7 设STACK[M]为n(n>2)个堆栈共享。各栈栈顶指针为top[n]，分别指出各栈栈顶元素的位置；栈底

指针为bot[n+1]，分别指出各栈栈底元素的位置。初始时， bop[i]=bot[i]=i*ROUND(M／n—0．5) (i=1，2，....，n)

其中，ROUND()为四舍五人取整函数。请写一算法，该算法向任意指定的第i个堆栈插入一个新的元

素x。仅当M个空间全部占用时才产生溢出，并报告相应信息(1≤i≤n)。

4．8 设中缀表达式E存放于字符数组中，并以@作为结束标志。请写出判断一个中缀表达式E中左、右

圆括号是否配对的算法。

4．9 写出将中缀表达#(a+b)／c-d#变换为后缀表达式的过程中，每读到一个单词时堆栈的状态(#为中缀表

达式的左、右分界符)。

4．10 已知Ackerman函数定义如下：

(1)写出递归算法；

(2)利用堆栈写出非递归算法；

(3)根据非递归算法，求出A(：K(2，1)的值。

4．12 已知求两个正整数m和n的最大公约数的过程可以表达为如下递归函数：

请写出求解该递归函数的非递归算法。m MOD n表示m对n取模。 4．13 假设以数组Q[M]存放循环队列的元素，同时设置变量rear与qlen分别指示循环队列中队尾元素的位置和队列中元素的个数。请给出此循环队列的队满条件，并写出相应的进队与出队算法(在出队算法中要求返回队头元素)。

4．14 编写一非递归算法，对于给定的十进制整数n，打印出对应的r进制整数(2≤r≤16，r<>10)。

栈和队列 历年试题

1．栈和队列都是（ ） A．限制存取位置的线性结构 C．链式存储的线性结构

B．顺序存储的线性结构

D．限制存取位置的非线性结构

2．若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（ ）

A．1和n+1 B．1和n/2 C．－1和n D．－1和n+1

3.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( ) A.4 B.5 C.6 D.7

4．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为________________，不可能得到的出栈序列为________________。

第 21 页 共 63 页

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

5．在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现： _____________； sq -> data[sq -> top]=x；

6．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的_____________。 7．如图所示，设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为_______________。

8．队列中允许进行删除的一端为________________。 9.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，

得到的输出序列为________。 10、设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，

则顺序栈的容量至少应为多少？

11．如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可

能的输入序列。（5分）

第四章 数组补充内容

3．3．2 对角矩阵的压缩存储

所谓对角矩阵是指矩阵中的所有非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在主对角线上、下方对称的若干条对角线上的元素之外，其余元素均为零。

下面给出的矩阵B就是一个对角矩阵(确切地说是一个三对角矩阵，这里，我们仅以三对角矩阵为例子)。

三对角矩阵一共有3n—2个非零元素。我们可以按照某个原则(或者以行序为主序的分配方式，或者以列序为主序的分配方式，或者按照对角线的顺序进行分配)将对角矩阵B的所有非零元素压缩存储到一个一维数组LTB[3n—2]中。这里，不妨仍然以行序为主序的分配方式对B进行压缩存储，当B中任一非零元素Bij与LTB[k]之间存在着如下一一对应关系k=2*i+j-3时，则有Bij=LTB[k]。称LTB[3n—2]为对角

第 22 页 共 63 页

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

矩阵B的压缩存储，如下图所示。

上面讨论的几种特殊矩阵中，非零元素的分布都具有明显的规律，因而都可以被压缩 存储到一个一维数组中，并且能够确定这些矩阵的每一个元素(或非零元素)在一维数组 中的位置。但是，对于那些非零元素在矩阵中的分布没有规律的特殊矩阵(如稀疏矩阵)， 则需要寻求其他的方法来解决压缩存储问题。 3．5 稀疏矩阵的十字链表表示

上一节讨论了用三元组表的形式来存储一个稀疏矩阵的方法。但是，在实际应用中，当稀疏矩阵中非零元素的位置或者个数经常发生变化时，使用三元组表就不太方便了。

本节将介绍稀疏矩阵的另一种表示方法，即十字链表表示。

如何用链表形式来表示一个稀疏矩阵呢?方法之一就是将所有非零元素以行序为主序方式(当然也可以以列序为主序方式)采用循环链表链接起来。链结点的构造由四个域组成：

其中i,j分别表示某一个非零元素所在的行号与列号；value表示该非零元素的值； link域用来指向下一个非零元素所在的链结点，它是一个指针。另外，再设置一个链表头结点，其构造如下：

其中，m，n分别表示稀疏矩阵的行数与列数；t为稀疏矩阵非零元素的总个数；link域用来指向第一个非零元素对应的链结点。

例如，对于如下一个稀疏矩阵：

若采用行序为主序方式(每行又按列的先后顺序)依次将所有非零元素链接起来，则得到如图3．4所示的一个带有头结点的循环链表。

这种表示方法最明显的一个缺点就是，当要访问某行某列的一个非零元素时，必须从链表的最前面那个链结点开始进行搜索，其效率之低可想而知。

一个能提高访问效率的方法就是采用十字链表表示。这种方法为稀疏矩阵的每一行设置一个单独的行循环链表，同样也为每一列设置一个单独的列循环链表。这样，稀疏矩阵中的每一个非零元素同时包含在两个链表中，即包含在它所在的行链表与所在的列链表中，也就是这两个链表的交汇处。

对于一个mXn的稀疏矩阵，分别建立m个行的循环链表与n个列的循环链表，每个非零元素用一个链结点来存储。链结点的结构可以设计为

第 23 页 共 63 页

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

其中，rOW，c01，value分别表示某非零元素所在的行号、列号和相应的元素值；down与right分别称为向下指针与向右指针，它们分别用来链接同一列中的与同一行中的某非零元素结点。也就是说，稀疏矩阵中同一行的所有非零元素是通过right指针链接成一个行链表，同一列中的所有非零元素是通过down指针链接成一个列链表。而对每一个非零元素而言，它既是某个行链表中的一个链结点，同时又是某个列链表中的一个链结点，这个非零元素好比处在一个十字路口，故称这种链表表示为十字链表表示法。 作为链表，应该用某种方式能访问表中的第一个结点，为此，对于m个行链表，分别设置m个行链表表头结点。表头结点的构造与链表中其他链结点一样，只是令row与凹1域的值均为0，right域指向相应行链表的第一个链结点。同理，对于n个列链表，分别设置n个列链表表头结点。头结点结构也同其他链结点一样，只是令rOW与c01的值均为0，down域指向相应列链表的第一个链结点。另外，通过value域把所有这些表头链结点也链接成一个循环链表。 十字链表中的链结点类型可以描述如下： typedefstructnode{ int row,col； union{

ElemType val； struct node'ptr； 1value；

struct node 1 right，'down；

1 CNode，xCrossLink； ／‘定义十字链表结点类型x／

从m个行链表的表头结点与n个列链表的表头结点的设置情况看到，行链表的头结点只用了right域作为指针，而列链表的头结点只用了down域与 value域，其他域没有使用。因此，可以设想原来的(m+n)个头结点实际上可以合并成 MAX(m，n)。为此，再设置一个结点作为头结点链表的头结点，不妨称之为总头结点，其结构如下所示： m t n Link

其中，m，n分别为稀疏矩阵的行数与列数；t为非零元素的总个数；1ink指向头结点链表的第一个头结点。

总头结点的类型可以如下描述： typedefstruct{

int m，n，t,nil； CrossLink x link；

}HNode,*HLink； ／x定义十字链表总头结点类型x／ ‘

综上所述，若给出一个稀疏矩阵B如下，则它的十字链表表示如图3．5所示。

第 24 页 共 63 页

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

下面给出创建一个具有m行n列、有t个非零元素的稀疏矩阵的十字链表的算法。 稀疏矩阵用三元组表的形式作为输入。首先输入稀疏矩阵的行数、列数以及非零元素总个数(m，n，t)，然后依次读入个三元组。算法中用到了一个辅助数组hdnode [MAX(m，n)]。其中，hdnode[i]用来分别存放第i列(也是第i行)链表的头结点的指针 (1≤i≤MAX(m，n))。 #defineMaxNl00 HLinkMREAD() {

HLinkHEAD，p，last，hdnode[MaxN]； iht m,n t，k，i，Current_row， int rrow,ccol，val；

scanf(\％d％d％\，&n，&n，&t)； ／x读入矩阵的行、列和非零元素的个数‘／ if(t<=0)

return NULL； k=(m>n)?m：n；

第 25 页 共 63 页

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

for(i=0；i

p=(HLink)malloc(sizeof(HNode))； hdnode[i]=p； p->row=0； p->col=0；

p->value.ptr=P； p->rlght=p； p->down=p；

} ／*建立k个头结点；初始时第i个头结点的地址存放于hdnode[i-1]中x／ Current_row=1； last=hdnode[0];

for(i=1；i<=t；i++){

scanf(\％d％d％d\，&rrow,&ccol，&val)； ／x读人一个某非零元素的三元组x／ if(rrow>current_row){

last—>right=hdnode[Current_row—1]； current_row=rrow； last=hdnode[rrow—1]； }

p=(CrossLink)malloc(sizeof(CNode))； ／x申请一个新的链结点空间x／ p—>row=rrow； p->col=ccol；

p—>value.val=val；

last->right=p； ／x生成一个新的链结点x／ last=p；

hdnode[ccol—1)->value．ptr->down=p； ／‘将新结点链接到相应行链表中，／ kfnode[ccol—1)->value．ptr=p； ／x将新结点链接到相应列链表中，／ ； if(t!=0)

last->right：hdnode[current—row—1]； ／x封闭最后——行x／

for(i=0;ivalue．ptr->down=hdnode[i]；／x封闭所有列链表x／

HEAD=(HLink)malloc(sizeof(HNode))； ／，申请一个总的头结点x／ HEAD->m=m； HEAD->n=n； HEAD->t=t；

for(i=0；i

hdnode[i]->value.ptr=nanode[i+1]； if(k==0)

HEAD->value.ptr=HEAD； else{

hdnode[k-1]->value.ptr=HEAD； HEAD->value.ptr=hdnode[0]；

return HEAD； }

第 26 页 共 63 页

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

第四章 广义表 字符串 数组

4．1单项选择题。

(1)空的广义表是指广义表——。 A．深度为0 B。尚未赋值

C．不含任何原子元素 D．不含任何元素 (2)广义表中元素分为——。 A．原子元素 B．表元素

C．原子元素和表元素 D．任意元素 (3)广义表的长度是指——。

A．广义表中元素的个数 B．广义表中原子元素的个数 C．广义表中表元素的个数 Di广义表中括号嵌套的层数 (4)广义表的深度是指——。

久广义表中元素的个数 B．广义表中原子元素的个数 C．广义表中表元素的个数 D．广义表中括号嵌套的层数 (5)在一个长度为n，包含m个原子元素的广义表中，——。

A．m和n相等 B．m不大于n C．m不小于n D．m与n无关 (6)广义表A=(( )，(a)，(b，(c，d)))的长度为——。 A．2 B．3 C．4 D．5

(7)广义表A：(( )，(a)，(b，(c，d)))的深度为——。 A．2 B．3 C．4 D．5

4．2有人说，m*n阶矩阵是一种广义表结构，你认为如何?请说明你的理由。 4．3请分别写出下列各广义表的长度与深度： (1)A=((a))

(2)B=(a，(b，c，d)，e，()) (3)C=(x，((y)，B，A)) (4)D=(A,D)

4．6 试写出判断两个广义表是否相等的递归算法。

4．7 根据本章介绍的m元多项式的表示方法，试写出一个m元多项式相加的算法。 4．1 请回答空串与空格串有何区别。

4．2 两个字符串相等的充分必要条件是什么?

4．3 已知字符串S采用链式存储结构，链结点大小为1。试写出求该串长度的算法。

4．4 已知字符串S1与S2都采用链式存储结构，链结点大小为1。试写出判断S1与S2是否相等的算法。若S1与S2相等，算法返回1否则返回0。

4．5 设串S，S1，S2分别采用顺序存储结构，长度分别为len，lenl，len2。试写一算法，用串S2替换串S中的子串S1。

4．6 设串采用链式存储结构，链结点大小为1。试写出删除S中从第i个字符开始连续k个字符的算法。 4．7 在字节编址的机器中，字符串S1与S2分别存放在字符数组S饥M1]与S2[M2]中(LEN(S1)≤M1，LEN(S2)≤M2)，并以，@，为串的结束标志。试写一算法，求在S1中第一次出现而在S2中不出现的字符的位置。

4．8 已知字符串的存储结构同

4．7题，并且有LEN(S1)=M，LEN(S2)=N,试写一算法，从S1中位置k开始插入字符串S2，并且取代S1中从第k个字符开始的连续t个字符。设k+1

第 27 页 共 63 页

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

4．9 已知字符串存放于字符数组S[M]中，并以’@’为串的结束标志。试写一算法，判断该字符串是否是回文(即正读与反读相同)。若字符串是回文，算法返回1，否则返回0。

4．10 根据你所确定的一种存储结构设计一个算法，该算法的功能是求串S中出现的第一个最长重复子串的位置与长度。

4．11 已知字符串采用链式存储结构，链结点大小为1。对于给定的字符串S1与S2，请写一算法，求在S1中第一次出现，而在S2中不出现的所有字符。

第四章 各种考试试题

数组部分

选择题

(1)数组是一种线性表结构。 ( )

(2)数组最基本的操作是插入和删除。 ( ) (3)对数组的操作是基于数组下标进行的。 ( ) (4)具有特殊用途的矩阵称为特殊矩阵。 ( )

(5)只需存储n阶对称矩阵的下三角部分的元素。 ( )

(6)在n阶三对角矩阵中，矩阵的每一列都有3个非零元素。 ( ) (7)稀疏矩阵的特点就是矩阵中的元素较少。 ( )

(8)采用三元组表方法存储稀疏矩阵的优点之一是可以随机地访问矩阵中的每一个非零元 素。 ( )

(9)用一维数组存储特殊矩阵的目的是为了节省存储空间。 ( )

(10)从理论上说，任何一个矩阵都可以采用三元组表方法进行存储。 ( ) 填空题。

(1)一般情况下，数组最基本的操作是——。

(2)一个m行n列的矩阵可以看成是长度为——的线性表，表中的每一个元素是长度为 m的线性表。

(3)一个m行n列的矩阵可以看成是长度为——的线性表，表中的每一个元素是长度为n的线性表。 (4)已知二维数组A(4)[6]采用行序为主序方式存储，每个元素占用4个存储单元，该数组一 共占用了——个存储单元。

(5)已知二维数组A[4爪6]采用行序为主序方式存储，每个元素占用3个存储单元，并且 A10爪0]的存储地址为1200，元素A12)14]的存储地址是——。

(6)已知二维数组A14爪6]采用列序为主序方式存储，每个元素占用4个存储单元， 并且A[3][4]的存储地址为1234，元素A[0][0]的存储地址是——。 (7)对特殊矩阵采用压缩存储方法的目的是——。

(8)一个20阶五对角矩阵一共有——个元素，其中有——个非零元素。

(9)将n阶三对角矩阵A中所有非零元素按照行序为主序方式依次存放于数组B中，非零元素A[i][j]在B中的位置是——。 3．3单项选择题。 (1)所谓稀疏矩阵是指——的矩阵。

A．零元素较多且分布无规律 ·B非零元素较少 C．元素较少 D．不适合采用二维数组表示 (2)下面的说法中，不正确的是——。

A．只需存放对称矩阵中包括主对角线元素在内的下(或上)三角部分的元素即可 B‘只需存放对角矩阵中的非零元素即可

第 28 页 共 63 页

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

C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储

D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储 (3)与三元组表方法相比，稀疏矩阵采用十字链表表示的优点在于——。 A．便于实现增加或减少矩阵中非零元素的操作 B．便于实现增加或减少矩阵元素的操作 C．节省存储空间

D.可以更快地查找到某个矩阵元素

(4)对稀疏矩阵采用压缩存储，其缺点之一是——。 A．无法判断矩阵的行数和列数

B．无法根据行列号计算矩阵元素的存储地址 C．无法根据行列号查找某个矩阵元素

D．使得矩阵元素之间的逻辑关系更加复杂

(5)将一个20阶的五对角矩阵中所有非零元素压缩存储到一个一维数组中，该一维数组至少应该有——个数组元素。

A．90 B．92 C．94 D．96

(6)将10阶三对角矩阵中的所有非零元素按照行序为主序方式依次存放于一维数组中，矩阵的第7行第8列的元素在该一维数组中————。

A．是第22个数组元素 B．是第21个数组元素 C．是第20个数组元素 D．不存在

(7)将10阶三对角矩阵中的所有非零元素按照行序为主序方式依次存放于一维数组中，一维数组中的第18个数组元素是矩阵——的那个元素。

A．第6行第3列 B．第6行第7列 C。第7行第7列、 D．第7行第6列

(8)若将n阶对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，则该对称矩阵在B中占用了一个数组元素。 A．n2 B．n*(n-1) C．n*(n+1)/2 D．n*(n-1)／2

(9)若将n阶三对角矩阵A按照行序为主序方式将所有非零元素依次存放在一个一维数组B中，则该三对角矩阵在B中占用了——个数组元素。 A．n2 B．3n-2 C．3n D．3n+2

(10)若将对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，那么，A中某元素Aij(i

C．(j*(j—1))／2十i—1 D．(j*(j-1))/2—i—1

(11)对三对角矩阵A采用压缩存储的方法将所有非零元素存放于一个一维数组BC3n—2]中，某非零元素Aij在B中位置是——。

A．2*i+j-2 B．2*i+j+2 C．2*i+j-3 D．2*i+j-1

4.4已知一元多项式f(x)=4X(6)—5X(4)十7X(2)-1，请写出f(x)的一维数组表示的两种方法。

4.5按照压缩存储的思想，对于一个具有t个非零元素的mXn阶稀疏矩阵，若采用三元组表存储方法，t到达什么程度时这样做才有意义?

4.6 已知稀疏矩阵A[6][5]如下所示，请分别写出它的三元组表表示与十字链表表示。

第 29 页 共 63 页

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

4.8 已知稀疏矩阵A为m行n列，请写出将该稀疏矩阵转换为三元组表表示的算法。

4.9 设A为一个n阶上三角矩阵，若将此三角矩阵的所有非零元素按照列序为主序分配方式存放在数组B[n*(n+1)/2]中，a11存放于B[0]中，请写出此三角矩阵的非零元素Aij(i≤j)的寻址公式。

4.10 请写算法，该算法将一个n阶矩阵A主对角线以下的所有元素(不包括主对角线上的元素)按照列序为主序方式依次存放于一个一维数组B中。

4.11 请写算法，该算法将一个n阶矩阵A主对角线以下的所有元素(包括主对角线上的元素)按照行序为主序方式依次存放于一个一维数组B中。

4.12 已知n阶对称矩阵A的下三角部分元素按照行序为主序方式依次存放于一个一维数组B[m]中，请写出输出该对称矩阵的算法。

4.13 已知某二维数组A[n][n]按照行序为主序方式依次为每个数组元素获取值，请写一算法，求该数组两条对角线上的元素之乘积。

4.14 已知二维数组A[m][n]，请写一算法，求出该数组最外围一圈的元素之和。

已知二维数组A[n][n]，请写一时间复杂度为O(1)的算法，将该数组按照顺时针方向旋转若稀疏矩阵采用三元组表表示，请写出求两个具有相同行、列数的稀疏矩阵相加的算法。

4.17 若在m*n阶的矩阵A中有一元素Aij满足条件：Aij既是第i行元素的最小值，同时又是第j列元素的最大值，此时称Aij为A的鞍点。试写出求矩阵鞍点的算法。若矩阵中不存在鞍点，应给出相应信息。 4.18 编写一个将十字链表表示的矩阵A转置的算法，转置的结果仍采用十字链表表示。 4.19 若稀疏矩阵采用十字链表表示，请设计两个稀疏矩阵进行相乘运算的算法，即已知A矩阵与B矩阵，求矩阵C=A*B，并且要求C也采用十字链表表示。 4.20 试设计一个算法，将数组A[n]中的元素循环右移k位，要求只用一个元素大小的附加空间。 4.21 试设计一个时间复杂度为O(n)的算法，该算法将数组A[n]中的元素循环右移k位，要求采用尽可能少的附加空间。

4.22 n阶三对角矩阵A按行序为主序分配方式把所有非零元素存放于数组B[3n—2]中，Aij存放于B[0]中，请设计一个算法以确定数组B中元素～的值(1≤i，j≤n)。

4.23 已知存放整型数据的一维数组A[n]，请写一时间复杂度为O(n)的算法，该算法将数组调整为左右两部分，使得左边所有元素均为奇数，右边所有元素均为偶数。

4.24 已知具有n个数组元素的一维数组A，请写一算法，将该数组中所有值为0的元素都依次移到数组的前端A[i](0≤i≤n-1)。

综合部分

1．执行下列程序段后，串X的值为（ ）

S=〞abcdefgh〞; T=〞xyzw〞; substr (X,S,2,strlen(T)); substr (Y,S, stelen(T),2); strcat (X,Y);

第 30 页 共 63 页

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

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 页

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