江苏师范大学数据结构总复习总结

复习第一章绪论本章要点：（1）有关数据结构的基本概念，包括：数据、数据对象、数据元素或者数据成员、数据结构、数据类型等；数据抽象、抽象数据类型、数据结构的抽象层次等。（2）算法设计与分析：算法的定义和算法的特性算法的设计方法：包括问题解决的基本思路、算法设计的基本步骤、算法的实现算法的性能分析：包括算法的性能标准，算法的后期测试；算法的事情估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法1、顺序存储结构中数据元素间的逻辑结构是由（）来表示的，链接存储结构中数据元素间的逻辑关系是由（）表示。A指针B逻辑顺序C存储位置D问题上下文2、算法的时间复杂度与（）有关。A问题规模B计算机硬件的运行速度C源程序的长度D编译后执行程序的质量3、某算法的时间复杂度为O(n2)，表明该算法（）A问题规模是n2B问题规模与n2成正比C执行时间等于n2D执行时间与n2成正比CAAD4、算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应当具有输入、输出、（）、有穷和可行性等特性。5、算法效率的度量分为（）和（）。前者主要通过在算法的某些部位插装时间函数来测定算法完成某一个规定功能所需要的时间。而后者不实际运行算法，它是分析算法中语句的执行次数来度量算法的时间复杂度。6、程序所需要的存储空间包含两个部分（）和（）。前者空间的大小与输入输出数据的个数多少，数值大小无关。后者空间主要包括其大小与问题规模有关的成分变量所占空间等等。确定性事后测量事前估计固定部分可变部分7、有实现同一功能的两个算法A1和A2，其中A1的渐进时间复杂度是，A2的渐进时间复杂度为。仅就时间复杂度而言，具体分析这两个算法哪个好。比较算法好坏，需要比较两个函数2n和n2当n=1时，21>12，算法A2好于A1当n=2时，22=22，算法A2与A1相当当n=3时，23<32，算法A1好于A2当n=4时，24>42，算法A2好于A1当n>4时，24>n2，算法A2好于A1当n→

时，算法A2在时间上好于A1第二章线性表本章要点：（1）线性表的定义和特点，包括：线性表的定义，注意几个关键词：有穷、序列、数据元素；线性表特点：唯一前驱和唯一后继。③线性表元素类型④线性表与向量（一维数组）的关系，注意它们间的异同⑤线性表的操作归类：包括访问操作（搜索，遍历）、维护操作（插入、删除），设置操作（初始化或者置空），判断操作（判空、判满）、游标操作（前驱、后继）第二章线性表本章要点：（2）线性表的顺序存储表示：顺序表的静态和动态的C结构定义，以及C++类定义顺序表的特点：即元素的逻辑顺序和物理顺序的一致性顺序表的主要操作，如插入、删除、搜索等的实现算法④掌握主要功能的关键语句：如遍历整个顺序表、遍历到指定节点的语句；插入、删除时成片移动元素的语句等⑤掌握简单的效率分析，包括搜索算法中数据比较次数的计算，插入、删除的数据移动次数的计算第二章线性表本章要点：（3）线性表的链接存储表示：单链表的C结构定义，以及C++类定义单链表的特点：即元素的逻辑顺序和物理顺序的不一致性单链表的主要操作，如插入、删除、搜索等的实现算法。注意无附加头结点和带附加头结点的单链表上操作实现的差异④掌握主要功能的关键语句：如遍历整个顺序表、遍历到指定节点的语句；无头结点单链表的表头插入、删除；带头结点单链表的搜索操作；带头结点单链表的插入、删除运算以及单链表的创建、释放、逆置、分裂、合并等运算⑤有序单链表的主要操作：如搜索、插入、删除等，以及分裂，合并，剔除重复元素等运算1、在下列关于线性表的叙述中正确的是（）

A线性表的逻辑顺序和物理顺序总是一致的

B线性表的顺序存储表示优于链式存储表示

C线性表若采用链式存储表示时，所有存储单元的地址可连续或者可不连续

D每种数据结构都应具备三种基本运算——插入、删除和查找2、若长度为n的非空线性表采用顺序存储结构，在表的i个位置插入一个数据元素，i的合法值应该是（）

Ai>0B1<=i<=nC0<=i<=n-1D0<=i<=n3、对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算应（）

A将n个元素从小到大排序

B从线性表中删除第i个元素（1<=i<=n）

