数据结构习题.pdf

《数据结构习题.pdf》由会员分享，可在线阅读，更多相关《数据结构习题.pdf（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章知识点：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)试按照图论中的画法画出其逻辑结构图。d1d5d2d3d4d62、称算法的时间复杂度为O(f(n)，其含义是指算法的执行时间和_【1】_的数量级相同。3.计算下面程序段的时间复杂度。x=0;for(i=1;in;i+)for(j=1;j=n-i;j+)x+;解：因为 x+共执行了 n-1+n-2+1=

2、n(n-1)/2，所以执行时间为 O（n）.4.计算下面程序段的时间复杂度。x=n;y=0;解：设执行了 t(n)次，则(t(n)+1)=n，推出 t(n)=n-1。所以时间复杂度为 O（n）.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

3、;、【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.

4、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-p

5、rior=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）

6、的操作是：（E）访问第 i 个结点（1in）和求第 i 个结点的直接前驱（2in）（F）在第 i 个结点后插入一个新结点（1in）（G）删除第 i 个结点（1in）（H）将 n 个结点从小到大排序9、线性链表不具有的特点是（A）。A随机访问 B不必事先估计所需存储空间大小C插入与删除时不必移动元素 D所需空间与线性表长度成正比10.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用(C )存储方式最节省时间。A.单链表B.双链表D.单循环链表 C.带头结点的双循环链表11.带头结点的双循环链表L 为空表的条件是_ L-next=L-prior或 L-next=L _

7、。12.不带头结点的单链表 head 为空的判定条件是head=NULL。13一个带表头结点的单循环链表，指针P 指向链的某一个结点，若P-next-next-next=P，则此链表的长度可能是 0 或 2。14.向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（B）个元素A.8 B.C.63 D.715.对于长度为 n 的顺序表执行删除操作，则其结点的移动次数（C）A.最少为 0，最多为 n B.最少为 1，最多为 nC.最少为 0，最多为 n-1 D.最少为 1，最多为 n-116.线性表的长度是线性表所占用的存储空间的大小。(F)17.双循环链表中，任意一结

8、点的后继指针均指向其逻辑后继。(T)18、线性表在 B情况下适用于使用链式结构实现。、需经常修改中的结点值、需不断对进行删除插入、中含有大量的结点、中结点结构复杂19 若某线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋元素，则采用（）存储方式最节省时间。单链表双链表单向循环顺序表1.假设线性表 L=(a1,a2,an)用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an,a2,a1)。2试编写算法，以统计带头结点单链表的元素个数。3.设某单链表的结点结构为 data|next,试编写算法判断该链表的元素是否是递增的

9、。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 5 C.2 3 1 4 5B.5 4 1 3 2D.1 5 4 3 23.在

10、对链队列作出队操作时，不会改变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，CD

11、BAE8、向顺序栈中压入新元素时，应当（A）。A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针C先后次序无关紧要 D同时进行9.设一个链栈的栈顶指针是ls，栈中结点格式为 info|link,栈空的条件是_.如果栈不为空，则退栈操作为p=ls；_ Ls=NULL、ls=ls-；free(p);。10.如果以链表作为栈的存储结构，则退栈操作时（）必须判别栈是否满 对栈不作任何判别 必须判别栈是否空 判别栈元素的类型11.判定一个栈 ST（最多元素为 m0）为空的条件是 BST-top0ST-top=0ST-topm0ST-top=m0（D）12数组用来表示一个循环队列，为当前队列头元素

12、的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为（）rf;（）（nfr）%n;（）nrf;（）（nrf）%n13.判定一个队列 QU（最多元素为 m0）为满队列的条件是 AAQU-rear QU-front=m0 B QU-rear QU-front 1=m0CQU-front=QU-rear DQU-front=QU-rear+114.设循环队列的容量为 40（序号从 0 到 39），现经过一系列的入队和出队运算后，有 front=11，rear=19;front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个答：L=（401911）%40=8

13、 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.队列

14、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

15、，求 q 在 p 中首次出现的位置的运算称作：（）连接模式匹配求子串求串长3、串是一种特殊的线性表，其特殊性体现在：（）可以顺序存储数据元素是一个字符可以链式存储数据元素可以是多个字符5、设 S=“A;/document/”，则 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,

