数据结构常见题型整合.docx

数据结构常见题型整合1、设栈的输入序列是1，2，3，4, 则（ ）不可能是其出栈序列。A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， 2、在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为( )(A) f-next=c；f=s (B) r-next=s；r=s(C) s-next=r；r=s (D) s-next=f；f=s3、顺序存储的栈和队列中已经各有N个结点，要删除一个结点分别需要移动数据（ ）次和（ ）次。A. N/2 , N B. N , N/2 C. 0 , N D. N , 04、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。AXYZ B. YZX C. ZXY D. ZYX5、 一个递归算法必须包括（ ）。A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分6、如下四个选项中，那个选项是能够正确判断循环队列是否排满元素的操作（其中MAXQSIZE表示队列的容量） （ ）：Aif (Q.rear = Q.front) Bif (Q.rear = (Q.front + MAXQSIZE)Cif (Q.rear = (Q.front + 1) % MAXQSIZE)Dif (Q.front = (Q.rear + 1) % MAXQSIZE)7、假设以数组Am存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m8、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 9、利用栈进行十进制数1348转换成八进制数，则入栈的数依次是（ ）。A. 1 , 3 , 4 , 8 B. 8 , 4 , 3 , 1 C. 2 , 5 , 0 , 4 D. 4 , 0 , 5 , 2 10、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front11、栈和队列的共同点是（ ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点1、栈是_操作受限（或限定仅在表尾进行插入和删除操作） 的线性表，其运算遵循_后进先出_的原则。2、队列的插入操作在_ 队尾_进行，删除操作在 队头_进行，其特点是_先进先出_。3、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_SSSS _。4、表达式求值是_栈_应用的一个典型例子。5、栈和队列在本质上都是同一种基本数据结构的特例，这种基本的数据结构就是 线性表 。6、在作进栈运算时，应先判别栈是否 . 满 ，在作退栈运算时应先判别栈是否 空 。当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为 n 。12、在二叉树的第I层(I1)上最多含有结点数为（ ） A. 2I B. 2I-1-1 C. 2I-1 D. 2I -113、深度为6的二叉树最多有( )个结点 A64 B.63 C.32 D.3114、一棵树高为K的完全二叉树至少有( )个结点 A.2k 1 B.2k-1 1 C.2k-1 D.2 k 15、有关二叉树下列说法正确的是（ ）A. 二叉树的度为2 B. 一棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 16、n个结点的线索二叉树上含有的线索数为（ ）A. 2n B. nl C. nl D. n 17、线性表和树的结构区别在于（ ）A前驱数量不同，后继数量相同B前驱数量相同，后继数量不同C前驱和后继的数量都相同D前驱和后继的数量都不同18、已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，则其前缀形式为( )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE19、设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ）A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G20、一棵具有 n个结点的完全二叉树的树高度（深度）(符号表示取不大于x的最大整数)是（ ）A. B. C. D.21、利用二叉链表存储树，则根结点的右指针是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空22、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（ ）。ACBEFDA B FEDCBA C CBEDFA D不定 23、若前序遍历二叉树的结果为序列A、B、C，则有_棵不同的二叉树可以得到这一结果。A. 3 B. 4 C. 5 D. 624、线索二叉树是一种（ ）结构。A逻辑 B逻辑和存储 C物理 D线性 二、填空题 7、对于任意一棵二叉树，如果其叶子结点数为N0，度为1的结点数为N1，度为2的结点数为N2，则N0=_ N2 + 1_。8、具有256个结点的完全二叉树的深度为_9_。9、一个深度为4的二叉树，其结点至少有 4 个，至多有 15 个：10、深度为H 的完全二叉树至少有_ 2H-1_个结点；至多有 2H-1_个结点；H和结点总数N之间的关系是 H=log2N+1。11、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，N个结点的二叉树共有_2N_个指针域，其中有_N-1_个指针域是存放了地址，有_N+1_个指针是空指针。12、设一棵赫夫曼树有6个叶子结点，权值分别为3、4、7、14、15、20，则根结点的权值是_63_13、对一棵完全二叉树，设一个结点的编号为i，若它的左孩子结点存在，则其编号为 2i ；若右孩子结点存在，则其编号为 2i+1 ；而双亲结点的编号为 。 14、赫夫曼树是带权路径长度 最小的 二叉树，又称最优二叉树，路径上权值较大的结点离根较近。15、下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。typedef struct node int data; struct node *lchild;_ struct node *rchild _; BiTNode, *BiTree;void createBitree(BiTree &T) scanf(“%c”, &ch);if(ch=#) T=NULL ;else T=( BiTNode *)malloc(sizeof(BiTNode); T-data=ch; createBitree(T-lchild)；_createBitree(T-rchild);16、二叉树由_根结点_，_左子树_，_右子树_三个基本单元组成。17、树的链表存储结构常用的有三种，其中，双亲 表示法以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。孩子 表示法每个结点的孩子以单链表的形式存储，n个结点有n个孩子链表，n个头指针又组成一个线性表，并以顺序存储结构存储。孩子兄弟 表示法以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。/P135-13618、利用树的孩子兄弟表示法存储，可以将一棵树转换为_二叉树_。19、在二叉树中，指针p所指结点为叶子结点的条件是_ p-lchild=NULL & p-rchlid=NULL _。20、树的孩子兄弟表示法和二叉树的二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。21、树和二叉树逻辑上都是树形结构，但是二叉树不是树的特例，二叉树与树是两个不同的概念。二叉树的度 至多为2，树无此限制；二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是 左子树还是右子树，树无此限制。三、简答题 1、已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ，中序遍历的结果是KBCDAFHIGJ, 试画出这棵二叉树，并写出后序遍历结果。 答案：当前序序列为ABKCDFGHIJ，中序序列为KBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：这棵二叉树的后序遍历结果是：K D C B I H J G F A2、某通信电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数（权值）分别是16，5，7，3，8，1。试画出其哈夫曼树，确定其对应的哈夫曼编码，并计算其带权路径长度。为使结果唯一，请将权值较小的结点作为其双亲的左孩子，而将权值较大的结点作为其双亲的右孩子。答案：哈夫曼树如下：对应的哈夫曼编码如下：A: 0B: 101C: 110D: 1001E: 111F: 1000带权路径长度为: WPL=(1+3)*4+(5+7+8)*3+16*1=923、对下图所示二叉树分别按前序中序后序遍历，给出相应的结点序列，同时给二叉树加上中序线索。答案：（1）前序序列：ABDEHCFG（2）中序序列：DHEBAFCG（3）后序序列：HEDBFGCA （4）中序线索见图中虚线箭头所示。25、以下数据结构中，哪种具有非线性结构？A栈 B队列 C双向链表 D十字链表 26、下面关于图的存储的叙述中正确的是（ ）。 A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。 B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。 C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。 D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关27、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 （ ） A.先根遍历 B.中根遍历 C.后根遍历 D.按层次遍历28、图的广度优先遍历算法类似于树的（ ）。 A. 中根遍历B. 先根遍历C. 后根遍历D. 按层次遍历29、设无向图的顶点个数为n，则该图最多有（ ）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 30、设有n个结点的无向图，该图至少应有( )条边才能确保是一个连通图。An-1 Bn Cn+1 Dnlogn；31、一个含有n个顶点的非连通图，则（ ）：A它的边一定不大于n-1B它的边一定不大于nC它的边一定小于n-1D它的边一定大于032、要连通具有n个顶点的有向图，至少需要（ ）条边。An-l Bn Cn+l D2n33、下列说法不正确的是（ ）。A图的遍历是从给定的源点出发每一个顶点仅被访问一次 B遍历的基本算法有两种：深度遍历和广度遍历C图的深度遍历不适用于有向图 D图的深度遍历是一个递归过程34、无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b 35、若一个连通图有n个顶点, 则它的生成树有（ ）条边。A. nB. n-1C. n+1D. n(n-1)/2二、填空题22、邻接多重表适于表示 稀疏无向图 ，邻接表、逆邻接表和十字链表 适于表示稀疏有向图。23、设有向图的顶点个数为n，则该图最多有 n(n-1) 条弧。24、右图中顶点D的出度是 3 。 25、8层完全二叉树至少有_ 128(第七层满，加第八层个) _个结点，拥有100个结点的完全二叉树的最大层数为_7_。26、求图的最小生成树有两种算法：_普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法 。其中，_克鲁斯卡尔_算法适合于求_边稀疏 _的稀疏图的最小生成树。普里姆算法适用于求边稠密的网的最小生成树。 27、对于含n个顶点e条边的无向连通图，利用普里姆算法生成最小代价生成树其时间复杂度为_ O(n2）_，利用克鲁斯卡尔算法生成最小代价生成树其时间复杂度为_ O(eloge)_。 28、在无向图的 深度优先遍历算法 中，DFS（从某个顶点出发深度优先遍历图的算法）被调用了几次就说明该图有几个 联通分量 。29、一个有n个结点的图，最少有 1 个连通分量，最多有 n 个连通分量。30、判断一个无向图是一棵树的条件是_有n个顶点，n-1条边的无向连通图 。31、有向图G的强连通分量是指_有向图的极大强连通子图_。32、右图中的强连通分量的个数为 3 个。33、一个连通图的_生成树_是一个极小连通子图。34、若用n表示图中顶点数目，则有_ n(n-1)/2_条边的无向图成为完全图。35、已知一无向图G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_深度优先_遍历方法。36、为实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列_存放被访问的结点以实现遍历。37、设无向图G有n个顶点，m条边。阅读下面用邻接表存储该图的算法。（设顶点值用1n或0n-1编号），并在画线处完成填空。 void CreatGraph (AdjList g) /建立有n个顶点和m 条边的无向图的邻接表存储结构int n,m; scanf(%d%d,&n,&m);for (i =1,i=n;i+) /输入顶点信息, 建立顶点向量 scanf(&gi.vertex); gi.firstarc=null;for (k=1;kadjvex=j; p-next=gi.firstarc; gi.firstarc=p; /将边结点链入 p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=i;p-next=gj.firstarc;gj.frstarc=p; 三、简答题 4、已知一个无向网的顶点集为a,b,c,d,e，其邻接矩阵如下所示 (1)画出该无向网图形； (2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。答案：(1)该无向网图形如下：(2) 深度优先序列为：a b c d e ； 广度优先序列为：a b d c e36、适用于折半查找的表的存储方式及元素排列要求为( ) A链接方式存储，元素无序 B链接方式存储，元素有序C顺序方式存储，元素无序 D顺序方式存储，元素有序37、对有18个元素的有序表A作折半查找，则查找A3的比较序列的下标为（ ） A.1，2，3 B.9，5，2，3 C.9，5，3 D.9，4，2，3 38、对有14个数据元素的有序表R进行折半搜索，搜索到R3的关键字等于给定值，查找过程中元素比较的顺序依次为（ ）。A. R6, R2 ,R4, R3 B. R6, R4 ,R2, R3C. R0, R1 ,R2, R3 D. R0, R13 ,R2, R339、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A（N+1）/2 B. N/2 C. N D. （1+N）*N /240、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下 查找成功所需的平均比较次数为（ ）。 A35/12 B.37/12 C.39/12 D.43/12 41、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减42、设有序表的关键字序列为1，4，6，10，18，35，42，53，67，71，78，84，92，99，当用二分查找法查找健值为84的结点时，经（ ）次比较后查找成功。A.2 B. 3 C. 4 D.1243、在查找过程中，只完成查找操作，这种查找称为（ ）A. 静态查找B.动态查找C.内部查找D.外部查找44、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A（100，80，90，60，120，110，130） B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130） D. (100，80， 60，90，120，130，110)二、填空题38、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败，它们的平均查找长度是 不同的 ，对于查找成功,他们的平均查找长度是 相同的 。39、执行顺序查找时，储存方式可以是_顺序存储或链式存储 _，二分法查找时，要求线性表_顺序存储且有序_。40、在数据结构中一般采用平均查找长度衡量查找算法时间性能，而对于排序算法一班通过统计记录的比较次数和移动次数衡量排序算法的时间性能。41、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较 _7_ 次就可以断定数据元素X是否在查找表中42、二叉查找树的查找效率与二叉树的 树型 有关, 在 呈单枝树 时其查找效率最低。43、若表中元素个数为n，则顺序查找该表中的元素，若查找成功，则比较关键字的次数最多为_n _次，平均比较次数为 (n+1)/2 ；若进行折半查找，则最大比较次数是 _2n+1 。44、给定一个主关键字，在长为n的有序表中进行折半查找，则最多经过 log2n +1次比较即可确定该关键字是否在表中，至少经过1次比较即可确定该关键字在表中。45、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为_4_。46、在有序表A1.12中，采用二分查找算法查等于A12的元素，所比较的元素下标依次为_6,9,11,12 。47、己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需_2_次查找成功，47时_4_成功，查100时，需_3_次才能确定不成功。48、假定查找有序表A1.12中每个元素的概率相等，则进行二分查找时的平均查找长度为_37/12_。49、在查找中，能够唯一标识一个记录的关键字称之为主关键字，能够标识若干记录的关键字称之为次关键词。50、动态查找表和静态查找表的重要区别在于前者包含有_插入 _和_ 删除_运算，而后者不包含这两种运算。51、已知二叉排序树的左右子树均不为空，则_左子树_上所有结点的值均小于它的根结点值，_ 右子树_上所有结点的值均大于它的根结点的值。三、简答题5、设有序表为(a, b, c, d, e, f, g, h, i, j, k, p, q)，请分别画出对给定值a, g和n进行折半查找的过程。【答案】（1）查找a的过程如下(圆括号表示当前比较的关键字)，经过三次比较，查找成功。（2）g的查找过程如下，一次比较成功。 abcdef(g)hijkpq（3）n的查找过程如下，经过四次比较，查找失败。6、构造有12个元素的二分查找的判定树，并求解下列问题：（1）各元素的查找长度最大是多少？（2）查找长度为1、2、3、4的元素各有多少？具体是哪些元素？（3）查找第5个元素依次要比较哪些元素？（4）试求解在等概率情况下，查找成功情况下二分查找的平均查找长度。【答案】12个元素的二叉判断树如下图所示：（1）最大查找长度是树的深度4。（2）查找长度为1的元素有1个，为第6个，查找长度为2的元素有2个，为第3个和第9个，查找长度为3的元素有4个，为第1、4、7、11个，查找长度为4的元素有5个，为第2、5、8、10、12个。（3）查找第五个元素依次比较6，3，4，5。（4）根据, 平均查找长度ASL =（1+2*2+4*3+5*4）/12 = 37/12 7、设有一个输入数据的序列是 46, 25, 78, 62, 12, 80 , 试画出从空树起，逐个输入各个数据而生成的二叉排序树。答案：8、已知序列40，30，50，24，28，46，60，10。试画出由该输入序列构成的二叉排序树，并分别给出依次执行下列操作后的二叉排序树（共画四棵树） （1）插入数据42和80；（2）删除数据30；（3）删除数据50。答案：45、n个记录进行直接插入排序时，记录最小的比较次数是 ( ) A.(n-1) B.0C.(n+3)(n-2)/2D.n2/246、对n个记录进行希尔排序，所需要的辅助存储空间为（ ）。 A.O（1og2n） B.O（n） C.O（1） D.O（n2）47、就平均性能而言，目前最好的内排序方法是( )排序法。 A.冒泡 B.希尔插入 C.交换 D.快速48、直接插入排序在最好情况下的时间复杂度为（ ）A O(logn) B O(n) C O(n*logn) D O(n2)49、以下算法思路分别出自什么排序算法：取当前最小的数，插入到已经排好序的数据末尾：（ ）；取当前要排序的数，插入到已经排好序的数据中适当位置：（ ）；相邻两个数比较，如果大小顺序颠倒就把两者交换过来：（ ）。A. 插入排序、选择排序、起泡排序 B. 选择排序、插入排序、起泡排序C. 插入排序、选择排序、快速排序 D. 选择排序、插入排序、快速排序50、设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。 (A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21 (C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，2151、下列四种排序算法中，哪一个需要采用递归调用的方式实现A、直接插入排序B、快速排序C、冒泡排序D、折半插入排序52、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。 A.插入 B.选择 C.希尔 D.快速53、快速排序方法在（ ）情况下最不利于发挥其长处。 A.要排序的数据量太大 B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数 D.要排序的数据已基本有序54、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47 25 15 21（2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84 则采用的排序是 ( )。 A. 选择 B. 冒泡 C. 快速 D. 插入55、在希尔排序算法中，需要借助（ ）实现A、直接插入排序B、快速排序C、冒泡排序D、折半插入排序56、若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行（ ）次比较。 A. 3 B. 10 C. 15 D. 25 57、在下列排序算法中，哪一个算法的时间复杂度与初始排序无关（ ）。 A.直接插入排序 B.起泡排序 C. 快速排序 D.选择排序 58、对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。A直接插入 B. 起泡排序 C. 快速排序 D. 二分法插入59、若采用希尔排序法对序列 12,36,21,7,2,19,6,31,49,13,27,38,5 进行排序，增量分别为5、3、1。那么当增量为3时，排序结束后的序列是哪一个A. 5, 2, 19, 6, 27, 21, 7, 31, 38, 12, 36, 49, 13 B. 12,6, 5, 7,2,19, 36, 21,49,13,27,38, 31 C. 7, 2, 5, 12, 6, 19, 13, 21, 38, 31, 27, 49, 36 D. 2, 6, 5, 7, 12, 13, 27, 21,31, 19, 36, 38, 49 二、填空题52、直接插入排序、折半插入排序、起泡排序都属于稳定排序。希尔排序、快速排序、选择排序都属于不稳定排序。53、直接插入排序用监视哨的作用是 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率 。54、对有限个记录进行起泡排序，第n趟起泡排序的排序结束位置应为上一趟排序中最后一次发生记录交换的位置。55、对n个记录的表r1.n进行简单选择排序，所需进行的关键字间的比较次数为 n(n-1)/2 ,若进行 起泡排序 ，则最多需要n(n-1)/2次的比较。56、假设存放在计算机内存中的含n个记录的序列为 R1, R2, ，Rn ，其相应的关键字序列为 K1, K2, ，Kn ，这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Ks1Ks2Ksn，按此固有关系将n个记录序列重新排列为 Rs1, Rs2, ，Rsn 。若整个排序过程都在内存中完成，不需要访问外存，则称此类排序问题为内部排序。57、对于排序算法，其基本思想是不断扩大有序序列区，同时不断缩小无序序列区。58、判定起泡排序的结束条件是：当至多进行n-1趟起泡排序，或一趟起泡排序中未发生交换（即已有序）时，结束排序。三、简答题9、(1)请简单叙述希尔排序的基本思想。(2)写出初始数列49，38，65，97，76，13，27，49，55，4 在希尔排序下的状态变化过程（假设增量d=5、3、1）。(1)希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将待排序的记录划分成几组（缩小增量分组），从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。(2)：算法描述题输入50个学生的记录（每个学生的记录包括学号和成绩），组成记录数组，然后按成绩由高到低的次序输出（每行10个记录）。排序方法采用选择排序。 请写出该算法。 typedef struct int num; float score; RecType;void SelectSort(RecType R51，int n) for(i=1; in; i+) k=i; /假定第i个元素的关键字最大 for(j=i+1; jRk.score) k=j;if(i!=k) Ri Rk; /与第i个记录交换 for(i=1; i=n; i+) /输出成绩 printf(%d,%f, Ri.num, Ri.score); if(i%10=0) printf(n);