数据结构数据结构历年考题及答案2

1、word中国矿业大学2022-2012学年 数据结构 试卷A卷考试时间：100分钟一. 填空每空2分，共40分1. 数据结构式具有相同性质的数据元素的 1 。2. 通常程序在调用另一个程序时，都需要使用一个 2 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，A的起始存储地址基址为1000，在行优先存储和列优先存贮情况下A5,5的存储地址分别为_3_,_(4)_。4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，那么共有 (7) 个节点。5.

2、请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_(8)_,_(9)_。6. 字符串t=child，s=cake，请写出以下函数的结果：StrLength(t) =10_;Concat(SubString(s,3,1)，SubString(t,2,2)=_11_。7. 一棵二叉树为CGEDFBHA那么后序序列为 12 ，中序序列为 13 ，先序序列为_14_。8. 请用数据序列53，17，12，66，58，70，87，25，56，60 构造一棵二叉排序树_(15_。9.。一个栈输入的序列式1,2,3，那么可能的且以2为开头

3、的输出序列是 (16) ，不可能的序列是_17_。10. 有n个结点的无向完全图的边数分别为_(18)_。11. 要从数据：2，3，4，8，9，11，13查找11，假设采用折半查找法，那么在 19 次比拟后，才找到该数据。12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下20_最快。二简答题：1给定15,3,14,2,6,9,16,17，试为这8个数设计哈夫曼编码，并计算其带权路径长度。2请对以下图的无向带权图按克鲁斯卡尔算法求其最小生成树。要求使用图画出每一步过程。3 假定存在数据表：3，4，5，7，24，30，54，63，72，87，95，102，请解决如下问题：假设哈希函

4、数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，利用线性探测请画出存放状态；4 森林和二叉树的转换，画出和以下二叉树相应的森林5设要将序列46,79,56,38,40,84中的关键码按升序重新排列，写出快速排序的过程。(每一步过程)三 程序题(10分)编写算法判别给定二叉树是否为完全二叉树 数据结构 A卷答案一填空每空2分，共40分1. 集合。2. 递归工作栈 。3. 1270 , 1210 。4. 2, 8, 1023 。5. Q.front=Q.rear, Q.front=Q.rear+1% 10 。6. 5 , “iak。7. DECBHGFA, B

5、DCEAFHG, ABCDEFGH8. 25706617535812605687 。9. 231 或 213 , 312 。10. n(n-1)/2 。11. 2 。12. 快速排序 。二. 简答题每题10分，共50分1. 图不唯一WPL=2292.aacabadhgfe3.01234567891011121025434530772879524634.DkCEAHBJG IFM5.46,79,56,38,40,8440,38,46,56,79,84(38,40,46,56,79,84三. 程序题10分int IsFull_Bitree(Bitree T)/判断二叉树是否完全二叉树,是那么返回1

6、,否那么返回0 InitQueue(Q); flag=0;  EnQueue(Q,T); /建立工作队列  while(!QueueEmpty(Q)  DeQueue(Q,p);    if(!p) flag=1; /如果孩子为空，那么说明左孩子为空 else if(flag) return 0;    else          EnQ

7、ueue(Q,p->lchild);      EnQueue(Q,p->rchild); /不管孩子是否为空,都入队列      /while  return 1;/IsFull_Bitree中国矿业大学2022-2012学年 数据结构 试卷B卷考试时间：100分钟一填空每空2分，共40分1. 数据结构是指数据及其相互之间的_。当结点之间存在M对NM：N的联系时，称这种结构为_。2. 通常程序在调用另一个程序时，都需要使用一个 来保存被调用程

8、序内分配的局部变量、形式参数的存储空间以及返回地址。3.有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，A的起始存储地址基址为1000，在行优先存储和列优先存贮情况下A5,5的存储地址分别为_,_。4. 设目标T=abccdcdccbaa，模式P=“cdcc，那么第 次匹配成功。5.请描述在循环队列中，队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间，判断队空和队满的条件分别分：_,_。6. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。7. 在具有n个单元的循环队列中，队满时共有

9、个元素。8. 深度为k 的二叉树的结点总数，最多为_个。最少为_个。9二叉树中元素按照顺序存储方式存放在如下一维数组中，那么结点G所在层次为 。01234567891011121314ABCDEFGHIJ10. 有n个结点的无向完全图和有向完全图的边数分别为_,_。11. 图的深度优先遍历算法类似于树的 。12. 要从序列1，3，5，7，9，11，13中查找11，假设采用折半查找法，那么在 次比拟后，才找到该数据。13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下_最快，其时间复杂度为_。二简答题：每题10分，共50分1. 假设9个字母为：A B C D E F G H，权值分别

10、为5，13，7，4，20，34，16, 9，8。试为这9个字母设计哈夫曼编码。并计算其带权路径长度。2. 一个图的顶点集V和边集E分别为： V=1,2,3,4,5,6,7;E=<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>假设存储它采用邻接表，试写出临界表。并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按拓朴排序算法进行排序，试给出得到的拓朴排序的序列。3. i

11、nt Prime(int n) int i=1; int x=(int) sqrt(n); while (+i<=x) if (n%i=0) break; if (i>x) return 1; else return 0; (1)指出该算法的功能；(2) 该算法的时间复杂度是多少？请说明。4假定存在数据表：3，4，5，7，24，30，54，63，72，87，95，102，请解决如下问题：1) 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，利用线性探测请画出存放状态；2) 请按比拟顺序写出查找102的过程中比拟的数值，以及比拟的次数；

12、5设要将序列Q, H, C, Y, P, A, M, S, R, D, F, X中的关键码按字母序的升序重新排列，那么写出希尔shell排序的过程，初始步长为4三 程序题请写出折半查找方法的函数Search_Bin( SSTable S, value v)。要求：1函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值；2如果找到，那么函数返回值为该数在序列中的位置，否那么返回-1；3不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。中国矿业大学2022-2012学年 数据结构 试卷B卷答案专业： 班级： 序号： 姓名： 一填

13、空每空2分，共40分1. 联系 , 图或图结构。2. 通常程序在调用另一个程序时，都需要使用一个 栈 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。3.有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，A的起始存储地址基址为1000，在行优先存储和列优先存贮情况下A5,5的存储地址分别为_1270 , 1210_。4. 设目标T=abccdcdccbaa，模式P=“cdcc，那么第 6次匹配成功。5.请描述在循环队列中，队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间，判断队空和队满的条件分别分：_ Q.front=Q

14、.rear, Q.front=Q.rear+1% MS _。6. O1 On _。7. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。8. 深度为k 的二叉树的结点总数，最多为_2k-1_个。最少为_k_个。9二叉树中元素按照顺序存储方式存放在如下一维数组中，那么结点G所在层次为 3 。01234567891011121314ABCDEFGHIJ10. 有n个结点的无向完全图和有向完全图的边数分别为_ n(n-1)/2 , n(n-1) _。11. 图的深度优先遍历算法类似于树的 先序 。12. 要从序列1，3，5，7，9，11，13中查找11，假设采用折半查找法，那么在 2 次比拟

15、后，才找到该数据。13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下_最快，其时间复杂度为_。快速排序 , O(n lg n)二简答题：每题10分，共50分1. 假设9个字母为：A B C D E F G H，权值分别为5，13，7，4，20，34，16, 9，8。试为这9个字母设计哈夫曼编码。并计算其带权路径长度。 116 68 48 34 34 28 20 18 16 15 13 9 9 7 85 4 2. 拓朴排序为： 4 3 6 5 7 2 1 3. (1) 判断n是否是素数或质数2O4假定存在数据表：3，4，5，7，24，30，54，63，72，87，95，102，请解

16、决如下问题：1) 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，利用线性探测请画出存放状态；012345678910111210254345307728795246324,63,102共计比拟了3次2) 请按比拟顺序写出查找102的过程中比拟的数值，以及比拟的次数；5设要将序列Q, H, C, Y, P, A, M, S, R, D, F, X中的关键码按字母序的升序重新排列，那么写出希尔shell排序的过程，初始步长为4Shell P, A, C, S, Q, D, F, Y, R, H, M, C, A, , F D, M, H, P, S