16、len(s2),2)的结果串是BCDEFEF。8.设串 sl=Data Structures with Java,s2=it，则子串定位函数 index(s1,s2)的值为（D）A 15 B 16 C 17 D 189.令 t=abcaabcab，根据 KMP 算法原理，分别求出它们的Next 函数值。i串 tNext(i)1a2b3c4a5a6b7c8a9b第 5 章 数组和广义表知识点：二维数组的存储、特殊矩阵、广义表作业 P31-331.假设有二维数组 A68，每个元素用相邻的6 个字节存储，存储器按字节编址。已知 A 的起始存储位置（基地址）为 1000，则数组 A 的体积（存储量）为

17、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.1140

18、C.1120B.1145D.11254.二维数组 A15 20采用按行为主序的存储方式，每个元素占4 个存储单元，若A00的存储地址为 300，则 A10 10的地址为（D）5写出广义表操作的结果：GetTail【GetHead【GetTail【(a,b),(x,y)】=(y)。5.取出广义表 A=(x,(a,b,c,d)中原子 x 的函数是_ head(A)_。7.下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。i7j6v61234674152537897318、设有一个10 阶的对称矩阵 A1010，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组 B 中，A00存入 B

19、0中，则 A85在 B 中（C）位置。A32 B33 C41 D659、假设有 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)和一维数

20、组 B中下标 k 的对应关系。解：对应关系如下：a1,1a2,1A an,1a2,2an,2an,n i(i 1)j 12k j(j 1)i 12n i j 11 i j n第 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树有三种常用的存储结构，即孩子链表法、

21、孩子兄弟链表法和_双亲表示法。4.把一棵树转换为二叉树后，这棵二叉树的形态是 A。A.唯一的 B.有多种C.有多种，但根结点都没有左孩子 D.有多种，但根结点都没有右孩子5、若一棵二叉树中度为2 的结点数是 10，则叶子结点数为 11个。10、3 个结点可构成 2 棵不同形态的树。5 棵不同形态的二叉树。6.深度为 6（根的层次为 1）的二叉树至多有（）结点。7.将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为 1。编号为 49 的结点 X 的双亲编号为（）242523无法确定8.设一棵完全二叉树具有1000 个结点，则此完全二叉树有 500个叶子结

22、点；有 499个度为 2 的结点，有 1个度为 1 的结点。643231639.一棵具有个结点的完全二叉树，它的深度为 9。10、已知完全二叉树的第8 层有 8 个结点，则其叶子结点数是68。11.在完全的二叉树中，若一个结点没有 A，则它必定是叶结点。A.左子结点 B.右子结点 C.左子结点或者没有右子结点 D.兄弟12.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是(.A )的二叉树。A.空或只有一个结点 C.任一结点无左孩子B.高度等于其结点数D.任一结点无右孩子13.在有 n 个结点的二叉链表中，值为非空的链域的个数为(A )A.n-1 C.n+1B.2n-1D.2n+114.

23、一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为(.B )A.0 C.2B.1D.不确定算法的时间复杂度为(C )A.O(n)C.O(n)2B.O(n)D.O(n+e)316、有 n 个叶子结点的哈夫曼（Huffman）树所具有的结点数为2n-117.判断线索二叉树中某结点指针P 所指结点有左孩子的条件是_P-ltag=1_。18、二叉树在线索化后，仍不能有效求解的问题是（D）。A.先 序 线 索 二 叉 树 中 求 先 序 后 继B.中 序 线 索 二 叉 树 中 求 中 序 后继C.中序线索二叉树中求中序前驱D.后序线索二叉树中求后序后继19、将下图中的树用孩子-兄弟链表来表示。（

24、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-rchi