C查找第i个元素（1<=i<=n）

D在第i个元素（1<=i<=n）后插入一个新元素4、若长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）

AO(n)BO(1)CO(n2)DO(log2n)5、已知L是带表头的单链表，L是表头指针，则摘除首元结点的语句是（）

AL=L->linkBL->link=L->link->linkCL=L->link->linkDL->link=L6、已知单链表A长度为m，单链表B长度为n，若将B接在A的末尾，在没有链尾指针的情形下，算法的时间复杂度应为（）

AO(1)BO(m)CO(n)DO(m+n)7、从一个具有n个结点的有序单链表中查找其值等于x的结点时，在查找成功的情况下，平均需要比较（）个结点。

AnBn/2C(n-1)/2D(n+1)/28、在一个具有n个结点的单链表中插入一个新结点，并可以不保持原有顺序的算法的时间复杂度是（）

AO(1)BO(n)CO(n2)DO(nlog2n)9、给定有n个元素的一维数组，建立一个有序单链表的时间复杂度是（）。

AO(1)BO(n)CO(n2)DO(nlog2n)判断一个带附加头结点的双向循环链表L是否对称相等的算法如下所示，请在算法中的______中填入正确的语句boolsymmetry(DblListDL){ boolsym=true; DblNode*p=DL->rLink,*q=DL->lLink; while(p!=q||p->lLink!=q||

) if(p->data==q->data){______________________________ } else sym=false; returnsym;}sym=truep=p->rLinkq=q->lLink第三章栈和队列本章要点：（1）栈的队列定义和特点，包括：栈的定义，注意栈顶进出、栈底不能进出，顺序存取的概念，栈的先进后出的特点队列的定义，注意队头出、队尾进、顺序存取的概念，队列的先进先出的特点③注意区分栈、队列、向量。栈的队列是顺序存取，向量是直接存取④进栈、出栈、判空、置空操作的使用⑤栈空、队空在实际使用时不算出错，它标志某种处理的结束⑥栈满、队满在实际使用时用力判断可能的出错第二章线性表（2）栈的存储表示及其基本运算的实现：顺序栈的类结构定义顺序栈的栈顶指针实际指示的位置，以及如何用栈顶指针表示顺序栈的栈空、栈满条件顺序栈的进栈、出栈运算的实现。注意操作的前置条件和后置条件，以及在参数表中应用参数的作用④双栈共用一个数组的进栈、退栈、置空栈、判栈空算法以及栈满、栈空条件⑤链式栈的结构定义，注意链式栈的栈顶指针实际指示的位置⑥链式栈的进栈、出栈运算的实现，注意链式栈的栈空条件⑦栈满时的扩充算法第二章线性表（3）队列的存储表示及其基本运算的实现循环队列的雷结果定义，注意对头指针和队尾指针进退的方向，以及如何用这两个指针判对空和队列满循环队列的进队、出队的取模操作的实现使用对头指针front和队列长度length实现循环队列时进队列和出队列的操作④链式队列的类结构定义⑤链式队列的进队和出队列操作的实现⑥

双端队列的进队、出队运算的实现⑦优先级队列的存储结构第二章线性表（4）栈的应用1、已知一个栈的进栈序列为1,2,3，…,n，其输出序列的第一个元素是i，则第j个出战元素是（）

Aj-iBn-iCj-i+1D不确定2、已知一个栈的进栈序列为1,2,3，…,n，其输出序列是p1,p2,p3,…,pn。若p1=n，则pi的值是（）

AiBn-iCn-i+1D不确定3、已知一个栈的进栈序列为1,2,3，…,n，其输出序列是p1,p2,p3,…,pn。若p1=3，则p2的值是（）

A一定是2B一定是1C可能是1D可能是24、将递归算法转换成对应的非递归算法时，除了单向递归和尾递归的情况外，通常需要使用（）保存中间结果

A链表B栈C队列D顺序表5、设求解某问题的递归算法如下voidF(intn){ if(n==1)Move(1); else{ F(n-1); Move(n); F(n-1); }};求解算法的计算时间，仅考虑算法move所作的计算，且move为常数级算法。则算法F的计算时间T(n)的递推关系为（）AT(n)=T(n-1)+1BT(n)=2T(n-1)

CT(n)=2T(n-1)+1DT(n)=2T(n+1)+16、一个队列的进队顺序是1,2,3,4，则该队可能的输出序列是（）

