3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续(   )

6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个

8、线性的数据结构可以顺序存储也可以链接存储。非线性的数据结构只能链接存储（     ）

11、删除二叉简单选择排序怎么排树中一个结点，再重新插入上去一定能得到原来的二叉简单选择排序怎么排树。（  ）

12、快速简单选择排序怎么排是简单选择排序怎么排算法中最快的┅种（  ）

16、98、对一个堆按层次遍历，不一定能得到一个有序序列（  ）

17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个度为k嘚结点有nk个，则有n0=nk+1（   ）

18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表（   ）

24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（    ）

25、用一组地址连续的存储单元存放的元素一定构成线性表（    ）

28、只有在初始数据为逆序时，冒泡简单选择排序怎么排所执行的比较次数最多（   ）

29、希尔简单选择排序怎么排在较率上较直接接入简单选择排序怎么排有较大的改進。但是不稳定的（  ）

30、在平均情况下，快速简单选择排序怎么排法最快堆积简单选择排序怎么排法最节省空间。（    ）

35、数据的存储結构不仅有顺序存储结构和链式存储结构还有索引结构与散列结构。（      ）

37、若线性表采用顺序存储结构每个数据元素占用4个存储单元，第12个数据元素的存储地址为144则第1个数据元素的存储地址是101。（     ）

45、线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的（    ）

47、稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储（     ）

48、不管堆栈采用何种存储结构，只要堆栈不空可以任意删除一个元素。（    ）

52、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树（     ）

54、对一棵二叉简单选择排序怎麼排树进行前序遍历一定可以得到一个按值有序的序列。（    ）

55、一个广义表的深度是指该广义表展开后所含括号的层数（   ）

56、散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。（     ）

57、序列初始为逆序时冒泡简单选择排序怎么排法所进行的元素之间的比較次数最多。（     ）

58、已知指针P指向键表L中的某结点执行语句P=P-〉next不会删除该链表中的结点。

61、设与一棵树T所对应的二叉树为BT则与T中的叶孓结点所对应的BT中的结点也一定是叶子结点。（     ）

62、若图G的最小生成树不唯一则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的頂点数）（    ）

63、给出不同的输入序列建造二叉简单选择排序怎么排树，一定得到不同的二叉简单选择排序怎么排树（     ）

64、由于希尔简單选择排序怎么排的最后一趟与直接插入简单选择排序怎么排过程相同，因此前者一定比后者花费的时间多（     ）

70、带权连通图中某一顶點到图中另一定点的最短路径不一定唯一。（    ）

76、若一个有向图的邻接矩阵中,对角线以下元素均为0,则该图的拓扑有序序列必定存在（   ）

77、树的带权路径长度最小的二叉树中必定没有度为1的结点。（    ）

87、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内以尽可能减少冲突。（     ）

88、简单选择排序怎么排是计算机程序设计中的一种重要操作它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列（    ）

90、在索引顺序表上实现分块查找，在等概率查找情况下其平均查找长度不与表的个数有關，而与每一块中的元素个数有关（   ）

91、对于有向图，顶点的度分为入度和出度入度是以该顶点为终点的入边数目；出度是以该顶点為起点的出边数目，该顶点的度等于其入度和出度之和（    ）

92、无向图的邻接矩阵是对称的有向图的邻接矩阵是不对称的。（    ）

1、《数据結构》课程讨论的主要内容是数据的逻辑结构、存储结构和______________

2、数据结构算法中，通常用时间复杂度和__________________两种方法衡量其效率

4、若频繁地對线性表进行插入与删除操作，该线性表应采用____________存储结构

5、在非空线性表中除第一个元素外，集合中每个数据元素只有一个_______；除最后一個元素之外集合中每个数据元素均只有一个_________。

7、______链表从任何一个结点出发都能访问到所有结点。

9、在双向链表中每个结点含有两个指针域，一个指向______结点另一个指向________结点。

10、某带头结点的单链表的头指针head判定该单链表非空的条件______________。

11、在双向链表中每个结点含有兩个指针域，一个指向_______结点另一个指向_____结点。

13、已知在结点个数大于1的单链表中指针p指向某个结点，则下列程序段结束时指针q指向*p嘚_____________结点。

14、若要在单链表结点*P后插入一结点*S执行的语句_______________。

15、线性表的链式存储结构地址空间可以_________而向量存储必须是地址空间___________。

16、栈结構允许进行删除操作的一端为_____________

17、在栈的顺序实现中，栈顶指针top栈为空条件______________。

18、对于单链表形式的队列其空队列的F指针和R指针都等于__________________。

19、若数组s[0..n-1]为两个栈s1和s2的共用存储空间仅当s[0..n-1]全满时，各栈才不能进行栈操作则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初徝分别为_________。

20、允许在线性表的一端插入,另一端进行删除操作的线性表称为_______插入的一端为______,删除的一端为______。

22、对于顺序存储的队列存储空間大小为n，头指针为F尾指针为R。若在逻辑上看一个环则队列中元素的个数为___________。

23、已知循环队列的存储空间为数组data[21]且头指针和尾指针汾别为8和3，则该队列的当前长度__________

24、一个串的任意个连续的字符组成的子序列称为该串的________，包含该子串的串称为

26、在初始为空的队列中插叺元素A,B,C,D以后紧接着作了两次删除操作，此时的队尾元素是__________

27、在长度为n的循环队列中，删除其节点为x的时间复杂度为_______________

29、已知一顺序存儲的线性表，每个结点占用k个单元若第一个结点的地址为DA1，则第i个结点的地址为______________

31、设有二维数组A[9][19]，其每个元素占两个字节第一个元素的存储地址为100，若按行优先顺序存储则元素A[6,6]的存储地址为______________，按列优顺序存储元素A[6,6]的存储地址为______________。

32、在进行直接插入简单选择排序怎麼排时, 其数据比较次数与数据的初始排列________关；而在进行直接选择简单选择排序怎么排时其数据比较次数与数据的初始排列__________关。

35、稀疏矩陣一般采用__________方法进行压缩存储

37、若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0则称为__________。

39、对于上彡角形和下三角形矩阵分别以按行存储和按列存储原则进行压缩存储到数组M[k]中，若矩阵中非0元素为Aij则k对应为________和__________。

40、设有一上三角形矩陣A[5][5]按行压缩存储到数组B中B[0]的地址为100，每个元素占2个单元则A[3][2]地址为____________。

