东南大学数据结构试卷

共 11 页 第1页东 南 大 学 考 试 卷（A 卷） 课程名称 数据结构 考试学期 10-11-3 得分 适用专业 吴健雄学院610 考试形式 闭卷 考试时间长度 120分钟自 觉 遵 守 考 场 纪 律 如 考 试 作 弊 此 答卷无 效一、选择题（每题1分，共5分）1．设有一个二维数组A[m][n]，如果A[0][0]的首地址为644(10进制)，A[2][2]的首地址为676，每个元素占一个字节，则A[4][5]的首地址为（）。

A．692 B．626 C．709 D．7242．若让元素1，2，3依次但并非连续进栈，则哪种出栈次序是不可能的（）A．3，2，1 B．2，1，3C．3，1，2 D．1，2，33．设完全二叉树有82个结点，从根结点开始顺序编号，根节点为1号，其他结点自上向下，同一层次自左向右连续编号。

则第41号结点的双亲结点的编号为（）A．20 B．21 C．81 D．824．采用对半搜索算法搜索长度为n的有序表，元素的平均搜索长度为（）A．O(n2) B．O(n) C．O(n log2n) D．O(log2n)5．采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）A．中序遍历B．前序遍历C．后序遍历D．按层次遍历二、判断题（每题1分，共5分）1．邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

（）2．直接选择排序是一种不稳定的排序方法。

（）3．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。

在设计再散列函数时，要求计算出的值与表的大小m互质。

（）4．连通分量是无向图中的极小连通子图。

（）5．若有一个叶子节点是二叉树中某子树的前序遍历结果序列的最后一个结点，它一定是该子树的中序遍历结果序列的最后一个结点。

（）共11页第2页三、填空题（每空1分，10分）1．每次从表的无序部分取出一个元素，把它插入到表的有序部分的适当位置，此种排序方法叫作（1）排序；每次从表的无序部分中挑选出一个最小或最大元素，把它与表的有序部分的后一元素交换，此种排序方法叫作（2）排序。

数据结构试卷（一）三、计算题（每题6 分，共24分）1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。

A 0 1 2 3 4 5 6 7data 60 50 78 90 34 40next 3 5 7 2 0 4 12.请画出下图的邻接矩阵和邻接表。

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）设链表表示的线性表为（a1,a2, …,a n）,写出算法执行后的返回值所表示的线性表。

