1．（ ）线性表的顺序存储结构比链式存储结构更好。F 2．( )线性表就是顺序存储的表。× 3．（ ）线性表中的所有元素都有一个前驱元素和后继元素。F 4．（ ）非空的双向循环链表中任何结点的前驱指针均不为空。T 5．（ ）不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。T
6．( )对链表进行插入和删除操作时不必移动链表中结点。T 7．( )线性表只能用顺序存储结构实现。× 8．( )如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。×
9．( )进栈操作时，必须判断栈是否已满。× 10．( )进栈、出栈操作的时间复杂度是O(n)。×
11．( )采用链式结构存储线性表时，其地址可以是不连续的。√ 12．( )线性表中的每个元素都有一个前驱元素和后继元素。× 13．( )采用顺序结构存储线性表时，其地址可以是不连续的。× 14．（ ）如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。√ 15．（ ）线性表的唯一存储形式就是链表。× 16．（ ）线性表不能采用链式存储。× 17．（ ）在单链表中插入结点主要通过移动元素实现。× 18．( )所谓静态链表就是一直不发生变化的链表。× 19．( )集合与线性表的区别在于是否按关键字排序。× 20．（ ）用头部插入结点的方法建立单链表时，插入元素的顺序和链表中的元素顺序相同。× 21．（ ）线性表中的每个元素都有一个前驱元素和后继元素。 × 22．（ ）线性表中每个元素都有一个直接前驱和一个直接后继。× 23．（ ）线性表采用顺序存储表示时，必须占用一片连续的存储单元。√ 24．( )数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。×
25．( )数据的逻辑结构是指数据的各数据项之间的逻辑关系。× 26．( )算法的优劣与算法描述语言无关，但与所用计算机有关。× 27．( )健壮的算法不会因非法的输入数据而出现莫名其妙的状态。√ 28．（ ）算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。×
29．( )数据的物理结构是指数据在计算机内的实际存储形式。√ 30．( )数据结构的抽象操作的定义与具体实现有关。× 31．( )数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。√ 32．（ ）算法独立于具体的程序设计语言，与具体的计算机无关。√ 33．（ ）Huffman树、平衡二叉树都是数据的逻辑结构。√ 34．（ ）抽象数据类型与计算机内部表示和实现无关。√ 35．（ ）在一个设有头指针和尾指针的单链表中,执行删除该单链表中最后一个元素的操作与链表的长度无关。×
36．( )顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。×
11
37．（ ）顺序存储方式只能用于存储线性结构。× 38．( ) 线性表只能用顺序方式存放。X
39．( ) 在带表头结点的双循环链表中，每个结点的前趋和后继指针均不为空。√
40．（ ）顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。×
41．( )顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 42．（ ）在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。×
43. （ ）在单链表中，要取得某元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。× 四、简答题
1．线性结构与非线性结构的差别
前驱与后继之间通常为一对多或多对多的关系。 2．比较顺序表与单链表的优缺点。 顺序表优点：随机查找，存储密度大
顺序表缺点：插入、删除不便，静态分配，表长固定 单链表优点：插入、删除方便，动态分配，表长灵活
单链表缺点：查找不便，存储密度小 3．简要说明算法与程序的区别。
算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。
4．说明以下三个概念的关系：头指针，头结点，首元素结点。 头指针指向头结点，头结点的后继域指向首元素结点。
5．设有编码为A，B，C，D的4列火车，依次进入一个栈式结构的站台，试写出这4列火车开出站台的所有可能的顺序。
根据栈的数学性质，n个元素的出栈序列数目恰好符合卡塔南数列。 Cn=C2nn/(n+1)=1/n+1*(2n)!/n!(2n-n)! 这里:
1/n+1*(2n)!/n!(2n-n)!=1/5*8!/(4!*4!)=14 ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CBDA CDBA DCBA 分析解答：
6．写出在双向链表中，在指针p所指结点前插入一个结点*S的语句序列。 答： 答：（1）S->prior=P->prior; （2）P->prior->next=S; （3）S->next=P; （4）P->prior=S;
7．试叙述一维数组与有序表的异同。
一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中的元素按值排列（非递增或非递减），而一维数组中的元素没有按元素值排列顺序的要求。 8．试比较顺序存储和链式存储的优缺点。
顺序存储查找效率高，插入和删除效率低；链式存储插入和删除效率高，查找效
12
率低。
9．写出线性表(26,45,12,20,30)采用快速排序算法排序后，第一趟排序过程及结果。
20 12 26 45 30。
10．试说明单链表采用头结点的优点。 解决单链表的“第一个结点问题”，使头指针变量不为空。 11. 画出带头结点的单链表、单循环链表和双向循环链表的示意图，并归纳三者的不同之处。
H a1 ??
an H L A B 单链表：只有从头结点出发，才能访问到所有结点。
单循环链表：从任意一结点出发，均可访问到其他结点。
双向循环链表：既可以方便的找到前趋结点，又可方便的找到后继结点。
12．有五个数依次进栈：1，2，3，4，5。在各种出栈的序列中，以3，4先出的序列有哪几个。（３在４之前出栈）。 【解答】34215 ，34251， 34521 13．铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6， 那么是否能够得到435612， 325641， 154623和135426的出站序列，如果不能，说明为什么不能； 如果能， 说明如何得到(即写出\进栈\或\出栈\的序列)。
【解答】输入序列为123456，不能得出435612和154623。不能得到435612的理由是，输出序列最后两元素是12，因为前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。 得到325641的过程如下：1 2 3顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。 得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。
14．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？ 【解答】2和 4
15．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过
13
栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，e6，e2，e1，则栈S的容量至少应该是多少？ 【解答】 4
16．循环队列的优点是什么，如何判断“空”和“满”。 【解答】循环队列解决了常规用0--m-1的数组表示队列时出现的“假溢出”（即队列未满但不能入队）。在循环队列中，我们仍用队头指针等于队尾指针表示队空，而用牺牲一个单元的办法表示队满：即当队尾指针加1（求模）等于队头指针时，表示队列满。也有通过设标记以及用一个队头或队尾指针加上队列中元素个数来区分队列的“空”和“满”的。
17．设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队的时间如何？若只设尾指针呢？
【解答】若只设头指针，则入队的时间为O(n），出队的时间为O(1)。若只设尾指针，则入队和出队的时间均为O(1)。 18．试将下列递推过程改写为递归过程。 void ditui(int n) {i=n;
while(i>0) printf(i--); }
【解答】void digui(int n) {if(n>0){printf(n); digui(n-1); } }
19．写出下列中缀表达式的后缀表达式：
(1)A*B*C (2)(A+B)*C-D (3)A*B+C/(D-E) (4)(A+B)*D+E/(F+A*D)+C 解答】 (1)ABC** (2)AB+C*D- (3)AB*CDE-/+
(4)AB+D*EFAD*+/+C+
20．线性表的顺序存储结构具有三个弱点：第一，在作插入或删除操作时，需要移动大量元素；第二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；第三，表的容量难以扩充。试问，线性表的链式存储结构是否一定能够克服上述三个弱点？请简述之。【北京师范大学2003二.4(6分)】 链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储结构的缺点。
21．说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。 【厦门大学 2000 五.1 （14%/3分）】 在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。有头结点后，对在
14
第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。
22. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？
【中国人民大学 2001 二.4 （2分）】 本题是链表的逆置问题。设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。
23．已知L是一个数据类型linkedlist的单循环链表，pa和pb是指向L中结点的指针。简述下列程序段的功能。【山东科技大学 2001 一.2 （5分）】 TYPE linkedlist=↑node; node=RECORD
data:datatype; next:linkedlist END;
PROC Mp(pa,pb:linkedlist); PROC subp(s,q: linkedlist); p:=s;
WHILE p↑.next<>q DO p:=p↑.next; p↑.next:=s ENDP;
subp(pa,pb); subp(pb,pa); ENDP;
mp是一个过程，其内嵌套有过程subp。
subp(s,q)的作用是构造从s到q的循环链表。
subp(pa,pb)调用结果是将pa到pb的前驱构造为循环链表。
subp(pb,pa)调用结果是将pb到pa的前驱（指在L链表中，并非刚构造的pa循环链表中）构造为循环链表。 总之，两次调用将L循环链表分解为两个。第一个循环链表包含从pa到pb的前驱,L中除刚构造的pa到pb前驱外的结点形成第二个循环链表。
24．阅读下面的算法，说明算法实现的功能 【东华大学2004二.1(10分)】 a) node *link(node *head1, *head2) {node *p, *q; p=head1;
while (p->next!=head1) p=p->next; q=head2;
while (q->next!=head2) q=q->next; p->next=head2; q->next=head1; return(head1); }
本算法功能是将两个无头结点的循环链表合并为一个循环链表。head1最后一个结点的链域指向head2， head2最后一个结点的链域指向head1，head1为结果循环链表的指针。 五、应用题
15