石大070109数据结构期末复习题.docx

《石大070109数据结构期末复习题.docx》由会员分享，可在线阅读，更多相关《石大070109数据结构期末复习题.docx（13页珍藏版）》请在课桌文档上搜索。

1、数据结构课程综合复习资料一、单选题1带头结点的双向链表中，Pcor指针指向当前结点的前驱，NeXt指向当前结点的后继。在指针P指向的结点前插入指针S指向的结点，以下操作不正确的是()。A.s-Prior=p-Prior;p-Prior=sjp-Prior-Next=s;s-Next=pB.s-Next=p;s-Prior=p-Prior;p-Prior-Next=s;p-Prior=sC.s-Prior=p-Prior;sNext=p;p-Prior-Next=sjpPrior=sD.s-Prior=p-Prior;p-Prior-Next=s;s-Next=p;p-Prior=s答案：A2.

2、采用BF算法在主串aabaaacaacbbb中查找子串aaacaacb的查找次数为()。A.13B.14C.15D.16答案：B3.一棵具有n个结点的完全二叉树的树高度(深度)是()。A.LlognJB.logn+1C.logz(zrH)1D,Iogn-I答案：C4.计算以下程序的时间复杂度为()。SUin=O;for(i=l;i=n;:i+)for(j=l;j=n;j+)cij=0;for(k=l;k=t;k+-cij+=aikkj;A.O1)B.O(n)C.O(/J)D.O(/)答案：D5.使用C语言定义的二维数组DataTypeAmn,每个数据元素占K个存储单元，二维数组中任意元素aij

3、的存储位置可由O式确定。A.Loci,j=Am,n+(n+l)*i+j*kB.Loci,j=loc0,O+(m+n)*i+j*kC.Loci,j=loc0,O+n*i+j*kD.Loci,j=(n+l)*i+j*k答案：C6.以下排序算法的平均时间复杂度不是(Knlogzn)的排序方法是()。A.堆排序B.直接插入排序C.二路归并排序D.快速排序答案：B7.下程序段的时间复杂度为()。for(i=2;i=n;:+!)forj=2;jnext=p-next；p-next=qB.p-next=q-next；q=pC.q-next=p-next；p-next=qD.p-next=q-next；q-n

4、ext=p答案：D9.设矩阵A是一对称矩阵（aij=aji,K=i,j=8）,若每个矩阵元素占3个单元，将其上三角部分（包括对角线）按行序为主序存放在数组B中，B的首地址为IOo0,则矩阵元素a67的地址为（）。A.1031B.1093C.1096D.1032答案：B10如图所示，（）是该图的拓扑排序。B.1,3,2,4,5C.1,2,4,3,5D.1,2,3,5,4答案:A11.在具有n个结点的二叉树（二叉链表表示）中，树中的链域数为（）。A.n-1B,n+1C.2nlD.2n+l答案：B12.哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行

5、O次探测。A.kB.k-1C.k(k+l)2D.l+k（k-l）2答案：C13.关于算法，下面描述正确的是（）。A.时间复杂度就是算法的执行时间B.算法必须有输入量和输出量C.算法就是程序D.时间复杂度仅反映时间关于问题规模的增长率答案：D14.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A.24B.48C.72D.51答案：D15.以下说法正确的是（）。A.平衡二叉树一定是满二叉树B.虽然关键字序列的顺序不一样，但依次生成的二叉排序树是一样的C.在二叉排序树上插入新的结点时，不必移动其他结点，只需改动某个结点的指针，由空变为非空即可D.在二叉排序树上删除

6、一个结点时，不必移动其他结点，只要将该结点的父结点的相应的指针域置空即可答案：C16.希尔排序属于（）。A.插入排序B.选择排序C.归并排序D.交换排序答案：A17.对于一组结点，从空二叉树开始，把它们插入到二叉排序树中，就建立了一棵二叉排序树。这时，整个二叉排序树的形状取决于OoA.结点的输入顺序B.结点的存储结构C.结点的取值范围D.计算机的硬件答案:A二、填空题1.字符串sl=Iamastudent!（单词与单词之间一个空格）,s2=student，则字符串SI的长度为15,第一个字符的起始位置为1,串s2是串Sl的一个子串，串s2在Sl中的位置为（）。答案：82.求下列程序的时间复杂度

7、，并用大O表示方法表示（）。for（i=l;i=n;+i）for（j=l;jlink;e=p-info;()答案；free(p)11.以二分查找方法查找一个线性表时，此线性表必须是顺序存储的有序表，二分查找的时间复杂度为()。答案：0(log2)12.直接插入排序的时间复杂性为()。答案：0(n2)13.棵二叉排序树是平衡的，当且仅当每个结点的左右子树的高度至多相差为1,AVL树的平均查找长度为()。答案：0(log2n)14.用于查找的数据元素集合称为查找表，用0表示时间复杂度，那么顺序查找的时间复杂度为。（n）,二分查找的时间复杂度为（）。答案：o（log；）15.n个元素的序列（K1,K

