数据结构习题

精选文库第一章知识点：1.基本概念： 数据结构分类、特点等：如线性结构，是数据元素之间存在一种（ 一对一关系）数据元素的概念（数据项）2.时空复杂度1、设有数据结构（D，R），其中D=d1,d2,d3,d4,d5,d6,R=r ,r=(d1,d2),(d2,d3),(d3,d4),(d2,d5),(d3,d5)试按照图论中的画法画出其逻辑结构图。d1d2d31d5d4d62、称算法的时间复杂度为O(f(n)，其含义是指算法的执行时间和_【1】_的数量级相同。 3. 计算下面程序段的时间复杂度。 x=0;for(i=1; in; i+) for (j=1; j=(y+1)*(y+1) y+;1. 解：设执行了t(n)次，则(t(n)+1)2=n，推出t(n)=n1/2-1。所以时间复杂度为O（n1/2）.5. 分析下面各程序段的时间复杂度 （1） O(n*m) (2) O(log3n) 1）for (i=0; in; i+)for (j=0; jm; j+)Aij=0; 2） i=1; while(inext=qB. p-next=q-nextC. p=q-nextD. p-next=q-next-next2、在一个头指针为head的带头结点单链表中，要向表头插入一个由指针p指向的结点,则应执行 【4】p-next=head-next; 、 【5】head-next=p 。 4.在双链表中，在指针P所指结点前面插入一个结点S时的语句序列是：S-next=P;S-prior=P-prior;P-prior=S;_ S-prior-next=S _；3. 在双向链表指针p的结点前插入一个指针q的结点操作是（C ）。A. p-Prior=q;q-Next=p;p-Prior-Next=q;q-Prior=p-Prior;B. p-Prior=q;p-Prior-Next=q;q-Next=p;q-Prior=p-Prior;C. q-Next=p;q-Prior=p-Prior;p-Prior-Next=q;p-Prior=q;D. q-Prior=p-Prior;q-Next=p;p-Prior=q;p-Prior-Next=q;4. 已知p结点是某双向链表的中间结点，要删除p结点的直接后继结点的语句序列是：DA. p-next-next-prior=p; p-next= p-next-next; q=p-next; free(q);B. q=p-next; p-next= p-next-next; p-next-next-prior=p; free(q);C. q=p-next; p-next-prior=p; p-next= p-next-next; free(q);D. q=p-next; p-next= p-next-next; p-next -prior=p; free(q);5.设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_ P-next= = NULL _；r=s; r-next=null;。6.在单链表中，指针p所指结点为最后一个结点的条件是_Ls= =NULL 、ls=ls-link 。7 对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为 O(1) ,在给定值为x的结点后插入一个新结点的时间复杂度为 O(n) _。8. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此顺序表也称为随机存取 的数据结构。（ A ）1. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（E） 访问第i个结点（1in）和求第i个结点的直接前驱（2in） （F） 在第i个结点后插入一个新结点（1in）（G） 删除第i个结点（1in）（H） 将n个结点从小到大排序9、线性链表不具有的特点是（ A ）。A随机访问 B不必事先估计所需存储空间大小C插入与删除时不必移动元素 D所需空间与线性表长度成正比10.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( C )存储方式最节省时间。 A.单链表B.双链表 C.带头结点的双循环链表D.单循环链表11.带头结点的双循环链表L为空表的条件是_ L-next=L-prior 或 L-next=L _。12. 不带头结点的单链表head为空的判定条件是 head=NULL 。 13一个带表头结点的单循环链表，指针P指向链的某一个结点，若P-next-next-next = = P，则此链表的长度可能是 0或2 。14. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（B ）个元素A. 8 B. 63.5 C. 63 D. 715.对于长度为n的顺序表执行删除操作，则其结点的移动次数（C）A.最少为0，最多为n B.最少为1，最多为nC.最少为0，最多为n-1 D.最少为1，最多为n-116.线性表的长度是线性表所占用的存储空间的大小。( F )17.双循环链表中，任意一结点的后继指针均指向其逻辑后继。( T )18、线性表在 B 情况下适用于使用链式结构实现。、需经常修改中的结点值 、需不断对进行删除插入 、中含有大量的结点 、中结点结构复杂19若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。单链表 双链表 单向循环 顺序表1. 假设线性表 L=(a1,a2,an) 用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an, a2,a1)。2试编写算法，以统计带头结点单链表的元素个数。3. 设某单链表的结点结构为data |next,试编写算法判断该链表的元素是否是递增的。4. 已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min和max是两个给定的参数。请分析你的算法的时间复杂度。第3章 栈和队列知识点：栈、循环队列 考点：出入栈操作、栈和队列特点、循环队列操作（元素个数、队头队尾指针）、应用 1一个栈的入栈序列是1、2、3、4，若第二个出栈的元素是4，则最后出栈的元素可能是或。2.一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( B ) A. 2 3 4 1 5B. 5 4 1 3 2 C. 2 3 1 4 5D. 1 5 4 3 23.在对链队列作出队操作时，不会改变front指针的值。( T )4.若一个栈的输入序列为123n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=n-i+1(i=1,2.,n)( T )5. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 , 不允许插入和删除运算的一端称为 栈底 。6、如果入栈序列是1，3，5，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为_41 _。 7有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？答：三个：CDEBA，CDBEA，CDBAE8、向顺序栈中压入新元素时，应当（ A ）。 A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针C先后次序无关紧要 D同时进行9.设一个链栈的栈顶指针是ls，栈中结点格式为info | link ,栈空的条件是_.如果栈不为空，则退栈操作为p=ls；_ Ls= =NULL 、ls=ls-link._；free(p);。10.如果以链表作为栈的存储结构，则退栈操作时（ ） 必须判别栈是否满 对栈不作任何判别 必须判别栈是否空 判别栈元素的类型11. 判定一个栈ST（最多元素为m0）为空的条件是BST-top0 ST-top=0 ST-topm0 ST-top=m0（ D ）12数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为（）rf; （）（nfr）% n; （）nrf; （）（nrf）% n13. 判定一个队列QU（最多元素为m0）为满队列的条件是AAQU-rear QU-front = = m0 BQU-rear QU-front 1= = m0 CQU-front = = QU-rear DQU-front = = QU-rear+114. 设循环队列的容量为40 （序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？答： L=（401911）% 40=8 L=（401119）% 40=3215、假设为循环队列分配的向量空间为Q20，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为_10_。 16.设数组Data0.m作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ）front=front+1 front=(front+1)% mrear=(rear+1)%m front=(front+1)%(m+1) 12. 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A）A队列 B栈C线性表 D有序表13. 用邻接表表示图进行深度优先遍历时，通常是采用 C 来实现算法的。A 树 B. 队列 C. 栈 D. 图 17. 简述以下算法的功能（栈和队列的元素类型均为int）。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。第4章 串知识点：定义、串的基本操作、根据KMP算法原理，分别求出它们的Next函数值作业1.串是任意有限个（ ）符号构成的序列 符号构成的集合字符构成的序列 字符构成的集合2、设有两个串p和q，求q在p中首次出现的位置的运算称作：（） 连接 模式匹配 求子串 求串长3、串是一种特殊的线性表，其特殊性体现在： （ ） 可以顺序存储 数据元素是一个字符 可以链式存储 数据元素可以是多个字符 5、 设S=“A;/document/Mary.doc”，则strlen(s)= 20 。6. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。7.设串s1=ABCDEFG，s2=PQRST，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的结果串是 BCDEFEF 。8. 设串sl=Data Structures with Java,s2=it，则子串定位函数index(s1,s2)的值为（D）A15 B16 C17 D189. 令t=abcaabcab，根据KMP算法原理，分别求出它们的Next函数值。i123456789串tabcaabcabNext(i)第5章 数组和广义表知识点：二维数组的存储、特殊矩阵、广义表作业P31-331. 假设有二维数组A68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 1072 ；若按列存储时，元素A47的第一个字节地址为 1276 。（ ）2. 假设有60行70列的二维数组a160, 170以列序为主序顺序存储，其基地址为1000，每个元素占2个存储单元，那么第32行第58列的元素a32,58的存储地址为()。（无第0行第0列元素） ()4454 ()6904 ()7902 ()答案A, B, C均不对3数组A的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A，的地址为( A ) A. 1140B. 1145 C. 1120D. 11254.二维数组A1520采用按行为主序的存储方式，每个元素占4个存储单元，若A00的存储地址为300，则A1010的地址为（D）A.700B.1120C.1180D.11405写出广义表操作的结果：GetTail【GetHead【GetTail【(a,b),(x,y)】= (y) 。5.取出广义表A=(x,(a,b,c,d)中原子x的函数是_ head(A)_。7. 下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。 ijv7661472183594276537318、设有一个10阶的对称矩阵A1010，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B 中，A00存入B0中，则A85在B 中（ C ）位置。A32 B33 C41 D65 9、假设有100行200列的二维数组a100200以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第45行第67列的元素a4466的存储地址为 23288 。10、已知广义表L=（a），b），（），d），（e，f），（1）写出广义表L的头、尾；（2）计算L的深度；（3）画出L的头尾链表存储结构图。11. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B中（注：B下标从0开始），求矩阵中任一元素ai,j(ij)和一维数组B中下标k的对应关系。解：对应关系如下：第6章 二叉树知识点： 树、二叉树（完全二叉树）、森林基本概念（度、），存储结构，遍历，转换，线索1、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ C ）个。An-1 Bn Cn+1 Dn+22 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有_12_ 个叶子的结点。3 树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和_双亲表示法。4. 把一棵树转换为二叉树后，这棵二叉树的形态是 A 。A. 唯一的 B. 有多种C. 有多种，但根结点都没有左孩子 D. 有多种，但根结点都没有右孩子5、若一棵二叉树中度为2的结点数是10，则叶子结点数为 11 个。10、3个结点可构成 2 棵不同形态的树。5棵不同形态的二叉树。6.深度为6（根的层次为1）的二叉树至多有（ ）结点。 64 32 31 637.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（ ）24 25 23 无法确定8.设一棵完全二叉树具有1000个结点，则此完全二叉树有500 个叶子结点；有 499 个度为2的结点，有 1 个度为1的结点。9. 一棵具有个结点的完全二叉树，它的深度为 9 。10、已知完全二叉树的第8层有8个结点，则其叶子结点数是68。11. 在完全的二叉树中，若一个结点没有 A ，则它必定是叶结点。A. 左子结点 B. 右子结点 C. 左子结点或者没有右子结点 D. 兄弟12.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( .A )的二叉树。 A.空或只有一个结点B.高度等于其结点数 C.任一结点无左孩子D.任一结点无右孩子13.在有n个结点的二叉链表中，值为非空的链域的个数为( A ) A. n-1B. 2n-1 C. n+1D. 2n+114.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为(.B ) A. 0B. 1 C. 2D.不确定15.DFS算法的时间复杂度为( C ) A. O(n)B. O(n3) C. O(n2)D. O(n+e)16、有n个叶子结点的哈夫曼（Huffman）树所具有的结点数为2n-117.判断线索二叉树中某结点指针P所指结点有左孩子的条件是_P-ltag=1_。18、二叉树在线索化后，仍不能有效求解的问题是（D ）。A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前驱D.后序线索二叉树中求后序后继 19、将下图中的树用孩子-兄弟链表来表示。 （1）画出该二叉链表；（2）对该二叉链表进行何种遍历方式可实现树的后根遍历？写出后根序列。20. 求出下图的一棵最小生成树。21. 指出下面函数FS的功能。其中，p指向先序线索二叉树的某个结点。 typedef enumLINK，THERADflag; typedef char DataType; typedef struct node DataType data; flag ltag，rtag; struct node * lchild， * rchild; BinNode; BinNode * FS(BinNode *p) if(p-ltag=LINK) return p-lchild; else return p-rchild; 函数功能：在先序线索二叉树中查找某结点的后继。22. 给定二叉树的两种遍历序列，分别是：中序遍历序列：DCBGEAHFIJK；后序遍历序列：DCEGBFHKJIA。（1） 请画出该树。（2） 画出与（1）求得的二叉树对应的森林。23. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为abcdefgh0.070.190.020.060.320.030.210.10要求：（1） 为这8个字母设计哈夫曼编码，并画出哈夫曼树。（2） 求该哈夫曼树的带权路径长度。24树的后根遍历方法是：若树非空则（1）依据次后根遍历根的各个子树，m;（2）访问根结点。对下图所示的树，用后根遍历方法进行遍历，请写出遍历所得到的结点访问序列。ABACADAEAFAGAHAIJKA25. 假设一棵二叉树的先序序列为 EBADCFHGIKJ 和中序序列为 ABCDEFGHIJK。i. 请画出该树。ii. 画出与（1）求得的二叉树对应的森林。26.已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树及对应的二叉树。123456789101112131415dataABCDEFGHIJKLMNOparent0111223344566781.计算二叉树的深度的算法Int deepTree(p) / P为指向二叉树之根 If(p=NULL) return t; Else If(deepTree(p-Lchild)deepTree(p-Rchild) Return deepTree(p-Lchild)+1; Else Return deepTree(p-Rchild)+1;2、读程序二叉树以二叉链表作为存储结构，其定义如下：TypedefstructNodechardata;StructNode*lc,*rc;/*lc,rc分别指向左，右子树*/BiTNode,*BiTree;Intn=0;二叉树如右图，根的地址为root，请给出：（1）下列函数的功能（2）调用语句prek(root,5);输出结果是什么？Voidprek(BiTreeT,intk)if(T&nlc,k);Prek(T-rc,k);N+;printf(“%c”,T-data);3、编写递归算法，计算二叉树中叶子结点的数目。 4设二叉树以二叉链表为存储结构，结点结构为lchild |data |rchild 。设计一个算法，求在前根序列中处于第k个位置的结点Bitreptr search(bitreptr t ,int k)if (t!=null) count+;if (count= =k)return (t); else search(t-lchild,k); search(t-rchild,k); 5. 以线索链表作为存储结构，写出后序线索树中查找 *p的后序前驱的算法。第七章 图知识点：基本概念（度、完全图、连通子图、生成树、最小生成树），图的存储（邻接矩阵、邻接表），图的遍历，最小生成树，拓扑排序，最短路径，关键路径1 求最短路径的DIJKSTRA算法的时间复杂度为( C ) A. O(n)B. O(n+e) C. O(n2)D. O(ne)2.有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的非零元个数。( T )3.有向图的邻接表和逆邻接表中的结点数一定相同。( T )4.图G的拓扑序列唯一，则其弧数必为n-1(其中n为G的顶点数)。( F )5. 在一个图中，所有顶点的度数之和等于图的边数的 C 倍。 A1/2 B. 1 C. 2 D. 4 6. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。 A1/2 B. 1 C. 2 D. 4 7. 已知图的邻接表如下图1所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是DA0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 38有n个顶点的强连通有向图G至少有 n 条弧。 9、设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ B ）。AO（nlog2e） BO（n+e）CO(ne) DO(n2)10、求最短路径的FLOYD算法的时间复杂度为（D ）。A.O(n)B.O(n+e)C.O(n2)D.O(n3)11、若要求一个稀疏图G的最小生成树，最好用 A 算法来求解。 A克鲁斯卡尔(Kruskal) B. 普里姆(Prim) C迪杰斯特拉（Dijkstra） D. 以上均可，没有区别12设有一个无向图G=（V，E）和G=（V，E）如果G为G的生成树，则下面不正确的说法是（ ）G为G 的子图 G为G 的边连通分量G为G的极小连通子图且V=V G为G的一个无环子图13一个有向图G中若有弧、和, 则在图G的拓扑序列中，顶点vi,vj和vk的相对位置为_i,j,k_。14. 有8个结点的有向图最多有 56 条边。15. 用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 O(n2) ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e) 。（ A ）16用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。(A)队列 (B). 栈 (C). 树 (D). 图 17. 用邻接表表示图进行深度优先遍历时，通常是采用 C 来实现算法的。A 树 B. 队列 C. 栈 D. 图 1、请对下图的无向带权图：（1） 写出它的邻接矩阵；（2） 写出它的邻接表；（3） 设起点为a，按普里姆算法或克鲁斯卡尔算法求其最小生成树。 2. 已知图的邻接矩阵，根据算法，分别求从顶点0出发按深度和广度优先遍历的结点序列。解：按深度优先遍历的结点序列是0134256；按广度优先遍历的结点序列是0123465。3. 对于下图所示的AOE网络，计算各活动弧的e(ai)和l(aj)的函数值，各事件（顶点）的ve(vi)和vl(vj)函数值，列出各条关键路径。v2v4v1v5v3v6162111143361918654 下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。求最小生成树，两种方案5. 已知某有向图的邻接矩阵如右图所示，要求：（1） 确定图中每个顶点的入/出度；（2） 画出该图；（3） 画出该图的邻接表（4） 画出该图的逆邻接表。6 利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。 第8章 查找知识点：折半查找过程，堆概念，二叉排序树，哈希查找，平衡二叉树。1.对有18个元素的有序表作二分查找，则查找A3的比较序列的下标依次为(D ) A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，32、对表长为900的索引顺序表进行分块查找，假设每一块的长度均为15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为_38.5_。 3. 在表长为的链表中进行线性查找，它的平均查找长度为 ()/ 。 4. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。（ ）5在对有6400个记录的索引顺序表进行查找，最理想的块长为 .(). 64 (). 100 () 80 () log26400 6、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（B ）型调整以使其平衡。 A. LLB.LRC.RLD.RR7、）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找。（1） 画出描述折半查找过程的判定树；（2） 若查找元素54，需依次与哪些元素比较？（3） 若查找元素90，需依次与哪些元素比较？（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。8、设哈希（Hash）表的地址范围为015，哈希函数为：H（Key）Key mod 13。Key为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，48，41，65，49）造出Hash表，试回答下列问题：（1） 画出哈希表的示意图；（2） 若查找关键字30，需要依次与哪些关键字进行比较？(3) 计算填充因子；(4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。9.已知长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）(1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。(2) 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。10在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树，并求出其平均查找长度。11、有一个40000项的表,要采用等分区间顺序查找的索引 (分块)查找法,问:(1)每块理想长度是多少?(2)最理想的块数是多少?(3)计算平均查找长度ASL。(4)若每块长度为100,计算ASL。12.下面是将键值为x 的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。typedef struct pnode int key; struct pnode *left, *right; pnode;void searchinsert(int x, pnode t ) /*t为二叉排序树根结点的指针*if ( )p=malloc(size);p-key=x;p-lchild=null; p-rchild=null;t=p; else if (xkey) searchinsert(x,t-lchild) else_;13设n个元素的有序表为，为一个给定的值，二分查找算法如下： int binsearch(sqlist R, keytype K) j=1;h=n ;suc=0; while(j=h)&(!suc) mid =(j+h)/2; switch case K=Rmid.key: suc=1; break; case KRmid.key: j=mid+1 if (suc) return(mid); else return(0);将上述算法中划线语句改为：KRmid.key: h=mid.（1）改动后，算法能否正常工作？请说明原因。（2）若算法不能正常工作，给出一个查找序列和一个出错情况的查找键值；若能正常工作，请给出一个查找序列和查找某个键值的比较次数。14. 从空树起，依次插入关键字37，50，42，18，12，56，30，23，构造一棵二叉排序树。（1） 画出该二叉排序树。（2） 画出从（1）所得树中删除关键字为37的结点之后的二叉排序树。15. 已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。第九章 排序知识点：堆的判定，排序算法的稳定性，各类排序算法执行过程、复杂性分析，1. 下列关键字序列中， 是堆。. 16, 72, 31, 23, 94, 53 . 94, 23, 31, 72, 16, 53 . 16, 53, 23, 94，31, 72 . 16, 23, 53, 31, 94, 722 以下排序方法中稳定的是：. 希尔排序 . 快速排序 . 归并排序 . 堆排序3.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行（按递增排序），冒泡排序最省时间，快速排序最费时间。4. 堆是一个键值序列k1,k2, kn,对i=1,2,|_n/2_|,满足( )kik2ik2i+1 kik2i+1k2ikik2i且kik2i+1(2i+1n) kik2i 或kik2i+1(2i+1n) 5、堆是一种 排序。. 插入 .选择 . 交换 . 归并6、若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为. 38, 40, 46, 56, 79, 84 . 40, 38, 46 , 79, 56, 84. 40