数据结构习题

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

2、+;解：因为x+ 共执行了n-1+n-2+ 1= n(n-1)/2 ，所以执行时间为O（ n2）.4. 计算下面程序段的时间复杂度。x=n;y=0;/n 是不小于1 的常数while (x>=(y+1)*(y+1)y+;1. 解： 设执行了 t(n) 次，则 (t(n)+1) 2<=n ，推出 t(n)<=n 1/2-1。所以时间复杂度为5.分析下面各程序段的时间复杂度（ 1） O(n*m)(2) O(log3n)O（ n1/2） .1） for (i=0;i<n; i+)for (j=0; j<m; j+)Aij=0;2）i=1;while(i<=n)i=

3、i*3;6. 在n 个结点的顺序表中，算法的时间复杂度是O（1）的操作是：A（ A ）访问第 i 个结点（ 1 i n）和求第（ B ）在第 i 个结点后插入一个新结点（i 个结点的直接前驱（ 1 i n）2i n）（ C）删除第 i 个结点（ 1 i n）（ D ）将 n 个结点从小到大排序精选文库第二章线性表知识点：顺序表、单链表、双向链表（插入、查找、删除运算）循环链表(单双向 )特点，考点：基本操作、复杂度、特点、算法应用1. 在一个单链表中，若p 所指结点是q 所指结点的前驱结点，则删除结点q 的正确操作是（B）A. p->next=qB. p->next=q->n

4、extC. 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 ）

5、。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-&g

6、t;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-&

7、gt;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),在给

8、定值为 x 的结点后插入一个新结点的时间复杂度为O(n) _ 。8.在顺序表中访问任意一结点的时间复杂度均为O(1)，因此顺序表也称为随机存取的数据结构。（A）1.在 n 个结点的顺序表中，算法的时间复杂度是O（ 1）的操作是：（ E）访问第 i 个结点（ 1 i n）和求第i 个结点的直接前驱（2i n）（ F）在第 i 个结点后插入一个新结点（1 i n）（ G）删除第 i 个结点（ 1 i n）（ H ）将 n 个结点从小到大排序9、线性链表不具有的特点是（A）。A 随机访问B不必事先估计所需存储空间大小C插入与删除时不必移动元素D所需空间与线性表长度成正比10.若某链表最常用的操作是在

9、最后一个结点之后插入一个结点和删除最后一个结点，则采用 ( C)存储方式最节省时间。A. 单链表B. 双链表2精选文库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 个元素的顺序表中插入一个新元素并保持原来顺序不变，

10、平均要移动（ B ）个元素A.8B.63.5C.63D. 715. 对于长度为n 的顺序表执行删除操作，则其结点的移动次数（C）A. 最少为 0，最多为nB.最少为 1，最多为nC. 最少为 0，最多为n-1D.最少为 1，最多为n-116. 线性表的长度是线性表所占用的存储空间的大小。 ( F )17. 双循环链表中，任意一结点的后继指针均指向其逻辑后继。( T )18、线性表在B情况下适用于使用链式结构实现。、需经常修改中的结点值、需不断对进行删除插入、中含有大量的结点、中结点结构复杂19 若某线性表中最常用的操作是取第i个元素和找第i 个元素的前趋元素，则采用（）存储方式最节省时间。单链

11、表双链表单向循环顺序表1. 假设线性表 L=(a1,a2, ,an)用带头结点的单链表存储表示，试编写算法对其实现就地逆置， 即利用原链表中每一个结点存储空间， 使得元素的逻辑次序改变为 (an, , a2,a1)。2 试编写算法，以统计带头结点单链表的元素个数。3. 设某单链表的结点结构为data |next,试编写算法判断该链表的元素是否是递增的。4.已知单链表L 是一个递增有序表，试写一高效算法，删除表中值大于min 且小于 max的结点 (若表中有这样的结点 )，同时释放被删结点的空间， 这里 min 和 max 是两个给定的参数。请分析你的算法的时间复杂度。3精选文库第3章栈和队列知

