题_部分答案_全真模拟.doc 34页

'云南财经大学信息学院《数据结构》模拟试题题库《数据结构》课程建设小组 模拟试题部分一、单项选择题1.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用____（3）__________存储方式最节省运算时间。（1）单链表（2）双链表(3)容量足够大的顺序表（4）带头结点的双循环链表2.若某线性表中最常用的操作是取第I个元素的前驱元素，则采用____（3）__________存储方式最节省运算时间。（1）单链表（2）双链表(3)顺序表（4）带头结点的双循环链表3.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（______A____）。A．98B.99C.50D.484.一个具有n个顶点的无向完全图的边数为（B）。A．n(n+1)/2B．n(n-1)/2C．n(n-1)D．n(n+1)5.折半查找要求查找表中各元素的关键字值必须是____A_______排列。 A.递增或递减B.递增C.递减D.无序6.栈操作的原则是B。A.先进先出B.后进先出C.只能进行插入D.只能进行删除7.设一个栈的输入序列为A，B，C，D，则借助一个栈所得的输出序列不可能是____（4）___。（1）A，B，C，D（2）D，C，B，A（3）A，C，D，B（4）D，A，B，C8.将下三角矩阵A[1..10，1..10]的所有非0元素以行序为主序存放在首地址为2000的存储区中，每个元素占有4个单元，则元素A[9，5]的首地址为（D）A．2340B．2336C．2164D．21609.串是______（4）_______。（1）      不少于一个字母的序列（2）任意个字母的序列（3）      不少于一个字符的序列（4）有限个字符的序列10. 链表不具有的特点是______（1）______.（1）可随机访问任一元素（2）插入删除不需要移动元素（3）不必事先估计存储空间（4）所需空间与线性表长度成正比11.在有n个结点的哈夫曼树中，其结点总数为____（4）__________。（1）（1）      不确定（2）2n（3）2n+1（4）2n-112.任何一个无向连通图的最小生成树_____（2）______。（1）      只有一棵（2）有一棵或多棵（3）一定有多棵（4）可能不存在13.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为____（1）______。（1）98（2）99（3）50（4）4814.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为____2______。 （1）98（2）99（3）50（4）481.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的双亲编号为____2______。（1）23（2）24（3）25（4）无法确定2.设计一个判别表达式中左右括号是否配对出现的算法，采用（B）数据结构最佳。A．线性表的顺序存储结构B．栈C．队列D．线性表的链式存储结构3.下列序列中，______（1）______ 是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。（1）[da,ax,eb,de,bb]ff[ha,gc](2)[cd,eb,ax,da]ff[ha,gc,bb](3)[gc,ax,eb,cd,bb]ff[da,ha](4)[ax,bb,cd,da]ff[eb,gc,ha]4.用n个键值构造一棵二叉排序树，最低高度为___（4）_________。（1）n/2(2)n1/2(3)NLOG2N(4)[LOG2N]+15.折半查找要求查找表中各元素的关键字值必须是___1________排列。（1）      递增或递减（2）递增（3）递减（4）无序6.对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为_____（3）____的结点开始。（1）100（2）12（3）60（4）157.快速排序的记录移动次数（C）比较次数，其总执行时间为0（NLOG2N）A．大于B．大于等于C．小于等于D．小于8.3个结点可构成（D）个不同形态的二叉树。A．2B．3C．4D．59.对有n个记录的有序表采用二分查找，其平均查找长度的量级为（A）A．O（LOG2N）B．O（NLOG2N）C．O（N）D．O（N2）10.对有n个记录的表按记录键值有序的顺序建立二叉排序树，在这种情况下，其平均查找长度的量级为（C）A．O（LOG2N）B．O（NLOG2N）C．O（N）D．O（N2）11.设矩阵A[1..8,1..8]是一对称矩阵，若每个矩阵元素占3个单元，将其上三角部分按行序为主序存放在数组B中，B的首址为1000，则矩阵元素A[6，7]的地址为（B）A．1031B．1093C．1096D．103212.链表适用于顺序查找，但在链表中进行（D）操作的效率比在顺序存储结构中进行同样操作的效率高。A．顺序查找B．二分法查找C．快速查找D．插入13.散列法中的冲突指的是（C）。A．两个元素具有相同的序号B．两个元素的键值不同，而其它属性相同C．不同键值的元素对应于相同的存储地址D．数据元素过多14.如果以链表作为栈的存储结构，则退栈操作时（C）A．必须判断栈是否满B．对栈不作任何判断C．必须判断栈是否空D．判断栈元素的类型15.设数组A[0..M]作为循环队列SQ的存储空间，front为队头指针，rear为对尾指针，则执行出队操作的语句为（D）A．front=front+1B．front=(front+1)%mC．rear=rear+1D．rear=(rear+1)%m16.深度为6的二叉树至多有（D）个结点 A．64B．32C．31D．631.设高度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（C）A．K+1B．2KC．2K-1D．2K+12.堆的存储表示（A）A．顺序存储B.静态链接存储C.动态链接存储D.不一定3.若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用(A)遍历方法最合适。A．前序B．中序C．后序D．按层次4.利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行(A)元素间的比较。A．4次B．5次C.7次D．10次5.下面给出的四种排序法中(D)排序法是不稳定性排序法。A．插入B．冒泡C．二路归并D．堆积6.下面B方法可以判断出一个有向图中是否有环（回路）？A.深度优先遍历B.拓朴排序C.求最短路径D.求关键路径7..若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为(D)A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构8.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为(A)A.n-i+1B.n-iC.iD.i-19..对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为(C)A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表10..为查找某一特定单词在文本中出现的位置，可应用的串运算是(D)A.插入B.删除C.串联接D.子串定位11.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到(A)A.P=″SCIENCE″B.P=″STUDY″C.S=″SCIENCE″D.S=″STUDY″12.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为(B)A.356B.358C.360D.36213.如右图所示广义表是一种(C)A.线性表B.纯表C.结点共享表D.递归表 1.下列陈述中正确的是(D)A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分2.n个顶点的有向完全图中含有向边的数目最多为(D)A.n-1B.nC.n(n-1)/2D.n(n-1)3.已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为(A)A.adbefcB.adcefbC.adcbfeD.adefbc4..在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(C)A.快速排序B.堆排序C.归并排序D.基数排序5.不可能生成右图所示二叉排序树的关键字序列是(A)A.45312B.42531C.45213D.423156.ALV树是一种平衡的二叉排序树，树中任一结点的(B)A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度7.在VSAM文件的控制区间中，记录的存储方式为()A.无序顺序B.有序顺序C.无序链接D.有序链接二、判断题(判断下列各题是否正确，若正确在括号内打“√”，错误的打；1．如果两个串含有相同的字符，则这两个串相等。（N）2．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。(N)，3．在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块元素个数有关。（Y）4．在顺序表中取出第i个元素所花费的时间与i成正比。（N）5．在栈满情况下不能作进栈运算，否则产生“上溢”。（Y）6．二路归并排序的核心操作是将两个有序序列归并为一个有序序列，(Y)7．对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。（N） 8．二叉排序树或是一棵空二叉树，或是具有下列性质的二叉树；若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。（N）9．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的(N)。10．一个有向图的邻接表和逆邻接表中表结点的个数一定相等（Y）①（101，88，46，70，34，39，45，58，66，10）是堆（Y）；②将一棵树转换成二叉树后，根结点没有左子树（N）；③用二叉树的前序遍历和中序遍历可以导出树的后序遍历（Y）；④即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同(N)；⑤哈夫曼树是带权路径长度最短的二叉树，路径上权值较大的结点离很较近（Y）。11、表示一个有1000个顶点、1000条边的有向图的邻接矩阵有1000000个矩阵元素，是否稀疏矩阵是12.（N）串长度是指串中不同字符的个数。13.（N）数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等运算。14.（Y）在顺序表中取出第i个元素所花费的时间与i成正比。15.(Y)在栈满的情况下不能作进栈的运算，否则产生“上溢”。16.（Y二路归并排序的核心操作是将两个有序序列归并为一个有序序列。17.（N）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。18.（Y）一个有向图的邻接表和逆邻接表中的结点个数一定相等。19（Y）在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。12（N）叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。21（N）执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。三、填空题1.    在带有头结点的单链表L中，第一个元素结点的指针是___L->next________。2.      在双循环链表中，在指针p所指结点前插入指针s所指的结点，需执行下列语句：s->next=p;s->prior=p->prior;p->prior=s;_s->prior->next_______________=s;3.      设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是___top==0__________，栈为满的条件是________top==maxsize_____________。4.      具有100个结点的完全二叉树的深度为______7__________________。5.      有向图G用邻接矩阵A[1..n,1..n]存储，其第i行的所有元素之和等于顶点i的____出度_______________。6．r指向单链表的最后一个结点，要在最后一个结点之后插入e所指的结点，需执行的三条语句是r->next=s;r=s；r—>next=NULL。7在单链表中，指针p所指结点为最后一个结点的条件是p->next==null8设一个链栈的栈顶指针是ls，栈中结点格式为info;link;栈空的条件是ls==null。如果栈不为空，则退栈操作为p=ls；ls=ls->link；free(p)。9已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有12个叶子结点。 10．图有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和双亲表示法。11．n个顶点的连通图的生成树有n-1条边。12．一个有向图G中若有弧、和，则在图G的拓扑序列中，顶点vi,vjvk的相对位置为i,j,k13．设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序)：冒泡最省时间，快速最费时间。14。下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。typedefstructpnode}intkey；structnode*left，*right；}voidsearchinsert(intx;pnodet)/*t为二叉排序树根结点的指针*/{if(t==null){p=malloc(size);p->key=x;p->left=null;p->right=null;t=p;}elseif(xkey)searchinsert(x,t->left)elsesearchinsert(x,t->right)}15．线性表的循环链表的主要优点是从表中任一结点出发都能访问到所有的结点。而使用双向链表，可根据需要在前后两个方向上方便地进行查找。16．在带有头结点的单链表L中，则需执行下列三条语句：u=L->next；L—>next=u->next；free(u);17．有一个长度为20的有序表采用二分查找方法进行查找，共有4个元素的查找长度为3。18．采用冒泡排序对有n个记录的表A按键值递增排序；若L的初始状态是按键值递增，则排序过程中记录的比较次数为n-1。若A初始状态为递减排列，则记录的交换次数为n(n-1)/219.在无头结点的双链表中，指针p所指结点是第一结点的条件是p->prior==null.20．G为无向图，如果从q的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是连通图。21．如果一个有向图中没有环，则该图的全部结点可以排成一个拓扑序列。22．深度为8(根的层次号为1)的满二叉树有8个叶子结点。23．将一棵有100个结点的完全二叉树按层编号，则编号为49的结Ⅸ，其双亲PARENT(X)的编号为24。24．设有一个链队，结点结构为data;next；front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p);p->data=x;p->next=null;rear->next=p;rear=p;25.在散列法中，元素个数越多，发生冲突的可能性越大。26．在带有头结点的单链表L中，第一个元素结点的指针是L->next。27．在顺序文件中，存取第i个记录，必须先存取第I-1号元素。28．设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是top==0 ，栈为满的条件是top==maxsize29．具有64个结点的完全二叉树的深度为730．有向图G用邻接矩阵A[1..N,1..N]存储，其第I列的所有元素之和等于顶点I的入度。31．在双循环链表中，若要在指针P所指结点前插人指针S所指的结点，则需执行下列语句s->next=p;s->prior=p->prior;p->prior=s;s->prior->next=p;32．对于下图所示二叉树；按前序遍历所得到的结点序列A，B，D，E，H，C，F．33．分别采用堆排序、快速排序、冒泡排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是冒泡排序，最费时间的是快速算法34.对于下面的二叉树，按中序遍历所得到的结点序列为_______________。35.      对下图所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上适当的内容，以说明该算法的执行过程。  155 42  3214 顶点134UV（U，V）代价（2，1）∞（2，3）4（2，4）2{2}{1，3，4}（U，V）代价 （2，3）4    {2，4}{1，3}（U，V）代价（3，1）1        {2，4，3}{1}（U，V）代价            {2，4，3，1}  36、设广义表L＝(（），（）)则head(L)是()；tail(L)是(())；L的长度是2；深度是237、在n个记录的有序顺序表中进行折半查找，最大的比较次数是logn。在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是_S->NEXT->NEXT=P->NEXT_和_P->NEXT=S__。   38．串S=″Iamaworker″的长度是_14_______。假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为__55____。39．在n个结点的线索二叉链表中，有___n+1_个线索指针。40．对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为_48,44,52,63,80,91___。一、应用题1．已知二叉树的后跟序列和中根序列如下，构造出该二叉树。后根序列：ABCDEFG中根序列：ACBGEDF2．有一组关键码序列{8，9，5，3，7，2，1}，分别采用冒泡排序、快速排序、直接选择排序、直接插入排序、二路归并排序方法由小到大进行排序，在下面的选项中请选择各种排序第一趟排序的结果。冒泡排序：E快速排序：A直接选择排序：B直接插入排序：C二路归并：FA．{1，2，5，3，7，8，9}B．{1，9，5，3，7，2，8}C．{9，8，5，3，7，2，1}D．{9，5，3，7，2，1，8}E．{8，5，3，7，2，1，9}F．{8，9，3，5，2，7，1}3．设图G=（V，E），V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6>，<6，5>，<5，4>，<6，4>}，请写出图G中顶点的所有拓扑序列。4．设图G=（V，E），V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6>，<6，5>，<5，4>，<6，4>}，请画出其邻接表，并说明每个顶点的入度和出度。5．对如下所示的二叉树，画出其顺序存储结构。6．已知图G的邻接表如图所示，画出图G的所有连通分量。现有5个结点（A，B，C，D，E），它们的权值分别为{5，10，12，15，30}，在下面的选项中选择一个编号，说明这5个结点的哈夫曼编码。（2）（1）A：1，B：001，C：010，D：011，E：000（2）A：000，B：001，C：010，D：011，E：1（3）A：001，B：011，C：010，D：000，E：1（4）A：000，B：1，C：010，D：011，E：001 1．已知一表为{23，45，24，6，57，45，35}，按表中顺序依次插入初始为空的二叉排序树，要求画出建立的二叉排序树。设有序序列30,18,3,61,14,49，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度。答：二叉排序树: (3分)　平均查找长度=(1+2×2+3×2+4)*1/6=2.5 (2分) 2．对如下所示的交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修路的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。3．设有n个元素的有序表为A，K为一个给定的值，填空完成二分查找算法：binsrch(a,n,k)inta[],k;{intlow,hig,mid;low=0;hig=n;while(low<=hig){mid=(low+hig)/2;if(kn=G1->n;G2->e=G1->e;for(i=0;in;i++){G2->adjlist[i].vertex=G1->vexs[i];G2->adjlist[i].firstedge=(1);}for(i=0;in;i++)for(j=0;jn;j++)if(G1->edges[i][j]weight=(2);p->adjvex=j;p->next=G2->adjlist[i].firstedge;(3);}}(1)NULL(2)G1->edges[i][j](3)G2->adjlist[i].firstedge=p11.阅读下列算法，并回答下列问题： (1)该算法采用何种策略进行排序?插入排序(2)算法中R[n+1]的作用是什么?监视哨Typedefstruct{KeyTypekey;infoTypeotherinfo;}nodeType;typedefnodeTypeSqList［MAXLEN］;voidsort(SqListR,intn){//n小于MAXLEN-1intk;i;for(k=n-1;k>=1;k--)if(R[k].key>R[k+1].key){R[n+1]=R[k];for(i=k+1;R[i].key=hr)h=h1+1;                   2分else  h=hr+1}}四、算法填空和分析1、ListInsert_L(LinkListL,intpos,ElemTypee)//在带头结点的单链表L中第pos个数据元素之前插入数据元素eStatusListInsert_L(LinkListL,intpos,ElemTypee){p=L;j=0;while(p&&jnext;++j;}//寻找第pos-1个结点if(!p||j>pos-1)returnERROR;//pos小于1或者大于表长s=(LinkList)malloc(sizeof(LNode));//生成新结点s->data=e;s->next=p->next;//插入L中p->next=s;returnOK;}2、voidMerge(ElemSR[],ElemTR[],inti,intm,intn){//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]for(j=m+1,k=i;i<=m&&j<=n;++k){//将SR中记录由小到大地并入TRif(SR[i].key<=SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)TR[k..n]=SR[i..m];//将剩余的SR[i..m]复制到TRif(j<=n)TR[k..n]=SR[j..n];//将剩余的SR[j..n]复制到TR}//Merge3、intPartition(ElemR[],intlow,inthigh) {//交换记录子序列R[low..high]中的记录，使枢轴记录到位，并返回//其所在位置，此时，在它之前（后）的记录均不大（小）于它R[0]=R[low];//用子表的第一个记录作枢轴记录pivotkey=R[low].key;//枢轴记录关键字while(low=pivotkey)--high;R[low]=R[high];//将比枢轴记录小的记录移到低端while(lowr[mid].key)low=mid+1;elseif(k==r[mid].key)found=1;elsehigh=mid-1;}if(found==1)return(mid);elsereturn(0);}5、设有一个表头为head的单链表。通过遍历一趟链表，将链表中所有结点按逆序链接。Typedefstructnode{intdata;structnode*next;}pointer;Voidinvert(pointerhead){p=NULL;while(head!=NULL){u=head;head=head->next; u->next=p;p=u;}had=p;}五、编写算法：1、设某单链表L的结点结构如下，单链表L用于存放某人的电话薄，现在由于电话号码从7位升为8位（加60000000），请用C语言编写算法，实现电话薄中所有电话号码从7位升为8位。Typedefstructnode{charname[9];//姓名longdata;//电话号码structnode*next;}pointer;intlength(pointerL){p=L;while(p!=NULL){p->data=p->data+60000000;p=p->next;}}2、设二叉树采用二叉链表表示，编写算法，将二叉树中所有结点的左右子树相互交换。voidBitree_Revolute(BitreeT)//交换所有结点的左右子树{  T->lchild<->T->rchild;//交换左右子树  if(T->lchild)Bitree_Revolute(T->lchild);  if(T->rchild)Bitree_Revolute(T->rchild);//左右子树再分别交换各自的左右子树}设计题：1．设某单链表L的结点结构为data,next,试画出该链表的结构图，并用类C语言编写算法，判断该链表的元素是否是递增的。2．设某单链表L的结点结构为data,next,试画出该链表的结构图，并用类C语言编写算法，统计该链表的长度。3．设一棵二叉树以二叉链表作为存储结构，结点结构为lch,data,rch，其中data域中存放一个字符，设计一个算法按前根遍历顺序打印出data域为数字的字符。4．设BT为二叉排序树，t指向根结点，每个结点的结构为lch,key,rch，试用类C语言写出算法，用来输出二叉排序树中最小的键值。5．设一棵二叉树以二叉链表为存储结构，结点结构为lch,data,rch ，设计一个算法求此二叉树上度为2的结点数。1．设一个环上有若干个整数，若采用单循环链表L存储该环，L的存储结构为：data,next，试画出链表L的结构图，并编写算法判断环上任意两个相邻的键值之差的绝对值是否不超过2。7.假设二叉树T采用如下定义的存储结构：typedefstructnode{DataTypedata;structnode*lchild,*rchild;}PBinTree;其中，结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针。请编写一个递归算法，将该存储结构中各结点的lchild和rchild域的值进行交换。2001年10月数据结构试题及答案一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1．算法指的是（）A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列2．线性表采用链式存储时，结点的存储地址（）A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）A．O（1）B．O（n）C．O（m）D．O（m+n）4．由两个栈共享一个向量空间的好处是：（）A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率5．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1B．front=(front+1)%(m-1)C．front=(front-1)%mD．front=(front+1)%m6．如下陈述中正确的是（）A．串是一种特殊的线性表B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串 7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（）A．O（）B．O（n）C．O（n2）D．O（n3）8．一个非空广义表的表头（）A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表02335对应的稀疏矩阵是（）10．在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为()A．4B．5C．6D．711．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()A．eB．2eC．n2－eD．n2－2e12．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是()A．O(n)B．O(e)C．O(n+e)D．O(n*e)13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（）A．选择排序B．希尔排序C．归并排序D．快速排序14．适于对动态查找表进行高效率查找的组织结构是（）A．有序表B．分块有序表C．三叉排序树D．线性链表15．不定长文件是指（）A．文件的长度不固定B．记录的长度不固定C．字段的长度不固定D．关键字项的长度不固定第二部分非选择题（共70分）二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的无关，是独立于计算机的。17．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=。18．栈顶的位置是随着操作而变化的。19．在串S=“structure”中，以t为首字符的子串有个。20．假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B�存储矩阵中第1个元素a1,1,则B中存放的元素是。 21．已知一棵完全二叉树中共有768结点，则该树中共有个叶子结点。22．已知一个图的广度优先生成树如右图所示，则与此相应的广度优先遍历序列为。23．在单链表上难以实现的排序方法有和。24．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为。25．多重表文件和倒排文件都归属于文件。三、解答题（本大题共4小题，每小题5分，共20分）26．画出下列广义表的共享结构图形表示P=（（（z）,(x,y)）,((x,y),x),(z)）27．请画出与下列二叉树对应的森林。28．已知一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示(1)画出该图的图形；（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。29．已知一个散列表如下图所示：35203348590123456789101112其散列函数为h(key)=key%13,处理冲突的方法为双重散列法，探查序列为：hi=(h(key)+*h1(key))%m=0,1,…，m－1其中h1(key)=key%11+1回答下列问题：（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？（2）该散列表在等概率查找时查找成功的平均查找长度为多少？四、算法阅读题（本大题共4小题，每小题5分，共20分）30．下列算法的功能是比较两个链串的大小，其返回值为：comstr(s1,s2)=请在空白处填入适当的内容。intcomstr(LinkStrings1,LinkStrings2){//s1和s2为两个链串的头指针while(s1&&s2){if(s1－>datedate)return－1； if(s1－>date>s2－>date)return1；①；②；}if(③)return－1；if(④)return1；⑤；}①②③④⑤31．阅读下面的算法LinkListmynote(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）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。32．假设两个队列共享一个循环向量空间（参见右下图），其类型Queue2定义如下：typedefstruct{DateTypedata[MaxSize]；intfront,rear；}Queue2；对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。intEnQueue(Queue2*Q,inti,DateTypex){//若第i个队列不满，则元素x入队列，并返回1；否则返回0if(i<0||i>1)return0；if(Q－>rear[i]==Q－>front[①]return0；Q－>data[②]=x；Q－>rear[i]=[③];return1；} ①②③33．已知二叉树的存储结构为二叉链表，阅读下面算法。typedefstructnode{DateTypedata；Structnode*next；}ListNode；typedefListNode*LinkList；LinkListLeafhead=NULL；VoidInorder(BinTreeT){LinkLists；If(T){Inorder(T－>lchild)；If((!T－>lchild)&&(!T－>rchild)){s=(ListNode*)malloc(sizeof(ListNode))；s－>data=T－>data；s－>next=Leafhead；Leafhead=s；}Inorder(T－>rchild)；}}对于如下所示的二叉树（1）画出执行上述算法后所建立的结构；（2）说明该算法的功能。五、算法设计题（本题共10分）34．阅读下列函数arrange()intarrange(inta&#;,int1,inth,intx){//1和h分别为数据区的下界和上界inti,j,t；i=1；j=h；while(i=x)j--；while(i=x)i++；if(inext－>next18．进栈和退栈19．1220．a4,821．38422．abefcdg23．快速排序、堆排序、希尔排序24．２25.多关键字三、解答题（本大题共4小题，每小题5分，共20分）26．图1图227．28．该图的图形为：深度优先遍历序列为：abdce广度优先遍历序列为：abedc29．（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１；（２）平均查找长度四、算法阅读题（本大题共4小题，每小题5分，共20分）30．①S1=S1－>next②s2=s2－>next③s2(或s2!=NULL或s2&&!s1)④s1(或s1!=NULL或s1&&!s2)⑤return031.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,…,an,a1）32.①(i＋1)%2(或1－i)②Q－>rear[i]③(Q－>rear[i]＋)%Maxsize 33.(1)LeafheadFHGD∧（2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。五、算法设计题（本题共10分）34．（1）该函数的功能是：调整整数数组a&#;中的元素并返回分界值i，使所有=YThenBeginM:=N;P:=A[N]EndElse BeginM:=Z;P:=YEndEndEnd;BeginReadln(N);ForI:=1ToNDoRead(A[I]);Readln;L:=N;ForI:=1ToLDoBeginK=P9A,J,N);A[J]:=A[N];A[N]:=K;N:=N-1End;ForI;=1ToLDoWrite(A[I]:3);Writeln;End;输入数据为： 8618435279（10分）已知二叉树用下面的顺序结构存储，写出中序遍历该二叉树的算法。TypeArray[1..maxn]ofRecordData:Char;//存结点值Lc,Rc:Integer//左、右孩子下标，0表示无左、右孩子如树T=A（B（D，E），C（#，F（H，I）））存储如表1所示：表1树T的存储             1     2    3     4    5    6     7    8    9ABCDEFGHI24000800035607900010（10分）试写出以带头结点单链表为存储结构实现简单选择排序的算法。东北大学2000硕士入学数据结构试题1（20分）简要回答下列问题①（3分） 内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。②（5分）假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。③（4分）一棵共有n个结点的树，其中所有分枝结点的度均为k，求该树中叶子结点的子数。④（4分）图1表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。图1题1.4图⑤（4分）在起泡（汽泡）排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。快速排序过程中有没有这种现象？2（15分）设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：①找出最小值结点，且打印该数值；②若该数值是奇数，则将其与直接后继结点的数值交换；③若该数值是偶数，则将其直接后继结点删除；3（14分） 解答下列问题：①(4分）将算术表达式((a+b)+c*(d+e)+f)*(g+h)转化为二叉树；②(10分）假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。4（21）解答下列问题：①（5分）画出有向图的十字链表存储结构中头结点和表结点的结点结构。②(4分）下面哪一个方法可以判断出一个有向图中是否有环（回路）？(1)深度优先遍历(2)拓朴排序(3)求最短路径(4)求关键路径③(12分）假设一个有向图g已经以十字链表形式存储在内中，试写一个判断该有向图中是否有环（回路）的算法。5（15分）写出删除二叉排序树bt中值为x的结点的算法（二叉排序树以二叉链表形式存储，删除后仍然保持二叉排序性质）。6（15分）设有大小不等的n个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内，每个数据占一个存储单元，数据组的首地址由数组s给出（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。 图2题6图02年北京文考“数据结构”试题一、判断题(每小题1分，共15分)1.程序就是算法，但算法不一定是程序。()2.线性表只能采用顺序存储结构或者链式存储结构。()3.线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。()4.除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。()5.稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。()6.不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。()7.确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。()8.深度为h的非空二叉树的第i层最多有2i-1个结点。()9.满二叉树就是完全二叉树。()10.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。()11.非空二叉排序树的任意一棵子树也是二叉排序树。()12.对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。()13.若有向图G=(V,E)的拓扑序列不唯一，则图中必须有两条弧和。()14.散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。()15.序列初始为逆序时，泡排序法所进行的元素之间的比较次数最多。()二、单项选择题(每小题2分，共20分)1.算法分析的目的是()A.研究算法的输入与输出之间的关系B.找出数据结构的合理性C.分析算法的效率以求改进算法D.分析算法的可读性与可移植性 2.在由list所指的非空线性链表中删除由p指的链结点的下一个链结点的过程是依次执行q←link(p),____________,callRET(q)。()A.link(p)←qB.link(q)←pC.link(q)←link(p)D.link(p)←link(q)3.依次在初始为空的队列中插入元素为a,b,c,d以后，紧接着作了两次删除操作，此时的队头元素是()A.aB.bC.cD.d4.若某堆栈的输入序列为1，2，3，…，n-1，n，输出序列的第1个元素为n，则第个输出元素为()A.n-i+1B.n-1C.iD.哪个元素无所谓5.设计递归问题的非递归算法一般需要用到__________机制。()A.数组B.堆栈C.队列D.二叉树6.已知非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即ABC□DEF□□G□□H□□该二叉树的中序列遍历序列为()A.G,D,B,A,F,H.C,EB.G,B,D,A,F,H,C,EC.B,D,G,A,F,H,C,ED.B,G,D,A,F,H,C,E7.在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，那么，该树有__________个叶结点。()A.4B.5C.6D.78.已知有向图G=，其中V＝{v1,v2,v3,v4,v5,v6},E＝{,，，，，，，}，G的拓扑序列是______。()A.v3,v1,v4,v5,v2,v6B.v3,v4,v1,v5,v2,v6C.v1,v3,v4,v5,v2,v6D.v1,v4,v3,v5,v2,v69.在初始为空的散列表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN),散列函数为H(k)=iMOD7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为[0:6]，采用线性再散列法处理冲突。插入后的散列表应该如__________所示。()A.0123456THUTUEWEDFRISUNSATMONB.0123456TUETHUWEDFRISUNSATMONC.0123456TUETHUWEDFRISATSUNMOND.0123456TUETHUWEDSUNSATFRIMON10.对数据元素序列(49，72，68，13，38，50，97，27)进行排序，前三趟排序结束时的结果依次为：第一趟：13，72，68，49，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；该排序采用的方法是()A.插入排序法B.选择排序法C.泡排序法D.堆积排序法 三、填空题(每小题2分，共20分)1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的数据元素前，需要先依次移动_________个数据元素。2.在非空双向循环链表中由q所指的那个链结点后插入一个由p指的链结点的动作对应的语句依次为：llink(p)←q，rlink(p)←rlink(q)，rlink(q)←p,______________。(空白处为一条赋值语句)3.已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)=________________。4.具有2000个结点的二叉树，其深度至少为_________。5.具有n0个叶结点的哈夫曼树(Huffman)的分支总数为_________。6.若连通图的顶点个数为n，则该图的生成树的边数为_________。7.在序列(2，5，8，11，15，16，22，24，27，35，40)中采用折半查找(二分查找)方法查找元素24，需要进行_________次元素之间的比较。8.索引文件中的索引表是_________提供的，并且索引表的表项按_________有序列排列。9.对具有n个元素的任意序列采用插入排序法进行排序，整个排序过程中要进行_________次元素之间的比较。10.插入排序法、选择排序法、拓扑排序法与归并排序法中，_________不是内排序方法。四、问题求解题(每小题10分，共20分)1.已知一带权连通图采用邻接矩阵存储方法，并且邻接矩阵采用三元组表表示，其中，第一个三元组(5，5，16)分别表示邻接矩阵的行数、列数字与非零元素的个数，从第二个三元组开始，依次按行序为主序的次序分别给出16个非零元素，它们依次为(1，2，7)，(1，3，6)，(1，4，9)，(2，1，7)，(2，3，8)，(2，4，4)，(2，5，4)，(3，1，6)，(3，2，8)，(3，4，6)，(4，1，9)，(4，2，4)，(4，3，6)，(4，5，2)，(5，2，4)，(5，4，2)；请分别画出该带权连通图的两棵最小生成树。2.已知散列范围为[0：9]，散列函数为H(key)=keyMOD9，处理冲突的方法为链地址法，请画出依次插入关键字8,10,14,19,21,23,28,32以后的哈希表。五、算法题(本题共25分)1.(10分)下面的算法将一维数组A[1:n]中所有奇数移到数组的左边，所有偶数字移到数组的右边。请在算法的空白处填入适当内容，使之能够正常工作。(提示：用xMODy表示求x除以y的余数)procedureEXCHANGE(A,n)i←1j←nrepeatwhile_________do//当A[i]为奇数时//i←i+1endwhile_________do//当A[i]为偶数时//j←j-1endif(i[temp←A[i] A{i}←A[j]______________]//交换A[i]与A[j]的位置//elseexituntil__________end2.(15分)已知非空线性链表的链结点的构造为date|link，第一个链结点的指针为list，下面的算法在链表的第i个链结点(设i>0)前插入一个数据信息为item的新结点。请在算法的空白处填入适当内容，使之能够正常工作。procedureINSERT(list,i,item)if(i=1)then[callGETNODE(p)//申请一个新的链结点//date(p)←itemlink(p)←list　________________//将新结点插在第1个链结点前//else[q←listforj←1to___________dor←qq←link(q)if__________then[callERROR(""i"超过链表的长度!")return]end//r与q分别指向第i-1个与第i个链结点//callGETNODE(p)//申请一个新的链结点空间//data(p)←itemlink(p)←q__________________]//将新结点插在第i个结点前//end'