44、在树结构里有且仅有一个结点没有前驱，称为根非根结点有苴仅有一个___________,且存在一条从根到该结点的_______________。

45、度数为0的结点即没有子树的结点叫作__________结点或_________结点。同一个结点的儿子结点之间互称为___________结点 

48、完全二叉树、满二叉树、线索二叉树和二叉简单选择排序怎么排树这四个名词术语中，与数据的存储结构有关系的是_____________

47、有三个结点的②叉树，最多有________种形状

48、每一趟简单选择排序怎么排时从排好序的元素中挑出一个值最小的元素与这些未排小序的元素的第一个元素交換位置，这种简单选择排序怎么排方法成为_____________简单选择排序怎么排法

49、高度为k的二叉树具有的结点数目，最少为_____,最多为_____

50、对任何一棵二叉树，若n0n1，n2分别是度为01，2的结点的个数则n0=_______。

51、在含100个结点的完全二叉树叶子结点的个数为_______。

52、将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列叫_____。

53、若一棵满二叉树含有121个结点则该树的深度为_________。

54、一个具有767个结点的完全二叉树其叶孓结点个数为________。

55、深度为90的满二叉树第11层有________个结点。

56、有100个结点的完全二叉树深度为________。

57、设一棵二叉树中度为2的结点10个则该树的叶孓个数为________。

59、含有3个2度结点和4个叶结点的二叉树可含__________个1度结点

60、一棵具有５层满二叉树中节点总数为___________。

61、一棵含有16个结点的完全二叉树对他按层编号，对于编号为7的结点他的双亲结点及左右结点编号为______、______、_______。

62、深度为k(设根的层数为1)的完全二叉树至少有_______个结点, 至多有_______个結点

63、若要对某二叉简单选择排序怎么排树进行遍历，保证输出所有结点的值序列按增序排列应对该二叉简单选择排序怎么排树采用________遍历法。

65、设有10个值构成哈夫曼树，则该哈夫曼树共有______个结点

66、从树中一个结点到另一个结点之间的分支构成这两个结点之间的____________。

67、關键字自身作为哈希函数即H（k）=k，也可自身加上一个常数作为哈希函数即H(k)=k+C这种构造哈希函数的方式叫____________。

68、对于一个图G若边集合E（G）為无向边的集合，则称该图为____________

69、对于一个图G，若边集合E（G）为有向边的集合则称该图为____________。

70、对于有向图顶点的度分为入度和出度，鉯该顶点为终点的边数目叫________；以该顶点为起点的边数目叫_________

71、一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个______________

72、有一个n个顶點的有向完全图的弧数_____________。

73、在无向图中若从顶点A到顶点B存在_________，则称A与B之间是连通的

74、在一个无向图中，所有顶点的度数之和等于所有邊数的___________倍

75、一个连通图的生成树是该图的____________连通子图。若这个连通图有n个顶点, 则它的生成树有__________条边

77、如果从一无向图的任意顶点出发进荇一次深度优先搜索即可访问所有顶点，则该图一定是_____ _______

78、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的____________遍历

79、若图嘚邻接矩阵是对称矩阵，则该图一定是________________

80、从如图所示的临接矩阵可以看出，该图共有______个顶点如果是有向图，该图共有______条弧；如果是无姠图则共有________条边。

81、如果从一个顶点出发又回到该顶点则此路径叫做___________。

82、一个具有个n顶点的无向图中要连通全部顶点至少需要________条边。

84、从未简单选择排序怎么排序列中选择一个元素该元素将当前参加简单选择排序怎么排的那些元素分成前后两个部分，前一部分中所囿元素都小于等于所选元素后一部分中所有元素都大于或等于所选元素，而此时所选元素处在简单选择排序怎么排的最终位置这种简單选择排序怎么排法称为_____________简单选择排序怎么排法。

87、在索引查找中首先查找________，然后查找相应的_________整个索引查找的平均查找长度等于查找索引表的平均长度与查找相应子表的平均查找长度的_______。

（   ）3.将一棵有100个结点的完全二叉树从上到下从左到右依次对结点进行编号，根结點的编号为1则编号为49的结点的左孩子的编号为______。

A.被简单选择排序怎么排数据中含有多个相同简单选择排序怎么排码  B.被简单选择排序怎么排数据已基本有序

A减少存取时间,降低下溢发生的机率  B节省存储空间,降低上溢发生的机率

C减少存取时间,降低上溢发生的机率  D节省存储空间,降低下溢发生的机率

（    ）12.设长度为n的链队列用单循环链表表示若只设头指针，则入队操作的时间复杂度为_______

　　 已知指针p所指结点不是尾結点，若在*p之后插入结点*s则应执行下列哪一个操作______。

非空的循环单链表first的尾结点（由p所指向）满足：______

（   ）19.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是________

（   ）26．如果某图的邻接矩阵是对角线元素均为零的上三角矩阵则此图是_______

C.强连通图 D.有向無环图

A．用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关 

B．用相邻矩阵法存储图,占用的存储空间数只与图中边數有关,而与结点个数无关

C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关而与边数无关

D．用邻接表法存储图，占用的存儲空间数只与图中边数有关而与结点个数无关

（   ）34.在长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时需要从前向后依次前移____個元素。

（   ）35.设一个广义表中结点的个数为n则求广义表深度算法的时间复杂度为____。

（   ）38．若需要利用形参直接访问实参则应把形参变量说明为____参数。

（    ）39．在一个单链表HL中若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行____

（   ）41．向二叉搜索树中插入┅个元素时，其时间复杂度大致力____

C.简单选择排序怎么排算法 D.解决问题的有限运算序列

C.必须是连续的 D.和头结点的存储地址相连续

（   ）44.将长充为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为________

A.减少存取时间，降低下溢发生的机率 B.节省存储空间降低上溢发生的机率

C.減少存取时间，降低上溢发生的机率 D.节省存储空间降低下溢发生的机率

（   ）48.若目标串的长充为n，模式串的长度为[n/3]则执行模式匹配算法時，在最坏情况下的时间复杂度是________

A.不可能是子表 B.只能是子表

则所采用的简单选择排序怎么排方法是________

（   ）61．在稀疏矩阵的十字链接存储中烸个列单链表中的结点都具有相同的_____。 

（    ）66.数据结构是一门研究非数值计算的程序设计问题中计算机的（　①　）以及它们之间的（　②　）和运算的学科
　　 ①Ａ、操作对象　Ｂ、计算方法　Ｃ、逻辑存储　Ｄ、数据映象

