题号—一二二四五总分评卷得分评卷签名复核得分复核签名(完整word版)广东工业大学数据结构试卷广东工业大学试卷用纸,共7页,第1页广东工业大学考试试卷(B)课程名称：数据结构试卷满分100分—•单项选择题(共16分，每题2分)1.设某数据结构的二元组形式表示为A=(D,S),D={a,b,c,d,e,f},S={va,b>,va,c>,vb,d〉，vb,e>,〈c,e>,〈c,f>},则数据结构A是()。[A]线性结构[B]树型结构[C]集合结构[D]图型结构2.假设以数组A[60]存放循环队列的元素，如果当前的尾指针rear=15,头指针front=32,贝V当前循环队列的元素个数是()。[A]43[B]16[C]17[D]423.广义表A=(a,b,(c,d)),执行Head(Head(Tail(Tail(A))))的结果是()。[A](c)[B](d)[C]c[D]d4.下列有关二叉树的正确陈述是().[A]二叉树中任何一个结点的度都为2[B]一棵二叉树的度可以小于2[C]二叉树中至少有一个结点的度为2[D]二叉树的度为25.若将一棵树t转换为孩子一兄弟链表表示的二叉树h,则t的后根遍历是h的().[A]前序遍历[B]中序遍历[C]后序遍历[D]层次遍历7•散列表的地址区间为0—17，散列函数为H（K）=Kmod17，采用线性探测法处理冲突，并将关键字序列26,25,72,38,8,18,59依次存储到散列表中。元素59存名姓考试时间：年月日(第周星期)广东工业大学试卷用纸，共7页，第2页列文件二.填空题（共12分，每空1分）1•线性表L=（a1,a2，…，an）采用顺序存储表示，假定删除表中任一元素的概率相同，则删除一个元素需要移动元素的平均次数是。2•在栈结构中，允许插入和删除的一端称为另一端称为。3•模式串P二’ababc'的next函数值序列为。4•深度为6的完全二叉树的结点数至少有个。5•线索二叉树舶勺左线索指向右线索指向其.6•已知无向图G=（V,E），其中V={a,b,c,d,e},E={（a,b）,（a,d）,（a,c）,（d,c）,（b,e）},若从顶点a开始遍历图，得到的序列为a,b,e,c,d,则采用的遍历方法.7•动态查找表和静态查找表的重要区别在于前者包含有和运算，而后者不包含这两种运算。8•简单选择排序的平均时间复杂度是堆排序的平均时间复杂度是O三.解答题（共40分）1（6分）假设电文中仅由a到e共5个字母组成,字母在电文中出现的频率依次为0。2,0.15,0。32,0.28,0.05请画出由此构造的哈夫曼树（要求树中所有结点的左右孩子必须是左大右小），并计算该哈曼夫树的带权路径长度WPL.广东工业大学试卷用纸，共7页，第3页3.(10分)若带权无向图G的邻接矩阵如右图所示，顶点集是M,VJ,(1)画出图G的邻接表，要求每个顶点的表结点序号都是按照从小到大的次序链接；g11g32542gV2,32gg3V3,V4,52_4gg3g44g2.（8分）设对称矩阵A=_i002_030000052050(1)若将A中包括主对角线的下三角元素按行的顺序压缩到数组S中，即S为1030002050下标：12345678910请求出A中任一元素的行列下标[i,j](1v二i,j〈=4)与S中元素的下标K之间的关系；(2)若将A[i,j](1〈二i,j<=4)视为稀疏矩阵，画出其三元组表.4.(8分)从空树开始构造一棵平衡二叉排序树依次插入的关键字为(11,13,15,17,19,20),请按下图要求画出该树的部分生成过程。插入11,13,15后插入17后插入19后插入20后5.(8分)对序列(3,87,12,61,70,97,26,45)执行升序排序。试根据堆排序原理，填写完整下列各步骤纟吉果。建立大顶堆结构：交换与调整：(1)87,70,26,61,45,12,3,97;(2);广东工业大学试卷用纸，共7页，第4页⑶61,45,26,3,12,70,87,97;(4)45,12,26,3,61,70,87,97;(5)26,12,3,45,61,70,87,97;(6);(7)3,12,26,45,61,70,87,97;四•算法阅读题(共24分)1.(6分)阅读算法f1,并回答问题。(1)设线性表L=(2,3,6,5,4),并采用带头结点的单链表储存，写出执行算法f1(L)后的L;(2)简述算法f1(L)对线性表L的操作意义.voidf1(LinkList&L){LinkListp,s;p=L->next;L—>next=NULL;while(p!=NULL){s=p一〉next;p-〉next二L->next;L->next=p;p=s;广东工业大学试卷用纸，共7页，第5页}}2.（6分）假设以带头结点的循环链表表示队列，并且只设一个指针rear指向队尾元素（注意不设头指针），算法f2实现相应的出队列操作。请在空缺处填入合适内容，使其成为完整的算法。Statusf2（LinkList&rear,ElemType&x）{LinkListfront;if（①）returnERROR;else{front=②;rear—〉next...