2.void ABC(BTNode * BT){if BT {ABC (BT->left);ABC (BT->right);cout<<BT->data<<' ';}}该算法的功能是：五、算法填空（共8分）二叉搜索树的查找——递归算法:bool Find(BTreeNode* BST,ElemType& item){if (BST==NULL)return false; //查找失败else {if (item==BST->data){item=BST->data;//查找成功return ___________;}else if(item<BST->data)return Find(______________,item);else return Find(_______________,item);}//if}六、编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。

东南大学1998年研究生入学考试：数据结构试题一、简要回答下列问题(共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 Mul tilists),并说明,若已知点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 dobeginA[i]:=0;；。

东南大学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)比A VL树有效?分析其原因·(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分）。

★数据结构是一门研究非数值计算的程序设计问题中的（A ）以及它们之间的（B ）和运算的学科。

A ．操作对象 B ．计算方法 C ．逻辑存储 D ．数据映象 A ．结构 B ．关系 C ．运算 D ．算法★ 试举例说明，如果两个数据结构的逻辑结构和存储结构相同，但基本运算（操作）不同，则这两个数据结构就是不同的。

例如二叉树和二叉排序树在逻辑结构上都是二叉树，都采用二叉链表形式存储，但是对于某些运算的定义不同，例如插入操作，二叉树需指明作为哪个结点的左孩子还是右孩子插入，而二叉排序树无需指明，由二叉排序树的形状决定插入位置★算法有哪些特点？为什么说一个具备了所有特点的算法，不一定就是实用的算法？答：特点：输入、输出、确定性、有穷性、有效性；一般地说，只有多项式时间度杂度的算法才是实用的。

★如何评价算法的好坏？ 答：正确性（四个层面）；可读性；健壮性；时空效率（复杂性）。

★程序段for (i=n-1; i>=1; i++) for (j=1; j<=i; j++) if (A[j]>A[j+1])A[j]与A[j+1]对换；其中n 为正整数，则最后一行的语句频度在最坏情况下是（D ） A. O(n) B. O(nlog2n) C. O(n3) D. O(n2)★分析以递归方式求阶乘的算法的时间复杂度。

long Factorial ( long n ) {if ( n = = 1 ) return 1; // 递归终止 else return n*Factorial ( n-1); // 递归})()1())2(()1(2))1(()1())((n O O n n T O O n T O O n T O =⨯==-+⨯=-+=★分析二分查找函数的时间复杂度。

int BinarySearch(int *a, const int x, const int n) {for(int left = 0, right = n –1; left <= right;){ int middle = (left + right)/2; switch(compare(x, a[middle])){ case ‘>’: left = middle + 1; break; // x > a[middle] ca se ‘<’: right = middle – 1; break; // x < a[middle] case ‘=’: found x; // x == a[middle] } }return –1; // not found }实例特性是数组a 中元素的个数n 。

东南大学99考研题试题科目：数据结构一．简要回答下列问题（共40分）1．利用两个栈s1，s2模拟一个时，如何用栈的运算实现队列的插入删除及判队空算法。

请简述算法思想。

（7分）2．二叉树有n个顶点，编号为1，2，3，、、、、、n设：*T中任一定点V的编号等于左子树中最小编号减1；*T中任一顶点V的右子树中的最小编号等于其左子树中的最大编号加1；试描绘该二叉树。

（7分）3．设某文件经内排序后得到100个初始归并段，若使用多路归并排序算法，并要求三趟归并完成排序，归并路数最少为多少？（5分）4．若一棵树中有度数为1至m的各种结点数分别为n1，n2、、、、nm（nm表示度数n为的结点个数，试推导出该树中共有多少个叶结点n0的公式。

（8分）5．试举例分析堆排序法是否稳定（5分）6．试利用KMP算法和改进算法分别求p1=‘abaabaa’和p2=‘aabbaab’的NEXT函数和NEXTV AL函数。

（8分）二．阅读下列算法，指出算法的功能和时间复杂性（10分）procedure A(h,g:pointer);(h,g分别为单循还列表中两个结点指针)procedure B(s,q:pointer)var p:pointer;beginp:=s;while p^.next<>q do p:=p^.next;p^.next:=s;end;beginB(h,g); B(g,h);End;三．已知无向图采用邻接表存储方式，试写出删除边（ i，j ）的算法。

（10分）四．线性表中有个n元素，每个元素是一个字符，存在向量R[1。

n]中，试一写算法，使其中的字符按字母字符，数字字符和其字符的顺序排列，要求利用原空间。

且元素移动的次数最少。

（15分）五．四阶B树中（如图所述），插入关键字87，试画出插入调整后树的形状。

东南大学2000年考研专业课试卷数据结构试题一:简要回答下列问题(共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到其它各顶点的最短路径,写出执行算法过程。

东大15春学期《数据结构Ⅱ》在线作业2满分答案一,单选题1. 对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为A.（1，2，3，4，5，6，7，8）B.（1，4，3，2，5，7，8，6）C.（2，1，4，3，5，7，8，6）D.（8，7，6，5，4，3，2，1）?正确答案：C2. 下面关于线性表的叙述中，错误的是A.线性表采用顺序存储，必须占用一片连续的存储单元。

B.线性表采用顺序存储，便于进行插入和删除操作。

C.线性表采用链接存储，不必占用一片连续的存储单元。

D.线性表采用链接存储，便于插入和删除操作。

?正确答案：B3. 若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为A. 1和n+1B. 1和n/2C.－1和nD. －1和n+1?正确答案：C4. 在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是A. 访问第i个元素的前驱B.在第i个元素之后插入一个新元素C.删除第i个元素D.对顺序表中元素进行排序?正确答案：A5. 当采用分快查找时，数据的组织方式为A. 数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成若干块，每块（除最后一块外）中数据个数需相同?正确答案：B6. 在下列各种文件中，不能进行顺序查找的文件是A. 顺序文件B. 索引文件C.散列文件D.多重表文件?正确答案：C7. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为A. f,c,bB. f,d,bC. g,c,bD. g,d,b?正确答案：A8. 三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为A. 356B. 358C. 360D. 362?正确答案：B9. 已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为A. 5B. 8C. 11D. 18?正确答案：C10. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为A. n-1B. nC.n+lD.2n?正确答案：C11. 为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为。

数据结构试卷（一）三、算（每6分，共24 分）1. 在如下数 A 中存了一个性表，表指 A [0].next，写出性表。

A01234567data605078903440next35720412.画出下的接矩和接表。

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）表表示的性表（ a1,a 2, ⋯ ,a n）, 写出算法行后的返回所表示的性表。

2. void ABC(BTNode * BT){if BT {ABC (BT->left);ABC (BT->right);cout<<BT->data<<' ';}}算法的功能是：五、算法填空（共8 分）二叉搜索的找——算法:bool Find(BTreeNode* BST,ElemType& item){if (BST==NULL)return false; //查找失败else {if (item==BST->data){item=BST->data;//查找成功return ___________;}else if(item<BST->data)return Find(______________,item);else return Find(_______________,item);}//if}六、编写算法（共8 分）统计出单链表HL 中结点的值等于给定值X 的结点数。

2022年东南大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、线性表的顺序存储结构是一种（）。

A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、已知串S='aaab'，其next数组值为（）。

A.0123B.1123C.1231D.12115、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341566、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。

8、在下述结论中，正确的有（）。

①只有一个结点的二叉树的度为0。

②二叉树的度为2。

③二叉树的左右子树可任意交换。

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A.①②③B.⑦③④C.②④D.①④9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

东南大学研究生入学考试数据结构试题东南大学一九九四年攻读硕士学位研究生入学考试试题试题编号:451试题名称:数据结构一: 回答下列问题(共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.构造最佳二叉检索树的前提条件是什么?在动态情况下,一般A VL树的查询性能不如完全二叉检索树的,为什么人们却采用A VL树呢?(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 doA[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分) ________________________________________________________________ _______________试题编号:451试题名称:数据结构1.在磁带文件上进行二分查找行吗?为什么?(6分)2.分析确定下列程序中语句k:=k+1执行次数与n所成的数量级关系(即表示为O(f(n))的形式).(6分)k:=1; i:=k;while i<="" p="">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分)________________________________________________________________ _试题编号:451试题名称:数据结构一:回答下列问题(共46分)1.线性表(a(1),a(2),……a(n))用顺序映射表示时,a(i)与a(i+1)(1<=i<n)的< bdsfid="113" p=""></n)的<>物理位置相邻吗?链接表示时呢?(5分)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分)________________________________________________________________试题编号:451试题名称:数据结构一:简要回答下列问题(共32分)1.在表达式中,有的运算符要求从右到左运算,如A^B^C的计算次序应为(A^(B^C)),这在由中缀生成后缀的算法中是怎样实现的?(8分)2.给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的技术特点是什么?(8分)3.Fibonacci查找算法(fibsrch)中为什么要求m<f(a-1),试用图示说明.(8分)< bdsfid="139" p=""></f(a-1),试用图示说明.(8分)<>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分)________________________________________________________________试题编号:451试题名称:数据结构一:简要回答下列问题(共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 dobeginA[i]:=0;i:=i-1;end;A[i]:=1;end;四:下面是一改进了的快速分类算法:1 procedure qsort1(var list:afile;m,n:integer);2 (设list[m].key<list[n+1].key)< bdsfid="180" p=""></list[n+1].key)<>3 var i,j,k:integer;4 begin5 while m<="" p="">6 begin7 i:=m;j:=n+1;k:=list[m].key;8 repeat9 repeat i:=i+1 until list[i].key>=k;10 repeat j:=j-1 until list[j].key<=k;11 if i<="" p="" then="">12 until i>=j;13 interchange(list[m],list[j]);14 if n-j>=j-m15 then begin qsort1(list,m,j-1);m:=j+1;end16 else begin qsort1(list,j+1,n);n:=j-1;end17 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分)________________________________________________________________ _____东南大学一九九九年攻读硕士学位研究生入学考试试题试题编号:451试题名称:数据结构注意事项:(1) 答卷上需写清题号,不必抄题;回答问题字迹工整,卷面清洁.(2) 编程中所用的数据结构及主要变量需加以说明,必要时程序中加以注释.一:简要回答下列问题(共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;beginp:=s;while p^.next<>q do p:=p^.next;p^.next:=s;end; (of B)beginB(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分)________________________________________________________________ _____东南大学二○○○年攻读硕士学位研究生入学考试试题科目编号:451科目名称:数据结构一:简要回答下列问题(共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分)________________________________________________________________ _____二○○一年的题目（缺两道小题):一:1.设胜者树(selection tree)由k个记录缓冲区和k-1个非叶结点构成.概念上非叶结点表示其两个子女中关键字较小者,而实际上非叶结点存放的是什么? 3.给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的技术特点是什么?5.是一道关于Huffman树中叶子结点和非叶结点数量关系的计算题,具体题目记不得了.6.求有向图中任意一对顶点之间最短路径的弗洛伊德算法(allcosts-Floyd)中,要求有向图满足什么前提条件?二:在二叉树的结点结构中增加一个域:leftsize,t^.leftsize表示t结点的左子树中结点的总个数,试编写算法alloc(k),在二叉树中查找中序序号为k的结点,要求时间复杂度为O(log2(n)).三:编写算法输出从n个自然数中取k个(k<=n)的所有组合.例如,当n=5,k=3时,你的算法应该输出:543,542,541,532,531,521,432,431,421,321.四:设有向图G用邻接表的方式存储,u,v是G中的任意两个结点,写一算法,求出G中从u到v的所有简单路径.五:下面是一改进了的快速排序算法,试补充其中的空白语句,并分析该算法所需的最大递归空间是多少?procedure qsort1(var list:afile;m,n:integer);(设list[m].key<list[n+1].key)< bdsfid="324" p=""></list[n+1].key)<>var i,j,k:integer;beginwhile m<="" p="">begini:=m;j:=n+1;k:=list[m].key;repeatrepeat i:=i+1 until list[i].key>=k;repeat j:=j-1 until list[j].key<=k;if i<="" p="" then="">until i>=j;interchange(list[m],list[j]);if n-j>=j-mthen begin qsort1(list,m,___);______;endelse begin qsort1(list,___,n);______;endend;(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中.。

东南大学1995年研究生入学考试：数据结构试题1、在磁带文件上进行二分查找行吗?为什么?(6分)2、分析确定下列程序中语句k:=k+1执行次数与n所成的数量级关系(即表示为O(f(n))的形式)。

(6分)k:=1；i:=k；while i<n dobegin 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的邻接多表(adjacencymultilists)，要求该算法的时间复杂性为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，S P={123，132，213，231，321}、问:IP包含于SP成立否?证明你的结论。

(16分)9、设记录R[i]的关键字为R[i].key(1<=i<=k)，树结点T[i](1<=i<=k-1)指向败者记录，T&#0；为全胜记录下标。

写一算法产生对应上述R[i](1<=i<=k)的败者树(tree ofloser)，要求除R[1..k]和T[0..k-1]以外，只用O(1)辅助空间。

东南大学1997年数据结构专业课考研真题试卷
一:简要回答下列问题(共32分)
1.在表达式中,有的运算符要求从右到左运算,如A^B^C的计算次
序应为(A^(B^C)),这在由中缀生成后缀的算法中是怎样实现的?(8分)
2.给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的技术特点是什么?(8分)
3.Fibonacci查找算法(fibsrch)中为什么要求m
4.为什么在倒排
文件(invertedfiles)组织中,实际记录中的关键字域(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分)。