十套数据结构试题及答案.pdf

该【十套数据结构试题及答案 】是由【小屁孩】上传分享，文档一共【31】页，该文档可以免费在线阅读，需要了解更多关于【十套数据结构试题及答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..数据结构试卷(一)二、填空题(每空1分,共26分):、、和。(n+nlogn+14n)/n2,其数量级表示为。(C,D(E,F,G),H(I,J)),则树中所含的结点数为个,树的深度为,树的度为。+-102/-的值为。中缀算式(3+4X)-2Y/3对应的后缀算式为。,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。在这种存储结构中,n个结点的二叉树共有个指针域,其中有个指针域是存放了地址,有个指针是空指针。,在其对应的邻接表中,所含边结点分别有个和个。。,包含有条边,在一个具有n个顶点的有向完全图中,包含有条边。(12,23,74,55,63,40),若按Key%4条件进行划分,使得同一余数的元素成为一个子表,则得到的四个子表分别为、、和。,若最终引起树根结点的分裂,,对任一分支结点进行筛运算的时间复杂度为,整个堆排序过程的时间复杂度为。、堆排序、归并排序中,排序是稳定的。三、计算题(每题6分,共24分),表头指针为A[0].next,试写出该线性表。。S2:p—>next=q;q—>next=NULL;}returnL;}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};用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。4画出向小根堆中加入数据4,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;:..请回答下列问题:(1)说明语句S1的功能;(2)说明语句组S2的功能;(3)设链表表示的线性表为(a,a,???,a,写出算法执行后的返回值所表示的线性表。i2n)(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):..二、填空题(24分),,要求在下划线处填上正确的语句。typedefstruct(ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx)(if(==m-1)printf(aoverflow");else(;;}}(填有序或无序)。,平均时间复杂度为。,度数为1的结点数为N,则该二叉树中度数为2的结点数为;若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有个空指针域。,所有顶点的度数之和为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)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。,要求给出用普里姆算法构造最小生成树所走过的边的集合。5:..(45,80,48,40,22,78),要求构造一棵二叉排序树并给出构造过程。四、算法设计题(16分)(Ki,&,???,KO,要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于K,右半部分的每个关键字均大于等于K。,要求设计生成集合0=/^B的算法,其中集合A、B和C用链式存储结构表示。:..二、填空殖(每空1分共20分)。,则该二叉树的深度为;若用二叉链表作为该完全二叉树的存储结构,则共有个空指针域。、2、3,则经过栈的作用后可以得到种不同的输出序列。[n][n]作为存储结构,则该邻接矩阵中第i行上所有元素之和等于顶点i的,第i列上所有元素之和等于顶点i的。,贝U该哈夫曼树中有个度数为1的结点。,所有的顶点入度数之和为d,(填先序、中序或后序)。,如果用二分法查找方法查找数据元素X,则最多需要比较次就可以断定数据元素X是否在查找表中。,,如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的双亲结点编号为,右孩子结点的编号为。(72,73,71,23,94,16,5),则以记录关键字72为基准的—趟快速排序结果为。={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>},则该图的——种拓扑序歹U为。,请在下划线处填上正确的语句。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,套,8)请用快速排序写出每一趟排序的结果。四、算法设计题(每题15分,共30分)。。:..数据结构试卷(四)二、填空题(每空1分共20分),则直接插入排序的时间复杂度为,快速排序的平均时间复杂度为。,则删除结点X需要执行的语句序列为_____________________________________________________________(设结点中的两个指针域分别为llink和rlink)。(19,22,01,38,10)建立的二叉排序树的高度为。。(K1,&,???,K),则用筛选法思想建堆必须从第个元素开始进行筛选。,则该树中有个叶子结点;若采用二叉链表作为存储结构,则该树中有个空指针域。,则该循环队列中最多能够存储个队列元素;当前实际存储个队列元素(设头指针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;i<m;i++);for(i=0;i<n;i++){s=(lklist*)malloc(sizeof(lklist));s->key=a[i];k=a[i]%p;s->next=hashtable[k];;}三、计算题(每题10分,共30分)1、画出广义表LS=((),(e),(a,(b,c,d)))的头尾链表存储结构。2、下图所示的森林::..(1)求树(a)的先根序列和后根序列;(2)求森林先序序列和中序序列;(3)将此森林转换为相应的二叉树;3、设散列表的地址范围是[0..9],散列函数为H(key)=(key2+2)MOD9,并采用链表处理冲突,请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。四、算法设计题(每题10分,共30分)(大写字母、数字和其它字符),要求利用原单链表中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。。。:..二、填空题(共20分)[0:n-1],其中第一个栈项指针topi的初值为-1,第二个栈顶指针top2的初值为n,则判断共享栈满的条件是。。,如果按照行的顺序将下三角矩阵中的元素(包括对角线上元素)存放在n(n+1)个连续的存储单元中,贝UA[i][j]与A[0][0],后进栈的元素必定先出栈,所以又把栈称为表;队列的插入和删除运算分别在队列的两端进行,先进队列的元素必定先出队列,所以又把队列称为表。,中序遍历序列为,后序遍历序列为。,则该完全二叉树的深度为,,则A中第i行中所有非零元素个数之和等于顶点i的,第i列中所有非零元素个数之和等于顶点i的。(k-k2,……,k)是堆,则对i=1,2,…,n/2而言满足n的条件为。,请在下划线处填上正确的语句。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=1;}if(exchange==0)return;}},请在下划线处填上正确的语句。structrecord(intkey;intothers;};intbisearch(structrecordr[],intk)(intlow=0,mid,high=n-1;while(low<=high)(if(r[mid].key==k)return(mid+1);elseif()high=mid-1;elselow=mid+1;}return(0);}三、应用题(32分)。:..(如右图所示),给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。(15,17,18,22,35,51,60),要求计算出成功查找时的平均查找长度。,散列函数H(k)=kmod7,初始记录关键字序列为(25,31,8,27,13,68),要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。四、算法设计题(28分)。。:..数据结构试卷(六)二、判断题(20分)。(),而且与块的长度有关。()。(),完全二叉树不一定是满二叉树。(),则能够唯一确定出该二叉树的形状。()。(),则二叉树BT中一定没有右子树。()。()。()。()三、填空题(30分)(i=1,t=1,s=0;i<=n;i++){t=t*i;s=s+t;}的时间复杂度为。,指针变量s指向被插入的新结点X,则进行插入操作的语句序列为(设结点的指针域为next)。=(D,R),D={1,2,3,4,5},R={r},r={<1,2>,<2,4>,<4,5>,<1,3>,<3,2>,<3,5>},贝U给出该图的一种拓扑排序序列。,则该无向图中每个顶点的度数最多是。,度数为1的结点数为30,则该二叉树中总共有个结点数。,,则判断指针变量p所指向的结点为叶子结点的条件是。。,最坏的情况下为。。四、算法设计题(20分)。。:..数据结构试卷(七)二、判断题(20分),在顺序存储结构上都需要考虑“溢出”情况。(),则该结点一定成为叶子结点。(),则在该堆中插入一个新结点的时间复杂度为O(logn)。()。()。()。()。(),该二叉树的右子树不一定为空。()。()。()三、填空题(30分),指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为=p;s->right=p->right;=s;p->right->left=s;(设结点中的两个指针域分别为left和right)。,则该完全有向图中共有条有向条;设完全无向图中有n个顶点,贝U该完全无向图中共有条无向边。(Kl,&,???,K),则用筛选法建初始堆必须从第个元素开始进行筛选。。,21个度数为2的结点,则该二叉树中度数为3的结点数有个。,最多有个结点。(24,35,12,27,18,26),则第3趟直接插入排序结束后的结果的是。(24,35,12,27,18,26),则第3趟简单选择排序结束后的结果的是。。,请在下划线处填上正确的语句。structrecord{intkey;datatypeothers;};voidquickpass(structrecordr[],ints,intt,int&i){intj=t;structrecordx=r[s];i=s;while(i<j){while(i<j&&r[j].key>)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while()i=i+1;if(i<j){r[j]=r[i];j=j-1;}};:..四、算法设计题(20分)。。。:..数据结构试卷(八)三、填空题(30分)(49,38,65,97,76,13,27,50),则以d=,请在下划线处填上正确的内容。typedefstructnode(intdata;structnode*lchild;structnode*rchild;}bitree;voidbstinsert(bitree*&t,intk)(if(t==0)(;t->data=k;t->lchild=t->rchild=0;}elseif(t->data>k)bstinsert(t->lchild,k);else;},则在结点A的后面插入结点X需要执行的语句序列:s->next=p->next;;。,指针变量p指向双向链表中的第一个结点,则指针变量p和指针变量head之间的关系是p=和head=(设结点中的两个指针域分别为llink和rlink)。,最多有个结点。<V,V>,则其对应的邻接矩阵A中的数组元素A[i][j](49,38,65,97,76,13,27,50),则第4趟直接选择排序结束后的结果为。,则对应的最小生成树上有条边。(50,16,23,68,94,70,73),则将它们调整成初始堆只需把16与相互交换即可。四、算法设计题(20分)。。:..二、填空题(30分),指针s指向被插入的结点X,则在结点A的前面插入结点X时的操作序列为:1)s->next=;2)p->next=s;3)t=p->data;4)p->data=;5)s->data=t;,则该二叉树中有个叶子结点。,且规定队头指针F指向队头元素的前一个位置,队尾指针R指向队尾元素的当前位置,则该循环队列中最多存储队列元素。(40,50,95,20,15,70,60,45,10)进行冒泡排序,则第一趟需要进行相邻记录的比较的次数为,在整个排序过程中最多需要进行趟排序才可以完成。,如果从平均情况下排序的速度最快的角度来考虑应最好选择排序,如果从节省存储空间的角度来考虑则最好选择排序。(20,12,42,31,18,14,28),则根据这些记录关键字构造的二叉排序树的平均查找长度是。。,字母在电文中出现的频率分别为7、19、2、6、32、3、21、10,根据这些频率作为权值构造哈夫曼树,。(80,70,33,65,24,56,48),则,则其最小生成树上所有边的权值之:..数据结构试卷(十)二、填空题(48分,其中最后两小题各6分),则至少需要比较次,至多需要比较次。,直接插入排序算法的平均时间复杂度为。,则在该树中查找关键字key最多需要比较次。,则比较一次查找成功的结点数有个,比较两次查找成功有结点数有个。,用多重链表表示其存储结构,则该树中有个空指针域。:q=p->next;p->data=q->data;p->next=;feee(q);:、和。,则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为;用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为。,散列函数H(k)=k%7,用线性探测法解决冲突,则根据一组初始关键字序列(8,15,16,22,30,32)构造出的散列表的平均查找长度是。(38,65,97,76,13,27,10),则第3趟冒泡排序结束后的结果为。(38,65,97,76,13,27,10),则第3趟简单选择排序后的结果为。=(<1,2>,<2,3>,<1,4>,<4,5>,<5,3>,<4,6>,<6,5>},贝U该图的一个拓扑序歹U为。,请在下划线处填上正确的内容。typedefstructnode(intdata;structnode*lchild;;}bitree;voidcreatebitree(bitree*&bt)(scanf("%Cch);if(ch=='#');else(bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;;createbitree(bt->rchild);}},请在下划线处填上正确的内容。typedefstructnode(intdata;structnode*next;}lklist;voidlklistcreate(*&head)(for(i=1;i<=n;i++)(p=(lklist*)malloc(sizeof(lklist));scanf("%d',&>data));p->next=0;if(i==1)head=q=p;else(q->next=p;;}}三、算法设计题(22分)。。(kk…,k)是堆,设计算法将关键字序列(kk整为)i,2,n-ii,2,…,k,X调n-1:..堆。:..数据结构试卷(一)参考答案二、填空题二、填空题(每空1分,共26分)(n).-134X*+2Y*3/--1n+(n-1)/2n(n-1)9.(12,40)()(74)(23,55,63)(logn)