2022年数据结构习题

..精品文本精品文本.精品文本第一章知识点：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)}试按照图论中的画法画出其逻辑结构图。d1d1d2d31d5d4d62、称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和_【1】_的数量级相同。3.计算下面程序段的时间复杂度。x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;解：因为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)<=n1/2-1。所以时间复杂度为O〔n1/2〕.5.分析下面各程序段的时间复杂度〔1〕O(n*m)(2)O(log3n)1〕for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;2〕i=1;while(i<=n)i=i*3;6.在n个结点的顺序表中，算法的时间复杂度是O〔1〕的操作是：A访问第i个结点〔1≤i≤n〕和求第i个结点的直接前驱〔2≤i≤n〕在第i个结点后插入一个新结点〔1≤i≤n〕删除第i个结点〔1≤i≤n〕将n个结点从小到大排序第二章线性表知识点：顺序表、单链表、双向链表〔插入、查找、删除运算〕循环链表(单双向)特点，考点：根本操作、复杂度、特点、算法应用1.在一个单链表中，假设p所指结点是q所指结点的前驱结点，那么删除结点q的正确操作是〔B〕A.p->next=q B.p->next=q->nextC.p=q->next D.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结点的直接后继结点的语句序列是：Dp->next->next->prior=p;p->next=p->next->next;q=p->next;free(q);q=p->next;p->next=p->next->next;p->next->next->prior=p;free(q);q=p->next;p->next->prior=p;p->next=p->next->next;free(q);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〕的操作是：访问第i个结点〔1≤i≤n〕和求第i个结点的直接前驱〔2≤i≤n〕在第i个结点后插入一个新结点〔1≤i≤n〕删除第i个结点〔1≤i≤n〕将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.8B.63.5C.63D.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.一个栈的输入序列为12345，那么以下序列中不可能是栈的输出序列的是(B)A.23415 B.54132C.23145 D.154323.在对链队列作出队操作时，不会改变front指针的值。(T)4.假设一个栈的输入序列为123…n，其输出序列的第一个元素为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〕为空的条件是BＡ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0〔D〕12．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为〔Ａ〕r－f;〔Ｂ〕〔n＋f－r〕%n;〔Ｃ〕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+114.设循环队列的容量为40〔序号从0到39〕，现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？答：①L=〔40＋19－11〕%40=8②L=〔40＋11－19〕%40=3215、假设为循环队列分配的向量空间为Q[20]，假设队列的长度和队头指针值分别为13和17，那么当前尾指针的值为__10____。16.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，那么执行出队操作的语句为〔④〕①front=front+1②front=(front+1)%m③rear=(rear+1)%m④front=(front+1)%(m+1)12.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是〔A〕A．队列

B．栈C．线性表

