资源描述：
《十套大数据结构精彩试题及问题详解》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实用文档数据结构试卷（一）二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_ _________个，树的深度为___________，树的度为_________。4.后缀算式923+-102/-的值为__________。中缀算式（3+4X）-2Y/3对应的后缀
2、算式为_______________________________。5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。7.AOV网是一种___________________的图。8.在一个具有n个顶点的无向完全图中，包含有______
3、__条边，在一个具有n个顶点的有向完全图中，包含有________条边。9.假定一个线性表为(12,23,74,55,63,40)，若按Key%4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。11.在堆排序的过程中，对任一分支结
4、点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。12.在快速排序、堆排序、归并排序中，_________排序是稳定的。三、计算题（每题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,
5、(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。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；}r
6、eturnL；}请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。1.voidABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<data<<'';}}该算法的功能是：五、算法填空（共8分）二叉搜索树的查找——递归算法:boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失败else{if(it
7、em==BST->data){item=BST->data;//查找成功return ___________;}elseif(itemdata)returnFind(______________,item);elsereturnFind(_______________,item);}//if}六、编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex)文案大全实用文档数据结构试卷（二）二、填空题(24分)1.为了能有效地应用HASH查找技术，必须解决的两
8、个问题是____________________和__________________________。2.下面程序段的功
