东南大学93考研题
（1）答卷上需写清题号，不必抄题
（2）描述可用你熟悉的一种类高级语言，如类Pascal，所用主要数据结构及变量的意义须加以注释。必要时算法中应加注释。
一、回答下列问题 : (共 35分)
l与链式结构相比，线性表的顺序存贮的一个主要优点和一个主要缺点分别是什么 ? (4分)
2在表达式中，有的运算符要求从右到左计算，如A**B**C的计算次序应为(A**(B**C))，这在由中缀生成后缀的算法中是怎样实现的?(以**为例说明 ) (6分)
3.给出KMP算法中失败函数f的定义，并说明利用f进行串模式匹配的规则，该算法的技术特点是什么？（9分）
4二叉树的中序与后序序列能唯一地定义一棵二叉树吗?这里所指序列中的符号代素树结点中的标识符吗？二叉村的前序与后序序列能唯一地定义一棵二叉树吗?为什么?(8分)
5在什么情况下m阶B树(m>>2)比AVL树有效?分析其原因·(8分)
二。将n个队列顺序映射到数组v[l···m]中，每一队列在v中表示为一，循环队列。试画出其示意图并写出对应这种表示的addq和deleteq 过程。 (20分)
三、给出中序线索树的结点结构并画出一个具有头结点的中序线索树，使其树结点至少应有6个，写一算法在不使用栈和递归的情况下前序遍历一中序线索树，并分析其时间复杂度，（20分）
四、证明：具有n个点和多于n-1条边的无向连通图G一定不是树（10分）
五、若S是n个元素的集合，则S的幂集P(S)定义为S所有子集的集合。例如，S=(a,b,c),P(S)={() ,(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}给定S，写一递归算法求P(S)。（15分）
东南大学一九九四年攻读硕士学位研究生入学考试试题
一: 回答下列问题(共32分)
1.最近最少使用(Least-Recently-Used)页替换是虚拟存储系统中常用的策略,试说明如何利用一页链接表时刻跟踪最近最少使用页?(8
2.已知无向图G,V(G)={1,2,3,4},E(G)={(1,2),(1,3),(2,3),(2,4),(3,4)},试画出G的邻接多表(Adjacency Multilists),并说明,若已知点i,如何根据邻接多表找到与i相邻的点j?(8分)
3.欲求前k个最大元素,用什么分类(sorting)方法好?为什么?什么是稳定分类?分别指出下列算法是否稳定分类算法,或易于改成稳定分类算法?(a) 插入分类 (b) 快速分类 (c) 合并分类 (d) 堆(heap)分类 (e) 基数分类(radix sort) (8分)
4.构造最佳二叉检索树的前提条件是什么?在动态情况下,一般AVL树的查询性能不如完全二叉检索树的,为什么人们却采用AVL树呢?(8 二:下列算法对一n位二进制数加1,假设无溢出,该算法的最坏时间复杂度是什么?并分析它的平均时间复杂性.(15分)
type Num=array[1..n] of [0..1];
procedure Inc(var A:Num);
var j: integer;
begin i:=n;
while A[i]=1 do
A[i]:=0;i:=i-1;
end;
A[i]:=1;
end Inc;
三:给定n*m矩阵A[a..b,c..d],并设A[i,j]<=A[i,j+1](a<=i<=b,c<=j<=d-1)和A[i,j]<=A[i+1,j](a<=i<=b-1,c<=j<=d),设计一算法以比O(n*m)小的时间复杂度判定值x是否在A中.(17分)
四:设图G有n个点,利用从某个源点到其余各点最短路径算法思想,设计一产生G的最小生成树的算法.(18分)
五:字符序列的子序列由删除该序列任意位置的任意个元素而得.序列x和y的最长公共子序列记为Lcs(x,y),是x和y的公共子序列,且长度最大.例如,adcbcb是x=abdcbcbb和y=adacbcb的最长公共子序列.设x长度为n,y长度为m,设计一算法计算x和y的最长公共子序列的长度,尽可能改进你的算法,使它的时间复杂性为O(n*m).(18分)
东南大学一九九五年攻读硕士学位研究生入学考试试题
1.在磁带文件上进行二分查找行吗?为什么?(6分)
2.分析确定下列程序中语句k:=k+1执行次数与n所成的数量级关系(即表示为O(f(n))的形式).(6分)
k:=1; i:=k;
while i begin k:=k+1; i=i+k; end; 3.外排序中为什么采用k-路合并而不采用2-路合并?这种技术用于内排序有意义吗?为什么?(8分) 4.索引顺序存取方法(ISAM)中,主文件已按主关键字(primary key)排序,为什么还需要主关键字索引?(6分) 5.满二叉检索树(full binary search tree)符合B树定义吗?B树的插入(insetb)和删除(deleteb)算法适用于满二叉检索树吗?为什么?(10 6.设无向图G有n个点e条边,写一算法建立G的邻接多表(adjacency multilists),要求该算法的时间复杂性为O(n+e),且除邻接多表本身所占空间外只用O(1)辅助空间.(16分) 7.写一改进的递归快速排序算法,要求对于n个记录,该算法的递归深度<=1+log2(n),并说明你的算法满足这一要求.(17分) 8.定义前序排列(preorder permutation)为1,2,……n的全部二叉树的中序排列(inorder permutation)集合为IP;再定义将1,2,……n 从右到左经过一个栈可得到的全部排列集合为SP.例如,当n=3,SP={123,132,213,231,321}.问:IP包含于SP成立否?证明你的结论.(16分) 9.设记录R[i]的关键字为R[i].key(1<=i<=k),树结点T[i](1<=i<=k-1)指向败者记录,T�为全胜记录下标.写一算法产生对应上述 R[i](1<=i<=k)的败者树(tree of loser),要求除R[1..k]和T[0..k-1]以外,只用O(1)辅助空间.(15分) 东南大学一九九六年攻读硕士学位研究生入学考试试题 一:回答下列问题(共46分) 1.线性表(a(1),a(2),……a(n))用顺序映射表示时,a(i)与a(i+1)(1<=i 2.一棵前序序列为1,2,3,4的二叉树,其中序序列可能是4,1,2,3吗?设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为 2,3,1,5,4,7,8,6,9,试画出该二叉树.(7分) 3.在模式匹配KMP(Knuth,Morris and Pratt)算法中所用失败函数f的定义中,为什么要求p(1)p(2)……p(f(j))为p(1)p(2)……p(j)两头 匹配的真子串?且为最大真子串?(7分) 4.在union-find问题中,控制union操作的权重(weighting)规则是何含义, 有何效果?控制find操作的倒塌(collapsing)规则是何含义,有何效果?(7分) 5.堆排序(heap sort)是稳定排序吗?举例说明.(6分) 6.给定输入文件:101,48,19,65,3,74,33,17,21,20,99,53,24,并设记录缓冲区个数k=4,写出基于败者树的外排序顺串生成算法runs输出的顺串.(6分) 7.m阶B树中,m大小的确定与什么因素有关?(8分) 二:设结点结构为:| data | link |,试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队和出队deleteq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间).(10分) 三:设有向图G有n个点(用1,2,……n表示),e条边,写一算法根据G的邻接表生成反向邻接表,要求时间复杂性为O(n+e).(13分) 四:设二叉树结点结构为:| left | data | bf | right |,定义二叉树结点T的平衡因子bf(T)=h(左)-h(右),写一递归算法确定二叉树tree 中所有节点的平衡因子bf,同时返回二叉树tree中非叶结点个数.(15分) 五: 设符号表T重的标识符x满足1<=x<=m,且n为对T表的最大插入次数.设计符号表T的表示结构,允许使用O(m+n)空间,并写出T的初始化(init),查找(search),插入(insert)和删除(delete)算法,要求它们的时间复杂性都是O(1).(16分) 东南大学一九九七年攻读硕士学位研究生入学考试试题 一:简要回答下列问题(共32分) 1.在表达式中,有的运算符要求从右到左运算,如A^B^C的计算次序应为(A^(B^C)),这在由中缀生成后缀的算法中是怎样实现的?(8分) 2.给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的技术特点是什么?(8分) 3.Fibonacci查找算法(fibsrch)中为什么要求m 4.为什么在倒排文件(inverted files)组织中,实际记录中的关键字域(key fields)可删除以节约空间?而在多表(multilists)结构中这样做为什么要牺牲性能?(8分) 二:试写一算法,建立无向图G的邻接多表(adjacency multilists),要求说明算法中主要数据结构和变量的意义.(15分) 三:给出中序线索树的结点结构并画出一个具有头结点的中序线索树,使其树结点至少应有6个,写一算法在不使用栈和递归的情况下前序遍历一中序线索树,并分析其时间复杂性.(18分) 四:若S是n个元素的集合,则S的幂集P(S)定义为S的所有子集的集合.例 如,S=(a,b,c),P(S)={(),(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}.给定S,写一递归算法求P(S).(15分) 五:已知在llink-rlink存储法表示的二叉树中,指针t指向该二叉树的根结点,指针p,q分别指向树中的二个结点,试写一算法,求距离这两个结点最近的共同的祖先结点.(20分) 东南大学一九九八年攻读硕士学位研究生入学考试试题 一:简要回答下列问题(共40分) 1.设胜者树(selection tree)由k个记录缓冲区和k-1个非叶结点构成.概念上非叶结点表示其两个子女中关键字较小者,而实际上非叶结点存放的是什么?(5分) 2.索引顺序存取方法(ISAM)中,主文件已按主关键字(primary key)排序,为什么还需要主关键字索引?(6分) 3.一棵前序序列为1,2,3,4的二叉树,其中序序列可能是4,1,2,3吗?设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为 2,3,1,5,4,7,8,6,9,试画出该二叉树.(7分) 4.构造最佳二叉检索树的前提条件是什么?在动态情况下,一般AVL树的查询性能不如完全二叉检索树的,为什么人们却采用AVL树呢?(8 5.将两个栈存入数组V[1..m]中应如何安排最好?这时栈空栈满的条件是什么?(6分) 6.已知无向图G,V(G)={1,2,3,4},E(G)={(1,2),(1,3),(2,3),(2,4),(3,4)},试画出G的邻接多表(Adjacency Multilists),并说明,若已知点i,如何根据邻接多表找到与i相邻的点j?(8分) 二:写出用堆排序(heap sort)算法对文件F=(12,3,15,30,9,28)进行排序时,初始堆及以后每挑好一个元素重新调整后堆的状态,并指出这里的堆和败者树(tree of loser)的一个主要区别.(8分) 三:设数组A存放一n位二进制数,试说明下列算法X的功能.假设无溢出,算法X的最坏时间复杂度是什么?分析它的平均时间复杂性.(8分) type Num=array[1..n] of [0..1]; procedure X(var A:Num); var j: integer; begin i:=n; while A[i]=1 do begin A[i]:=0; i:=i-1; end; A[i]:=1; end; 四:下面是一改进了的快速分类算法: 1 procedure qsort1(var list:afile;m,n:integer); 2 (设list[m].key 3 var i,j,k:integer; 4 begin 5 while m 6 begin 7 i:=m;j:=n+1;k:=list[m].key; 8 repeat 9 repeat i:=i+1 until list[i].key>=k; 10 repeat j:=j-1 until list[j].key<=k; 11 if i 12 until i>=j; 13 interchange(list[m],list[j]); 14 if n-j>=j-m 15 then begin qsort1(list,m,j-1);m:=j+1;end 16 else begin qsort1(list,j+1,n);n:=j-1;end 17 end;(of while) 18 end; 问: (共20分) 1.将第9,10行中的>=,<=分别改成>,<行吗?为什么?(5分) 2.该排序算法稳定否,举例说明.(5分) 3.对输入文件(22,3,30,4,60,11,58,18,40,16),列表表示该文件在每次调用qsort1时的状态及相应m,n的值.(5分) 4.若输入文件有n个记录,简要说明支持qsort1递归所需最大栈空间用量(设一层递归用一个单位栈空间).(5分) 五:给定AOE网络各事件(标号1..n)的ee,le值和邻接表,写一算法求该AOE的所有活动(用相应边的两端点表示)的关键度(criticality).(10分) 六:给出中序线索树的结点结构,并画出一个具有头结点和六个树结点的中序线索树,试写一算法在不使用栈和递归的情况下前序遍历一中序线索树,并分析它的时间复杂性.(18分) 东南大学一九九九年攻读硕士学位研究生入学考试试题 一:简要回答下列问题(共40分) 1.利用两个栈s1,s2模拟一个队列时,如何用栈的运算实现队列的插入,删除以及判队空运算.请简述算法思想.(7分) 2.二叉树有n个顶点,编号为1,2,3,……n,设: T中任一顶点V的编号等于左子树中最小编号减一; T中任一顶点V的右子树中最小编号等于其左子树中最大编号加一; 试描绘该二叉树.(7分) 3.设某文件经内排序后得到100个初始归并段(初始顺串),若使用多路归并排序算法,并要求三趟归并完成排序,归并路数最少为多少?(5 4.若一棵树中有度数为1至m的各种结点数分别为n1,n2,...nm(nm表示度数为m的结点个数),请推导出该树中共有多少个叶结点n0的公式.(8分) 5.试举例分析,堆排序法是否稳定.(5分) 6.试利用KMP算法和改进算法分别求p1='abcabaa'和p2='aabbaab'的NEXT函数和NEXTVAL函数.(8分) 二: 阅读下列算法,指出算法A的功能和时间复杂性.(10分) procedure A(h,g: pointer); (h,g分别为单循环链表(single linked circular list)中两个结点指针) procedure B(s,q: pointer); var p: pointer; begin p:=s; while p^.next<>q do p:=p^.next; p^.next:=s; end; (of B) begin B(h,g);B(g,h); end; (of A) 三:已知无向图采用邻接表存储方式,试写出删除边(i,j)的算法.(10分) 四:线性表中有n个元素,每个元素是一个字符,存在向量R[1..n]中,试写一个算法,使R中的字符按字母字符,数字字符和其它字符的顺序排列.要求利用原空间,且元素移动次数最少.(15分) 五: 四阶B树中(如图所示),插入关键字87,试画出插入调整后树的形状.(10分) |30 60 80| / / \ \ |20 25| |35 50| |60 70 75| |82 85 90| 六:试编写一算法对二叉树按前序线索化.(15分) 东南大学二○○○年攻读硕士学位研究生入学考试试题 一:简要回答下列问题(共40分) 1.假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树.(6分) 2.简单比较文件的多重表和倒排表组织方式各自的特点.(6分) 3.画出对算术表达式A-B*C/D+E^F求值时操作数栈和运算符栈的变化过程.(6分) 4.找出所有满足下列条件的二叉树6分) a)它们在先序遍历和中序遍历时,得到的结点访问序列相同; b)它们在后序遍历和中序遍历时,得到的结点访问序列相同; c)它们在先序遍历和后序遍历时,得到的结点访问序列相同. 5.对一个由n个关键字不同的记录构成的序列,能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏情况下至少进行多少次比较?(8分) 6.已知某文件经过置换选择排序后,得到长度分别为47,9,31,18,4,12,23,7的8个初始归并段.试为3路平衡归并设计读写外存次数最少的归并方案,并求出读写外存的次数.(8分) 二:已知L是无表头结点的单链表,其中P结点既不是首元结点,也不是尾元结点,(10分) a)在P结点后插入S结点的语句序列是______ b)在P结点前插入S结点的语句序列是______ c)在表首插入S结点的语句序列是______ d)在表尾插入S结点的语句序列是______ (1) P^.next:=S; (2) P^.next:=P^.next^.next; (3) P^.next:=S^.next; (4) S^.next:=P^.next; (5) S^.next:=L; (6) S^.next:=NIL; (7) Q:=P; (8) WHILE P^.next<>Q DO P:=P^.next; (9) WHILE P^.next<>NIL DO P:=P^.next; (10) P:=Q; (11) P:=L; (12) L:=S; (13) L:=P; 三:设计一个符号表的表示方法,编写算法使得在该表中进行查询,插入和删除任何一个标识符X的操作在O(1)的时间内.假设1<=x<=m,n 为要插入的个数,所需空间为m+n.(10分) 四:试利用Dijkstra算法求下图中从顶点a到其它各顶点的最短路径,写出执行算法过程中各步的状态.(10分) ____________ / 4 \ ↓ 6 \ b------→e___9 \ 15↑↑ \ / / 2 /8 ↓/ a------→c g (和严蔚敏习题集上题目相同) \ \4 ↑↑ 12↓ 5 ↓ 10/ / d←------f__/ / \___________/ 3 五:以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度.(15分) 六:写出按后序序列遍历中序线索树的算法.(15分) 东南大学二○○一年的题目: 一:（共40分） 1．判断下列叙述是否正确：（10分） ①在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。 ②从逻辑结构上看，n维数组的每个元素均属于n个向量。 ③无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。 ④用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。 ⑤带权的连通无向图的最小代价生成树是唯一的。 ⑥中序遍历一棵平衡的二叉排序树，可得到排好序的关键码序列。 ⑦树与二叉树是两类不同的树型结构。 ⑧完全二叉树中，若一个结点没有左孩了，则它必是树叶。 ⑨快速排序总比简单排序快。 ⑩对处理大量数据的外存介质而言，索引顺序存取方法（ISAM）是一种方便的文件组织方法。 2．为什么文件的倒排表比多重表组织方式节省空间。（6分） 3.设胜者树(selection tree)由k个记录缓冲区和k-1个非叶结点构成.概念上非叶结点表示其两个子女中关键字较小者,而实际上非叶结点存放的是什么? （6分） 4.给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的技术特点是什么? （6分） 5.是一道关于Huffman树中叶子结点和非叶结点数量关系的计算题,具体题目记不得了. （6分） 6.求有向图中任意一对顶点之间最短路径的弗洛伊德算法(allcosts-Floyd)中,要求有向图满足什么前提条件? （6分） 二:在二叉树的结点结构中增加一个域:leftsize,t^.leftsize表示t结点的左子树中结点的总个数,试编写算法alloc(k),在二叉树中查找中序序号为k的结点,要求时间复杂度为O(log2(n)). （10分） 三:编写算法输出从n个自然数中取k个(k<=n)的所有组合.例如,当n=5,k=3时,你的算法应该输出:543,542,541,532,531,521,432,431,421,321. （12分） 四:设有向图G用邻接表的方式存储,u,v是G中的任意两个结点,写一算法,求出G中从u到v的所有简单路径. （15分） 五:下面是一改进了的快速排序算法,试补充其中的空白语句,并分析该算法所需的最大递归空间是多少? （10分） procedure qsort1(var list:afile;m,n:integer); (设list[m].key var i,j,k:integer; begin while m begin i:=m;j:=n+1;k:=list[m].key; repeat repeat i:=i+1 until list[i].key>=k; repeat j:=j-1 until list[j].key<=k; if i until i>=j; interchange(list[m],list[j]); if n-j>=j-m then begin qsort1(list,m,___);______;end else begin qsort1(list,___,n);______;end end;(of while) end; 六:给定n*m矩阵A[a..b,c..d],并设A[i,j]<=A[i,j+1](a<=i<=b,c<=j<=d-1)和A[i,j]<=A[i+1,j](a<=i<=b-1,c<=j<=d),设计一算法以 O(n+m)的时间复杂度判定值x是否在A中. （13分） 东南大学2002年数据结构考研试题 一、判断下列叙述是否正确：(10分) 1、设指针P指向单链表中的一个结点，则语句序列U:=P.next; U:=U.next 将删除一个结点。 2、栈和队列都是运算受限的线性表。 3、广义表的长度是广义表中的原子个数。 4、若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。 5、二叉树在按任一种次序线索化后，都很容易地求出相应地次序下地前驱和后继。 6、在采用线性探测法处理冲突地散列表中，所有同义词在表中相邻。 7、对B树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。 8、在数据表基本有序时，冒泡排序算法的时间复杂度一定接近O（n）。 9、若从某顶点开始对有向图G进行深度遍历，所得的遍历序列唯一，则可断定其弧度数为n－1。 10、AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。 二、选择题：（10分） 1、一个栈的输入序列为12345，则不可能的栈的输出序列的是（） （1）12345 （2）54321 （3）23451 （4）41235 2、一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为（） （1）0 （2）1 （3）2 （4）不确定 3、在用邻接表表示图的情况下，拓扑排序算法的时间复杂度为（） （1）O（n＋e）（2）O（n2）（3）O（n*e）（4）O（n3） 4、下列排序算法中，在每一趟都能选出一个元素放在其最终位置上，并且其时间性能受数据初始特性影响的是（） （1）直接插入排序（2）快速排序（3）直接选择排序（4）堆排序 5、下列排序算法中，依次将待排序序列中的元素和前面有序序列合并为一个新的有序序列的排序算法是（） （1）冒泡排序（2）直接插入排序（3）直接选择排序（4）快速排序 三、简要回答下列问题：（30） 1．一棵二叉树的先序、中序和后序序列如下：其中一部分为标出，请构造出该二叉树(6分) 先序： CDE GHI K 中序：CB FA JKIG 后序： EFDB JIH A 2．将下面数据表建成一个堆（70，12，20，31，1，5，44，66，61，200，30，80，150，4，28）(6分) 3．试写出取出广义表A=（（a,x,y,z）,(b,c)）中的c的复合函数(6分) 4．设目标串为S="abcaabbabcabaacbacba"，模式为P="abcabaa"，手工计算P的nextval值，并写出利用nextval值按KMP算法对目标 S进行模式匹配的过程(6分) 5．1-9，请标出各结点的值。(6分) 20后和删除关键字150后得到的B-树 （10） 10） 六、试写一个判定所给二叉树是否为二叉排序树的算法。设此二叉树采用二叉链表存储，且树中结点的关键字均不同（10） 七、已知数组A[1..n]中元素类型为integer ，设计算法将其调整为左右两部分，左边所有为奇数，右边所有为偶数，并要求算法的时间复杂度为O(n)(10) 八、设计算法求距离顶点V0的最短路径长度（以弧度为单位）为K 的所有顶点，要求尽可能节省时间（10） 东南大学2003年数据结构考研试题 一、试用面向对象编程语言（C++或Java ）描述单链表类（class List ）中的插入和删除操作。（8分） 二、将算术表达式((a+b)+c*(d+e)+f)*(g+h)转化为二叉树。（7分） 三、给出一组关键字Ｔ＝（12，2，16，30，8，28，4，10，20，6，18） ，写出用下列 算法从小到大排序时第一趟结束时的序列： （1）希尔排序（第一趟排序的增量为5）（5分） （2）链接基数排序（基数为10）（5分） 四、 在二叉树中查找值为X 的结点，试编写算法，打印值为X 的结点的所有祖先，假定值为X 的结点不多于１个，最后，试分析该算法的时间复杂性。（10分） 五、 从根到叶子的最大距离称为树的半径（radius ）。给定一个无向连通图，写一个算法以找出半径最小的生成树。(10分) 东南大学2004年数据结构考研试题 一、 简要回答下列问题（共10分，每题5分） 1、 一棵完全二叉数有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完 全二叉数有501个结点，结果如何？请写出推导过程。 2、 设模式串为P ＝“bookboxlookbood ”，手工计算P 的失效函数f （j ）的值。 二、 外存储索引为什么采用m 阶B 树（m>>2），而不用AVL 树？满二叉检索树符合B 树的定义吗？B_树的插入和删除算法适用于满二叉检 索树吗？为什么？（5分） 设有3阶B_树，如图所示，分别算出插入关键字20后所得到的B_树，以及在此基础上删除关键字150后得到的B_树。（5分） B ， C ， D ，……， Y ，Z 的序号为1，2，3，4，……25，26），其键值的输入顺序Jan ，Feb ，Mar ，Apr ，Jun ，Jul ，Aug ，Sep ，Oct ，Nov ，Dec ，用拉链法（链接法）处理冲突，要求： （1） 构造散列表（5分） （2） 求出在等概率情况下，查找成功时的平均查找长度。（5分） 四、 已知存储于数组S 中长度为n 的字符串中含有字母字符、数字字符和空格字符，请使用一种排序方法将所有字母字符移到字符串的前 部，将所有空格字符移到字符串的后部。试写出此算法。要求利用字符串的原有空间以及最少的时间代价。（10分） 五、 设计算法求中序线索二叉树中指针P 所指结点的前驱结点的指针。（10分） 东南大学2005年数据结构考研试题 一、简要回答下列问题（10分） ①含9个叶子结点的3阶B —树中至少有多少个非叶子结点？ 含10个叶子结点的3阶B —树中至多有多少个非叶子结点？ ②设目标串为S=“abcaabbabcabaacbacba ”，模式为P=“abcabaa ”,手工计算P 的失败（失效）函数f(j), 并写出利用f(j)值按KMP 算法对目标S 进行模式匹配的过程。 二、给定输入文件的关键字为（4，6，2，15，9，20，30，5，35，1，7，3，50，10，40）。设K=4，列出用置换-选择算法求初始归并段（顺串）的结果以及主要过程。（10分） 三、设二叉树结点结构为： 定义二叉树结点的平衡因子bf （T ）= h L -h R ，写一递归算法； 确定二叉树tree 中各结点的平衡因子bf ，同时返回二叉树tree 中非叶子结点的个数。（10分） 四、给定nxm 矩阵A[a..b, c..d]，并设A[i ，j]≤A[i, j +1] (a ≤i ≤b ，c ≤j ≤d-1）和A[i, j] ≤Aij +1, j] (a ≤i ≤b-1，c ≤j ≤d)。设计算法判断X 的值是否在A 中，要求时间为O(m+n)。(10分) 五、设计算法求距离顶点VO 的最短路径长度（以弧数为单位）为K 的所有顶点，要求尽可能节省时间。（10分） 2014年真题 、管路敷设技术各类管路习题到位。在管路敷设过程中，要加强看护关于管路高中资料试卷连接管口处理高中资料试卷弯扁度固定盒位置保护层防腐跨接地线弯曲半径标高等，要求技术交底。管线敷设技术包含线槽、管架等多项方式，为解决高中语文电气课件中管壁薄、接口不严等问题，合理利用管线敷设技术。线缆敷设原则：在分线盒处，当不同电压回路交叉时，应采用金属隔板进行隔开处理；同一线槽内，强电回路须同时切断习题电源，线缆敷设完毕，要进行检查和检测处理。、电气课件中调试卷调控试验；对设备进行调整使其在正常工况下与过度工作下都可以正常工作；对于继电保护进行整核对定值，审核与校对图纸，编写复杂设备与装置高中资料试卷调试方案，编写重要设备高中资料试卷试验方案以及系统启动方案；对整套启动过程中高中资料试卷电气设备进行调试工作并且进行过关运行高中资料试卷技术指导。对于调试过程中高中资料试卷技术问题，作为调试人员，需要在事前掌握图纸资料、设备制造厂家出具高中资料试卷试验报告与相关技术资料，并且了解现场设备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况，然后根据规范与规程规定，制定设备调试高中资料试卷方案。 、电气设备调试高中资料试卷技术，需要在最大限度内来确保机组高中资料试卷安全，并且尽可能地缩小故障高中资料试卷破坏范围，或者对某些异常高中资料试卷工况进行自动处理，尤其要避免错误高中资料试卷保护装置动作，并且拒绝动作，来避免不必要高中资料试卷突然停机。因此，电力高中资料试卷保护装置调试技术，要求电力保护装置做到准确灵活。对于差动保护装置高中资料试卷调试技术是指发电机一变压器组在发生内部故障时，需要进行外部电源高中资料试卷切除从而采用高中资料试卷主要保护装置。 东南大学1996数据结构试题 试题编号:451 试题名称:数据结构 一:回答下列问题(共46分) 1.线性表(a(1),a(2),……a(n))用顺序映射表示时,a(i)与a(i+1)(1<=i 《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 数据结构试卷（一） 三、计算题（每题 6 分，共24分） 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试 写出该线性表。 A 0 1 2 3 4 5 6 7 dat a nex t 2. 3.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到 的各条边。 4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的 变化。 四、阅读算法（每题7分，共14分） 1.LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a 1,a 2 , …,a n ）,写出算法执行后的 返回值所表示的线性表。 2.void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout< 山东科技大学继续教育学院 《数据结构C》模拟试题一 班级姓名学号 一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。 共 8 页 第1页 东 南 大 学 考 试 卷（A 卷） 课程名称 数据结构 考试学期 08-09-3 得分 适用专业 吴健雄学院电类 考试形式 半开卷 考试时间长度 120分钟 一、选择题（每题1分，共5分） 1．下面有关链栈的描述，对常规情况正确的是 （ ） A ．在链头插入，链尾删除。 B ．在链尾插入，链头删除。 C ．在链尾插入，链尾删除。 D ．在链头插入，链头删除。 2．对线性表进行对半搜索时，要求线性表必须（ ） A ．以数组方式存储 B ．以数组方式存储并按关键码排序 C ．以链表方式存储 D ．以链表方式存储并按关键码排序 3．对包含n 个元素的散列表进行搜索，平均搜索长度为（ ） A ．O(log 2n) B ．O(n) C ．不直接依赖于n D ．三者均不是 4．在同一个有向图中，所有结点的入度和与出度和之比为（ ） A ．1 B ．2 C ．1/2 D ．都不对 5．在具有n 个顶点的无向图中，要连通全部顶点至少需要（ ）条边。 A ．n B ．n+1 C ．n-1 D ．n/2 二、判断题（每题1分，共5分） 1．链式存储的线性表所有存储单元的地址可连续可不连续。 （ ） 2．存储有向图的邻接矩阵是对称的，所以可以仅存矩阵上三角部分。 （ ） 3．在采用闭散列法解决冲突时，不要立刻做物理删除，否则搜索时会出错。 （ ） 4．二叉树中序遍历结果序列的最后一个结点必是前序遍历的最后一个结点。 （ ） 5．堆排序的时间复杂度是O(n log 2 n)，但需要额外存储空间。 （ ） 三、填空题（每空1分，第1空、第2空为2分，共11分） 1．中缀表达式“(a+b)*d+e/(f+a*d)+c)”所对应的后缀表达式为 （1） 2．后缀表达式“ab&&ef>!||”所对应的中缀表达式为（2） 自 觉 遵 守 考 场 纪 律 如 考 试 作 弊 此 答 卷 无 效 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 结构力学复习题 一、填空题。 1、在梁、刚架、拱、桁架四种常见结构中，主要受弯的是 和 ，主要承受轴力的是 和 。 2、选取结构计算简图时，一般要进行杆件简化、 简化、 简化和 简化。 3、分析平面杆件体系的几何组成常用的规律是两刚片法则、 和二元体法则。 4、建筑物中用以支承荷载的骨架部分称为 ，分为 、 和 三大类。 5、一个简单铰相当于 个约束。 6、静定多跨梁包括 部分和 部分，内力计算从 部分开始。 7、刚结点的特点是，各杆件在连接处既无相对 也无相对 ，可以传递 和 。 8、平面内一根链杆自由运动时的自由度等于 。 二、判断改错题。 1、三刚片用三个铰两两相联必成为几何不变体系。（ ） 2、对静定结构，支座移动或温度改变会产生内力。（ ） 3、力法的基本体系必须是静定的。（ ） 4、任何三铰拱的合理拱轴都是二次抛物线。（ ） 5、图乘法可以用来计算曲杆。（ ） 6、静定结构的影响线全部都由直线段组成。（ ） 7、多跨静定梁若附属部分受力，则只有附属部分产生内力。（ ） 8、功的互等定理成立的条件是小变形和线弹性。（ ） 9、力法方程中，主系数恒为正，副系数可为正、负或零。（ ） 三、选择题。 1、图示结构中当改变B 点链杆方向（不能通过A 铰）时，对该梁的影响是（ ） A 、全部内力没有变化 B 、弯矩有变化 C 、剪力有变化 D 、轴力有变化 2、图示桁架中的零杆为（ ） A 、DC, EC, DE, DF , EF B 、DE, DF , EF C 、AF , BF , DE, DF , EF D 、DC, EC, AF , BF 3、右图所示刚架中A 支座的反力H A 、P B 、2P - C 、P - 2016年硕士研究生入学统一考试软件基础考试大纲 考试科目：程序设计基础、数据结构 考试形式和试卷结构 一、试卷满分及考试时间 试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 程序设计基础50％ 数据结构50% 程序设计基础 一、C++语言基础 考试内容 基本数据类型、enum数据类型、运算符、控制语句 考试要求 1．理解计算机信息的存储于表示，掌握C++的基本数据类型的用法. 2．掌握运算符与表达式的基本用法． 3．理解逗号表达式与条件表达式的作用． 4．掌握enum枚举类型的定义、枚举变量声明及使用. 5．掌握和运用三种(if、if…else、switch)选择语句. 6．掌握和运用三种(while、for、do…while)循环语句． 7．掌握和运用其他(break、continue)控制语句. 二、C++程序的结构(一)：函数 考试内容 函数定义、函数声明、函数调用、函数的参数传递、递归调用、函数重载、函数模板 考试要求 1.掌握函数定义的语法形式，熟练运用自定义函数来实现多函数程序设计． 2．理解函数声明的作用，掌握函数声明的用法． 3．理解函数调用的过程． 4．明确参数传递的意义，理解和掌握函数调用中参数传递的三种参数传递调用：传值调用、引用调用、传地址调用. 5．掌握和运用递归函数的概念、算法和实现方法． 6．理解函数重载的概念，掌握函数重载的实现方法． 7．理解函数模板的概念，掌握函数模板的实现方法． 三、C++程序的结构(二)：类 考试内容 抽象数据类型、类的定义、对象创建、构造函数与析构函数、公共接口函数、工具函数 类的组合、类模板 课程测试试题（卷） ----------------------以下为教师填写-------------------- I、命题院（部）：数学与计算机科学学院 II、课程名称：数据结构 III、测试学期：20 －20 学年度第学期 IV、测试对象：学院专业级班 V、问卷页数（A4）：页 VI、答卷页数（A4）：页 VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚） VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号） 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指 向的结点，则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多 可以组成( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为 ( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述 序列出发建堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四 种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 _________，在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是 ________________;删除一个结点时，需要执行的操作是 ______________________________（假设栈不空而且无需回收被删除结点）。 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 1.计算机识别、存储和加工处理的对象被统称为（）。 A ．数据 B ．数据元素 C ．数据结构 D ．数据类型 2.数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（）三方面内容。 A ．数据的逻辑结构、数据的存储结构、数据的描述 B ．数据的逻辑结构、数据的存储结构、数据的运算 C ．数据的存储结构、数据的运算、数据的描述 D ．数据的逻辑结构、数据的运算、数据的描述3．数据的逻辑结构包括（）。 A ．线性结构和非线性结构 B ．线性结构和树型结构 C ．非线性结构和集合结构 D ．线性结构和图状结构 4.（）的特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。 A ．线性结构 B ．非线性结构 C ．树型结构 D ．图状结构 5. 评价一个算法时间性能的主要标准是（）。 A ．算法易于调试 B ．算法易于理解 C ．算法的稳定性和正确性 D ．算法的时间复杂度 6. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 东北大学继续教育学院 数据结构II 试卷（作业考核线上1） A 卷 院校学号：******姓名***** （共 6 页） [ A]1．抽象数据类型的三个组成部分分别为 A．数据对象、数据关系和基本操作 B．数据元素、逻辑结构和存储结构 C．数据项、数据元素和数据类型 D．数据元素、数据结构和数据类型 [B ]2．要求相同逻辑结构的数据元素具有相同的特性，其含义为 A. 数据元素具有同一的特点 B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致 C. 每个数据元素都一样 D. 仅需要数据元素包含的数据项的个数相同 [D ]3．下列各式中，按增长率由小至大的顺序正确排列的是 A．，n！，2n ，n3/2 B．n3/2，2n，n logn，2100 C．2n，log n，n logn，n3/2 D．2100，logn, 2n, n n [B ]4. 在下列哪种情况下，线性表应当采用链表表示为宜 A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 [ C]5．设指针p指向双链表的某一结点，则双链表结构的对称性是 A. p->prior->next=p->next->next; B. p->prior->prior=p->next->prior; C. p->prior->next=p-> next->prior; D. p->next->next= p->prior->prior; [ D]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为 A. s->next=q；p->next=s->next； B. s->next=p；q->next=s->next； C. p->next=s->next；s->next=q； D. q->next=s->next；s->next=p； [A ]7. 栈和队列的共同特点是 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 [ D]8. 对于链队列，在进行插入运算时. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 [B ]9．设有一个顺序栈的入栈序列是1、2、3，则3个元素都出栈的不同排列个数为 A．4 B．5 C. 6 D. 7 [D ]10．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是 A．A，B，C，D B．D，C，B，A C. A，C，D，B D. D，A，B，C [C ]11．表达式a*(b+c)-d的后缀表达式是 A．abcd*+- B．abc*+d- C．abc+*d- D．-+*abcd [B ]12．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是 A. 空或只有一个结点 B.高度等于其结点数 C. 任一结点无左孩子 D.任一结点无右孩子 [B ]13．下面的说法中正确的是 (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。 (2)按二叉树定义，具有三个结点的二叉树共有6种。 A．(1)，(2) B．(1) C．(2) D．(1)，(2)都错 [B ]14．树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的 说法正确的是 A．树的后序遍历与其对应的二叉树的先序遍历相同 B．树的后序遍历与其对应的二叉树的中序遍历相同 C．树的先序序遍历与其对应的二叉树的中序遍历相同 D．以上都不对 [ D]15．下列说法正确的是 (1)二又树按某种方式线索化后，任一结点均有前趋和后继的线索 (2)二叉树的先序遍历序列中，任意一个结点均处于其子孙结点前 (3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值 A．(1)(2)(3) B．(1)(2) C．(1)(3) D．都不对 [ D]16. 二叉树的第k层的结点数最多为 A．2k-1 B.2K+1 《数据结构》模拟题（开卷） 一、单项选择题 1.分析下列算法suanfa1(n): void suanfa1(int n) { int i,j,x=1； for(i=0；i东南大学925结构力学考研真题及答案剖析 汇编
东南大学1996数据结构试题
数据结构模拟题(开卷)
数据结构模拟试题及答案
2017年数据结构期末考试题及答案A
东南大学十套数据结构试题及答案
《数据结构C》模拟试题
东南大学数据结构试卷
《数据结构》模拟试卷一及答案
数据结构复习资料,java数据结构期末考试
数据结构模拟试卷(含答案)
《数据结构》期末考试题及答案
东南大学期末结构力学复习题及答案
东南大学软件基础考试大纲
数据结构期末模拟试题05(有答案)
《数据结构》期末考试试卷
数据结构II A卷 东北大学(答案)
数据结构模拟题(开卷)
相关主题
文本预览