{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 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； } } 11 第三节 栈和队列 一、选择题 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．顺序队列的入队操作应为( sq.rear初值为-1 )。 *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．循环队列的入队操作应为(sq.rear初值为-1 )。 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； 9．顺序队列的出队操作为(sq. front初值为-1 )。 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．循环队列的出队操作为(sq. front初值为-1 )。 *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； 12 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；__。 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[n]来表示一个栈，令A[0]为栈底。用整型变量t来指示当前栈顶的位置，A[t]为栈顶元素。往栈中压入一个新元素时，变量t的值__加1___，从栈中弹出一个元素时，变量t的值___减1___。设空栈时，输入序列a，b，c经过push，pop，push，push，pop操作后，从栈中弹出的元素是___c__。 四、应用题 2．设有字符串为3*-y-a/y^2，试利用栈写出将其转换为3y-*ay2^/-的操作过程。假定用X代表扫描该字符串过程中顺序取一个字符入栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS。 答：XSXXXSSSXXSXXSXXSSSS 3．设有一个输入序列a，b，c，d，元素经过一个栈到达输出序列，而且元素一旦离开输入序列就不能再回到输入序列，试问经过这个栈后可以得到多少种输出序列? 答：可以得到14种输出序列：abcd,abdc,acbd,acdb,adcb,bacd,bcad,bcda,bdca,cbad,cbda,cdba,dcba,badc. 4．按照运算符优先法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程：9-2*4+(8+1)/3。 答： 序号 运算符栈 操作数栈 输入字符 1 # 9 2 # 9 - 3 #- 9 2 4 #- 92 * 5 #-* 92 4 13 6 #-* 924 + 7 #- 98 8 # 1 9 #+ 1 ( 10 #+( 1 8 11 #+( 18 + 12 #+(+ 18 1 13 #+(+ 181 ) 14 #+ 19 / 15 #+/ 19 3 16 #+/ 193 # 17 #+ 13 18 # 4 5．链栈中为何不设置头结点? 答：因为链栈只在链表头插入和删除结点，不可能在链表中间插入或删除结点，算法实现很简单，所以一般不设置头结点。 第四节 数组 一、选择题 1．数组通常具有的两种基本操作是( )。 A．建立和删除 B．索引和修改 *C．查找和修改 D．查找和索引 2．二维数组A[11，6]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[0，0]的存储地址是1000，则A[8，4]的存储地址是( )。 *A．1208 B．1212 C．1368 D．1364 3．对矩阵压缩存储是为了( )。 A．方便运算 *B．节省空间 C．方便存储 D．提高运算速度 4．稀疏矩阵的压缩存储方法通常有两种，即( )。 A．二元数组和三元数组 B．三元组和散列 *C．三元组和十字链表 D．散列和十字链表 二、判断题 √ 1．数组是同类型值的集合。 √2．数组是一组连续的内存单元。 ╳3．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。 ╳4．插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。 √ 5．使用三元组表示稀疏矩阵的元素，有时并不能节省存储空间。 三、填空题 1．二维数组A[10， 20]采用列序为主序方式存储，每个元素占一个存储单元，并且A[1，1]的存储地址是200，则A[6，12]的地址是___315___。 2．有一个10阶对称矩阵A采用压缩存储方式(以行序为主序方式)存储其下三角元素，且第一个元素A[0，0]的存储地址为1，则A[4，5]的地址是__14__，A[8，3]的地址是___31_。 3．下三角矩阵A[N,N]的下三角元素已压缩到一维数组S[N(N+1)／2]中，若按行序为主序存储，则A[i，j]对应的S中的存储位置是__I(I-1)/2+j(i≥j),n(n+1)/2+1(I 1．假设有二维数组A[6,8]，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始地址(基地址)为1000，计算：(1)数组A的容量。(2)按行优先方式存储时，元素A[1，4]的地址。(3)按列优先方式存储时，元素A[4,7]的地址。 答：(1)数组A的容量:6*8*6=288。(2)按行优先方式存储时，元素A[1，4]的地址=1000+3*6=1018。(3)按列优先方式存储时，元素A[4,7]的地址=1000+(6*6+3)*6=1234。 2．设有三对角矩阵A[n，n]，将其三条对角线上的元素逐行存放于数组B[3n-3]中，使得B[k]=A[i,j]，求： (1)用i，j表示k的下标变换公式。 (2)用k表示i，j的下标变换公式。 答：(1) k=2i+j-3 (2) I=(k+1)/3+1，j=k-2i+3。 3．画出图5-2所示的稀疏矩阵A的三元组表和十字链表。 14 答： row 1 2 2 3 5 5 col 4 1 3 5 1 3 e 2 5 6 8 4 9 4．用三元组表表示图5-3所示的稀疏矩阵的转置矩阵。 答： row col e 1 2 2 2 1 1 3 3 4 4 4 5 5 2 3 五、算法设计题 1．设计将数组A[n]中的所有奇数移到所有偶数之前的算法。要求不另外增加存储空间且时间复杂度为O(n)。 算法采用两个变量i和j分别表示数组的开头和末尾元素，同时向中间搜索： void change(int a[n]) { I=0; j=n-1; while (I {while (a[I]%2!=0&&I {c=a[I];a[I]=a[j];a[j]=c; I++;j--;} } } *2．当稀疏矩阵A和B均以三元组作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组C中。 略。 第五节 树 (树根结点的高度为1) 一、选择题 1．以下说法错误的是( )。 *A．树形结构的特点是一个结点可以有多个直接前驱 B．线性结构中的一个结点至多只有一个直接后继 C．二叉树与树是两种不同的数据结构 D．树(及一切树形结构)是一种“分支层次’结构 2．以下说法错误的是( )。 A．二叉树可以是空集 *B．二叉树的任一结点都有两棵子树 C．二叉树与树具有相同的树形结构 D、二叉树中任一结点的两棵子树有次序之分 3．以下说法错误的是( )。 A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B．在三叉链表上，二叉树的求双亲操作很容易实现 C．在二叉链表上，求根以及求左、右孩子等操作很容易实现 *D．在二叉链表上，求双亲操作的时间性能很好 15 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库软件基础习题 答案 - 图文(3)在线全文阅读。
相关推荐：