数据结构练习题--201X级--参考答案

1、选择题：1.1数据结构在计算机内存中的表示是指：A. 数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的矢系1.2 数据的逻辑结构是指：A. 数据所占的存储空间量B. 各数据元素之间的逻辑矢系C. 数据在计算机中顺序或链接的存储方式D. 存储在内存或外存中的数据1 -3在下列的叙述中，正确的是：A 数据的逻辑结构是指数据的各数据项之间的逻辑矢系。B. 数据的物理结构是指数据在计算机内的实际存储形式。C. 在顺序存储结构中，数据元素之间的矢系是显示体现的。D链接存储结构是通过结点的存储位置相邻来体现数据元素之间的矢系。填空题:1.4数据结构主要研究数据的逻辑结构,数据的存储结构，数据

2、的运算二个方面的内容。1.5链接存储的特点是通过附加L亠扌旨针来表示数据元素之间的逻辑矢系。1.6数据结构中讨论的二种经典结构包括线性表L,树，图。1.7数据结构中常用的存储方法有：顺序，链接，索引1，散列。1.8顺序存储结构可以通过位置一隐含表示矢系，链接存储结构通过附加指针来显示表示矢系。1.9算法的特性包括有穷性，确定性，可行性 ，输入和输岀。1.10算法性能分析的两个主要定量评价指标是时间复杂度和空间复杂度。简答题：1.11数据结构研究的三方面内容之间有什么联系和区别？数据结构研究的三方面内容包括：数据的逻辑结构、存储结构和运算。数据的逻辑结构是数学模 型，存储结构是指逻辑结构到存储区

3、域的映射，运算是定义在逻辑结构上，实现在存储结构上。1.12简述数据结构中讨论的三种经典结构的逻辑特征是什么？三种经典结构：线性表、树和图。逻辑特征分别为：(1) 线性表：一对一。有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋 结点和一个后继结点。(2) 树：一对多。有且仅有一个幵始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前 趋结点，可以有若干个后继结点。(3) 图：多对多。可有若干个幵始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个 后继结点。1.13简述各种常用存储方法的基本思想。各种方法的基本思想：顺序存储：逻辑上相邻的数据元素存储在物理位

4、置上相邻的存储单元里。链接存储：通过附加指针域 表示数据元素之间的尖系。索引存储：除了存储数据元素，还要建立附加的索引表来标识数据元素的地址。散列存储：根据尖键 字直接计算出该结点的存储地址，通常称为尖键字地址转换法。选择题：2.1线性表L二(a, aa,an),下列说法正确的是:A. 每个元素都有一个直接前驱和一个直接后继。B. 线性表中至少有一个元素。C. 表中元素的排列顺序必须是由小到大或由大到小。D. 除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继。2.2下面矢于线性表的叙述中，错误的是：A. 线性表若采用顺序存储，必须占用一片连续的存储单元B. 线性表若采

5、用顺序存储，便于进行插入和刪除操作C. 线性表若采用链接存储，不必占用一片连续的存储单元D. 线性表若采用链接存储，便于插入和刪除操作2.3在长度为n的顺序表的第i(1< i< n+1)个位置上插入一个元素，元素的移动次数为:A .n-i+1B .n-i C .i D .i-12.4删除长度为n的顺序表中的第i(1< i< n)个位置上的元素元素的移动次数为:A. n-i+1B. n-i C. i D. i-1整理文档2.5已知一个带头结点单链表A. L=s; s->next=L;C. s=L; s->next=L;L,在表头元素前插入新结点*s的语句为:B

6、. sonext=L->next; L->next=s;D. s->next=L; s=L;2.6已知一个不带头结点单链表的头指针为L.则在表头元素之前插入一个新结点*s的语句为:A. L=s; s->next=L;B. s->next=L; L=s;C. s=L; s->next=L;D. s->next=L; s=L;2.7 已知单链表上一结点的指针为p,则在该结点之后插入新结点*s的正确操作语句为：A. p>next=s; s>next=p->next;B.s->next=p->next; p>next=s;C

7、. p>next=s; p->next=s->next;D. p>next=s->next; p->next=s;2.8 已知单链表上一结点的指针为p,则删除该结点后继的正确操作语句是：A. s= p->next; p=p->next; free(s);B. p=p->next; free(p);C. s= p->next; p->next=s>next; free(s);D. p=p->next; free(p->next);2.9 设一个链表最常用的操作是在表尾插入结点和在表头删除结点，则选用下列哪种存储结

