首页 数据结构笔试题答案

数据结构笔试题答案

数据结构笔试题答案数据结构笔试题答案选择题C插入排序从后面插入的时候，只要把8和9交换一下就行了，遍历到前面都不再有任何操作。冒泡排序第一次循环把9沉到最后面，然后第二次循环发现没有任何交换操作，说明已经排好序了。AD已知前序和后序不能唯一确定BD填空题(1)!=null(2)p->next(3)r!=null(4)r->datadata(5)r->next(6)p->next题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。EACBDGFsort_b_tree(&((*tree)-...

数据结构笔试题答案选择题C插入排序从后面插入的时候，只要把8和9交换一下就行了，遍历到前面都不再有任何操作。冒泡排序第一次循环把9沉到最后面，然后第二次循环发现没有任何交换操作，说明已经排好序了。AD已知前序和后序不能唯一确定BD填空题(1)!=null(2)p->next(3)r!=null(4)r->datadata(5)r->next(6)p->next题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。EACBDGFsort_b_tree(&((*tree)->right),s)sort_b_tree(&((*tree)->left),s)简答题数组和链表的区别，请详细解释。从逻辑结构来看：数组必须事先定义固定的长度(元素个数)，不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。(数组中插入、删除数据项时，需要移动其它数据项，非常繁琐)链表必须根据next指针找到下一个元素从内存存储来看：(静态)数组从栈中分配空间,对于程序员方便快速,但是自由度小链表从堆中分配空间,自由度大但是申请管理比较麻烦从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反，如果需要经常插入和删除元素就需要用链表数据结构了。排序算法有哪些？#include#includestructstudent{intvalue;structstudent*lchild;structstudent*rchild;};voidarraytotree(int*a,intlen,structstudent**p){if(len){*p=(structstudent*)malloc(sizeof(structstudent));(*p)->value=a[len/2];arraytotree(a,len/2,&((*p)->lchild));arraytotree(a+len/2+1,len-len/2-1,&((*p)->rchild));}else{*p=NULL;}}voiddisplay_tree(structstudent*head){if(head->lchild)display_tree(head->lchild);printf("%d,",head->value);if(head->rchild)display_tree(head->rchild);}intmain(){inta[]={1,2,3,4,9,10,33,56,78,90};structstudent*tree;arraytotree(a,sizeof(a)/sizeof(a[0]),&tree);printf("Afterconvert:\n");display_tree(tree);printf("\n");return0;}在二叉查找树中查找某一个值所在的位置。intfind_btree(btree*bt,datatypex){if(bt){if(bt->key==x)returnTRUE;if(!find_btree(bt->lchild,x))if(!find_btree(bt->rchild,x))returnFALSE;}}二叉树，比父节点大的元素，都在右子树，比父节点小的元素都在左子树。也就是排序二叉树，写出插入一个节点或者删除一个节点。#include#include#include#include#defineTRUE1#defineFALSE0typedefintstatus;typedefintdatatype;typedefstructnode{datatypekey;structnode*lchild,*rchild;}btree;voidbst_insert(btree**bt,datatypekey)//二叉排序树的插入{if(NULL==*bt){btree*node=malloc(sizeof(btree));node->key=key;node->lchild=node->rchild=NULL;*bt=node;}elseif(key>(*bt)->key){bst_insert(&(*bt)->rchild,key);}else{bst_insert(&(*bt)->lchild,key);}}statusbst_delete(btree**bt,datatypekey)//二叉排序树的删除{btree*tmp=NULL;if(!*bt){returnFALSE;}else{if(key<(*bt)->key)//在左子树中找{bst_delete(&(*bt)->lchild,key);}elseif(key>(*bt)->key)//在右子树中找{bst_delete(&(*bt)->rchild,key);}else//找到了{tmp=*bt;if(!(*bt)->lchild)//左子树为空{*bt=(*bt)->rchild;}elseif(!(*bt)->rchild)//右子树为空{*bt=(*bt)->lchild;}free(tmp);returnTRUE;}}}voidpreorder_btree(btree*bt)//二叉树的先序遍历{if(bt!=NULL){printf("%d,",bt->key);preorder_btree(bt->lchild);preorder_btree(bt->rchild);}}voidinorder_btree(btree*bt)//二叉树的中序遍历{if(bt!=NULL){inorder_btree(bt->lchild);printf("%d,",bt->key);inorder_btree(bt->rchild);}}intmain(intargc,char*argv[]){btree*bt=NULL;intn;while(1){scanf("%d",&n);if(n==0)//输入0则结束{break;}else{bst_insert(&bt,n);}}preorder_btree(bt);putchar('\n');bst_delete(&bt,8);preorder_btree(bt);putchar('\n');return0;}4.实现单向链表:创建链表、插入链表、查询链表、删除特定序号链表节点、遍历剩余链表节点简单的链表操作，这里假设链表无头结点。可以自己完善有头结点的单向链表。头文件：/*list.h--headerfileforasimplelisttype*/#ifndef__LIST_H_#define__LIST_H_#include#include#include#include/*C99feature*/#ifdef__cplusplusextern"C"#endif/*__cplusplus*//*program-specificdeclarations*/typedefintdataType;/*generaltypedefinitions*/typedefdataTypeItem;typedefstructnode{Itemitem;structnode*next;}Node;typedefNode*List;/*functionprototypes*/voidListCreate(List*plist);boolListIsEmpty(constList*plist);boolListIsFull(constList*plist);unsignedintListItemCount(constList*plist);boolAddItem(Itemitem,List*plist);voidEmptyTheList(List*plist);voidTraverseTheList(List*plist);unsignedintListItemSearch(constList*plist,constItemitem);voiddeleteTheListNode(List*plist,unsignedintnum);#ifdef__cplusplus}#endif/*__cplusplus*/#endif/*__LIST_H_*/.c文件/*list.c--functionssupportinglistoperations*/#include#include#include"list.h"/*localfunctiondefinition*/staticvoidCopyToNode(constItemitem,Node*pnode);staticvoiddisplayTheNOde(constNode*pnode);staticboolItemIsEqu(constItemItem,constNode*pnode);/*initaemptylist*/voidListCreate(List*plist){*plist=NULL;}/*returnstrueiflistisempty*/boolListIsEmpty(constList*plist){if(*plist==NULL)returntrue;elsereturnfalse;}/*returnstrueiflistisfull*/boolListIsFull(constList*plist){Node*pt;boolfull;pt=(Node*)malloc(sizeof(Node));if(pt==NULL)full=true;elsefull=false;free(pt);returnfull;}/*returnsnumberofnodes*/unsignedintListItemCount(constList*plist){unsignedintcount=0;Node*pnode=*plist;while(pnode!=NULL){++count;pnode=pnode->next;}returncount;}/*searchiteminthelist*/unsignedintListItemSearch(constList*plist,constItemitem){intnum=0;Node*pnode=*plist;while(pnode!=NULL){num++;if(ItemIsEqu(item,pnode))returnnum;pnode=pnode->next;}return0;}/*createsnodetoholditemandaddsittotheendoflist*/boolAddItem(Itemitem,List*plist){Node*pnew=NULL;Node*scan=*plist;pnew=(Node*)malloc(sizeof(Node));if(pnew==NULL)returnfalse;CopyToNode(item,pnew);pnew->next=NULL;if(scan==NULL)/*emptylist,soplace*/*plist=pnew;/*pnewatheadoflist*/else{while(scan->next!=NULL)*/scan=scan->next;/*findendoflist*/scan->next=pnew;/*addpnewtoend}returntrue;}/*deletethenodebynum*/voiddeleteTheListNode(List*plist,unsignedintnum){Node*pnode=*plist;Node*psave=NULL;if(ListIsEmpty(plist))return;if(1==num){psave=*plist;*plist=psave->next;free(psave);return;}--num;while(pnode->next!=NULL&&num>1){--num;pnode=pnode->next;}if(pnode->next!=NULL&&1==num){psave=pnode->next;pnode->next=psave->next;free(psave);}}/*TraverseTheList*/voidTraverseTheList(List*plist){Node*pnode=*plist;while(pnode!=NULL){displayTheNOde(pnode);pnode=pnode->next;}putchar('\n');}/*freememoryallocatedbymalloc()*/voidEmptyTheList(List*plist){Node*psave=NULL;while(*plist!=NULL){psave=(*plist)->next;/*saveaddressofnextnode*/free(*plist);/*freecurrentnode*/*plist=psave;/*advancetonextnode*/}}/*localfunctiondefinition*//*copiesanitemintoanode*/staticvoidCopyToNode(constItemitem,Node*pnode){pnode->item=item;/*structurecopy*/}/*displayanodedata*/staticvoiddisplayTheNOde(constNode*pnode){printf("%d",pnode->item);}/*Todeterminethenode*/staticboolItemIsEqu(constItemItem,constNode*pnode){returnItem==pnode->item?true:false;}5.编程实现判断一个链表是否是递增的假设链表无头结点.若链表为空默认为递增。思路之前结点的数据与之后的数据依次比较typedefintdataType;/*generaltypedefinitions*/typedefdataTypeItem;typedefstructnode{Itemitem;structnode*next;}Node;typedefNode*List;boollistItemIsIncrease(List*plist){Node*preptr=*plist;Node*curptr=NULL;if(NULL==*plist)returntrue;curptr=preptr->next;while(curptr!=NULL){if(preptr->item>curptr->item)/*如果是严格递增，则判断用>=*/break;preptr=curptr;curptr=curptr->next;}return(curptr==NULL)?true:false;}6.编程实现删除链表中的重复节点假设链表无头结点，挨个遍历链表数据，与之后的结点依次比较，发现重复的就删除typedefintdataType;/*generaltypedefinitions*/typedefdataTypeItem;typedefstructnode{Itemitem;structnode*next;}Node;typedefNode*List;voiddelRepeatedNodeOnce(List*plist){Node*p=*plist,*q,*u,*y;while(p){q=p->next;u=p;while(q){if(q->item==p->item){u->next=q->next;y=q;q=q->next;free(y);}else{u=q;q=q->next;}}p=p->next;}}7.只遍历一次链表，实现链表的倒序假设链表无头节点，链表头插入，直到遍历到链表末尾typedefintdataType;/*generaltypedefinitions*/typedefdataTypeItem;typedefstructnode{Itemitem;structnode*next;}Node;typedefNode*List;voidListInverse(List*plist){Node*pnode=*plist;Node*pcur=NULL;Node*ptmp=NULL;if(NULL==pnode||NULL==pnode->next)return;pcur=pnode->next;pnode->next=NULL;while(pcur!=NULL){ptmp=pcur->next;pcur->next=*plist;*plist=pcur;pcur=ptmp;}}8.将两个有序链表A1,A2表合并为一个有序链表A3假设链表无头节点，简单递增序列，思路：链表插入排序typedefintdataType;/*generaltypedefinitions*/typedefdataTypeItem;typedefstructnode{Itemitem;structnode*next;}Node;typedefNode*List;voidListMerge(List*A1,List*A2,List*A3){Node*p=*A1;Node*q=*A2;Node*t=*A1;*A3=*A1;if(NULL==p){*A3=*A2;}if(NULL==q){*A3=*A1;}p=p->next;while(q!=NULL&&p!=NULL){if(p->itemitem){t->next=p;t=p;p=p->next;}else{t->next=q;t=q;q=q->next;}}if(q!=NULL){t->next=q;}else{t->next=p;}}已知链表节点structLNode{intiValue;LNode*next;};已创建一个有序的链表，从小到大排列。实现以下函数，将数据插入到链表中，并且有序。请实现以下函数：boolInsertLink(LinkList*p,inta){};思路：该题未说明有无头结点，且顺序未知，这里假设为递增序列，简单遍历比较插入。/*将data插入到递增有序的链表中，使该链表仍保持递增有序*/boolInsertLink(LinkList*p,inta){LNode*pre=NULL,*temp=NULL;temp=(LNode*)malloc(sizeof(LNode));if(NULL==temp){fprintf(stderr,"mallocfailed\n")returnfalse;}temp->iValue=a;temp->next=NULL;/*搜索链表，找到插入位置*/for(pre=p;pre->next!=NULL&&pre->next->iValuenext);/*插入新结点*/temp->next=pre->next;pre->next=temp;returntrue;}写一个链表，实现创建链表，添加链表节点，删除链表节点，查找链表节点，写一个main函数，创建一个链表，里面添加20个学生节点(节点含有姓名和学号)，再删除其中任意一个节点，输出任意指定节点，输出最后10名学生节点。头文件：/*list.h--headerfileforasimplelisttype*/#ifndef__LIST_H_

                    本文档为【数据结构笔试题答案】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

数据结构笔试题答案

你可能还喜欢