《2022年数据结构练习参考 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构练习参考 .pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构练习1填写下面表格，对以下几种排序方法进行比较：习题一填空题1 进栈序列是1、2、3、4，进栈过程中可以出栈，则可能的出栈序列有个，不可能的出栈序列是。2 具有 N 个元素的顺序存储的循环队列中，假定front 和 rear 分别指向队头元素的前一位置和队尾元素的位置，则判断队空的和队满的条件分别是f=r 和f=r mod m+1。求 此 队 列 中 元 素 个 数 的 计 算 公 式 为：(r+m)-f-1)mod m+1。入队运算：r:=r mod m+1。出队运算：f:=f mod m+1。3 单链表是非顺序线性的链式存储结构，链栈和链队分别是和的链式存储结构。4线性表的顺序存储
2、中，元素之间的逻辑关系是通过元素存储地址次序决定的，在线性表的链接存储中，元素之间的逻辑关系是通过元素存储指针地址访问决定的。5深度为 5 的二叉树至多有结点数为31。6 数据结构即数据的逻辑结构包括顺性存储结构、链式存储结构、非线性结构三种类型，树型结构和图型结构称为非线性结构。？四种基本存储方法：（1）顺序存储方法（2）链接存储方法（3）索引存储方法（4）散列存储方法二选择题排序方法平均时间复杂度最坏情况空间复杂度是否稳定选择排序直接选择排序O(n2)O(n2)O(1)不稳定堆排序O(nlog2n)O(nlog2n)O(1)不稳定插入排序直接接插入排序O(n2)O(n2)O(1)稳定拆半接
3、插入排序O(nlog2n)O(n2)O(1)稳定Shell 排序O(nlog2n)O(nlog2n)O(1)不稳定冒泡排序交换排序O(n2)O(n2)O(1)稳定快速排序O(nlog2n)O(n2)O(1)不稳定归并排序2-路归并排序O(nlog2n)O(nlog2n)O(n)稳定红黑树O(nlog2n)O(nlog2n)O(1)不稳定线性排序计数排序O(N+K)O(N+K)O(N+K)稳定桶排序O(N)O(N)O(N)稳定基数排序O(d(n+rd)O(d(n+rd)O(rd)稳定解释：时间复杂度O(d(n+rd)：其中分配为O（n）；收集为O（rd）（r 为基、d 为“分配收集”的趟数）名师
4、资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 13 页 -1 有一个 10 阶对称矩阵，采用压缩存储方式，以行序为主序存储，A00的地址为1，则 A74的地址为（C ）A 13 B 18 C 33 D 402 线性表采用链表存储时其存储地址D。A必须是连续的 B部分地址必须是连续的C一定是不连续的 D连续不连续都可以3 下列叙述中错误的是 C。A串是一种特殊的线性表，其特殊性体现在数据元素是一个字符B栈和队列是两种特殊的线性表，栈的特点是后进先出，队列的特点是先进先出。C线性表的线性存储结构优于链式存储结构D二维数组是其数据元素为线性表的线性表4 一棵二叉树的顺序存储结构如题图4-
5、1 所示，若中序遍历该二叉树，则遍历次序为A .A.DBEGACFH B.ABDEGCFH C.DGEBHFCA D.ABCDEFGH 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5设一棵二叉树的顺序存储结构如题图4-2 所示，则该二叉树是 C .A完全二叉树 B满二叉树 C深度为 4 的二叉树D深度为 3 的二叉树 1 2 3 4 5 6 7 8 9 10 11 6设 T 是 Huffman 树，它具有6 个树叶，且各树叶的权分别为1，2，3，4，5，6。那么该树的非叶子结点的权之和为A。A 51 B 21 C 30 D49 7设有一无向图的邻接矩阵如下所示，则该图所有
6、顶点的度之和为C。a b c d e a 0 1 1 1 0 b 1 0 1 0 1 c 1 1 0 0 0 d 1 0 0 0 0 e 0 1 0 0 0 A B C D E F G H 1 2 3 4 5 6 7 题图 4-1题图 4-2名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 13 页 -A8 B9 C10 D 11 8已知二叉树的后序遍历序列是fedbgca，中序遍历序列是dfebagc，则该二叉树的先序遍历序列是 D。Adefbagc B abcdgef Cdbaefcg Dabdefcg 9由三个结点构成的二叉树，共有 C种不同的形态。A3 B 4 C 5 D
7、6 10在一个具有n 个顶点的无向图中，要连通全部顶点至少需要 D条边 A n Bn+1 Cn/2 D n-1 11对线性表进行折半（二分）查找时，要求线性表必须B。A以顺序方式存储 B以顺序方式存储且数据元素有序C以链表方式存储 D以链表方式存储且数据元素有序12顺序查找一个具有n 个元素的线性表，其时间复杂度为A，二分查找一个具有n 个元素的线性表，其时间复杂度为B。A O(n)B O(log2n)C O(n2)DO(nlog2n)13.从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列中的正确位置上，此方法称为直接插入排序；从未排序序列中挑选元素，并将其放入已排序
8、序列中的一端，此方法称为直接选择排序；依次将每两个相临的有序表合并成一个有序表的排序方法称为归并排序；当两个元素比较出现反序时就相互交换位置的排序方法称为交换排序；A归并排序 B 选择排序C交换排序 D插入排序三简述下面的几个概念：单链表，栈、队列，排序二叉树。四简述空串和空格串的区别。五一棵度为2 的树与二叉树有何区别？六试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。七已知一二叉树如题图4-3 所示，1 用二叉链表和顺序存储方式分别存储此二叉树。画出相应的存储结构图。2 写出此二叉树的中序、先序、后序遍历序列。八已知一无向图如题图4-4 所示，请给出该图的1 每个顶点的度。
9、2 邻接矩阵3 邻接表4 按上述的邻接表写出广度和深度遍历序列。九已知一组数据元素为（46，75，18，54，15，27，42，39，88，67）A B C D E F G H 图 4-3 1 2 3 4 5 6 题图 4-4 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 13 页 -1 利用直接插入排序方法，写出每次插入后的结果。2 利用快速排序方法，写出每趟排序后的结果。3 利用 2-路归并排序方法，写出每趟归并后的结果。4 利用冒泡排序方法，写出每趟排序后的结果。十假定一个表为（32，75，63，48，94，25，36，18，70），散列空间为0.10，1 若采用除留余数
10、法构造表，哈希函数为H（K）=K MOD 11，用线性探测法解决冲突，试画出哈希表，并求在等概率情况下的平均查找长度。2 若采用除留余数法构造表，哈希函数为H（K）=K MOD 11，用链地址法解决冲突，试画出哈希表，并求在等概率情况下的平均查找长度。十一有 8 个带权结点，权值为（3，7，8，2，6，10，14，9），试以它们为叶子结点构造一棵哈夫曼树（要求每个结点左子树的权值小于等于右子树的权值），并计算出带权路径长度。十二一对称阵 An*n，若只存储此对称阵的上半三角元，写出以行为主序存储和以列为主序存储时计算每一元素Aij存储地址的公式。十三算法设计1 写出在循环单链表L 中查找查找第
11、i 个元素的算法：SEARCH（L，i）。2 设有如下题图4-3 的单链表，链表头指针为H，写一个将链表进行逆转的算法，逆转以后的链表为题图4-4 所示。3 假定用一个带头结点的循环单链表表示循环队列（循环链队），该队列只设一个队尾指针，不设头指针，试编写下面的算法：A 向循环链队中插入一个元素x 的算法（入队）。B从循环链队中删除一个结点（出队）。4 数组 AN 存放循环队列中的元素，同时设两个变量分别存储队尾元素的位置和队列中实际元素个数。A 写出此队列的队满条件。B写出此队列的出、入队算法。5 设 LA 和 LB 为两个顺序存储的线性表，且元素按非递减排列，写出算法将其合并为LC，且 L
12、C 中的元素也按非递减排列。6 已知一个由n 个整数组成的线性表，请定义该线性表的一种存储结构，并用C语言编写算法，实现将 n 个元素中所有大于等于20 的整数放在所有小于等于20 的整数之后，要求算法的时间复杂度为O（n）,空间复杂度为O（1）。a1 a2an NULLH,题图 4-3 单链表示意图an an-1a1 NULLH,题图 4-4 单链表示意图名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 13 页 -7 编写算法，计算二叉树中叶子结点的数目。8 编写一个按层次顺序（同一层自左向右）遍历二叉树的算法。三种基于“分配”“收集”的线性排序算法-计数排序、桶排序与基数排序
13、文中代码见原文链接：http:/ 在计算机科学中，排序是一门基础的算法技术，许多算法都要以此作为基础，不同的排序算法有着不同的时间开销和空间开销。排序算法有非常多种，如我们最常用的快速排序和堆排序等算法，这些算法需要对序列中的数据进行比较，因为被称为基于比较的排序。基于比较的排序算法是不能突破O(NlogN)的。简单证明如下：N 个数有 N!个可能的排列情况，也就是说基于比较的排序算法的判定树有N!个叶子结点，比较次数至少为log(N!)=O(NlogN)(斯特林公式)。而非基于比较的排序，如计数排序，桶排序，和在此基础上的基数排序，则可以突破O(NlogN)时间下限。但要注意的是，非基于比较
14、的排序算法的使用都是有条件限制的，例如元素的大小限制，相反，基于比较的排序则没有这种限制(在一定范围内)。但并非因为有条件限制就会使非基于比较的排序算法变得无用，对于特定场合有着特殊的性质数据，非基于比较的排序算法则能够非常巧妙地解决。本文着重介绍三种线性的非基于比较的排序算法：计数排序、桶排序与基数排序。计数排序 首先从 计数排序(Counting Sort)开始介绍起，假设我们有一个待排序的整数序列A，其中元素的最小值不小于0，最大值不超过K。建立一个长度为K 的线性表C，用来记录不大于每个值的元素的个数。算法思路如下：扫描序列 A，以 A 中的每个元素的值为索引，把出现的个数填入C 中。
15、此时Ci可以表示 A 中值为 i 的元素的个数。对于 C 从头开始累加，使Ci-Ci+Ci-1。这样，Ci 就表示 A 中值不大于 i的元素的个数。按照统计出的值，输出结果。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 13 页 -由线性表 C 我们可以很方便地求出排序后的数据，定义B 为目标的序列，Orderi为排名第 i 的元素在 A 中的位置，则可以用以下方法统计。?View Code CPP 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
16、34/*Memo:计数排序*/#include#include#include#include#include usingnamespace std;void CountingSort(int*A,int*B,int*Order,int N,int K)int*C=newint K+1;int i;memset(C,0,sizeof(int)*(K+1);for(i=1;i=N;i+)/把 A 中的每个元素分配C A i +;for(i=2;i=1;i-)B C A i=A i ;/按照统计的位置，将值输出到B中，将顺序输出到Order中Order C A i=i;C A i -;int ma
17、in()int*A,*B,*Order,N=15,K=10,i;A=newint N+1;B=newint N+1;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 13 页 -35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 Order=new int N+1;for(i=1;i=N;i+)A i =rand()%K+1;/生成 1.K的随机数printf(Before CS:/n );for(i=1;i=N;i+)printf(%d ,A i);CountingSort(A,B,Order,N,K);printf(/n After CS:
18、/n );for(i=1;i=N;i+)printf(%d ,B i);printf(/n Order:/n );for(i=1;i=N;i+)printf(%d ,Order i);return0;程序运行效果如下：Before CS:2 8 5 1 10 5 9 9 3 5 6 6 2 8 2 After CS:1 2 2 2 3 5 5 5 6 6 8 8 9 9 10 Order:4 1 13 15 9 3 6 10 11 12 2 14 7 8 5 显然地，计数排序的时间复杂度为O(N+K)，空间复杂度为O(N+K)。当 K 不是很大时，这是一个很有效的线性排序算法。更重要的是，它是
19、一种 稳定排序算法，即排序后的相同值的元素原有的相对位置不会发生改变(表现在 Order上)，这是计数排序很重要的一个性质，就是根据这个性质，我们才能把它应用到基数排序。桶排序 可能你会发现，计数排序似乎饶了点弯子，比如当我们刚刚统计出C，Ci 可以表示A 中值为 i 的元素的个数，此时我们直接顺序地扫描C，就可以求出排序后的结果。的确是这样，不过这种方法不再是计数排序，而是桶排序(Bucket Sort)，确切地说，是桶排序的一种特殊情况。用这种方法，可以很容易写出程序，比计数排序还简单，只是不能求出稳定的Order。?View Code CPP 名师资料总结-精品资料欢迎下载-名师精心整理
20、-第 7 页，共 13 页 -1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36/*Memo:桶排序特殊实现*/#include#include#include#include#include usingnamespace std;void BucketSort(int*A,int*B,int N,int K)int*C=newint K+1;int i,j,k;memset(C,0,sizeof(int)*(K+1);for(i=1;i=N;i+)
21、/把 A 中的每个元素按照值放入桶中C A i +;for(i=j=1;i=K;i+,j=k)/统计每个桶元素的个数，并输出到 Bfor(k=j;kj+C i ;k+)B k=i;int main()int*A,*B,N=1000,K=1000,i;A=newint N+1;B=newint N+1;for(i=1;i=N;i+)A i =rand()%K+1;/生成 1.K的随机数BucketSort(A,B,N,K);for(i=1;i=N;i+)printf(%d ,B i);return0;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 13 页 -这种特殊实现的方式时间
22、复杂度为O(N+K)，空间复杂度也为O(N+K)，同样要求每个元素都要在 K 的范围内。更一般的，如果我们的K 很大，无法直接开出O(K)的空间该如何呢？首先定义桶，桶为一个数据容器，每个桶存储一个区间内的数。依然有一个待排序的整数序列 A，元素的最小值不小于0，最大值不超过K。假设我们有M 个桶，第i 个桶 Bucketi存储 i*K/M至(i+1)*K/M之间的数，有如下桶排序的一般方法：扫描序列A，根据每个元素的值所属的区间，放入指定的桶中(顺序放置)。对每个桶中的元素进行排序，什么排序算法都可以，例如快速排序。依次收集每个桶中的元素，顺序放置到输出序列中。对该算法简单分析，如果数据是期
23、望平均分布的，则每个桶中的元素平均个数为N/M。如果对每个桶中的元素排序使用的算法是快速排序，每次排序的时间复杂度为O(N/M*log(N/M)。则总的时间复杂度为O(N)+O(M)*O(N/M*log(N/M)=O(N+N*log(N/M)=O(N+N*logN N*logM)。当 M 接近于 N 是，桶排序的时间复杂度就可以近似认为是O(N)的。就是桶越多，时间效率就越高，而桶越多，空间却就越大，由此可见时间和空间是一个矛盾的两个方面。桶中元素的顺序放入和顺序取出是有必要的，因为这样可以确定桶排序是一种稳定排序算法，配合基数排序是很好用的。?View Code CPP 1 2 3 4 5
24、6 7 8 9 10 11 12 13 14 15 16 17 18/*Memo:桶排序一般实现*/#include#include#include#include#include usingnamespace std;struct linklist linklist*next;int value;linklist(int v,linklist*n):value(v),next(n)linklist()if(next)delete next;inlineint cmp(constvoid*a,constvoid*b)return*(int*)a-*(int*)b;名师资料总结-精品资料欢迎下载
25、-名师精心整理-第 9 页，共 13 页 -19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56/*为了方便，我把 A 中元素加入桶中时是倒序放入的，而收集取出时也是倒序放入序列的，所以不违背稳定排序。*/void BucketSort(int*A,int*B,int N,int K)linklist*Bucket 101 ,*p;/建立桶int i,j,k,M;M=K/100;memset(Bucket,0,sizeof
26、(Bucket);for(i=1;i=N;i+)k=A i /M;/把 A 中的每个元素按照的范围值放入对应桶中Bucket k=new linklist(A i ,Bucket k);for(k=j=0;knext)B+j =p-value;/把桶中每个元素取出，排序并加入 Bdelete Bucket k;qsort(B+i+1,j-i,sizeof(B 0),cmp);int main()int*A,*B,N=100,K=10000,i;A=newint N+1;B=newint N+1;for(i=1;i=N;i+)名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 13
27、页 -57 58 59 A i =rand()%K+1;/生成 1.K的随机数BucketSort(A,B,N,K);for(i=1;i=N;i+)printf(%d ,B i);return0;基数排序 下面说到我们的重头戏，基数排序(Radix Sort)。上述的基数排序和桶排序都只是在研究一个关键字的排序，现在我们来讨论有多个关键字的排序问题。假设我们有一些二元组(a,b)，要对它们进行以a 为首要关键字，b 的次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一
28、堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。第二种方式是从最低有效关键字开始排序，称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD 方法往往比MSD 简单而开销小。下文介绍的方法全部是基于LSD 的。通常，基数排序要用到计数排序或者桶排序。使用计数排序时，需要的是Order数组。使用桶排序时，可以用链表的方法直接求出排序后的顺序。下面是一段用桶排序对
29、二元组基数排序的程序：?View Code CPP 1 2 3 4 5 6 7 8 9 10 11 12 13/*Memo:基数排序结构数组*/#include#include#include#include#include usingnamespace std;struct data int key 2;struct linklist 名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 13 页 -14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
30、 45 46 47 48 49 50 51 linklist*next;data value;linklist(data v,linklist*n):value(v),next(n)linklist()if(next)delete next;void BucketSort(data*A,int N,int K,int y)linklist*Bucket 101 ,*p;/建立桶int i,j,k,M;M=K/100+1;memset(Bucket,0,sizeof(Bucket);for(i=1;i=N;i+)k=A i .key y/M;/把 A 中的每个元素按照的范围值放入对应桶中Buck
31、et k=new linklist(A i ,Bucket k);for(k=j=0;knext)j+;for(p=Bucket k,i=1;p;p=p-next,i+)A j-i+1=p-value;/把桶中每个元素取出delete Bucket k;void RadixSort(data*A,int N,int K)for(int j=1;j=0;j-)/从低优先到高优先 LSDBucketSort(A,N,K,j);int main()int N=100,K=1000,i;名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 13 页 -52 53 54 55 56 57 58
32、 59 60 61 62 63 data*A=new data N+1;for(i=1;i=N;i+)A i .key 0=rand()%K+1;A i .key 1=rand()%K+1;RadixSort(A,N,K);for(i=1;i=N;i+)printf(%d,%d),A i .key 0,A i .key 1);printf(/n );return0;基数排序是一种用在老式穿卡机上的算法。一张卡片有80 列，每列可在12 个位置中的任一处穿孔。排序器可被机械地”程序化”以检查每一迭卡片中的某一列，再根据穿孔的位置将它们分放 12 个盒子里。这样，操作员就可逐个地把它们收集起来。其
33、中第一个位置穿孔的放在最上面，第二个位置穿孔的其次，等等。对于一个位数有限的十进制数，我们可以把它看作一个多元组，从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序。三种线性排序算法的比较 从整体上来说，计数排序，桶排序都是非基于比较的排序算法，而其时间复杂度依赖于数据的范围，桶排序还依赖于空间的开销和数据的分布。而基数排序是一种对多元组排序的有效方法，具体实现要用到计数排序或桶排序。相对于快速排序、堆排序等基于比较的排序算法，计数排序、桶排序和基数排序限制较多，不如快速排序、堆排序等算法灵活性好。但反过来讲，这三种线性排序算法之所以能够达到线性时间，是因为充分利用了待排序数据的特性，如果生硬得使用快速排序、堆排序等算法，就相当于浪费了这些特性，因而达不到更高的效率。在实际应用中，基数排序可以用于后缀数组的倍增算法，使时间复杂度从O(N*logN*logN)降到 O(N*logN)。线性排序算法使用最重要的是，充分利用数据特殊的性质，以达到最佳效果。名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 13 页 -