发布时间 : 星期三 文章数据结构c语言版试题大全（含答案）更新完毕开始阅读13adb34dc850ad02de804116
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 -