《数据结构》题型和答案

《《数据结构》题型和答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一.单项选择题1.若str1存储为字符序列SCUT$;执行下列语句后str2存储的字符序列是_____。PUSH(STACK,'$');i=0;while(*(str1+i)!='$'){PUSH(STACK,*(str1+i));i++;}i=0;*(str2+i)=POP(STACK);while(*(str2+i)!='$'){i++;*(str2+i)=POP(STACK);*(str2+i)=POP(STACK);}(A)SCUT;(B)TUCS$;(C)TC$;(D)TC.2.intfun(structnode**f,structnode**r)实现的功能是____

2、_。structnode{intdata;structnode*link;};intfun(structnode**f,structnode**r){structnode*q;intitem;if(*f==NULL)printf(“empty”);else{if(*f==*r){item=(*f)->data;free(*f);*f=NULL;*r=NULL;}else{q=*f;item=q->data;*f=(*f)->link;(*r)->link=*f;free(q);}returnitem;}returnNULL;}(A)普通队列中插入结点；(B)普通队列中删除结点；

3、(C)环形队列中删除结点；(D)环形队列中插入结点.3.设单向链表中结点的结构为structnode{intdata;intlink;};structnode*p,*s,*q.已知指针p->link=s;s->link=q;若在*p与*q之间删除结点*s，则应执行操作_____。(A)q->link=q;(B)q->link=p;(C)p->link=q;(D)p->link=p.4.由二叉树的根开始，令a=3,8,7,9,1,2,4，依次调用函数*create，执行下列语句后建立的二叉树是Fig.1中的_____。(A)(B)structtree*create(structt

4、ree*root,inta){if(root==NULL){root=(structtree*)malloc(sizeof(structtree));root->data=a;root->left=NULL;root->right=NULL;return(root);}else{if(adata)(C)(D)root->left=create(root->left,a);elseroot->right=create(root->right,a);《数据结构》试卷A第1页共5页return(root);}}其中:structtree{intdata;structtr

5、ee*left;structtree*right;};Fig.1二.填空题1.ThePOSTfixexpression:ABC^D-+EAC/-*，writedownthecorrespondingINfixandPREfixexpressions:_______________________________________________________________________________2.Considerthefollowingvariable-lengthcodesforthe36-charactertextstring:FCFCECACBDEDFEABF

6、BAFFCDCBEDFFFCCDEEFUsingtheHuffmanencoding,fillintheTable1.Table1SymbolsABCDEFFixedLengthCodesOccurFrequencyHuffmanCodes3.Pleaseshowthedifferenttraversaloutputonthefollowingtree:PRE-orderDepth-FirstTraversal(DFT)____________________IN-orderDepth-FirstTraversal(DFT)____________________POST-or

7、derDepth-FirstTraversal(DFT)_____________________BreadthFirstSearchTraversal(BFST)______________________Fig.2三.算法分析题1.Implementationofbinarytreeanditsbreadthfirstanddepthfirsttraversaloperation.以Fig.3tree为例，分别详细分析：(1.1)breadth(tree*rt)执行过程中queue的变化