完整版广东工业大学数据结构试卷

1、G）广东工业大学考试试卷（试卷满分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图型结构rear=15,头指针front2.假设以数组A60存放循环队列的元素，如果当前的尾指针=32,则当前循环队列的元素个数是（A43B16)C17

2、D423.广义表A=(a,b,(c,d),执行Head(Head(Tail(Tail(A)的结果是A(c)B(d)Cc()。DdBD一棵二叉树的度可以小于2二叉树的度为24,下列有关二叉树的正确陈述是（A二叉树中任何一个结点的度都为C二叉树中至少有一个结点的度为5.若将一棵树t转换为孩子一兄弟链表表示的二叉树h,则t的后根遍历是h的:）。A前序遍历B中序遍历C后序遍历D层次遍历6.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的AG中有弧<Vi,Vj>CG中没有弧<Vi,Vj>BG中有一条从Vi到Vj的路径DG中有一条从Vj到Vi的路径广东工业大

3、学试卷用纸，共6页，第1页7,散列表的地址区间为0-17,散列函数为H(K户Kmod17,采用线性探测法处理冲突，并将关键字序列26,25,72,38,8,18,59依次存储到散列表中。元素59存放在散列表中的地址是()。A8B9C10D118.ISAM文件和VASM文件属于()。A索引非顺序文件B顺序文件C索引顺序文件D散列文件二.填空题(共12分，每空1分)1,线性表L=(a1,a2,an)采用顺序存储表示，假定删除表中任一元素的概率相同，则删除一个元素需要移动元素的平均次数是。2 .在栈结构中，允许插入和删除的一端称为,另一端称为。3 .模式串P='ababc'的next

4、函数值序列为。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请画出

5、由此构造的哈夫曼树(要求树中所有结点的左右孩子必须是左大右小)，并计算该哈曼大树的带权路径长度WPL。2. (8分)设对称矩阵A=-1002一03000005_2050_广东工业大学试卷用纸，共6页，第2页1030002050(1)若将A中包括主对角线的下三角元素按行的顺序压缩到数组S中，即S为下标：12345678g10请求出A中任一元素的行列下标i,j(1<=i,j<=4)与S中元素的下标K之间的关系；(2)若将Ai,j(1<=i,j<=4)视为稀疏矩阵，画出其三元组表。r°°135：22003. (10分)若带权无向图G的邻接矩阵如右图所示，顶

6、点集是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;

7、(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;广东工业大学试卷用纸，共6页，第3页四.算法阅读题(共24分)1. (6分)阅读算法fl,并回答问题。(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-&g

8、t;next=L->next;L->next=p;p=s;)2. (6分)假设以带头结点的循环链表表示队列，并且只设一个指针rear指向队尾元素(注意不设头指针)，算法f2实现相应的出队列操作。请在空缺处填入合适内容，使其成为完整的算法。Statusf2(LinkList&rear,ElemType&x)LinkListfront;if()returnERROR;elsefront=;rear->next->next=front->next;if(front=rear)rear=;x=front->data;free(front);retur

9、nOK;)广东工业大学试卷用纸，共6页，第4页ABFDGI3. (6分)阅读下列算法，并回答问题(1) 设二叉树bt如右图所示，请写出执行intc=0;f3(bt,c);之后c的结果；(2) 简述算法f3的功能。voidf3(BiTreebt,int&x)if(bt)if(bt->lchild|bt->rchild)x+;f3(bt->lchild,x);f3(bt->rchild,x);)4. (6分)图的邻接表存储结构的类型定义如下：typedefstructArcNodeintadjvex;/该弧所指向的顶点的位置ArcNode*nextarc;/指向下一

10、条弧的指针ArcNode;/定义弧的结点typedefstructVertexTypedata;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧VNode,AdjListMAX_VERTEX_NUM;/定义顶点数组typedefstructAdjListvertices;intvexnum,arcnum;/图的当前顶点数和弧数intkind;ALGraph;/邻接表类型算法f4(G,v)是以顶点v为起点，对图进行深度优先遍历。请在空缺处填入合适内容,使其成为完整的算法。voidf4(ALGraphG,intv)AcrNode*p;visitedv=1;visit(v);广东工业大学试卷用纸，共6页，第5页p=®while(p)v=p->adjvex;if(!visited