中国石油大学期末考试复习题-070109数据结构-18

《数据结构》综合复习资料一、填空题1、数据结构是（）。2、数据结构的四种基本形式为集合、（）、（）和（）。3、线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接前驱外，其他结点有且仅有一个直接（）；除终端结点没有直接（）外，其它结点有且仅有一个直接（）。4、堆栈的特点是（），队列的特点是（），字符串中的数据元素为（）。5、字符串s1=“Iamastudent！”(单词与单词之间一个空格),s2=“student”,则字符串s1的长度为（），串s2是串s1的一个（）串，串s2在s1中的位置为（）。6、KMP算法的特点：效率较（）；（）回溯，对主串仅需要从头到尾扫描（）遍，可以边读入边匹配。7、广义表（（a），（（b），c），（（（d））））的长度为（），表头为（），表尾为（）。8、ADT称为抽象数据类型，它是指（）。9、求下列程序的时间复杂度，并用大O表示方法表示（）。for(i=1;i<=n;++i)for(j=1;j<=i;++j){++x;a[i][j]=x;}10、以下运算实现在链栈上的退栈操作，请在_____处用适当句子予以填充。intPop(LstackTp*ls,DataType*x){LstackTp*p;if(ls!=NULL){p=ls;*x=;ls=;;return(1)；}elsereturn(0);}11、用堆栈求中缀表达式a+b*c/d+e*f的后缀表达式，求出的后缀表达式为（）。12、C语言中存储数组是采用以（）为主序存储的，在C语言中定义二维数组floata[8][10],每个数据元素占4个字节，则数组共占用（）字节的内存。若第一个数据元素的存储地址为8000，则a[5][8]的存储地址为（）。13、含零个字符的串称为（）串，用表示。其他串称为（）串。任何串中所含字符的个数称为该串的（）。14、数据的逻辑结构被分为（）、（）、（）和（）四种。15、算法设计的评价标准为（）、（）、（）、（）。16、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为（），若假定p为一个数组a中的下标，则其后继结点的下标为（）。17、堆栈的特点是（），所以又称（）表，队列的特点是（），所以又称（）表。18、（）通常称作串的模式匹配。在一个主串中查找子串是否存在，存在返回（）；不存在返回()。19、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的（）、（）和（）三项,同时存储稀疏矩阵行数、列数和非零数据元素的个数。20、线性表的常见链式存储结构有（）、（）和（）。21、队列简称（）表，在队列中，新插入的结点只能添加到（），被删除的只能是排在（）的结点。二、单项选择题1、一个堆栈的入栈序列为abcde，若出栈和入栈操作可间隔进行，则出栈序列不可能的为（）。A、edcbaB、decbaC、decabD、abcde2、设A是一个m*n阶矩阵，A按列序存储在一组连续的存储单元中，每个元素占用w个存储单元，若A[1,1]的存储地址为base，则A[i,j]的存储地址为（）。A、base+[(i-1)*m+(j-1)]*wB、base+[(j-1)*m+(i-1)]*wC、base+（j*m+i）*wD、base+（j*m+i）*w3、设定树根的层次为1，则有64个结点的完全二叉树的深度为（）。A、8B、7C、6D、4、在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点的先后顺序（）。A、都不相同Ｂ、前序遍历和中序遍历相同，而与后序遍历不同Ｃ、完全相同Ｄ、前序遍历和后序遍历相同，而与中序遍历不同5、关于有向图的邻接矩阵存储结构，下列叙述正确的是（）。①存储矩阵不一定是对称的;②第i行中1的个数为顶点i的出度;③第i列中1的个数为顶点i的入度;④矩阵中1的个数为图中弧的数目;⑤很容易判断顶点i和顶点j是否有弧相连。A、①②③④B、②③④⑤C、①③④⑤D、全对6、关于逻辑结构和存储结构，正确的描述是（）。A、线性数据结构必须采用链式存储结构B、一种逻辑结构，可以用不同的存储结构来存储，反之亦然C、一种逻辑结构，可以用不同的存储结构来存储，反之不然D、一种存储结构只能表示一种逻辑结构7、关于链表的特点描述不正确的是（）。A、存储空间不一定连续；B、元素之间的后继关系是由指针来体现的；C、逻辑上相邻，物理上不一定相邻；D、随机存取（顺序存取），即访问任何一个元素的时间相同。8、在顺序存储（空间大小为m）的循环队列q中，下列判满正确的是（）。A、q.front%m=0;B、q.rear%m=0;C、(q.rear+1)%m=q.front;D、q.front=q.rear;9、已知广义表:A=(a,b),B=(A,A),C=(a,(b,A),B),求下列运算的结果:tail(head(tail(C)))=()。A、（a）B、(A)C、(b)D、A10、已给下图，哪一项是该图的拓扑排序？（）A、1，2，3，4，5B、1，3，2，4，5C、1，2，4，3，5D、1，2，3，5，411、已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（）。A、1.0B、2.9C、3.4D、12、以下说法错误的是（）。A、散列法存储的基本思想是由关键码的值决定数据的存储地址。B、散列表的结点中只包含数据元素自身的信息，不包含任何指针。C、装填因子是散列法的一个重要参数，它反映散列表的装填程度。D、散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。13、以下说法正确的是（）。A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”14、下列判断正确的是（）。A、如果两个串含有相同的字符，则这两个串相等。B、数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。C、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每一块中元素个数有关。D、对任意图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。15、对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是（）。A、(c,d)B、(d)C、bD、(b)16、下列说法正确的是（）。A、树的先根遍历序列与其对应的二叉树的先根遍历序列相同B、树的先根遍历序列与其对应的二叉树的后根遍历序列相同C、树的后根遍历序列与其对应的二叉树的先根遍历序列相同D、树的后根遍历序列与其对应的二叉树的后根遍历序列相同三、基本技能测试题1、已知一任意关键字序列{19,14,22,01,66,21,83,27,56,13}，按元素在序列中的次序构造一棵平衡二叉树，给出构造过程（当有调整时给出调整后的平衡二叉树）并求查找成功的平均查找长度。2、有待排序的元素序列{72，13，70，23，95，16，5，68，26，45}，请用快速排序的方法对上述序列排序，给出每一趟排序后的结果。3、画出下图的邻接表存储结构示意图，并根据邻接表存储结构示意图求出图的深度优先遍历序列和广度优先遍历序列。4、学习数据结构的目的是什么？5、已知二叉树的先序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC，画出这个二叉树。6、给出一组关键字序列{29，18，25，47，58，12，15，10}，构造初始堆，给出构造工程。7、已知字符A、B、C、D、E、F的使用频率分别为9、15、32、22、18、4，构造哈夫曼树（HuffmanTree），求出各个字符的哈夫曼编码。8、已知一个无向图的邻接表如下图所示。Λ421V1Λ421V1Λ1452V2Λ1452V244Λ53V3Λ53V3Λ3214V4Λ3214V4Λ325V5Λ325V5(1)画出这个图。(2)根据邻接表，以v1为出发点，对图进行广度优先搜索和深度优先搜索，写出各自访问序列。ABCFEABCFEDG5065406045524250307010、给出下面二叉树的先序遍历、中序遍历、后续遍历和层序遍历序列。11、已知无向图如下，请完成。（1）给出图的邻接链表存储结构图；（2）依据你的存储结构图，写出从A开始的广度和深度优先遍历序列。12、对于数据序列{49,38,65,97,76,13,27,50}，构造平衡二叉树，给出构造过程。三、算法设计与编程题1、以顺序表作为存储结构，编写一个实现线性表就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表数据元素顺序有(a1，a2,...,an)逆置为(an,...,a2,a1)。2、用顺序表存储空间的动态分配的方法实现线性表的插入算法。即在顺序存储的线性表中的第i个数据元素之前插入一个数据元素。3、已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有：makeEmpty(s:stack)；置空栈push(s:stack;value:datatype)；新元素value进栈pop(s:stack):datatype；出栈，返回栈顶值isEmpty(s:stack):boolean；判栈空否队列的ADT函数有：enqueue(q:queue;value:datatype)；元素value进队deQueue(q:queue):datatype；出队列，返回队头值isEmpty(q:queue):boolean；判队列空否4、图的邻接矩阵和邻接表存储结构定义如下：邻接矩阵:typedefstruct{intvexnum,arcnum;charvexs[100];intarcs[100,100]}MGraph;邻接表：typedefstructarcptr{intadjvex;//邻接点的存储位置structarcptr*nextarc;}ArcNode;//下邻接点typedefstructvexnode{chardata;//数据元素ArcNode*firstarc;}Vnode;//第一个邻接点typedefstruct{intvexnum,arcnum;//图的顶点个数Vnodevertices[100];}ALGraph;给出将无向图的邻接矩阵转换成邻接表的算法。

《数据结构》综合复习资料参考答案一、填空题1、答案：相互之间存在一种或多种特定关系的数据元素的集合，即带结构的数据元素的集合2、答案：线性结构、树型结构、图状结构或网状结构3、答案：前驱、后继、后继4、答案：先进后出、先进先出、字符5、答案：15、子、86、答案：高、不、一7、答案：3、（a）、（（（b），c），（（（d））））8、答案：一个数学模型及定义在这个模型上的一组操作或运算的总称9、答案：O(n2)10、答案：p->datals->next;free(p);11、答案：abc*d/+ef*+12、答案：行、320、823213、答案：空、非空、长度14、答案：集合结构、线性结构、树形结构、图形结构15、答案：正确性、易读性、健壮性、效率16、答案：p->next、p+117、答案：先进后出、先进后出、先进先出、先进先出18、答案：子串的定位操作、子串在主串中的位置、019、答案：行号、列号、元素值20、答案：单链表、双链表、循环链表21、答案：先入先出、队尾、队头二、单项选择题题目12345678910答案CBBCDBDCBA题目111213141516答案BBACDA三、基本技能测试题1、答案：参见教材227-232页。2、答案：参见教材273-276页。3、答案：参见教材163页和167-170页。4、答案：（1）学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择合适的逻辑结构、存储结构及其相应的算法；（2）初步掌握算法的时间分析和空间分析技术；（3）能够设计符合软件工程规范的、较复杂的程序；程序结构清晰，正确易懂，较好的时间和空间复杂度。5、答案：6、答案：7、答案：A:0001B:001C:01D:11E:10F:00008、答案：（1）（2）广度优先搜索序列：V1->V2->V4->V5->V3深度优先搜索序列：V1->V2->V5->V3->V49、答案：10、答案：先序遍历序列：abdgcef中序遍历序列：dgbaecf后续遍历序列：gdbefca层序遍历序列：abcdefg11、答案：（1）(2)广度优先遍历序列：ABCGFDE深度优先遍历序列：ABDCEFG12、答案：三、算法设计与编程题1、答案：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：

//表结构定义同上

voidReverseList(Seqlist*L)

{Datatypet;//设置临时空间用于存放data

inti;

for(i=0;i<L->length/2;i++)

{t=L->data[i];//交换数据

L->data[i]

=L->data[L->length-1-i]

;

L->data[L->length-1-i]=t

;

}

}2、答案：StatusListInsert_sq(sequenlist&L,inti,entrytypee){if(i<1||i>L.len+1)returnERROR;//i值不合法if(L.len>=L.listsize)//检查空间是否已满{newbase=(elemtype*)realloc(L.a,(listsize+LISTINCREMENT)*sizeof(elemtype));//增加空间if(!newbase)exit(Overflow);//空间增加失败L.a=newbase;//空间增加成功L.listsize+=LISTINCREMENT;}q=&(L.a[i-1])；//q指向插入位置for(p=&(L.a[L.len-1]);p>=q;--p)*(p+1)=*p;//将线性表第i个元素之后的所有元素向后移动*q=e;//插入e++L.len;//表长+1ReturnOK;}3、答案：voidchange（queueq,stacks）{datatypetemp;