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

广东工业大学考试试卷 ( B )课程名称: 数据结构 试卷满分 100 分考试时间: 年 月 日 (第 周 星期 )题 号一二三四五总分评卷得分评卷签名复核得分复核签名一单项选择题（共16分，每题2分）1设某数据结构的二元组形式表示为A=(D,S)，D=a,b,c,d,e,f，S =,，则数据结构A是（ ）。A 线性结构 B 树型结构 C 集合结构 D 图型结构2假设以数组A60存放循环队列的元素，如果当前的尾指针rear = 15，头指针front32，则当前循环队列的元素个数是（ ）。 A 43 B 16 C 17 D423广义表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 二叉树的度为2 5若将一棵树t 转换为孩子兄弟链表表示的二叉树h，则t的后根遍历是h的（ ）。A 前序遍历 B 中序遍历 C 后序遍历 D 层次遍历6在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。 A G中有弧 B G中有一条从Vi到Vj的路径 C G中没有弧 D G中有一条从Vj到Vi的路径 学 院： 专 业： 学 号： 姓 名： 装 订 线7散列表的地址区间为0-17，散列函数为H(K)=K mod 17，采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ ）。A 8 B 9 C 10 D 118ISAM文件和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下标： 1 2 3 4 5 6 7 8 9 10请求出A中任一元素的行列下标i,j(1=i,j=4)与S中元素的下标K之间的关系；（2）若将Ai,j（1=i, jnext; L-next = NULL; while (p!= NULL) s=p-next; p-next=L-next; L-next =p; p=s; 2（6分）假设以带头结点的循环链表表示队列，并且只设一个指针rear指向队尾元素（注意不设头指针），算法f2实现相应的出队列操作。请在空缺处填入合适内容，使其成为完整的算法。Status f2(LinkList &rear, ElemType &x) LinkList front; if ( ) return ERROR; else front = ; rear-next-next = front-next; if ( front = rear ) rear = ; x = front-data; free(front); return OK; KHFEABGICD3（6分）阅读下列算法，并回答问题（1） 设二叉树bt如右图所示，请写出执行 int c=0; f3(bt, c);之后c的结果；（2） 简述算法f3的功能。void f3(BiTree bt, int &x) if (bt) if( bt-lchild | bt-rchild ) x+;f3(bt-lchild, x);f3(bt-rchild, x); 4（6分）图的邻接表存储结构的类型定义如下：typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 ArcNode *nextarc; / 指向下一条弧的指针 ArcNode; / 定义弧的结点typedef struct VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; / 定义顶点数组typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; ALGraph; / 邻接表类型算法f4(G, v)是以顶点v为起点，对图进行深度优先遍历。请在空缺处填入合适内容，使其成为完整的算法。void f4(ALGraph G, int v) AcrNode *p;visitedv=1; visit(v); p = ; while (p) v = p-adjvex;if (!visitedv) ;p = ;五算法设计题（8分）假设二叉树T中结点值互不相同，并采用二叉链表存储结构 typedef struct node ElemType data; struct node *lchild, *rchild; *BiTree;编写算法，求元素值为x的结点在二叉树T中的层次。 广东工业大学试卷用纸，共6页，第6页