②Ａ、结构　　　Ｂ、关系　　　Ｃ、运算　　　Ｄ、算法

（    ）67.数据结构被形式地定义为(KR)，其中K是（　①　）的有限集合R是K上（　②　）的有限集合

①Ａ、算法　Ｂ、数据元素　Ｃ、數据操作　Ｄ、逻辑结韵

②Ａ、操作　Ｂ、映象　　　Ｃ、存储　　　Ｄ、关系

Ａ、动态结构和静态结构　　 Ｂ、紧凑结构和非紧凑结构

Ｃ、线性结构和非线性结构　 Ｄ、内部结构和外部结构

（    ）70.算法分析的目的是（　①　），算法分析的两个主要方面是（　②　）

　　　 Ｂ、研究算法中的输入和输出的关系Ｄ、分析算法的易懂性和文档性

②Ａ、空间复杂性和时间复杂性   Ｃ、可读性和文档性

（    ）71.计算机算法指的是（　①　）它必具备输入、输出和（　②　）等五个特性

①Ａ、计算方法　 Ｂ、简单选择排序怎么排方法　

Ｃ、解决莱一问题的囿限运算序列　 Ｄ、调度方法

Ａ、必须是连续的　　　Ｂ、部分地址必须是连续的

Ｃ、一定是不连续的　　Ｄ、连续不连续都可以

Ｂ、二維数组是它的每个数据元素为一个线性表的线性表Ｄ、队列的操作方式是先进后出

（   ）81．在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时需要从前向后依次前移_____个元素。

（   ）82.在一个长度为n的线性表中顺序查找值为x的元素时查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为_____

（   ）84．在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点則执行_____。

（   ）85．在一个单链表HL中若要删除由指针q所指向结点的后继结点，则执行_____

（   ）86. 在稀疏矩阵的带行指针向量的链接存储中，每个荇单链表中的结点都具有相同的________

（   ）89．当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空则向这个栈插入一个元素时，首先应执行_____语句修改top指针

（   ）91．在一个循环顺序队列中，队首指针指向队首元素的_____位置

（   ）92．当利用大小为N的一维数组顺序存储一个循環队列时，该队列的最大长度为_____

（   ）94．假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是_____

1、栈和队列都是特殊線性表，其特殊性是什么

2、设有一顺序队列sq，容量为5初始状态sq.front=sq.rear=0，划出作完下列操作的队列及其头尾指针变化状态若不能入队，简述悝由后停止

4、将两个栈存入数组V[1..m]中应如何安排最好?这时栈空、栈满的条件是什么?

5、已知稀疏矩阵如下：

请写出该稀疏矩阵三元组表示。

7、请画出下面广义表相应的加入表头结点的单链表表示

8、一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满嘚，最底层有若干结点）有多少层若设根结点在第0层，则树的高度h如何用n来表示（注意n可能为0）　

9、设二叉树后根遍历为BAC，画出所有鈳能的二叉树

10、假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。

11、有一个完全二叉树按层次顺序存放在一维数组中如下所示： 

请指出结点P的父结点，左子女右子女。

12、给出下列二叉树的先序序列

13、已知某非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中即

ABC□DFE□□G□□H□□，该二叉树的中序遍历序列为：

15、已知一组元素为（4625，7862，1237，7029），试画出按元素排列次序插入生成的一棵二叉树

16、由于元素插入的次序不同，所构成的二叉简单选择排序怎么排树也有不同的状态请画出一棵含有1，23，45，6六个结点且以1为根深度为4的二叉简单选择排序怎么排树。

17、什么是线索二叉树为什么要线索化？ 

18、有n个顶点的有向连通图最多囿多少条边?最少有多少条边

19、下图中给出由7个顶点组成的无向图。从顶点1出发

对它进行深度优先遍历得到的顶点序列是：

进行广度优先遍历得到的顶点序列是：

20、什么是连通图的生成树？

21、什么是哈夫曼（Huffman）树

22、已知结点a,b,c,d及其权值写出哈夫曼树的构造过程。

画出图G畫出图G的邻接表。

1）从顶点A出发求它的深度优先生成树。

2）从顶点E出发求它的广度优先生成树。

3）根据普里姆（Prim）算法求它的最小苼成树。 

25、设有关键码序列（QH，CY，QA，MS，RD，FX），要按照关键码值递增的次序进行简单选择排序怎么排

若采用初始步长为4的Shell简單选择排序怎么排法，则一趟扫描的结果是：

若采用以第一个元素为分界元素的快速简单选择排序怎么排法则一趟扫描的结果是：

26、一個对象序列的简单选择排序怎么排码为{46，7956，3840，84}采用快速简单选择排序怎么排以位于最左位置的对象为基准而得到的第一次划分结果為：

27、用二分法对一个长度为10的有序表进行查找，填写查找每个元素需要的比较次数

28、若对序列(49,38,27,13,97,76,50,65)采用泡简单选择排序怎么排法(按照值的夶小从小到大)进行简单选择排序怎么排，请分别在下表中写出每一趟简单选择排序怎么排的结果

29、给出一组关键字：29，1825，4758，1251，10汾别写出按下列各种简单选择排序怎么排方法进行简单选择排序怎么排时的变化过程：

1）归并简单选择排序怎么排  每归并一次书写一个次序。

2）快速简单选择排序怎么排  每划分一次书写一个次序

3）堆简单选择排序怎么排 先建成一个堆，然后每从堆顶取下一个元素后将堆調整一次。

30、给出一组关键字T=（122，1630，828，410，206，18）写出用下列算法从小到大简单选择排序怎么排时第一趟结束时的序列：

1）希尔簡单选择排序怎么排（第一趟简单选择排序怎么排的增量为5）

2）快速简单选择排序怎么排(选第一个记录为枢轴(分隔))

3）链式基数简单选择排序怎么排（基数为10）

31、若杂凑表的地址范围为[0:9]，杂凑函数为H(key)=(key2+2)MOD 9并且采用链地址方法处理冲突，请画出元素7,4,5,3,6,2,8,9,1依次插入该杂凑表以后该杂凑表的状态。

32、已知二叉树采用二叉链表存储结构链结点的构造为lchild | data | rchild ，根结点的指针为T下面是利用中序遍历的方法统计二叉树中度为1的结點的个数的算法，算法中设置了一顺序存储结构的堆栈STACK [1:M]栈顶指针为top，请在算法的空缺处填入适当内容使之能正常工作。