17、, Q, Y, R, A C D F H M P Q R S Y三 程序题请写出折半查找方法的函数Search_Bin( SSTable S, value v)。要求：1函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值；2如果找到，那么函数返回值为该数在序列中的位置，否那么返回-1；3不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。见课本Int search(array ST, Key key)Low =1; high<=high;While(low<high)Mid=(low+high)/2;If(key

18、=arraymid.key) return mid;Else if (key<arraymid.key) high=mid-1;Else low=mid+1;return 0计算机学院2022-2022学年第一学期 数据结构 试卷A卷考试时间：100分钟专业： 班级： 序号： 姓名： 一. 填空每空2分，共40分1. 双向循环链表中，P指针所指向的结点的前驱指针域和后继指针域分别用prior和next表示，删除P指针所指向的结点，那么其根本操作为_ ,_ ,free(p)。2. 通常程序在调用另一个程序时，都需要使用一个 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。

19、3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，A的起始存储地址基址为1000，在行优先存储和列优先存贮情况下A5,5的存储地址分别为_,_。4. 设目标T=abccdcdccbaa，模式P=“cdcc，那么第 次匹配成功。5. 请描述在循环队列中，队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间，判断队空和队满的条件分别分：_,_。6. 字符串t=a very cute child，s=I like coffee and cake，请写出以下函数的结果：StrLength(t) =_;Concat(SubString(s,3,1

20、5)，SubString(t,12,6)=_。7. 一棵二叉树的后序序列为DECBHGFA，中序序列为BDCEAFHG，请画出这棵树的结构_。8. 请用数据序列53，13，24，37, 18, 90 构造一棵二叉排序树_。9. 二叉树的中序遍历相当于对应树的_遍历，或者对应森林的_遍历。10. 二叉树中元素完全序列按照顺序存储方式存放在如下一维数组中，那么结点G所在层次为 。01234567891011121314ABCDEFGHIJ11. 有n个结点的无向完全图和有向完全图的边数分别为_,_。12. 要从数据：1，3，5，7，9，11，13查找11，假设采用折半查找法，那么在 次比拟后，才找

21、到该数据。13. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下_最快，其时间复杂度为_。二. 简答题每题10分，共50分1 假设9个字母为：A B C D E F G H I，权值分别为5，13，7，4，20，34，16, 9，8。试为这9个字母设计哈夫曼编码。并计算其带权路径长度。要求画出树、写出编码，计算WPL2请对以下图的无向带权图：写出它的邻接矩阵，并按普里姆算法求其最小生成树。要求使用图画出每一步过程3试利用Dijkstra算法求图中从顶点V1到其他各顶点间的最短路径，写出执行算法过程中各步的状态。G使用邻接矩阵表示，要求使用表描述算法中每一步顶点与状态的变化情况，即求

22、解过程4假定存在数据表：3，4，5，7，24，30，54，63，72，87，95，102，请解决如下问题：3) 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，利用线性探测请画出存放状态；4) 请按比拟顺序写出查找102的过程中比拟的数值，以及比拟的次数；5设要将序列Q, H, C, Y, P, A, M, S, R, D, F, X中的关键码按字母序的升序重新排列，那么：1写出冒泡排序的过程；每一步过程2写出希尔shell排序的过程，初始步长为4。(每一步过程)三. 程序题10分编写算法判别给定二叉树是否为完全二叉树。要求：1函数为：int I