25、ld;函数功能：在先序线索二叉树中查找某结点的后继。22.给定二叉树的两种遍历序列，分别是：中序遍历序列：DCBGEAHFIJK；后序遍历序列：DCEGBFHKJIA。（1）请画出该树。（2）画出与（1）求得的二叉树对应的森林。23.假设用于通信的电文仅由 8 个字母组成，字母在电文中出现的频率分别为a要求：（1）为这 8 个字母设计哈夫曼编码，并画出哈夫曼树。（2）求该哈夫曼树的带权路径长度。24树的后根遍历方法是：若树非空则（1）依据次后根遍历根的各个子树，m;（2）访问根结点。对下图所示的树，用后根遍历方法进行遍历，请写出遍历所得到的结点访问序列。EAAbcdefghBACADAFAGA

26、HAIJKA25.假设一棵二叉树的先序序列为 EBADCFHGIKJ 和中序序列为 ABCDEFGHIJK。i.ii.请画出该树。画出与（1）求得的二叉树对应的森林。26.已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树及对应的二叉树。dataparent1.计算二叉树的深度的算法Int deepTree(p)以线索链表作为存储结构，写出后序线索树中查找*p 的后序前驱的算法。1A02B13C14D15E26F27G38H39I410J411K512L613M614N715O8第七章 图知识点：基本概念（度、完全图、连通子图、生成树、最小生成树），图的存储（邻接矩阵、邻接表），图

27、的遍历，最小生成树，拓扑排序，最短路径，关键路径1 求最短路径的 DIJKSTRA 算法的时间复杂度为(C )A.O(n)C.O(n)2B.O(n+e)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.46.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B倍。A1/2 B.1 C.2 D.47.已知图的邻接

28、表如下图 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）。(n)(n+e)(n2)(n3)11、若要求一个稀疏图 G 的最小生成树，最好用A算法来求解。A克鲁斯卡尔(Kruskal)B.普里姆(Prim)C迪杰斯特拉（Dijkstra

29、）D.以上均可，没有区别12 设有一个无向图 G=（V，E）和 G=（V，E）如果 G为 G 的生成树，则下面不正确的说法是（）G为 G 的子图G为 G 的边连连通分量G为 G 的极小连通子图且 V=VG为 G 的一个无环子图13 一个有向图 G 中若有弧、和,则在图 G 的拓扑序列中，顶点 vi,vj和vk的相对位置为_i,j,k_。14.有 8 个结点的有向图最多有 56条边。15.用普里姆(Prim)算法求具有 n 个顶点 e 条边的图的最小生成树的时间复杂度为O(n)；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e)。（A）16 用邻接表表示图进行广度优先遍历时，通

30、常是采用来实现算法的。(A)队列 (B).栈 (C).树 (D).图217.用邻接表表示图进行深度优先遍历时，通常是采用 C来实现算法的。A 树 B.队列 C.栈 D.图1、请对下图的无向带权图：（1）写出它的邻接矩阵；（2）写出它的邻接表；（3）设起点为 a，按普里姆算法或克鲁斯卡尔算法求其最小生成树。2.已知图的邻接矩阵，根据算法，分别求从顶点 0 出发按深度和广度优先遍历的结点序列。01解：按深度优先遍历的结点序列是 0134256；按广度优先遍历的11结点序列是 0123465。1011111010010010001001001100110100011011000103.对于下图所示的

31、 AOE 网络，计算各活动弧的 e(ai)和 l(aj)的函数值，各事件（顶点）的 ve(vi)和 vl(vj)函数值，列出各条关键路径。4下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的 n-1 条公路，画出所有可能的方案。19v1162111v266145v633v3求最小生成树，两种方案v518v45.已知某有向图的邻接矩阵如右图所示，要求：（1）确定图中每个顶点的入/出度；（2）画出该图；（3）画出该图的邻接表（4）画出该图的逆邻接表。6利用 Dijkstra 算法求图中从顶点 a 到其他各顶点间的最

32、短路径，写出执行算法过程中各步的状态。第 8 章 查找知识点：折半查找过程，堆概念，二叉排序树，哈希查找，平衡二叉树。1.对有 18 个元素的有序表作二分查找，则查找A3的比较序列的下标依次为(D )A.1，2，3 C.9，5，3B.9，5，2，3D.9，4，2，3 b15a68e429gc42、对表长为900 的索引顺序表进行分块查找，假设每一块的长度均为15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为。3.在表长为的链表中进行线性查找，它的平均查找长度为 ()/。5d312f104.在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是散列查找

