数据结构题库课后练习题答案章节测试题1-9章全.doc

第一章 绪论
一．填空题
1.数据结构是一门研究非数值计算的程序设计问题中计算机的_____________ 以及它们之间的_________ 和操作等的学科。
2.数据结构包括数据的_____________ 结构、_____________ 结构和运算。
3.数据的物理结构被分为_________、________、__________和___________四种。
4.数据的逻辑结构是指数据元素之间的逻辑关系，根据数据元素之间关系的不同特性，逻辑结构通常有_______________ ，________________ ，________________ 和 __________________四类基本结构。
5.一种抽象数据类型包括 ____________和_____________ 两个部分。
6.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为____________当结点之间存在1 对N（1：N）的联系时，称这种结构为____________。
7.数据结构被形式地定义为（D, R），其中D是___________ 的有限集合，R是D上的有限集合。
8. 数据的基本单位是________，它在计算机中是作为一个整体来处理的。
9.算法的特性有________，___________ ，____________ ，_______________ 和__________ 等五种特性。
10.通常从四个方面评价算法的质量：_________、_________、_________和_________。
11.算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
12.算法的效率可分为______________ 效率和__________________ 效率。
13.算法的时间复杂度为(3n3+2000nlog2n+90)/n2，其数量级表示为________。
14.下面程序段的时间复杂度为____________。
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
a[i][j]=i*j;
15．for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_________。
16．对算法从时间和空间两方面进行度量，分别称为_____和_______ 分析。
二．选择题
1.计算机识别、存储和加工处理的对象被统称为_________。
A、数据 　　　B、数据元素　　　C、数据结构 　　D、数据类型
2.数据结构通常是研究数据的__________及它们之间的联系。
A、存储和逻辑结构 B、存储和抽象 C、理想和抽象 D、理想与逻辑
3.在数据结构中，从逻辑上可以把数据结构分成__________。
A、动态结构和静态结构 B、紧凑结构和非紧凑结构
C、线性结构和非线性结构 D、内部结构和非内部结构
4．不是数据的逻辑结构是__________。
A、散列结构 B、线性结构 C、树结构 D、图结构
5．不是数据的存储结构是__________。
A、散列结构 B、顺序结构 C、链接结构 D、线性结构
6.同一记录结构中的各数据项的类型__________一致。
A、必须 B、不必 C、不能 D、不可能
8.组成数据的基本单位是__________。
A、数据项 B、数据类型 C、数据元素 D、数据变量
9．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r} ，r={<1 ，2> ，<2 ，3>，<3 ，4> ，<4 ，1>}，则数据结构 A是__________。
A、线性结构 B、树型结构 C、图型结构 D、集合
10．设某数据结构的二元组形式表示为 A=(D ，R)，D={01 ，02，03，04，05，06，07，08，
09}，R={r} ，r={<01 ，02>，<01，03>，<01 ，04>，<02 ，05>，<02 ，06>，<03 ，07>，
<03 ，08>，<03，09>}，则数据结构 A是__________。
A、线性结构 B、树型结构 C、物理结构 D、图型结构
11.对一个算法的评价，不包括如下__________方面的内容。
A、健壮性和可读性 B、并行性 C、正确性 D、时空复杂度
12.算法的五个重要特性是________？
A、可执行性、可移植性、可扩充性、输入和输出。
B、可行性、确定性、有穷性、输入和输出。
C、确定性、有穷性、稳定性、输入和输出。
D、可执行性、可移植性、可扩充性、输入和输出。
13．算法分析的两个方面是________。
A、空间复杂性和时间复杂性 B、正确性和简明性
C、可读性和文档性 D、数据复杂性和程序复杂性
14. 算法分析的目的是__________？
A、找出数据结构的合理性 B、研究算法中的输入和输出的关系
C、分析算法的效率以求改进 D、分析算法的易懂性和文档性
15. 以下算法的空间复杂度是__________。
#include
#define n 10
cout(int A[])
{
int B[n],i;
for(i=0;i<N;I++)< p>
B[n-i-1]=A[i];
for(i=0;i<N;I++)< p>
printf("%d",B[i]);
}
A、O(1) B、O(n) C、O(log2n) D、O(n*n)
16．下面程序的时间复杂为__________。
for（i=1，s=0； i<=n ； i++ ）
{
t=1 ；
for(j=1；j<=i；j++)
t=t*j ；
s=s+t；
}
A、O(n) B、O(n2) C、O(n3) D、O(n4)
17.一个算法的时间复杂度为(9n2+2nlog n+2)/(5n)，其数量级表示为________。
A、O(1) B、O(n2) C、O(log2n) D、O(n)
18.阅读以下的程序段,它的时间复杂度为__________。
for(i=1;i<=m;++i)
for(j =1;j<=n;++j)
c[i][j]=0;
A、O(n) B、O(m+2n) C、O(m+n) D、O(m*n)
19．程序段 s=i=0；do {i=i+1 ； s=s+i ；}while(i<=n)；的时间复杂度为（ ）。
A、O(n) B、O(nlog2n) C、O(n2 ) D、O(n/2)
20．下列程序段的时间复杂度为__________。
for(i=0 ； i<m； i++) for(j=0 ； j<t ； j++) c[i][j]=0 ；
for(i=0 ； i<m； i++) for(j=0 ； j<t ； j++) for(k=0 ； k<n ； k++) c[i][j]=c[i][j]+a[i][k]*b[k][j] ；
A、 O(m*n*t) B、O(m+n+t) C、O(m+n*t) D、O(m*t+n)
21. 在数据结构中，与所使用的计算机无关的是数据的__________结构。
A、逻辑 B、存储 C、逻辑和存储 D、物理
22. 数据结构在计算机中的表示是指__________？
A、数据的逻辑结构 B、数据结构 C、数据的存储结构 D、数据元素之间的关系
23. 下面__________的时间复杂性最好，即执行时间最短。
A、O(n) B、O(log2n) C、O(nlog2n) D、O(n2)
三、判断题
1. 程序越短，程序运行的时间就越少。
2. 数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。
四、简答题
1．数据的逻辑结构有哪几种？常用的存储有哪几种？
2．举一个数据结构的例子，叙述其逻辑结构、存储结构和运算三方面的内容。
3．什么叫算法？它有哪些特性？
4．有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑结构图，并指出它们分别以属于何种结构。
（1）A=(K,R),其中
K={a,b,c,d,e,f,g,h}
R={r}
r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}
(2) B=(K,R),其中
K＝{a,b,c,d,e,f,g,h}
R={r}
r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}
(3) B=(K,R),其中
K={1,2,3,4,5,6}
R={r}
r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}
5．简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。
6. 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。
7. 设有数据结构(D,R)，其中
，，
试按图论中图的画法惯例画出其逻辑结构图。
解：

