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

.第1章选择题：1.1 数据结构在计算机内存中的表示是指：A数据的存储结构 B.数据结构C数据的逻辑结构 D.数据元素之间的关系1.2 数据的逻辑结构是指： A. 数据所占的存储空间量 B各数据元素之间的逻辑关系C. 数据在计算机中顺序或链接的存储方式D. 存储在内存或外存中的数据1.3 在下列的叙述中，正确的是： A数据的逻辑结构是指数据的各数据项之间的逻辑关系。B数据的物理结构是指数据在计算机内的实际存储形式。 C在顺序存储结构中，数据元素之间的关系是显示体现的。D链接存储结构是通过结点的存储位置相邻来体现数据元素之间的关系。填空题：1.4 数据结构主要研究 数据的逻辑结构 ， 数据的存储结构 ， 数据的运算 三个方面的内容。1.5 链接存储的特点是通过附加 指针域 来表示数据元素之间的逻辑关系。1.6 数据结构中讨论的三种经典结构包括： 线性表 ， 树 ， 图 。1.7 数据结构中常用的存储方法有： 顺序 ， 链接 ， 索引 ， 散列 。1.8 顺序存储结构可以通过位置 隐含 表示关系，链接存储结构通过附加指针来 显示 表示关系。1.9 算法的特性包括 有穷性 ， 确定性 ， 可行性 ，输入和输出。1.10 算法性能分析的两个主要定量评价指标是 时间复杂度 和 空间复杂度 。简答题：1.11 数据结构研究的三方面内容之间有什么联系和区别？ 数据结构研究的三方面内容包括: 数据的逻辑结构、存储结构和运算。数据的逻辑结构是数学模型，存储结构是指逻辑结构到存储区域的映射，运算是定义在逻辑结构上，实现在存储结构上。1.12 简述数据结构中讨论的三种经典结构的逻辑特征是什么？三种经典结构：线性表、树和图。逻辑特征分别为：（1）线性表：一对一。有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点。（2）树：一对多。有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点。（3）图：多对多。可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点。1.13 简述各种常用存储方法的基本思想。各种方法的基本思想：顺序存储：逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。链接存储：通过附加指针域表示数据元素之间的关系。索引存储：除了存储数据元素，还要建立附加的索引表来标识数据元素的地址。散列存储：根据关键字直接计算出该结点的存储地址，通常称为关键字地址转换法。第2章选择题：2.1 线性表L=（a1，a2，an），下列说法正确的是：A. 每个元素都有一个直接前驱和一个直接后继。B. 线性表中至少有一个元素。C. 表中元素的排列顺序必须是由小到大或由大到小。D. 除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继。2.2 下面关于线性表的叙述中，错误的是：A线性表若采用顺序存储，必须占用一片连续的存储单元B线性表若采用顺序存储，便于进行插入和删除操作C线性表若采用链接存储，不必占用一片连续的存储单元D线性表若采用链接存储，便于插入和删除操作2.3 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为：A .n-i+1 B .n-i C .i D .i-12.4 删除长度为n的顺序表中的第i(1in)个位置上的元素，元素的移动次数为：A. n-i+1 B. n-i C. i D. i-12.5 已知一个带头结点单链表L，在表头元素前插入新结点 *s的语句为：A. L=s; s-next=L; B. s-next=L-next; L-next=s; C. s=L; s-next=L; 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 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 设一个链表最常用的操作是在表尾插入结点和在表头删除结点，则选用下列哪种存储结构效率最高？A. 单链表B. 双链表 C. 单循环链表D. 带尾指针的单循环链表2.10 线性表的链接存储结构是一种（ ）存储结构。A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取2.11 链表不具备的特点是：A. 插入删除不需要移动元素 B. 不必事先估计存储空间 C. 可随机访问任一结点 D. 所需空间与其长度成正比填空题：2.1 在单链表L中，指针p所指结点有后继结点的条件是 p-next!=NULL 。2.2 判断带头结点的单链表L为空的条件 L-next=NULL。2.12 顺序表和链表中能实现随机存取的是 顺序表 ，插入、删除操作效率高的是 链表 。2.13 对于一个具有n个结点的单链表，已知一个结点的指针p，在其后插入一个新结点的时间复杂度为 O（1） ；若已知一个结点的值为x，在其后插入一个新结点的时间复杂度为 O（n） 。2.14 顺序表的存储密度 大 ，链表的存储密度 小 。 简答题：2.15 比较顺序表和链表这两种线性表不同存储结构的特点。顺序表存储密度大存储空间连续静态分配随机存取插、删效率低链表存储密度大存储空间可不连续动态分配顺序存取插、删效率高2.16 简述头结点的作用。头结点的作用是使得单链表在表头位置的插、删操作同中间位置的插、删操作完全相同。即使“空表”与“非空表”的操作统一，也使“表头结点”与其他位置结点的操作完全一致，无须特殊处理。2.17 写出单链表存储结构的C语言描述。typedef int DataType; typedef struct Node DataType data; struct Node *next; LinkList;完善程序题：2.18 设计一个算法，其功能为：向一个带头结点的有序单链表（从小到大有序）中插入一个元素x，使插入后链表仍然有序。请将代码补充完整。typedef int DataType;typedef struct Node DataType data; ; /*定义指向该结构类型的指针变量next*/Linklist;void insert(Linklist *L,DataType x) Linklist *s,*p=L; while(p-next & p-next-datadata=x; ; ; /*将*s结点插入到*p结点的后面*/struct Node * next; p=p-next; s=(LinkList *)malloc(sizeof(LinkList);s-next=p-next; p-next=s;2.19 设计一个函数功能为：在带头结点的单链表中删除值最小的元素。请将代码补充完整。typedef int DataType;typedef Node /*定义结构体类型*/DataType data;struct Node * next;LinkList;void deleteMin(LinkList *L)LinkList *p=L-next,*q;/*首先查找值最小的元素，指针q指向最小元素结点*/q=p;while(p)if( p-data data)q=p; ; /* p指针后移一步，比较单链表中的每一个结点*/if(!q) return; /*不存在最小结点（空表）时，直接退出*/ p=L; /*若存在最小结点，则先找到最小结点的前驱，即*q的前驱*/while( )p=p-next; ; /*从单链表中删除最小元素结点（指针q所指结点）*/ ; /* 释放指针q所指结点的空间*/structp=p-next;p-next!=qp-next=q-next; 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,j=0; for(i=0;ilast ;i+) if( L-datai item ) j+; return j;（2）线性表采用单链表存储typedef int DataType; typedef struct Node DataType data; struct Node *next; LinkList;int locateElem(LinkList *L, DataType item ) LinkList *p=L-next; int i=0; while ( p ) if( p-data item) i+; return i ;2.21 试写一算法实现对不带头结点的单链表H进行就地（不额外增加空间）逆置。 typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;LinkList * Reverse(LinkList *L)LinkList *p,*q;if (!L) return;p=H-next; q=H-next; L-next=NULL;while(q)q=q-next; p-next= L; L=p; p=q; return L;第3章选择题：3.1 设一个栈的输入序列是 1，2，3，4，5，则下列序列中，是栈的合法输出序列的是：A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 2 1 5 D. 3 5 2 4 1 3.2 设有一顺序栈，元素1，2，3，4，5依次进栈，如果出栈顺序是2，4，3，5，1则栈的容量至少是：A .1 B. 2 C. 3 D. 43.3 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当入队一个元素，再出队两个元素后，rear和front的值分别为： A. 1和 5 B. 2和4 C. 4和2 D. 5和1 填空题：3.4 栈和队列都是操作受限的线性表，栈的运算特点是 LIFO ，队列的运算特点是 FIFO 。3.5 若序列a、b、c、d、e按顺序入栈，假设P表示入栈操作，S表示出栈操作，则操作序列PSPPSPSPSS后得到的输出序列为 acdeb 。3.6 已知一个顺序栈*s，栈顶指针是top，它的容量为MAXSIZE，则判断栈空的条件为 s-top=-1 ，栈满的条件是 s-top=MAXSIZE-1 。3.7 对于队列来说，允许进行删除的一端称为 队头 ，允许进行插入的一端称为 队尾 。3.8 某循环队列的容量MAXSIZE=6，队头指针front=3，队尾指针rear=0，则该队列有_3_个元素。简答题：3.9 栈上的基本运算有哪些？栈的基本运算有：（1）初始化栈 initStack（s）：构造了一个空栈s。（2）判栈空empty（s）：若栈s为空栈，返回值为“真”（1），否则返回值为“假”（0）。（3）入栈push（s，x）：在栈s的顶部插入一个新元素x， x成为新的栈顶元素。（4）出栈pop（s）：删除栈s的栈顶元素。（5）读栈顶元素top（s）：栈顶元素作为结果返回，不改变栈的状态。3.10 循环顺序队列的存储结构图示及C语言描述？C语言描述： 循环顺序队列图示：#define MAXSIZE 1024 typedef int DataType;typedef struct DataType dataMAXSIZE; int rear , front; SeQueue;SeQueue *sq; 3.11 简述栈和队列有哪些联系与区别？栈和队列都是运算运算受限的线性表，逻辑结构相同；都可以顺序存储和链接存储，存储结构也相同；插入和删除运算都限制在线性表的表端完成，且不需要查找运算。二者差别主要体现在运算的限制不同：栈是后进先出（LIFO）的线性表，限制它的插入和删除操作仅在表的一端进行。队列是先进先出（FIFO）的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。算法设计题：3.12 通常称正读和反读都相同的字符序列为“回文”，例如，“abcdeedcba”、 “abcdcba”是回文。若字符序列存储在一个单链表中，编写算法判断此字符序列是否为回文。（提示：将一半字符先依次进栈）#define maxsize 100typedef char datatype1;typedef struct datatype1 datamaxsize; int top; seqstack;typedef int datatype;typedef struct node datatype data; struct node *next; Linklist;Duichen(Linklist *head) int i=1;Linklist *p; seqstack *s;s=initSeqStack();p= head-next;n=0;while(p)n+; p=p-next;p=head-next;while(idata); i+; if (n%2!=0) p=p-next; while(p&p-data=pop(s) p=p-next;if (p) return 0 else return 1;第5章选择题：5.1 设数据结构D-S可以用二元组表示为D-S=(D，S)，rS，其中：D=A，B，C，D，r=，则数据结构D-S是：A线性结构 B树形结构 C图形结构 D集合5.2 树最适合用来表示： A有序数据元素 B.无序数据元素 C元素之间具有分支层次关系的数据 D.元素之间无联系的数据5.3 有关二叉树下列说法正确的是：A二叉树是度为2的有序树B二叉树中结点的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为25.4 深度为10的完全二叉树，第3层上的的结点数是：A .15B .16C . 4D .325.5 设一棵树的度为4，其中度为1、2、3、4的结点个数分别为6、3、2、1，则这棵树中叶子结点的个数为：A .8 B. 9 C. 10 D. 115.6 对于二叉树来说，第i 层上最多包含的结点个数为： A2i - 1 B. 2i + 1 C2i D.2i5.7 树的后根遍历序列等同于与该树对应的二叉树的哪种序列？A. 前序序列 B. 中序序列 C. 后序序列 D. 层序序列5.8 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是： AM1 BM1+M2 CM3 DM2+M3填空题：5.9 二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 11 。5.10 包含n个结点的二叉树，高度最大为 n ，高度最小为。5.11 某完全二叉树共有200个结点，则该二叉树中有 1 个度为1的结点。5.12 一棵高度为10的满二叉树中的结点总数为 210-1 个，其中叶子结点数为 29 。5.13 某完全二叉树结点按层顺序编号（根结点的编号是1），若21号结点有左孩子结点，则它的左孩子结点的编号为_42_。5.14 深度为k的完全二叉树至少有 2k-1 个结点，至多有 2k-1 个结点。5.15 n个结点的线索二叉树上含有 n+1 条线索。简答题：5.16 画出包含三个结点的树和二叉树的所有不同形态。5.17 找出满足下面条件的二叉树：（1）前序遍历与中序遍历结果相同：只有右分支的单分支二叉树（2）前序遍历和后序遍历结果相同：只有一个根结点的二叉树 （3）中序遍历和后序遍历结果相同：只有左分支的单分支二叉树5.18 一棵二叉树的中序、后序遍历序列分别为： G L D H B E I A C J F K和L G H D I E B J K F C A，请回答：（1）画出二叉树逻辑结构的图示。（2）画出此二叉树的二叉链表存储结构的图示并给出C语言描述。（3）画出上题中二叉树的中序线索二叉树。（4）画出中序线索二叉链表存储结构图示并给出C语言描述。（1）二叉树的逻辑结构图示：（2）二叉链表存储结构的图示及C语言描述： typedef char DataType; typedef struct NodeDataType data; struct Node *lchild,*rchild;BiTree;（3）中序线索二叉树：（4）中序线索二叉链表的图示及C语言描述：typedef char DataType; typedef struct NodeDataType data; struct Node *lchild,*rchild; int ltag,rtag;BiThrTree;5.19 设有森林如图5.31所示，请回答：（1）画出与该森林对应的二叉树的逻辑结构图示。（2）写出该二叉树的前序、中序、后序遍历序列。（3）画出该二叉树的中序线索二叉链表的图示并给出C语言描述。图5.31（1）二叉树的逻辑结构图示： （2）前序遍历序列：ABCDFGEH，中序遍历序列：ADGFCBHE 后序遍历序列：GFDCHEBA（3）中序线索二叉链表的图示及C语言描述：typedef char DataType; typedef struct NodeDataType data; struct Node *lchild,*rchild; int ltag,rtag;BiThrTree;5.20 设有森林 B=(D,S), D=A,B,C,D,E,F,G,H,I,J, rSr=, 请回答：（1）画出与森林对应的二叉树的逻辑结构图示。（2）写出此二叉树的前序、中序、后序遍历序列。（3）画出此二叉树的二叉链表存储结构的图示并给出C语言描述。（1）与森林对应的二叉树的逻辑结构图示：（2）前序遍历序列：ABECFDGHIJ，中序遍历序列：EBFCDAHJIG后序遍历序列：EFDCBJIHGA（3）二叉链表存储结构的图示及C语言描述： typedef char DataType; typedef struct NodeDataType data; struct Node *lchild,*rchild;BiTree;5.21 请画出5.32中的各二叉树对应的森林。图5.325.22 假设用于通信的电文由字符集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个字母进行哈夫曼编码。请回答：（1）画出哈夫曼树（按根点权值左小右大的原则）。（2）写出依此哈夫曼树对各个字母的哈夫曼编码。（3）求出此哈夫曼树的带权路径长度WPL。（1）哈夫曼树： （2）各字母的哈夫曼编码： a:1010 b:00 c:10000 d:1001e:11f:10001g:01h:1011（3）哈夫曼树的带权路径长度WPL： =0.074+0.192+0.025+0.064+0.322+0.035+0.212+0.104=2.61完善程序题：5.23 设计一个算法，其功能为：利用中序线索求结点的中序后继。请将代码补充完整。typedef char DataType; typedef struct NodeDataType data; struct Node *lchild, ; int ltag,rtag;BiThrTree;BiThrTree * InOrderNext(BiThrTree *p) /* 求中序后继 */if( ) p=p-rchild; /*若结点*p无右孩子 */ else /*若结点*p有右孩子 */ ; while(p-ltag=0) ; return ;*rchild p-rtag=1p=p-rchildp=p-lchildp第6章选择题：6.1 n个顶点的有向图中有向边的数目最多为：A n-1 B n C n(n-1)/2 D n(n-1)6.2 下面哪一方法可以判断出一个有向图是否有环（回路）：A深度优先遍历 B. 求最短路径 C. 拓扑排序 D. 广度优先遍历填空题：6.3 某无向图的邻接矩阵如下所示，则该图中有 9 条边，有 6 个顶点。6.4 在无向图的邻接矩阵存储结构中，第i列上非零元素的个数是顶点vi的 度 ，而在有向图的邻接矩阵中，第i列上非零元素的个数是顶点vi的 入度 。6.5 若无向图采用邻接矩阵存储，则存储空间的大小只与图中 顶点 的个数有关。6.6 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为 n 和n-1 。简答题：6.7 设一个有向图为G=(V,E)，其中V= v1,v2,v3,v4，E=,，请回答下列各问：（1）画出该有向图，求出每个顶点的入度和出度。（2）画出该图的邻接矩阵存储结构图示。（3）对（2）中的邻接矩阵，给出从顶点v2出发的DFS序列和DFS生成树。（4）对（2）中的邻接矩阵，给出从顶点v2出发的BFS序列和BFS生成树。（1）有向图：顶点v1的入度是2，出度是1；顶点v2的入度是1，出度是2；顶点v3的入度是1，出度是0；顶点v4的入度是1，出度是2。（2）邻接矩阵存储结构图示：（3）DFS序列： v2, v1,v4,v3 （4）BFS序列： v2, v1,v3,v4生成树： 生成树：6.8 对图6.44所示的无向图，依次输入各边：(v1,v2)、(v1,v4)、(v2,v3)、(v3,v4)、(v3,v5)，请回答下列各问：（1）写出该无向图的二元组表示。（2）画出该图的邻接表（头插法建表）存储结构图示。（3）对（2）中的邻接表，给出从顶点v1出发的DFS序列和DFS生成树。（4）对（2）中的邻接表，给出从顶点v1出发的BFS序列和BFS生成树。 （1）无向图的二元组表示：设G=(V,E)，V为顶点集，E为边集，则V=v1,v2,v3,v4,v5E=(v1,v2)、(v1,v4)、(v2,v3)、(v3,v4)、(v3,v5) （2）图的邻接表（头插法建表）存储结构图示：（3）从顶点v1出发： （4）从顶点v1出发：DFS序列：v1,v4,v3,v5,v2 BFS序列：v1,v4,v2,v3,v5 DFS生成树： BFS生成树：画出图6.45中所有可能的最小生成树。 图6.44 图6.456.1 图6.45的所有可能的最小生成树：第7章选择题：7.1 在对n个元素进行起泡排序的过程中，最好情况下的时间复杂度为：A O(n3) B O(n2) C O(n) D O(1) 7.2 堆排序属于下列哪类排序？A. 插入 B. 交换 C. 归并 D. 选择7.3 下列哪组序列是堆： 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.4 下列排序算法中，哪种排序方法在一趟结束后不一定能选出一个元素放在其最终位置上。A. 简单选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序7.5 就平均性能而言，目前最好的内排序方法是：A. 冒泡 B. 希尔插入 C. 交换 D. 快速7.6 在下面的排序方法中，平均时间复杂度为O(n2)且是不稳定的排序方法为： A. 快速排序 B. 直接插入排序 C. 直接选择排序 D. 起泡排序填空题：7.7 每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做 插入 排序。7.8 快速排序的平均时间复杂度是 O（nlog2n） ，平均空间复杂度是O（log2n） 。7.9 设记录的排序码序列为：（49，38，65，97，76，13，27），若采用快速排序，则第一趟划分的结果为 27,38,134976,97,65 。7.10 快速排序、堆排序和归并排序的平均时间复杂度都是 O（nlog2n），但其中稳定的排序方法只有归并 。7.11 在直接插入排序、希尔排序、起泡排序、快速排序中稳定的排序方法有 直接插入 和 起泡 。7.12 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则首先应选取 堆排序 方法，其次选取快速排序方法。7.13 直接插入排序和简单选择排序两种排序算法中，关键字的比较次数与初始序列无关的是 简单选择 。简答题：7.14 常用的实现排序的方法有几大类？它们的实现思想是什么？插入排序的基本思想是：将一个待排序记录按照排序码的大小插入到一个有序序列的适当位置，使得插入后的序列仍然有序，直到所有记录全部插入到有序序列中。交换排序的基本思想是： 两两比较待排序记录的排序码，不符合排列顺序则交换记录，直到所有记录的排序码都符合排序要求。选择排序的基本思想是： 每一次从待排序记录序列中选取一个排序码最小（或最大）的记录，放在待排序记录序列的最前面（或最后面），重复此过程，直到所有的记录按排序码排好序。归并排序的基本思想是： 利用“归并”技术实现的排序方法。所谓归并就是将两个或多个有序表合并成一个有序表的过程。如果是将两个有序表合并成一个有序表称为二路归并，二路归并是最简单和最常用的。基数排序的基本思想是：基数排序是基于排序码的结构分解，然后通过“分配”和“收集”方法实现的排序。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）快速排序：393313155841274623 （初始）23 33131527 39 41 4658 （1层划分结果）1513 23 33 27 39 41 46 58 （2层划分结果）1315 23 27 3339 41 46 58 （3层划分结果）7.16 判断下列序列是否为堆？如果不是，则把它们调整成堆。 （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，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）第一趟堆排序后对应的完全二叉树（2）初始大根堆序列：91 67 43 25 39 2 19 23完善程序题：7.18 设计一个算法，其功能为：利用直接插入排序的方法，将一组存储在带头结点的单链表中的记录递增排序。请将算法补充完整。typedef struct node int 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从头开始查找，寻找合适的插入位置 */ ;s=p-next; ; /* 将指针p所指的结点插入到q之后 */ ;p=s;struct node *next;q-next-datadataq=q-next;p-next=q-next;q-next=p;第8章选择题：8.1 对线性表进行二分查找时，要求线性表必须：A以顺序方式存储 B以顺序方式存储，且按关键字有序C以链接方式存储 D以链接方式存储，且按关键字有序8.2 顺序查找法适合于存储结构为（ ）的线性表。 A散列存储 B顺序存储或链接存储C压缩存储D索引存储8.3 若结点的存储地址与其关键字之间存在某种函数关系，则称这种存储结构为：A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 8.4 下面关于散列查找的说法正确的是：A在采用线性