下载此文档

东南大学十套数据结构试题及答案.doc


文档分类:研究生考试 | 页数:约28页 举报非法文档有奖
1/28
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/28 下载此文档
文档列表 文档介绍
--------------------------校验:_____________-----------------------日期:_____________东南大学十套数据结构试题及答案数据结构试卷(一)三、计算题(每题6分,共24分)在如下数组A中链接存储了一个线性表,表头指针为A[0].next,试写出该线性表。A01234567data605078903440next3572041请画出下图的邻接矩阵和邻接表。已知一个图的顶点集V和边集E分别为:V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。画出向小根堆中加入数据4,2,5,8,3时,每加入一个数据后堆的变化。四、阅读算法(每题7分,共14分)LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L->next){q=L;L=L->next;p=L;S1:while(p->next)p=p->next;S2:p->next=q;q->next=NULL;}returnL;}请回答下列问题:(1)说明语句S1的功能;(2)说明语句组S2的功能;(3)设链表表示的线性表为(a1,a2,…,an),写出算法执行后的返回值所表示的线性表。voidABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<<BT->data<<'';}}该算法的功能是:五、算法填空(共8分)二叉搜索树的查找——递归算法:boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失败else{if(item==BST->data){item=BST->data;//查找成功return___________;}elseif(item<BST->data)returnFind(______________,item);elsereturnFind(_______________,item);}//if}六、编写算法(共8分)统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex)数据结构试卷(二)三、应用题(36分)设一组初始记录关键字序列为(45,80,48,40,22,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。设一棵树T中边的集合为{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。设有无向图G,要求给出用普里姆算法构造最小生成树所走过的边的集合。设有一组初始记录关键字为(45,80,48,40,22,78),要求构造一棵二叉排序树并给出构造过程。四、算法设计题(16分)设有一组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示。数据结构试卷(三),请在下划线处填上正确的语句。structrecord{intkey;intothers;};inthashsqsearch(structrecordhashtable[],intk){inti,j;j=i=k%p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);}if(_______________________)return(j);elsereturn(-1);}下列算法实现在二叉排序树上查找关键值k,请在下划线处填上正确的语句。typedefstructnode{intkey;structnode*lchild;struc

东南大学十套数据结构试题及答案 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数28
  • 收藏数0 收藏
  • 顶次数0
  • 上传人水中望月
  • 文件大小442 KB
  • 时间2019-11-12
最近更新