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

数据结构课程综合复习资料一、单选题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;s>Next=p;p->Prior->Next=sjp>Prior=sD.s->Prior=p->Prior;p->Prior->Next=s;s->Next=p;p->Prior=s答案：A2.采用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.O¢1)B.O(n)C.O(/J)D.O(/)答案：D5.使用C语言定义的二维数组DataTypeAmn,每个数据元素占K个存储单元，二维数组中任意元素aij的存储位置可由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;j<=i-l;+j)+x;ai,j=x;A.OB.O(n)C.O(/)D.O()答案:C8.在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针P指向的结点，则执行()。A.q->next=p->next；p->next=qB.p->next=q->next；q=pC.q->next=p->next；p->next=qD.p->next=q->next；q->next=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个关键字对应的记录存入哈希表中，至少要进行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.在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应的指针域置空即可答案：C16.希尔排序属于（）。A.插入排序B.选择排序C.归并排序D.交换排序答案：A17.对于一组结点，从空二叉树开始，把它们插入到二叉排序树中，就建立了一棵二叉排序树。这时，整个二叉排序树的形状取决于OoA.结点的输入顺序B.结点的存储结构C.结点的取值范围D.计算机的硬件答案:A二、填空题1.字符串sl="Iamastudent!"（单词与单词之间一个空格）,s2="student"，则字符串SI的长度为15,第一个字符的起始位置为1,串s2是串Sl的一个子串，串s2在Sl中的位置为（）。答案：82.求下列程序的时间复杂度，并用大O表示方法表示（）。for（i=l;i<=n;+i）for（j=l;j<=i;+j）+x;aij=x;答案：Q（案3.含零个字符的串称为（）串，用0表示。答案：空4.在32位计算机中，如下图所示的字符串存储结构中，其存储密度为（）。P答案：20%5.下列二叉树的先序遍历序列为（）。答案：abdgcef6.下列二叉树的中遍历序列为（）。答案：dgbaecf7.下列二叉树的后遍历序列为()。答案：gdbefca8.下列二叉树的层序遍历序列为()。答案；abcdefg9.深度为k的二叉树至多有O个结点(kNl)。答案：2k-l10.设一个链栈的栈顶指针是1s,栈中结点格式为IinfOllink!,栈空的条件是Is=MJLL;如果栈不为空，则退栈操作为P=ls；ls=ls->link;e=p->info;()答案；free(p)11.以二分查找方法查找一个线性表时，此线性表必须是顺序存储的有序表，二分查找的时间复杂度为()。答案：0(log2)12.直接插入排序的时间复杂性为()。答案：0(n2)13.棵二叉排序树是平衡的，当且仅当每个结点的左右子树的高度至多相差为1,AVL树的平均查找长度为()。答案：0(log2n)14.用于查找的数据元素集合称为查找表，用0表示时间复杂度，那么顺序查找的时间复杂度为。（n）,二分查找的时间复杂度为（）。答案：o（log；）15.n个元素的序列（K1,K2,.,Kn,当且仅当满足KiK2i和KiMK2i+l时称之为最小堆。在一个最小堆中，堆顶结点的值是所有结点的值中O的。答案：最小16.用堆栈求中缀表达式a+b*c/d+e*f的后缀表达式，求出的后缀表达式为（）。答案：（abc*d+ef*+）17.一般情况下，当待排序序列关键字是随机情况时，快速分类是所有数量级0（nlogn）的排序方法中最好的。对快速排序来讲，其最好情况下的时间复杂度是O（nlogn）,其最坏情况下的时间复杂度是（）。答案：OG）18.数据在计算机中的存储只有两种形式，一种是数据元素逐个连续存放，通过物理相邻来确定关系，这种存储方式称为顺序存储；另一种是数据元素任意存放，通过存储地址确定关系,这种存储方式称为（）存储。答案：链式19.字符串中的数据元素为（）。答案:字符20.串中所含字符的个数称为该串的（）。答案:长度21.在邻接表中，无向图中顶点Vi的度恰为（）。答案:Vi顶点对应的链表长度22.通常采用顺序存储结构来存放数组。对二维数组可有两种存储方法：一种是以行为主序的存储方式，另一种是以（）为主序的存储方式。答案：列23.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是稳定的，否则称为O的。答案:不稳定24.一个串中任意个连续字符组成的序列称为该串的（）串，该串称为主串。答案：子25.遍历图的基本方法有广度优先搜索和()优先搜索两种。答案:深度三、综合题1.以下运算实现在链栈上的退栈，请在处用适当语句予以填充。intPop(LstackTp*ls,DataType*x)LstackTp*p;if(ls!三NULL)p=ls;*x=;Treturn(1)；elsereturn(0);答案：p->data,ls=ls->next>free(p)2.以下为求带头结点的单链表表长的算法，分析算法，在一处填上正确的语句。intlength_lklist(Iklisthead)/*求单链表head的长度*/intj=0-while()J11：return(j)：答案：Iklistp=head;p->next!=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,请用快速排序的方法对上述序列排序，给出每一趟排序后的结果。答案:第一趟: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;下邻接点typedefstructvexnodechardata;数据元素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;i<n;i+)/*给所有头结点的指针域置初值*/G>verticesiJ.data=g.vexsi;G->verticesi.fIrstarc=NULL;for(i=0;i<n;i+)/*检查邻接矩阵中每个元素*/for(j=n-l;j>=0;j)if(g.arcsij!=0)p=(ArcNode*)malIoc(siZeof(ArcNode)：*创建结点*p*/p->adjvex=j;p->nextarc=G->adjlisti.firstarc;/*将*p链到链表上*/G>verticesi.firstarc=p;G->vexnum=n;G->arcnum=g.arcnum;7.二叉链表存储结构如下所示，编写算法求二叉树的深度。typedefstructBINTREENODE(ElemTypedata;StrUCtBINTREENODElchild,rchild;BinNode,*BinTree答案：intBinTreeDepth(BinTreeT)求二叉树的深度If(T=NULL)return0;ElseI=BinTreeDepth(T->lchiId);r=BinTreeDepth(T->rchiId);return(l>r?!:r)+1);/BinTreeDepth8.待排记录序列的数据元素类型定义如下：typedefstructintkey：/关键字项InfoTypeOtherinfo;/其它数据项RcdType;RcdTypeRn;给出冒泡排序的排序算法。答案：voidBubbleSort(intn)inti,m,n,temp;for(i=l;i<n;i+)m=0;for(j=n;j>i：j)if(Rj-1.key>Rj.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;