33、。（）5在对有 6400 个记录的索引顺序表进行查找，最理想的块长为 .().64 ().100 ()80 ()log264006、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知 A 的左孩子的平衡因子为-1，右孩子的平衡因子为 0，则做（B）型调整以使其平衡。A.LL7、）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找。（1）画出描述折半查找过程的判定树；（2）若查找元素 54，需依次与哪些元素比较（3）若查找元素 90，需依次与哪些元素比较（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。8、设哈希（Hash

34、）表的地址范围为 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)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入

35、完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。(2)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。10在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树，并求出其平均查找长度。11、有一个 40000 项的表,要采用等分区间顺序查找的索引(分块)查找法,问:(1)每块理想长度是多少(2)最理想的块数是多少(3)计算平均查找长度 ASL。(4)若每块长度为 100,计算 ASL。12.下面是将键值为 x 的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。type

36、def 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)&(!su

37、c)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）所得树中删除关键字为3

38、7 的结点之后的二叉排序树。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.设表中元素的初始状态是按键值递增的，分别用堆排

39、序、快速排序、冒泡排序和归并排序方法对其进行（按递增排序），冒泡排序最省时间，快速排序最费时间。4.堆是一个键值序列k1,k2,kn,对 i=1,2,|_n/2_|,满足()kik2ik2i+1kik2i+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,38，46,56,79,84.40,38,46,84,5

40、6,797、设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：初始步长为 4 的希尔（shell）排序一趟的结果是 P A C S Q D F X R H M Y。8.在插入和选择排序中，若初始数据基本正序，则选用快速排序；若初始数据基本反序，则选用插入排序。9.对于堆排序、快速排序和归并排序这三种排序方法进行比较，若只从存储空间考虑，则应首先选取堆排序方法；若只从排序结果的稳定性考虑，则应 选取归并排序方法。10.冒泡排序在最好情况下时间复杂度为O(n)。11.下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关 D.A.直接插入排序B

41、.起泡排序C.快速排序D.直接选择排序（）13从未排序序列中挑选元素，并将其依次插入已排序序列的一端的方法，称为().希尔排序 ().归并排序.插入排序.选择排序（）14若一组记录的排序码为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为().().84,79,56,38,40,46 ().79,46,56,38,40,84().84,79,56,46,40,38 ().84,56,79,40,46,3815、试将关键字序列（503，87，512，61，908，170，897，275，653，462），采用堆排序法排序。（1）调整为一个初始大顶堆，用二叉树形式说明调整过

42、程；（2）简要说明如何从初始堆进行升序排序。16、已知待排序的关键字值为：49,12,33,74,87,65,5,49,55,23,27。；按照希尔排序算法对该数列进行排序，请写出步长因子为5、3、1 的各趟排序结果。17有一组键值 25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大进行排序，请写出每趟的结果，并标明在第一趟排序过程中键值的移动情况。18、按下面要求进行算法设计（1）设计一算法实现带表头的单链中两个相邻结点交换次序的函数（3）利用(1)中的交换函数，设计带表头的单链元素的排序算法，并分析时间复杂度。19.设 S 是长度为 length 的整型数组，试

43、设计一算法满足：（1）删除数组中重复的元素；（2）进行排序。并给出算法的时间复杂度。1、给定权值集合15,03，14,02，06,09,17，构造相应的赫夫曼树，并计算它的带权路径长度。答案：WPL=229.2、假定用于通信的电文仅由 8 个字母 C1，C2，C3，C4，C5，C6，C7，C8 组成，各字母在电文中出现的频率分别为：5,25,3,6,10,11,36,4。试为这 8 个字母设计不等长赫夫曼编码，并给出该电文的总码数。答案：电文总码数为：257。3、请给出下图的二叉链表结构图、中序线索树、先序遍历、中序遍历、后序遍历序列。A AB BD DF F4、设计二叉树的中序（先序）非递归遍历算法。5、设计统计二叉树的深度、叶子结点数、总结点数的递归算法。6、二叉树的性质的灵活运用。C CE E