算法笔试或面试题.docx
- 文档编号:16087812
- 上传时间:2023-07-10
- 格式:DOCX
- 页数:42
- 大小:24.22KB
算法笔试或面试题.docx
《算法笔试或面试题.docx》由会员分享,可在线阅读,更多相关《算法笔试或面试题.docx(42页珍藏版)》请在冰点文库上搜索。
算法笔试或面试题
------------------------------------------------------------------------------
直接插入排序
voidinsertsort(intR[])
//按递增序对R[1]~R[n]进行直接插入排序
{inti,j;
for(i=2;i<=n;i++)
{R[0]=R[i];//设定R[0]为监视哨
j=i-1;
while(R[0] {R[j+1]=R[j]; j--; } R[j+1]=R[0];//插入第i个记录 } } ------------------------------------------------------------------------------ 试题关键字快速排序 试题内容 voidqksort(intR[],intl,intr)//按递增序对R[l]~R[r]进行快速排序 {inti=l,j=r; R[0]=R[i];//R[0]作临时单元 while(__i { while(i if(i while(i if(i }; R[i]=___R[0]__; i++;j--; if(j>l)qksort(R,l,j); if(i } ------------------------------------------------------------------------------ 试题关键字直接选择排序 试题内容 voidselectsort(intR[]) //按递增序对R[1]~R[n]进行直接选择排序 {inti,j,k,temp; for(i=1;i<=n-1;i++) {k=i; for(j=i+1;j<=n;j++) if(R[j] if(K<>i) {temp=R[i];R[i]=R[k];R[k]=temp;} } } ------------------------------------------------------------------------------ 试题关键字二分插入排序(对半) 试题内容 voidinsertsort(intR[]) //按递增序对R[1]~R[n]进行二分插入排序 {inti,j,left,right,mid; for(i=2;i<=n;i++) {R[0]=R[i];//设定R[0]为监视哨 left=1;right=i-1; while(left<=right) {mid=(left+right)div2; if(R[0] elseleft=mid+1; } for(j=i-1;j>=left;j--) R[j+1]=R[j];//元素后移 R[left]=temp; } } ------------------------------------------------------------------------------ 知识点线性表/单链表 试题内容 在带头结点的head单链表的结点a之后插入新元素x typedefstructnode {elemtypedata; structnode*next; }node; voidlkinsert(node*head,elemtypex) {node*s,*p; s=─────────────────────; s->data=_____; p=head->next; while(p! =NULL)&&(p->data! =a) ___________________; if(p==NULL) printf(“不存在结点a”); else{__________________________; __________________________; } } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号3 题型算法填空题 难度级别4 知识点树 分值13分 所需时间15分钟 试题关键字中序遍历的非递归算法 试题内容 设二叉树用二叉链表表示,以t为根指针,二叉链表结点的类型为node;栈s的元素类型为指向node的指针类型,栈容量m足够大。 中序遍历的非递归算法如下: typedefstructnode {chardata; node*lc,*rc; }node; voidinorder(node*t) {node*s[m],*p=t; inttop=-1;//置栈空 do {while(p! =NULL) {s[++top]=; ; } if(top! =-1) {p=s[top--]; ; ; } }while(()||(p! =NULL)); 答案内容 评分细则本题13分,全对得满分,否则按空计分 ----------------------------------------------------------------------- 试题序号5 题型算法填空题 难度级别4 知识点树 分值13分 所需时间15分钟 试题关键字先序遍历的非递归算法 试题内容 设二叉树用二叉链表表示,以t为根指针,二叉链表结点的类型为node;栈s的元素类型为指向node的指针类型,栈容量M足够大。 先序遍历的非递归算法如下: typedefstructnode {chardata; node*lc,*rc; }node; voidpreorder(node*t) {node*s[M],*p=______; inttop=-1;//置栈空; do {while(p! =NULL) {; s[++top]=; ; } if(top! =-1) {p=s[top--]; ; } }while((top! =-1)||(p! =NULL)); } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号8 题型算法填空题 难度级别4 知识点树 分值13分 所需时间15分钟 试题关键字层次遍历二叉树的算法 试题内容 设二叉树用二叉链表表示,以t为根指针,二叉链表结点的类型为node;队列s的元素类型为指向node的指针类型,队列容量m足够大。 层次遍历二叉树的算法如下: typedefstructnode {chardata; node*lc,*rc; }node; voidlevelorder(node*t) {node*s[m],*p=; intf=r=1;//设置队列头、尾指针 s[1]=———————; while(f<=r) {p=s[f++]; ; } if(p->lc! =NULL) {r++; }; if(p->rc! =NULL) { ; s[r]=p->rc; } } } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号9 题型算法填空题 难度级别4 知识点线性表 分值13分 所需时间15分钟 试题关键字顺序表 试题内容 voidmerge(intR[],intA[],ints,intm,intt) //对两个升序顺序表R[s]~R[m]和R[m+1]~R[t]合并,结果存入升序顺序表A中 {inti,j,k; i=s;j=m+1;k=s; while((i<=m)&&(j<=)) if(R[i]<=R[j]) {A[k]=R[i];i++;;} else {A[k]=R[j];;k++;} while(i<=)//复制第一个区间中剩下元素 {A[k]=R[i];i++;k++;} while(j<=t)//复制第二个区间中剩下元素 {;j++;k++;} 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号10 题型算法填空题 难度级别4 知识点查找 分值13分 所需时间15分钟 试题关键字二分查找 试题内容 对有序表R[0]至R[n-1]进行二分查找,成功时返回记录在表中的位置,失败时返回0 Structsqlist {keytypekey; }; intbinsrch(sqlistR[],keytypek) //在表R中查找关键字k {intlow,high,mid; low=0;high=n-1; while() {; if()returnmid; elseif(k──────R[mid].key) high=mid-1; elselow=mid+1; } return; } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号11 题型算法填空题 难度级别4 知识点串 分值13分 所需时间15分钟 试题关键字链串 试题内容 下列算法的功能是比较两个链串的大小,请在空白处填入适当的内容。 intcomstr(LinkStrings1,LinkStrings2) {//s1和s2为两个链串的头指针 while(s1&&s2){ if(s1->date if(s1->date>s2->date)return1; ①; ②; } if(③)return-1; if(④)return1; ⑤; } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号12 题型算法填空题 难度级别4 知识点栈和队列 分值13分 所需时间15分钟 试题关键字队列 试题内容 假设两个队列共享一个循环向量空间,其类型Queue2定义如下: typedefstruct {DateTypedata[MaxSize]; intfront[2],rear[2]; }Queue2; 对于i=0或1,front[i]和rear[i]分别为第i个队列的头指针和尾指针。 请对以下算法填空,实现第i个队列的入队操作。 intEnQueue(Queue2*Q,inti,DateTypex) {//若第i个队列不满,则元素x入队列,并返回1;否则返回0 if(i<0||i>1)return0; if(Q->rear[i]==Q->front[①]return0;Q->data[②]=x; Q->rear[i]=[③]; Return1; } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号13 题型算法填空题 难度级别4 知识点查找 分值13分 所需时间15分钟 试题关键字链地址法 试题内容 设散列函数H(k)=kmodp,解决冲突的方法为链地址法。 要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点,成功时返回指向关键字的指针,不成功时返回标志0。 typedefstructnode{intkey;structnode*next;}lklist; voidcreatelkhash(lklist*hashtable[]) { inti,k;lklist*s; for(i=0;i for(i=0;;i++) { s=(lklist*)malloc(sizeof(lklist)); ; k=a[i]%p;s->next=hashtable[k];_______________________; } } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号14 题型算法填空题 难度级别4 知识点树 分值13分 所需时间15分钟 试题关键字二叉排序树 试题内容 在链式存储结构上建立一棵二叉排序树。 要求在下列算法划线处填上正确的语句。 #definen10 typedefstructnode {intkey; structnode*lchild,*rchild;}bitree; voidbstinsert(bitree*bt,intkey) { if(bt==0) {; bt->key=key; ; } elseif() bstinsert(bt->lchild,key); else; } voidcreatebsttree(bitree*&bt) { inti; for(i=1;;i++)bstinsert(bt,random(100)); } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号15 题型算法填空题 难度级别4 知识点线性表 分值13分 所需时间15分钟 试题关键字单链表 试题内容 设计两个有序单链表的合并排序算法。 要求在下列算法划线处填上正确的语句。 voidmergelklist(lklist*ha,lklist*hb,lklist*&hc) { lklist*s=hc=0; while() if(ha->data {if(s==0)hc=s=ha; else{;s=ha;};;} else{if(s==0)hc=s=hb; else{s->next=hb;;};hb=hb->next;} if(ha==0)s->next=hb; else; } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号16 题型算法填空题 难度级别4 知识点排序 分值13分 所需时间15分钟 试题关键字直接插入排序 试题内容 在链式存储结构上实现直接插入排序算法。 要求在下列算法划线处填上正确的语句。 voidstraightinsertsort(lklist*&head) { lklist*s,*p,*q;intt; if(head==0||head->next==0)return; elsefor(q=head,p=head->next;p! =0;) { for(s=head;;s=s->next) if(s->data>p->data)break; if(s==q->next); else{q->next=p->next; ; s->next=p; t=p->data; ; s->data=t;} } } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号17 题型算法填空题 难度级别4 知识点排序 分值13分 所需时间15分钟 试题关键字快速排序 试题内容 下面程序段的功能是实现一趟快速排序,请在下划线处填上正确的语句。 structrecord{intkey;datatypeothers;}; voidquickpass(structrecordr[],ints,intt,int&i) { intj=t;structrecordx=r[s];; while() { while(i if(i while(____________________)i=i+1; if(i } _________________; } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号18 题型算法填空题 难度级别4 知识点排序 分值13分 所需时间15分钟 试题关键字简单选择排序 试题内容 设计在链式结构上实现简单选择排序算法。 voidsimpleselectsorlklist(lklist*&head) { lklist*p,*q,*s;intmin,t; if(head==0||head->next==0)return; for(q=head;q! =0;q=q->next) { min=q->data;s=q; for(;p! =0;) if(min>p->data) { ; s=p; } if(s! =q){t=s->data;;q->data=t;} } } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号19 题型算法填空题 难度级别4 知识点串 分值13分 所需时间15分钟 试题关键字子串 试题内容 在顺序存储结构上实现求子串算法。 要求在下列算法划线处填上正确的语句。 voidsubstring(chars[],longstart,longcount,chart[]) { longi,j,length=strlen(s); if() printf("Thecopypositioniswrong"); elseif(start+count-1>length) printf("Toocharacterstobecopied"); else{for(,j=0;;i++,)t[j]=s[i];;} } 答案内容 评分细则本题13分,全对得满分,否则按空计分 ------------------------------------------------------------------------------ 试题序号20 题型算法填空题 难度级别4 知识点图 分值13分 所需时间15分钟 试题关键字无向图 试题内容 下列程序段的功能是将无向图的邻接矩阵转为对应邻接表,请在下划线处填上正确的语句。 typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix; typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode; typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode; voidadjmatrixtoadjlist(gadjmatrixg1[],glinkheadnodeg2[]) { inti,j;glinklist
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 笔试 试题