资源描述：
《广东工业大学数据结构试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、广东工业大学考试试卷(B)课程名称:数据结构试卷满分100分考试时间:年月日(第周星期)题号一二三四五总分评卷得分评卷签名复核得分复核签名一．单项选择题（共16分，每题2分）1．设某数据结构的二元组形式表示为A=(D,S)，D={a,b,c,d,e,f}，S={,,,,,}，则数据结构A是（）。[A]线性结构[B]树型结构[C]集合结构[D]图型结构2．假设以数组A[60]存放循环队列的元素，如果当前的尾指针rear=15，头指针front＝32，则当前循环队列的元素个数是（）。[A]43 [B]16 [C]17
2、[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中有弧[B]G中有一条从Vi到Vj的路径[
3、C]G中没有弧[D]G中有一条从Vj到Vi的路径学院：专业：学号：姓名：装订线广东工业大学试卷用纸，共6页，第6页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）采用顺序存储表示，假定删除表中任一元素的概率相同，则删除一
4、个元素需要移动元素的平均次数是___________。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，则采用的是___________遍
5、历方法。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为广东工业
6、大学试卷用纸，共6页，第6页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
7、后插入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,
