东南大学十套数据结构试题及答案

共 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的结点数。

一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（）。

A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。

A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。

A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。

数据结构试题及答案(10套)数据结构试题及答案(10套)根据您的需求，我为您准备了10套数据结构试题及答案。

每套试题包含以下几个部分：选择题、填空题、编程题及答案解析。

下面是试题的具体内容：第一套试题：选择题：1. 在数据结构中，什么是栈？A. 先进先出（FIFO）的数据结构B. 后进先出（LIFO）的数据结构C. 随机访问的数据结构D. 无序排列的数据结构2. 以下哪种操作与队列的特性不相符？A. 入队操作B. 出队操作C. 查找操作D. 获取队首元素填空题：1. ______ 是一种动态集合，支持插入、删除和查找等操作。

2. 在二叉搜索树中，中序遍历的结果是________。

编程题：实现一个栈的数据结构，并包含以下操作：- push(x)：将元素 x 压入栈中- pop()：删除栈顶的元素并返回该元素- top()：获取栈顶元素的值- empty()：检查栈是否为空答案解析：选择题：B、C填空题：1. 集合 2. 升序序列编程题：略第二套试题：选择题：1. 以下哪个数据结构是一种广度优先搜索的应用？A. 栈B. 队列C. 堆D. 链表2. 在链表中，如果要删除一个节点，只给出该节点的指针，那么需要通过什么方式完成删除操作？A. 直接删除该节点B. 指向该节点的前一个节点的指针C. 指向该节点的后一个节点的指针D. 无法完成删除操作填空题：1. 树是一种________的数据结构。

2. 二叉树每个节点最多有______个子节点。

编程题：实现一个队列的数据结构，并包含以下操作：- enqueue(x)：将元素 x 入队- dequeue()：删除队首的元素并返回该元素- peek()：获取队首元素的值- is_empty()：检查队列是否为空答案解析：选择题：B、B填空题：1. 分层组织 2. 2编程题：略（以下部分省略）通过以上的题目，您可以对数据结构的知识点进行综合练习和复习。

每套试题包含了不同难度和类型的题目，能够帮助您全面了解和掌握数据结构的概念和操作。

★数据结构是一门研究非数值计算的程序设计问题中的（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 。

十套数据结构试题及答案1.请设计一个栈结构，满足以下要求：-支持常规的入栈和出栈操作。

-支持获取当前栈中最小元素的操作，并要求时间复杂度为O(1)。

答案：可以使用两个栈，一个用于存储数据，另一个用于维护当前栈中的最小值。

每次入栈时，比较要入栈的元素与当前栈中的最小值，将较小的值入最小栈。

出栈时，同时从数据栈和最小栈中出栈，保持栈的一致性。

2.请用链表实现一个队列结构，满足以下要求：-支持常规的入队和出队操作。

-支持获取队列中的最大值和最小值的操作，并要求时间复杂度为O(1)。

答案：使用双向链表实现队列，每个结点保存当前最大值和最小值，入队时更新队列相关结点的最大值和最小值，出队时删除队首结点，并更新队列最大值和最小值。

3. 设计一个LRU（Least Recently Used）缓存结构，要求如下：-缓存结构内存固定大小。

-当缓存结构满时，插入新的数据时需要剔除最近最少使用的数据。

答案：可以使用哈希表和双向链表来实现。

哈希表用于实现快速查找，双向链表用于保存数据的访问顺序。

当一些数据被访问时，根据哈希表快速定位到对应的结点，并将该结点移到链表头部。

当需要插入新数据时，如果缓存容量已满，则将链表尾部的结点剔除。

4.设计一个支持并发访问的并且具有线程安全性的哈希表结构。

答案：可以使用读写锁来保证线程安全性。

读操作时，多个线程可以同时读取，不会产生冲突；写操作时，需要获取写锁，保证同时只能有一个线程执行写操作。

5.实现一个拓扑排序算法，对有向无环图进行排序。

答案：可以使用DFS和栈结构来实现。

从任意一个未被访问的结点开始，递归地进行深度优先，并将访问完毕的结点入栈。

最终得到的栈中的结点顺序即为拓扑排序结果。

6.设计一个支持高效插入与删除的动态数组结构。

答案：可以使用动态平衡二叉树（例如AVL树）来实现。

插入与删除操作的时间复杂度为O(log n)，并保持树的平衡性，避免树的高度过大。

7.设计一个支持高效查找的散列表结构。

最新十套数据结构试题及答案最新十套数据结构试题及答案数据结构试卷（一）.................1数据结构试卷（二）.. (4)数据结构试卷（三）.................6数据结构试卷（四）.................8数据结构试卷（五）................11数据结构试卷（六）................14数据结构试卷（七）................16数据结构试卷（八）................18数据结构试卷（九）................20数据结构试卷（十）. (23)数据结构试卷（一）参考答案.........26数据结构试卷（二）参考答案 (27)数据结构试卷（三）参考答案.........28数据结构试卷（四）参考答案.........30数据结构试卷（五）参考答案.........32数据结构试卷（六）参考答案.........33数据结构试卷（七）参考答案.........36数据结构试卷（八）参考答案.........37数据结构试卷（九）参考答案.........38数据结构试卷（十）参考答案.........39数据结构试卷（一）一、单选题（每题2分，共20分）1.栈和队列的共同特点是()。