8、构效率最高?A.单链表B.双链表C.单循环链表D.带尾指针的单循环链表2.10线性表的链接存储结构是一种(A.随机存取B顺序存取2.11链表不具备的特点是：A.插入删除不需要移动元素C.可随机访问任一结点 填空题：)存储结构。C.索引存取D.散列存取B. 不必事先估计存储空间D. 所需空间与其长度成正比2.1在单链表L中，指针p所指结点有后继结点的条件是p->next!=NULL。2.2判断带头结点的单链表L为空的条件L->next=NULL。. 2.12顺序表和链表中能实现随机存取的是顺序表 ，插入、刪除操作效率高的是 链表一。2.13对于一个具有n个结点的单链表，已知一个结点的

9、指针P,在其后插入一个新结点的时间复杂度为0(1):若已知一个结点的值为X,在其后插入一个新结点的时间复杂度为_o(n)o2.14顺序表的存储密度大_，链表的存储密度小一。简答题：2.15比较顺序表和链表这两种线性表不同存储结构的特点顺序表存储密度大静态分配随机存取插、刪效率低链表存储密度人存储空间可不连续动态分配顺序存取插、刪效率咼216简述头结点的作用。头结点的作用是使得单链表在表头位置的插、删操作同中间位置的插、删操作完全相同。即使“空表” 与“非空表”的操作统一，也使“表头结点”与其他位置结点的操作完全一致，无须特殊处理。2.17写出单链表存储结构的C语言描述。typedef int