8.设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：
(1) i=1; k=0;
while(i<=n-1){
@ k += 10*i;
i++;
}
(2) i=1; k=0;
do {
@ k += 10*i;
i++;
} while(i<=n-1);
(3) i=1; k=0;
while (i<=n-1) {
i++;
@ k += 10*i;
}
(4) k=0;
for(i=1; i<=n; i++) {
for(j=i; j<=n; j++)
@ k++;
}
(5) for(i=1; i<=n; i++) {
for(j=1; j<=i; j++) {
for(k=1; k<=j; k++)
@ x += delta;
}
(6) i=1; j=0;
while(i+j<=n) {
@ if(i>j) j++;
else i++;
}
(7) x=n; y=0; // n是不小于1的常数
while(x>=(y+1)*(y+1)) {
@ y++;
}
(8) x=91; y=100;
while(y>0) {
@ if(x>100) { x -= 10; y--; }
else x++;
}
解：(1) n-1
(2) n-1
(3) n-1
(4) n+(n-1)+(n-2)+...+1=
(5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=
=
=
(6) n
(7) 向下取整
(8) 1100
五、程序算法题
1.设n为整数，求下列各程序段的时间复杂度
（1）i=1;k=2;
While(i<n){
k=k+10*I;
i=i+1;
}
(2)i=1;j=0;
While(i+j<=n)
If(i>j)j=j+1;
Else i=i+1;
(3)x=91;y=100
While(y>0)
If(x>100){
x=x-10;
y=y-1;
}else x=x+1;
2. 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值
解：
int max3(int x,int y,int z)
{
if(x>y)
if(x>z) return x;
else return z;
else
if(y>z) return y;
else return z;
}

第二章 线性表
一、选择题
1．线性表是具有n个__C___的有限序列（n>0）。
A．表元素 B．字符 C．数据元素 D．数据项
2．一个顺序表所占用的存储空间大小与___B___无关。
A．表的长度 B．元素的存放顺序
C．元素的类型 D．元素中各字段的类型
3．线性表的顺序存储结构是一种__A___。
A．随机存取的存储方式 B．顺序存取的存储方式
C．索引存取的存储方式 D．Hash存取的存储方式
4. 若线性表采用顺序存储结构，每个元素占用 4 个存储单元，第一个元素的存储地址为 100,则第 12 个元素的存储地址是__B____。
A．112 B.144 C.148 D.412
5. 线性表是__A____。
A．一个有限序列，可以为空 B．一个有限序列，不能为空
C．一个无限序列，可以为空 D．一个无限序列，不能为空
6．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为__C____。
A．O（n）O（n） B．O（n）O（1） C．O（1）O（n） D．O（1）O(1)
7．若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中___A____中数据元素。
A．n-i B．n+i C．n-i+1 D．n-i-1
8．对顺序存储的线性表，设其长度为n，在任何位置插入或删除操作都是等概率的。删除一个元素时平均要移动表中的____C____个元素。
A.n/2 B.（n+1）/2 C.（n-1）/2 D.n
9．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为__C____。（1≤i≤n+1）
A．O（0） B．O（1） C．O（n） D．O（n2）
10．线性表中各链接点之间的地址___C____。
A．必须连续 B．部分地址必须连续
C．不一定连续 D．连续与否无所谓
11．在n个结点的线性表的数组表示中，算法的时间复杂度是O（1）的操作是_A______。
A．访问第i个结点后插入一个新结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．以上都不对
12．单链表中，增加一个头结点的目的是为了____C_____。
A．使单链表至少有一个结点 B．标识表结点中首结点的位置
C．方便运算的实现 D．说明单链表是线性表的链式存储
13．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是_B____。
A．head==NULL B．head->next==NULL
C．head->next==head D．head!=NULL
14．将长度为n的单链表链接在长度为m的单链表后面的算法的时间复杂度采用大O形式表示应该是___C____。
A．O（1） B．O（n） C．O（m） D．O（n+m）
15．静态链表中指针表示的是___C____。
A．下一个元素的地址 B．内存储器的地址
C．下一个元素在数组中的位置 D．左链或右链指向的元素的地址
16．非空的循环单链表head的尾结点p满足__A______。
A．P->link=head B．P->link=NULL C．P=NULL D．P=head
17．某线性表用带头结点的循环单链表存储，头指针为head，当head->next->next==head成立时，线性表的长度是___B____。
A．0 B．1 C．2 D．3
18．在什么情况下，应使用链式结构存储线性表L?___B____
A．需经常修改L中的结点值 B．需不断对L进行删除插入
C．需要经常查询L中的结点值 D．L中结点结构复杂
19．与单链表相比较，双向链表的优点之一是___D_____。
A．可以省略头结点指针 B．可以随机访问
C．插入、删除操作更简单 D．顺序访问相邻结点更灵活
20．某线性表常发生的操作为删除第一个数据元素和最后一个元素后添加新元素，采用__D__作为存储结构，能使其存储效率和时间效率最高。
A．单链表 B．仅用头指针的循环单链表
C．双向循环链表 D．仅用尾指针的循环单链表
21．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用_D___存储方式最节省运算时间。
A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表
22．对于一个线性表既要求能够进行较快的插入和删除，又要求存储结构能够反映数据之间的逻辑关系，则应用___C____。
A．顺序方式存储 B．散列方式存储 C．链接方式存储 D．以上方式均可
23．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用___A___存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
24．若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式为___D_____。
A．单链表 B．双向链表 C．单循环链表 D．顺序表
25．下面哪一条是顺序存储结构的优点？___C______
A．插入运算方便 B．可方便地用于各种逻辑结构的存储表示
C．存储密度大 D．删除运算方便
26．下面关于线性表的叙述中，错误的是___B_____。
A.线性表采用顺序存储，必须占用一批连续的存储单元
B.线性表采用顺序存储，便于进行插入和删除的操作
C.线性表采用链接存储，不必占用一片连续的存储单元
D.线性表采用链接存储，便于插入和删除操作
27．在非空线性链表中由p所指的链接点后面插入一个由q所指的链接点的过程是依次执行动作__B____。
A．q->link=p；p->link=q； B．q-link=p->link；p->link=q；
C．q->link=p->link；p=q； D．p->link=q；q->link=p；
26．在非空双向循环链表中由q所指的链接点前面插入一个由p指的链接点的过程是依次执行语句p->rlink=q；p->llink=q->llink;q->llink=p; ____D____。
A．q->rlink->llink=p; B．q->llink->rlink=p;
C．p->rlink->llink=p; D．p->llink->rlink=p;
29．在非空双向循环链表中由q所指的链接点后面插入一个由p指的链接点的动作依次为__D____。
A．p->llink=q ; p->rlink=q->rlink ; q->rlink=p ; q->rlink->llink=p；
B．p->rlink=q->rlink ; p->llink=q ; q->rlink ; q->rlink->llink=p；
C．p->llink=q ; p->rlink=q->rlink ; q->rlink=p ; p->llink->rlink=p；
D．p->llink=q ; p->rlink=q->rlink ; q->rlink=p ; p->rlink->llink=p；
30．在双向链表存储结构中，删除p所指的结点时须修改指针__A____。
A．p->llink->rlink=p->rlink ; p->rlink->llink=p->llink ;
B．p->llink=p->llink->llink ; p->llink->rlink=p ;
C．p->rlink->llink=p ; p->rlink=p->rlink->rlink ;
D．p->rlink=p->llink->llink ; p->llink=p->rlink->rlink ;
31．单链表的存储密度为__C____。
A．大于1 B．等于5 C．小于1 D．不能确定

二．判断题
1. 线性表的逻辑顺序与存储顺序总是一致的。 （ ）
2. 线性表的顺序存储结构比链式存储结构更好。 （ ）
3. 线性表中的所有元素都有一个前驱元素和后继元素。 （ ）
4. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X 的结点的时间复杂度均为O(n)。 （ ）
5. 线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。 （ ）
6. 非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（ ）
7. 用一组地址连续的存储单元存放的元素一定构成线性表。 （ ）
8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（ ）
9. 顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （ ）
10. 顺序表中所有结点的类型必须相同。 （ ）
11. 对链表进行插入和删除操作时不必移动链表中结点。 （ ）
12. 非空的双向循环链表中任何结点的前驱指针均不为空。 （ ）
13. 链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 （ ）
14. 单链表从任何一个结点出发，都能访问到所有结点。 （ ）
15. 符号p->next 出现在表达式中表示p 所指的那个结点的内容。（ ）
16. 带表头结点的双向循环链表判空的条件是： first->rlink == first（first 为表头指针）。 （ ）

三、综合应用题
1.利用顺序表的操作，实现以下函数：
1）从顺序表中删除具有最小值的元素并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。
2）从顺序表中删除第i个元素并由函数返回被删除元素的值，如果i不合理或顺序表为空则显示出错信息并退出运行。
3）向顺序表中第i个位置插入一个新元素x。如果i不合理则显示出错信息并退出运行
4）从顺序表中删除具有给定值x的所有元素。
5）从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。如果s或t不合理或者顺序表为空，则显示错误信息并退出。
6）从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空，则显示错误信息并退出。
7）将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表
8）从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。
2.请设计算法将不带头结点的单链表就地逆置。
3.有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。
4.设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：
找出最小值结点，且打印该数值。
若该数值是奇数，则将其与直接后继结点的数值交换。
若该数值是偶数，则将其直接后继结点删除。
5.给定（已生成）一个带表头结点的单链表，设head为头指针，结点的结构为（data，next），data为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作辅助空间）。
6.假设有两个按元素值递增次序排列的线性表，并要求利用原来两个单链表的结点存放归并后的单链表。
7.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7,10,10,21,30,42,42,42,51,70）将变为（7,10,21,30,42,51,70）。
8.试编写在带头结点的单链表中删除一个最小值结点的高效算法：void delete(Linklist &L)。
9.已知两个单链表A和B，其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。
10.已知非空线性表由list指出，链结点的构造为（data，link）。请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面（要求：不得额外申请新的链结点）。
11.带头结点且头指针为ha和hb的两线性表A和B分别表示两个集合，两表中的元素皆为递增有序。请写一算法求A和B的并集A U B，要求该并集中的元素仍保持递增有序，且要利用A和B的原有结点空间。
12.已知两个链表A和B分别表示两个集合，其元素递增排列。编写一函数程序，求A与B的交集，并存放于A链表中。
13.设计一个求两个集合A和B之差C=A-B的程序，即当且仅当e是A的一个元素，但不是B中的一个元素时，e才是C中的一个元素。集合用有序链表实现，初始时，A、B集合中的元素按递增排列，C为空；操作完成后，A、B保持不变，C中元素按递增排列。下面的函数append（last，e）是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；在执行A-B运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当A-B运算执行完毕后，再删除并释放表示结果集合的链表的表头结点。
typedef struct node{
int element;
struct node *link;
}NODE;;
NODE *A,*B,*C;
NODE *append (NODE *last,int e){
last->link=(NODE*)malloc(sizeof(NODE));
last->link->element=e;
return (last->link);
}
NODE *difference (NODE *A,NODE *B)
{
………
}
14.设一单向链表的头指针为head，链表的记录中包含着整数类型的key域，试设计算法，将此链表的记录按照key递增的次序进行就地排序。
15.设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于等于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。
16.将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。
1）写出其类型定义。
2）写出算法。
17.两个整数序列A=a1，a2，a3，…，am和B=b1，b2，b3，…，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。
18.已知线性表（a1，a2，a3，…，an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值（假设0为正数）元素前边的算法。例如：（x，-x，-x,x,x,-x, …,x）变为（-x,-x,-x, …,x,x,x）。
19.一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef，指数域exp和指针域next。现对链表求一阶导数，链表的头指针为ha，头结点的exp域为-1。
20．设用带头结点的双向循环链表表示的线性表为L=（a1，a2,a3, …,an）。写出算法将L改造成：L=（a1,a3, …,an, …,a4,a2）.
结点和结点指针类型定义如下：
typedef struct node{
ElemType data;
Struct node *prior,next;
}*DLinkList;
21.设有一个头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针）、data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate（L，x）运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate（L，x）运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。

第三章 栈和队列
一．选择题
1.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当做退栈处理时，top变化为 。
A．top不变 B．top＝top-n C．top＝top-1 D．top=top+1
2.在一个顺序存储的循环队列中，队首指针指向队首元素的 。
A．前一个位置 B．后一个位置 C．队首元素位置 D．队尾元素位置
3.若进栈序列为1,2,3,4,栈过程中可以出栈，则 不可能是一个出栈序列。
A．3,4,2,1 B．2,4,3,1 C．1,4,2,3 D．3,2,1,4
4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是 。
A．front= =rear+1 B．front+1= =rear C．front= =rear D．front= =0
5.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行 。
A．hs->next=s; B．s->next=hs->next;hs->next=s;
C．s->next=hs;hs=s; D．s->next=hs;hs=hs->next;
6.下列说法哪个正确：_______
A．堆栈是在两端操作、先进后出的线性表
B．堆栈是在一端操作、先进先出的线性表
C．队列是在一端操作、先进先出的线性表
D．队列是在两端操作、先进先出的线性表
7.栈和队列的共同点_______
A．都是先进后出 B．都是先进先出
C．只允许在端点处插入和删除元素 D．没有共同点
8.以下数据结构中哪一个是非线性结构？_______
A．队列 B．栈 C．线性表 D．二叉树
9.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3 ，…，pn，若p1=n，则 pi 为_______
A．i B．n=i C．n-i+1 D．不确定
10.当利用大小为 N 的一维数组顺序存储一个栈时，假定用top==N 表示栈空，则向这个栈插入一个元素时，首先应执行_______语句修改top指针。
A．top++ B．top-- C．top=0 D．top
11.4个元素进S栈的顺序是 A,B,C,D,经运算 POP(S)后栈顶元素是_______
A．A B．B C．C D．D
12.一个栈的输入序列是a,b,c,d,e,则栈的不可能的输出序列是_______
A. edcba B.decba C.dceab D. abcde
13．设用链表作为栈的存储结构则退栈操作_______。
A．必须判别栈是否为满 B．必须判别栈是否为空
C．判别栈元素的类型 D．对栈不作任何判别
14．设输入序列是 1、2、3、……、n，经过栈的作用后输出序列的第一个元素是 n，则输出序列中第i个输出元素是_______。
A． n-i B．n-1-i C．n+1-i D．不能确定
15．递归函数f(n)=f(n-1)十 n(n>1) 的递归出口是_______。
A．f(1)=0 B．f(1)=1