D．有序表13.用邻接表表示图进行深度优先遍历时，通常是采用C来实现算法的。A．树B.队列C.栈D.图17.简述以下算法的功能〔栈和队列的元素类型均为int〕。voidalgo3(Queue&Q){StackS;intd;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=″DataStructureswithJava″,s2=″it″，那么子串定位函数index(s1,s2)的值为〔D〕A．15

B．16C．17

D．189.令t=‵abcaabcab′，根据KMP算法原理，分别求出它们的Next函数值。i123456789串tabcaabcabNext(i)

第5章数组和广义表知识点：二维数组的存储、特殊矩阵、广义表作业P31-331.假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。A的起始存储位置〔基地址〕为1000，那么数组A的体积〔存储量〕为288；末尾元素A57的第一个字节地址为1282；假设按行存储时，元素A14的第一个字节地址为1072；假设按列存储时，元素A47的第一个字节地址为1276。〔〕2.假设有60行70列的二维数组a[1…60,1…70]以列序为主序顺序存储，其基地址为1000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为(Ｃ)。〔无第0行第0列元素〕(Ａ)．4454(Ｂ)．6904(Ｃ)．7902(Ｄ)．答案A,B,C均不对3．数组A［５］［６］的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，那么元素A［５，５］的地址为(A)A.1140 B.1145C.1120 D.11254.二维数组A［15］［20］采用按行为主序的存储方式，每个元素占4个存储单元，假设A［0］［0］的存储地址为300，那么A［10］［10］的地址为〔D〕A.700 B.1120C.1180 D.11405．写出广义表操作的结果：GetTail【GetHead【GetTail【((a,b),(x,y))】】】===(y)。5.取出广义表A=(x,(a,b,c,d))中原子x的函数是___head(A)____。7.以下各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。ijv7661472183594276537318、设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角局部的元素存入一维数组B[]中，A[0][0]存入B[0]中，那么A[8][5]在B[]中〔C〕位置。A．32B．33C．41D．659、假设有100行200列的二维数组a[100][200]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第45行第67列的元素a[44][66]的存储地址为23288。10、广义表L=〔〔〔〔a〕，b〕〕，〔〔〔〕，d〕，〔e，f〕〕〕，〔1〕写出广义表L的头、尾；〔2〕计算L的深度；〔3〕画出L的头尾链表存储结构图。11.设矩阵A是一个对称矩阵，为了节省存储，将其下三角局部〔如以下列图所示〕按行序存放在一维数组B中〔注：B下标从0开始〕，求矩阵中任一元素ai,j(i≤j)和一维数组B中下标k的对应关系。解：对应关系如下：

第6章二叉树知识点：树、二叉树〔完全二叉树〕、森林根本概念〔度、〕，存储结构，遍历，转换，线索1、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，那么B中右指针域为空的结点有〔C〕个。A．n-1B．nC．n+1D．n+2一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，那么该树中有_____12_______个叶子的结点。树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和_____双亲表示法。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-1 B.2n-1C.n+1 D.2n+114.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为(.B)A.0 B.1C.2 D.不确定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〕对该二叉链表进行何种遍历方式可实现树的后根遍历？写出后根序列。求出以下列图的一棵最小生成树。21.指出下面函数FS的功能。其中，p指向先序线索二叉树的某个结点。

typedefenum{LINK，THERAD}flag;

typedefcharDataType;

typedefstructnode{

DataTypedata;

flagltag，rtag;

structnode*lchild，*rchild;

}BinNode;

BinNode*FS(BinNode*p)

{

if(p->ltag==LINK)

returnp->lchild;

else

returnp->rchild;

}函数功能：在先序线索二叉树中查找某结点的后继。22.给定二叉树的两种遍历序列，分别是：中序遍历序列：DCBGEAHFIJK；后序遍历序列：DCEGBFHKJIA。请画出该树。画出与〔1〕求得的二叉树对应的森林。23.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为abcdefgh0.070.190.020.060.320.030.210.10要求：为这8个字母设计哈夫曼编码，并画出哈夫曼树。求该哈夫曼树的带权路径长度。24．树的后根遍历方法是：假设树非空那么〔1〕依据次后根遍历根的各个子树Ｔ１，Ｔ２，……Ｔm;〔2〕访问根结点。对以下列图所示的树，用后根遍历方法进行遍历，请写出遍历所得到的结点访问序列。AABACADAEAFAGAHAIJKA25.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。画出与〔1〕求得的二叉树对应的森林。26.一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树及对应的二叉树。123456789101112131415dataABCDEFGHIJKLMNOparent0111223344566781.计算二叉树的深度的算法IntdeepTree(p)//P为指向二叉树之根{If(p==NULL)returnt;ElseIf(deepTree(p->Lchild)>deepTree(p->Rchild))ReturndeepTree(p->Lchild)+1;ElseReturndeepTree(p->Rchild)+1;}2、读程序

二叉树以二叉链表作为存储结构，其定义如下：

Typedef

struct

Node{char

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〞,T->data);

}

}

