数据结构试题A

一、单项选择题（在每小题的4个备选答案中，选出1个正确的答案，并将其号码填在题干的括号内。每小题2分，共30分）若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用（）存储方式最节省时间。A）单链表B）双链表 C）单向循环链表D）顺序表串是任意有限个（ ）A）符号构成的序列 B）符号构成的集合 C）字符构成的序列 D）字符构成的集合设矩阵A的任一元素aij（1<i,j<10）满足：a丰0;（i>j,1<i,j<10）<ija=0；（i<j,1<i,j<10）ij现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9,5]的首地址为（）。A）2340B）2336C）2164D）2160如果以链表作为栈的存储结构，则退栈操作时（）A）必须判别栈是否满B）对栈不作任何判别C）必须判别栈是否空D）判别栈元素的类型设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（）A）front二front+1B）front=（front+1）%mC）rear=（rear+1）%mD）front=（front+1）%（m+1）深度为6（根的层次为1）的二叉树至多有（）结点。A）64 B）32 C）31 D）63将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。则编号为49的结点X的双亲的编号为（）。A)24 B)25 C)23D)无法确定设有一个无向图G=(V,E)和仑'=(V',E'),如果G;G的生成树，则下面不正确的说法是()。A)G'为G的子图B)G'为G的连通分量 C)G'为G的极小连通子图且V=VD)G'为G的一个无环子图下列序列中，( )是执行第一趟快速排序后得到的序列。(排序的关键字类型是字符串)A)[da，ax，eb，cd，bb]ff[ha，gc]B)[ge，ax，eb，cd，bb]ff[da，ha]C)[cd，eb，ax，da]ff[ha，gc，bb]D)[ax，bb，cd.da]ff[eb，gc，ha]二分查找要求被查找的表是( )。A)键值有序的链接表 B)链接表但键值不一定有序C)键值有序的顺序表 D)顺序表但键值不一定有序当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为( )。A)n2 B)nlognc)lognD)n-1堆是一个键值序列代，k2,…，k\对i二1,2,…，_n/2_|，满足()。A)kWkWk B)k<k<ki2i2i+1 i2i+12iC)kWk且kWk(2i+IWn) D)kWk或kWk(2i+1Wn)i2ii2i+1 i2ii2i+1使用双向链表存储数据,其优点是可以()。A)提高检索速度 B)很方便地插入和删除数据C)节约存储空间 D)很快回收存储空间设计一个判别表达式中左右括号是否配对出现的算法,采用()数据结构最佳。A)线性表的顺序存储结构 B)栈C)队列 D)线性表的链式存储结构设高度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为()。A)k+IB)2kC)2k-1 D)2k+1

