电子科技大学期末大数据结构精彩试题及问题详解.pdf

该【电子科技大学期末大数据结构精彩试题及问题详解 】是由【小屁孩】上传分享，beplayapp体育下载一共【27】页，该beplayapp体育下载可以免费在线阅读，需要了解更多关于【电子科技大学期末大数据结构精彩试题及问题详解 】的内容，可以使用beplayapp体育下载的站内搜索功能，选择自己适合的beplayapp体育下载，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此beplayapp体育下载到您的设备，方便您编辑和打印。:..beplayapp体育下载数据结构试卷(一)一、单选题(每题2分,共20分)(A)。,在进行插入运算时(D).、、?(D)[m][n],假设A[0][0]存放位置在644,A[2][2]存放位置在(10)676,每个元素占一个空间,问A[3][3]存放在什么位置?脚注表示用10进(10)(10)(10)制表示。(C)。(D).-+--[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为(D),2,,5,2,,5,,4,2,,(1)(n)(1ogn)(n2)(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K%9作为散列函数,则散列地址为1的元素有(D),该图至少应有(A)条边才能确保是一个连通图。、填空题(每空1分,共26分):正确性易读性强壮性和_高效率。(n3+n2logn+14n)/n2,其数量级表示为___0(n)_____。(C,D(E,F,G),H(I,J)),则树中所含的结点数为_____9_____个,树的深度为_____3____,树的度为_____3____。+-102/-的值为___-1_____。中缀算式(3+4X)-2Y/3对应的后缀算式为_______4X*+2X*3/-________________________。,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。在这种存储结构中,n个结点的二叉树共有__2n______个指针域,其中有___n-1_____个指针域是存放了地址,有______n+1__________个指针是空指针。,在其对应的邻接表中,所含边结点分别有____e___个和____2e____个。。,包含有___n(n-1)/2_____条边,在一个具有n个顶点的有向完全图中,包含有____n(n-1)____条边。:..(12,23,74,55,63,40),若按Key%4条件进行划分,使得同一余数的元素成为一个子表,则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。,若最终引起树根结点的分裂,则新树比原树的高度___________。,对任一分支结点进行筛运算的时间复杂度为________,整个堆排序过程的时间复杂度为________。、堆排序、归并排序中,_________排序是稳定的。三、计算题(每题6分,共24分),表头指针为A[0].next,试写出该线性表。。: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,5,8,3时,每加入一个数据后堆的变化。四、阅读算法(每题7分,共14分)(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)设链表表示的线性表为(a,a,…,a),写出算法执行后的返回值所表示的线12n性表。(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<data<<'';}}:..beplayapp体育下载该算法的功能是:五、算法填空(共8分)二叉搜索树的查找——递归算法:boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失败else{if(item==BST->data){item=BST->data;//查找成功return___________;}elseif(itemdata)returnFind(______________,item);elsereturnFind(_______________,item);}//if}六、编写算法(共8分)统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex):..beplayapp体育下载数据结构试卷(二)一、选择题(24分)()。(A)线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D),若用二叉链表作为存储结构,则该哈夫曼树中总共有()个空指针域。(A)2m-1(B)2m(C)2m+1(D)[0:M-1]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置,尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为()。(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%,前序遍历序列为CABD,则后序遍历该二叉树得到序列为()。(A)BADC(B)BCDA(C)CDAB(D),则该完全无向图中有()条边。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-,则该二叉树的最小高度为()。(A)9(B)10(C)11(D),则该有向图对应的邻接表中有()个表头结点。(A)n-1(B)n(C)n+1(D)2n-(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快速排序的结果为()。(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2,3,6,5,8二、填空题(24分),必须解决的两个问题是____________________和__________________________。,要求在下划线处填上正确的语句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(==m-1)printf(“overflow”);else{____________________;_________________;}}(填有序或无序)。,平均时间复杂度为__________。,度数为1的结点数为N,则该二叉树中度数为012的结点数为_________;若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有_______个空指针域。:..,所有顶点的度数之和为d,则e=_______。(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为___________________________。:从顶点1出发,DFS遍历的输出序列是,BFS遍历的输出序列是三、应用题(36分)(45,80,48,40,22,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。,要求给出用普里姆算法构造最小生成树所走过的边的集合。(45,80,48,40,22,78),要求构造一棵二叉排序树并给出构造过程。四、算法设计题(16分)(K,K,…,K),要求设计一个算法能够在O(n)的时间12n复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于K,右半部分的每i个关键字均大于等于K。,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示。:..beplayapp体育下载数据结构试卷(三)一、选择题(每题1分,共20分)=(D,R),D={01,02,03,04,05,06,07,08,09},R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>},则数据结构A是()。(A)线性结构(B)树型结构(C)物理结构(D)()for(i=1,s=0;i<=n;i++){t=1;for(j=1;j<=i;j++)t=t*j;s=s+t;}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4),若删除单链表中结点A,则需要修改指针的操作序列为()。(A)q=p->next;p->data=q->data;p->next=q->next;free(q);(B)q=p->next;q->data=p->data;p->next=q->next;free(q);(C)q=p->next;p->next=q->next;free(q);(D)q=p->next;p->data=q->data;free(q);,则在堆排序中需要()个辅助记录单元。(A)1(B)n(C)nlogn(D)(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序结束后的结果为()。(A)10,15,14,18,20,36,40,21(B)10,15,14,18,20,40,36,21(C)10,15,14,20,18,40,36,2l(D)15,10,14,18,20,36,40,,则在二叉排序树的平均平均查找长度为()。(A)O(1)(B)O(logn)(C)(D)O(n2),则其对应的邻接表中的表头结点和表结点的个数分别为()。(A)n,e(B)e,n(C)2n,e(D)n,,则该强连通图中至少有()条边。(A)n(n-1)(B)n+1(C)n(D)n(n+1),如果需要用最快的方法选出其中最小的10个记录关键字,则用下列()方法可以达到此目的。(A)快速排序(B)堆排序(C)归并排序(D)()的空间复杂度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序二、填空殖(每空1分共20分)。,则该二叉树的深度为__________;若用二叉链表作为该完全二叉树的存储结构,则共有___________个空指针域。、2、3,则经过栈的作用后可以得到___________种不同的输出序列。[n][n]作为存储结构,则该邻接矩阵中第i行上所有元素之和等于顶点i的________,第i列上所有元素之和等于顶点i的________。:..,则该哈夫曼树中有________个度数为1的结点。,所有的顶点入度数之和为d,则e和d的关系为_________。(填先序、中序或后序)。,如果用二分法查找方法查找数据元素X,则最多需要比较________次就可以断定数据元素X是否在查找表中。,其入栈和出栈操作的时间复杂度均为____________。,如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的双亲结点编号为____________,右孩子结点的编号为___________。(72,73,71,23,94,16,5),则以记录关键字72为基准的一趟快速排序结果为___________________________。={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>},则该图的一种拓扑序列为____________________。,请在下划线处填上正确的语句。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);},请在下划线处填上正确的语句。typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){if(t==0)return(0);elsewhile(t!=0)if(t->key==k)_____________;elseif(t->key>k)t=t->lchild;else_____________;}三、计算题(每题10分,共30分),中序遍历序列是EFAGBCHKIJD,画出此二叉树,并画出它的后序线索二叉树。(36,15,40,63,22),散列用的一维地址空间为[0..6],假定选用的散列函数是H(K)=Kmod7,若发生冲突采用线性探查法处理,试:(1)计算出每一个元素的散列地址并在下图中填写出散列表:`0123456(2)求出在查找每一个元素概率相等情况下的平均查找长度。(10,18,4,3,6,12,1,9,18,8)请用快速排序写出每一趟排序的结果。四、算法设计题(每题15分,共30分):..。。:..beplayapp体育下载数据结构试卷(四)一、选择题(每题1分共20分),则读取第i个数组元素的平均时间复杂度为()。(A)O(n)(B)O(nlogn)(C)O(1)(D)O(n2),则该二叉树中最多有()个结点。(A)2k-1(B)2k(C)2k-1(D)2k-,则该无向图中所有顶点的入度之和为()。(A)n(B)e(C)2n(D)()。(A)O(1)(B)O(n)(C)O(logn)(D)O(n2),则该图中有()条有向边。(A)n(B)n-1(C)m(D)m-(345,253,674,924,627),则用基数排序需要进行()趟的分配和回收才能使得初始关键字序列变成有序序列。(A)3(B)4(C)5(D)()。(A)必须判别栈是否为满(B)必须判别栈是否为空(C)判别栈元素的类型(D)()的空间复杂度最大。(A)快速排序(B)冒泡排序(C)希尔排序(D),度数为1的结点数为N,度数为2的结点数为N,0l2则下列等式成立的是()。(A)N=N+1(B)N=N+N(C)N=N+1(D)N=2N+,则利用二分查找法查找数据元素X的最多比较次数不超过()。(A)logn+1(B)logn-1(C)logn(D)log(n+1)2222二、填空题(每空1分共20分),则直接插入排序的时间复杂度为________,快速排序的平均时间复杂度为_________。,则删除结点X需要执行的语句序列为_________________________________________________________(设结点中的两个指针域分别为llink和rlink)。(19,22,01,38,10)建立的二叉排序树的高度为____________。。(K,K,…,K),则用筛选法思想建堆必须从第______个元12n素开始进行筛选。,则该树中有_________个叶子结点;若采用二叉链表作为存储结构,则该树中有_____个空指针域。,则该循环队列中最多能够存储________个队列元素;当前实际存储________________个队列元素(设头指针F指向当前队头元素的前一个位置,尾指针指向当前队尾元素的位置)。:..,则第i个位置上插入一个数据元素需要移动表中_______个数据元素;删除第i个位置上的数据元素需要移动表中_______个元素。(20,18,22,16,30,19),则以20为中轴的一趟快速排序结果为______________________________。(20,18,22,16,30,19),则根据这些初始关键字序列建成的初始堆为________________________。,用邻接矩阵A作为该图的存储结构,则顶点i和顶点j互为邻接点的条件是______________________。,则A中第i上非0元素的个数_________第i列上非0元素的个数(填等于,大于或小于)。,中序遍历该二叉树的序列为BADC,则后序遍历该二叉树的序列为_____________。(k)=kmodp,解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点,成功时返回指向关键字的指针,不成功时返回标志0。typedefstructnode{intkey;structnode*next;}lklist;voidcreatelkhash(lklist*hashtable[]){inti,k;lklist*s;for(i=0;ikey=a[i];k=a[i]%p;s->next=hashtable[k];_______________________;}}三、计算题(每题10分,共30分)1、画出广义表LS=((),(e),(a,(b,c,d)))的头尾链表存储结构。2、下图所示的森林:(1)求树(a)的先根序列和后根序列;(2)求森林先序序列和中序序列;(3)将此森林转换为相应的二叉树;AGBCHDEFIJK(a)(b)3、设散列表的地址范围是[0..9],散列函数为H(key)=(key2+2)MOD9,并采用链表处理冲突,请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。四、算法设计题(每题10分,共30分):..(大写字母、数字和其它字符),要求利用原单链表中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。。。:..beplayapp体育下载数据结构试卷(五)一、选择题(20分)()。(A)数据项(B)数据类型(C)数据元素(D)(50,40,95,20,15,70,60,45),则以增量d=4的一趟希尔排序结束后前4条记录关键字为()。(A)40,50,20,95(B)15,40,60,20(C)15,20,40,45(D)45,40,15,(25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序子表,则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为()。(A)15,25,35,50,20,40,80,85,36,70(B)15,25,35,50,80,20,85,40,70,36(C)15,25,35,50,80,85,20,36,40,70(D)15,25,35,50,80,20,36,40,70,(“DATASTRUCTURE”,5,9)的返回值为()。(A)“STRUCTURE”(B)“DATA”(C)“ASTRUCTUR”(D)“DATASTRUCTURE”,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为()。(A)O(logn)(B)O(1)(C)O(n2)(D)O(n),度数为1的结点数为N,……,度数为m的结0l点数为Nm,则N=()。0(A)N+N+……+Nm(B)l+N+2N+3N+……+(m-1)Nml2234(C)N+2N+3N+……+(m-1)Nm(D)2N+3N+……+(m+1),则用二分查找查找元素X最多需要比较()次。(A)25(B)10(C)7(D)={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深度优先遍历的顶点序列为()。(A)abedfc(B)acfebd(C)aebdfc(D)、2、3、……、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是()。(A)n-i(B)n-1-i(C)n+1-i(D)不能确定10设一组初始记录关键字序列为(45,80,55,40,42,85),则以第一个记录关键字45为基准而得到一趟快速排序的结果是()。(A)40,42,45,55,80,83(B)42,40,45,80,85,88(C)42,40,45,55,80,85(D)42,40,45,85,55,80二、填空题(共20分)[0:n-1],其中第一个栈项指针top1的初值为-1,第二个栈顶指针top2的初值为n,则判断共享栈满的条件是____________________。。:..,如果按照行的顺序将下三角矩阵中的元素(包括对角线上元素)存放在n(n+1)个连续的存储单元中,则A[i][j]与A[0][0]之间有_______个数据元素。,后进栈的元素必定先出栈,所以又把栈称为__________表;队列的插入和删除运算分别在队列的两端进行,先进队列的元素必定先出队列,所以又把队列称为_________表。,则该二叉树的前序遍历序列为___________,中序遍历序列为___________,后序遍历序列为___________。,则该完全二叉树的深度为________,有__________个叶子结点。,则A中第i行中所有非零元素个数之和等于顶点i的________,第i列中所有非零元素个数之和等于顶点i的__________。(k,k,……,k)是堆,则对i=1,2,…,n/2而言满足12n的条件为_______________________________。,请在下划线处填上正确的语句。voidbubble(intr[n]){for(i=1;i<=n-1;i++){for(exchange=0,j=0;j<_____________;j++)if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=