23、sFull_Bitree(Bitree T)/判断二叉树是否完全二叉树,是那么返回1,否那么返回02不用写主函数； 3如使用其他函数，请注释。 数据结构 A卷答案一填空每空2分，共40分1. p->prior->next=p->next , p->next->prior=p->prior。2. 递归工作栈 。3. 1270 , 1210 。4. 4-1 。5. Q.front=Q.rear, Q.front=Q.rear+1% MS 。6. 17 , “like coffee and child。7.CGEDFBHA 8. 243718901353 。9.

24、后序 , 中序 。10. 3 。11. n(n-1)/2 , n(n-1) 。12. 2 。13. 快速排序 , O(n lg n) 。二. 简答题1 先将概率放大100倍，以方便构造哈夫曼树。 w=7,19,2,6,32,3,21,10，按哈夫曼规那么：【2,3，6, (7,10)】, 19, 21, 3210040 6019 21 32 28（17） 11 7 10 6 5 2 3 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 编码为：A :1100 B:00 C:11110 D:1110 E:10 F: 11111 G:01 H:1101 2 请

25、对以下图的无向带权图：写出它的邻接矩阵，并按普里姆算法求其最小生成树解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种类!邻接矩阵为： 3 4 DAFIGCEBH其后续序列为：BHECIGFAD5 设要将序列Q, H, C, Y, P, A, M, S, R, D, F, X中的关键码按字母序的升序重新排列，那么：冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ；初始步长为4的希尔shell排序一趟的结果是 P A C S Q H F X R D M Y ；二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X；快速排序一趟扫

