数据结构考试试题

东华理工大学2015—2016学年第一学期考试试卷A《答案》一、填空题（50分）1、数据结构是一门研究非数值计算的程序设计问题中的数据元素以及它们之间关系和运算等的科学。（2分）2、数据结构的类型通常分为：集合、线性结构、树形结构、图状结构或网状结构；从逻辑上可以把它们分成：线性结构和非线性结构。3、数据的逻辑结构只抽象反映数据元素的逻辑关系；数据的存储（物理）结构是数据的逻辑结构在计算机存储器中的实现。4、算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是空间复杂度和时间复杂度。5、计算机算法是解决问题的有限运算序列，它必须具备输入、输出、确定性、有穷性和稳定性等5个方面的特性。6、线性结构中元素之间的关系存在一对一关系，树形结构中元素之间的关系存在一对多关系，图形结构中元素之间的关系存在多对多关系。7、试写出以下算法的时间复杂度i=s=0while(sn){i++;s+=i;}7、试写出以下算法的时间复杂度i=1while(i=n)i=i*2O(log2n))(nO8、抽象数据类型的定义由三元组来定义：(D,S,P)其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。9、写出抽象数据类型线性表的定义ADTList{数据对象：D={ai|aiElemset,i=1,2,…,n,n0}数据关系：R={ai-1,ai|ai-1,aiD,i=2,…,n}基本操作：InitList(&L)//构造一个空的线性表LDestroyList(&L)//消毁线性表LListLength(L)//返回L中数据元素的个数ListInsert(&L,i,e)//1≤i≤ListLength(L)+1,在L中第i个位置之前插入数据元素e,L长度加1ListDelete(&L,i,&e)//1≤i≤ListLength(L),删除L中的第i个元素，并用e返回ListTraverse(L,visit())//依次对L的每个元素调用函数visit()…………}ADTList10、指出线性表顺序存储、链式存储结构的优缺点。答：顺序存储优点：逻辑上相邻，物理位置也相邻，可以随机存取表中任一元素；缺点：插入和删除元素时需要移动大量元素。链式存储结构优点：插入、删除元素时不需要移动元素；缺点：逻辑上相邻，物理位置不一定相邻，不能随机存取表中元素，需要依次查找，求线性表的长度时不如顺序存储结构方便，需要逐个结点搜索计算，或设置带头结点的线性链表。11、完成下列在单链表中删除元素算法StatusListDelete_L(LinkList&L,inti,ElemType&e){//删除第i个元素ep=L;j=0;//p指向头结点while(p-next&&ji-1){p=p-next;++j}//寻找第i个结点,并令p指向其前驱if(!(p-next)||ji-1)returnERROR;//删除位置不正确q=p-next;p-next=q-next;//删除与释放结点e=q-data;free(q);returnOK;}12、在一个长度为n的线性链表中第i个元素（1in）之前插入一个元素时，需向后移动n-i+1个元素。13、在一个长度为n的线性链表中删除第i个元素（1in）时，需向前移动n-i个元素。14、在一个单链表中p所指结点之后插入一个s所指结点时，应执行s-next=p-next和p-next=s的操作。15、在单链表中，插入或删除一个结点元素时，仅需要修改指针而不需要移动元素。16、栈(Stack)是限定仅在表尾进行插入和删除操作的线性表，17、栈链式存储结构中删除栈顶元素，并用e返回，完成下列算法StatusPop(ListStack&S,SElemType&e){if(S.top=NULL)returnERROR;//栈无元素p=S.top;S.top=S.top-next;e=p-data;free(p);//释放节点批pS.len--;returnOK;}17、设有一队列，(a1,a2,…,an)则对头元素是a1队尾元素是an。18、假设队列以带头结点的链式表示，则删除一个元素并返回给e的算法如下：StatusDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnEEROR;p=Q.front-next;//p为需要删除的结点e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;//队列中只有一个元素被删除时，队尾等于队头free(p);returnOK;}19、循环队列中，假设少用一个元素，则插入元素到队尾的算法StatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//队满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;//Q.rear前移returnOK;}20、循环队列中，假设少用一个元素，则/删除队头元素并赋给e的算法如下StatusDeQueue(SqQueue&Q,QElemType&e){if(Q.front=Q.rear)returnERROR;//队空e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;//Q.rear前移returnOK;}21、判定一个队列QU（最多元素为MaxSize）为空的条件是:QU-front==QU-rear；为满队列的条件是:QU-rear-QU-front==MaxSize。22、S1=‘ABCDEFG’，s2=‘PQRST’，假设con(x,y)为连接两字符串函数，subs(s,i,j)返回串s中从第i个位置起的j个字符，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串为：BCDEFEF23、什么是稀疏矩阵？如何衡量？举例采用三元子顺序表示已稀疏矩阵。答：当矩阵中的非零元素比较少，且分布没有一定的规律，称为稀疏矩阵。稀疏矩阵的衡量标准，可以用稀疏因子表示，通常认为当≤0.05是称为稀疏矩阵nmt24、深度为5的二叉树最多有31个结点。25、深度为k的完全二叉树至少有2k-1个结点，至多有2k-1个结点，若自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶结点的编号是2k-1。26、已知一棵二叉树的中序遍历序列为cbedahgijf，后序遍历序列为cedbjigfa，画出该二叉树。二、设有下列一棵树，回答下列问题：（15分）1）该树的根结点是A；2）这棵树的叶结点是G、E、F、I、J；3）该树的非终端结点是A、C、B、D、H；4）D结点的度是1；5）该树的度是3；树深度是4；6）将该树转换成二叉树。（5分）7）假设对该树进行先根遍历、后根遍历，写出该树的先根序列、后根系列。（5分）acbdefghijADCGBEFHIJACGBEFDHIJ先根序列：ACGDHIJBEF后根系列：GCIJHDEFBA2、数据逻辑结构包括：线性结构、树形结构和图形结构三种类型，树形结构和图形结构合称为非线性结构。（4分）3、下列程序段的时间复杂度是O(n)。（2分）i=s=0;while(sn){i++;s+=i;}4、判断一个循环队列QU（最多元素为m0）为满队列的条件是QU-front==(QU-rear+1)%m0。（2分）5、带头结点的单链表head为空的判断条件是head-next==NULL。（2分）6、假设线性表采用单链表存储结构,完成下列插入元素的算法(5分)StatusListInsert_L(LinKList&L,inti,ElementTypee){//在带头结点的单链线性表L中第i个位置之前插入元素p=L;j=0;while(p&&ji-1){p=p-next;++j}if(!p||ji-1)returnERRORs=(LinkList)malloc(sizeof(LNode));s-data=e;s-next=p-next;p-next=s;returnOK；}7、若x和y是两个采用顺序结构存储的串，编写并完成比较两个串是否相等的函数。（6分）intIssame(orderstring*x,orderstring*y){inti=0;tag=1;if(x-len!=y-len)return(0);else{while(ix-len&&tag){if(x-vec[i]!=y-vec[i])tag=0;i++;}return(tag);}}8、已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0]),则A[i][j]用的地址是LOC(A[0][0])+(n*i+j)*k。（2分）10、下图所示的4棵二叉树，是平衡二叉树的树是B、D。（4分）BADC11、深度为k的完全二叉树至少有2k-1个结点，至多有2k-1个结点，若从上而下，从左到右次序给结点编号（从1开始），则编号最小的叶结点的编号是2k-2+1。（3分）.12、有向完全图：具有n(n-1)条边的有向图称为有向完全图。（2分）13、对线性表进行折半查找时，要求线性表必须以顺序方式存储，且结点按关键字有序排列。（4分）14、一组记录的排序码为（17,48,24,35,69,82,23,79,36,72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并排序后的结果为：17,24,35,48,23,69,79,82,36,72。（6）15、已知系列{503，87，512，61，908，170，897，275，653，462}，以第一个记录为枢轴（基准），写出采用快速排序法对该序列作升序排序时的第一趟的结果：（5分）[462，87，275，61，170]503[897，908，653，503]。三、已直一棵二叉树的中序遍历系列为kbedohgijf，后序遍历系列为kedbhjigfo，画出该二叉树。（5分）Kobfdkeghij四、稀疏矩阵有什么特点？假设用三元组顺序表来表示稀疏矩阵，试设计该方法的存储结构。写出下列稀疏矩阵的三元组表示。（10分）0000510000030200答：实际非零元素的个数远远小于矩阵元素的个数（0.05）。A三元组顺序表示存储结构可设计如下：#MAXSIZE12500;typedefstruct{inti,j;Elemtypee;}Triple;typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix;将下列树转换成二叉树ijv10222103322-14235已知有5个字符（a,b,c,d,e），它们出现的权值分别是{12,4,5,2,3}。试构建一个赫夫曼树，并求它们的赫夫曼编码。a（0），b（100），c（101），d（110）,e（111）完全图:对于有n顶点的无向图，边E的取值范围是0~n(n-1)/2，当n个顶点的无向图有n(n-1)/2条边时称为完全图有向完全图:对于有n顶点的无向图，边E的取值范围是0~n(n-1)，当n个顶点的有向图有n(n-1)条边时称为有向完全图采用邻接表存储图的深度优先遍历法算类似与二叉树的先序遍历，而广度优先遍历算法类似与二叉树的层序遍历。已知一个有向图用邻接矩阵表示，则计算第i结点入度的方法是求矩阵第i列非0元素之和。图的深度优先搜索序列和广度优先搜索序列是不惟一的。三、图的存储结构有哪几种？请用邻接矩阵和邻接表两种存储结构表示下图。（10分）V1V2V3V4V5参考答案：（1）图的存储结构有有：数组表示法（邻接矩阵）、邻接表、十字链表和邻接多重表四种表示方法。（2分）（2