②单链表的每一个结点都被一个指针所指
③任何结点只能通过指向它的指针才能引用 ④终端结点的指针域就为NULL
⑤尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表
14．有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是 （ ） ①将“指针型变量”简称为“指针” ②将“头指针变量”称为“头指针”
③将“修改某指针型变量的值”称为“修改某指针” ④将“p中指针所指结点”称为“P值”
15．设指针P指向双链表的某一结点，则双链表结构的对称性可用（ ）式来刻画 ① p->prior->next->==p->next->next ② p->prior->prior->==p->next->prior ③ p->prior->next->==p->next->prior ④ p->next->next==p->prior->prior
16.以下说法错误的是 （ ）
①对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表 ②对单链表来说，只有从头结点开始才能扫描表中全部结点 ③双链表的特点是找结点的前趋和后继都很容易
④对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。
17．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是 （ ）
①real和rear->next->next ②rear->next 和real
③rear->next->next和rear ④rear和rear->next 18.以下说错误的是 ( )
①对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）
②读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构 ③在链表上实现读表元运算的平均时间复杂性为O（1）
④链入、摘除操作在链表上的实现可在O（1）时间内完成
⑤链入、摘除操作在顺序表上的实现，平均时间复杂性为O（n） 19．在串的基本运算中，属于加工型运算的有 （ ）
①EQAL(S,T) ②LENGTH(S) ③CONCAT(S,T) ④REPLACE(S,T,R) ⑤INDEX(S,T) 20. 在串的基本运算中，属于引用型运算的有 （ ）
①ASSIGN(S,T) ②INSERT(S1,i,S2)
③DELETE(S,i,j) ④SUBSTR(S,i,j) ⑤REPLACE(S,T,R) 21．循环链表主要优点是 （ ）
①不再需要头指针了
②已知某个结点的位置后，能够容易找到它的直接前趋
③在进行插入、删除运算时，能更好地保证链表不断开 ④从表中任一结点出发都能扫描到整个链表
22，每种数据结构都具备三个基本操作:插入、删除和查找，这种说法 （ ）
6
①正确 ②错误
23．以下说法错误的是 （ ）
①数据的物理结构是指数据在计算机内实际的存储形式 ②算法和程序没有区别，所以在数据结构中二者是通用的 ③对链表进行插人和删除操作时，不必移动结点 ④双链表中至多只有一个结点的后继指针为空 24．以下说法正确的是
①线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继
②线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要
低
③在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置有关 ④顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动
25．以下说法错误的是 （ ）
①求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
②顺序存储的线性表可以随机存取
③由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 ④线性表的链式存储结构优于顺序存储结构
26．以下说法错误的是 （ ）
①线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻 ②在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻 ③在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻
④线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 27．以下说法正确的是（ ）
①在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素
②在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构
③顺序存储结构属于静态结构，链式结构属于动态结构 ④顺序存储方式只能用于存储线性结构 28.以下说法正确的是（ ）
①顺序存储方式的优点是存储密度大、且插入、删除运算效率高 ②链表的每个结点中都恰好包含一个指针
③线性表的顺序存储结构优于链式存储结构
④顺序存储结构属于静态结构，链式结构属于动态结构 29.下面关于线性表的叙述正确的是( )
①线性表采用顺序存储，必须占用一片连续的存储单元 ②线性表采用顺序存储，便于进行插人和删除操作 ③线性表采用链接存储，不必占用一片连续的存储单元 ④线性表采用链接存储，不便于插人和删除操作 30.线性表L=(a1,a2,...,ai,...,an),下列说法正确的是( )
①每个元素都有一个直接前驱和直接后继 ②线性表中至少要有一个元素
7
③表中诸元素的排列顺序必须是由小到大或由大到小的
④除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继
31.线性表的逻辑顺序与存储顺序总是一致的，这种说法( )
①正确 ②不正确 32.设p,q是指针,若p=q,则*p=*q ,这种说法( )
①正确 ②不正确
33.线性表若采用链表存储结构时，要求内存中可用存储单元的地址( )
①必需是联系的 ②部分地址必须是连续的
③一定是不连续的 ④连续不连续都可以
34.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为( )
①p=rear; ②rear=rear->next; rear=rear->next; free(rear); free(p)
③rear=rear->next->next; ④ p=rear->next->next; free(rear); rear->next->next=p->next;
free(p); 35. 单链表中，增加头结点的目的是为了 ( )
①使单链表至少有一个结点 ②标示表结点中首结点的位置
③方便运算的实现 ④说明单链表是线性表的链式存储实现
36线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着
① 每个结点所代表的数据元素都一样。
② 每个结点所代表的数据元素包含的数据项的个数要相等
③ 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 ④ 结点所代表的数据元素有同一特点
37．带头结点的单链表Head为空的判定条件是
①Head=Null ②Head->next=NULL ③Head->next=Head 38.非空的单循环链表L的尾结点*P,满足
P->next=NULL P=NULL P->next=L P=L. 39.双向链表结点结构如下：
LLink data RLink 其中：LLink是指向前驱结点的指针域：
data是存放数据元素的数据域； Rlink是指向后继结点的指针域。
下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。不能正确完成要求的算法段是
①Q->LLink=P->LLink; ②P->LLink=Q; Q->Rlink=P; Q->Rlink=P;
P->LLink=Q; P->LLink->Rlink=Q; P->LLink->Rlink=Q; Q->LLink=P->LLink; ③Q->LLink=P->LLink; Q->Rlink=P;
8
P->LLink->Rlink=Q;
P->LLink=Q;
40.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
①顺序表 ②单链表 ③双链表 ④单循环链表 41．串是任意有限个
①符号构成的集合 ②符号构成的序列 ③字符构成的集合 ④字符构成的序列 四、简答及应用
1． 请用类C语言描述顺序表，并予以解释说明。
2． 请用类C语言描述单链表的类型定义，并予以解释说明。 3． 请用类C语言描述双链表的类型定义，并予以解释说明。 4． 请用类C语言描述顺序串的类型定义。 5． 请用类C语言描述链串的类型定义。
6.叙述以下概念的区别：头指针变量、头指针、头结点、首结点，并说明头指针变量和头结点的作用。
7．有哪些链表可仅由一个尾指针来惟一确定，即从尾指针出发能访问到链表上任何一个结点。 8．简述下列每对术语的区别：
空串和空格串;串变量和串常量;主串和子串;串变量的名字与串变量的值。 9．设有 A=” ”,B=\，C=\，D=\试计算下列运算的结果(注:A+B是CONCAT（A,B）的简写,A=\的 \含有两个空格)。 (a) A+B (b) B+A (c) D+C+B
(d) SUBSTR(B,3,2) (e) SUBSTR(C,1,0) (f) LENGTH(A) (g) LENGTH(D) (h) INDEX(B,D) (i) INDEX(C,\(j) INSERT(D,2,C) (k) INSERT(B,1,A) (l) DELETE(B,2,2) (m) DELETE(B,2,0)
10.已知:S=\。试利用连接、求子串和置换等基本运算，将S转换为T。 五、算法设计
1． 设A=（a1,a2,a3,......an）和B=(b1,b2,.. .,bm)是两个线性表（假定所含数据元素均为整数）。若n=m且ai=bi(i=1,.. .,n),则称A=B;若ai=bi(i=1,.. .,j)且aj+1
2，试编写在无头结点的单链表上实现线性表基本运算LOCATE(L,X)、INSERT(L,X，i)和DELETE(L,i)的算法，并和在带头结点的单链表上实现相的算法进行比较。 3．试编写在不带头结点的单链表上实现线性表基本运算LENGTH(L)的算法。
4．假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算
9
法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。
5．设有线性表A=(a1,a2,.. .,am)和B=(b1,b2,.. .,bn).试写合并A、B为线性表C的算法，使得：
?(a1,b1,...,am,bm,bm?1,bn)当m??n;C=? ?(a1,b1,...,an,bn,an?1,...,am)当m?n;假设A、B均以单链表为存储结构(并且m、n显示保存)。要求C也以单链表为存储结构并利用单链表A、B的结点空间。
6，设线性表存放在向量A[arrsize]的前elenum分量中，且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。 7．已知单链表L中的结点是按值非递减有序排列的，试写一算法将值为x的结点插入表L中，使得L仍然有序。
8，试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2,.. .,an)逆置为(an,.. .,a2,a1)。 9．假设分别以两个元素值递增有序的线性表A、B表示两个集合(即同一线性表中的元素各不相同)，现要求构成一个新的线性表C，C表示集合A与B的交，且C中元素也递增有序。试分别以顺序表和单链表为存储结构，填写实现上述运算的算法。
10，已知A、B和C为三个元素值递增有序的线性表，现要求对表A作如下运算： 删去那些既在表B中出现又在表C中出现的元素。试分别以两种存储结构(一处种顺序结构，一种链式的)编写实现上述运算的算法。
11．假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的前趋结点。
12．已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。
13.(Josephus环)任给正整数n、k，按下述方法可得排列1，2，??,n的一个置换:将数字1，2，.. .,n环形排列(如图算法设计题13.所示)，按顺时针方向从1开始 计数；计满K时输出该为之上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10,k=3时，输出的置换是3，6，9，2，7，1，8，5，10，
4。试编写一算法，对输人的任意正整数n、k，输出相应的置换
14·在双链表上实现线性表的下列基本运算(a)初始化； (b)定位(c)插入(d)删除。 15·设有一双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在双链表上进行一次LOCATEL，X)运算时，令元素值为X的结点中freq域的值增1，并使此链表中结点保持按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的LOCATE运算的算法。 16·若X和Y是用结点大小为1单链表表示的串，设计一个算法找出X中第一个不在y中出
10