26、描的结果是 F H C D P A M Q R S Y X ；堆排序初始建堆的结果是 A D C R F Q M S Y P H X 。三. 程序题10分int IsFull_Bitree(Bitree T)/判断二叉树是否完全二叉树,是那么返回1,否那么返回0 InitQueue(Q); flag=0; EnQueue(Q,T); /建立工作队列 while(!QueueEmpty(Q) DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else EnQueue(Q,p->lchild); EnQueue(Q,p->rchi

27、ld); /不管孩子是否为空,都入队列 /while return 1; /IsFull_Bitree计算机学院2022-2022学年第一学期 数据结构 试卷B卷考试时间：100分钟专业： 班级： 序号： 姓名： 一填空每空2分，共40分1.双向循环链表中，结点的前驱指针域和后继指针域分别用prior和next表示，删除P指针所指向的结点，那么其根本操作为_ ,_。2. 通常程序在调用另一个程序时，都需要使用一个 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。3.有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，A的起始存储地址基址为1000，在行优先

28、存储和列优先存贮情况下A5,5的存储地址分别为_,_。4. 设目标T=abccdcdccbaa，模式P=“cdcc，那么第 次匹配成功。5.请描述在循环队列中，队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间，判断队空和队满的条件分别分：_,_。6.字符串t=a very cute child，s=I like coffee and cake，请写出以下函数的结果：StrLength(s) =_;Concat(SubString(s,3,15)，SubString(t,12,6)=_。7. 在具有n个单元的循环队列中，队满时共有 个元素。8. 深度为k 的二叉

29、树的结点总数，最多为_个。最少为_个。9二叉树中元素按照顺序存储方式存放在如下一维数组中，那么结点G所在层次为 。01234567891011121314ABCDEFGHIJ10. 有n个结点的无向完全图和有向完全图的边数分别为_,_。11. 图的深度优先遍历算法类似于树的 。12. 要从序列1，3，5，7，9，11，13中查找11，假设采用折半查找法，那么在 次比拟后，才找到该数据。13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下_最快，其时间复杂度为_。二简答题：每题10分，共50分1. 假设9个字母为：A B C D E F G H，权值分别为5，13，7，4，20，34

30、，16, 9，8。试为这9个字母设计哈夫曼编码。并计算其带权路径长度。2. 森林和二叉树的转换，画出和以下二叉树相应的森林3. 使用克鲁斯卡尔算法求以下图中最小生成树，请写出步骤。bcdehgfki23625431134假定存在数据表：3，4，5，7，24，30，54，63，72，87，95，102，请解决如下问题：1) 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，利用线性探测请画出存放状态；2) 请按比拟顺序写出查找102的过程中比拟的数值，以及比拟的次数；5设要将序列Q, H, C, Y, P, A, M, S, R, D, F, X中的