8、2,.,Kn,当且仅当满足KiK2i和KiMK2i+l时称之为最小堆。在一个最小堆中，堆顶结点的值是所有结点的值中O的。答案：最小16.用堆栈求中缀表达式a+b*c/d+e*f的后缀表达式，求出的后缀表达式为（）。答案：（abc*d+ef*+）17.一般情况下，当待排序序列关键字是随机情况时，快速分类是所有数量级0（nlogn）的排序方法中最好的。对快速排序来讲，其最好情况下的时间复杂度是O（nlogn）,其最坏情况下的时间复杂度是（）。答案：OG）18.数据在计算机中的存储只有两种形式，一种是数据元素逐个连续存放，通过物理相邻来确定关系，这种存储方式称为顺序存储；另一种是数据元素任意存放，通

9、过存储地址确定关系,这种存储方式称为（）存储。答案：链式19.字符串中的数据元素为（）。答案:字符20.串中所含字符的个数称为该串的（）。答案:长度21.在邻接表中，无向图中顶点Vi的度恰为（）。答案:Vi顶点对应的链表长度22.通常采用顺序存储结构来存放数组。对二维数组可有两种存储方法：一种是以行为主序的存储方式，另一种是以（）为主序的存储方式。答案：列23.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是稳定的，否则称为O的。答案:不稳定24.一个串中任意个连续字符组成的序列称为该串的（）串，该串称为主串。答案：子25.遍历图的基本方

10、法有广度优先搜索和()优先搜索两种。答案:深度三、综合题1.以下运算实现在链栈上的退栈，请在处用适当语句予以填充。intPop(LstackTp*ls,DataType*x)LstackTp*p;if(ls!三NULL)p=ls;*x=;Treturn(1)；elsereturn(0);答案：p-data,ls=ls-nextfree(p)2.以下为求带头结点的单链表表长的算法，分析算法，在一处填上正确的语句。intlength_lklist(Iklisthead)/*求单链表head的长度*/intj=0-while()J11：return(j)：答案：Iklistp=head;p-next

11、!=NULLp-next;3.己知一个无向图的邻接表如图所示，画出这个图。根据邻接表，以Vl为出发点，对图进行广度优先搜索和深度优先搜索，写出各自访问序列。广度优先搜索序列：V1-V2-V4-V5-V3深度优先搜索序列：V1-V2-V5-V3-V44.将记录的关键字序列119,11,213,104,55,80,84,107,68,31,60,77采用哈希表存放，哈希函数采用H(key)=key%10,处理冲突采用线性探测再散列的方法。请构造此哈希表a5.有待排序的元素序列68,82,72,10,70,23,95,16,26,45,请用快速排序的方法对上述序列排序，给出每一趟排序后的结果。答案:

12、第一趟:45,26,16,10,23,68,95,70,72s82第二趟：23,26,16,10,48,68,82,70,72,95第三趟：10,16,23,26,48,68,72,70,82,95第四趟：10,16,23,26,48,68,70,72,82,956.图的邻接矩阵和邻接表存储结构定义如下：邻接矩阵：typedefstructintvexnum,arcnum;charvexs100;intarcs100,100MGraph;邻接表：typedefstructarcptr(intadjvex;邻接点的存储位置structarcptr*nextarc;ArcNode;下邻接点type

13、defstructvexnodechardata;数据元素ArcNode*firstarc;Vnode;第一个邻接点typedefstructintvexnum,arcnum;图的顶点个数Vnodevertices100;)ALGraph;给出将无向图的邻接矩阵转换成邻接表的算法。答案：voidMatToList(MGraphg,ALGraph*G)/*将邻接矩阵g转换成邻接表G*/inti,j,n=g.vexnum;ArcNode*p;*n为顶点数*/G=(ALGraph*)malloc(sizeof(ALGraph);for(i=0;iverticesiJ.data=g.vexsi;G-v

14、erticesi.fIrstarc=NULL;for(i=0;i=0;j)if(g.arcsij!=0)p=(ArcNode*)malIoc(siZeof(ArcNode)：*创建结点*p*/p-adjvex=j;p-nextarc=G-adjlisti.firstarc;/*将*p链到链表上*/Gverticesi.firstarc=p;G-vexnum=n;G-arcnum=g.arcnum;7.二叉链表存储结构如下所示，编写算法求二叉树的深度。typedefstructBINTREENODE(ElemTypedata;StrUCtBINTREENODElchild,rchild;BinN

15、ode,*BinTree答案：intBinTreeDepth(BinTreeT)求二叉树的深度If(T=NULL)return0;ElseI=BinTreeDepth(T-lchiId);r=BinTreeDepth(T-rchiId);return(lr?!:r)+1);/BinTreeDepth8.待排记录序列的数据元素类型定义如下：typedefstructintkey：/关键字项InfoTypeOtherinfo;/其它数据项RcdType;RcdTypeRn;给出冒泡排序的排序算法。答案：voidBubbleSort(intn)inti,m,n,temp;for(i=l;ii：j)i

16、f(Rj-1.keyRj.key)temp=Rj.key;Rjkey=Rj-l.key;Rj-1.key=temp;m=1：是否进行过交换的标志/ififCm=O)break;/for/BubbleSort9.有待排序的元素序列(72,13,70,23,95,16,5,68,26,45,请用快速排序的方法对上述序列排序，给出每一趟排序后的结果。答案:第一趟排序结果：451326231662689570第二趟排序结果：161326234562689570第三趟排序结果：131626234562687095第四趟排序结果：13162326456268709510.给出求带头结点的单链表的长度的算法。答案：typedefstructInodeelemtypedata;structInode*next;Inodes*linklist;intLength(linklistla)i=0;p=la;while(p-next!=NULL)i=i+l;p=p-nextreturni;