数据构造试卷〔一〕三、计算题〔每题 6 分，共 24 分〕1.在如下数组 A 中链接存储了一个线性表，表头指针为 A [0].next，试写出该线性表。A01234567data605078903440next35720412.请画出以下列图的邻接矩阵和邻接表。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=L－>next；p=L； S1：while(p－>next) p=p－>next；S2：p－>next=q；q－>next=NULL；}returnL；}请答复以下问题：〔1〕说明语句 S1 的功能；〔2〕说明语句组 S2 的功能；〔3〕设链表表示的线性表为〔a1,a2, …,a 〕,写出算法执行后的返回值所表示的线性n表。2. void ABC(BTNode * BT){ifBT {ABC (BT->left);ABC (BT->right); cout<data<<' ';}}该算法的功能是：五、算法填空〔共 8 分〕二叉搜索树的查找——递归算法:bool Find(BTreeNode* BST,ElemType& item){if (BST==NULL)return false; //查找失败 else {if (item==BST->data){item=BST->data;//查找成功return ;}else if(itemdata)return Find( ,item); else return Find( ,item);}//if}六、编写算法〔共 8 分〕统计出单链表 HL 中结点的值等于给定值 X 的结点数。 int CountX(LNode* HL,ElemType x)数据构造试卷〔二〕三、应用题(36 分)1. 设一组初始记录关键字序列为(45，80，48，40，22，78)，那么分别给出第 4 趟简单项选择择排序和第 4 趟直接插入排序后的结果。2. 设指针变量 p 指向双向链表中结点 A，指针变量 q 指向被插入结点 B，要求给出在结点 A 的后面插入结点 B 的操作序列〔设双向链表中结点的两个指针域分别为 llink 和rlink〕。3. 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字 62 时的比较次数并计算出查找成功时的平均查找长度。4. 设一棵树 T 中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法...
