数据结构试卷及答案资料.doc

东华理工大学2015 2016学年第 一 学期考试模拟试卷 A 一、 填空题（50分）1、数据结构是一门研究非数值计算的程序设计问题中的 数据元素 以及它们之间 关系 和运算等的科学。（2分）2、数据结构的类型通常分为： 集合、线性结构、树形结构、图状结构或网状结构 ；从逻辑上可以把它们分成： 线性结构和非线性结构 。3、数据的 逻辑结构 只抽象反映数据元素的 逻辑关系 ；数据的 存储（物理）结构 是数据的逻辑结构 在计算机存储器中的实现 。4、算法分析的目的是分析算法的 效率以求改进 ，算法分析的两个主要方面是 空间复杂度和时间复杂度 。A5、计算机算法是解决问题的 有限运算序列 ，它必须具备 输入、输出、确定性、有穷性和稳定性 等5个方面的特性。6、线性结构中元素之间的关系存在 一对一 关系，树形结构中元素之间的关系存在 一对多 关系，图形结构中元素之间的关系存在 多对多 关系。7、试写出以下算法的时间复杂度i=s=0while (sn) i+;s += i;7、试写出以下算法的时间复杂度i = 1 while( i = n)i = i*2 O(log2n)8、抽象数据类型的定义由三元组来定义：(D,S,P)其中，D是 数据对象， S是D上的关系集，P是 对D的基本操作集。9、写出抽象数据类型线性表的定义ADT List数据对象：D=ai | ai Elemset, i=1,2,n,n0数据关系：R= | 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() ADT List10、指出线性表顺序存储、链式存储结构的优缺点。答：顺序存储优点：逻辑上相邻，物理位置也相邻，可以随机存取表中任一元素；缺点：插入和删除元素时需要移动大量元素。链式存储结构优点：插入、删除元素时不需要移动元素；缺点：逻辑上相邻，物理位置不一定相邻，不能随机存取表中元素，需要依次查找，求线性表的长度时不如顺序存储结构方便，需要逐个结点搜索计算，或设置带头结点的线性链表。11、完成下列在单链表中删除元素算法Status ListDelete_L(LinkList &L, int i, ElemType &e) /删除第i个元素ep = L; j =0; /p指向头结点while(p-next & jnext; +j /寻找第i个结点,并令p指向其前驱if(!(p-next) | ji-1) return ERROR; /删除位置不正确q= p -next; p-next = q-next ; /删除与释放结点e = q-data; free(q); return OK;12、在一个长度为n的线性链表中第i个元素（1in）之前插入一个元素时，需向后移动 n-i+1 个元素。13、在一个长度为n的线性链表中删除第i个元素（1in）时，需向前移动 n-i 个元素。14、在一个单链表中p所指结点之后插入一个 s所指结点时，应执行 s-next = p-next 和 p-next = s 的操作。15、在单链表中，插入或删除一个结点元素时，仅需要修改 指针 而不需要移动 元素 。16、栈(Stack)是限定仅在表尾进行插入和删除操作的线性表，17、栈链式存储结构中删除栈顶元素，并用e返回，完成下列算法Status Pop(ListStack &S, SElemType &e)if(S.top=NULL) return ERROR; /栈无元素p = S.top;S.top = S.top-next;e = p-data;free(p);/释放节点批pS.len-;return OK;17、设有一队列，(a1,a2,an)则对头元素是 a1 队尾元素是 an 。18、假设队列以带头结点的链式表示，则删除一个元素并返回给e的算法如下：Status DeQueue(LinkQueue &Q, QElemType &e)if(Q.front = Q.rear) return EEROR;p = Q.front-next;/p为需要删除的结点e = p-data;Q.front-next = p-next;if (Q.rear =p) Q.rear = Q.front;/队列中只有一个元素被删除时，队尾等于队头free(p);return OK;19、循环队列中，假设少用一个元素，则插入元素到队尾的算法Status EnQueue(SqQueue &Q, QElemType e)if(Q.rear+1)%MAXQSIZE = Q.front) return ERROR;/队满 Q.baseQ.rear=e; Q.rear = (Q.rear +1) % MAXQSIZE;/ Q.rear前移return OK;20、循环队列中，假设少用一个元素，则/删除队头元素并赋给e的算法如下Status DeQueue(SqQueue &Q, QElemType &e)if(Q.front = Q.rear) return ERROR;/队空e = Q.baseQ.front; Q.front = (Q.front +1) % MAXQSIZE; / Q.rear前移return OK; 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、什么是稀疏矩阵？如何衡量？举例采用三元子顺序表示已稀疏矩阵。答：当矩阵中的非零元素比较少，且分布没有一定的规律，称为稀疏矩阵。稀疏矩阵的衡量标准，可以用稀疏因子d表示，通常认为当d 0.05是称为稀疏矩阵24、深度为5的二叉树最多有 31 个结点。25、深度为k的完全二叉树至少有 2k-1 个结点，至多有 2k-1 个结点，若自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶结点的编号是 2k-1 。26、已知一棵二叉树的中序遍历序列为cbedahgijf，后序遍历序列为cedbjigfa，画出该二叉树。acbdefghij二、设有下列一棵树，回答下列问题：（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分） 先根序列：A C G D H I J B E F 后根系列：G C I J H D E F B A2、数据逻辑结构包括： 线性结构 、树形结构 和 图形结构 三种类型，树形结构和图形结构合称为 非线性结构 。（4分）3、下列程序段的时间复杂度是 O(n) 。（2分）i=s=0;while(sfront = (QU-rear + 1) % m0。（2分）5、带头结点的单链表head为空的判断条件是 head-next=NULL。（2分）6、假设线性表采用单链表存储结构,完成下列插入元素的算法 (5分)Status ListInsert_L( LinKList &L, int i, ElementType e )/在带头结点的单链线性表L中第i个位置之前插入元素p= L; j=0;while ( p & j next ; +jif(!p | j i-1 ) return ERRORs = ( LinkList ) malloc( sizeof (LNode );s - data = e ; s-next = p-next ;p-next = s ;return OK；7、若x和y是两个采用顺序结构存储的串，编写并完成比较两个串是否相等的函数。（6分）int Issame( orderstring *x, orderstring *y)int i =0; tag = 1 ;if(x-len != y-len ) return(0);elsewhile (i len & tag)if(x-veci != y-veci) tag = 0 ; i+ ;return ( tag );8、已知二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A00),则Aij用的地址是 LOC(A00)+ (n*i+j)*k 。（2分）10、下图所示的4棵二叉树，是平衡二叉树的树是 B、D 。（4分）11、深度为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分）A四、稀疏矩阵有什么特点？假设用三元组顺序表来表示稀疏矩阵，试设计该方法的存储结构。写出下列稀疏矩阵的三元组表示。（10分） 答：实际非零元素的个数远远小于矩阵元素的个数（0.05）。三元组顺序表示存储结构可设计如下：#MAXSIZE 12500;typedef structint i, j;Elemtype e;Triple;typedef structTriple dataMAXSIZE +1;int mu,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的取值范围是0n(n-1)/2，当n个顶点的无向图有n(n-1)/2条边时称为完全图有向完全图:对于有n顶点的无向图，边E的取值范围是0n(n-1) ，当n个顶点的有向图有n(n-1)条边时称为有向完全图采用邻接表存储图的深度优先遍历法算类似与二叉树的 先序遍历 ，而广度优先遍历算法类似与二叉树的 层序遍历 。已知一个有向图用邻接矩阵表示，则计算第i结点入度的方法是 求矩阵第i列非0元素之和。图的深度优先搜索序列和广度优先搜索序列是 不惟一的 。三、图的存储结构有哪几种？请用邻接矩阵和邻接表两种存储结构表示下图。（10分）参考答案：（1）图的存储结构有有：数组表示法（邻接矩阵）、邻接表、十字链表 和邻接多重表四种表示方法。（2分）（2）邻接矩阵储结构如下：（4分）（3）邻接表存储结构如下：（4分）五、用Dijstra方法求下图中从V0点到各终点的最短路径，并在表格中填写求解过程。（12分）参考答案：（1）在表格中填写算过程（8分）终点从V0点到各终点的D值和最短路径的求解过程I=1I=2I=3I=4I=5V11(v0,v1)V22v0,v1,v2V35(v0,v3)5(v0,v3)3(v0,v1,v2,v3)V4无V55(v0,v5)4(v0,v1,v5)4(v0,v1,v5)4(v0,v1,v5)VjV1V2V3V5Sv0,v1v0,v1,v2v0,v1,v2,v3v0,v1,v2,v3,v5（2）阐述v0到各点的路径（4分）v0到v1点的最短路径为1，顶点为(v0,v1) v0到v2点的最短路径为2，顶点为(v0,v1,v2) v0到v3点的最短路径为3，顶点为 (v0,v1,v2,v3)v0到v4点之间无路径 v0到v5点的最短路径为4，顶点为(v0,v1,v5)五、试找出下列有向无环网的关键路径。（10分）顶点vevl边ell-eV100a1099V2413a2077V3613a3000V455a44139V5714a56137V677a6550V71624a77158V82121a87147V92626a9770a1016248a1121210关键活动为：a3, a6, a9, a11；关键路径为：(v1,v4,v6,v8,v9)六、什么是最小生成树？用普里姆算法写出下列连通图的最小生成树。（10分）参考答案：（1）在一个具有n个顶点的连通图G中，如果存在一个子图G包含G中的全部顶点和一部分边，且不形成回路，则称G为图G的一棵生成树。代价最小的生成树称为最小生成树。（4分）（2）最小生成树（6分）