广东工业大学-数据结构试卷

广东工业大学试卷用纸，共6页，第4页广东工业大学考试试卷(B)课程名称:广东工业大学考试试卷(B)课程名称:数据结构试卷满分100分考试时间:年月日(第周星期)题号一二三四五总分评卷得分评卷签名复核得分复核签名一．单项选择题（共16分，每题2分）1．设某数据结构的二元组形式表示为A=(D,S)，D={a,b,c,d,e,f}，S={<a,b>,<a,c>,<b,d>,<b,e>,<c,e>,<c,f>}，则数据结构A是（）。 [A]线性结构 [B]树型结构 [C]集合结构 [D]图型结构2．假设以数组A[60]存放循环队列的元素，如果当前的尾指针rear=15，头指针front＝32，则当前循环队列的元素个数是（）。[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]层次遍历6．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。[A]G中有弧<Vi，Vj>[B]G中有一条从Vi到Vj的路径[C]G中没有弧<Vi，Vj>[D]G中有一条从Vj到Vi的路径学院：专业：学号：姓名：装订线7．散列表的地址区间为0-17，散列函数为H(K)=Kmod17，采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（）。[A]8[B]9[C]10[D]118．ISAM文件和VASM文件属于（）。[A]索引非顺序文件[B]顺序文件[C]索引顺序文件[D]散列文件二．填空题（共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．简单选择排序的平均时间复杂度是___________，堆排序的平均时间复杂度是___________。三．解答题（共40分）1．（6分）假设电文中仅由a到e共5个字母组成，字母在电文中出现的频率依次为0.2，0.15，0.32，0.28，0.05请画出由此构造的哈夫曼树（要求树中所有结点的左右孩子必须是左大右小），并计算该哈曼夫树的带权路径长度WPL。2．（8分）设对称矩阵A=（1）若将A中包括主对角线的下三角元素按行的顺序压缩到数组S中，即S为1030002050下标：12345678910请求出A中任一元素的行列下标[i,j](1<=i,j<=4)与S中元素的下标K之间的关系；（2）若将A[i,j]（1<=i,j<=4）视为稀疏矩阵，画出其三元组表。3．（10分）若带权无向图G的邻接矩阵如右图所示，顶点集是{V1,V2,V3,V4,V5}，（1）画出图G的邻接表，要求每个顶点的表结点序号都是按照从小到大的次序链接；（2）画出图G的最小生成树。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）________________________；（3）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;}}2．（6分）假设以带头结点的循环链表表示队列，并且只设一个指针rear指向队尾元素（注意不设头指针），算法f2实现相应的出队列操作。请在空缺处填入合适内容，使其成为完整的算法。Statusf2(LinkList&rear,ElemType&x){LinkListfront;if(①)returnERROR;else{front=②;rear->next->next=front->next;if(front==rear)rear=③;x=front->data;free(front);returnOK;}}KHKHFEABGICD设二叉树bt如右图所示，请写出执行intc=0;f3(bt,c);之后c的结果；简述算法f3的功能。voidf3(BiTreebt,int&x){if(bt){if(bt->lchild||bt->rchild)x++;f3(bt->lchild,x);f3(bt->rchild,x);}}4．（6分）图的邻接表存储结构的类型定义如下：typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置ArcNode*nextarc;//指向下一条弧的指针}ArcNode;//定义弧的结点typedefstruct{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];//定义顶点数组typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;}ALGraph;//邻接表类型算法f4(G,v)是以顶点v为起点，对图进行深度优先遍历。请在空缺处填入合适内容，使其成为完整的算法。voidf4(ALGraphG,intv){AcrNode*p;visited[v]=1;visit(v);p=①;while(p){v=p->adjvex;if(!visited[v])②