资源描述：
《东南大学十套数据结构试题及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、22数据结构试卷（一）三、计算题（每题6分，共24分）1.在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。A01234567data605078903440next35720412.请画出下图的邻接矩阵和邻接表。3.已知一个图的顶点集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};用克鲁斯卡尔算法得到
2、最小生成树，试写出在最小生成树中依次得到的各条边。4.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。四、阅读算法（每题7分，共14分）1.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）设链表表示的线
3、性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。2.voidABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<data<<'';}}该算法的功能是：五、算法填空（共8分）二叉搜索树的查找——递归算法:boolFind(BTreeNode*BST,ElemType&item)22{if(BST==NULL)returnfalse;//查找失败else{if(item==BST->data){item=BST->data;//查找成功ret
4、urn ___________;}elseif(itemdata)returnFind(______________,item);elsereturnFind(_______________,item);}//if}六、编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex)22数据结构试卷（二）三、应用题(36分)1．设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排
5、序后的结果。2．设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。3．设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。4．设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成
6、对应的二叉树。5．设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。6．设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。四、算法设计题(16分)1．设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。2．设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。22数据结构试卷（三）
7、二．填空题1.下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。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(
8、-1);}2.下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){if(
