数据结构精品课程习题

更新时间：2024-06-13 02:34:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

数据结构精品课程网站推荐度：
相关推荐

第一章绪论

一、单项选择题

1、下列说法正确的是（）。

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

B.数据元素是数据项中不可分割的最小单位 C.数据可由若干个数据元素构成 D.数据项可由若干个数据元素构成

2、数据元素是数据的基本单位，其内（）数据项。

A.只能包括一个 B.不包含 C.可以包含多个 D.可以包含也可以不包含 3、逻辑关系是指数据元素的（）。

A.关联方式 B.存储方式 C.结构 D.数据项 4、逻辑结构是（）关系的整体。

A.数据元素之间逻辑 B.数据项之间逻辑 C.数据类型之间 D.存储结构之间 5、数据结构的基本任务是（）。

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

6、下列数据组织形式中，（）的结点按逻辑关系依次排列形成一个“铰链”。

A.集合 B.树形结构 C.线性结构 D.图状结构 7、一个存储结点存放一个（）。

A.数据项 B.数据元素 C.数据结构 D.数据类型

8、每个结点只存储一个数据元素，存储结点存放在连续的存储空间，该存储方是（）存储方式。

A.顺序 B.链式 C.索引 D.散列

9、每个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（）

存储方式。

A.顺序 B.链式 C. 索引 D.散列

10、每个存储结点只含有一个数据元素，存储结点存放在连续的存储空间另外有一组指明结点存储位置的表，该存储方式是（）存储方式。

A.顺序 B.链式 C.索引 D.散列

11、每个存储结点只含有一个数据元素，存储结点均匀地存放在连续的存储空间，使用函数值对应结点存储位置，该存储方式是（）存储方式。

A.顺序 B.链式 C.索引 D.散列

12、数据结构可以形式化地定义为（S，△）其中S指某种逻辑结构，△是指（）

A.S上的算法 B.S的存储结构

C.在S上的一个基本运算集 D.在S上的所有数据元素

13、算法能正确的实现预定功能的特性称为（）。

A.正确性 B.易读性 C.健壮性 D.高效率 14、算法的便于阅读和理解的特性称为（）。

A.正确性 B.易读性 C.健壮性 D.高效率

15、算法在发生非法操作时可以作出处理的特性称为（）。

A.正确性 B.易读性 C.健壮性 D.高效率 16、算法可以达到所需时空的特性称为（）。

A.正确性 B.易读性 C.健壮性 D.高效率 17、下列时间复杂度中最坏的是（）。

A.O（1） B.O（m） C.O(1og2n) D.O(n2) 18、下列时间复杂度中最好的是（）。