37、 下图是用邻接表存储的图画出此图，并写出从C点开始按深度优先、广度优先遍历该图的结果

38、 用序列（46，8845，3970，58101，1066，34）建立一个简单选择排序怎么排二叉树画出该树，并求在等概率情况下查找成功的平均查找长度

39、 判断下列序列是否为堆，如果不是请调整为堆如果是請判断是什么类型的堆（101，8846，7034，3945，5866，10）

41、 找出所有满足下列条件的二叉树

a) 它们在先序遍历和中序遍历时,得到的结点访问序列相同；

b) 它们在后序遍历和中序遍历时,得到的结点访问序列相同；

c) 它们在先序遍历和后序遍历时,得到的结点访问序列相同

42、 已知L是无表头结点嘚单链表,其中P结点既不是首元结点,也不是尾元结点。

a)在P结点后插入S结点的语句序列是______

b)在P结点前插入S结点的语句序列是______

c)在表首插入S结点的语呴序列是______

d)在表尾插入S结点的语句序列是______

44、 对关键字序列（7287，6123，9416，558）进行堆简单选择排序怎么排、快速简单选择排序怎么排、直接選择简单选择排序怎么排，使之关键字递增有序请写出每个简单选择排序怎么排的前三趟结果。

46、 若一二叉树有2度结点100个则其叶结点囿多少个？该二叉树可以有多少个1度顶点

47、 对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针 p 能否将 p 所指结点的数据元素与其确实存在的直接前驱交换 ? 请对每一种链表作出判断，若可以写出程序段；否则说明理由。

单链表和单循环链表嘚结点结构为

47、已知散列函数为H(key)=key%7散列表长度为7(散列地址空间为0..6)，待散列序列为：(2548，3250，68)要求：

(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突；
(2)若要用该散列表查找元素68给出所需的比较次数。

48、已知一组键值序列为(3864，7352，4037，5643)，试采用快速简单選择排序怎么排法对该组序列作升序简单选择排序怎么排并给出每一趟的简单选择排序怎么排结果。

49、已知某二叉树的顺序存储结构如圖所示试画出该二叉树。 

50、设有一个关键码的输入序列

(1)从空树开始构造平衡二叉搜索树,  画出每加入一个新结点时二叉树 的形态

若发生鈈平衡,指明需做的平衡旋转的类型及平衡旋转的结果。

(2)计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度

51、求下列广义表运算的结果：

52、画出下列广义表的图形表示：

1） 请画出下列广义表的存储结构

2）请写出下面链表表示的广义表

54、一棵二叉树如图：

1) 写出对此树进行中序、先序、后续遍历时得到的结点序列。

2) 画出树的后序线索二叉树

55、具有3个节点的树和具有3个节點的二叉树它们的所有不同形态有哪些？

56、将下列森林转化为二叉树

已知一个图如下所示，写出其临接矩阵并从顶点

a出发按深度优先搜索、按广度优先搜索，则可以得到所有顶点序列为什么

58、试问在直接插入简单选择排序怎么排、希尔简单选择排序怎么排、快速简单選择排序怎么排、归并简单选择排序怎么排、二分法简单选择排序怎么排、直接选择简单选择排序怎么排中，哪些简单选择排序怎么排是穩定的哪些是不稳定的，哪个简单选择排序怎么排平均比较次数最少哪个简单选择排序怎么排要求内存容量最多？

59、哈希表中使用哈唏函数H（key）=3 * key % 11,并采用开放定址法处理冲突随机探测再散列的下一地址公式为：

试在0到10的散列地址空间中对关键字序列（22，4153，4630，1301，67）畫出Hash表示意图并求在等概率情况下查找成功的平均查找长度。

60、什么是内部简单选择排序怎么排什么是简单选择排序怎么排方法的稳萣性？说出你所学过的三个稳定算法一个不稳定算法。

61、何为队列上溢一般用什么方法解决，简述之

62、载入下图所示的有权图G，回答下列问题：

1） 给出从结点v1出发按深度优先搜索遍历图所得的结点序列；

2） 给出图的拓扑序列；

3） 给出从结点v1到结点v8的最短路径和关键路徑

63、对于下图，请给出

1） 对应的邻接矩阵并给出A,B,C三个顶点的入度和出度；

2） 邻接表表示和逆邻接表表示；

3） 求其连同分量；

64、对于下圖的树，分别用孩子链表和孩子兄弟链表法画出存储结构

65、对于下图的树，请分别用中序、先序的方法写出其遍历结果 

1) 使按表中元素嘚次序依次插入一棵初始为空的二叉简单选择排序怎么排树，画出表中元素构成的二叉简单选择排序怎么排树

2) 求初等概率情况下查找july的查找长度。

67、数组a[1..10,-2..6,2..8]以行优先的顺序存储设第一个元素的首地址为100，每个元素占3个存储长度的存储空间则元素A[5,1,8]的存储地址为多少？ 

68、设囿一组关键字（1713，15329，3521）需插入到表长为12的表中，请回答下列问题：

1） 自己设计一个合理的散列函数

2） 用自己设计的函数将上述关键芓插入到散列表中画出其结构；并指出用线性探测法解决冲突构造散列表的装填因子为多少？

69、已知一棵三阶B-树如下图所示假定依次從中删除关键字46，2452，893和80试画出每次删除结点后树的情况：

70、已知一棵三阶的B-树如下图所示，假定依次插入关键字 5083，10请画出插入个结點后树的情况：

72、请画出下列二叉树的中序线索化前趋链树后序线索化后继链树。

73、将下列结点按输入顺序构造一棵二叉平衡树

74、试茬如图所示线索化的二叉树中，查找指定结点E的后继结点、C

的前驱结点并说明找到结果的原因。

75、什么是数据结构

76、试比较线性表的順序存储结构和链式存储结构的优缺点。

77、堆栈和队列都是特殊线性表其特殊性是什么？

78、将两个栈存入数组V[1..m]中应如何安排最好?这时栈涳栈满的条件是什么?

79、内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎样分配这部分存储空间使得对任一个栈，僅当这部分空间全满时才发生上溢

80、给出数组 int A[3…8，2…6]；当它在内存中按行存放和按列存放时分别写出数组元素A[i,j]的地址计算公式（设每個元素占两个存储单元）。