A1,2,3,4B1,3,2,4C1,4,2,3D4,3,2,17、牺牲一个单元区分队空、队满条件的循环队列的队满条件是（）

A(q.rear+1)%maxSize==(q.front+1)%maxSize

B(q.front+1)%maxSize==q.rearC(q.rear+1)%maxSize==q.frontDq.frong==q.rear8、设循环队列存储数组的下标是0～maxSize-1，其队尾指针和队头指针分别为rear和front，则队列中的元素个数为（）

Aq.rear-q.front

Bq.rear-q.front+1C(q.rear-q.front)%maxSize+1Dq.rear-q.front+maxSize)%maxSize9、设栈S的队列Q的初始状态为空，元素a,b,c,d,e,f,g依次进栈栈S。如果每个元素出栈后立即进入队列Q，且7个元素出队的顺序为b,d,e,f,e,a,g，则栈S的容量至少是（）

A1B2C3D4第四章：数组和广义表1要点：

确定数组元素的三要素：行号、列号、元素值

数组元素的存放地址计算2、顺序表：顺序表的定义、搜索、插入与删除要点：

顺序表搜索算法、平均比较次数的计算

插入与删除算法、平均移动次数的计算3、字符串：字符串的定义及其操作的实现要点：

串重载操作的定义与实现4.广义表：广义表定义、长度、深度、表头、表尾1、设有一个10阶的对称矩阵A，采用下三角阵压缩存储方式，以行序为主存储，a11为第1个元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.402.将一个n*n的对称矩阵A的下三角部分（包括对角线）以行序存储到一维数组T中，A[0][0]存放于T[0]中，则对任一上三角元素A[i][j]对应T[k]的下标k是（）。

A.i（i+1）/2+jB.j（j+1）/2+iC.i（j-i）/2+1D.j（i-1）/2+13．若广义表L=(a,(b,c,d))，则GetHead（L）=

，GetTail（L）=第5章树1、树：树的定义、树的基本运算要点：

树的分层定义是递归的

树中结点个数与高度的关系2、二叉树：二叉树定义、二叉树的基本运算要点：

二叉树性质、二叉树中结点个数与高度的关系、不同种类的二叉树棵数、完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位置，二叉树的前序·中序·后序遍历的递归算法和使用栈的非递归算法二叉树的层次遍历算法

中序线索化二叉树、前驱与后继的查找方法、建立中序线索化二叉树的算法3、霍夫曼树：霍夫曼树的构造方法、霍夫曼编码、带权路径长度的计算4、树与森林要点：

树的广义表表示、树的双亲表示、树的左子女-右兄弟表示

树、森林与二叉树的对应关系

树的先根·后根·层次遍历算法 1、用顺序存储的方法，将有n个结点的完全二叉树中所有结点按层逐个顺序存放在一维数组R[n]中，若结点R[i]有左子女，则其左子女是（）；若结点R[i]有右子女，则其右子女是（）。

AR[2i-1]BR[2i] CR[2i+1] DR[2i+2]CD2、用顺序存储的方法，将有n个结点的完全二叉树中所有结点按层逐个顺序存放在一维数组R[n]中，若结点R[i]有双亲（即父结点），则其双亲是（）；该树中编号最大的非叶结点是（）。

AR[(i-1)/2]BR[i/2] CR[n/2-1] DR[n/2]AC3、一个深度为k且只有k个结点的二叉树按照完全二叉树顺序存储的方式存放于一个一维数组R[n]中，那么n最大为（）。

A2kB2k+1 C2k-1 D2kC4、在一棵二叉树的二叉链表中，空指针数等于非空指针数加（）。

A2B1 C0 D-1A5、二叉树的叶结点在前序、中序和后序遍历过程中的相对顺序（）。

A发生改变B不发生改变

C无法确定 D以上均不正确B6、给定二叉树如图所示。设V代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3175624，则其遍历方式为（）

ALRVBVRL CRLV DRVLC7、设n/m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（）。

An在m的右方Bn是m的祖先

Cn在m左方 Dn是m的子孙C12345678、在二叉树中有两个结点m和n，如果m是n的祖先，使用（）可以找到从m到n的路经。

A前序遍历B中序遍历

C后序遍历 D层次序遍历C9、设一棵二叉树的前序序列为abdec，中序遍历为dbeac，则该二叉树的后序遍历序列为（）。