二、填空题（每空2分，共28分）设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是 r=s；r-＞next二NULL。在单链表中，指针p所指结点为最后一个结点的条件是3.设一个链栈的栈顶指针是Is,栈中结点格式为3.设一个链栈的栈顶指针是Is,栈中结点格式为infolink栈空的条件是 。如果栈不为空，则退栈操作为p=ls； ;free（p）。已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有 个叶子结点。TOC\o"1-5"\h\z树有三种常用的存储结构，即孩子链表法，孩子兄弟链表法禾 。n个顶点的连通图的生成树有 条边。—个有向图G中若有弧＜v,v＞、＜v,v＞和＜v,v＞,则在图G的拓扑序列中，顶点v,i j j k i k iv和v的相对位置为 。j k设表中元素的初始状态是按键值递增的，分别用堆排序，快速排序、冒泡排序和归并排序方法对其进行排序（按递增顺序）， 最省时间， 最费时间。下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。typedefstruetnode{intkey；struetnode*left,*right；}voidsearehinsert(intx;pnodet)/*t为二叉排序树根节点的指针*/{if( ){p=malloe(suze)；p->key=x;p->left二NULL；p->right二NULL；t=p；elseif（x<t->key）searchinsert（x,t->left）else }线性表的 主要有点是从表中任一结点出发能访问到所有结点。而使用 ，可根据需要在前后两个方向上方便地进行查找。三、应用题（本题共28分）树的后根遍历方法是：若树非空，则1） 依次后根遍历根的各个子树T,T2,……，T；12m2） 访问根节点。对图1所示的树，用后根遍历方法进行遍历，请写出遍历所得到的结点访问序列。（4分）图1树将图2的森林转换成二叉树。（4分）

图2森林图3表示一个地区的交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。（4分）4．已知一个无向图的邻接表如图4所示。V—*2—*4AV54 >1 AV345A-11图4邻连表1） 画出这个图。2） 以v1为出发点，对图进行广度优先搜索，写出所有可能的访问序列。本题4分，每设n个元素的有序表为R,K为一个给定的值，二分查找算法如下:intbinswarth(sqlistR；keytypeK){L=1；h=n；suc=O；while((L<=h)&&(!suc){mid二(L+h)/2；switch{K二R[mid].key：suc=L；break；k<R「mid].key：h二mid-丨；break：K>R[mid].key:L=mid+1}}if(suc)return(mid)elsereturn(O)：}将上述算法中划线语句改为：K<R[mid].key：h二mid。改动后，算法能否正常工作请说明原因。若算法不能正常工作，给出一个查找序列和一个出错情况的查找键值：若能正常工作，请给出一个查找序列和查找某个键值的比较次数。(本题6分，每小题3分)有一组键值25,84,21,47,15,27,68,35,24,采用快速排序方法由小到大进行排序，请写出每趟的结果，并标明在第一趟排序过程中键值的移动情况。(本题6分)、设计题(共14分)1•设一颗二叉树以二叉链表为存储结构,1•设一颗二叉树以二叉链表为存储结构,Ickild.lata.rchild。设计一个算法,求在先根序列中处于第k个位置的结点。(本题6分)2•设某个单链表L的结点结构为"能|，试画出该链表的结构图，并用c语言编数据结构导论模拟试卷(一)分析与解答一、单项选择题1，D．2，C．3，D．4，C．5，D．6，D．7，A．8，B．9，A．10，C．11，D．12，C．13，A．14B．15，C。二、填空题1分析：在r所指链尾插入了所指结点，需执行的三步操作是：1)r->next=s；2)r=s；r->next=NULL答案：r->next二s。分析：单链表最后一个结点的指针域为空，所以可用p->next二二NULL作为判断最后一个结点的条件。3•分析：当栈空时，栈顶指针为空，故判栈空条件为Is二二NULL。栈非空时，退栈操作步骤为：p=Is；Is=Is->Iink；free(p)答案：Is二二NULL,Is二ls->link。分析：设n=2,n=3,n二4,123树的总结点数为n二n+n+n+n。0123(1)树的分支树为nT二n+2n+n。1 2 3(2)(2)-(1)：-1=n+2n-n230有n二n+2n+1=3+2X4+仁120 2 3答案：12。答案：双亲表示法。6•分析：n个顶点的连通图，其生成树有且仅有n-1条边。答案：n-1。分析：按题意画出图5所示示意图。由此知，在拓扑序列中i,j,k的相对位置是i,j,k。答案：i,j,k。分析：对冒泡排序来讲，由于哨兵的作用，经一趟排序后，就能判断出当前无序区已经自然有序，终止算法。故它最省时间。对快速排序来讲，由于待排序空间是有序的，每趟排序后，中间元素的左边总是一个空区域，而右边区域长度仅比上一趟少1。因此当在最坏情况下，占用时间最长。答案：冒泡排序、快速排序。答案：t二二NULL,searchinsert(x,t->right)。分析：线性表的存储方式有多种，其中循环链表的主要优点是从表中任一结点出发，都能访问到所有其它的结点。而如果采用双向链表，则可以按前后两个方向进行查找。答案：循环链表、双向链表。

三、应用题1答案:EBFGCKHIJDA。2.分析：先将每棵树转换成二叉树，然后再将各二叉树的根结点作为兄弟连接在一起而树转换成二叉树的方法是，先将兄弟结点连在一起，然后除最左边的孩子外，断开其它双亲到孩子的连线。答案：如图6所示。(b)以结点为中心旋转45°图6森林转换成二叉树分析：本题实际上是求最小生成树问题。由于图中有两条权值为6的边，故可以得到两种方案。答案：如图7所示。图7由网络得到的最小生成树答案：1）如图8所示。

图8图4所示邻接表所对应的图(2)VVVVV和vvvvv。1245314235分析：经过改动以后，有可能出现死循环，比如当查找的键值k小于有序表中的最小键值时，就会出现死循环。答案：(1)算法不能正常运行。(2)假设有序表的查找序列为(7,10,12,16,24,39,42)，当待查的键值为k=5时,出现死循环。6．答案：25842l471527683520第一趟[201521]25[4727683584]第二趟[15]20[21]25[3527]47[6884]第三趟15202125[27]354768[84]得到：15202l252735476884第一趟排序过程中键值的移动情况如图9所示。设计题1.分析：因为是求前根序列中处于第k个位置的结点，所以本算法是按前根遍历来实现的。在这当中，访问根结点的操作就是计算器count加1，然后判断count是否等于k，等于k就退出并返回指向对应结点的指针，否则继续按前根遍历往下查找。答案：Viodsearch(bitreptrt；integerk){if(t!=NULL){count++；if(count==k)return(t)；else{search(t->lchild,k)；search(t->rehi