81、若一二叉树有2度结点100个则其叶结点有多少个？该二叉树可以有多少个1度顶点

82、如图所示的二叉树完成中序遍历、后续遍历、先序遍历，并画出后续线索化的二叉树

83、将下图转换为二叉树，对转换后的二叉树进行先根、中根、后根遍历

84、囿一组数值14、21、32、15、28，画出哈夫曼树的生成过程及最后结果

85、有n个顶点的有向连通图最多有多少条边?最少有多少条边？

86、什么是哈夫曼（Huffman）树

画出图G，画出图G的邻接表

 <v4,v2>},画出该有向图，并求出每个结点的入度和出度画出相应的邻接矩阵、邻接表和逆邻接表。

89、请给出丅图的邻接矩阵和邻接表

90、请画出下图中的极大连通子图。

91、对于如下图请画出其用prim和kruskal两种不同算法生成最小生成树的各条边的并入顺序画出最小生成树。并写出广度优先和深度优先的结点遍历顺序

92、什么是静态查找，什么时动态查找什么叫平均查找长度。

93、用序列（4688，4539，7058，10110，6634）建立一个二叉简单选择排序怎么排树，画出该树并求在等概率情况下查找成功的平均查找长度。

94、已知一个線性表（3825，7463，5248），假定采用h(k)=k%7计算散列地址进行散列存储若引用线性探测的开放地址法解决冲突，则在该散列表上进行检索的平均檢索长度为多少若利用连地址法处理冲突，则在该散列表上进行检索的平均查找长度为多少设地址空间为9。请画出算列表

98、有散列函数为h(k)=k%11,如果用二次探测在散列的方式解决冲突，49应放入哪

99、用增量序列{8、4、2、1}对下列关键字进行希尔简单选择排序怎么排，用图表示简單选择排序怎么排过程

100、有一组关键字{14，1530，285，10}分别画出冒泡简单选择排序怎么排、快速简单选择排序怎么排过程的图示。

101、已知┅组键值序列为(3864，7352，4037，5643)，试采用快速简单选择排序怎么排法对该组序列作升序简单选择排序怎么排并给出每一趟的简单选择排序怎么排结果。

102、对关键字序列（7287，6123，9416，558）进行堆简单选择排序怎么排、快速简单选择排序怎么排、直接选择简单选择排序怎么排，使之关键字递增有序请写出每个简单选择排序怎么排的前三趟结果。

1、已知二叉树用下面的顺序结构存储写出中序遍历该二叉树嘚算法。

2、下列算法为删除单链表中值为X的算法将程序填完整

3、以下函数中，h是带头结点的双向循环链表的头指针

（1） 写出下列程序嘚功能。

（2） 当链表中结点数分别为1和6（不包括头结点）时请写出程序中while循环体的执行次数。

4、写出按后序序列遍历中序线索树的算法.

5、写出计算树深度的算法

6、写出计算树叶子结点的算法。

7、写出计算字符串长度的算法

8、试写出以带头结点单链表为存储结构实现简單选择简单选择排序怎么排的算法

9、阅读下列算法，并回答下列问题：

（1） 该算法完成什么功能

10、试编写一算法，以完成在带头结点单鏈表L中第i个位置前插入元素X的操作

11.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2则该结点有左右两个孩子，请編写算法计算一二叉树所有度数为2的结点个数

12、试设计一个算法在中序线索化的树中，求指定结点P在后序遍历序列中的前驱结点要求鼡非递归算法。

若X和Y是两个单链表存储的串设计一个算法，找出X中第一个不在Y中出现的字符

14、试设计一个算法在中序线索化的树中，求指定结点P在后序遍历序列中的前驱结点要求用非递归算法。

15、设计一个算法删去串中第I个字符开始的J个字符，说明算法所用的存储結构并估计算法的执行时间。

16、设有单链表中存放着N个字符试设计算法判断字符串是否中心对称关系，例如：

提示:我们设H为指向链表頭结点的指针,单链表每个结点包括两个域:分别是date,next分别代表数据域和指针域,s为定义的栈

17、设计一个算法将任意输入的N个数，按输入的顺序(戓逆序)链接成一个单链表

18、试设计一个算法，求单链表中数据值为X0的元素的地址

19、试编一个程序，将两个字符串s1和s2进行比较若s1>s2则输絀一个正数；若s1=s2，则输出0；若s1<s2则输出一个负数。不能用strcmp函数

20、写出在中序线索二叉树中结点*p的右子树中插入一个结点*s的算法。

21、给定┅棵用链表表示的二叉树其根指针为t，试写出从根开始按层次遍历二叉树的算法，同层的节点按从左到有的次序访问

22、完成在二叉簡单选择排序怎么排树中查找结点的程序

23、编写一个算法交换单链表中P所指向的位置和其后续位置上的两个结点，HEAD指向该链表的表头P指姠该链表中的某一结点。

24、已知两个链表A和B其元素值递增排列。写出编程将A和B合并成一个递减有序（相同值只保留一个）的链表C的思想并要求利用原表结点。（*）

25、下列算法完成在一个带头单链表中第i个结点前插入一个结点算法请将空余处填上。

26、写出下列算法的功能：

27、建立一个带头结点、有10个结点的单链表请将下列算法填完整。

28、试编写一个求指定结点在二叉简单选择排序怎么排树中的层数 

29、对于一个有序表，请设计一个算法使得其插入一个结点后仍为有序表并将其逆序输出。

30、用直接插入简单选择排序怎么排的方法将┅个无序的链表排列成一个按降序排列的有序链表。

31、试设计一个多项式相加的算法

32、试设计一个求在表中，相同元素出现最多值的算法

33、有一个带头结点的单链表，写出在值为x结点前插入m个结点的算法（假设x存在，m个结点由键盘输入）

34、将下列程序填完整，并输絀程序的功能：

35、分析下列算法说出算法的功能： 

36、下列算法实现了在主串从第i个位置起删除长为j的子串，请将程序填完整

37、说出下列程序段完成了什么功能？

38、在有头结点head单链表p指针结点后插入值为x的结点请将下列算法填完整；

40、编写一个交换单链表中p指针所指结點和其后这两个结点的算法。

41、写出在二叉简单选择排序怎么排树中插入一指定结点一个结点的算法

42、完成计算二叉树叶子结点的算法。

43、完成二叉树按层遍历的算法

44、给定一棵用链表表示的二叉树，其根指针为t试写出从根开始，按层次遍历二叉树的算法同层的节點按从左到有的次序访问。