AabdecBdebac Cdebca DabedcC10、设结点x和y是二叉树中任意的两个结点。在该二叉树的前序序列中x在y之前，在其后序序列中x在y之后，则x和y的关系式（）。

Ax是y的左兄弟Bx是y的右兄弟

Cx是y的祖先 Dx是y的子孙C11、线索二叉树是一种（）结构。

A逻辑B逻辑和存储C物理 D线性C12、n个结点的线索二叉树中，线索的数目是（）。

An-1Bn+1 C2n D2n-1B13、在线索二叉树中，指针t所指结点的左子树为空的充要条件是（）。

At->leftChild==NULLBt->ltag==1 Ct->ltag==1&&t->leftChild==NULLD以上都不对C11、线索二叉树是一种（）结构。

A逻辑B逻辑和存储C物理 D线性C12、n个结点的线索二叉树中，线索的数目是（）。

An-1Bn+1 C2n D2n-1B13、在线索二叉树中，指针t所指结点的左子树为空的充要条件是（）。

At->leftChild==NULLBt->ltag==1 Ct->ltag==1&&t->leftChild==NULLD以上都不对C14、将下图中的二叉树按中序线索化，结点e的右指针和结点g的左指针分别指向（）

Aa,dBb,c Cd,a Dc,aD15、在一非空二叉树的中序序列中，根结点的右边（）。

A只有右子树上的所有结点

B只有右子树的部分结点

C只有左子树上的所有结点

D只有左子树上的部分结点Aabcdegf16、设一棵具有n个结点，则它所有结点的度数之和是（）。

A2nB2n-1Cn+1 Dn-1D17、设一棵树中只有度0和度为3的结点，则该树的第i层(i≥1)的结点个数最多为（）。

A3i-1-1B3i-1 C3i-1 D3iC18、设森林F对应的二叉树为B，它有m个结点。B的根为p，p的右子树中结点个数为n，则森林F中第一棵树的结点个数是（）。

Am-nBm-n-1Cn+1D无法确定A19、如果T2是由有序树T转换成的二叉树，那么T中结点的先根遍历顺序对应T2中的结点的（）遍历顺序。

A前序B中序C后序 D层次序A20、设森林中有三棵树，第1,2,3棵树中的结点个数分别为m1,m2和m3。那么在由森林转化成的二叉树中根结点的右子树上有（）个结点。

Am1+m2Bm2+m3Cm3+m1 Dm1+m2+m3B21、将森林转化为对应的二叉树，若在二叉树中，结点u是结点v的双亲结点的双亲结点，则在原来的森林中，u和v可能具有的关系是（）。

Ⅰ父子关系Ⅱ兄弟关系

Ⅲu的双亲结点与v的双亲结点是兄弟关系

A只有ⅠBⅠ和ⅡCⅠ和Ⅲ D全部都有B523417869uvuvuv22、设一棵树的广义表表示为A(B(E),C(F(H,I,J),G),D)，则该树的度为（），树的深度为（），叶节点个数为（）。

A3B4C5 D6A21、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。

An-1BnCn+1 Dn+2CBD六七八章复习第六章有关散列的知识：散列方法的实质散列函数的构造方法出现冲突的解决方法1、散列法存储的基本思想是根据（）来决定元素的存储地址的。

A元素的序号 B元素个数

C关键码值 D非码属性2、设一个散列表中有n个元素，用散列法进行搜索的平均搜索长度是（）

AO(1)BO(n) CO(log2n) DO(n2)3、使用散列函数将元素的关键码值映射为散列地址时，常会发生冲突。此时的冲突是指（）。

A两个元素具有相同的序号

B两个元素的关键码值不同，而非关键码值相同

C不同关键码值对应到相同的存储地址

D装载因子过大，数据元素过多CAC4、计算出的地址分布最均匀的散列函数是（）

A数字分析法 B除留余数法

C平方取中法 D折叠法5、除留余数法的基本思路是：设散列表的地址空间为0～m-1，元素的关键码值为k，用p去除k，将余数作为元素的散列地址，即h(k)=k%p，为了减少发生冲突的可能性，一般取p为（）

Am B小于或等于m的最大素数

C大于m的最小素数 D小于或等于m的最大合数6、已知一个线性序列{38,25,74,63,52,48}，假定采用散列函数h(key)=key%7计算散列地址，并散列存储在散列表A[10]中，若采用线性探查法解决冲突，则在该散列表上进行等概率成功搜索的评价搜索长度为（）。

