《据结构习题与解析》（C语言版）

第2章顺序表 >sIST->top=x 出饯 进找 找底 图2.1栈中元素和找顶指针之间的关系 3.栈的弹出pop(ST) 从找中弹出栈顶元素的函数如下: void pop(ST) stack * ST: fsT->tp==0)prin(栈下溢出!vn");*若機空则显示相应信息* ST->top--I /*否则栈指针减1,即栈顶为下一个元素“/ 4.读栈顶元素top(ST,x) 读取栈顶元素而保持栈不变的函数如下: void top(ST.x) i(sT->top==0) printf无找顶元素!v"):/“若栈为空则显示相应信息*/ x=sT->s[sT->top]:/*否則把栈顶元素赋给x但保持栈不变* 5判定栈是否为空 empty(ST) 判定栈ST是否为空栈的函数如下: int empty (ST)

数据结构习题与解析《C语言篇 i(sT->top==0) return(1)41米若找为空则返回true else retn(o) 否则返回fase* 取栈顶元素ptop(sr) 从栈中取出梭顶元素并从饯中删除该找顶元素的函数如下: int ptop(ST〕 stack ST: top(ST.x) *将找顶元菸赋给x pOp(ST)t *将栈顶元素弹出*f return(x): ≯返回x值 2.1.3队列 队列是-种线性表、所有的插入都只允许在表的一端进行插入,在表的另一端进行删 除:进行删除的一端叫队列的头,进行插入的一端叫队列的尾。 1.队列的存储方式 假设队列的元素个数最人不超过幣数m0,所有的元素都具有同一数据类型 datatype, 则可用下列方式来定义队列类型 queue: typedef stru int front. rear 这里的 Elem Type可以是任何相应的数据类型如int,oat或char等,在算法中,我们规 定 ElemType缺省是int类型。变址 front指向队列的头部变量rear指向队列的尾部 般队列的形式如图2.2所示。 出队列 入队列 fr 队头 队尾 图2.2队列 2.队列的插人enq(QU,x 将整数x插入到QU队列中的函数如下:

第2章胍序表 f(oU-:rear==mo) printf("队列上溢出:n") QU- >rear 队尾指针后移 oU→>q[oU->rer,=X 新几素赋给队尾单 if(QU- >front==()QU->front=l: 若原为空队,则进行插入后,同时把队首指针置为* 3.队列元紊的删除 删除一个QU队列尾部元素的函数如下: ifou-> front==t! printf("队姆下溢出!wn") (oU-> front==QU->rear):·队列空的情况 >front=(: else qu -- >> front--: 队列为窀的情况* 读队列的头结点 node(QU,x 读取队列QU的队列头元素的函数如下: void node QUx) f(QU->ront==)prin(“队列下溢出!wn") else=QU->Q[QU->front;: 5判定队列是否为空 qempty(QU) 判定队列QU是否为空的函数如下:

数据结构习题与解析(C语言篇 int empty (qu qU。U“。U if (QU->tront==o)retum (1), /,为空,则证,始*/ etse return(O); *不为空,则返回tg黄 2.2基本题 2.2.1单项选择题 .一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址 是① A.110 B.108 C.100 D.120 答:①B [第5个元素的地址=100+2*(5-1)=108] 2.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 A, edcba B dech C. dceab D. abcde 答:①C 栈的特点是先进后出,所以在C中eab是不可能产生的。] 3.若已知一个栈的入栈序列是1,2,3,,n,其输出序列为p1p2p3……,pn,若p1= n则p为①。 A. i B n=i Cn-i+1 D.不确定 答:①C [当p1=n,即n是最先出栈的根据栈的原理n必定是最后入栈的,那么输入顺序必定 是1,2,3,n,则出栈的序列是n,,3,2,1,所以答案是C。] 4.栈结构通常采用的两种存储结构是① A.顺序存储结构和链表存储结构 B.散列方式和索引方式 C.链表存储结构和数组 D.线性存储结构和非线性存储结构 答:①A 5判定一个栈ST最多元素为m0)为空的条件是①。 A. ST->top<>o B. ST->top=0 C. ST->top<>mo 谷:①B 6.判定一个栈ST最多元素为m0)为栈满的条件是①

序表 A. ST->top! =0 B. ST->top==0 C. ST->top! =m0 D. ST p==m0 答:①D 7.栈的特点是①,队列的持点是②。 A.先进先出 B.先进后出 答:①B② 8一个队列的入列序列是1,2,3,4则队列的输出序列是①。 A.43,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1 答 9.判定一个队列QU(最多元素为m0)为空的条件是① A. QU->rear-QU->front==m0 B. QU->rear-QU-->front-I==m0 C. QU->front ===QU->rear D. QI 答:CC 10.判定一个队列QU(最多元素为m0)为满队列的条件是①。 A. QU->rear-QU->front==mO B. QU->rear-QU->front-1==m0 C, QU->front==QU->rear D. QU->front==QU->rear+1 答:①A 11.判定一个循环队列QU(最多元素为m0)为空的条件是①。 A. QU->front==QU->rear B. QU->front! =QU C. QU->front=(QU->rear+1)%m0 D.QU->front! =(QU->rear+1)% m0 答:①A 12判定一个循环队列QU(最多元素为m0)为满队列的条件是① A. QU->front ==QU->rear B. QU->front!=QU->rear C. QU->front==(QU->rear+1)%m0 D. QU->front! =(QU->rear-+1)%mO 答:①C 13.循环队列用数组AC0,m-1]存放其元素值,已知其头尾指针分别是 front和rear 则当前队列中的元素个数是①。 A(rear-front +m)% B read -front+I C. read-front-1