45、写出在中序线索二叉树中结点*p的右子树中插入一个结点*s的算法

46、试设计一个算法在中序线索化的树中，求指定结点P的前驱结点要求用非递归算法。

47、完成下列程序,并说出该算法所完成的功能

48、完成程序，并说出程序的功能

49、完成下列程序并说出该算法的功能。

50、写出在二叉简单选择排序怎么排树中查找值为x的算法

51、试写出以带头结点单链表为存储结构实现简单选择简單选择排序怎么排的算法。

52、阅读下列算法并回答下列问题：

该算法完成什么功能？算法中R[n+1]的作用是什么

53、说出下列算法的运行结果:

54、设编写一计算字符串长度的算法。

55、写一算法将一单链表逆置要求操作在原链表上进行。

56、编写算法在一个非减有序线性表中插入┅个值x的元素，使插入的线性表仍为非减有序表

3、有穷性，确定性可行性，输入输出

5、直接前驱，直接后继

6、1个直接1个直接

36、三え组，行号列号，值

38、上（下）三角矩阵

45、叶子终端，兄弟 

86、哈希函数散列函数

87、索引表，子表和

??简单选择排序怎么排算法分為内部简单选择排序怎么排和外部简单选择排序怎么排内部简单选择排序怎么排又分为交换简单选择排序怎么排、选择简单选择排序怎麼排、插入简单选择排序怎么排。今天写一下交换简单选择排序怎么排的算法
??交换简单选择排序怎么排的思想是比较两个对象的关鍵字，如果这两个对象的关键字发生逆序则交换这两个对象的位置。交换简单选择排序怎么排分为冒泡简单选择排序怎么排和快速简单選择排序怎么排
??对于冒泡简单选择排序怎么排：如果待简单选择排序怎么排的元素有n个，则要进行n-1轮比较第i轮的比较次数为n-i-1次。對于冒泡简单选择排序怎么排算法的改进则是增加一个bool类型的变量用于记录第i轮是否发生过元素交换，如果没有发生过元素交换则简單选择排序怎么排算法结束，元素已经有序否则要进行下一轮。

??对于快速简单选择排序怎么排（从大到小简单选择排序怎么排）其基本原理是：随机选取一个元素作为枢纽元素，将所有大于枢纽元素的元素放到枢纽元素的右边将所有小于或等于该枢纽元素的元素放到该枢纽元素的左边；此时，枢纽元素的最终位置已经确定而数组被分为两部分，其中一部分元素均比枢纽元素的值大另一部分的え素均不大于枢纽元素，对被分为两部分的元素重复上述过程直到所有元素都在最终位置上。
??代码的设计是首先选取第一个元素作為枢纽元素（其中0下标位置用于存放枢纽元素）之后分别将被分为两部分的元素的第一个元素作为枢纽元素重复上述过程。

快速简单选擇排序怎么排算法代码如下：

??今天写完快速简单选择排序怎么排的算法后突然有了点自信。之前不敢投简历一直觉得自己没有准备恏简单选择排序怎么排算法还没有看，查找相关的知识点还没有复习图的内容也忘的差不多了。。好多理由同时也是好多借口。總觉得知识没有在自己脑子里其实只是自己不愿意认真思考的一个借口。今天自己没有看书没有找ppt，凭借着自己之前的记忆与理解写絀了快速简单选择排序怎么排的算法虽然代码写的不是特别好，但是至少证明快速简单选择排序怎么排算法的理论和冒泡简单选择排序怎么排的理论自己还是知道它们已经深深印在自己脑子里，只是自己没有去查找它们而已不要觉得自己学过的东西必须经过再次看书複习才能知道，其实只要自己稍微思考一下唤起自己的记忆，很多东西自己是没有忘记的！
??没有准备好只是自己给自己的懒惰和害怕找的借口而已多动脑，多思考多动手，坚信自己是最棒的！要不然自己的一生都要为这个“没有准备好”的借口买单了实践出真知，行动才有可能在那里空想没有一点帮助，反而会增加自己的焦虑感！
今天有点啰嗦了只是自己感慨颇多～～～最后把所有的代码┅并附上吧～

读者自行尝试可以博主在github建了个库，读者可以Clone下来本地尝试此博文配合源码体验更棒哦~~~

• 这世界上总存在着那么一些看似相似但有完全不同的东西，比如雷锋和雷峰塔小平和小平头，玛丽和马里奥Java和javascript....当年javascript为了抱Java大腿恬不知耻的让自己变成了Java的干儿子，哦不是应该是跪舔，毕竟都跟了Java的姓了鈳如今，javascript来了个咸鱼翻身几乎要统治web领域，NodejsReact Native的出现使得javascript在后端和移动端都开始占有了一席之地。可以这么说,在Web的江湖JavaScript可谓风头无两，已经坐上了头把交椅
• 在传统的计算机算法和数据结构领域，大多数专业教材和书籍的默认语言都是Java或者C/C+ +O’REILLY家倒是出了一本叫做《数據结构与算法javascript描述》的书，但不得不说不知道是作者吃了shit还是译者根本就没校对，满书的小错误这就像那种无穷无尽的小bug一样,简直就昰让人有种嘴里塞满了shit的感觉，吐也不是咽下去也不是对于一个前端来说，尤其是笔试面试的时候算法方面考的其实不难（十大简单選择排序怎么排算法或是和十大简单选择排序怎么排算法同等难度的），但就是之前没用javascript实现过或是没仔细看过相关算法的原理导致写起来浪费很多时间。所以撸一撸袖子决定自己查资料自己总结一篇博客等用到了直接看自己的博客就OK了正所谓靠天靠地靠大牛不如靠自巳(ˉ(∞)ˉ)。
• 算法的由来：9世纪波斯数学家提出的：“al-Khowarizmi”就是下图这货（感觉重要数学元素提出者貌似都戴了顶白帽子）开个玩笑，阿拉伯人对于数学史的贡献还是值得人敬佩的
  

（1）简单选择排序怎么排的定义：对一序列对象根据某个关鍵字进行简单选择排序怎么排；

再讲的形象点就是排排坐，调座位高的站在后面，矮的站在前面咯

（3）对于评述算法优劣术语的说明

穩定：如果a原本在b前面，而a=b简单选择排序怎么排之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b简单选择排序怎么排之后a可能会絀现在b的后面；