12、识点：栈、循环队列考点：出入栈操作、栈和队列特点、循环队列操作（元素个数、队头队尾指针）、应用1一个栈的入栈序列是1、 2、 3、4，若第二个出栈的元素是4，则最后出栈的元素可能是或。2.一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是(B)A.23415B.54132C.23145D.154323.在对链队列作出队操作时，不会改变front 指针的值。 (T)4.若一个栈的输入序列为123 n，其输出序列的第一个元素为n，则其输出序列的每个元素ai 一定满足ai=n-i+1(i=1,2.,n)(T)5. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶, 不允

13、许插入和删除运算的一端称为栈底。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 , 栈空的条件是_.如果栈不为空，则退栈操作

14、为p=ls； _ Ls= =NULL、 ls=ls->link._ ； free(p); 。10. 如果以链表作为栈的存储结构，则退栈操作时（） 必须判别栈是否满 对栈不作任何判别 必须判别栈是否空 判别栈元素的类型11. 判定一个栈 ST （最多元素为 m0）为空的条件是 B ST->top<>0 ST->top=0 ST->top<>m0 ST->top=m0（ D ） 12数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为（） r f;（）（n f r） % n;（

15、） n r f;（）（ n r f） % n13. 判定一个队列 QU（最多元素为 m0）为满队列的条件是 AA QU->rear QU->front = = m0B QU->rear QU->front 1= = m0C QU->front = = QU->rearD QU->front = = QU->rear+14精选文库14. 设循环队列的容量为 40 （序号从 0 到 39），现经过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？答： L=

16、（ 4019 11） % 40=8 L= （40 11 19） % 40=3215、假设为循环队列分配的向量空间为Q20 ，若队列的长度和队头指针值分别为13 和 17，则当前尾指针的值为 _10_。16. 设数组 Data0.m 作为循环队列 SQ的存储空间， front 为队头指针， rear 为队尾指针，则执行出队操作的语句为（）front=front+1front=(front+1)%mrear=(rear+1)%mfront=(front+1)%(m+1)12. 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A）A队列B栈C线性表D有序表13. 用邻接表表示图进行深度优先遍历

17、时，通常是采用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);答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。5精选文库第4章串知识点：定义、串的基本操作、根据KMP 算法原理，分别求出它们的Next 函数值作业1. 串是任意有限个（）符号构成的序列符

18、号构成的集合字符构成的序列字符构成的集合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