10、DataType;typedef struct Node DataType data; struct Node *n ext;Lin kList;完善程序题：2.18设计一个算法，其功能为：向一个带头结点的有序单链表(从小到大有序)中插入一个元素X,使插入后链表仍然有序。请将代码补充完整。typedef int DataType;typedef struct Node DataType data;；广定义指向该结构类型的指针变量next*/JLinklist;void insert(Linklist *L,DataType x) Linklist *s,*p=L;while(p-ext &am

11、p;& p->next->data<x)；/*P指针后移一步*/；广申请一个新结点空间，将其地址赋给变量s7 s->data=x;；广将卞结点插入到巾结点的后面*/structKI 亠I *p=p->n.“JL s=(L in kList *)malloc(sizeof(L inlie 、s>n ext=p->n ext;、n c /+ o 2.19设计一个函数功能为：在带头结点的单链表中刪除值最小的元素。请将代码补充完整。typedef int DataType;typedef Node广定义结构体类型*/ DataType data; st

12、ruct Node * next;JLinkList;void deleteMin(LinkList *L) LinkList *p=L->next,*q;广首先查找值最小的元素，指针q指向最小元素结点*/q=p;while(p)if( p->data < q->data)q=p;if(!q) return;P=L；厂P指针后移一步，比较单链表中的每一个结点广不存在最小结点（空表）时，直接退出广若存在最小结点/则先找到最小结点的前驱/即*/*q的前驱*/while(p=p->n ext;厂从单链表中删除最小元素结点（指针 q所指结点V/ ;厂释放指针q所指结点的空

13、间7structp=p >n ext;p>n ext!=qp>n ext=q >n ext;free（q）;算法设计题：2.20已知长度为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。分两种情况编写函数：（1）线性表采用顺序存储；（2）线性表采用单链表存储。（1）线性表采用顺序存储#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int LocateElem （SeqList *L, DataType item）int i,

14、j=0;j+；for(i=0;i<=L->last ;i+) if( L->datai >item ) return j;(2) 线性表采用单链表存储 typedef int DataType; typedef struct Node DataType data;struct Node ext;Li nkList;in t locateElem(Li nkList *L,item )DataType Li nkList *p=L-> next;int i=0;while ( p)if( p->data >item) i+;return i ;2.21试

15、写一算法实现对不带头结点的单链表H进行就地（不额外增加空间）逆置typedef int DataType; typedefstruct Node DataType data; struct Node ext;Lin kList;Lin kList * Reverse(Li nkListt)iL-> next=NULL;L=P； P=q；if (!L) return; p=H _>n ext;q=H_>n ext;while(q)q=q_>n ext; p_>n ext= return L;选择题：3.1 设一个栈的输入序列是1，2，3，4、5,则下列序列中，是栈的

16、合法输岀序列的是：A. 5 1 2 3 4B. 45 1 32C. 4 3 2 1 5D. 3 5 2 4 13.2 设有一顺序栈，元素1, 2, 3, 4, 5依次进栈，如果出栈顺序是2,4,3, 5, 1则栈的容量至少是：A.1B. 2C. 3D. 43.3 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3,当入队一个元素，再出队两个元素后，rear和front的值分别为：A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 1填空题：3.4栈和队列都是操作受限的线性表，栈的运算特点是LIFO，队列的运算特点是FIFO-o3.5 若序列a、b、c、d

17、、e按顺序入栈，假设P表示入栈操作，S表示出栈操作，则操作序列PSPPSPSPSS后得到的输出序列为acdeb。3.6 已知一个顺序栈S栈顶指针是top，它的容量为MAXSIZE，则判断栈空的条件为s->top=-1_ ,栈满的条件是 s>top=MAXSIZE1 °3.7 对于队列来说，允许进行刪除的一端称为队头，允许进行插入的一端称为队尾。3.8 某循环队列的容量MAXSIZE =6，队头指针front=3，队尾指针reauO,则该队列有_3_个元素。简答题：3.9 栈上的基本运算有哪些？栈的基本运算有：（1）初始化栈initStack（ s）：构造了一个空栈&

18、; 判栈空empty（S）：若栈s为空栈，返回值为“真”G,否则返回值为“假”（0）。 入栈push（ s, x）：在栈s的顶部插入一个新元素x, x成为新的栈顶元素。 出栈pop（ s）：删除栈s的栈顶元素。（5）读栈顶元素top（ s）:栈顶元素作为结果返回不改变栈的状态。3.10循环顺序队列的存储结构图示及C语言描述？循环顺序队列图示:rearfrontC语言描述：#define MAXSIZE 1024typedef int DataType;typedef struct DataType dataMAXSIZE; int rear, front;JSeQueue;SeQueue *s

19、q;3.11简述栈和队列有哪些联系与区别？栈和队列都是运算运算受限的线性表，逻辑结构相同；都可以顺序存储和链接存储，存储结构也相同；插入和刪除运算都限制在线性表的表端完成，且不需要查找运算。二者差别主要体现在运算的限制不同：栈是后进先出（LIFO ）的线性表，限制它的插入和删除操作仅 在表的一端进行。队列是先进先出（FIFO ）的线性表，只允许在表的一端进行插入，而在表的另一端 进行删除。算法设计题：3.12通常称正读和反读都相同的字符序列为“回文”，例如，“abcdeedcba °、“abcdcba “是回文。若字符序列存储在一个单链表中，编写算法判断此字符序列是否为回文。（提示：

20、将一半字符先依次进栈）#defi ne maxsize 100typedef char datatype 1;typedef structdatatype 1 datamaxsize;int top; seqstack;typedef int datatype;typedef struct node datatype data; struct node F ext; Lin klist;Duiche n（Li nklist *head）int i=1;Li nklist *p;seqstack *s;s=i nitSeqStack（）;选择题：5.15.25.3p= head->n ex

21、t ;n=0;while(p) n+; p=p->n ext; p=head->n ext; while(i<=n/2)push(s, p->data); i+;if (n %2!=0) p=p-> next;while(p&&p->data=pop(s) p=p->n ext;if (p) return 0 else return 1;设数据结构D-S可以用二元组表示为D-S=(D , S)七S,其中:r=A，B，A，C，B，D，则数据结构 D-S 是： A.线性结构B.树形结构C.图形结构D 集合树最适合用来表示：A.有序数据元素B

22、.无序数据元素C.元素之间具有分支层次矢系的数据有矢二叉树下列说法正确的是:A二叉树是度为2的有序树D 元素之间无联系的数据B.二叉树中结点的度可以小于25.4C 二叉树中李少有一个结占的廓为 深度为10的完全二叉树，第A.15B .16C. 4D .325.5设一棵树的度为4,其中度为1、23的结点个数分别为6、3 V、1，则这棵树中叶子结点的个5.6数为：A .8B. 9对于二叉树来油，A . 2mC. 10D. 11第i层上最多包含的结点个数为：C. 2B. 2i + 1D.2iD 二叉树中任何一个结点的度都为23层上的的结点数是：5.75.8A前序序列B中序序列C后序序列D 层序序列设

23、森林F中有三棵树，第一，第二，第三棵树的结点个数分别为Mi, M2和M3。与森林F对应的二叉树的后根遍历序列等同于与该树对应的二叉树的哪种序列?树根结点的右子树上的结点个数是:B. Mi+M 2C. MaD . M2+M 3填空题：5.9 二叉树具有10个度为2的结点、5个度为1的结点，则度为0的结点个数是11 o 5.10包含n个结点的二叉树，高度最大为n，高度最小为logzn 1 o5.11某完全二叉树共有200个结点，则该二叉树中有1个度为1的结点。5.12 一棵高度为10的满二叉树中的结点总数为210-1个，其中叶子结点数为29 O5.13某完全二叉树结点按层顺序编号(根结点的编号是1

24、)，若21号结点有左孩子结点，则它的左孩子结点的编号为42o5.14深度为k的完全二叉树至少有5.15 n个结点的线索二叉树上含有2k1 个结点，至多有 2k-1个结点n+1条线索。简答题：5.17找出满足下面条件的二叉树：(1) 前序遍历与中序遍历结果相同：只有右分支的单分支二叉树(2) 前序遍历和后序遍历结果相同：只有一个根结点的二叉树(3) 中序遍历和后序遍历结果相同：只有左分支的单分支二叉树5.18 棵二叉树的中序、后序遍历序列分别为： GLDHBEIACJFK和LGHDIEBJKFCA，请回答：(1) 画岀二叉树逻辑结构的图示。画岀此二叉树的二叉链表存储结构的图示并给岀C画岀中序线索

25、二叉链表存储结构图示并给出 C语言描(2) 语言描述。(3) 画岀上题中二叉树的中序线索二叉树。(4)述。(2)二叉链表存储结构的图示及C语言描述:rootAActypedef char DataType; typedef struct Node DataType data;struct Node*lchild,*rchild; JBiTree;DAFj|±i H /A1AAJAAKAiL1电AL(3)中序线索二叉树:A INULL(4)中序线索二叉链表的图示及C语言描述:电I J AL IA 41H 1B01C041typedef char DataType; typedef st

26、ruct Node DataType data;struct Node *lchild,*rchild;int ltag3rtag;JBiThrTree;5.19设有森林如图5.31所示，请回答：(1) 画出与该森林对应的二叉树的逻辑结构图示(2) 写岀该二叉树的前序中序后序遍历序列(3) 画岀该二叉树的中序线索二叉链表的图示并给出D FC图 5.31/1 DO(1)二叉树的逻辑结构图示:c语言描述:typedef char DataType; typedef struct Node DataType data;struct Node *lchild,*rchild; int ltag,rta

27、g;JBiThrTree;5.20设有森林B=(D,S),D二A,B,C,D,E,F,G,H,l,J,rSr 二vA,B,vA,C,vA，D，vB，E，vC，F，vG,H，vG,v|,J画出与森林对应的二叉树的逻辑结构图示。请回答:(2)写岀此二叉树的前序、中序、后序遍历序列。(3)画岀此一叉树的一义链表存储结构的图不并给岀 描述。C语言整理文档(1)与森林对应的二叉树的逻辑结构图示:(2)前序遍历序列：ABECFDGHIJ ,中序遍历序 列：EBFCDAHJIG后序遍历 序列：EFDCBJIHGAC语言描述：L忙门芮hII /J ；|/' IF'A7"! I / I

28、 A5.21请画出5.32中的各二叉树話金的森林。typedef char DataType;typedef struct Node DataType data;struct Node *lchild,*rchild;(a)(b)图 5.32(Fo何 (E(a)(b)5.22假设用于通信的电文由字符集(1 )哈夫曼树:100(3)哈夫曼树的带权路径长度WPL :(c)<d)a, b, c,d, e, f, g, h中的字母构成，这8个字母在电文中岀现的概率分别为0.07, 0.19,0.02, 0.06 0.32, 0.03 0.21, 0.10,试为这8个字母进行哈夫曼编码。请回答：(

29、1 )画出哈夫曼树(按根点权值左小右大的原则)。(2 )写出依此哈夫曼树对各个字母的哈夫曼编码。(3) 求出此哈夫曼树的带权路径长度WPL。2)各字母的哈夫曼编码:a:1010b:00 c:10000 d:1001 e:11 f:10001g：oih:1011WPLWjlji 1=0.07 X 4+0.19 X 2+0.02 X 5+0.06 X 4+0.32 X 2+0.03 X 5+0.21 X 2+0.10 X 4=2.61 完善程序题：5.23设计一彳、算法，其功能为：利用中序线索求结点的中序后继。请将代码补充完整。typedef char DataType;typedef struc

30、t Node DataType data;struct Node *lchild,;int ltag,rtag;BiTh 订 ree;BiThrTree * lnOrderNext(BiThrTree *p)/* 求中序后继 */if() p=p->rchild;/* 若结点 *p 无右孩子 */else广若结点巾有右孩子*/while(p->ltag=0)return*rchildJ>rtag=：1 p=p>rchild p=p>lchild选择题：6.1 n个顶点的有向图中有向边的数目最多为：A. n-1B. nC. n(n-1)/2D.n(n-1)6.2 下

31、面哪一方法可以判断出一个有向图是否有环(回路)：A.深度优先遍历B.求最短路径C.拓扑排序D.广度优先遍历填空题：6.3 某无向图的邻接矩阵如下所示，则该图中有9条边，有 6个顶点0 10 10 110 10 11010001A= 1 0 0 0 1 10101001111006.4 在无向图的邻接矩阵存储结构中，第 i列上非零元素的个数是顶点Vi的 度，而在有向图的邻接矩阵中，第i列上非零元素的个数是顶点“的入度。6.5 若无向图采用邻接矩阵存储，则存储空间的大小只与图中顶点一的个数有矢。6.6 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为n和。简答题：6.7 设一个

32、有向图为 G=(V,E)，其中 V= v i,V2,V3,V4 » E=< v 2,Vi>,v V2,V3>,< v 4,Vi>,< v i,V4>,v V4,V2> » 请回 答下列各问：(1) 画岀该有向图，求岀每个顶点的入度和岀度。(2) 画岀该图的邻接矩阵存储结构图示。(3)(4)对(2)中的邻接矩阵，给出从顶点V2出发的DFS序列和DFS生成树。对(2)中的邻接矩阵，给出从顶点V2出发的BFS序列和BFS生成树。V2 V3(1) 有向图：顶点S的入度是2，出度是1 ;顶点V2的入度是1，出度是2;顶点V3的入度是 1

33、，出度是0;顶点V4的入度是 1，出度是2。(2) 邻接矩阵存储结构图示:图 6.45图 6.446.1图6.45的所有可能的最小生成树:选择题：在对n个元素进行起泡排序的过7.1 程中，32A . O(n3)B. 0(")7.2堆排序属于下列哪类排序？A.插入B.交换最好情况下的时间复杂度为：C. 0(n)D . 0(1)C.归并D.选择73下列哪组序列是堆:A. (79,40,46,56,38,84)B. (84,56,79,46,38,40)C. (40,38,46,56,79,84)D. (84,38,46,40,56,79)7.47.5就平均性能而言，目前最好的内排序方法A

34、.冒泡是：B.希尔插入7.6在下面的排序方法中，平均时间复杂度为C.交换D.快速0(/)且是不稳定的排序方法为:A.快速排序B.直接插入排序C.直接选择排序D.起泡排序下列排序算法中，哪种排序方法在一趟结束后不一定能选出一个元素放在其最终位置 卜°A.简单选择排序丄 B.冒泡排序C.归并排序D.堆排序填空题：7.7 每次从无序子表中取岀一个元素5把它插入到有序子表中的适当位置，此种排序方法叫做插入排序。7.8 快速排序的平均时间复杂度是0( n Iog2n)_，平均空间复杂度是O (如门)7.9 设记录的排序码序列为：(49, 38，65，97，76,13, 27)，若采用快速排序，

35、则第一趟划分的结果为27,38,134976,97,65。7.10快速排序、堆排序和归并排序的平均时间复杂度都是° (nlogzn),但其中稳定的排序方法只有归并7-11在直接插入排序、希尔排序、起泡排序、快速排序中稳定的排序方法有直接插入 和 起泡。7.12在堆排序、快速排序和归并排序中，若只从存储空间考虑、则首先应选取堆排序方法，其次选取快速排序方法。7.13直接插入排序和简单选择排序两种排序算法中，矢键字的比较次数与初始序列无尖的是简单选择。简答题：7.14常用的实现排序的方法有几大类?它们的实现思想是什么？使得插入后插入排序的基本思想是：将一个待排序记录按照排序码的大小插入到

36、一个有序序列的适当位置，的序列仍然有序，直到所有记录全部插入到有序序列中。交换排序的基本思想是：两两比较待排序记录的排序码，不符合排列顺序则交换记录，直到所有记录的排序码都符合排序要求。选择排序的基本思想是：每一次从待排序记录序列中选取一个排序码最小（或最大）的记录，放在待排序记录序列的最前面（或最后面），重复此过程，直到所有的记录按排序码排好序。归并排序的基本思想是：利用“归并”技术实现的排序方法。所谓归并就是将两个或多个有序表合并成一个有序表的过程。如果是将两个有序表合并成一个有序表称为二路归并，二路归并是最简单和最常用的。基数排序的基本思想是：基数排序是基于排序码的结构分解，然后通过“分

37、配”和“收集”方法实现的排序。7.15 给定排序码的序列（39、33、13、15、58、41、27、46、23。请回答：（1）采用希尔（Shell）排序（步长分别为5,3,1 ），写出各趟排序结果。（2 ）采用快速排序的方法进行排序，写出各趟排序结果。（1 ）希尔排序：393313155841274623（初始）392713155841334623（1趟希尔排序结152713334623395841（2趟希尔排序结131523273339414658（3趟希尔排序结（2快速排序：、r-r-1 、393313155841274623（初始）2333131527394146 58（1层划分结果）1

38、5 13 23 33 27 39 41 46 58（2层划分结果）13 15 23 27 33 39 41 46 58（3层划分结果）7.16判断F列序列是否为堆？如果不是，则把它们调整成堆。(1 )( 503, 87，512, 61，908，170，896, 275, 653，462)(2) ( 12, 70, 33，65，24，48，92，86, 33, 55)(3) ( 100, 55, 97, 30, 23,86,60, 8, 12)(4) ( 5,56, 18, 40, 38, 27, 58, 30, 78, 28, 98)(1) 不是堆，调整为大根堆：(908,653, 896,

39、503, 462, 170, 512, 275, 61, 87)(2) 不是堆，调整为小根堆：(12, 24, 33, 33, 55, 48, 92, 86, 65, 70)(3) 是大根堆(4) 不是堆，调整为小根堆:(5, 28, 18, 30, 38, 27, 58, 40, 78, 56, 98)7.17设待排序文件各个记录的排序码序列为：19、23、2、67、39、91、43、25,逬行堆排序，请回答：（1 ）画出初始建成的大根堆对应的完全二叉树°（2）写出初始大根堆序列。（3 ）画出第一趟堆排序后对应的完全二叉树。(1)初始建成的大根堆(3)第一趟堆排序后对应的完全二叉树

40、91(2)初始大根堆序列:6791 67 43 25 39 2 19 23完善程序题：7.18设计一个算法，其功能为：利用直接插入排序的方法，将一组存储在带头结点的单链表中的记录递增排序。请将 算法补充完整。typedef struct nodeint key;DataType other;厂定义单链表的指针域next */ LinkList;void insertSort(LinkList *L) LinkList *p,*q,*s;p=L->next; L->next=NULL; while(p)q=L；while(q->next && ) 厂指针q从头开

41、始査找，寻找合适的插入位置*/s=p->n ext;广将指针P所指的结点插入到q之后*/P=s；struct node 11q>n ext->data<p->dataq=q>n ext; p>n ext=q->n ext;q>n ext=p;选择题：8.1 对线性表进行二分查找时，要求线性表必须：A.以顺序方式存储 B.以顺序方式存储，且按矢键字有序C.以链接方式存储D以链接方式存储，且按矢键字有序8.2 顺序查找法适合于存储结构为()的线性表。A.散列存储B.顺序存储或链接存储C.压缩存储D 索引存储8.3 若结点的存储地址与其尖键字之间存在某种函数矢系，则称这种存储结构为：A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构8.4 下面矢于散列查找的说法正确的是：A. 在采用线性探测法处理冲突的散列表中，同义词在表中一定相邻；B. 除留余数法是所有散列函数中最好的；C. 在散列表中逬行查找，“比较”次数的多少与冲突有尖；D. 散列函数构造的越复杂越好，因为这样随机性好，冲突小。填空题：8.5 对于n个元