a.只允许在端点处插入和删除元素b.都是先进后出c.都是先进先出d.没有共同点2.用链接方式存储的队列，在展开填入运算时().a.仅修改头指针b.头、尾指针都要修改c.仅修改尾指针d.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？()a.队列b.栈c.线性表d.二叉树4.设有一个二维数组a[m][n]，假设a[0][0]存放位置在644(10)，a[2][2]存放位置在676(10)，每个元素占一个空间，问a[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

a．688b．678c．692d．6965.树最适合用来表示()。

数据结构试题及答案(10套最新)数据结构试题及答案(10套最新)第一套试题：问题一：什么是数据结构？数据结构的作用是什么？回答：数据结构是一种组织和存储数据的方式，它关注数据元素之间的关系以及对数据元素的操作。

数据结构的作用包括提供高效的数据存储和访问方式，减少资源消耗，简化问题的解决方法，提高算法的性能和程序的可读性。

问题二：请列举几种常见的线性数据结构，并简要介绍它们的特点。

回答：常见的线性数据结构包括数组、链表和栈。

数组是一种连续存储数据元素的结构，具有随机访问的特点；链表是一种通过指针相连的数据元素，可以灵活地插入和删除元素；栈是一种遵循先进后出原则的数据结构，常用于解决递归问题。

问题三：请说明二叉树的定义及其性质。

回答：二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点。

二叉树具有以下性质：每个节点最多有两个子节点，分别称为左子节点和右子节点；左子树和右子树都是二叉树；二叉树的节点个数为n，边的个数为n-1。

问题四：在数组中查找一个元素的时间复杂度是多少？为什么？回答：在数组中查找一个元素的时间复杂度是O(n)，其中n是数组的长度。

因为在数组中查找元素需要按照索引一个一个比较，最坏情况下需要比较n次才能找到目标元素。

问题五：请解释堆排序算法的原理及时间复杂度。

回答：堆排序算法利用堆这种数据结构进行排序。

首先将待排序的元素构建成一个大顶堆，然后将堆顶元素与最后一个元素交换，继续调整堆，再取出堆顶元素与倒数第二个元素交换，依次执行，最后得到从小到大排序的序列。

堆排序的时间复杂度为O(nlogn)。

第二套试题：问题一：请解释图的邻接矩阵和邻接表表示法。

回答：图的邻接矩阵表示法是使用二维数组来表示图的连接关系，数组中的元素表示相应节点之间的边的关系。

邻接表表示法使用链表来表示图的连接关系，链表中的元素表示相邻节点之间的边的关系。

问题二：请说明深度优先搜索算法的原理及其应用。

回答：深度优先搜索（DFS）算法是一种遍历或搜索图的算法，其原理是从起始节点开始，依次深入到尽可能远的节点，直到无法继续深入为止，然后回溯到上一个节点，再继续深入其他未访问过的节点。

数据结构试卷（九） 数据结构试卷（十）................ ................22 24 26 27 29 31 33 34 36 37 38 39数据结构试卷（一）参考答案 数据结构试卷（二）参考答案数据结构试卷（三）参考答案 数据结构试卷（四）参考答案 数据结构试卷（五）参考答案 数据结构试卷（六）参考答案 数据结构试卷（七）参考答案 数据结构试卷（八）参考答案 数据结构试卷（九）参考答案 数据结构试卷（十）参考答案........ ........ ........ ........ ........ ........ ........ ........ ........ ........数据结构试卷（一） ...................................数据结构试卷（三） 数据结构试卷（四） 数据结构试卷（五） 数据结构试卷（六） 数据结构试卷（七） 数据结构试卷（八） 0 数据结构试卷（二） 4 7 10 13 15 18 20.................. ................. ................. ................. ................. .................数据结构试卷（一）20 分）A )； 一，单项题（每题 2 分，共 栈和队列的共同特点是 ( A. 只答应在端点处插入和删除元素 B. 都是先进后出 C.都是先进先出 D. 没有共同点1. 用链接方式储备的队列，在进行插入运算时( D ).头，尾指针都要修改仅修改头指针 仅修改尾指针 A. C.B. D. 头，尾指针可能都要修改 2. 以下数据结构中哪一个是非线性结构？ ( D )A. 队列 3. 设有一个二维数组B. 栈 A[ m][ n]，假设C. 线性表 A[0][0] 存放位置在D. 二叉树644(10)，A[2][2] 存放位置在 676(10)，每个元素占一个空间，问 （ C ）；A ．688 A[3][3] (10) 存放在什么位置？脚注 (10) 表示用 10 进制表示B ． 678 )；C ． 692D ． 696 4. 树最适合用来表示 ( C A. 有序数据元素C. 元素之间具有分支层次关系的数据B. 无序数据元素D.元素之间无联系的数据5. 二叉树的第 k 层的结点数最多为 ( D ).kk-1． 2 -1 A B.2K+1D. 26. 如有 18 个元素的有序表存放在一维数组 中，第一个元素放 A[1] 中，现进行二分A[19] 查找，就查找 A ［ 3］的比较序列的下标依次为 ( D ) A. 1 ， 2， 3 C. 9， 5， 3 B. 9 ， 5， 2， 3D. 9 ，4， 2， 37. 对 n 个记录的文件进行快速排序，所需要的帮助储备空间大致为（C ）（ n2）（ 1） B. O （ n ） C. O （ 1og 2n ） A. O D. O8. 对于线性表（ 7，34，55，25，64，46， 20，10）进行散列储备时，如选用 H （ K ）=K %9作为散列函数，就散列地址为 1 的元素有（ ）个，D ． 4 ) 条边才能确保是一个连通图；D ． 1 ． 2 ． 3 (A B C9. 设有 6 个结点的无向图，该图至少应有 A三，运算题（每题 1.在如下数组 6 分，共 24 分）A 中链接储备了一个线性表，表头指针为A [0].next ，试写出该线性表； A 0 1 2 3 4 5 6 7data605078903440next 35720410 1 1 11111111111111线性表为：（78，50，40，60，34，90 ）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};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边；用克鲁斯卡尔算法得到的最小生成树为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204.画出向小根堆中加入数据4, 2, 5, 8, 3 时，每加入一个数据后堆的变化；见图12244222图12524445458832354.图11四，阅读算法（每题7 分，共14 分）1. LinkList mynote(LinkList L){//L 是不带头结点的单链表的头指针if(L&&L->next){q=L ；L=L －>next ；p=L ；S1：S2：while(p －>next) p=p －>next ；p－>next=q ；q－>next=NULL ；}return L；}请回答以下问题：（1）说明语句S1 的功能；查询链表的尾结点（2）说明语句组S2 的功能；将第一个结点链接到链表的尾部，作为新的尾结点,a n）,写出算法执行后的返回值所表示的线性（3）设链表表示的线性表为（a1,a2,表；返回的线性表为（a2,a3, ,a n,a1）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;//returnelse if(item<BST->data) return Find(查找胜利;}trueBST->left _ _,item);else return Find( _BST->right ,item);}//if}六，编写算法（共8 分）统计出单链表HL 中结点的值等于给定值X 的结点数；int CountX(LNode* HL,ElemType x)int CountX(LNode* HL,ElemType x)int i=0; LNode* p=HL;//i 为计数器{while(p.=NULL){ if (P->data==x) i++;p=p->next;}//while, 出循环时i 中的值即为x 结点个数return i;}//CountX数据结构试卷（二）一，挑选题(24 分)1．下面关于线性表的表达错误选项（）；(A) 线性表采纳次序储备必需占用一片连续的储备空间(B) 线性表采纳链式储备不必占用一片连续的储备空间(C) 线性表采纳链式储备便于插入和删除操作的实现(D) 线性表采纳次序储备便于插入和删除操作的实现2．设哈夫曼树中的叶子结点总数为m，如用二叉链表作为储备结构，就该哈夫曼树中总共有（）个空指针域；(A) 2m-1 3．设次序循环队列(B) 2m (C) 2m+1 (D) 4mF 和R，头指针F 总是指向队头元素Q[0 ：M-1] 的头指针和尾指针分别为的前一位置，尾指针R 总是指向队尾元素的当前位置，就该循环队列中的元素个数为（）；(C) (R-F+M) ％M ABCD ，前序遍历序列为(D) (F-R+M) ％MCABD ，就后序遍历该二叉树(A) R-F (B) F-R 4．设某棵二叉树的中序遍历序列为得到序列为（(A) BADC ）；(B) BCDA (C) CDAB (D) CBDA）条边；(D) n -15．设某完全无向图中有(A) n(n-1)/26．设某棵二叉树中有(A) 9n 个顶点，就该完全无向图中有（22 (B) n(n-1) (C) n2000 个结点，就该二叉树的最小高度为（）；(B) 10 (C) 11 (D) 127．设某有向图中有(A) n-1 n 个顶点，就该有向图对应的邻接表中有（）个表头结点；(D) 2n-1(B) n (C) n+18．设一组初始记录关键字序列(5 ，2，6，3，8) ，以第一个记录关键字 5 为基准进行一趟快速排序的结果为（(A) 2 ，3，5，8，6(C) 3 ，2，5，6，8 三，应用题(36 分) ）；(B) 3 ，2，5，8，6(D) 2 ，3，6，5，81．设一组初始记录关键字序列为(45 ，80，48，40，22，78) ，就分别给出第 4 趟简洁挑选排序和第 4 趟直接插入排序后的结果；(22 ，40，45，48，80，78) ，(40 ，45，48，80，22，78)2．设指针变量p 指向双向链表中结点A，指针变量q 指向被插入结点B，要求给出在结点 Allink和rlink）；的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;3．设一组有序的记录关键字序列为二分查找，要求运算出查找关键字度；2,ASL=91*1+2*2+3*4+4*2)=25/9 (13 ，18，24，35，47，50，62，83，90) ，查找方法用62 时的比较次数并运算出查找胜利时的平均查找长4．设一棵树T 中边的集合为{(A ，B)，(A ，C) ，(A ，D) ，(B ，E)，(C，F)，(C，G)} ，要求用孩子兄弟表示法（二叉链表）表示出该树的储备结构并将该树转化成对应的二叉树；树的链式储备结构略，二叉树略5．设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合；E={(1 ，3)，(1，2)，(3，5)，(5，6)，(6，4)}6．设有一组初始记录关键字为(45 ，80，48，40，22，78) ，要求构造一棵二叉排序树并给出构造过程；四，算法设计题(16 分)1．设有一组初始记录关键字序列（K1，K2，，K n），要求设计一个算法能够在O(n) 的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K i ，右半部分的每个关键字均大于等于K i ；设有一组初始记录关键字序列（K1，K2，，K n），要求设计一个算法能够在O(n) 的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K i ，右半部分的每个关键字均大于等于K i；void quickpass(int r[], int s, int t){int i=s, j=t, x=r[s];while(i<j){while (i<j && r[j]>x) j=j-1; if (i<j) {r[i]=r[j];i=i+1;}while (i<j && r[i]<x) i=i+1; if (i<j) {r[j]=r[i];j=j-1;}}r[i]=x;}2．设有两个集合 A 和集合B，要求设计生成集合C=A∩B 的算法，其中集合A，B 和C用链式储备结构表示；设有两个集合A 和集合B，要求设计生成集合C=A∩B 的算法，其中集合A，B 和C 用链式存储结构表示；typedef struct node {int data; struct node *next;}lklist;void intersection(lklist *ha,lklist *hb,lklist *&hc){lklist *p,*q,*t;for(p=ha,hc=0;p.=0;p=p->next){for(q=hb;q.=0;q=q->next) if (q->data==p->data) break;if(q.=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} }}数据结构试卷（三）一，挑选题 ( 每题 1 分，共 20 分 ) 1．设某数据结构的二元组形式表示为A=(D ， R)， D={01 ， 02， 03， 04， 05， 06， 07， 08，09} ， R={r} ， r={<01 ， 02>， <01 ， 03>， <01 ，04>， <02， 05>，<02 ， 06>， <03 ， 07>， <03 ，08>， <03， 09>} ，就数据结构 A 是（ ）； (A) 线性结构 树型结构 ）(C) 物理结构 (D) 图型结构(B) 2．下面程序的时间复杂为（for （ i=1 ， s=0； i<=n ； i++ ） {t=1 ； for(j=1 ； j<=i ； j++) t=t*j ； s=s+t ；}234(A) O( n) 3．设指针变量 (B) O(n )p 指向单链表中结点 (C) O(n )A ，如删除单链表中结点(D) O(n )A ，就需要修改指针的操作序列为（）；(A ) q=p->next； p->data=q->data (B ) q=p->next ； q->data=p->data (C ) q=p->next ； p->next=q->next (D ) q=p->next ； p->data=q->data ； p->next=q->next ； p->next=q->next ； free(q) ；； free(q) ； ； free(q) ； free(q) ； ； 4．设有 n 个待排序的记录关键字，就在堆排序中需要（）个帮助记录单元； 2(A) 1(B) n(C) nlog 2n (D) n5．设一组初始关键字记录关键字为录的一趟快速排序终止后的结果为(20 ，15，14，18， 21， 36，40，10) ，就以 20 为基准记( ) ；(A) 10 ， 15， 14， 18，20， 36， 40， 21 (B) 10 ， 15， 14， 18， 20， 40， 36， 21 (C) 10 ， 15， 14， 20， 18， 40， 36， 2l (D) 15 ， 10， 14， 18， 20， 36， 40， 216．设二叉排序树中有 (A) O(1) n 个结点，就在二叉排序树的平均平均查找长度为（）；2(B) O(log2n) (C) (D) O(n )7．设无向图 G 中有个顶点 e 条边，就其对应的邻接表中的表头结点和表结点的个数分别 n 为（ ）； (A) n ， e 8. 设某强连通图中有 (A) n(n-1) (B) e ， n (C) 2n ， e (D) n ，2e ）条边； (D) n(n+1)n 个顶点，就该强连通图中至少有（(B) n+1(C) n9．设有 5000 个待排序的记录关键字，假如需要用最快的方法选出其中最小的10 个记录关键字，就用以下（ (A) 快速排序 10. 以下四种排序中（(A) 插入排序）方法可以达到此目的； (B) 堆排序 (C) 归并排序 插入排序 (D) ）的空间复杂度最大；(B) 冒泡排序堆排序归并排序(C) (D) 三，运算题 ( 每题 分，共 30 分 )10 1.已知二叉树的前序遍历序列是 AEFBGCDHIKJ ，中序遍历序列是 EFAGBCHKIJD ，画出此二叉树，并画出它的后序线索二叉树；ABECGFNULLDHF KJ2．已知待散列的线性表为（ 36， 15， 40， 63， 22），散列用的一维地址空间为[0 ..6]，假定选用的散列函数是 H （ K ） = K mod 7 ，如发生冲突采纳线性探查法处理，试：.冲突H(36)=36 mod 7=1;H(15)=15 mod 7=1; H １ (22)=(1+1) mod 7=2;.冲突 H 2 (22)=(2+1) mod 7=3;H １ (15)=(1+1) mod 7=2;H(40)=40 mod 7=5; H(63)=63 mod 7=0; .冲突H(22)=22 mod 7=1;（ 1）运算出每一个元素的散列地址并在下图中填写出散列表： `0 1234 405663361522（ 2）求出在查找每一个元素概率相等情形下的平均查找长度； 1 2 1 51 3ASL=3．已知序列（ 10，18， 4， 3， 6，12，1，9，18，8）请用快速排序写出每一趟排序的结果；(8,9,4,3,6,1),10,(12,18,18) (1,6,4,3),8,(9),10,12,(18,18) 1,(3,4,6),8,9,10,12,18,(18) 1,3,(4,6),8,9,10,12,18,18 1,3, 4,6,8,9,10,12,18,18四，算法设计题 ( 每题 15 分，共 30 分 )1． 设计在单链表中删除值相同的余外结点的算法；设计在单链表中删除值相同的余外结点的算法；typedef int datatype;typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) {lklist *p,*q,*s;for(p=head;p.=0;p=p->next) {for(q=p->next,s=q;q.=0; )if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;}}}2．设计一个求结点设计一个求结点x 在二叉树中的双亲结点算法；x 在二叉树中的双亲结点算法；typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;bitree *q[20]; int r=0,f=0,flag=0;void preorder(bitree *bt, char x){if (bt.=0 && flag==0)if (bt->data==x) { flag=1; return;}else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } }void parent(bitree *bt,char x){int i;preorder(bt,x);for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break;if (flag==0) printf("not found x\n");else if (i<=r) printf("%c",bt->data); else printf("not parent");}数据结构试卷（四）一，挑选题 ( 每题 1 分共 20 分 )1．设一维数组中有 (A) O(n)n 个数组元素，就读取第i 个数组元素的平均时间复杂度为（）；2(B) O(nlog2n) (C) O(1)(D) O(n ) ）个结点；(D) 2 -12．设一棵二叉树的深度为 k ，就该二叉树中最多有（kk-1k(A) 2k-1 3．设某无向图中有 (A) n (B) 2 (C) 2 n 个顶点 e 条边，就该无向图中全部顶点的入度之和为（）；(B) e (C) 2n(D) 2e4．在二叉排序树中插入一个结点的时间复杂度为（ ）；2n)2(A) O(1) (B) O(n)(C) O(log (D) O(n )5．设某有向图的邻接表中有n 个表头结点和 m 个表结点，就该图中有（）条有向边；(A) n(B) n-1 (C) m (D) m-16．设一组初始记录关键字序列为(345 ，253，674，924，627) ，就用基数排序需要进行 （ ）趟的安排和回收才能使得初始关键字序列变成有序序列；(A) 3(B) 4(C) 5(D) 87．设用链表作为栈的储备结构就退栈操作（(A) 必需判别栈是否为满(C) 判别栈元素的类型 ）； (B) 必需判别栈是否为空 (D) 对栈不作任何判别8．以下四种排序中（(A) 快速排序9．设某二叉树中度数为 ）的空间复杂度最大；(B) 冒泡排序0 的结点数为 (C) 希尔排序堆N l ，度数为 2 的结点数为 (D) N 0，度数为 1 的结点数为 N 2，就以下等式成立的是（ ）；(A) N 0=N 1+1 10. 设有序次序表中有 (B) N 0=N l +N 2(C) N 0=N 2+1(D) N 0=2N 1+ln 个数据元素，就利用二分查找法查找数据元素X 的最多比较次数不超过（ (A) log）； 2n+1(B) log2n-1 (C) log 2n (D) log 2(n+1)三，运算题 ( 每题 分，共 30 分 ) 10 1，画出广义表 的头尾链表储备结构；LS=(( ) , (e) , (a , (b , c , d ))) 1 1----> 1LS1^ ^----> 1 ----> 11^ ^ 0 0 ea1----> ----> 1 1 ^ b0 0 cd0 2，下图所示的森林：(1) 求树（ a ）的先根序列和后根序列； BDEFCA ； (2) ABCDEFGHIJK;林转换为相应的二叉树；(1) ABCDEF;BDEFCAIJKHGAGBC HIDJEF K(2) 求森林先序序列和中序序列； BDEFCA ；ABCDEF;（ 3）将此森林转换为相应的二叉树；A GBC H FD EIJ (b)K(a)(2) ABCDEFGHIJK;BDEFCAIJKHG 林转换为相应的二叉树；AGBC HIDJEF K23，设散列表的地址范畴是 表处理冲突，请画出元素 ，散列函数为 H （ key ） = （ key +2） MOD 9,并采纳链 [ 0..9 ] 7， 4， 5， 3， 6， 2，8， 9 依次插入散列表的储备结构； H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6540 ^1 2 3 4 5 6 7 89 ^63 89^^ ^7^2^ ^ ^四，算法设计题( 每题10 分，共30 分)1．设单链表中有仅三类字符的数据元素( 大写字母，数字和其它字符) ，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符；设单链表中有仅三类字符的数据元素( 大写字母，数字和其它字符) ，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符；typedef char datatype;typedef struct node {datatype data; struct node *next;}lklist;void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc){lklist *p; ha=0,hb=0,hc=0;for(p=head;p.=0;p=head){head=p->next; p->next=0;if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;}else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;}}}设计在链式储备结构上交换二叉树中全部结点左右子树的算法；2.设计在链式储备结构上交换二叉树中全部结点左右子树的算法；typedef struct node {int data; struct node *lchild,*rchild;} bitree;void swapbitree(bitree *bt){bitree *p;if(bt==0) return;swapbitree(bt->lchild); swapbitree(bt->rchild);p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p;}在链式储备结构上建立一棵二叉排序树；3.在链式储备结构上建立一棵二叉排序树；#define n 10typedef struct node{int key; struct node *lchild,*rchild;}bitree;void bstinsert(bitree *&bt,int key){if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;}else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key);}void createbsttree(bitree *&bt){int i;for(i=1;i<=n;i++) bstinsert(bt,random(100));}数据结构试卷（五）一，挑选题 (20 分 ) 1．数据的最小单位是（(A) 数据项）； (B) 数据类型(C) 数据元素(D) 数据变量2．设一组初始记录关键字序列为(50 ， 40， 95， 20， 15， 70， 60， 45) ，就以增量 d=4 的一趟希尔排序终止后前 (A) 40 ， 50， 20， 95 (C) 15 ， 20， 40， 454 条记录关键字为（ (B) 15 (D) 45 ）；， 40， 60， 20 ，40， 15， 20 3．设一组初始记录关键字序列为 (25， 50， 15，35，80， 85，20，40，36，70)，其中含有 5 个长度为 果为（2 的有序子表，就用归并排序的方法对该记录关键字序列进行一趟归并后的结）；(A) 15 ，25， 35 ， 50， 20， 40， 80， 85， 36， 70 (B) 15 ，25， 35，50， 80，20， 85， 40， 70， 36 (C) 15 ，25， 35，50， 80，85， 20， 36， 40， 70 (D) 15 ，25， 35，50， 80，20， 36，40， 70，85 4．函数 substr( “DATASTRUCT U ”R E ， 5， 9) 的返回值为（）；(A) “STRUCTUR ”E (C) “ASTRUCTU ”R 5．设一个有序的单链表中有就该操作的时间复杂度为（“ DATA ”(B) (D) “ DATASTRUCT U ”REn 个结点， 现要求插入一个新结点后使得单链表仍旧保持有序，）；2(A) O(log2n)(B) O(1) (C) O(n )(D) O(n)6．设一棵 m 叉树中度数为 点数为 Nm ，就 N =（ 0 的结点数为 ）；N 0，度数为 1 的结点数为 N l ， ，度数为 m 的结 (A) N l +N 2+ +Nm (B) l+N 2+2N 3+3N 4++(m-1)Nm (C) N 2+2N 3+3N 4+ +(m-1)Nm (D) 2N l +3N2+ +(m+1)NmX 最多需要比较（(D) 17．设有序表中有 (A) 251000 个元素，就用二分查找查找元素）次；(B) 10(C) 78．设连通图 G 中的边集 E={(a ，b)，(a ， e)，(a ， c)，(b ， e)，(e ， d)，(d ， f)， (f ，c)} ，就从顶点 a 动身可以得到一种深度优先遍历的顶点序列为（ ）；(A) abedfc9．设输入序列是 (B) acfebd(C) aebdfc(D) aedfcb1， 2，3，， n ，经过栈的作用后输出序列的第一个元素是 ）；n ，就输出序列中第 (A) n-ii 个输出元素是（ (B) n-1-i(D) 不能确定(C) n+1-i10 设一组初始记录关键字序列为(45 ， 80， 55， 40，42， 85) ，就以第一个记录关键字45为基准而得到一趟快速排序的结果是（ (A) 40 ， 42， 45， 55， 80， 83 (C) 42 ， 40， 45，55， 80， 85 ）；(B) 42 ， 40， 45， 80， 85， 88 (D) 42 ， 40， 45， 85， 55， 80三，应用题 (32 分 ) 1.设某棵二叉树的中序遍历序列为DBEAC ，前序遍历序列为 ABDEC ，要求给出该二叉树的的后序遍历序列； DEBCA2. 设无向图G（如右图所示），给出该图的最小生成树上边的集合并运算最小生成树各边上的权值之和；E={(1,5),(5,2),(5,3),(3,4)},W=103. 设一组初始记录关键字序列为(15 ，17，18，22，35，51，60) ，要求运算出胜利查找时的平均查找长度；ASL=(1*1+2*2+3*4)/7=17/74. 设散列表的长度为8，散列函数H(k)=k mod7，初始记录关键字序列为(25 ，31，8，27，13，68) ，要求分别运算出用线性探测法和链地址法作为解决冲突方法的平均查找长度；ASL1=7/6 ，ASL2=4/3四，算法设计题(28 分)1．设计判定两个二叉树是否相同的算法；设计判定两个二叉树是否相同的算法；typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;int judgebitree(bitree *bt1,bitree *bt2){if (bt1==0 && bt2==0) return(1);else if (bt1==0 || bt2==0 ||bt1->data.=bt2->data) return(0);else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}2．设计两个有序单链表的合并排序算法；设计两个有序单链表的合并排序算法；void mergelklist(lklist *ha,lklist *hb,lklist *&hc){lklist *s=hc=0;while(ha.=0 && hb.=0)if(ha->data<hb->data){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;}else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;}if(ha==0) s->next=hb; else s->next=ha;}数据结构试卷（六）一，挑选题 (30 分 )1． 设一组权值集合 W={2， 3， 4，5，6} ，就由该权值集合构造的哈夫曼树中带权路径长度之和为（ (A) 20）；(B) 30(C) 40）； ，63] (D) 452．执行一趟快速排序能够得到的序列是（(A) [41 ，12， 34， 45，27] 55 [72 (B) [45 ， 34， 12， 41] 55 [72 ，63， 27] (C) [63 ， 12， 34， 45， 27] 55 [41 ， 72] (D) [12 ， 27， 45， 41] 55 [34 3．设一条单链表的头指针变量为(A) head==0(C) head->next==head，63， 72] head 且该链表没有头结点，就其判空条件是（(B) head->next==0 (D) head.=0 ）；4．时间复杂度不受数据初始状态影响而恒为O(nlog 2n) 的是（ ）； 快速排序(A) 堆排序(B) 冒泡排序(C) 希尔排序(D) 5．设二叉树的先序遍历序列和后序遍历序列正好相反，就该二叉树满意的条件是（）； (A) 空或只有一个结点 (C) 任一结点无左孩子 高度等于其结点数 任一结点无右孩子(B) (D) 6．一趟排序终止后不肯定能够选出一个元素放在其最终位置上的是（）；希尔排序）； (A) 堆排序 7．设某棵三叉树中有 (A) 3 (B) 冒泡排序 (C) 快速排序 (D) 40 个结点，就该三叉树的最小高度为（(B) 4 (C) 5 (D) 68．次序查找不论在次序线性表中仍是在链式线性表中的时间复杂度为（）；21/2(A) O(n) (B) O(n ) (C) O(n ) (D) O(1og 2n) 9．二路归并排序的时间复杂度为（ ）；2 (A) O(n) 深度为 (B) O(n ) k 的完全二叉树中最少有（(C) O(nlog ）个结点； (C) 2+12n)(D) O(1og 2n) 10. k-1k-1k-1k(A) 2-1设指针变量 (B) 2(D) 2 -1rear 表示链式队列的队尾指针，front 表示链式队列的队头指针，指针变量11. 指针变量 s 指向将要入队列的结点 X ，就入队列的操作序列为（）；； front=s ；rear=s ； ；； rear=s ；； front=s ； (A) front->next=s(C) rear->next=s 设某无向图中有 (A) O(n+e) 设某哈夫曼树中有 (A) 99 设二叉排序树上有 (A) O(n)(B) s->next=rear(D) s->next=frontn 个顶点 e 条边，就建立该图邻接表的时间复杂度为（）；12. 23(B) O(n ) (C) O(ne) (D) O(n ) ）个叶子结点； (D) 102199 个结点，就该哈夫曼树中有（13. (B) 100 (C) 101 n 个结点，就在二叉排序树上查找结点的平均时间复杂度为（）； 14. 2 (B) O(n )(C) O(nlog2n)(D) O(1og 2 n)设用邻接矩阵 A 表示有向图 G 的储备结构，就有向图 G 中顶点 i 的入度为（）；15. (A) 第 (C) 第 i 行非 0 元素的个数之和 第 第 i 列非 0 元素的个数之和i 列 0 元素的个数之和(B) (D) i 行 0 元素的个数之和 四，算法设计题 (20 分 )１．设计在次序有序表中实现二分查找的算法；设计在次序有序表中实现二分查找的算法；struct record {int key; int others;};int bisearch(struct record r[ ], int k){int low=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;return(mid+1);else if(r[mid].key>k)high=mid-1;else if(r[mid].key==k)low=mid+1;}return(0);}２．设计判定二叉树是否为二叉排序树的算法；设计判定二叉树是否为二叉排序树的算法；int minnum=-32768,flag=1;typedef struct node{int key; struct node *lchild,*rchild;}bitree;void inorder(bitree *bt){if(bt.=0){inorder(bt->lchild);if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild);}}３．在链式储备结构上设计直接插入排序算法在链式储备结构上设计直接插入排序算法void straightinsertsort(lklist *&head){lklist *s,*p,*q;int t;if (head==0 || head->next==0) return;else for(q=head,p=head->next;p.=0;p=q->next){for(s=head;s.=q->next;s=s->next) if (s->data>p->data) break;if(s==q->next)q=p;p->next=s->next;s->next=p;else{q->next=p->next;t=p->data;p->data=s->data;s->data=t;}}}数据结构试卷（七）一，挑选题 (30 分 )1．设某无向图有 (A) 2nn 个顶点，就该无向图的邻接表中有（）个表头结点； (D) n(n-1)）条边； (D) 2n-1(B) n(C) n/22．设无向图 (A) n G 中有 n 个顶点，就该无向图的最小生成树上有（(B) n-1 (C) 2n 3．设一组初始记录关键字序列为而得到的一趟快速排序结果是（ (60 ，80，55，40，42， 85) ，就以第一个关键字 ）；45 为基准(A) 40 ， 42， 60， 55， 80， 85(C) 42 ， 40， 55， 60， 80， 85 (B) 42 ， 45， 55， 60， 85， 80(D) 42 ， 40， 60， 85， 55， 80 4．（ ）二叉排序树可以得到一个从小到大的有序序列； (A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历5．设依据从上到下，从左到右的次序从1 开头对完全二叉树进行次序编号，就编号为i 结点的左孩子结点的编号为（ ）；(A) 2i+1 (B) 2i (C) i/2(D) 2i-16．程序段 s=i=0； do {i=i+1 ； s=s+i ； }while(i<=n) ；的时间复杂度为（）；23(A) O(n) (B) O(nlog2n)(C) O(n ) (D) O(n /2)7．设带有头结点的单向循环链表的头指针变量为 head ，就其判空条件是（）；(A) head==0(C) head->next==head 8．设某棵二叉树的高度为(B) head->next==0 (D) head.=0 10，就该二叉树上叶子结点最多有（）；(A) 20(B) 256 (C) 512(D) 1024 9．设一组初始记录关键字序列为 (13 ，18，24，35，47，50， 62， 83， 90，115， 134), 就利用二分法查找关键字 90 需要比较的关键字个数为（）；(D) 4(A) 1 10. 设指针变量 (B) 2 (C) 3 top 指向当前链式栈的栈顶，就删除栈顶元素的操作序列为（）；(A) top=top+1; (C) top->next=top; (B) top=top-1; (D) top=top->next;四，算法设计题 (20 分 ) 1.设计在链式结构上实现简洁挑选排序算法； 设计在链式结构上实现简洁挑选排序算法；void simpleselectsorlklist(lklist *&head) {lklist *p,*q,*s;int min,t;if(head==0 ||head->next==0) return; for(q=head; q.=0;q=q->next) {min=q->data; s=q;for(p=q->next; p.=0;p=p->next) if(min>p->data){min=p->data; s=p;} if(s.=q){t=s->data; s->data=q->data; q->data=t;} } }2. 设计在次序储备结构上实现求子串算法；设计在次序储备结构上实现求子串算法；void substring(char s[ ], long start, long count, char t[ ]){long i,j,length=strlen(s);if (start<1 || start>length) printf("The copy position is wrong");else if (start+count-1>length) printf("Too characters to be copied");else { for(i=start-1,j=0; i<start+count-1;i++,j++) t[j]=s[i]; t[j]= '\0';}}3. 设计求结点在二叉排序树中层次的算法；设计求结点在二叉排序树中层次的算法；int lev=0;typedef struct node{int key; struct node *lchild,*rchild;}bitree;void level(bitree *bt,int x){if (bt.=0){lev++;if(bt->key==x)return;else if(bt->key>x)level(bt->lchild,x);else level(bt->rchild,x);}}数据结构试卷（八）一，挑选题 (30 分 ) 字符串的长度是指（ (A) 串中不同字符的个数 (C) 串中所含字符的个数 ）；1.串中不同字母的个数 串中不同数字的个数(B) (D) 建立一个长度为 (A) O(n)n 的有序单链表的时间复杂度为（ ）2. 2(B) O(1)(C) O(n ) ）；(D) O(log 2n)两个字符串相等的充要条件是（ (A) 两个字符串的长度相等 (C) 同时具备 (A) 和 (B) 两个条件3.两个字符串中对应位置上的字符相等 以上答案都不对(B) (D) 设某散列表的长度为 (A) 99 100，散列函数 (B) 97 H(k)=k % P ，就 (C) 91 P 通常情形下最好挑选（ (D) 93）； (D) O(n )）；4. 在二叉排序树中插入一个关键字值的平均时间复杂度为（5. 2(A) O(n)设一个次序有序表 (B) O(1og 2n)A[1:14] 中有 ； (C) O(nlog2n)14 个元素，就采纳二分法查找元素A[4] 的过程中比较6.元素的次序为 ( (A) A[1] ， A[2] (C) A[7] ， A[3] ) ， A[3] ， A[5] ，A[4] ，A[4]， A[14] ， A[7] ，A[4] ， A[4] ）； (B) A[1] (D) A[7] ，A[5] ， A[3] 设一棵完全二叉树中有 65 个结点，就该完全二叉树的深度为（7. (A) 8设一棵三叉树中有 就该三叉链权中有（ (B) 72 个度数为 (C) 61 的结点，2 个度数为 (D) 52 的结点， 2 个度数为3 的结点， 8.）个度数为 0 的结点；(C) 7(A) 5设无向图 就从顶点 (A) aedfcb(B) 6G 中的边的集合 (D) 8E={(a ， b)， (a ， e)， (a ，c) ， (b ， e)， (e ， d)，(d ，f) ，(f ，c)} ，9.a 动身进行深度优先遍历可以得到的一种顶点序列为（ ）； (B) acfebd ）的线性表； (B) 先进后出(C) aebcfd(D) aedfbc队列是一种（(A) 先进先出10. (C) 只能插入(D) 只能删除四，算法设计题 分 ) (20 1.设计一个在链式储备结构上统计二叉树中结点个数的算法； 设计一个在链式储备结构上统计二叉树中结点个数的算法；void countnode(bitree *bt,int &count) {if(bt.=0){count++; countnode(bt->lchild,count); countnode(bt->rchild,count);}} 2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法； 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法；typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix;typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]) {int i,j; glinklistnode *p;for(i=0;i<=n-1;i++) g2[i].firstarc=0;for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++)if (g1.edge[i][j]==1){p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j;p->nextarc=g[i].firstarc; g[i].firstarc=p;p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i;p->nextarc=g[j].firstarc; g[j].firstarc=p;}}数据结构试卷（九）一，挑选题 (30 分 )1．以下程序段的时间复杂度为（）；for(i=0 ； i<m ； i++) for(j=0 ； j<t ； j++) c[i][j]=0 ；for(i=0 ； i<m ； (A) O(m*n*t) i++) for(j=0 ； j<t ； j++) for(k=0 ； k<n ； k++) c[i][j]=c[i][j]+a[i][k]*b[k][j] ；(B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)2．设次序线性表中有 (A) n-in 个数据元素，就删除表中第i 个元素需要移动（(D) i）个元素；(B) n+l -i(C) n-1-i3．设 F 是由 数分别为 (A) N1-1 T1，T2 和 T3 三棵树组成的森林，与 F 对应的二叉树为 B ，T1，T2 和 T3 的结点N1， N2 和 N3，就二叉树 (B) N2-1 B 的根结点的左子树的结点数为（）； (C) N2+N3(D) N1+N34．利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）；2n)X ，就在结点 A 的后 2(A) O(n)5．设指针变量 面插入结点 (B) O(nlog2n)(C) O(n ) A ，指针变量 (D) O(1og s 指向被插入的结点 p 指向双向链表中结点 X 的操作序列为（ ）；(A) p->right=s ； s->left=p ； p->right->left=s ； s->right=p->right ；p->right->left=s ； s->right=p->right ；(B ) s->left=p ； s->right=p->right ； p->right=s ； (C )p->right=s ； p->right->left=s ； s->left=p ； (D) s->left=p ； s->right=p->right ； p->right->left=s ； p->right=s ；）； (D) 冒泡排序26．以下各种排序算法中平均时间复杂度为O(n ) 是（ (C) 归并排序(A) 快速排序堆排序(B) 7．设输入序列 1， 2，3， ，n 经过栈作用后，输出序列中的第一个元素是 ）； n ，就输出序列中的第 (A) n-ii 个输出元素是（ (D) 不能确定(B) n-1-im 个储备单元，散列函数 m 的最大奇数 m 的最大偶数(C) n+l -i8．设散列表中有 (A) 小于等于 (C) 小于等于 9．设在一棵度数为 H(key)= key % p ，就 p 最好挑选（(B) 小于等于 m 的最大素数(D) 小于等于 m 的最大合数）；3 的树中，度数为 2 个，那么度数为 (B) 53 的结点数有 0 的结点数有（ (C) 62 个，度数为 ）个；(D) 7 2 的结点数有 1 个，度数为 1 的结点数有 (A) 410. 设完全无向图中有 (A) n(n-1)/2 11. 设次序表的长度为 (A) nn 个顶点，就该完全无向图中有（ ）条边； (D) (n-1)/2）； (D) (n-1)/2(B) n(n-1) (C) n(n+1)/2 n ，就次序查找的平均比较次数为（ (B) n/2 (C) (n+1)/212. 设有序表中的元素为 的元素需要经过（ (A) 1 (13 ， 18，24，35，47，50，62) ，就在其中利用二分法查找值为 ）次比较； 24(B) 2(C) 35 块，每块 (D) 46 个元素，假如采纳分块查找，就其平均查13. 设次序线性表的长度为30，分成 找长度为（ (A) 614. 设有向无环图 ）；(B) 11G 中的有向边集合 (C) 5 (D)E={<1 ， 2>， <2， 3>， <3， 4> ， <1， 4>} ，就以下属于 该有向图 G 的一种拓扑排序序列的是（）；(C) 1 ， 4， 2， 3 (A) 1 ， 2， 3， 4 (B) 2 ， 3， 4，1(D) 1 ， 2， 4， 315. 设有一组初始记录关键字序列为生成的二叉排序树的深度为（(34 ，76，45，18，26，54，92) ，就由这组记录关键字）；(A) 4五，算法设计题(B) 5(20 分)(C) 6 (D) 71．设计运算二叉树中全部结点值之和的算法；设计运算二叉树中全部结点值之和的算法；void sum(bitree *bt,int &s){if(bt.=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);} }2．设计将全部奇数移到全部偶数之前的算法；设计将全部奇数移到全部偶数之前的算法；void quickpass(int r[], int s, int t){int i=s,j=t,x=r[s];while(i<j){while (i<j && r[j]%2==0) j=j-1; while (i<j && r[i]%2==1) i=i+1;if (i<j) {r[i]=r[j];i=i+1;} if (i<j) {r[j]=r[i];j=j-1;}}r[i]=x;}3．设计判定单链表中元素是否是递增的算法；设计判定单链表中元素是否是递增的算法；int isriselk(lklist *head){if(head==0||head->next==0) return(1);elsefor(q=head,p=head->next; p.=0; q=p,p=p->next)if(q->data>p->data) return(0);return(1);}数据结构试卷（十）一，挑选题 (24 分 )1．以下程序段的时间复杂度为（）；i=0 ， s=0； (A) O(n)while (s<n) {s=s+i ； i++ ； }1/21/32(B) O(n)(C) O(n)(D) O(n )2．设某链表中最常用的操作是在链表的尾部插入或删除元素，就选用以下（最节约运算时间；）储备方式(A) 单向链表 (C) 双向链表3．设指针 q 指向单链表中结点 单向循环链表 双向循环链表(B) (D) A ，指针 p 指向单链表中结点 A 的后继结点 B ，指针 s 指向被插入的结点 X ，就在结点 A 和结点 B 插入结点 X 的操作序列为（ ）；； p->next=-s ； ； s->next=p ；； s->next=q ；(A) s->next=p->next (C) p->next=s->next(B) q->next=s(D) p->next=s ； s->next=p ； 4．设输入序列为 1， 2， 3，4， 5， 6，就通过栈的作用后可以得到的输出序列为（）；(A) 5 ， 3， 4， 6，1， 2 (C) 3 ， 1， 2， 5，4， 6(B) 3 ，2， 5， 6， 4，1 (D) 1 ， 5， 4， 6， 2， 3A （包括对角线），依据从上到下，从左到右的次序储备到 5．设有一个 10 阶的下三角矩阵 连续的 55 个储备单元中， 每个数组元素占 1 个字节的储备空间， 就 A[5][4] 地址与 A[0][0] 的地址之差为（ (A) 106．设一棵 m 叉树中有 ）； (B) 19(C) 28(D) 552 的结点，N 1 个度数为 1 的结点， N 2 个度数为 ， Nm 个度数为m的结点，就该树中共有（ ）个叶子结点；mmmm(A)(C)(D) (i 1) N iN iN i1(i 1) N i(B)i 1i 1i 2i 27. 二叉排序树中左子树上全部结点的值均（）根结点的值；(D) .=(A) <8. 设一组权值集合 (B) >(C) =W=(15，3，14， 2， 6，9， 16， 17) ，要求依据这些权值集合构造一棵哈夫曼树，就这棵哈夫曼树的带权路径长度为（ ）；(A) 129 (B) 219 (C) 189(D) 2299. 设有 n 个关键字具有相同的 Hash 函数值，就用线性探测法把这n 个关键字映射到 HASH表中需要做（ ）次线性探测；(B) n(n+1)2(A) n(C) n(n+1)/2(D) n(n-1)/20 的结点数为 10. 设某棵二叉树中只有度数为0 和度数为 2 的结点且度数为 n ，就这棵二叉中共有（ (A) 2n ）个结点；(B) n+l (C) 2n-1 8，就最多经过（(C) 8(D) 2n+l）趟插入排序可以得到有序序列；(D) 911. 设一组初始记录关键字的长度为 (A) 6(B) 712. 设一组初始记录关键字序列为(Q ，H ， C ， Y ，P ， A ，M ， S ， R ，D ， F ， X) ，就按字母升序的第一趟冒泡排序终止后的结果是（）；(A )F ， H ，C ，D ， P ，A ，M ， Q ，R ， S ， Y ， X(B ) P ， A ，C ， S ， Q ，D ，F ， X ， R ，H ， M ， Y (C ) A ， D ， C ， R ， F ， Q ， M ， S ，Y ， P ， H ，X (D)H ， C ， Q ， P ，A ， M ， S ， R ， D ， F ， X ， Y。

十套数据结构试题及答案1编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（十套数据结构试题及答案1）的内容能够给您的工作和学习带来便利。

同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。

本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为十套数据结构试题及答案1的全部内容。

数据结构试卷（一) 0数据结构试卷（二) (4)数据结构试卷（三） (8)数据结构试卷（四) (13)数据结构试卷（五） (18)数据结构试卷（六） (22)数据结构试卷（七） (26)数据结构试卷（八) (29)数据结构试卷（九） (32)数据结构试卷（十) (36)数据结构试卷（一)参考答案 (40)数据结构试卷（二）参考答案 (41)数据结构试卷（三）参考答案 (43)数据结构试卷（四）参考答案 (47)数据结构试卷（五）参考答案 (50)数据结构试卷(六）参考答案 (52)数据结构试卷（七）参考答案 (55)数据结构试卷（八）参考答案 (57)数据结构试卷(九）参考答案 (59)数据结构试卷（十)参考答案 (61)数据结构试卷（一）一、单选题（每题 2 分，共20分)栈和队列的共同特点是( A ）。

A.只允许在端点处插入和删除元素B。

都是先进后出C.都是先进先出D.没有共同点1.用链接方式存储的队列，在进行插入运算时( D）。

A. 仅修改头指针 B。

头、尾指针都要修改C. 仅修改尾指针D。

头、尾指针可能都要修改2.以下数据结构中哪一个是非线性结构？( D）A. 队列 B。

栈 C。

线性表 D. 二叉树3.设有一个二维数组A[m]［n］，假设A[0］[0］存放位置在644（10)，A[2]［2]存放位置在676（10），每个元素占一个空间，问A［3][3］（10）存放在什么位置?脚注(10)表示用10进制表示（C）。

数据结构试卷（一）三、算（每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中.。

数据构造试卷〔一〕一、单项选择题〔每题 2 分，共20分〕1.栈和队列的共同特点是( a )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进展插入运算时( d ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据构造中哪一个是非线性构造？( d )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

cA．688 B．678 C．692 D．6965.树最适合用来表示( c )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.假设有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进展二分查找，那么查找A［3］的比拟序列的下标依次为( c d)A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进展快速排序，所需要的辅助存储空间大致为 cA. O〔1〕B. O〔n〕C. O〔1og2n〕D. O〔n2〕9.对于线性表〔7，34，55，25，64，46，20，10〕进展散列存储时，假设选用H〔K〕=K %9作为散列函数，那么散列地址为1的元素有〔 c d〕个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( a )条边才能确保是一个连通图。

二、填空题〔每空1分，共26分〕1.通常从四个方面评价算法的质量：____时间正确性_____、____占用内存_易读性____、____复杂度__强壮性___和_____准确度_ 高效率___。

一、单选题（每题 2 分，共20分）1.对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.AOV网是一种（）。

A．有向图B．无向图C．无向无环图D．有向无环图6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。

A．值B．函数C．指针D．引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。

A．行号B．列号C．元素值D．非零元素个数9.快速排序在最坏情况下的时间复杂度为（）。

A．O(log2n) B．O(nlog2n)C．0(n) D．0(n2)10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N （M：N）的联系时，称这种结构为_____________________。