指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。 (2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。
(3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。
2、不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、 扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。
3、在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指 针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。 4、 (1)向类型有list的线性表L的第i个元素（0≤i≤L.len）之后插入一个新元素x。 (1) 解答: status insert(SqList L,int i,ElemType x){
// 向线性表L中第i个元素之后插入值为x的新元素 (1) if (L.len = =m0) error('overflow');
(2) if (i<0) || (i>L.len) error ('out of range'); (3) for (j=L.len ;j>= i＋1;--j ) L.vec[j＋1]＝L.vec[j]; }
(4) L.vec[i＋1]＝x; (5) L.len＝len＋1; }
(2)从类型为list的线性表L中删除其值等于x的所有元素。 (2) 解答: status delete(L,x) {
// 从线性表L中删除其值等于x的所有元素 i＝1;
while (i<＝L.len ) if (L.vec[i]= =x ){
(Ⅰ) for( j＝i＋1 ;j<= L.len ;++j) L.vec[
5、解答：(1)将一个单链表中的所有结点按相反次序链接。 (1) 解答: status contrary(HL){
// 使HL单链表中的所有结点按相反次序链接
p＝HL ; //p指向未被逆序的第一个结点，初始指向原表头结点 HL＝nil; //HL指向逆序后的表头结点，初始值为空 while (p!=nil ){
(1) q＝p; //q指向将被逆序链接的结点 (2) p＝p＾.next; (3) q＾.next＝HL; (4) HL＝q; } }
- 31 -
(2)删除单链表中第i个（i≥1）结点。 (2) 解答:status delete(HL,i){
(1) if (i<＝0) or (HL＝nil) error('not h&&le'); (2) if (i＝1 )
{ HL＝HL->next; return ; }
(3) j＝1; p＝HL; //p指针所指向的结点，是单链表中第j
6、解答：(1) 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。
(2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。
7、解答：1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。
8、答：顺序表可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率；而链表内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序表方便，但结点的插入、删除操作较简单。 9、答：void Merge (LinkList &La, LinkList Lb) { pa=La->next; pb=Lb->next; p=La; while(pa && pb)
{ if (pa->data<=pb->data)
{p->next=pa; p=pa; pa=pa->next;} else
{p->next=pb; p=pb; pb=pb->next;} }
if(pa) p->next=pa; else p->next=pb; free(Lb); }
- 32 -
3 栈和队列
沈阳理工大学应用技术学院
信息与控制学院 计算机科学与技术教研室
2011-5-8
- 33 -
数据结构复习题：栈和队列 单选题
1、在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为_____。
2、向顺序栈中压入元素时，是_____。
3、在一个顺序存储的循环队列中，队首指针指向队首元素的_____。
4、若进栈序列为1,2,3,4,进栈过程中可以出栈，则_____不可能是一个出栈序列。
5、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是_____。
6、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是_____。
7、向一个栈项指针为hs的链栈中插入一个*s结点时，则执行_____。
8、在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行_____。
9、栈的特点是_______队的特点是______ 10、栈和队列的共同点是_______。
11、一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是________。
12、若己知一个栈的进栈序列是1,2,3,?,n,其输出序列为p1,p2,p3,?,pn,若p1=n,则pi(1 16、若己知一个栈的进栈序列p1,p2,p3,?,pn，输出序列是1,2,3,?,n。若pn=1,则pi(1<=i 20、向一个栈项指针为hs的链栈中插入一个s所指结点时，则执行_______。 21、从一个栈项指针为hs的链栈中删除一个结点时，用x保存被删结点的值，则执行______。 22、一个队列的入队序列是1,2,3,4,则队列的输出序列是_______。 23、判定一个环形队列qu(最多元素为MaxSize)为空的条件是________。 24、判定一个环形队列qi(最多元素为MaxSize)为满队列的条件是________。 25、环形顺序队列中是否可以插入下一个元素,________。 26、环形队列用数组A[0...MaxSize-1]存放其元素值,己知其头尾指针分别是front和rear,则当前队列的元素个数是_______。 27、若用一个大小为6的一维数组来实现环形队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是______。 28、最不适合用作链队的链表是______。 29、在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是_______。 30、在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算是_______。 31、用单链表表示的链队的队头在链用不着的________位置。 32、中缀表达式A*(B+C)/(D-E+F)的后缀表达式是________。 33、己知一个栈的进栈序列是ABC,出栈序列为CBA,经过的栈操作是________。 34、判定一个顺序栈st为(元素个数最多为MaxSize)空的条件为______。 - 34 - 35、判定一个顺序栈st(元素个数最多为MaxSize)为栈满的条件是______。 36、表达式a*(b+c)-d的后缀表达式是______。 37、表达式(2+2*3)*2+6*3/2的后缀表达式是______。 38、链栈与顺序栈相比有一个明显的优点,即______。 39、最不适合用作链栈的链表是______。 40、如果以链表作为栈的存储结构,则退链栈操作时______。 41、向一个不带头结点的栈指针为1st的链栈中插入一个s所指结点时,则执行______。 42、从一个不带头结点的栈顶指针为1st的链栈中删除一个结点时,用x保存被删结点的值,则执行______。 43、一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是______. 44、在一个长度为n的顺序存储的集合中查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度为_________。 45、在一个长度为n的链接存储的集合中查找值为x的元素时，算法的时间复杂度为_________。 46、已知一个元素x不属于一个长度为n的顺序或链接存储的集合Ｓ中的元素，把它插入集合Ｓ时不进行比较过程，则插入过程的时间复杂度为_________。 47、设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为_________。 数据结构复习题答案：栈和队列 单选题 1、top不变|top＝-n |top＝top-1|top=top+1 C 2、先移动栈顶指针，后存入元素|先存入元素，后移动栈顶指针|| A 3、前一个位置|后一个位置|队首元素位置| A 4、3,4,2,1|2,4,3,1|1,4,3,2|3,2,1,4 C 5、front= =rear+1|front+1= =rear|front= =rear|front= =0 C 6、\\rear % n= =front|(rear-1) % n= =front|(rear-1) % n= =rear|(rear+1) % n= =front D 7、hs->next=s;|s->next=hs->next; hs->next=s;|s->next=hs；hs=s;|s->next=hs; hs=hs->next; C 8、front->next=s; front=s;|rear->next=s; rear=s;|front=front->next;|front=rear->next; B 9、先进先出|先进后出|| B|A 10、都是先进后出|都是先进先出|只允许在端点处插入和删除元素|没有共同点 C 11、edcba|decba|dceab|abcde C 12、i|n=i|n-i+1|不确定 C 13、i|n=i|n-i+1|不确定 D 14、可能是2|一定不是2|可能是1|一定是1 A 15、可能是2|一定是2|不可能是2|不可能是3 C 16、n-i+1|n-i|i|有多种可能 A 17、st->top!=-1|st->top==-1|st->top!=MaxSize-1|st->top==MaxSize-1 B 18、st->top!=-1|st->top==-1|st->top!=MaxSize-1|st->top==MaxSize-1 D 19、只有表头指针没有表尾指针的循环双链表|只有表尾指针没有表头指针的循环双链表|只有表尾指针没有表头指针的循环单链表|只有表头指针没有表尾指针的循环单链表 D 20、hs->next=s;|s->next=hs->next;hs->next=s;|s->next=hs;hs=s;|s->next=hs;hs=hs->next; C 21、x=hs;hs=hs->next;|x=hs->data;|hs=hs->next;x=hs->data;|x=hs->data;hs=hs->next; D 22、4,3,2,1|1,2,3,4,|1,4,3,2|3,2,4,1 B 23、qu->rear-qu->front==MaxSize|qu->rear-qu->front-1==MaxSize|qu->front==qu->rear|qu->front==qu->rear+1 C 24、 - 35 -