数据结构下学期测试题及答案.pdf

该【数据结构下学期测试题及答案 】是由【青山代下】上传分享，文档一共【20】页，该文档可以免费在线阅读，需要了解更多关于【数据结构下学期测试题及答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..将一个n×n的三对角矩阵A=[a]的三条对角线上的元素按行优先顺序存储ij在一维数组B[1..3n-2]中,则元素a在B中的位置是________。+2j-+j+-j++j-。(S,1),PUSH(S,2),POP(S),PUSH(S,3),PUSH(S,4),POP(S),PUSH(S,5)后,栈S中从栈顶到栈底元素的排列顺序是________。,3,,3,,4,,4,[0..n-1]作为一个循环队列,f为队头元素的前一个位置,r为队尾元素的位置,那么在队列未满时进行将元素x进队的操作需要执行________。=r+1;Q[r]=x;=(r+1)%n;Q[r]=x;[r]=x;r=r+1;[r]=x;r=(r+1)%n;,中序序列是GECBFDA,那么其后序序列是________。。--(有向边)。(n-1)/-+,其广度优先搜索算法使用的一种辅助数据结构为_________。,采用折半查找技术,在等概率情况下,查找成功的平均查找长度是_________。//(),其地址()。:..)结构。,图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系,()为下图所示有向图的一个拓扑序列。{k1,k2,…,kn},当且仅当满足关系ki≤k2i且ki≤k2i+1(2i≤n,2i+1≤n)称其为小根堆,反之,当且仅当满足关系ki≥k2i且ki≥k2i+1(2i≤n,2i+1≤n)则为大根堆,以下序列中()不符合堆的定义。A.(4,10,15,72,39,23,18)B.(58,27,36,12,8,23,9)C.(4,10,18,72,39,23,15)D.(58,36,27,12,8,23,9),已知q所指结点是p所指结点的直接前驱,若在q和p之间插入s所指结点,则执行()操作。->next=p->next;p->next=s;->next=s;s->next=p;->next=s->next;s->next=p;->next=s;s->next=q;(),并进行中序遍历,可得到一个有序序列。,可能要探测多个位置,在查找成功的情况下,所探测的这些位置的键值()。,行下标的范围从0~8,列下标的范围从0~9,则存放A至少需要()个字节。,求q在p中首次出现的位置的运算称作()。:..)。、,在表头删除元素的时间复杂度为,在表尾删除元素的时间复杂度为。#5*3#12+-的值为__________。(#为数据间分隔符),b,c,d依次进S栈,若要在输出端得到序列cbda,则应进行的操作序列为push(S,a),push(S,b),push(S,c),_____________,pop(S),_____________,pop(S),pop(S)。[n]用来表示一个循环队列,front为队头元素的前一个位置,rear为队尾元素的位置,计算队列中元素个数的公式为__________。,一棵深度为3的满三叉树中的结点数为_________个。,3个度为2的结点,4个度为3的结点。则该树有个叶子结点。,则该图的全部顶点可以排成一个拓扑序列。,平均查找长度与结点个数无关的查找方法是。,在___________情况下比较的次数最少,其比较次数为__________。。(B,C(D,E,F),G(H,K)),则树中所含的结点数为______个,树的深度为______,树的度为______。3:.._________、_________、_________和强壮性四个方面评价算法的质量。,则直接插入排序的时间复杂度为(________),快速排序的平均时间复杂度为O(_________),以上两种排序算法中__________________是稳定的排序算法。,则比较一次查找成功的结点数有_________个,比较两次查找成功有结点数有_________个。(8,23,74,51,63,36),若按Key%4条件进行划分,使得同一余数的元素成为一个子表,则可以得到_________________________、_______________________、和__________________________三个子表。[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为;队满共有个元素。+-82/-的值为______。中缀算式(3+4*A)-2*B/3对应的后缀算式为___________________。,则该二叉树的前序遍历序列为_____________,后序遍历序列为_____________。,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。在这种存储结构中,n个结点的二叉树共有________个指针域,有________________个指针是空指针。,从顶点1出发,DFS遍历的输出序列是______________,BFS遍历的输出序列是______________。图14:..(data,next),next为指针域,已知指针px指向单链表中data为x的结点,指针py指向data为y的新结点,若将结点y插入结点x之后,则需要执行以下语句:;。,2,3,4……n,其输出序列为p1,p2,p3,……pn,若p1==n,则pi为___________;若用E表示入栈操作,D表示出栈操作,若元素入栈的顺序为1234,为了得到1342出栈顺序,相应的E和D的操作串为__________________。三、应用题/[m]存放循环队列的元素,设变量rear和qlen分别指示循环队列中队尾元素的位置和元素的个数。(1)写出队满的条件表达式;(2)写出队空的条件表达式;(3)设m=40,rear=13,qlen=19,求队头元素的位置。。下标从1开始。。5:..“abcdef”的字符串,出现的频度依次为14,6,7,33,12,28,试以频度为权值生成哈夫曼树(权值小在左,权值大在右),画出该哈夫曼树,给出各个字母相应的哈夫曼编码,并计算其带权的路径长度。(i,j):w为:(4,6):30(2,5):40(4,7):42(3,7):45(1,2):50(4,5):50(3,4):52(1,3):60(2,4):65(5,6):70用普里姆(prim)算法构造该图的最小生成树(从顶点1开始)。,画出此图,并写出从C点开始按深度优先遍历和广度优先遍历该图的结果。(46,88,45,39,70,58,66,40)建立一个AVL树(平衡二叉树,设初始为空),画出该树。(26,25,20,33,21,24,45,204,42,38,29,31),要用散列法进行存储,规定装载因子a=。(1)请给出除取余数法的散列(哈希)函数。6:..表,并指出发生冲突的次数。[8]={3,9,45,6,16,47,33,80};建立相应的大顶堆。: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};用克鲁斯卡尔算法得到最小生成树,(1)给出按边的权值排序的序列;(2)写出在最小生成树中依次得到的各条边。,表头指针为A[0].next,试写出该线性表。={<1,2>,<2,3>,<3,4>,<5,2>,<2,6>,<6,3>,<6,7>,<7,4>},(1)画出这个有向图;(2)在下面①~③的序列中,找出该图的一个拓扑序列_________________________。①1234567②1526374③(29,8,47,63,22),散列空间如下表,假定选用的散列函数为H(K)=K%7,对发生的冲突采用线性探查法处理,试:(1)计算出每一个元素的散列地址(2)并填写散列表;`0123456(3)求出在概率相等情况下查找成功的平均查找长度。7:..2所示的森林转换为相应的二叉树。(80,70,33,65,24,56,48),(1)给出用筛选法建成的初始小根堆;(2)给出输出两个关键字后的剩余堆。(8,5,2,12,7,1,6,10,9,3,4,11)升序重新排列,(1)给出冒泡排序一趟扫描的结果;(2)给出二路归并排序一趟扫描的结果;(3)给出快速排序一趟扫描的结果。,中序序列为CBEDFAGH,请画出该二叉树。{16,3,7,11,9,},(1)构造平衡二叉树;(2)给出该平衡二叉树的中序遍历序列。{C,A,S,T},各个字符出现的频度(次数)是W={2,7,4,5}。(1)以它们为各叶结点上的权值,建立哈夫曼树;(2)左分支赋0,右分支赋1,给出各个字符的哈夫曼编码。四、,现要删除单链表中多余的元素即元素值相同的只8:..structNode{intdata;structNode*next;};算法原型为:intdelGivenV(structnode&*head);试设计该算法。:typedefstructNode{intdata;structNode*lchild,*rchild;}BTree,*BT;算法原型为:intIsBiSTree(BTRoot);请设计该算法。,a[]表示顶点数据,n为顶点个数,e为边数,采用邻接矩阵存储结构,给出建立一个无向图的邻接矩阵的算法。Template<classDataType>Mgraph<DataType>::Mgraph(DataTypea[],intn,inte)}[],栈顶位置用top表示,设要遍历二叉树的根指针为root,左孩子lchild,右孩子rchild,给出二叉树前序遍历非递归算法。template<classDataType>voidBiTree::PreOrder(BiNode<DataType>*root){},存放在r[]中,见下面筛选法调整堆的算法,(1)给出堆排序算法;(2)排序结果是升序序列还是降序序列?voidsift(intr[],intk,intm){//要筛选结点的编号为k,堆中最后一个结点的编号为mi=k;j=2*i;while(j<=m)//筛选还没有进行到叶子{if(j<m&&r[j]<r[j+1])j++;//左右孩子中取较大者9:..else{r[i]r[j];i=j;j=2*i;}}}voidHeapSort(intr[],intn){},左孩子为lchild,右孩子为rchild,数据域为data。设计一个算法判断二叉树是否为平衡二叉树,设已有算法depth(BiNode*root),该算法返回树root的深度。voidIsAVL(BiNode*root){}10:..BABCDDBACBCADCA二、(n)O(1)(S)push(S,d)4.(n+rear-front)%-15或31(3-1)/-(或高效率)(n2)O(nlogn).(8,36)(74)(23,51,63)顺序无关16.(rear-front+m)%mm-117.-134A*+2B*3/-+120.(1,3,4,5,2)(1,3,2,4,5)->next=px->next;px->next=-i+1EDEEDEDD三、应用题/:(1)队满的条件表达式:qlen==m(2)队空的条件表达式:qlen==0(3)设m=40,rear=13,qlen=19,则11:..:设三元组的表示rowcolitem013111582324334344165625…MaxTerm-::哈夫曼树12:..b:0110c:0111d:11f:10e:010带权的路径长度WPL=2*(14+28+33)+12*3+(6+7)*4=:用prim算法求得的最小生成树如下::该图为:13:..CABDEFC点开始广度优先遍历该图的结果::按AVL树的构造规则,依次插入46,88,45,39,70,58,如下:出现了不平衡,为LL型,调整得:再插入66,40,得14:..型,调整得最终AVL树如下::因为关键码序列中元素个数为12,而规定装载因子a=,故散列表容量为12/=20(1)除取余数法的散列(哈希)函数H(key)=key%20(2)散列表为:序号012345678910111213141516171819key2021422425264520429313338发生冲突::数组intA[8]={3,9,45,6,16,47,33,80}对应的完全二叉树初始树为:经过调整后的大顶堆如下:15:..(1,2),(4,6),(1,3),(1,4),(2,5),(4,7)或(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7):(78,50,40,60,34,90):1526374或②13.(1)H(29)=29%7=1;H(8)=8%7=1;H(47)=47%7=5;H(63)=63%7=0;H(22)=22%7=1;(2)012345663298224712+1+1+3(3)ASL==:16:..BGCHDIEJFK初始小根堆:(24,65,33,80,70,56,48)剩余小根堆:(48,65,56,80,70)(8,5,2,12,7,1,6,10,9,3,4,11)中的关键码按字母序的升序排列,(1)冒泡排序一趟扫描的结果是5,2,8,7,1,6,10,9,3,4,11,12;(2)二路归并排序一趟扫描的结果是5,8,2,12,1,7,6,10,3,9,4,11;(3)快速排序一趟扫描的结果是4,5,2,3,7,1,6,8,9,10,12,11;,中序序列为CBEDFAGH,请画出该二叉树。A/BG/CDH/EF18.(1)构造平衡二叉树(2)中序序列:3,7,9,11,1617:..A:0T:10C:110S::structNode{intdata;structNode*next;};intdelGivenV(structnode&*head){structNode*p=head,*q;q=p->next;while(q->next){p=q;q=q->next;if(p->data==q->data){p->next=q->next;deleteq;q=p->next;}}}:typedefstructnode{intdata;structnode*lchild,*rchild;}BTree,*BT;18:..{if(Root->lchild!=NULL){if(Root->lchild->data>Root->data)returnfalse;if(IsBiSTree1(Root->lchild)==false)returnfalse;;}if(Root->rchild!=NULL){if(Root->rchild->data<Root->data)returnfalse;if(IsBiSTree1(Root->rchild)==false)returnfalse;}returntrue;}<classDataType>MGraph<DataType>::MGraph(DataTypea[],intn,inte){vertexNum=n;um=e;for(i=0;i<vertexNum;i++)vertex[i]=a[i];for(i=0;i<vertexNum;i++)for(j=0;j<vertexNum;j++)arc[i][j]=0;for(k=0;k<um;k++){cin>>i>>j;arc[i][j]=1;arc[j][i]=1;}}<classDataType>voidBiTree::PreOrder(BiNode<DataType>*root){top=-1;19:..{while(root!=NULL){cout<<root->data;s[++top]=root;root=root->lchild;}if(top!=-1){root=s[top--];root=root->rchild;}}}(intr[],intn){for(i=n/2;i>=1;i--)sift(r,i,n);for(i=1;i>n;i++){r[1]r[n-i+1];sift(r,1,n-i);}}(BiNode*root){if(Root==NULL)returntrue;if(IsAVL(Root->lchild)==false)returnfalse;if(IsAVL(Root->rchild)==false)returnfalse;if(abs(depth(Root->lchild)-depth(Root->rchild))<=1)returntrue;elsereturnfalse;}20