A.O（1） B.O（m） C.O(1og2n) D.O(n2) 19、下列算法的时间复杂度是（）。 for (i=0;i

c[i][j]=i+j;

A.O（1） B.O（m） C.O(1og2n) D.O(n2) 20、下列算法的时间复杂度是（）。 for (i=0;i

A.O（1） B.O（m） C.O(1og2n) D.O(n2)

21、下列存储A、B、C、D、E的方式是（）存储方式。

地址元素

1000 1001 1002 1003 1004 ? A B C D E A.顺序 B.链式 C.索引 D.散列 22、在计算机中存储一个数据元素的位串称为（）。

A.结点 B.数据项 C.数据域 23、记录中的各个数据项的类型（）。

A.必须相同 B.不必相同 C.不能相同 D.不确定

D.字符串

二、填空题

1、从数据结构S中找出满足条件的结点在S中位置的运算是。 2、从数据结构S中读出结构中指定位置上内容的运算是。 3、从数据结构S中的某指定位置上增加一个新结点的运算是。 4、下列程序段的时间复杂性的量级为。 for (i=1;i

5、从数据结构

S中修改结构中某指定结点内容的运算

是。三、应用题

1、简述数据与数据元素的关系与区别。

2、说出数据结构中的四类基本逻辑结构，并说明哪种关系最简单、哪种关系最复杂。

3、画出线性结构的示意图。 4、画出树形结构的示意图。 5、画出图状结构的示意图。

6、什么是逻辑结构、存储结构？有哪几种存储结构？

7、简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。 8、简述逻辑结构与存储结构的关系。 9、通常从哪几个方面评价算法的质量？

10、算法的时间复杂度主要有哪几种？按从优到劣的顺序写出各种表示形式。

第二章线性表

一、单项选择项

1、线性表L 的顺序存储示意图如下： a b c d e f g h （1）LENGTH(L)=( )。

A.a B.h C.6 D.8

（2）GET（L，4）=（）。

A.a B.d C.h D. 8

(3)INSERT（L，W，4）；GET（L，4）的值为（）。

A. a B.d C.w D.8

(4)DELETE（L，1）；GET（L，1）的值为（）。

A.a B.b C.w D.8 2、单链表表示意图如下：

L 2 5 (1)表

7 null P Q R 头指针（）。

A.L B.P C.Q D.R （2）指向链表首结点的指针是（）。

A.L B.P C.Q D.R

（3）指向链表Q结点的前驱的指针是（）。

A.L B.P C.Q D.R

（4）指向链表Q结点的后继的指针是（）。

A.L B.P C.Q D.R

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

A.0(1) B.0(n) C.0(nlog2n) D.0(n2)

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

A.n B.n/2

C.n+1 D.(n+1)/2

5、线性表L=（a,b,c,d,e），经运算Delete(L，3)后，L表等于（）。

A.(a,b,d,e) B.(a,b,c,d) C.(b,c,d,e) D.(d,e)

6、L是线性表，已知Length(L)的值是5，经运算Ddelete(L,2)，后Length(L)的值是（）。

A.5 B.0 C.4 D.6

7、线性表中（）只有一个直接前驱和一个直接前驱和一个直接后继。

A.首元素 B.尾元素 C.中间的元素 D.所有的元素 8、下列说法正确的是（）。

A.线性表的逻辑顺序与存储顺序总是一致的

B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续

C.线性表的顺序存储结构优于链式存储结构

D.每种数据结构都具有插入、删除和查找三种基本运算

9、设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为i个结点，下列算法段能正确完成上述要求的是（）

A.s-﹥next=p-﹥next=s; B.p-﹥next=s;s-﹥next=p-﹥next;

C.s-﹥next=p-﹥next=s;交换p-﹥data和 s-﹥data; D.p=s;s-﹥next=p;

10、指针p指向循环链表L 的首元素的条件是（）。

A.p= =L

B. p -﹥n e x t= =L C.L -﹥n e x t= =p D.p-﹥n e x t= =NULL

11、线性表中各元素之间的关系是（）关系。

A.层次 B.网状 C.有序 D.集合

12、假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要指一个指针s所指的新结点作为非空双链表中q所指结点（中间结点）的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是（）。

A.q-﹥right=sls-﹥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.以上都不对

13、在单链表的一个结点中有（）个指针。

A.1 B.2 C.0 D.3

14、设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为（）。

A.s-﹥tl-﹥r1=s-﹥tl;s-﹥rl-﹥tl=s-﹥rl; B.s-﹥tl-﹥rl=s-﹥rl;s-﹥rl-﹥tl=s-﹥tl; C.s-﹥rl=s-﹥tl-﹥rl;s-﹥tl=s-﹥rl-﹥tl; D.s-﹥tl=s-﹥tl-﹥rl;s-﹥rl=s-﹥rl-﹥tl

15、指针P 所指的元素是双向循环链表L的尾元素的条件是（）。

A.P= =L B.P= =NULL C.P-﹥Llink==L D.P-﹥Rlink==l

16、P和我两个指针分别指向双向循环表L的两个元素，P所指元素是Q所指元素的后继的条件是（）。

A.P= =Q B.Q-﹥Rlink==P

C.P-﹥Rlink==q D.Q-﹥Rlink==P-﹥Rlink

17、两指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素的前导的条件是（）。

A.p-﹥next==q B.Q-﹥next==p C.P= =Q D.P-﹥next==q-﹥next 18、指针P指向线性链表L的首元素的条件是（）。

A.P= =L B.L-﹥Next==P C.P-﹥next==L D.P-﹥next==NULL

19、L=(a,b,c,d,e,f)，函数Length(L)的值是（）。

A.1 B.TRUE C.6 D.C

20、已知s=‘a b c’,t=‘x y ’经运算ASSIGN(t, s)后，s的值是（）。

A.‘a b c’ B. ‘x y’ C. ‘a b c x y’ D. ‘x y a b c’

21、串S=‘abcdefg’，经DELETE（S，2）后S=（）。

A. ‘AEFG’ B. ‘abcd’ C. ‘’acdefg D. ‘ABCD’

22、replace(‘abacd’, ‘a’, ‘d’)的值是（）。

A. ‘a’ B. ‘d’ C. ‘dbacd’ D. ‘dbdcd’

23、吕、串S=‘abbcabdf’经运算REPLACE（S，‘ab’, ‘xy’）后S=（）。

A. ‘xybcxydf’ B. ‘xybcabdf’ C. ‘abbcxydf’ D. ‘abbcabdf’ 24、在数据结构中，（）不都是线性结构。

A栈和队列 B.队列和数组 C.数组和串 D.文件和队列二、填空题

1、Insert sqlist(L,X,i)的时间复杂度为0( )。 2、Delete sqlist(L,i)的时间复杂度为0（）。

3、顺序表中逻辑上相邻的元素在物理位置上相连。 4、链表中逻辑上相邻的元素的物理位置相连。

5、在单链表中除首结点外，任意结点的存储位置都由结点中的指针指示。

6、在单链表中，设置头结点的作用是在插入或删除头结点时不必对进行处理。

7、已知带表头结点的单链表L，指针P指向L链表中的一个结点，指针Q是指向L镕表外的一个结点，则：

（1）在指针P所指结点后插入Q所指结点的语句序列是；（2）在指针P所指结点前插入Q所指结点的语句序列是；（3）将Q所指结点插入在链表首结点的语句序列是；（4）将Q所指结点插入在链表尾结点的语句序列是。

8、书籍带头结点的单链表L，指针P指向L链表中的一个结点为（非首结点、非尾结点），则

（1）删除P结点的直接后继结点的语句是；

（2）删除P结点的直接前驱结点的语句序列是；（3）删除P结点的语句序列是；（4）删除首结点的语句序列是；（5）删除尾结点的语句序列是。 9、已知指针P指向双向链表中的一个结点（非首结点、非尾结点），则：（1）将结点S插入在P结点的直接后继位置的语句是；（2）将结点S插入在P结点的直接前驱位置的语句是；（3）删除P结点的直接后继结点的语句序列是；（4）删除P结点的直接前驱结点的语句序列是；（5）删除P结点的语句的序列是。 10、线性表的存储结构有顺序存储和存储两种。 11、线性表的元素长度为4，在顺序存储结构下LOC（ai）=2000，则LOC(ai+1)= 。

12、线性表a的元素长度为L，在顺序存储结构下LOC(ai)=LOC(ai)+ 。

13、线性表的存储结构有两种存储方式。 14、线性表的元素长度为4，LOC(a1)=1000，则LOC(a3)= ， 15、设某非空单链表，其结点形式为，若要删除指针q所指结点

data next 的直接后继结点，则需执行下列语句序列： p=q-﹥next; ;free(p);

16、存储空间长度为M的循环队列sq是满队列的条件是。

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

18、定义在线性表上的初始化、查找、插入和删除运算中，是引用型运算。

19、线性表（a0,a1,a2,?,an）(n≥1)中，每个元素占c个存储单元，m为a0的首地址，则按顺序存储方式存储线性表，an的存储地址是。 20、设某非空双链表，其结点形式为

prior data next 9

若要删除指针q所指向的结点，则需执行下述语段： q-﹥prior-﹥next=q-﹥next; 。 21、函数LENGTLL（‘abc’）的值是。 22、同一个线性表内各元素的长度。 23、线性表的元素没前导元素。 24、单链表S是空表的条件是。 25、循环链表S是空表的条件是。 26、双向链表S是空表的条件是。 27、P指针指向单链表的尾元素的条件是。 28、P指针指向循环链表S的尾元素的条件是。 29、P指针指向双向链表的尾元素的条件是。 30、若双向链表S中， s-﹥next==s-﹥prior则S 。三、应用题

1、已知线性表L，根据各步运算填写表格。运算运算后L表中的内容 INITATE(L) L=( ) INSERT(L,a,1) L=( ) INSERT(L,b,1) L=( ) INSERT(L,X,2) L=( ) GET(L,2) L=( ) LOCATE(L,X) L=( ) DELETE(L,1) L=( ) DELETE(L,1) L=( ) LENGTLL(L) L=( ) 函数值 ? ? ? L表中元素个数 ? ? ? ? ? ? ? ? ? 2、叙述链表的以下三个概念的区别：头指针、头结点、首结点。 3、在什么情况下使用顺序表比链表好？

4、对于以下单链表，分别执行下列各步骤的程序段，画出执行各步后链表指针变化的示意图。 L

(1)P= -﹥next;Q=P-﹥next;R=Q-﹥next;S=R-﹥next; (2)R-﹥data=P-﹥data;P-﹥data=p-﹥next-﹥data; (3)T=P;WHILE(T)｛T-﹥data=T-﹥data*2;T-﹥next｝;

2 5 7 8 ?

5、已知带表头的单链表L，简述下列对L链表操作算法的功能。 Status a(L) ｛

if (L ｛L-﹥next&&L-﹥next-﹥next｝｛

Q=L-﹥nwxt; L-﹥next=Q-﹥next; P=Q

While(P-﹥next)p=p-﹥next; P-﹥next=Q Q-﹥next=NULL; ｝ return OK ｝

6、已知带表头的循环链表L，简述下列对L链表操作算法的功能。 void BB(s,q)/* s、q是指向结点类型的指针*/｛ P=s;

While(P-﹥next!)=q P=P-﹥next; P-﹥next=s; ｝

Void AA(pa,pb)/*pa、pb是指向单向循环表中的两个结点的指针*/｛BB（pa,pb）; BB(pb,pa) ｝

7、分别画出线性表L=(a,b,c)存储在单链表、循环链表、双向循环链表中的示意图。

8、哪些链表从尾指针出发可以访问到链表中的任意结点？四、设计题

1、用类C语言写出在顺序存储条件下，初始化线性表L的算法：Initiate(L) 2、用类C语言写出在顺序存储条件下，求线性表L的长度的算法：

Length(L)

3、用类C语言写出在顺序存储条件下，读线性表L的第i个元素的算法： GET（L,i）

4、设某带头结点的单链表的结点结构说明如下： typedef struct nodel ｛ int data;

struct nodel *next; ｝node;

试设计一个算法:void copy (node *headl,node *head2),将以headl为头指针的单链表中。

5、没有两个按升序排列的单链表X和Y，其实指针分别为p,q，结点结构说明如下：

typedef struct nodel ｛ intadta;

struct nodel * next ｝node;

试设计一个算法void concat(node *p, *q)将它们合并成一个以 P为头指针的链表Z，使其仍然有序。

6、用类C语言写出在顺序存储条件下，将线性表L中的第i个元素删除的算法： DELETE(L,i)

7、用类C语言写出在顺序存储条件下，将X插入顺序表La的算法，La表中的元素是递增有序，有序表存储在a数组中： insert0rderlist(&a , X)

8、用类C语言写出在链式存储条件下，将单链表L1的元素连接在单链表L2的尾部的算法： Link（L1，L2）

9、用类C语言写出在链式存储条件下，删除单链表L中值大于max或min的元

素算法：

Delete9(L, max, min)

10、用类C语言写出在链式存储条件下，删除单链表L中值相同的多余元素（使链表中元素的值均不相同）的算法： Delete10(L)

11、用类C语言写出顺序表的逆置的算法，即利用原来的顺序表将线性表达式L=（a1, a2, a3,? an）逆置为L=(an,?a3, a2, a1): move11(L)

12、用类C语言写出单链表的逆置的算法，即利用原来的顺序表将线性表L=（a1, a2, a3,? an）L=(an,?a3, a2, a1): move12(L)

13、设单链表A=（a1, a2, a3,? an）和B=(bn,?b3, b2, b1)，用类C语言编写将A与B合并为链表C的算法。即：

C=（a1 ,b1, a2,b2, a3,b3,? ,an,bn,bn+1,?bm）当n≥ C=（a1 ,b1, a2,b2, a3,b3,? ,am,bm,am+1,?an）当n﹤m

其中n和m不是已知条件，C表A表和B表的结点空间Mpass13（A，B，C） 14、设单链表A=（a1,a2,a3?an）和B=(b1,b2,b3?bn)都是有序表（按值从小到大排列），用类C语言编写写将A与B合并为链表C的算法，C表也要求从小到大。

其中n和m不是已知条件，C表A表和B表的结点空间。 Mpass14(A,B,C)

15、已知A、B、C是三个按值从小到大有序的单链表，对A表进行如下操作删除那些既在B表又在C表中的元素。 Delete15(A,B,C)

16、已知指针S指向单铅循环链表的一个结点，该结点有前导结点，写出删除该结点的直接前导结点的算法。 Deletel16(s)

17、已知单链表L是按值从小到大有序，将X插入到L链表中，并保持L链表有序，写出算法。 Insert(L,X)

18、已知单链表L和指向L表中的一个结点的指针R，从R将L表分成两个单链表，要求R结点作为后一个链表的首结点。 Bin(L,R)

19、任意给出正整数m和n，将m个数1,2,3?m顺时针排列成环型，从1开始顺时针开始计数，将数到的第n个数输出，再继续从1数到n，并将第n个数输出，依次将这m个数全部输出。例如，例如，当=10，n=3时，输出的数是3,6,9,2,7,1,8,5,10,4。 Josephus(L,m,n)

第三、四、五章栈和队列、串、数组和广义表

一、单项选择题

1、栈是限定在（）处进行插入或删除操作的线性表。 A.端点

B.栈底

C.栈顶

D.中间

2、在栈顶一端可进行的全部操作是（）。

A.插入 B.删除 C.插入和删除 D.进栈

3、4个元素按A、B、C、D顺序连续进S栈，进行Pop(S,x)运算后，x的值是（）。 A.A

B.B

C.C

D.D

4、栈的特点是（）。 A.先进先出

B.后进先出

C.后进后出

D.不进不出

5、栈结构的元素个数是（）。 A.不变的

B.可变的

C.任意的

D.0

6、4个元素进S栈的顺序是A、B、C、D，进行两次Pop(S,x)操作后，栈顶元素的值是（）。 A.A

B.B

C.C

D.D

7、同一个栈内各元素的类型（）。 A.必须一致

B.可以不一致

C.不能一致

D.不必不一致

8、顺序栈存储空间的实现使用（）存储栈元素。 A.链表

B.数组

C.循环链表

D.变量

9、一个顺序栈一旦说明，其占用空间的大小（）。 A.已固定

B.可以改变

C.不能固定

D.动态变化

10、栈是一个（）线性表结构。 A.不加限制的

B.加了限制的

C.推广了的

D.非

11、栈与一般线性表的区别主要在（）方面。 A.元素个数

B.元素类型

C.逻辑结构

D.插入、删除元素的位置

12、顺序栈是空栈的条件是（）。 A.top= =0

B.top= =1

C.top= =-1

D.top= =m

13、初始化一个空间大小为5的顺序栈Ss后，Ss-﹥top的值（） A.是0

B.不定

C.不再改变

D.动态变化

14、元素A、B、C、D依次进顺序栈后，栈底元素是（）。 A.A

B.B

C.C

D.D

15、元素A、B、C、D依次进顺序栈后，栈底元素是（） A.A

B.B

C.C

D.D

16、经过下列栈的运算后勤工作GetTop(s)的值是（）。 InitStack(s);Push(s,a);Push(S,b),Pop(s); A.a

B.b

C.1

D.2

17、经过下列栈的运算后，X的值是（）。 InitStack (s);Push(s,a);Push(s,b),GetTop(S);Pop(s,x); A.a

B.b

C.1

D.2

18、经过下列栈的运算后，X的值是（）。 InitStack(s);Push(s,A);Pop(s,X),Push(s,B);Pop(s,X); A.a

B.b

C.1

D.2

19、经过下列栈的运算后EmptyStack(s)的值是（）。 InitStack(s);Push(s,A);Push(s,B);Push(s,x);Pop(s,x); A.a

B.b

C.1

D.2

20、经过下列栈的运算后EmptySTACK(s)的值是（）。 InitStack(s);Push(s,A);Push(s,B);Pop(s,x);GetTop(s); A.a

B.b

C.1

D.2

21、队列是限定在（）处进行插入操作的线性表。 A.端点

B.队头

C.队尾

D.中间

22、队列是限定在（）处进行删除操作的线性表。 A.端点

B.队头

C.队尾

D.中间

23、4个元素按A、B、C、D顺序连续进队Q，队的头元素是（） A.A

B.B

C.C

D.D

24、4个元素A、B、C、D顺序连续进队Q，队的尾元素的值是（）。 A.A

B.B

C.C

D.D

25、队列的特点是（）。 A.先进先出

B.后进先出

C.先进后出

D.不进不出

26、队列中的元素个数是（）。 A.不变的

B.可变的

C.任意的

D.0

27、4个元素进Q队列的顺序是A、B、C、D，进行OutQueue(Q)操作后，队头元素是（）。 A.A

B.B C.C

D.D

28、同一队列内各元素的类型（）。 A.必须一致

B.可以不一致

C.不能一致

D.不限制

29、循环队占用的空间（）。 A.必须连续

B.可以不连续

C.不能连续

D.不必连续

30、容量是10的循环队的头指针的位置Sq.front为2，则队的头元素的位置是（）。 A.2

B.3

C.1

D.0

31、容量是10的循环队的头指针的位置Sq.rear为2，则队的尾元素的位置是（）。 A.2

B.3

C.1

D.0

32、一个循环队列一旦说明，其占用空间的大小（）。 A.已固定

B.可以改变

C.不能固定

D.动态变化

33、队列是一个（）线性表结构。 A.不加限制的 B.加了限制的

C.推广了的

D.非

34、循环队列Sq是空队列的条件是（）。 A.Sq-﹥read= =Sq-﹥front C.Sq-﹥read= =0

B.(Sq-﹥read+1)%maxsize= =Sq-﹥front D.Sq-﹥frond= =0

35、徨队列Sq是满队列的条件是（）。 A.Sq-﹥read= =Sq-﹥front C.Sq-﹥read= =0

B.(Sq-﹥read+1)%maxsize= =Sq-﹥front D.Sq-﹥frond= =0

36、当循环队列Sq是满队列时，存放队列元素的数组data有n个元素，则data中存放（）个队列元素。 A.n

B.n—1

C.n—2

D.0

37、存放循环队列元素的数组长data有10个元素，则data数组的下标范围是（） A0..10

B.0..9

C.1..10

D.1..9

38、存放循环队列Sq元素的数组data有10个元素，sq-﹥from为9，队列的头元素的位置在（）。 A.9

B.0

C.1

D.10

39、初始化一个空间大小为5的循环队列Sq后，Sq-﹥front的值是（）。 A.0

B.不定

C.不再改变

D.1

40、初始化一个空间大小为5的循环队列Sq后，Sq-﹥rear的值是（）。 A.0

B.不定

C.不再改变

D.1

41、经过下列运算后GetHead(Q)的值是（）。 InitQueue(Q);EuQueue(Q,a);EnQueue(Q,b); A.a

B.b

C.1

D.2

42、经过下列运算后GetHead(Q)的值是（）。 InitQueue(q);EnQueue(Q,A);EnQueue(Q,b);OutQueue(Q,X) A.a

B.b

C.1

D.2

43、经过下列运算后EmptyQueue(Q)的值是（）。

InitQueue(Q);EnQueue(Q,a);EnQueue(Q,b);OutQueue(Q,X)QutQueue(Q,X); A.A

B.B

C.1

D.0

44、经过下列运算后X的值是（）。

InitQueue(Q);EnQueue(Q,a);EnQueue(Q,b);OutQueue(Q,X);OutQueue(Q,X); A.a

B.b

C.1

D.0

45、队列结构发球下列结构中的哪种？（） A.集合

B.线性

C.树形

D.网状

46、队列的特点是只能在它们的（）处添加结点。 A.头

B.尾

C.中间

D.端点

47、链栈ls的示意图如下，栈顶元素是（）。 ls A.a

B.b

表头结点 d c b a ∧ C.c D.d

48、在如上所示的链栈ls中，指向链栈的栈顶用元素的指针是（） A.ls

B.ls-﹥next

C.ls-﹥next-﹥next

D.d

49、对哪上所示的链栈ls，将X元素进栈，则X元素在（）。 A.d元素之间

B.a元素之后

C.d元素之后

D.表头结点中

50、链栈ls是空栈的条件是（）。

A.ls= =null B.ls-﹥next= =null C.ls= =0 D.ls-﹥nuxt= =ls

51、链队lq的示意图如下，链队的头元素是（）。

lq-﹥front

表头结点 a B c ∧ lq-﹥ rear A. a B.b C.c D.front

52、在如上所示的链队lq 中，链队的尾元素是（）。 A.a

B.b

C.c

D.rear

53、在如上所示的链队lq中，指向链队的尾元素的指针是（）。 A.lq-﹥front

B.lq

C.c

D.lq-﹥rear

54、在如上所示的链队lq中，指向链队的队头元素的指针是（）。 A.lq-﹥front

B.lq

C.lq-﹥front-﹥next

D.lq-﹥rear

55、如上所示的链队lq中，在进行进队、出队运算时指针lq-﹥front（）。 A.始终不改变

B.有时改变

C.进队时改变

D.出队时改变

56、如上所示链队lq在进行进队、出队运算时，指针lq-﹥rear( ) A.始终不改变

B.改变

C.进队时改变

D.出队时改变

57、如上所示的链队lq为空时，（）。 A.lq-﹥front==lq-﹥rear C.lq-﹥front!=lq-﹥rear 58、链队lq（）。 A.有队空的情况

B.不存在队空的情况 D.出队之间先判断满否

B.lq-﹥rear==null D.lq-﹥front==null

C.出队之间不必判断空否 59、链队lq( )。 A.存在队满的情况

B.不存在队空的情况 D.出队之间先判断空否

C.进队之间必须判断满否

60、链队lq中的元素类型（）。 A.必须一致

B.不能一致

C.可以一致

D.必须是字符型

61、数组的基本操作是（）。 A.插入数组元素

B.删除数组元素

C.只可以读

D.读和写

62、同一个数组中的元素（）。 A.长度可以不同

B.类型不限

C.类型相同

D.长度不限

63、数组结构一旦确定，其元素的个数是（）。 A.不变的

B.可变的

C.任意的

D.0

64、数组占用的空间（）。 A.必须连续

B.可以不连续

C.不能连续

D.不必连续

65、一个数组一旦说明，其占用空间的大小（）。 A.已固定

B.可以改变

C.不能固定

D.动态变化

66、设有一个5阶上三角矩阵A[1..5,1..5]，现将其上三角中的元素按列优先顺序存放在一维数组B[1..15]中。已知B[1]的地址为100，每个元素占用2个存储单元，则A[3，4]的地址为（）。 A.116

B.118

C.120

D.122

67、数组与一般线性表的区别主要在（）。 A.存储方面

B.元素类型一致

D.不能进行插入、删除运算

C.逻辑结构方面

68、一维数组的元素起始地址loc[6]=1000，元素长度为4，则loc[8]为（）。 A.1000

B.1004

C.1008

D.8

69、已知一个稀疏矩阵的三元组表如下:(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.)

70、二维数组a[4][4]，数组的元素起始地址loc[0][0]=1000，元素长度为2，则Loc[2][2]为( ) A.1000 二、填空题

1、已知顺序栈S，在对S进行进栈操作之间首先要判断。 2、已知栈S是顺序存储结构，在进行出栈操作之间产生要判断。 3、顺序栈S存储在数组Ss-﹥data[0...max]中，S栈满的条件是。 4、如图所示，设输入元素的顺序是A，B，C，D通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为。

B.1010

C.1008

D.1020

5、顺序栈S存储在数组长Ss-﹥data[0...max]中，S进行出栈操作后，要执行的语句序列中有Ss-﹥top。

6、顺序栈S存储在数组Ss-﹥data[0...max]k ,S进行进栈操作前，要执行的语句序列中有Ss-﹥top运算。

7、顺序栈S存储在数组Ss-﹥data[0...max]中，S栈满时，Ss-﹥top=。 8、顺序栈S存储在数组Ss-﹥data[0...max]中，S栈空时，Ss-﹥top=。 9、在栈的顺序实现中，设栈顶指针为top，栈空的条件为。 10、链栈ls是空栈的条件是。

11、链栈ls的栈顶元素是链表的元素。 12、链栈的类型定义如下： typedef struct node ｛DataType data; Struct node *next; ｝LstackTp;

若栈非空，则退栈操作可以用下列算法片段实现：p=ls;/*ls为栈顶用指针*/ x=p-﹥data;/*栈顶元素通过参数返回*/； free(p);/*释放原栈顶结点空间*/

13、栈S经过运算InitStack(s);Push(s,a);Push(s,b)后GetTop(S)的值是。 14、栈S经过运算InitStack(s);Push(s,a);Push(s,x)后GetTop(S)的值是。 15、队列可以看成一种运算受限制的线性表，也称为线性表。 16、队列中允许进行删除的一端为。 17、元素进入队列那端是。 18、队列出队的那端是。

19、已知循环队列Sq，在进行进队操作之间首先要判断。 20、已知循环队列Sq，在进行出队操作之间首先要判断。 21、循环队列Sq存储在数组Sq,data[0..max]中，Sq满的条件是。 22、循环队列Sq空的条件是。

23、循环队列Sq存储在数组Sq.data[0..max]中，Sq.front为max,则存放队列头元素的数组元素是。

24、队列中允许进行插入元素的一端称为。

25、循环队列Sq存储在数组Sq.data[0..max]中，则Sq中最多能存放个队列元素。

26、链队lq中，指向队头元素的指针是。 27、链队lq中，指向队尾元素的指针是。 28、链队lq是空队的条件是。

29、链队lq经过运算InitQueue(lq)，lq-﹥front与lq-﹥rear。 30、循环队列Sq经过运算InitQueue(sq),Sq.front等于。 31、循环队列Sq经过运算InitQueue(sq),Sq.rear等于。 32、队列Ｑ经过InitQueue(q);EnQueue(q,a);EnQueue(q,b); GetHead(Q,x)后，Ｘ的值是。

33、队列Ｑ经过InitQueue(q);EnQueue(q,a);OutQueue(Q,x)后,EmptyQueue(q)的值是。

34、队列Ｑ经过InitQueue(q);EnqUEUE(q,a);OutQueue(Q,x)后， EmptyQueue(q)的值是。

35、在链队列lq中，链队的尾元素是链表的元素。 36、在链队列lq中，链队的头元素是链表的元素。

37、循环队列Sq进行EnQueue(Sq,a)运算时，要执行的语句序列中有Sq.rear。 38、循环队列Sq进行OutQueue(Sq,x)运算时，要执行的语句序列中有Sq.front。

39、链队q是空队时，lq-﹥front-﹥next为。 40、队列进行OutQueue(Q,x)时首先要判断。 41、数组结构占用的内存空间。

42、数组结构咯元素的逻辑关系具有性。

43、同一数组中各元素的类型一致，称为数组的性。 44、数组存储，是基于数组的两个特性。

45、数组a[0..2][0..3]的实际地址是2000，元素长度是4，则Loc[1，2]=。 46、数组元素可以由若干个组成。

47、对称矩阵的下三角元素a[i,j]，存放在一维数组V的元素V[k]中，k

与i，j的关系是：k=。

48、对称矩阵的上三角元素a[i,j]的值存放在一维数组V的元素V[k]中，k与i,j的关系是：k=。

49、在n维数组中每个元素都受到个条件的约束。 50、同一数组中的各元素的长度。

51、对称的n阶矩阵的下三角各元素存储在一维数组V中，则V包含个元素。 52、稀疏矩阵的三元组有列。

53、稀疏矩阵中有n个非零元素，则其三元组有行。 54、稀疏矩阵的三元组中，第3列存储的是稀疏数组中的。

55、稀疏矩阵的三元组中，第1列存储的是稀疏数组中非零元素所在的。 56、稀疏矩阵的三元组中，第2列存储的是稀疏数组中非零元素所在的。 57、稀疏矩阵的三元组中，第1列中的数据按顺序排列。 58、数组的三元组存储是对矩阵的压缩存储。 59、可以进行压缩存储的三种矩阵是矩阵。

60、n阶三角矩阵的上三角元素值相等，进行压缩存储时，该值存储在下标为的数组元素中。三、应用题

1、已知顺序栈S，根据各步运算在括号内及问号处填写相应内容。

运算 InitStack() Push(S,a) Push(S,b) Push(S,c) Push(S,x) EmptyStack(S) GetTop(S) Pop(S,x) Pop(S,x) 运算后S栈中的内容 S=( ) S=( ) S=( ) S=( ) S=( ) S=( ) S=( ) S=( ) S=( ) 栈顶元素 ? ? ? ? ? ? ? ? 2、设有字符串3*-y-a/y22,试利用栈写同将其转换为3y-*ay22/-的操作步骤。

假定用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤XXSXSS。

3、设有一顺序队列sq，容量为5，初始状态时sq,front=sqrear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。（1）d,e,b入队（2）d,e出队（3）i,j入队（4）b出队（5）n,0,pty bw

4、A、B、C三个元素进S栈的顺序是A、B、C写出所有可能的出栈序列和相应操作，哪个顺序不会是出栈序列？ 5、写出下列程序段的输出结果。 main( ) ｛ Stack S; cha x,y; InitStack(S); x=‘c’;y=‘k’; Push(S,x); Push(S,‘a’); Push(S,y); Pop(S,x); Push(S,‘t’); Push(S,x); Pop(S,x) Push(S,‘s’)；

第六章树和二叉树

一、单项选择题 1、对于下列二叉树

A B C

D E F G H I J

（1）A结点是（）。

A.叶结点 B.根结点但不是分支结点 C.根结点也是分支结点 D.是分支结点但不是根结点（2）B结点是（）。

A.叶结点 B.根结点但不是分支结点 C.根结点也是分支结点 D.是分支结点但不是根结点（3）J结点是（）。

A.叶结点 B.根结点但不是分支结点 C.根结点也是分支结点 D.是分支结点但不是根结点（4）E结点是（）。

A.叶结点 B.根结点但不是分支结点. C.子树的根结点 D.是分支结点但不是子树的根结点（5）F结点是兄弟结点是（）。

A. E B. D C. 空 D. I （6）F结点的双亲结点是（）。

A. A B. B C. C D. D （7）E结点的祖先结点只有（）。

A. A B. A和B C. A、B、C D. D 2、对于下列树

（1）树的深度为（）。

A. 1 B. 2 C. 3 D.4 （2）树的度是（）。

A. 1 B. 2 C. 3 D.4 （3）B结点的度是（）。

A. 1 B. 2 C. 3 D.4

6、简述下列算法的功能。 algo ( Stack S ) {

int i, n, a[255]; n=0;

while ( !EmptyStack ( s ) ) {n++ ; Pop( S, A[n] ) ; }

for (i=1; i<=n ; i++ ) Push ( S, A[i]) ; } 7、

algo2 ( Stack S) {

stack T ; int d ; InitStack ( T ) ;

while ( !EmptyStack (s) ) {

Pop ( S, d ); Push ( T, d ); }

8、写出循环队列Q在下列运算中队列头和尾变化的情况。初态 e1进队 e2进队 e3进队出队出队 e4进队 Q.front 0 Q.rear 0 9、简述循环队列进行进队、出队操作前应当进行的判断。 10、简述队列的特点及与一般线性表的区别。 11、比较栈和队列的相同点与不同点。 12、写出下列算法的输出结果。

main ( ) {

InitQueue (Q); x=’e’; y=’c’;

EnQueue (Q, ‘h’) ; EnQueue (Q, ‘r’) ; EnQueue (Q, ‘y’) ; OutQueue (Q, x ) ; EnQueue (Q, x ) ; OutQueue (Q, x ) ; EnQueue (Q, ‘a’) ; while (! EmptyStack ( Q ) ) {

OutQueue (Q, y) ; printf (y) ; } printf (x) ; }

13、简述下列算法的功能。ex13 (Q) InitQueue (S) ;

while (!EmptyStack (Q) ) {

OutQueue (Q, d) ; Push (S, d) ; }

while (! EmptyStack (S) ) {

Pop (S, d) ;

EnQueue (Q,d) ; }

14、已知下列数组a的起始地址是2000，求a[2][2][1]的起始地址。 int a[3][4][2]； loc[2，2，1]=?

15、设有一循环队列sq. data[maxsize]，一般情况下队列中至多可存放多少个元素？为什么？四、设计题

1、借助栈将输入任意一个非负的十进制整数，打印输出与其等值的八进制。 2、已知带表头结点循环链表存储链队的元素（如下所示），指针rear指向队列的尾元素，写出将元素X进队的算法。

EnQueue ( rear, X)

3、设字符串仅由圆括号“（”和“）”，方括号“[”和“]”，花括号“{”和“}”组成，利用链栈的操作编写一个检查括号是否正确配对的算法：int Matcher ( LstackTP * ls)。例如，[{{（）}[]}（）{[]}]是正确的，而{（{（）[]}）}]}是不正确的。设链栈定义如下： typedef struck node {char data; struct node * next; } LStackTp ;

4、Ss是结构体变量，其内包括指示栈顶位置的域Ss.top和数组Ss.data，用类C语言写出顺序栈基本运算的算法。（1）获得一个空的顺序栈。 InitStack (Ss)

（2）将值X进顺序栈的算法。 Push (Ss, x)

（3）对顺序栈Ss进行出栈的算法，将出栈的值赋给变量X。 Pop (Ss, x)

（4）判断顺序栈Ss是否是空栈算法。 Emptys (Ss)

（5）将顺序栈Ss栈顶元素的值拷贝给变量X的算法。 GetTop (Ss,X)

（6）写出判断顺序栈Ss中元素个数的算法。 Length (Ss)

5、Sq 是结构体变量，其内包括循环队列头（Sq.front）、尾（Sq.rear）位置的信息，用类C语言写出循环队列基本运算的算法。（1）获得一个空的循环队列Sq。 InitQueue (Sq)

（2）将值X放进循环队列的算法。 EnQueue (Sq, x)

（3）对循环队列Sq进行出队的算法，将出队的值赋给变量X。 OutQueue (Sq,x )

（4）判断循环队列Sq是否是空队的算法。 EmptyQueue (Sq)

（5）将循环队列Sq头元素的值拷贝给变量X的算法。 GetHead (Sq, X)

（6）写出判断循环队列Sq中元素个数的算法。 Length (Sq)