资源描述:
《应用题复习(含解)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、一、应用题1.已知线性表的存储结构为顺序表,阅读下列算法,并回答问题:(1)设线性表L=(51,-9,-6,39,0,-11,34,70,-16),写出执行算法f11(&L)后的L状态;(2)简述算法f11的功能。voidf11(SeqListL){inti,j;for(i=j=0;ilen;i++)if(L->elem[i]>=0){if(i!=j)L->elem[j]=L->elem[i];j++;}L->len=j;}【答案】(1)L=(51,39,0,34,70)(2)删除顺序表中小于0的数。2
2、.假设以带头结点的单链表表示线性表,阅读下列算法f22,并回答问题:(1)设线性表为(a1,a2,a3,a4,a5,a6,a7),写出执行算法f22后的线性表;(2)简述算法f22的功能。voidfun(LNodeL){//L为带头结点单链表的头指针P=L;while(p&&p->next){q=p->next;p->next=q->next;p=q->next;free(q);}}【答案】(1)(a2,a4,a6)(2)删除单链表中数据结点序号为奇数的那些结点。3.假设以数组seqn[m]存放循环队列的元素,
3、设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。(1)写出队满的条件表达式;(2)写出队空的条件表达式;(3)设m=50,rear=19,quelen=25,求队头元素的位置;(4)写出一般情况下队头元素位置的表达式。【答案】(1)quelen==m(2)quelen==0(3)45(4)front=(rear-quelen+1+m)%m4.假设以数组seqn[m]存放循环队列的元素,设变量front和rear分别指示循环队列中队头元素的位置和队尾元素的位置。(1)写出队满的条件表达式
4、;(2)写出队空的条件表达式;(3)设m=40,rear=13,front=19,求队列的元素的个数quelen;(4)写出一般情况下元素的个数的表达式。【答案】(1)(rear+1)%m==front(2)rear==front(3)34(4)quelen=(rear-frontm)%m5.假设有一个如下图的8×8矩阵,矩阵元素都是整型量(次对角线以上的元素都是0)。若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中,请回答下列问题:(1)B数组的体积至少是多少?(2)若a18存储在B[0]中
5、,a56存储在B[k]中,则k值为多少?(1)(2)【答案】(1)36(2)136.阅读下列算法,并回答问题:(1)Q、Q1和Q2都是队列结构,设队列Q=(1,0,-5,2,-4,-6,9),其中1为队头元素,写出执行f33(&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态;(2)简述算法f33的功能。(注:lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作)voidf31(QueueQ,QueueQ1,QueueQ2){inte;lnitQue
6、ue(Q1);lnitQueue(Q2);while(!QueueEmpty(Q)){e=DeQueue(Q);if(e>=0)EnQueue(Q1,e);elseEnQueue(Q2,e)}}【答案】(1)Q=()Q1=(1,0,2,9)q2=(-5,-4,-6)(2)将Q队列中的数据全部出队;不小于0的进Q1,否则进Q2。ABCGDEF7.已知二叉树如右图所示。(1)画出该二叉树的二叉链表;(2)分别写出该二叉树的先根、中根和后根遍历序列。【答案】(1)二叉链表:D∧∧ACB∧E∧G∧∧F∧∧(2)先根遍历
7、序列:ABDCEGF中根遍历序列:DBAEGCF后根遍历序列:DBGEFCA8、假设一棵二叉树的先根遍历序列为ABCDEFGH,中根遍历序列为CDBEGFHA。(1)画出该二叉树;(2)写出后根遍历序列。DBEHGFAC【答案】(1)二叉树(2)后根遍历序列:DCGHFEBA9、假设一棵二叉树的中根遍历序列为DGBEACHFI,后根遍历序列为GDEBHIFCA(1)画出该二叉树;(2)写出先根遍历序列。【答案】(1)二叉树:(2)先根遍历序列:ABDGECFHIABCIDHFGE10.假设一棵二叉树的层次遍历序
8、列为ABCDEFGHI,中根遍历序列为DHBEAFCIG。(1)画出该二叉树;(2)写出先根和后根遍历序列。【答案】(1)二叉树:ABCIDFGHE(2)先根遍历序列:ABDHECFGI后根遍历序列:HDEBFIGCA000000111111TGMSHDA25116145323517107186011.设某通讯系统仅用七个英文字符{A,D,G,H,M,S,T},每个字符的使用频率分别为