19、开始的 j 个字符组成的子串， len(s)返回串 s 的长度，则 con(subs(s1, 2, len(s2),subs(s1, len(s2), 2)的结果串是BCDEFEF 。8.设串 sl= Data Structures withJava ,s2= ，则it子串定位函数index(s1,s2)的值为（ D）A15B 16C 17D 189.令 t= abcaabcab，根据KMP 算法原理，分别求出它们的Next 函数值。i123456789串 tabcaabcabNext(i)6精选文库第 5 章 数组和广义表知识点：二维数组的存储、特殊矩阵、广义表作业 P31-331. 假设有

20、二维数组 A 6× 8，每个元素用相邻的 6 个字节存储， 存储器按字节编址。已知 A 的起始存储位置（基地址）为 1000，则数组 A 的体积（存储量）为 288 ；末尾元素 A 57 的第一个字节地址为1282；若按行存储时，元素 A 14 的第一个字节地址为1072；若按列存储时，元素A 47 的第一个字节地址为1276。（ ）2.假设有 60 行 70 列的二维数组a1 60, 170 以列序为主序顺序存储，其基地址为 1000，每个元素占2 个存储单元， 那么第 32 行第 58 列的元素 a32,58 的存储地址为 ( )。（无第 0 行第 0 列元素）( ) 4454(

21、 ) 6904( )7902( )答案 A, B, C 均不对3数组 A的每个元素占 5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A ，的地址为 (A)A. 1140B. 1145C. 1120D. 11254. 二维数组 A 15 20采用按行为主序的存储方式，每个元素占4 个存储单元，若A 0 0的存储地址为 300，则 A 1010的地址为（D ） A.700 B.1120C.1180 D.11405写出广义表操作的结果：GetTail 【 GetHead【 GetTail 【 (a,b),(x,y) 】 =(y)。5.取出广义表A=(x,(a,b,c,d

22、) 中原子 x 的函数是 _ head(A)_ 。7. 下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。ijv7661472183594276537318、设有一个10 阶的对称矩阵A1010 ，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B 中， A00 存入 B0 中，则 A85 在 B 中（C ）位置。A32B33C41D659、假设有 100 行 200 列的二维数组a100200 以列序为主序顺序存储，其基地址为10000，每个元素占2 个存储单元，那么第 45 行第 67 列的元素 a4466 的存储地址为23288。10、已知广义表L=（ a）， b），（）

23、，d），（ e， f ），7精选文库（ 1）写出广义表 L 的头、尾；（ 2）计算 L 的深度；（ 3）画出 L 的头尾链表存储结构图。11. 设矩阵 A 是一个对称矩阵， 为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组 B 中（注： B 下标从 0开始），求矩阵中任一元素ai,j (i j) 和一维数组 B 中下标 k 的对应关系。a1,1Aa2,1a2,2an,1an ,2an ,n解：对应关系如下：i ( i1 )1nij1jk2j (j 1 )11ijni28精选文库第6章二叉树知识点：树、二叉树（完全二叉树）、森林基本概念（度、 ），存储结构，遍历，转换，线索1、设

24、F 是一个森林， B 是由 F 转换得到的二叉树，F 中有 n 个非叶结点，则B 中右指针域为空的结点有（C）个。A n-1B nC n+1D n+22已知一棵度为3 的树有 2 个度为 1 的结点， 3 个度为 2 的结点， 4 个度为 3 的结点，则该树中有 _12_ 个叶子的结点。3树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和_双亲表示法。4. 把一棵树转换为二叉树后，这棵二叉树的形态是A。A. 唯一的B. 有多种C. 有多种，但根结点都没有左孩子D. 有多种，但根结点都没有右孩子5、若一棵二叉树中度为2 的结点数是10，则叶子结点数为11个。10、 3 个结点可构成2 棵不同

25、形态的树。5 棵不同形态的二叉树。6. 深度为 6（根的层次为1）的二叉树至多有（ ）结点。643231637.将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49 的结点 X 的双亲编号为（） 24 25 23无法确定8.设一棵完全二叉树具有1000 个结点， 则此完全二叉树有500个叶子结点； 有499个度为 2 的结点，有1个度为 1 的结点。9.一棵具有个结点的完全二叉树，它的深度为9。10、已知完全二叉树的第8 层有 8 个结点，则其叶子结点数是68。11. 在完全的二叉树中，若一个结点没有A，则它必定是叶结点。A. 左子结点B.

26、 右子结点C. 左子结点或者没有右子结点D. 兄弟12.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是(.A)的二叉树。A. 空或只有一个结点B. 高度等于其结点数C. 任一结点无左孩子D. 任一结点无右孩子13.在有 n 个结点的二叉链表中，值为非空的链域的个数为(A)A. n-1B. 2n-1C. n+1D. 2n+114.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为(.B)A.0B.1C. 2D. 不确定15.DFS 算法的时间复杂度为(C)A. O(n)B. O(n 3)9精选文库C. O(n 2)D. O(n+e)16、有 n 个叶子结点的哈夫曼（Huffman

27、）树所具有的结点数为2n-117.判断线索二叉树中某结点指针P 所指结点有左孩子的条件是_P->ltag=1_ 。18、二叉树在线索化后，仍不能有效求解的问题是（D ）。A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C. 中序线索二叉树中求中序前驱D.后序线索二叉树中求后序后继19、将下图中的树用孩子-兄弟链表来表示。（ 1）画出该二叉链表；（ 2）对该二叉链表进行何种遍历方式可实现树的后根遍历？写出后根序列。20. 求出下图的一棵最小生成树。21. 指出下面函数 FS 的功能。其中， p 指向先序线索二叉树的某个结点。 typedef enumLINK ，THERADfl

28、ag;typedef char DataType; typedef struct nodeDataType data;flag ltag，rtag;struct node * lchild， * rchild;BinNode;BinNode * FS(BinNode *p)if(p->ltag=LINK)return p->lchild;10精选文库elsereturn p->rchild;函数功能：在先序线索二叉树中查找某结点的后继。22. 给定二叉树的两种遍历序列，分别是：中序遍历序列：DCBGEAHFIJK ；后序遍历序列： DCEGBFHKJIA 。（1） 请画出该树

29、。（2） 画出与（ 1）求得的二叉树对应的森林。23. 假设用于通信的电文仅由 8 个字母组成，字母在电文中出现的频率分别为abcdefgh0.070.190.020.060.320.030.210.10要求：（1） 为这 8 个字母设计哈夫曼编码，并画出哈夫曼树。（2） 求该哈夫曼树的带权路径长度。24树的后根遍历方法是：若树非空则（1）依据次后根遍历根的各个子树， m;（ 2）访问根结点。对下图所示的树，用后根遍历方法进行遍历，请写出遍历所得到的结点访问序列。ABCDEFGHIJK25. 假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK 。i.请画出该树。

30、ii.画出与（ 1）求得的二叉树对应的森林。26.已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树及对应的二叉树。123456789101112131415dataABCDEFGHIJKLMNOparent01112233445667811精选文库1.计算二叉树的深度的算法Int deepTree(p)/ P为指向二叉树之根If(p=NULL) return t;ElseIf(deepTree(p->Lchild)>deepTree(p->Rchild)Return deepTree(p->Lchild)+1;ElseReturn deepTree(p-&

31、gt;Rchild)+1;2、读程序二叉树以二叉链表作为存储结构，其定义如下：Typedef struct Nodechar data;Struct Node *lc,*rc;/*lc,rc分别指向左，右子树*/BiTNode,*BiTree;Int n=0;二叉树如右图，根的地址为root ，请给出：（ 1） 下列函数的功能（ 2） 调用语句 prek(root,5); 输出结果是什么？Void prek(BiTree T,int k)if(T&&n<k)prek(T->lc,k);Prek(T->rc,k);N+;printf(“ %c->data)

32、;”,T3、编写递归算法，计算二叉树中叶子结点的数目。4设二叉树以二叉链表为存储结构，结点结构为lchild |data |rchild。设计一个算法，求在前根序列中处于第k 个位置的结点Bitreptrsearch(bitreptr t ,int k)if (t!=null)count+;if (count= =k)return (t);else search(t->lchild,k);search(t->rchild,k);5.以线索链表作为存储结构，写出后序线索树中查找*p 的后序前驱的算法。12精选文库13精选文库第七章图知识点：基本概念（度、完全图、连通子图、生成树、最小

33、生成树） ，图的存储（邻接矩阵、邻接表），图的遍历，最小生成树，拓扑排序，最短路径，关键路径1 求最短路径的DIJKSTRA 算法的时间复杂度为(C)A. O(n)B. O(n+e)C. O(n 2)D. O(n × e)2.有向图用邻接矩阵表示后，顶点i 的入度等于邻接矩阵中第i 列的非零元个数。( T)3.有向图的邻接表和逆邻接表中的结点数一定相同。(T)4.图 G 的拓扑序列唯一，则其弧数必为n-1(其中 n 为 G 的顶点数 )。(F)5. 在一个图中，所有顶点的度数之和等于图的边数的C倍。A1/2B.1C.2D.46. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之

34、和的B倍。A1/2B.1C.2D.47. 已知图的邻接表如下图1 所示，根据算法，则从顶点0 出发按深度优先遍历的结点序列是 DA0132B.0231C.0321D.01238有 n 个顶点的强连通有向图G至少有n条弧。9、设有向图有n 个顶点和e 条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（B）。A O（nlog2e）B O（n+e）CO(ne)D O(n2)10、求最短路径的FLOYD算法的时间复杂度为（D ）。A.O(n)B.O(n+e)C.O(n2)D.O(n3)11、若要求一个稀疏图G 的最小生成树，最好用A算法来求解。A 克鲁斯卡尔 (Kruskal)B. 普

35、里姆 (Prim)C迪杰斯特拉（Dijkstra ）D. 以上均可，没有区别12 设有一个无向图G=（V ，E）和 G =（ V ， E）如果 G为 G 的生成树，则下面不正确的说法是（） G为 G 的子图G为 G 的边 连通分量14精选文库 G为 G 的极小连通子图且V =VG为 G 的一个无环子图13 一个有向图G 中若有弧 <v i,vj>、<vj ,vk>和 <v i,vk>, 则在图 G 的拓扑序列中，顶点vi,vj 和 vk的相对位置为 _i,j,k_ 。14.有 8 个结点的有向图最多有56条边。15. 用普里姆 (Prim) 算法求具有 n

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

37、序列是0134256；按广度优先遍历的01111011001001结点序列是 0123465。100010011001101011010000110111000103. 对于下图所示的 AOE 网络，计算各活动弧的 e(ai)和 l(aj) 的函数值，各事件（顶点）的 ve(vi) 和 vl(vj) 函数值，列出各条关键路径。15精选文库4下图表示一个地区的交通网，顶点表示城市， 边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的 n-1 条公路，画出所有可能的方案。v116v2求最小生成树，两种方案2111619v66v333145v518v45.

38、 已知某有向图的邻接矩阵如右图所示，要求：（ 1） 确定图中每个顶点的入 /出度；（ 2） 画出该图；（ 3） 画出该图的邻接表（ 4） 画出该图的逆邻接表。6 利用 Dijkstra 算法求图中从顶点 a 到其他各顶点间的最短路径，写出执行算法过程中各步的状态。b15648ea29cg41012f35d16精选文库第8章查找知识点：折半查找过程，堆概念，二叉排序树，哈希查找，平衡二叉树。1.对有 18 个元素的有序表作二分查找，则查找A 3的比较序列的下标依次为(D)A. 1 ，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，32、对表长为 900 的索引顺序表进行分块查找，假设

39、每一块的长度均为15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为38.5_。_3.在表长为的链表中进行线性查找，它的平均查找长度为( )/。4.在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是散列查找。（） 5在对有6400 个记录的索引顺序表进行查找，最理想的块长为.( ). 64( ). 100( )80( ) log 640026、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A ，并已知 A 的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（ B ）型调整以使其平衡。A. LLB.LRC.RLD.RR7、）假定对有序

40、表： （ 3， 4，5， 7， 24， 30， 42， 54， 63， 72， 87，95）进行折半查找。（ 1） 画出描述折半查找过程的判定树；（ 2） 若查找元素 54，需依次与哪些元素比较？（ 3） 若查找元素 90，需依次与哪些元素比较？（ 4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。8、设哈希（ Hash）表的地址范围为0 15，哈希函数为：H （Key ） Keymod13。Key 为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（ 10，24， 32，17， 31，30， 46，48， 41，65， 49）造出 Hash 表，试回答下列问题：（ 1） 画

41、出哈希表的示意图；（ 2） 若查找关键字 30，需要依次与哪些关键字进行比较？(3)计算填充因子；(4)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。9.已知长度为12 的表：（ Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec ）(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。(2)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。10在一棵空的二叉查找树中依次插入关键字序列为12， 7，1

42、7， 11， 16， 2， 13，9， 21，4，请画出所得到的二叉查找树，并求出其平均查找长度。11、有一个40000 项的表 , 要采用等分区间顺序查找的索引( 分块 ) 查找法 , 问:17精选文库(1) 每块理想长度是多少 ?(2) 最理想的块数是多少 ?(3) 计算平均查找长度 ASL。(4) 若每块长度为 100, 计算 ASL。12.下面是将键值为x 的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。typedef struct pnodeint 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 (x<t->key) 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;switchcase K=Rmid.k