发布时间 : 星期日 文章计算机软件技术基础所有题目答案-自学更新完毕开始阅读
r=head；
printf(”输入系数和指数：”)； scanf(&n，&m)； while(n!=0) ／／若n=0则退出循环
{s=(Plink)malloc(sizeof(struct PNode))；
s->coef=n；s->exp=m；r->next=s；r=s；／／把s链接到r的后面 printf(”输入系数和指数:”)； scanf(&n，&m)； } r->next=NULL；head=head—>next； ／／删除头结点 return head； }
19．根据上题的多项式链表结构，编写一个过程实现两个多项式相加的运算。
答：分析：对所有指数相同的项，将其对应系数相加，若和不为0，则构造新“和多项式”的结点；将所有指数不同的项复制到和多项式中。 Plink add(PLink pa，PLink pb) {／／多项式相加
p=pa；q=pb；pc=(PLink)malloc(sizeof(struct PNode))；r=pc； while(p!=NULL&&q!=NULL)
{if(p->exp==q->exp)／／两结点的指数相同时，将两系数相加生成新结点插入c中 {x=p->coef+q->coef；
if(x!=0){s=(PLink)malloc(sizeof(struct PNode))；s->coef=x； s->exp=p->exp； r->next=s； r=s； } p=p->next；q=q->next；}
else if(p->exp>q->exp)／／两结点的指数不同时，将较小系数的结点复制成新结点插入c中
{s=(PLink)malloc(sizeof(struct PNode))；s->coef=q->coef；s->exp=q->exp； r->next=s； r=s；q=q->next；}
else {s=(PLink)malloc(sizeof(struct PNode))；s->coef=p->coef；
s->exp=p->exp；r->next=s；r=s；p=p->next； }
}
while(p!=NULL) ／／复制A的余下部分
{s=(PLink)malloc(sizeof(struct PNode))；s->coef=p->coef；s->exp=p->exp； r->next=s：r=s；p=p->next；}
while(ql=NULL) ／／复制B的余下部分
{s=(PLink)malloc(sizeof(struct PNode))；s->coef=q->coef；s->exp=q->exp； r->next=s；r=s；q=q->next； }
r->next=NULL； ／／最后结点的next域置为空 s=pc；pc=pc->next； ／／删除c的头结点 free(s)； return pc; }
20．约瑟夫环问题：任给正整数n、k，按下述方法可得排列1，2，?，n的一个置换：将数字l，2，?，n环形排列，按顺时针方向从1开始计数；计满k时输出该位置上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10、k=3时，输出的置换是3，6，9，2，7，1，8，5，10。分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题。 答：void Js1(int A[n]，int N，iht K) {／／以数组为存储结构
for(i=0；i for(i=0；i while(s 13 A[j-1]=0;／／将计满k值的数字输出，并将其位置标为0表明已删除 } } void Js2(LinkedList last，int N，int K) {／／以不带头结点的、已知尾指针的单循环链表为存储结构 p=last； q=p->next； ／／此时q为头结点fp为q的前驱 while(N>0) {for(j=2；j<=K；j++) ／／循环K-1次 {p=q；q=p->next；} printf(”%d”，q->data)； N--； p->next=q->next; ／／删除q q=p—>next； } } 第三节 栈和队列 一、选择题 1．设有一顺序栈s，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是( )。 A．2 *B．3 C．5 D．6 2．若一个栈的输入序列是a、b、c，则通过入栈、出栈操作可能得到a、b、c的不同排列个数为( )。 A．4 *B．5 C．6 D．7 3．设有一顺序栈已经含有3个元素，如图3-1所示，元素a4正等待入栈。以下序列中不可能出现的出栈序列是( )。 *A．a3，a1，a4，a2 B．a3，a2，a4，a1 C．a3，a4，a2，a1 D．a4，a3，a2，a1 4．和顺序栈相比，链栈有一个比较明显的优势是( )。 *A．通常不会出现栈满的情况 B．通常不会出现栈空的情况 C．插入操作更容易实现 D．删除操作更容易实现 5．若一个栈的输入序列是1，2，3，4，?，n，输出序列的第一个元素是n，则第i个输出元素是( )。 A．不确定 B．n-i *C．n-i+1 D．n-i-1 6．以下说法正确的是( )。 *A．因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况 B．因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况 C．对于链栈而言，在栈满状态下，如果再进行入栈操作，则会发生“上溢” D．对于顺序栈而言，在栈满状态下，如果再进行入栈操作，则会发生“下溢” 7．顺序队列的入队操作应为( )。 *A．sq.rear=sq.rear+1；sq.data[sq.rear]=x; B．sq.data[sq.rear]=x； sq.rear=sq.rear+1； C．sq.rear=(sq.rear+1)％maxsize；sq.data[sq.rear+1]=x; D．sq.data[sq.rear]=x；sq.rear=x; sq.rear=(sq.rear+1)％maxslze； 8．循环队列的入队操作应为( )。 A．sq．rear=sq．rear+1；sq．data[sq．rear]=x B．sq．data[sq．rear]=x； sq．rear=sq．rear+l； *C．sq．rear=(sq．rear+1)％maxsize；sq．data[sq．rear]=x； D．sq．data[sq．rear]=x；sq．rear=(sq．rear+1)％maxsize； 14 9．顺序队列的出队操作为( )。 A．sq．front=(sq．front+1)％maxsize； *B．sq．front=sq．front+1； C．sq．rear=(sq．rear+1)％maxsize； D．sq．rear=sq．rear+1; 10．循环队列的出队操作为( )。 *A．sq．front=(sq．front+1)％maxsize； B．sq．front=sq．front+1； C．sq．rear=(sq．rear+1)％maxsize； D．sq．rear=sq．rear+l； 11．循环队列的队满条件为( )。 A．(sq．rear+1)％maxsize==(sq．front+1)％maxsize； B．(sq．rear+1)％maxsize==sq．front+1； *C．(sq．rear+1)％maxsize==sq．front； D．sq．rear==sq．front； 12．循环队列的队空条件为( )。 A．(sq．rear+1)％maxsize==(sq．front+1)％maxsize； B．(sq．rear+1)％maxsize==sq．front+1； C．(sq．rear+1)％maxsize==sq．front； *D．sq．rear==sq．front； 13．如果以链表作为栈的存储结构，则出栈操作时( )。 A．必须判别栈是否满 B．判别栈元素的类型 *C．必须判别栈是否空 D．对栈不做任何判别 14，向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为( )。 A．Top->next=s； B．s->next=Top->next；Top->next=s； *C．s->next=Top；Top=s； D．s->next=Top；Top=Top->next； 15．从栈顶指针为Top的链栈中删除一个结点，并将被删结点的值保存到x中，其操作步骤为( )。 *A．x=Top->data；Top=Top->next； B．Top=Top->next；x=Top->data； C．x=Top；Top=Top->next； D．x=Top->data； 16．在一个链队中，苕f、r分别为队头、队尾指针，则插入s所指结点的操作为( )。 A．f->next=s；f=s； *B．r->next=s；r=s； C．s->next=r；r=s； D．s->next=f；f=s； 17．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是( )。 A．e，d，c，b，a B．d，e，c，b，a *C．d，c，e，a，b D．a，b，c，d，e 18．一个队列的入队序列是1，2，3，4，则队列的可能的输出序列是( )。 A．4，3，2，1 *B．1，2，3，4 C．1，4，3，2 D．3，2，4，1 19．设计一个判别表达式中左，右括号是否配对出现的算法，采用( )数据结构最佳。 A．线性表的顺序存储结构 *B．栈 C．队列 D．线性表的链式存储结构 二、判断题 √1．在顺序栈栈满情况下，不能再入栈，否则会产生“上溢”。 ╳2．与顺序栈相比，链栈的一个优点是插入和删除操作更加方便。 ╳3．若一个栈的输入序列为1，2，3，?，n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=i+1(i=1，2，?，n)。 √4．在链队中，即使不设置尾指针也能进行入队操作。 √5．在对链队(带头指针)做出队操作时，不会改变front指针的值。 ╳6．循环队列中元素个数为rear-front。 ╳7．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2． √8．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。 ╳9．若以链表作为栈的存储结构，则入栈需要判断栈是否满． √10．若以链表作为栈的存储结构，则出栈需要判断栈是否空。 三、填空题 1．向一个栈顶指针为Top的链栈中插入一个s所指的结点时，其进行的操作是__ s->next=Top；Top =s；__。 2．从栈顶指针为Top的链栈中删除一个结点，并将结点保存在x中，进行的操作是_ x=Top->data；Top=Top->next；__。 15 3．在具有n个单元的循环队列中，队满时共有___n-1_个元素。 4．假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为__ b，c，e，d，a ___。 5．设有数组A[m]作为循环队列的存储空间，front为队头指针，rear为队尾指针，则元素x执行入队操作的语句是_rear=（rear +1）％（m+1）； A[rear]=x;__。 6．在一个链队中，如果f、r分别为队头、队尾指针，则插入s所指结点的操作是_r->next=s; r=s;___。 7．栈的逻辑特点是__后进先出____，队列的逻辑特点是_先进先出__，二者的共同特点是_操作受限__。 8．___栈___可以作为实现递归函数调用的一种数据结构。 9．在队列中，新插入的结点只能添加到__队尾__。 10．链队在一定范围内不会出现__队满___的情况。当lq．front==lq．rear时，队中无元素，此时___队空__。 11．设一个链栈的栈顶指针为ls，栈中结点的格式为data:next，栈空的条件是_ ls = NULL__；如果栈不为空，则出栈操作为p=ls; ___ ls = ls ->next __；free(p)。 12．对带有头结点的链队lq，判定队列中只有一个数据元素的条件是__lq->front->next= lq->rear___。 13．设有一个空栈，现在输入序列为1，2，3，4，5，经过push，push，pop，push，pop，push后，栈顶指针所指元素是__4__。 14．设用一维数组A[ln]来表示一个栈，令A[n]为栈底。用整型变量t来指示当前栈顶的位置，A[t]为栈顶元素。往栈中压入一个新元素时，变量t的值__加1___，从栈中弹出一个元素时，变量t的值___减1___。设空栈时，输入序列a，b，c经过push，pop，push，push，pop操作后，从栈中弹出的元素是___c__。 四、应用题 1．试证明：若借助栈由输入序列1，2，3，?，n得到输出序列p1，p2，?，pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在i 2．设有字符串为3*-y-a/y^2，试利用栈写出将其转换为3y-*ay2^/-的操作过程。假定用x代表扫描该字符串过程中顺序取一个字符入栈的操作，用s代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS。 答：XSXXXSSSXXSXXSXXSSSS 3．设有一个输入序列a，b，c，d，元素经过一个栈到达输出序列，而且元素一旦离开输入序列就不能再回到输入序列，试问经过这个栈后可以得到多少种输出序列? 答：可以得到13种输出序列： abcd,abdc,acbd,acdb,adcb,bacd,bcad,bcda,bdca,cbad,cbda,cdba,dcba. 4．按照运算符优先法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程：9-2*4+(8+1)/3。 答： 序号 运算符栈 操作数栈 输入字符 1 # 9 2 # 9 - 3 #- 9 2 4 #- 92 * 5 #-* 92 4 6 #-* 924 + 7 #- 98 8 # 1 16