济南铁道职业技术学院 专升本辅导教材 数据结构

}

6．下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。 void union (LinkList La, LinkList Lb) {

{ } if (pb) }

四、程序设计

1、设某头指针为head的单链表的结点结构说明如下：（6分） typedef struct node1 {

int data; struct node1*next

(3) ; if (pa -> data data) { pre = pa; pa = pa -> next;} else if (pa -> data > pb ->data) { (1) ; } else

{q = pb; pb = pb -> next; free (q); }

pre = pb; pb = pb -> next; (2) ;

//本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中 LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pd)

}node;

试设计一个算法void change (node*head),将该单链表中的元素按原单链表相反的次序重新存放，即第一个结点变成最后一个结点，第二个结点变为倒数第二个结点，如此等等。 2．设某带头结头的单链表的结点结构说明如下： typedef struct nodel {

int data;

struct nodel*next;

第 16 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

}node;

试设计一个算法：void copy(node*head l, node*head 2)，将以head 1为头指针的单链表复制到一个不带有头结点且以head2为头指针的单链表中。（6分） 3、、设带表头结点的双向链表的定义为 typedef int ElemType;

typedef struct dnode { //双向链表结点定义 ElemType data; //数据

struct dnode * lLink, * rLink; //结点前驱与后继指针 } DblNode;

typedef DblNode * DblList; //双向链表 试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。

4、阅读以下程序说明和C程序，将应填入程序中（n） 处的字句，写在答卷的对应栏内。

[程序说明]

本子程序利用递归法判别用链表表示的两个非递归链表是否相等. 程序中的非递归列表定义为: ⑴无元素的空列表;

⑵由元素序列组成的一个列表,其中的元素可以是一个字符,?或者是满足本定义的一个列表. 这种列表的一个例子是: Ｓ

┌───┐ ┌─┬─┬─┐ ┌─┬─┬─┐ │ ├→┤0 │ａ│ ├-→┤１│││＾│ └───┘ └─┴─┴─┘ └─┴┼┴─┘

┌──────┘

│ ┌─┬─┬─┐ ┌─┬─┬─┐ └→┤0 │ｂ│ ├→┤０│c │＾│ └─┴─┴─┘ └─┴─┴─┘

列表S由两个元素组成：第一个元素是字符a (标志为0)；第二个元素是另一个列*表(标志为1),该元素又有两个元素组成(标志为0),分别为字符b和字符c.

在两个列表中,若它们的元素个数相等,且表中元素依次相同,则两个列表相等(子程序回答1),否则不相等(子程序回答0).

[程序]

typedef struct lnode

{ int tag; union

{ char data;

struct lnode *dlink; } un;

struct lnode *link; } listnode;

int equal(s,t) listnode *s,*t; { int x,res; if(s==t) __(1)__ ;

else if( __(2)__ )

第 17 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

if( __(3)__ ) { if(!s->tag) x= __(4)__ ; else

x= __(5)__ ;

if(x) return (__(6)__); }

return(0);

}

5、阅读下列函数说明和Ｃ代码，将应填入其中__(n)__处的字句写在答卷的对应栏内。 【函数1.1说明】 设链表结点的类型为

typedef struct elem{ int val；

struct elem *next； }intNode；

函数merge(int *a，int *b)是将两个升序链表a和b合并成一个升序链表。 【函数1.1】

intNode *merge(intNode *a，intNode *b) { intNode *h=a，*p，*q； while(b)

{ for (p=h；p && p→val< b→val；q=p，p = p→next)； if (p = = h) __(1)__；else __(2)__； q=b；b=b→next； __(3)__； }

return h； }

【函数1.2说明】

递归函数dec(int a[]，int n)判断数组a[]的前n个元素是否是不递增的。不递增返回１，否则返回0。 【函数1.2】

int dec(int a[]，int n) { if (n<=1) __(4)__；

if (a[0]

}

第三章 栈和队列 习题

4．1 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)堆栈和队列都是特殊的线性表。 ( )

(2)堆栈和队列都将插入和删除操作限制在表的端点处进行。 ( ) (3)只允许在表的一端进行插入和删除操作的线性表称为堆栈。 ( )

第 18 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

(4)没有元素的堆栈称为空栈，空栈用不着栈顶指针。 ( ) (5)只要堆栈不空，就能任意删除堆栈的元素。 ( )

(6)堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。 ( ) (7)n个元素进栈的顺序一定与它们出栈的顺序相反。 ( ) (8)对采用链式存储结构的堆栈进行操作不必判断溢出。 ( )

(9)给出顺序堆栈的栈顶元素位置的指针是一个指针类型的变量。 ( )

(10)判断顺序堆栈是否为空的标志是top是否等于0(top为栈顶指针)。 ( ) (11)插入和删除操作比较简单是链接堆栈和链接队列的优点之一。 ( ) (12)n个元素进队的顺序与它们出队的顺序一定是相同的。 ( )

(13)没有任何元素的队列称为空队。空队用不着队头指针与队尾指针。 ( ) (14)元素进出队列一定满足“先进先出”的规律。 ( ) (15)链接队列不存在溢出问题。 ( )

(16)在链接队列中删除一个元素是在链表的最前端进行的。 ( ) (17)采用循环链表作为存储结构的队列称为循环队列。 ( ) (18)堆栈和队列都可以用来解决递归问题。 ( ) (19)堆栈和队列都不适合采用散列存储方法。 ( )

(20)无论是顺序队列还是链接队列，插入、删除操作的时间复杂度都是O(1)。 ( ) 4．2单项选择题。

(1)堆栈和队列的共同之处在于它们具有相同的——。

A．逻辑特性 B．物理特性 C．运算方法 D．元素类型 (2)堆栈和队列都是特殊的线性表，其特殊性在于_______。 A．它们具有一般线性表所没有的逻辑特性 B．它们的存储结构比较特殊 C．对它们的使用方法做了限制 D．它们比一般线性表更简单

(3)若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是——。

A．2，4，3，1，5 B．2，3，1，5，4 C．3，1，4，2，5 D．3，1，2，5，4 (4)某队列初始为空，若它的输入序列为a，b，c，d，它的输出序列应为——。 A．a，b，c，d B．d，c，b，a C．a，c，b，d D．d，a，c，b

(5)当4个元素的进栈序列给定以后，由这4个元素组成的可能的出栈序列应该有——。 A．24种 B．17种 C．16种 D．14种

(6)设n个元素的进栈序列为1，2，3，?，n，出栈序列为p1，p2，p3，?，pn，若Pi=n，则B(1≤i

A．为i B．为n-i C．为n-i+l D．有多种可能

(7)设n个元素的进栈序列为p1，p2，p3，?，pn，出栈序列为1，2，3，?，n，若Pn=l，则n(1≤i< n)的值——。

A．为i B．为n-i C．为n-i+l D．有多种可能

(8)若堆栈采用顺序存储结构，正常情况下，往堆栈中插入一个元素，栈顶指针top的变化是 ______. A．不变 B．top=0 C．top-- D．top++

(9)若堆栈采用顺序存储结构，正常情况下，删除堆栈中一个元素，栈顶指针top的变化是 ______. A．不变 B．top=0 C．top-- D．top++

(10)若队列采用顺序存储结构，元素的排列顺序——。 A．与元素的值的大小有关

B．由元素进入队列的先后顺序决定

第 19 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

C．与队头指针和队尾指针的取值有关 n与作为顺序存储结构的数组的大小有关 (11)“链接队列”这一概念不涉及——。

A．数据的存储结构 B．数据的逻辑结构 C.对数据进行的操作 D．链表的种类

(12)若堆栈采用链式存储结构，栈顶指针为top，向堆栈插入一个由p所指的新结点的过程是依次执行：——，top=p。

A．p=top B．top=p C．p->link=top D．top->link=p

(13)若非空堆栈采用链式存储结构，栈顶指针为top，删除堆栈的一个元素的过程是依次执行：p=top，——，free(p)。

A．top=p B．top=p->link C．p=top->link D．p=p->link

(14)若队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，向队列中插入一个由p所指的新结点的过程是依次执行：——，rear=p。

A．rear=p B．front=p C．rear->link=p D．front->link=p

(15)若非空队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，删除队列的一个元素的过程是依次执行：p=front，——，free(p)。

A．rear=p B．rear=p->link C．rear=p->link D．front=p->link

(16)在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列队空的条件是——。

A．front=rear+1 B。rear=front+1 C．front--rear D．b叭t：0

(17)若描述某循环队列的数组为ClUELIE[M]，当循环队列满时，队列中有——个元素。 A．M B．M-1 C．M十1 D．M+2

(18)在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓 冲区应该是一个——结构。

A．线性表 B．数组 C．堆栈 D．队列

(19)设计一个递归问题的非递归算法通常需要设置——结构。 A．线性表 B．数组 C．堆栈 D．队列 (20)中缀表达式A-(B+C／D)*E的后缀形式是——。

A．ABC+D／*E— B．ABCD／+E*— C．AB-C十D／E* D．ABC-+D／E* 4．3 填空题。

(1)堆栈和队列的逻辑结构都是——结构。

(2)堆栈的插入和删除操作都是在——位置进行，而队列的插入操作在——进行，删除操作在——进行。 (3)对某堆栈执行删除操作时，只有在——情况下，才会将栈底元素删除。

(4)在具体的程序设计过程中，堆栈的顺序存储结构一般是利用一个——描述的，同时还要定义一个整型变量来——。

(5)若堆栈采用顺序存储结构，在不产生溢出的情况下往堆栈中插人一个新元素，首先——，然后——。 (6)若队列采用顺序存储结构，未溢出时插入一个元素首先——，然后再——。 (7)当堆栈的最大长度难以估计时，堆栈最好采用——存储结构。 (8)递归算法都可以通过设置——机制改写成等价的非递归算法。 (9)中缀形式的算术表达式A+(B-C)／D*E的后缀形式为——。

(10)后缀形式的算术表达式ABCD/-E*+的中缀形式为——。

4．4 已知堆栈采用链式存储结构，初始时为空，请画出a，b，c，d四个元素依次进栈以后该堆栈的状态，

然后再画出此时的那个栈顶元素出栈后堆栈的状态。

第 20 页 共 63 页