下载文档原格式
数据结构试卷（一） (1)数据结构试卷（二） (5)数据结构试卷（三） (8)数据结构试卷（四） (11)数据结构试卷（五） (15)数据结构试卷（六） (17)数据结构试卷（七） (20)数据结构试卷（八） (22)数据结构试卷（九） (24)数据结构试卷（十） ...................... 26 数据结构试卷（一）参考答案 (28)数据结构试卷（二）参考答案 (30)数据结构试卷（三）参考答案 (31)数据结构试卷（四）参考答案 (33)数据结构试卷（五）参考答案 (35)数据结构试卷（六）参考答案 (36)数据结构试卷（七）参考答案 (38)数据结构试卷（八）参考答案 (39)数据结构试卷（九）参考答案 (40)数据结构试卷（十）参考答案 (41)数据结构试卷（一）一、单选题（每题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）。
A．688 B．678 C．692 D．6964.树最适合用来表示( C)。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据5.二叉树的第k层的结点数最多为( D ).A．2k-1 B.2K+1 C.2K-1 D. 2k-16.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( D)A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，37.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（C）A. O（1）B. O（n）C. O（1og2n）D. O（n2）8.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（D）个，A．1 B．2 C．3 D．49.设有6个结点的无向图，该图至少应有( A)条边才能确保是一个连通图。
数据结构试卷（一）一、单选题（每题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．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. 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的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
数据结构试卷（一） (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．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. 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的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
十套数据结构试题及答案1.请设计一个栈结构，满足以下要求：-支持常规的入栈和出栈操作。
-支持获取当前栈中最小元素的操作，并要求时间复杂度为O(1)。
答案：可以使用两个栈，一个用于存储数据，另一个用于维护当前栈中的最小值。
每次入栈时，比较要入栈的元素与当前栈中的最小值，将较小的值入最小栈。
出栈时，同时从数据栈和最小栈中出栈，保持栈的一致性。
2.请用链表实现一个队列结构，满足以下要求：-支持常规的入队和出队操作。
-支持获取队列中的最大值和最小值的操作，并要求时间复杂度为O(1)。
答案：使用双向链表实现队列，每个结点保存当前最大值和最小值，入队时更新队列相关结点的最大值和最小值，出队时删除队首结点，并更新队列最大值和最小值。
3. 设计一个LRU（Least Recently Used）缓存结构，要求如下：-缓存结构内存固定大小。
-当缓存结构满时，插入新的数据时需要剔除最近最少使用的数据。
答案：可以使用哈希表和双向链表来实现。
哈希表用于实现快速查找，双向链表用于保存数据的访问顺序。
当一些数据被访问时，根据哈希表快速定位到对应的结点，并将该结点移到链表头部。
当需要插入新数据时，如果缓存容量已满，则将链表尾部的结点剔除。
4.设计一个支持并发访问的并且具有线程安全性的哈希表结构。
答案：可以使用读写锁来保证线程安全性。
读操作时，多个线程可以同时读取，不会产生冲突；写操作时，需要获取写锁，保证同时只能有一个线程执行写操作。
5.实现一个拓扑排序算法，对有向无环图进行排序。
答案：可以使用DFS和栈结构来实现。
从任意一个未被访问的结点开始，递归地进行深度优先，并将访问完毕的结点入栈。
最终得到的栈中的结点顺序即为拓扑排序结果。
6.设计一个支持高效插入与删除的动态数组结构。
答案：可以使用动态平衡二叉树（例如AVL树）来实现。
插入与删除操作的时间复杂度为O(log n)，并保持树的平衡性，避免树的高度过大。
7.设计一个支持高效查找的散列表结构。
数据结构试题及答案(10套最新)数据结构试题及答案(10套最新)第一套试题：问题一：什么是数据结构？数据结构的作用是什么？回答：数据结构是一种组织和存储数据的方式，它关注数据元素之间的关系以及对数据元素的操作。
数据结构的作用包括提供高效的数据存储和访问方式，减少资源消耗，简化问题的解决方法，提高算法的性能和程序的可读性。
问题二：请列举几种常见的线性数据结构，并简要介绍它们的特点。
回答：常见的线性数据结构包括数组、链表和栈。
数组是一种连续存储数据元素的结构，具有随机访问的特点；链表是一种通过指针相连的数据元素，可以灵活地插入和删除元素；栈是一种遵循先进后出原则的数据结构，常用于解决递归问题。
问题三：请说明二叉树的定义及其性质。
回答：二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点。
二叉树具有以下性质：每个节点最多有两个子节点，分别称为左子节点和右子节点；左子树和右子树都是二叉树；二叉树的节点个数为n，边的个数为n-1。
问题四：在数组中查找一个元素的时间复杂度是多少？为什么？回答：在数组中查找一个元素的时间复杂度是O(n)，其中n是数组的长度。
因为在数组中查找元素需要按照索引一个一个比较，最坏情况下需要比较n次才能找到目标元素。
问题五：请解释堆排序算法的原理及时间复杂度。
回答：堆排序算法利用堆这种数据结构进行排序。
首先将待排序的元素构建成一个大顶堆，然后将堆顶元素与最后一个元素交换，继续调整堆，再取出堆顶元素与倒数第二个元素交换，依次执行，最后得到从小到大排序的序列。
堆排序的时间复杂度为O(nlogn)。
第二套试题：问题一：请解释图的邻接矩阵和邻接表表示法。
回答：图的邻接矩阵表示法是使用二维数组来表示图的连接关系，数组中的元素表示相应节点之间的边的关系。
邻接表表示法使用链表来表示图的连接关系，链表中的元素表示相邻节点之间的边的关系。
问题二：请说明深度优先搜索算法的原理及其应用。
回答：深度优先搜索（DFS）算法是一种遍历或搜索图的算法，其原理是从起始节点开始，依次深入到尽可能远的节点，直到无法继续深入为止，然后回溯到上一个节点，再继续深入其他未访问过的节点。
数据结构试卷（一）.................. 1 数据结构试卷（一）参考答案 .. (26)数据结构试卷（二）参考答案4 ........ 27 数据结构试卷（二）..................数据结构试卷（三）参考答案数据结构试卷（三）.................. 6 .. (28)数据结构试卷（四）参考答案.................. 8 ........ 30 数据结构试卷（四）数据结构试卷（五）参考答案数据结构试卷（五）................. 11 .. (32)数据结构试卷（六）参考答案 ................. 14 ........ 33 数据结构试卷（六）数据结构试卷（七）参考答案数据结构试卷（七）................. 16 .. (36)数据结构试卷（八）参考答案数据结构试卷（八）................. 18 .. (37)数据结构试卷（九）参考答案数据结构试卷（九）................. 20 .. (38)数据结构试卷（十）参考答案 ................. 23 ........ 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，A[2][2]存放位置在(10)676，每个元素占一个空间，问A[3][3]存放在什么位置？脚注表示用10进制(10)(10)(10)表示。
二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。
4.后缀算式9 2 3 +- 10 2 / -的值为__________。
中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。
5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。
在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。
6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。
7.AOV网是一种___________________的图。
8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。
9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。
10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。
11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。
数据结构试卷（一）一、单选题（每题 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］的比较序列的下标依次为( 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（1ogn） D. O（n2）29.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（D）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( A)条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：__正确性__、_易读性_、_强壮性_和__高效率___。
1.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为____O(n)____。
数据结构试卷（一） (1)数据结构试卷（二） (5)数据结构试卷（三） (8)数据结构试卷（四） (11)数据结构试卷（五） (14)数据结构试卷（六） (16)数据结构试卷（七） (19)数据结构试卷（八） (21)数据结构试卷（九） (23)数据结构试卷（十）....................................... 25 数据结构试卷（一）参考答案 .. (27)数据结构试卷（二）参考答案 (29)数据结构试卷（三）参考答案 (30)数据结构试卷（四）参考答案 (32)数据结构试卷（五）参考答案 (34)数据结构试卷（六）参考答案 (35)数据结构试卷（七）参考答案 (37)数据结构试卷（八）参考答案 (38)数据结构试卷（九）参考答案 (39)数据结构试卷（十）参考答案 (40)数据结构试卷（一）一、单选题（每题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）。
A．688 B．678 C．692 D．6964.树最适合用来表示( C)。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据5.二叉树的第k层的结点数最多为( D ).A．2k-1 B.2K+1 C.2K-1 D. 2k-16.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( D)A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，37.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（C）A. O（1）B. O（n）C. O（1og2n）D. O（n2）8.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（D）个，A．1 B．2 C．3 D．49.设有6个结点的无向图，该图至少应有( A)条边才能确保是一个连通图。
数据结构试卷（一） (1)数据结构试卷（二） (5)数据结构试卷（三） (9)数据结构试卷（四） (14)数据结构试卷（五） (19)数据结构试卷（六） (24)数据结构试卷（七） (28)数据结构试卷（八） (32)数据结构试卷（九） (36)数据结构试卷（十） .................................. 41 数据结构试卷（一）参考答案 (47)数据结构试卷（二）参考答案 (48)数据结构试卷（三）参考答案 (51)数据结构试卷（四）参考答案 (55)数据结构试卷（五）参考答案 (58)数据结构试卷（六）参考答案 (61)数据结构试卷（七）参考答案 (64)数据结构试卷（八）参考答案 (66)数据结构试卷（九）参考答案 (69)数据结构试卷（十）参考答案 (71)数据结构试卷（一）一、单选题（每题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．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. 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的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
十套数据结构试题及答案55426数据结构试卷（一）一、单选题（每题 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个记录的文件进行快速排序，所需要的辅助存储空间大致为 cn） D. OA. O（1）B. O（n）C. O（1og2（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 )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____时间正确性_____、____占用内存_易读性____、____复杂度__强壮性___和_____准确度_ 高效率___。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为___3 0（n）_____。
3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_____9_____个，树的深度为_____3______，树的度为____2_____。
4.后缀算式9 2 3 +- 10 2 / -的值为____3__-1____。
中缀算式（3+4X）-2Y/3对应的后缀算式为______3 4X* + 2Y* / -_________________________。
5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。
在这种存储结构中，n个结点的二叉树共有____n_2n___个指针域，其中有_____n-1___个指针域是存放了地址，有________3__n+1______个指针是空指针。
6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有___e+1_e___个和____e+1__2e__个。
7.AOV网是一种________有向无回路___________的图。
8.在一个具有n个顶点的无向完全图中，包含有____n-1_n(n-1)/2___条边，在一个具有n个顶点的有向完全图中，包含有____n-1___n(n-1)_条边。
9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为___________(12,40)_________________、_______(23,63,55)________、_______(74)________________和_________( )_________________。
10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度______增加1____。
1.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为___0（n/2）___ O(log2n)__，整个堆排序过程的时间复杂度为__0（1）__ O(nlog2n)____。
11.在快速排序、堆排序、归并排序中，____堆排序__归并排序___排序是稳定的。
三、计算题（每题 6 分，共24分）1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。
data 60 50 78 90 34 40next 3 5 7 2 0 4 1 线性表为：（78，50，40，60，34，90）2.请画出下图的邻接矩阵和邻接表。
1.邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡11111111111111113.已知一个图的顶点集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时，每加入一个数据后堆的变化。
四、阅读算法（每题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的功能；判断p的下一节点是否为空，如不为空p则指向下一节点查询链表的尾节点（2）说明语句组S2的功能；使P的下一节点赋值给q，并令q的下一节点为空指针。
将第一个节点链接到链表的尾部，作为新的尾节点（3）设链表表示的线性表为（a1,a2, …,a n）,写出算法执行后的返回值所表示的线性表。
a2,a3,…an,a12.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 ____item__true_____;}else if(item<BST->data)return Find(______BST->data____BST->left____,item);else return Find(_______item____BST->right____,item);}//if}六、编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。
int CountX(LNode* HL,ElemType x){int count;node *head,*p;head = HL;p=head->next;if(head->data!=null){while(p->next){if(p->data==x)count++;}}}Struct node HL{elemtype data;Struct node *next;}node;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数据结构试卷（一）参考答案一、选择题（每题2分，共20分）1.A2.D3.D4.C5.C6.D7.D8.C9.D 10.A二、填空题（每空1分，共26分）1.正确性易读性强壮性高效率2.O(n)3.9 3 34.-1 3 4 X * + 2 Y * 3 / -5.2n n-1 n+16.e 2e7.有向无回路8.n(n-1)/2 n(n-1)9.（12，40）（）（74）（23,55，63）10.增加111.O(log2n) O(nlog2n)12.归并三、计算题（每题6分，共24分）2.线性表为：（78，50，40，60，34，90）3.邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡1111111111111111邻接表如图11所示：图114.用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)205. 见图12四、 读算法（每题7分，共14分）1.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a 2,a 3,…,a n ,a 1）2. 递归地后序遍历链式存储的二叉树。
五、 法填空（每空2分，共8 分）true BST->left BST->right六、 编写算法（8分）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 ，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。