A1.5B1.67 C1.83 D2.24BBC7、假设有k个关键码值互为同义词，若用线性探查法把这k个关键码值存入散列表，至少要进行（）次探查。

Ak-1

Bk

Ck+1

Dk(k+1)/25、设散列表长m=14，散列函数H(key)=key%11,。表中已经有4个节点，地址分别为addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7，其余地址为空。如用二次探查法解决冲突，关键码值为49的散列地址为（）

A8 B3

C5

D9DD6、设散列表为HT[0..12]，即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：H0(key)=key%13Hi=(Hi-1+Rev(key+1)%11+1)%13其中函数Rev(x)表示颠倒10进行x的各位，如Rev(37)=73,Rev(7)=7。若插入的关键码值序列为{2,8,31,20,70,59,25,28}。

（1）试画出插入这8个关键码值后的散列表（2）计算搜索成功的评价搜索长度ASLsucc2023/10/20讲授目录7.1静态搜索结构7.2二叉搜索树7.3AVL树7.4伸展树7.5红黑树1、在顺序存储的线性表R[30]上进行顺序搜索的平均搜索长度为（）。

A15

B15.5

C16

D202、在对长度为n的顺序存储的有序表进行折半搜索，对应的折半搜索判定树的高度为（）AnB

log2n

C

log2(n+1)

D

log2(n+1)

3、已知有序顺序表(13,18,24,35,47,50,62,83,90,115,134)，当用顺序搜索法搜索值为83的元素时，搜索成功的数据比较次数为（）。

A5

B6

C7

D84、利用逐个数据插入的方法建立序列{35,45,25,55,50,10,15,30,40,20}对应的二叉搜索树后，搜索元素20需要进行（）次元素之间的比较。A5

B4

C7

D10BDDA5、如图所示的AVL树中插入关键码48，得到一棵新的AVL树，在这C新的AVL树中，关键码37所在节点的左右子女节点中保存的关键码分别是（）。

A13,48

B24,48

C24,53 D24,906、将关键码DEC,FEB,NOV,OCT,JUL,SEP,AUG,APR,MAR,MAY,JUN,JAN依次插入一棵初始为空的AVL树中，画出每插入一个关键码值后的AVL树，并标明平衡旋转的类型。并给出等概率时搜索成功的平均搜索长度和搜索不成功时的平均搜索长度。C241353379048讲授内容8.1图的基本概念8.2图的存储结构8.3图的遍历8.4最小生成树8.5最短路径8.6用顶点表示活动的网络（AOV网络）8.7用边表示活动的网络（AOE网络）教学目标：⒈了解图的定义及其存储结构。⒉掌握图的深度优先遍历算法和广度优先遍历算法。⒊掌握求最小生成树的普里姆算法和克鲁斯卡尔算法，并能运用这些算法解决综合问题。⒋理解图的最短路径算法。8.1.1与图有关的若干概念8.1.2图的抽象数据类型1、具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。

A5

B6

C7

D82、设G是一个非连通的无向图，有15条边，则该图至少有（）个顶点A5

B6

C7

D83、对于一个具有n个顶点和e条边的无向图，若采用邻接矩阵表示，则该矩阵的大小是（），矩阵中非零元的个数为（）。

An

B(n-1)

2

Cn-1

Dn2Ee F2e Ge2 Hn2ACDF4、假设有一个有向图具有n个顶点和e条边，若该有向图采用邻接矩阵存储，则删除与顶点i相关联的所有边的时间复杂度是（），若该有向图采用邻接表存储，则删除与该顶点i相关联的所有边的时间复杂度是（）

AO(n)

BO(e) CO(n+e) DO(n2)5、对如图所有的无向图，从顶点a开始进行深度优先搜索，可得到顶点访问序列（），从顶点a开始进行广度优先搜索，可得到顶点访问序列（）。Aabdecgf

Babdegfc Cabdefcg

DabcdegfEabcdefg Fabdcefg Gabcdegf HbeadgcfABEBabcdefg6、任何一个连通图的最小生成树（）

A只有一棵 B有一棵或者多棵

C一定有多棵 D可能不存在7、一个具有n个顶点和e条边的连通图的生成树具有（）条边An

Be

Cn-1

Dn+18、如果具有n个顶点的图是一个环，则它有（）棵生成树。

An

B2n

Cn-1

Dn+19、已知一个带权连通图如图所示，在该图的最小生成树中各条边上权值之和为（），在该图的最小生成树中，从顶点1到6的路径为（）。A31