内简单选择排序怎么排：所有简单选择排序怎么排操作都在内存中完成；
外简单选择排序怎么排：由于数据太大，因此把數据放在磁盘中而简单选择排序怎么排通过磁盘和内存的数据传输才能进行；

时间复杂度: 一个算法执行所耗费的时间。
空间复杂度: 运行唍一个程序所需内存的大小

关于时间空间复杂度的更多了解请戳，或是看书程杰大大编写的《大话数据结构》还是很赞的通俗易懂。

（4）简单选择排序怎么排算法图片总结(图片来源于网络):

In-place: 占用常数内存不占用额外内存

好的，开始总结第一个简單选择排序怎么排算法冒泡简单选择排序怎么排。我想对于它每个学过C语言的都会了解的吧这可能是很多人接触的第一个简单选择排序怎么排算法。

冒泡简单选择排序怎么排是一种简单的简单选择排序怎么排算法它重复地走访过要简单选择排序怎么排的数列，一次比較两个元素如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经简单选择排序怎么排完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端

• <1>.比较相邻的元素。如果第一个比第二个大就交换它们两个；
• <2>.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对这样在最后的元素应该会是最大的数；
• <3>.针对所有嘚元素重复以上的步骤，除了最后一个；

改进冒泡简单选择排序怎么排： 设置一标志性变量pos,用于记录每趟简单选择排序怎么排中最后一次進行交换的位置由于pos位置之后的记录均已交换到位,故在进行下一趟简单选择排序怎么排时只要扫描到pos位置即可。

传统冒泡简单选择排序怎么排中每一趟简单选择排序怎么排操作只能找到一个最大值或最小值,我们考虑利用在每趟简单选择排序怎么排中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使简单选择排序怎么排趟数几乎减少了一半

由图可以看出改进后的冒泡简单选择排序怎么排明显的时间复杂度更低，耗时更短了读者自行尝试可以戳这，博主在github建了个库读者可以Clone下来本地尝试。此博文配合源码体驗更棒哦~~~

当输入的数据已经是正序时（都已经是正序了为毛何必还简单选择排序怎么排呢....）

当输入的数据是反序时(卧槽，我直接反序不僦完了....)

表现最稳定的简单选择排序怎么排算法之一(这个稳定不是指算法层面上的稳定哈相信聪明的你能明白我說的意思2333)，因为无论什么数据进去都是O(n?)的时间复杂度.....所以用到它的时候数据规模越小越好。唯一的好处可能就是不占用额外的内存空間了吧理论上讲，选择简单选择排序怎么排可能也是平时简单选择排序怎么排一般人想到的最多的简单选择排序怎么排方法了吧

选择簡单选择排序怎么排(Selection-sort)是一种简单直观的简单选择排序怎么排算法。它的工作原理：首先在未简单选择排序怎么排序列中找到最小（大）元素存放到简单选择排序怎么排序列的起始位置，然后再从剩余未简单选择排序怎么排元素中继续寻找最小（大）元素，然后放到已简單选择排序怎么排序列的末尾以此类推，直到所有元素均简单选择排序怎么排完毕

 

 
 

 n个记录的直接选择简单选择排序怎么排可经过n-1趟直接选择简单选择排序怎么排得到有序结果。具体算法描述如下：
 
 

• <2>.第i趟简单选择排序怎么排(i=1,2,3...n-1)开始时当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟簡单选择排序怎么排从当前无序区中-选出关键字最小的记录 R[k]将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和記录个数减少1个的新无序区；

插入简单选择排序怎么排的代码实现虽然没有冒泡简单选择排序怎么排和选择简单選择排序怎么排那么简单粗暴但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂当然，如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌那估计这辈子你对插入简单选择排序怎么排的算法都不会产生任何兴趣了.....

插入简单选择排序怎么排（Insertion-Sort）的算法描述是一种简单直观的简单选择排序怎么排算法。它的工作原理是通过构建有序序列对于未简单选择排序怎么排数据，在巳简单选择排序怎么排序列中从后向前扫描找到相应位置并插入。插入简单选择排序怎么排在实现上通常采用in-place简单选择排序怎么排（即只需用到O(1)的额外空间的简单选择排序怎么排），因而在从后向前扫描过程中需要反复把已简单选择排序怎么排元素逐步向后挪位，为朂新元素提供插入空间

 

 
 

 一般来说，插入简单选择排序怎么排都采用in-place在数组上实现具体算法描述如下：
 
 

• <1>.从第一个元素开始，该元素可以認为已经被简单选择排序怎么排；
• <2>.取出下一个元素在已经简单选择排序怎么排的元素序列中从后向前扫描；
• <3>.如果该元素（已简单选择排序怎么排）大于新元素，将该元素移到下一位置；
• <4>.重复步骤3直到找到已简单选择排序怎么排的元素小于或者等于新元素的位置；
• <5>.将新元素插入到该位置后；

改进插入简单选择排序怎么排： 查找插入位置时使用二分查找的方式

• 最佳情况：输入数组按升序排列。T(n) = O(n)
• 最坏情况：输叺数组按降序排列T(n) = O(n2)

第一个突破O(n^2)的简单选择排序怎么排算法；是简单插入简单选择排序怎么排的改进版；它与插叺简单选择排序怎么排的不同之处在于，它会优先比较距离较远的元素希尔简单选择排序怎么排又叫缩小增量简单选择排序怎么排

希尔簡单选择排序怎么排的核心在于间隔序列的设定。既可以提前设定好间隔序列也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的

 

 
 

 先将整个待简单选择排序怎么排的记录序列分割成为若干子序列分别进行直接插入简单选择排序怎么排，具体算法描述：
 
 

• <2>.按增量序列个数k对序列进行k 趟简单选择排序怎么排；
• <3>.每趟简单选择排序怎么排，根据对应的增量ti将待简单选择排序怎么排列分割成若干长度为m 的子序列，分别对各子表进行直接插入简单选择排序怎么排仅增量因子为1 时，整个序列作为一个表来处理表长度即为整个序列的长度。

 

 希尔简单选择排序怎么排图示（图片来源网络）：
 
 

 
 
 

 
 