31、关键码按字母序的升序重新排列，那么：1写出冒泡排序的过程；2写出希尔shell排序的过程，初始步长为4三 程序题请写出折半查找方法的函数Search_Bin( SSTable S, value v)。要求：1函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值；2如果找到，那么函数返回值为该数在序列中的位置，否那么返回-1；3不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。计算机学院2022-2022学年第一学期 数据结构 试卷B卷(答案专业： 班级： 序号： 姓名： 一填空每空2分，共40分1.双向循环链表中，结点的前驱

32、指针域和后继指针域分别用prior和next表示，删除P指针所指向的结点，那么其根本操作为_ p->prior->next=p->next , p->next->prior=p->prior。2. 通常程序在调用另一个程序时，都需要使用一个 栈 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。3.有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，A的起始存储地址基址为1000，在行优先存储和列优先存贮情况下A5,5的存储地址分别为_1270 , 1210_。4. 设目标T=abccdcdccbaa，模式P=“cdcc，

33、那么第 6次匹配成功。5.请描述在循环队列中，队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间，判断队空和队满的条件分别分：_ Q.front=Q.rear, Q.front=Q.rear+1% MS _。6.字符串t=a very cute child，s=I like coffee and cake，请写出以下函数的结果：StrLength(s) =_22_;Concat(SubString(s,3,15)，SubString(t,12,6)=_ like coffee and child _。7. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。

34、8. 深度为k 的二叉树的结点总数，最多为_2k-1_个。最少为_k_个。9二叉树中元素按照顺序存储方式存放在如下一维数组中，那么结点G所在层次为 3 。01234567891011121314ABCDEFGHIJ10. 有n个结点的无向完全图和有向完全图的边数分别为_ n(n-1)/2 , n(n-1) _。11. 图的深度优先遍历算法类似于树的 先序 。12. 要从序列1，3，5，7，9，11，13中查找11，假设采用折半查找法，那么在 2 次比拟后，才找到该数据。13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下_最快，其时间复杂度为_。快速排序 , O(n lg n)二简

35、答题：每题10分，共50分1. 假设9个字母为：A B C D E F G H，权值分别为5，13，7，4，20，34，16, 9，8。试为这9个字母设计哈夫曼编码。并计算其带权路径长度。 116 68 48 34 34 28 20 18 16 15 13 9 9 7 85 4 2. 森林和二叉树的转换，画出和以下二叉树相应的森林 a c f i B e m D h k G j3. 使用Prim算法求以下图中最小生成树。bcdehgfki23625431134假定存在数据表：3，4，5，7，24，30，54，63，72，87，95，102，请解决如下问题：5) 假设哈希函数为：H(key)=k

36、ey mod 13，用该哈希函数将数据表存入长度为13的哈希表，利用线性探测请画出存放状态；012345678910111210254345307728795246324,63,102共计比拟了3次6) 请按比拟顺序写出查找102的过程中比拟的数值，以及比拟的次数；5设要将序列Q, H, C, Y, P, A, M, S, R, D, F, X中的关键码按字母序的升序重新排列，那么：1写出冒泡排序的过程；2写出希尔shell排序的过程，初始步长为4Shell P, A, C, S, Q, D, F, Y, R, H, M, C, A, , F D, M, H, P, S, Q, Y, R, A

37、 C D F H M P Q R S Y三 程序题请写出折半查找方法的函数Search_Bin( SSTable S, value v)。要求：1函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值；2如果找到，那么函数返回值为该数在序列中的位置，否那么返回-1；3不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。见课本Int search(array ST, Key key)Low =1; high<=high;While(low<high)Mid=(low+high)/2;If(key=arraymid.ke

38、y) return mid;Else if (key<arraymid.key) high=mid-1;Else low=mid+1;return 0计算机学院2009-2022学年第一学期 数据结构 试卷A卷考试时间：100分钟一单项选择每题2分，共20分1下面程序段的时间复杂度是_。 for(i=0;i<n;i+) for(j=1;j<m;j+)Aij=0； AO(n)BO(m+n+1)CO(m + n)DO(m*n)2在n个结点的顺序表中，算法的时间复杂度是O1的操作是_。1) 访问第i个结点1in和求第i个结点的直接前驱2in 2) 在第i个结点后插入一个新结点1in3) 删除第i个结点1in4) 将n个结点从小到大排序3在单链表中，假设p所指结点不是最后结点，在p之后插入s所指结点，那么执行_。A. s->next = p; p->next = s;B. s->next = p->next; p->next = s;C. s->next = p->nex