B38

C36

D43E136 F146G1546 H1436BCBCG10、在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带权值必须是（）。对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（）

A非零 B非整 C非负 D非正

E145 F1235 G1435 H12435CH11、已知一个图如图所示，依据Dijkstra算法求从顶点1到其余各个顶点的最短路径的顺序应是（）

A25463B25436 C23546 D54632

B第九章排序

1、基本概念：关键码、初始关键码排列、关键码比较次数、数据移动次数、稳定性、附加存储、内部排序、外部排序2、插入排序要点：

当待排序的关键码序列已经基本有序时，用直接插入排序最快3、选择排序要点：

用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，而不是顺次后移。这导致方法不稳定。

在堆排序中将待排序的数据组织成完全二叉树的顺序存储。4、交换排序要点：

快速排序是一个递归的排序方法

当待排序关键码序列已经基本有序时，快速排序显著变慢。5、二路归并排序要点：

归并排序可以递归执行归并排序需要较多的附加存储。

归并排序对待排序关键码的初始排列不敏感，排序速度较稳定1．给出一组关键字T=（30，8，16，12，2，28），写出用希尔排序从小到大排序时第一趟（gap=3）结束时的序列

12，2，16，30，8，28

。2．对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需要比较____3____次。3.已知一个数据表为{36,25,25*,62,40,53}，请写出在进行快速排序的过程中每次划分后数据表的变化。(0)[362525*624053](1)[25*25]36[624053]

(2)25*2536[5340]62(3)25*2536405362(1)每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做_______排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做________排序。(2)每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做________排序；(3)在直接选择排序中，记录比较次数的时间复杂度为___O(n2)_____，记录移动次数的时间复杂度为____O(n)____。(4)在堆排序的过程中，对n个记录建立初始堆需要进行________次调整运算，由初始堆到堆排序结束，需要对树根结点进行________次调整运算。(5)在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。(6)假定一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序方法建立的初始堆为________。(4)在堆排序的过程中，对n个记录建立初始堆需要进行___

n/2

_次调整运算，由初始堆到堆排序结束，需要对树根结点进行___n-1__次调整运算。(5)在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为__O(log2n）_，整个堆排序过程的时间复杂度为_O(nlog2n)_。(6)假定一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序方法建立的初始堆为_(84,79,56,38,40,46)_______。(7)快速排序在平均情况下的时间复杂度为________，在最坏情况下的时间复杂度为______。(8)快速排序在平均情况下的空间复杂度为________，在最坏情况下的空间复杂度为______。(9)在快速排序方法中，进行每次划分时，是从当前待排序区间的________向________依次查找出处于逆序的元素并交换之，最后将基准元素交换到一个确定位置，从而以该位置把当前区间划分为前后两个子区间。(10)假定一组记录的排序码为(46,79,56,38,40,80)，对其进行快速排序的一次划分的结果为________。(7)快速排序在平均情况下的时间复杂度为________，在最坏情况下的时间复杂度为________。(8)快速排序在平均情况下的空间复杂度为________，在最坏情况下的空间复杂度为________。(9)在快速排序方法中，进行每次划分时，是从当前待排序区间的两端（低端）向中间（高端）依次查找出处于逆序的元素并交换之，最后将基准元素交换到一个确定位置，从而以该位置把当前区间划分为前后两个子区间。(10)假定一组记录的排序码为(46,79,56,38,40,80)，对其进行快速排序的一次划分的结果为_[4038]46[567980]或[4038]46[795680]

_______。1.已知序列{17，25，55，43，3，32，78，67，91}，请给出采用冒泡排序法对该序列作递增排序时每一趟的结果。2.已知序列{491，77，572，16，996，101，863，258，689，325}，请给出快速排序时每一趟的结果。3.已知序列{86，94，138，62，41，54，18，32}，请给出采用插入排序法对该序列作递增排序时，每一趟的结果。4.已知序列{27，35，11，9，18，30，3，23，35，20}，请给出采用归并排序法对该序列作递增排序时的每一趟的结果。这就是为什么我们彼此喜欢却不能在一起的原因。在两人除去性爱更为广泛的圈子里，你找不到我，我也找不到你，夜晚短暂的爱只适合埋藏在不知哪一天你会出现在我眼前的等待里。我告诉自己，我应该是一个人，一个完整却如筛漏的女人，那