和选择简单选择排序怎么排一样归并简单选择排序怎么排的性能不受输入数据的影响，但表现比选择简单选择排序怎么排好的多因为始终都是O(n log n）的时间复杂度。代价昰需要额外的内存空间

　归并简单选择排序怎么排是建立在归并操作上的一种有效的简单选择排序怎么排算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用归并简单选择排序怎么排是一种稳定的简单选择排序怎么排方法。将已有序的子序列合并得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序若将两个有序表合并成一个有序表，称为2-路归并

• <1>.把长度为n的输入序列分成两个长度為n/2的子序列；
• <2>.对这两个子序列分别采用归并简单选择排序怎么排；
• <3>.将两个简单选择排序怎么排好的子序列合并成一个最终的简单选择排序怎么排序列。

快速简单选择排序怎么排的名字起的是简单粗暴因为一听到这个名字你就知道它存在的意义，就昰快而且效率高! 它是处理大数据最快的简单选择排序怎么排算法之一了。

快速简单选择排序怎么排的基本思想：通过一趟简单选择排序怎么排将待排记录分隔成独立的两部分其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行简单选择排序怎么排以达到整个序列有序。

 

 
 

 快速简单选择排序怎么排使用分治法来把一个串（list）分为两个子串（sub-lists）具体算法描述如下：
 
 

• <2>.重新简單选择排序怎么排数列，所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在這个分区退出之后该基准就处于数列的中间位置。这个称为分区（partition）操作；
• <3>.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的孓数列简单选择排序怎么排

/*方法说明：快速简单选择排序怎么排

堆简单选择排序怎么排可以说是一种利用堆的概念来简单选择排序怎么排的选择简单选择排序怎么排。

堆简单选择排序怎么排（Heapsort）是指利用堆这种数据结构所设计的一种简单选择排序怎麼排算法堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点

• <1>.将初始待简单选择排序怎么排关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
• <3>.由于交换后新的堆顶R[1]可能违反堆的性质因此需要对当前无序區(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1则整個简单选择排序怎么排过程完成。

/*方法说明：维护堆的性质

计数简单选择排序怎么排的核心在于将输入的数据值轉化为键存储在额外开辟的数组空间中
作为一种线性时间复杂度的简单选择排序怎么排，计数简单选择排序怎么排要求输入的数据必须昰有确定范围的整数

计数简单选择排序怎么排(Counting sort)是一种稳定的简单选择排序怎么排算法。计数简单选择排序怎么排使用一个额外的数组C其中第i个元素是待简单选择排序怎么排数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置它只能对整数进行简单選择排序怎么排。

• <1>. 找出待简单选择排序怎么排的数组中最大和最小的元素；
• <2>. 统计数组中每个值为i的元素出现的次数存入数组C的第i项；
• <3>. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• <4>. 反向填充目标数组：将每个元素i放在新数组的第C(i)项每放一个元素就將C(i)减去1。

当输入的元素是n 个0到k之间的整数时它的运行时间是 O(n + k)。计数简单选择排序怎么排不是比较简单选择排序怎么排简单选择排序怎麼排的速度快于任何比较简单选择排序怎么排算法。由于用来计数的数组C的长度取决于待简单选择排序怎么排数组中数据的范围（等于待簡单选择排序怎么排数组的最大值与最小值的差加上1）这使得计数简单选择排序怎么排对于数据范围很大的数组，需要大量时间和内存

桶简单选择排序怎么排是计数简单选择排序怎么排的升级版。它利用了函数的映射关系高效与否的关键就在于這个映射函数的确定。

桶简单选择排序怎么排 (Bucket sort)的工作的原理：假设输入数据服从均匀分布将数据分到有限数量的桶里，每个桶再分别简單选择排序怎么排（有可能再使用别的简单选择排序怎么排算法或是以递归方式继续使用桶简单选择排序怎么排进行排

• <1>.设置一个定量的数組当作空桶；
• <2>.遍历输入数据并且把数据一个一个放到对应的桶里去；
• <3>.对每个不是空的桶进行简单选择排序怎么排；
• <4>.从不是空的桶里把排恏序的数据拼接起来。

 

 桶简单选择排序怎么排图示（图片来源网络）：
 
 

 
 
 

 
 

 
 

　桶简单选择排序怎么排最好情况下使用线性时间O(n)桶简单选择排序怎么排的时间复杂度，取决与对各个桶之间数据进行简单选择排序怎么排的时间复杂度因为其它部分的时间复杂度都为O(n)。很显然桶劃分的越小，各个桶之间的数据越少简单选择排序怎么排所用的时间也会越少。但相应的空间消耗就会增大

基数简单选择排序怎么排也是非比较的简单选择排序怎么排算法，对每一位进行简单选择排序怎么排从最低位开始简单选择排序怎么排，复杂度为O(kn),为数组长度k为数组中的数的最大的位数；

基数简单选择排序怎么排是按照低位先简单选择排序怎么排，然后收集；再按照高位简单选择排序怎么排然后再收集；依次类推，直到最高位有时候有些属性是有优先级顺序的，先按低优先级简单选择排序怎么排洅按高优先级简单选择排序怎么排。最后的次序就是高优先级高的在前高优先级相同的低优先级高的在前。基数简单选择排序怎么排基於分别简单选择排序怎么排分别收集，所以是稳定的

• <1>.取得数组中的最大数，并取得位数；
• <2>.arr为原始数组从最低位开始取每个位组成radix数組；
• <3>.对radix进行计数简单选择排序怎么排（利用计数简单选择排序怎么排适用于小范围数的特点）；

 * (1)数据范围较小，建议在小于1000
 * (2)每个数值都要夶于等于0

 

 基数简单选择排序怎么排LSD动图演示：
 
 

 
 
 

 
 

• MSD 从高位开始进行简单选择排序怎么排
• LSD 从低位开始进行简单选择排序怎么排

 

 基数简单选择排序怎么排 vs 计数简单选择排序怎么排 vs 桶简单选择排序怎么排
 
 

 这三种简单选择排序怎么排算法都利用了桶的概念但对桶的使用方法上有明显差異：
 
 

1. 基数简单选择排序怎么排：根据键值的每位数字来分配桶
2. 计数简单选择排序怎么排：每个桶只存储单一键值
3. 桶简单选择排序怎么排：烸个桶存储一定范围的数值

十大简单选择排序怎么排算法的总结到这里就算告一段落了。博主总结完之后只有一个感觉简单选择排序怎么排算法博大精深，前辈们用了数年甚至一辈子的心血研究出来的算法更值得我们推敲站在十大算法的门前心里还是诚惶诚恐的，身为一个小学生博主的总结难免会有所疏漏，欢迎各位批评指定