1、线性表模拟试卷 3 及答案与解析一、单项选择题1 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。【2011 年全国硕士研究生入学计算机学科专业基础综合试题】简称【201 1 年全国试题 1(2 分)】x=2； while(x*x；（A）O(log 2n)（B） O(n)（C） O(nlog2n)（D）O(n 2)2 求整数 n(n0)阶乘的算法如下，其时间复杂度是( )。【2012 年全国试题 1(2 分)】int fact(int n)if(nfloat calul(float height)float s，t；s=height；if(height10e 一 6) re
2、turn 0； elset=calu1(09*height) ；return s=2*s+t：float calu2(float height)float s=height，temp；temp=height；while(height=1Oe 一 6)S=s+2*height；height=height*09：s=s 一 2*temp：return S；main()float f，n；printf(“请输入一个数：”)； scanf(“f”，&n)；f=calul(n)；f=fn：prinff(“递归算法结果 =fn”，f)；f=calu2(n)；prinff(“非递归算法结果= fn”，f)；
3、float S1(float h) 非递归算法，用好 whilefloat s=0；while(h=10e 一 6)s=s+19*h；h=0 9*h：return S：float S2(float h)递归算法if(h10e 一 6)return 0；else return 19*h+S2(09*h)；【知识模块】 线性表27 【正确答案】 本题实际上是通过修改双向链表的指针实现直接插人排序void insertion(LinkList*list)LinkNode*P，*q；int min； min 用来记录链表中的最小值P=list；if(P=null)retum； 空表的情况q=list
4、一 next；if(q=null)return；只有一个结点的情况min=list 一 data：if(q 一datamin) 结点个数多于一个时，特殊处理第一个结点min=q 一 data；P 一next=q 一next ； 插入排序修改指针q 一next 一prior=P ：q 一next=P ；list=q；第一个结点的处理P=list；q=P 一next：min=P 一data；while(q!=null) 非首元素的链结点的处理if(q 一datamin)rain=q 一 data；P 一next=q 一next ：q 一next 一prior=P ：q 一next=P ；q=p 一
5、next；【知识模块】 线性表28 【正确答案】 本题考查的是双向链表的插入和移动。struct Line 双向链表的结点int nun；char content255；struct Line*next；struct Line*prior；struct Bookint size；structLine *head； 指向第一行structLine *rear； 指向最后一行；(1)void insert(Book*b，Line*1，int Bum)int i；Line *rear，*temp；if(b 一sizeBum)总行数小于 Bum 时，认为是在最后进行插入rear=b 一rear ；b
6、一rear=1；1 一prior=rear；if(b 一size!=0)文章不为空时rear 一next=1；else 文章为空时b 一head=1；b 一size=b 一size+1；else 根据所指定的行进行插入temp=b 一headfor(i=0；i Bum 一 1；i+) 找到指定行temp=temp 一next；双向链表结点的插入1 一prior=temp 一prior；1 一next=temp；1 一num=num ；if(num!=1)temp 一prior 一next=1；不是在第一行进行插人elseb 一head=1；temp 一prior=1；b 一size=b 一si
7、ze+1；for(i=num； ib 一size；i+)插入行之后的各行进行行号更新temp 一num+；temp=temp 一next；(2)void change(Book*b，int num)交换第 num 和 num+1 行如果 num=size ，则交换最后两行P 为指定的结点， pp 为 P 的前驱结点pnext 为 P 的后续结点，pnn 为 pnext 的后续结点int i；Line*P，*PP，*pnext，*pnn；if(num=b 一size 一 1&b 一size1) 指定行大于总行数，则认为交换最后两行位置pnext=b 一rear；P=pnext 一 prior；P
8、P=P 一prior ；pnn=pnext 一next；if(P!=b 一head)pp 一next=pnext；不是对文章的第一行进行操作elseb 一head=pnext； 对文章第一行的操作双向链表结点的交换操作pnext 一prior=PP ；pnext 一next=P ；P 一prior=pnext；P 一next=pnn ；b 一rear=P；1=P 一num；P 一num=pnext 一num ；pnext 一num=i ；if(b 一size1&num 0&numb 一size 一 1)P=b 一head；for(i=1；i num；i+) 找到指定行P=P 一next；pne
9、xt=P 一 next：PP=P 一prior ；pnn=pnext 一next；if(P!=b 一ahead)PP 一next=pnext ； 不是对文章的第一行进行操作elseb 一head=pnext；对文章第一行的操作双向链表结点的交换操作pnext 一prior=PP ；pnext 一next=P ；P 一prior=pnext；P 一next=Pnn；pnn 一prior=P ；i：P 一num ；P 一num=pnext 一hum ；pnext 一hum=i ；【知识模块】 线性表29 【正确答案】 每次选择两个队列中较小的值放到队列 C 中。struct nodeint val
10、ues；struct node*next；Node 木 merge(node*A，node*B)int temp；node *pa，*pb，*pc，*next； pa=A；pb=B；if(pa 一valuepb 一value)pc=pa；pa=pa 一next；pc 一next=null；elsepc=pb；pb=Pb 一next；pc 一next=null：next=pc；while(pa!=null&b!=null)if(pa 一valuepb 一value)next 一next=pa；pa=pa 一next：next=next 一next；next 一next=null；elsenext 一next=pb；pb=pb 一next；next=next 一next；next 一next=null；if(pa=null&pb!=null)next 一next=pb；if(pb=null&pa!=null)next 一next=pa：retum*pc；【知识模块】 线性表
