DS综合练习A.doc

一单项选择题（每小题1分，共10分）1计算机算法必须具备输入、输出和 等5个特性。A可执行性、可移植性和可扩充性 B可行性、确定性和有穷性 C确定性、有穷性和稳定性 D易读性、稳定性和安全性2线性表采用链式存储时，结点的存储地址 。 A必须是不连续的 B连续与否均可C必须是连续的 D和头结点的存储地址相连续3.在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行 。Aq-next=p-next;p-next=q;B p-next=q-next;q=p;Cq-next=p-next;q-next=p;Dp-next=q-next;q-next=p;4设循环队列QN的头尾指针分别为F，R，则进行出队操作需要的指针变化为 。 AF=F+1 BF=（F+1）%N CR=（R+1）%N DR=R+15在一个具有n个顶点的无向图中，要连通全部顶点，至少需要 条边 。 An Bn+1 Cn-1 Dn/26在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) A e B 2e C n2e D n22e7假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅有I和O组成的序列。下面所示的序列中哪些是不合法的？ AIOIIOIOO BIOIOIIOO C IIIOIOIO D IIIOOIOO8 如图所示的4棵二叉树， 是平衡二叉树。A B C D9下面的序列中， _是堆。A 9,8,7,6,4、8,2,1 B 9,8,7,6,5,4,3,7 C 1,5,10,6,7,8,9,2 D 1,2,8,4,3,9,10,510有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值为82的结点时， 次比较后查找成功。 A 1 B 2 C4 D8二、填空题（每空1分，共15 分）1广义表（a,(a,b),d,e,(i,j),k)）的长度是 ， 深度是 。2在一个顺序栈sqm中，栈为空的条件是 ，栈为满的条件是 。 3.高度为h的二叉树至少有 个结点；至多有_个结点。 4无向图的邻接矩阵是一个 矩阵。 5表达式a+b*(c-d)-e/f的逆波兰式为 。6有n个结点的二叉树，已知它有m个叶子结点，则度为2的结点个数是 ，度为1的结点个数是 。 7 采用顺序查找方法查找长度为n的线性表，其等概率下查找成功的平均查找长度(ASL)为 。8设有向图G的邻接矩阵为A，如果图中不存在弧，则Aij的值为 。9二维数组A1020采用以列序为主方式存储，每个元素占一个存储单元，并且A00的存储地址是200，则A612的地址是 。 10在散列存储中，装填因子的值越大，则 的值越小，则 。 三已知一棵二叉树的中序遍历结果为DBHEAFICG，前序遍历结果为ABDEHCFIG。（15分）1 画出该二叉树；2 写出该二叉树的后序遍历；3 画出该二叉树的中序线索二叉树。四对如图所示的有向图，用弗洛伊德算法求出每对顶点间的最短路径及最短路径长度，要求写出其相应的矩阵序列。（15分） 50321 3 4 3 2 2 1五设数据集合d=1，12，5，8，3，10，7，13，9，试完成下列各题：（15分）1依次取d中各数据，构造一棵二叉排序树bt;2. 如何依据此二叉树bt得到d的一个有序序列？3画出在二叉树bt中依次删除“12”、“1”后的树结构。六已知散列表为HT13，散列函数为H（k）=k%13。采用线性探查再散列法解决冲突，对下列关键码序列12，23，45，57，20，03，78，31，15，36分别求出散列地址，并画出相应的散列表，计算等概率下查找成功时的平均查找长度ASL。（15分）七将关键码DEC，FEB，NOV，OCT，JUL，SEP，AUG，APR，MAR，MAY，JUN，JAN依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树，并标明平衡旋转的类型。（15分）一单项选择题（每小题1分，共10分）1计算机算法指的是 。A计算机程序B解决问题的计算方法C解决问题的有限运算序列 D排序算法2在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）之前插入一个新元素时，需要从后向前依次后移 个元素。 An-i Bn-i+1 Cn-i-1 Di3.在一个单链表HL中，若要向表头插入一个由指针P指向的结点，则执行 。A HL=p；p-next=HL ； B p-next=HL ；HL=p； Cp-next=HL；p=HL； D p-next=HL-next；HL=next=p；4数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A58的起始地址为 。 A SA+141 B SA+180 C SA+222 D SA+225 5设一数列的顺序为1、2、3、4、5、6，通过栈结构不可能排成的顺序为 。 A3、2、5、6、4、1 B1、5、4、6、2、3 C2、4、3、5、1、6 D4、5、3、6、2、16按照二叉树的定义，具有3个结点的二叉树有 种不同的形态。 A 3 B 4 C 5 D 67具有n个结点的完全有向图的边数为 。 A n(n-1)/2 B n(n-1) C n2 D n2-18在线索化二叉树中，t所指结点没有左子树的充要条件是 。A t-left=NULL Bt-ltag=1C t-ltag=1 且 t-left=NULL D 以上都不对9具有2000个结点的二叉树，其高度至少为 。 A 9 B 10 C 11 D 1210若给定的关键字集合为20，15，14，18，21，36，40，10，一趟快速排序结束时，关键字的排序为 。A 10、15、14、18、20、36、40、21B 10、15、14、18、20、40、36、21 C 10、15、14、20、18、40、36、21 D 15、10、14、18、20、36、40、21二、填空题（每空1分，共15 分）1 对于一个顺序存储的循环队列Qm，队头、队尾指针分别为f,r，其判空的条件是： ，判满的条件是： 。2广义表（a）,a）的表头是 ，表尾是 。3.设高度为h二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少有_个。 4假设带头结点的单循环链表中头指针L指向链表中最后一个结点，则在第一个结点之前插入指针s所指结点的语句组是 h = L-next; ； 。 5在散列存储中，处理冲突的方法可分为 和 。6已知一个有序表（13，18，24，35，47，50，62，83，90，115，134），当二分查找为90的元素时，查找成功的比较次数为_ _。7 在无权图G的邻接矩阵A中，若（vi,vj）或属于图G的边集，则对应元素Aij等于 否则等于 。8对下面的二叉树，按后序遍历得到的结点序列为 a栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。b栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。c栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。 d栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。g栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。e栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。f9在双向链表中，每个结点都含有两个指针域，一个指向该结点的 结点，另一个指向该结点的 结点。三一棵二叉树的结点数据采用顺序存储结构存储于数组t中，如下图所示。（15分）1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21eafdgcjihb1. 根据其存储结构，画出该二叉树的树形表示；2. 写出按前序、中序、后序遍历该二叉树所得的结点序列；3. 画出该二叉树的后序线索二叉树。四给定下图：（15分）1画出其邻接矩阵和邻接表示意图； 2使用普里姆（Prim）算法构造该图的最小生成树。要求写出集合U、TE和LW的变化过程。假设U=11 42 6 1 53 5 5 3 6 4 265 6 五在地址空间为0-13的散列区域中，对下面关键字序列构造散列表，用链接法处理冲突。（15分）（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）设散列函数为H(k)=i/2 ,其中i为关键字k的第一个字母在字母表中的序号(假设A的序号为1，B的序号为2，Z的序号为26)。1画出散列表；2求出在等概率情况下查找成功的平均查找长度。六假设用于通信的电文仅有8个字母组成，字母在电文中出现的频率分别为：7，19，2，6，32，3，21，10。试画出相应的哈夫曼树（请按照左子树根结点的权小于等于右子树根结点的权的次序构造），并求出这8个字母的哈夫曼编码。（14分）七如图所示的AOE网，求：（16分）642 3 4 4 10 5 719 6 3 5 2 6 1 853 2 3 41 每项活动ai的最早开始时间e(ai)和最迟开始时间l(ai);2 完成此工程最少需要多少天（设弧上权值为天数）；3 哪些是关键活动；4 是否存在某项活动，当其提高速度后能使整个工程缩短工期。一单项选择题（每小题1分，共10分）1计算机算法指的是 。A计算机程序B解决问题的计算方法C解决问题的有限运算序列 D排序算法2在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）之前插入一个新元素时，需要从后向前依次后移 个元素。 An-i Bn-i+1 Cn-i-1 Di3.在一个单链表HL中，若要向表头插入一个由指针P指向的结点，则执行 。A HL=p；p-next=HL ； B p-next=HL ；HL=p； Cp-next=HL；p=HL； D p-next=HL-next；HL=next=p；4数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A58的起始地址为 。 A SA+141 B SA+180 C SA+222 D SA+225 5设一数列的顺序为1、2、3、4、5、6，通过栈结构不可能排成的顺序为 。 A3、2、5、6、4、1 B1、5、4、6、2、3 C2、4、3、5、1、6 D4、5、3、6、2、16按照二叉树的定义，具有3个结点的二叉树有 种不同的形态。 A 3 B 4 C 5 D 67具有n个结点的完全有向图的边数为 。 A n(n-1)/2 B n(n-1) C n2 D n2-18在线索化二叉树中，t所指结点没有左子树的充要条件是 。A t-left=NULL Bt-ltag=1C t-ltag=1 且 t-left=NULL D 以上都不对9具有2000个结点的二叉树，其高度至少为 。 A 9 B 10 C 11 D 1210若给定的关键字集合为20，15，14，18，21，36，40，10，一趟快速排序结束时，关键字的排序为 。A 10、15、14、18、20、36、40、21B 10、15、14、18、20、40、36、21 C 10、15、14、20、18、40、36、21 D 15、10、14、18、20、36、40、21二、填空题（每空1分，共15 分）1 对于一个顺序存储的循环队列Qm，队头、队尾指针分别为f,r，其判空的条件是： ，判满的条件是： 。2广义表（a）,a）的表头是 ，表尾是 。3.设高度为h二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少有_个。 4假设带头结点的单循环链表中头指针L指向链表中最后一个结点，则在第一个结点之前插入指针s所指结点的语句组是 h = L-next; ； 。 5在散列存储中，处理冲突的方法可分为 和 。6已知一个有序表（13，18，24，35，47，50，62，83，90，115，134），当二分查找为90的元素时，查找成功的比较次数为_ _。7 在无权图G的邻接矩阵A中，若（vi,vj）或属于图G的边集，则对应元素Aij等于 否则等于 。8对下面的二叉树，按后序遍历得到的结点序列为 a栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。b栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。c栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。 d栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。g栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。e栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。f9在双向链表中，每个结点都含有两个指针域，一个指向该结点的 结点，另一个指向该结点的 结点。三一棵二叉树的结点数据采用顺序存储结构存储于数组t中，如下图所示。（15分）1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21eafdgcjihb4. 根据其存储结构，画出该二叉树的树形表示；5. 写出按前序、中序、后序遍历该二叉树所得的结点序列；6. 画出该二叉树的后序线索二叉树。四给定下图：（15分）1画出其邻接矩阵和邻接表示意图； 2使用普里姆（Prim）算法构造该图的最小生成树。要求写出集合U、TE和LW的变化过程。假设U=11 42 6 1 53 5 5 3 6 4 265 6 五在地址空间为0-13的散列区域中，对下面关键字序列构造散列表，用链接法处理冲突。（15分）（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）设散列函数为H(k)=i/2 ,其中i为关键字k的第一个字母在字母表中的序号(假设A的序号为1，B的序号为2，Z的序号为26)。1画出散列表；2求出在等概率情况下查找成功的平均查找长度。六假设用于通信的电文仅有8个字母组成，字母在电文中出现的频率分别为：7，19，2，6，32，3，21，10。试画出相应的哈夫曼树（请按照左子树根结点的权小于等于右子树根结点的权的次序构造），并求出这8个字母的哈夫曼编码。（14分）七如图所示的AOE网，求：（16分）642 3 4 4 10 5 719 6 3 5 2 6 1 853 2 3 45 每项活动ai的最早开始时间e(ai)和最迟开始时间l(ai);6 完成此工程最少需要多少天（设弧上权值为天数）；7 哪些是关键活动；8 是否存在某项活动，当其提高速度后能使整个工程缩短工期。一单项选择题（每小题2分，共30分）1下列有关线性表的叙述中，正确的是 。A 线性表中的元素之间是线性关系 B 线性表中至少有一个元素 C 线性表中任何一个元素有且仅有一个直接前趋 D 线性表中任何一个元素有且仅有一个直接后继2线性表采用链式存储时，结点的存储地址 。 A必须是不连续的 B连续与否均可C必须是连续的 D和头结点的存储地址相连续3.数据结构中，与所使用的计算机无关的是数据的 结构。 A 存储 B 物理 C 逻辑 D 逻辑和存储4已知一个数组A，第一个元素地址为100，若每个元素各占3存储单元，则第7个元素的地址为 。 A 114 B 118 C 116 D 120 5一个非空广义表的表头 。 A不可能是子表 B只能是子表 C只能是原子 D可以是子表或原子6线性表最常用的操作是取第i个元素和找第i个元素的直接前驱元素，则采用 存储方式最节省运算时间。 A 顺序表 B 单链表 C 双链表 D 单循环链表7单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度为 。 O(1) B O(m) C O(n) D O(m+n)8若编号为1,2,3,4,5,6的六节车厢依次通过一段栈形轨道，则在出口处不可能得到_的次序。 A 143562 B 456321 C 145326 D 4265319具有2000个结点的二叉树，其高度至少为 。 A 9 B 10 C 11 D 1210二叉树第i (i1)层上至多有 个结点。 A 2i B 2i C2 D 2i-111一棵二叉排序树T，用 方法进行遍历，可以得到各结点键值的递增序列。 A先根遍历 B中根遍历 C层次遍历 D后根遍历 12设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为 。Afront=front+1 B front=(front+1)%(m-1)C front=(front-1)%m D front=(front+1)%m13在有n个结点的树的二叉链表结构中，值为非空的链域的个数为( ) A n-1B 2n-1 C n+1D 2n+114.队列操作的原则是 。 A 先进先出 B 后进先出 C 只能进行插入 D 只能进行删除15从一个长度为n的顺序表中删除第 i个元素(1in)时，需向前移动 个元素。 A n-i B n-i+1 C n-i-1 D i二、填空题（每空2分，共30 分）1 构成抽象数据类型的三个要素为： 、 和 。2若一个栈的输入序列是1,2,n，输出序列的第一个元素是n，则第i个输出元素是 。3.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有_个。 4假设带头结点的单循环链表中头指针L指向链表中最后一个结点，则在第一个结点之前插入指针 s 所指结点的语句组是 h = L-next; ； 。 5已知广义表A=(a),(b),c,(a),(d,e),则该广义表的长度是 ，深度是 。 6判断线索二叉树中某结点指针P所指结点有左孩子的条件是_ _。7对于一个以顺序存储结构实现的循环队Qm，队头、队尾指针分别f、r，其判空的条件是 ，判满的条件是 。 8对下面的二叉树，按后序遍历得到的结点序列为 1栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。3栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。2栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。 6栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。5栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。4栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。栈顶的位置是随着 操作而变化的。9在带头结点的链栈hs中，判空的条件是 ；不带头结点的链栈hs中，判空的条件是 。三、(12分) 阅读下面的算法 LNode * mynote(LNode &L) /L是不带头结点的单链表的头指针 LNode * p,* q; if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 请回答下列问题：（1） 说明语句S1的功能；(2)说明语句组S2的功能； (3)设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性表。四（20分）已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK。(1)请构造出该二叉树。(2)写出该二叉树的后序序列。(3)给该树加中序线索，画出带中序线索的二叉链表。五（8分）算法设计题设计一算法，判定一个字符串是否是对称字符串。若是，则返回1；否则返回0。例如：“abcba”和“abba”均为对称字符串。数据结构试卷（一）一、单选题（每题 2 分，共20分）1. 栈和队列的共同特点是( )。A.只允许在端点处插入和删除元素B.都是先进后出 C.都是先进先出D.没有共同点 2. 用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改3. 以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树4. 设有一个二维数组Amn，假设A00存放位置在644(10)，A22存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用10进制表示。 A688 B678 C692 D6965. 树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据6. 二叉树的第k层的结点数最多为( ). A2k-1 B.2K+1 C.2K-1 D. 2k-17. 若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( ) A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，38. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2）9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个， A1 B2 C3 D410. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8二、填空题（每空1分，共26分）1. 通常从四个方面评价算法的质量：_、_、_和_。2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_。3. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J），则树中所含的结点数为_个，树的深度为_，树的度为_。4. 后缀算式9 2 3 +- 10 2 / -的值为_。中缀算式（3+4X）-2Y/3对应的后缀算式为_。5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有_个指针域，其中有_个指针域是存放了地址，有_个指针是空指针。6. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_个和_个。7. AOV网是一种_的图。8. 在一个具有n个顶点的无向完全图中，包含有_条边，在一个具有n个顶点的有向完全图中，包含有_条边。9. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_、_、_和_。10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度_。11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_，整个堆排序过程的时间复杂度为_。12. 在快速排序、堆排序、归并排序中，_排序是稳定的。三、计算题（每题 6 分，共24分）1. 在如下数组A中链接存储了一个线性表，表头指针为A 0.next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data605078903440next35720412. 请画出下图的邻接矩阵和邻接表。 3. 已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。四、阅读算法（每题7分，共14分）1. LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针 if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性表。2. void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right); coutdatadata) item=BST-data;/查找成功 return _; else if(itemdata) return Find(_,item); else return Find(_,item); /if六、编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x)数据结构试卷（二）一、选择题(24分)1下面关于线性表的叙述错误的是（ ）。(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现2设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m3设顺序循环队列Q0：M-1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。(A) R-F(B) F-R(C) (R-F+M)M(D) (F-R+M)M4设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为C