3、编写递归算法，计算二叉树中叶子结点的数目。4．设二叉树以二叉链表为存储结构，结点结构为lchild|data|rchild。设计一个算法，求在前根序列中处于第k个位置的结点Bitreptrsearch(bitreptrt,intk){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(n×e)2.有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的非零元个数。(T)3.有向图的邻接表和逆邻接表中的结点数一定相同。(T)4.图G的拓扑序列唯一，那么其弧数必为n-1(其中n为G的顶点数)。(F)5.在一个图中，所有顶点的度数之和等于图的边数的C倍。A．1/2B.1C.2D.46.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的B倍。A．1/2B.1C.2D.47.图的邻接表如以下列图1所示，根据算法，那么从顶点0出发按深度优先遍历的结点序列是DA．0132B.0231C.0321D.01238．有n个顶点的强连通有向图G至少有n条弧。9、设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为〔B〕。A．O〔nlog2e〕B．O〔n+e〕C．O(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.普里姆(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中假设有弧<vi,vj>、<vj,vk>和<vi,vk>,那么在图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、请对以下列图的无向带权图：写出它的邻接矩阵；写出它的邻接表；设起点为a，按普里姆算法或克鲁斯卡尔算法求其最小生成树。 2.图的邻接矩阵，根据算法，分别求从顶点0出发按深度和广度优先遍历的结点序列。解：按深度优先遍历的结点序列是0134256；按广度优先遍历的结点序列是0123465。3.对于以下列图所示的AOE网络，计算各活动弧的e(ai)和l(aj)的函数值，各事件〔顶点〕的ve(vi)和vl(vj)函数值，列出各条关键路径。v2v4v2v4v1v5v3v616211114336191865求最小生成树，两种方案5.某有向图的邻接矩阵如右图所示，要求：确定图中每个顶点的入/出度；画出该图；画出该图的邻接表画出该图的逆邻接表。6利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。第8章查找知识点：折半查找过程，堆概念，二叉排序树，哈希查找，平衡二叉树。1.对有18个元素的有序表作二分查找，那么查找A［3］的比较序列的下标依次为(D)A.1，2，3 B.9，5，2，3C.9，5，3 D.9，4，2，32、对表长为900的索引顺序表进行分块查找，假设每一块的长度均为15，且以顺序查找确定块，那么在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为__38.5___。3.在表长为ｎ的链表中进行线性查找，它的平均查找长度为(ｎ＋１)/２。4.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。〔Ｃ〕5．在对有6400个记录的索引顺序表进行查找，最理想的块长为.(Ａ).64(Ｂ).100(Ｃ)80(Ｄ)log264006、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并A的左孩子的平衡因子为-1，右孩子的平衡因子为0，那么做〔B〕型调整以使其平衡。

A.LL

B.LR

C.RL

D.RR

7、〕假定对有序表：〔3，4，5，7，24，30，42，54，63，72，87，95〕进行折半查找。画出描述折半查找过程的判定树；假设查找元素54，需依次与哪些元素比较？假设查找元素90，需依次与哪些元素比较？假定每个元素的查找概率相等，求查找成功时的平均查找长度。8、设哈希〔Hash〕表的地址范围为0～15，哈希函数为：H〔Key〕＝Keymod13。Key为关键字，用线性探测法再散列法处理冲突，输入关键字序列：〔10，24，32，17，31，30，46，48，41，65，49〕造出Hash表，试答复以下问题：画出哈希表的示意图；假设查找关键字30，需要依次与哪些关键字进行比较？计算填充因子；假定每个关键字的查找概率相等，求查找成功时的平均查找长度。9.长度为12的表：〔Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec〕试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。10．在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树，并求出其平均查找长度。11、有一个40000项的表,要采用等分区间顺序查找的索引(分块)查找法,问:(1)每块理想长度是多少?(2)最理想的块数是多少?(3)计算平均查找长度ASL。(4)假设每块长度为100,计算ASL。12.下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。typedefstructpnode{intkey;structpnode*left,*right;}pnode;voidsearchinsert(intx,pnodet)/*t为二叉排序树根结点的指针*／{if(){p=malloc(size);p->key=x;p->lchild=null;p->rchild=null;t=p;}elseif(x<t->key)searchinsert(x,t->lchild)else_________;}13．设n个元素的有序表为Ｒ，Ｋ为一个给定的值，二分查找算法如下：intbinsearch(sqlistR,keytypeK){j=1;h=n;suc=0;while((j<=h)&&(!suc)){mid=(j+h)/2;switch{caseK=R[mid].key:suc=1;break;caseK<R[mid].key:h=mid-1;break;caseK>R[mid].key:j=mid+1}}if(suc)return(mid);elsereturn(0);} 将上述算法中划线语句改为：K<R[mid].key:h=mid.〔1〕改动后，算法能否正常工作？请说明原因。〔2〕假设算法不能正常工作，给出一个查找序列和一个出错情况的查找键值；假设能正常工作，请给出一个查找序列和查找某个键值的比较次数。14.从空树起，依次插入关键字37，50，42，18，12，56，30，23，构造一棵二叉排序树。画出该二叉排序树。画出从〔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_|,满足()①ki≤k2i≤k2i+1②ki<k2i+1<k2i③ki≤k2i且ki≤k2i+1(2i+1≤n)④ki≤k2i