计算机数据结构考试题及答案

全真模拟试题（一）一、 单项选择题（在每小题的4个备选答案中，选出正确的答案，并将其号码填在题干的括号内。每小题2分，共24分）若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。单链表②双链表③单向循环④顺序表2．串是任意有限个（）①符号构成的序列 ②符号构成的集合③字符构成的序列 ④字符构成的集合设矩阵A（aij，l<i,j<10）的元素满足：aij和（Aj,1弐j<10）aij=0（i<j,l<i,j<10）现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9]⑸的首址为①2340 ②2336 ③2164 ④21604．如果以链表作为栈的存储结构，则退栈操作时（）必须判别栈是否满对栈不作任何判别必须判别栈是否空判别栈元素的类型5.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（）①front=front+l ②front=（front+l）%m③rear=（rear+l）%m ④front=（front+1）%（m+1）6．深度为6（根的层次为l）的二叉树至多有（）结点。① 64 ②32 ③31 ④637．将含l00个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（）①24 ②25 ③23 ④无法确定设有一个无向图G=（V，E）和G'=（V'，E'）如果G'为G的生成树，则下面不正确的说法是（）①G'为G的子图 ②G'为G的边通分量③G'为G的极小连通子图且V'=V④G'为G的一个无环子图9．用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（）①一定都是同义词②一定都不是同义词③都相同 ④不一定都是同义词10． 二分查找要求被查找的表是（ ）①键值有序的链接表②链接表但键值不一定有序③键值有序的顺序表④顺序表但键值不一定有序11． 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（）①n2 ②nlog2n ③1og2n ④n-112. 堆是一个键值序列{k1,k2,...,kn},对i=1,2,...,|_n/2_|,满足（）①ki<k2i<k2i+1 ②kivk2i+1vk2i③ki<k2i且ki0k2i+l（2i+19）④ki<k2i或ki<k2i+1（2i+1<n）二、 判断题（判断下列各题是否正确，正确在括号内打“V”，错的找“X”。每小题1分，共10分）1．双链表中至多只有一个结点的后继指针为空。（）2．在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（）3．对链表进行插入和删除操作时，不必移动结点。（）4．栈可以作为实现程序设计语言过程调用时的一种数据结构。（）在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧va,b>。（）i对有向图G,如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。（ ）“顺序查找法”是指在顺序表上进行查找的方法。（）向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）键值序列{A,C，D，E，F，E，F}是一个堆。二路归并时，被归并的两个子序列中的关键字个数一定要相等。（）三、 填空题（每空2分，共24分）设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是 ；r=s;r->next=null;。在单链表中，指针p所指结点为最后一个结点的条件是 。设一个链栈的栈顶指针是Is,栈中结点格式为info|link，栈空的条件是 .如果栈不为空，则退栈操作为p=ls； ；free（p）;。已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有 个叶子的结点。树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和 .N个顶点的连通图的生成树有 条边。一个有向图G中若有弧<vi,vj>、<vj,vk>和<vi,vk>,则在图G的拓扑序列中，顶点vi,vj和vk的相对位置为 。设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行（按递增排序）， 最省时间， 最费时间。下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。typedefstructpnode{intkey;structpnode*left,*right;}pnode;voidsearchinsert（intx,pnodet）/*t为二叉排序树根结点的指针*／{if（ ）{p=malloc（size）;p->key=x;p->lchild=null;p->rchild=null;t=p;}elseif（x<t->key）searchinsert（x,t->lchild）else ;}四、 应用题（本题共28分）树的后根遍历方法是：若树非空则（4分）(1)依据次后根遍历根的各个子树T1,T2,……Tm;(2)访问根结点将下图的森林转换为二叉树。(4分)下图表示一个地区的交通网,顶点表示城市,边表示连结城市间的公路,边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路,画出所有可能的方案。(4分)图7.11遍历无向图(a)无向图G6(b)深度优先搜索示例(c)G6的邻接表表示(c)表头结点4．已知一个无向图的邻接表如下图所示。(本题4分,每小题2分)画出这个图。以v1为出发点,对图进行广度优先搜索,写出所有可能的访问序列。5•设n个元素的有序表为R,K为一个给定的值，二分查找算法如下：intbinsearch(sqlistR,keytypeK){j=1;h=n;suc=0;while((j<=h)&&(!suc)){mid=(j+h)/2;switch{caseK=R[mid].key:suc=1;break;caseK<R[mid].key:h=mid-1;break;caseK>R[mid].key:j=mid+1}}if(suc)return(mid);elsereturn(0);}将上述算法中划线语句改为：K<R[mid].key:h=mid.改动后，算法能否正常工作？请说明原因。若算法不能正常工作,给出一个查找序列和一个出错情况的查找键值；若能正常工作，请给出一个查找序列和查找某个键值的比较次数。(本题6分，每小题3分)6.有一组键值25,84,21,47,15,27,68,35,24,采用快速排序方法由小到大进行排序请写出每趟的结果，并标明在第一趟排序过程中键值的移动情况。(本题6分)五、设计题(共14分)1．设棵二叉树以二叉链表为存储结构，结点结构为lchild|data|rchild。设计一个算法，求在前根序列中处于第k个位置的结点。(本题6分)设某单链表L的结点结构为dataInext，试画出该链表的结构图，并用类C语言编写算法判断该链表的元素是否是递增的。(本题8分)全真模拟试题(一)参考答案一、单项选择题1④2③3④分析：按题意，矩阵A是个三角矩阵，A[I,j]的首地址可用下列公式计算：LOC(aij)=LOC(a11)+(k-1)*L其中K为A[I,j]在A中的序号k=I*(I-1)/2+j,L为每个元素所占的单元数。所以有：LOC(aij)=2000+(9*(9-1)/2+5-1)*4=2000+160=2160。故为答案④TOC\o"1-5"\h\z③④④①②分析：如果G'为G的生成树，那么G'是G的子图，也是G的无环子图，并且还是G的极小连通子图，且V'=V，而连通分量则是指无向图的极大连通子图。故答案②是错误的。④10。③11。④12。③二、 判断题v2.x3.v4.v5.x6.x7.x8.v9.v10.x三、 填空题1. R->next=s.P->next==NULLLs==NULL、ls=ls->link.12分析：设n1=2,n2=3,n3=4,树的总结点数为n=n0+n1+n2+n3树的分支数为n-1=n1+2n2+3n3②-①得：-1=n2+2n3-n0有n0=n2+2n3+1=3+2*4+1=12双亲表示法。N-1I,j,k.冒泡排序、快速排序T==NULL、searchinsert(x,t->rchild).四、 应用题1. EBFGCKHIJDA。2.答案如图应用题I9.2.2所示。3.分析：本题实际上是求最小生成树问题。由于衅中有两条权值为6的边，故可以得到两种方案。答案如图应用题I9.3.2所示。答案：(1)答案如图应用题I9.4.2所示。(2)v1v2v4v5v3和v1v4v2v3v5。(1)经过改动以后，有可能出现死循环，比如当查找的键值K小于有序表中的最小键值时，就会出现死循环。故算法不能正常进行。(2)假设有序表的查找序列为(2,3,4,5,6)，当待查的键值K=1时，出现死循环。答案：25 84 214715276835 24第一趟[241521]25[4727683584]第二趟[2115]2425[3527]47[6884]AA* +比第三趟[15]212425[27]354768[84]得到152124252735476884第一趟排序过程中键值的移动情况如下：第一趟：[258421471527683524]一次交换之后[248421471527683525]二次交换之后[242521471527683584][242521471527683584][242521471527683584][242521471527683584]三次交换之后[241521472527683584][241521472527683584]四次交换之后[241521254727683584]以上“-”表示当前经比较不交换位置的元素。“”表示当前经比较交换位置的元素。五、设计题1.Bitreptrsearch(bitreptrt,intk