数据结构c语言版试题大全（含答案）

3、True 4、True 5、False 6、False

数据结构复习题：栈和队列 算法分析题

1、设计一个算法,利用栈的基本运算将指定栈中的内容进行逆转。 2、设计一个算法,利用栈的基本运算返回指定栈中的栈底元素。

3、有两个栈s1和s2共享存储空间c[1..MaxSize],其中一个栈底设在c[1]处,另一个栈底设在c[MaxSize]处,分别编写s1和s2的进栈push(i,x)、退栈pop(i)和设置栈空setnull(i)的函数,其中i=1,2。注意:仅当整个空间c[1..MaxSize]占满时才产生上溢。

6、用不带头结点的单链表存储链栈,设计初始栈、判断栈是否为空、进栈和出栈等相应的算法。

数据结构复习题答案：栈和队列 算法分析题

1、status Nizhuan(sqstacks, int a, int b, int t) {

If(s.top==s.base) error(‘no data’);

for(i=0;i

a=*--top; b=*s.base; a=t;t=b;b=a; s.top--; s.base++; } }

2、status Getbase(Aqstacks,int &e) {

If(s.top==s.base) Error(‘no data’) else

e =*s.base; return e; } 3、（1）初始化操作 【共享栈的初始化】

int initDupStack(dupsqstack *s)

{/*创建两个共享邻接空间的空栈由指针S指出*/

if((s=(dupsqstack*)malloc(sizeof(dupsqstack)))==NULL)

- 37 -

return FALSE; s->lefttop= -1;

s->righttop=MAXNUM; return TRUE; }

（2）入栈操作

【共享栈的入栈操作】

int pushDupStack(dupsqstack *s,char status,Elemtype x)

{*把数据元素x压入左栈（status=’L’）或右栈（status=’R’）*/ if(s->lefttop+1= =s->righttop) return FALSE; /*栈满*/ if(status=’L’)

s->stack[++s->lefttop]=x; /*左栈进栈*/ else

if(status=’R’)

s->stack[--s->lefttop]=x; /*右栈进栈*/ else

return FALSE; /*参数错误*/ return TRUE; }

（3）出栈操作

【共享栈的出栈操作】

Elemtype popDupStack(dupsqstack *s,char status) {/*从左栈（status=’L’）或右栈（status=’R’）退出栈顶 6、（1）入栈操作

【单个链栈的入栈操作】

int pushLstack(slStacktype *top,Elemtype x)

{//将元素x压入链栈top中 slStacktype *p;

if((p=(slStacktype*)malloc(sizeof(slStacktype)))==NULL) return FALSE; //申请一个结点 p->data=x; p->next=top; top=p;

return TRUE; }

（2）出栈操作

【单个链栈的出栈操作】

Elemtype popLstack(slStacktype *top) {//从链栈top中删除栈顶元素 slStacktype *p; Elemtype x; if (top= =NULL) return NULL; //空栈

- 38 -

p=top;

top=top->next; x=p->data; free(p); return x; }

数据结构复习题：栈和队列 填空题

1、在具有n个单元、顺序存储的循环队列中，队满时共有______个元素。 2、栈和队列的区别仅在于________。 3、通常元素进栈的操作是________。 4、通常元素退栈的操作是________。

5、一个栈的输入序列是12345,则栈的输出序列432512是__________。 6、一个栈的输入序列是12345,则栈的输出序列12345是________。 7、设有一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为________。

8、设栈采用顺序存储结构,若己知i-1个元素进栈,则将第i个元素进栈时,进栈算法的时间复杂度为________。

9、若用不带头结点的单链表来表示链栈S,则创建一个空栈所要执行的操作是________。 10、从环形队列中插入一个元素时,通常的操作是________。

11、在具有n个单元的环形队列(共有MaxSize个单元)中,队满时共有________个元素。 12、在链表qu中,判定只有一个结点的条件是________。

13、设栈S和队列Q的初始状态为空,元素a1,a2,a3,a4,a5,a6,a7和a8依次通过栈S,一个元素出栈后立即进入队列Q,若8个元素出队列的顺序是a3,a6,a7,a5,a8,a4,a2,a1,则栈S的容量至少应该是多少(即至少应该容纳多少个元素)?

14、设有算术表达式x+a*(y-b)-c/d,该表达式的前缀表达为________。后缀表示为______。 15、栈是一种具有______特性的线性表。

16、顺序栈和链栈的区别仅在于______的不同。

17、如果栈的最大长度难以估计,则最好使用______。

18、一个栈的输入序列是12345,则栈的输出序列12345是______。 19、设栈采用顺序存储结构,若己知i-1个元素进栈,则将第i个元素进栈时,进栈算法的时间复杂度为______。 20、表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是______。

21、若用不带头结点的单链表来表示链栈1st,则创建一个空栈所要执行的操作是______。 22、对于链栈1st,进栈操作在______端进行,出栈操作在_____端进行。 23、将递归算法转换为非递归算法时,通常使用______这种数据结构。 24、有如下递归算法: void print (int w) { int i;

if (w!=0) { print(w-1);

- 39 -

for(i=1;i<=w;i++) printf(\ printf(\ } }

调用语句printf(4)的结果是______。 25、有如下递归过程: void reverse(int m) {

printf(\ if (n/10 !=0) reverse(n/10); }

调用语句reverse(582)的结果是______。

26、求顺序存储的集合的长度的时间复杂度为____________。 27、求链接存储的集合的长度的时间复杂度为____________。

28、设集合S的长度为n，则判断x是否属于集合Ｓ的时间复杂度为____________

31、在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应____________对应三元组线性表的长度。

数据结构复习题答案：栈和队列 填空题 1、n-1

2、删除运算的不同

3、先移动栈顶指针，后存入元素 4、先取出元素，后移动栈顶指针 5、不可能的 6、可能的 7、3 8、O(1) 9、S=NULL

10、先存放元素,后移动队尾指针 11、MaxSize-1

12、qu->front==qu->rear&&qu->front!=NULL 13、5

14、-+x*a-yb/cd|xayb-*+cd/- 15、后进先出 16、存储结构 17、链栈 18、可能的 19、O(1)

20、23 12 3 * 2 - 4 / 34 5 * 7 / + + 108 9 / + 21、1st=NULL

22、链栈头|链栈头

- 40 -