A、表元素 B、字符 C、数据元素 D、数据项
19、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。
A、顺序表 B、双链表 C、带头结点的双循环链表 D、单循环链表 20、在双向链表指针p的结点前插入一个指针q的结点操作是（C ）。 A、p->prior=q;q->next=p;p->prior->next=q;q->prior=q； B、p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior; C、q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q; D、q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;
21、若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（D ）存储方式最节省时间。
A、单链表 B、双链表 C、单向循环 D、顺序表 22、链表不具有的特点是（ B ）
A、插入、删除不需要移动元素 B、可随机访问任一元素 C、不必事先估计存储空间 D、所需空间与线性长度成正比
23、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。
A、O(n) O(n) B. O(n) O(1) C、 O(1) O(n) D.O(1) O(1)
24、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B） A、head==NULL B、head→next==NULL C、head→next==head D、head!=NULL 25、在双向链表存储结构中，删除p所指的结点时须修改指针（S）。
A、p->prior->next=p->next；p->next->prior=p->prior; B、p->prior:=p->prior->prior；(p->prior)^.rlink:=p; C、p->next->prior=p；p->next=p->next->next
D、p->next =p->prior->prior；p->prior=->next->next;
四、简答题
1、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
6
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 2、在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?
答：在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。
五、算法设计题
1、有一个单链表，其头指针为head，编写一个算法计算数据域为x的结点的个数。
Int count（Node *heaD、{ node *p;
int n=0; p＝head； While（P！＝ NULL）｛ if（P->data==X） n＋＋； P=p->next；｝ return（n） }
2、试编写在带头结点的单链表中删除一个最小值结点的高效算法。
Void delete（Linklist &L）
∥L是带头结点的单链表，本算法删除其最小值结点。
{p=L->next；∥p为工作指针。指向待处理的结点。假定链表非空。 pre=L； ∥pre指向最小值结点的前驱。
q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点。 while（p->next!=null）
{if（p->next->data
pre->next=q->next；∥从链表上删除最小值结点 free（q）； ∥释放最小值结点空间 }∥结束算法delete。
3、已知不带头结点的线性链表list，链表中结点构造为（data、next），其中data为数据
域，next为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。 LinkedList LinkListSort(LinkedList list)
7
∥list是不带头结点的线性链表，链表结点构造为data和link两个域，data是数据域，link是指针域。本算法将该链表按结点数据域的值的大小，从小到大重新链接。
{p=list->next; ∥p是工作指针，指向待排序的当前元素。
list-> next=null;∥假定第一个元素有序，即链表中现只有一个结点。 while(p!=null)
{r=p-> next; ∥r是p的后继。 q=list;
if(q->data>p->data ∥处理待排序结点p比第一个元素结点小的情况。 {p-> next =list;
list=p;∥链表指针指向最小元素。 }
else∥查找元素值最小的结点。
{while(q-> next!=null&&q-> next ->data
p-> next =q-> next;∥将当前排序结点链入有序链表中。 q-> next =p;}
p=r;∥p指向下个待排序结点。 }}
4、以下程序的功能是实现带头结点的单链表数据结点逆序连接，请填空完善之。 void reverse(pointer h)
/* h为附加头结点指针；类型pointer同算法设计第3题*/
{pointer p,q;
p=h->next; h->next=NULL;
while(p!=null _____)∥链表未到尾就一直作 {q=p; p=p->next; q->next=h->next;
h->next= q; ∥将当前结点作为头结点后的第一元素结点插入
}}
5、设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，链表中结点构造为（data、next），其中data为数据域，next为指针域。请设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。
解：本题明确指出单链表带头结点，其结点数据是正整数且不相同，要求利用直接插入原则把链表整理成递增有序链表。这就要求从第二结点开释，将各结点依次插入到有序链表中。
8
LinkedList LinkListInsertSort(LinkedList la)
∥la是带头结点的单链表，其数据域是正整数。本算法利用直接插入原则将链表整理成
递增的有序链表。
{if(la->next!=null)∥链表不为空表。
{p=la->next->next;∥p指向第一结点的后继。
la->next->next=null;∥直接插入原则认为第一元素有序，然后从第二元素起依次插入 while(p!=null)
{r=p->next;∥暂存p的后继。
q=la;
while(q->next!=null&&q->next->data
q=q->next;∥查找插入位置。 p->next=q->next;∥将p结点链入链表。 q->next=p; p=r; }
6、设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点。 解：void DisCreat1(LinkedList A)
∥A是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C，B中结点的数据小于零，C中结点的数据大于零。 {B=A;
C=(LinkedList )malloc(sizeof(LNode));∥为C申请结点空间。 C->next=null ∥C初始化为空表。 p=A->next; ∥p为工作指针。 B->next=null; ∥B表初始化。 while(p!=null)
{r=p->next; ∥暂存p的后继。 if (p->data<0)∥小于0的放入B表。
{p->next=B->next; B->next=p; }∥将小于0的结点链入B表。 else {p->next=C->next; C->next=p; } p=r;∥p指向新的待处理结点。 }}∥算法结束。
9
第3章 栈和队列 一、填空题
1、队列是限定在 队尾 插入和 队首 删除元素的线性表。
2、栈是_操作受限__的线性表，其运算遵循__后进先出 的原则，最先放入栈中元素在 栈底 ，最后放入的元素在 栈顶 ，而删除元素刚好相反，最后放入的元素 最先 删除，最先放入的元素 最后 删除。
3、对栈的操作限定为：只能在 栈顶 插入和删除元素；
4、栈S的空间大小为stacksize，S.base[0]是栈底元素，S.top是栈顶指针，则：进栈时需将S.top加1，退栈时需将S.top 减1。S.top==0时表示空栈，S.top==stacksize表示栈满。 5、设有一个空栈，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_2，3___。
6、在作进栈运算时应先判别栈是否_满_;在作退栈运算时应先判别栈是否_空 ；当栈中元素为n个，再作进栈运算时发生上溢，则说明该栈的最大容量为_n_。
7、顺序栈用data[1..n]存储，栈顶指针是top,值为x的元素入栈的操作是data[++top]=x。 8、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是：s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s；r=s； 9、循环队列的引入，目的是为了克服__假溢出时大量移动数据元素_，区分循环队列的满与空，有__牺牲一个存储单元__和__设标记_两种方法。
10、在具有n个单元的循环队列中，队满时共有 n-1 个元素。
11、 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。
12、从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。 13、循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_（rear-front+m）% m； _。
14、设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为__ sq.front=(sq.front+1)%(M+1)；return(sq.data(sq.front))；，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_(sq.rear+1)%(M+1)==sq.front；
二、判断题
1、线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（×） 2、在表结构中最常用的是线性表，栈和队列不太常用。（×）
3、栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）
4、对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（√）
10