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

1、广东工业大学考试试卷( 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，头指针 front 32，则当前循环队列的元素个数是（）。A 43B 16C 17D423广义表 A=(a,b,(c,d)，执行 Head(He

2、ad(Tail(Tail(A) 的结果是 （）。：A (c)B (d)C cD d业4下列有关二叉树的正确陈述是（）。专A二叉树中任何一个结点的度都为2B一棵二叉树的度可以小于2装C二叉树中至少有一个结点的度为2D二叉树的度为 25若将一棵树 t 转换为孩子兄弟链表表示的二叉树h，则 t 的后根遍历是 h 的（）。A前序遍历B中序遍历C 后序遍历D 层次遍历：6在有向图 G 的拓扑序列中，若顶点V i 在顶点 V j之前，则下列情形不可能出现的是（）。院学A G 中有弧 B G 中有一条从 V i到 V j的路径C G 中没有弧 D G 中有一条从 V j到 V i的路径广东工业大学试卷用纸，

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

4、 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 分）假设电文

5、中仅由a 到 e 共 5 个字母组成，字母在电文中出现的频率依次为0.2，0.15， 0.32， 0.28，0.05请画出由此构造的哈夫曼树（要求树中所有结点的左右孩子必须是左大右小），并计算该哈曼夫树的带权路径长度WPL 。2（8 分）设对称矩阵 A= 1002030000052050广东工业大学试卷用纸，共6 页，第 2 页（1）若将 A 中包括主对角线的下三角元素按行的顺序压缩到数组S 中，即 S 为1030002050下标：12345678910请求出 A 中任一元素的行列下标 i,j(1=i,j=4)与 S 中元素的下标K 之间的关系 ；（2）若将 Ai,j （1=i, jnext;

6、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 =

7、 ;x = front-data;free(front);return OK;广东工业大学试卷用纸，共6 页，第 4 页3（ 6 分）阅读下列算法，并回答问题（1）设二叉树 bt 如右图所示，请写出执行BAint c=0; f3(bt, c);C之后 c 的结果；DEFG（2）简述算法 f3 的功能。HIvoid f3(BiTree bt, int &x) Kif (bt) if( bt-lchild | bt-rchild )x+;f3(bt-lchild, x);f3(bt-rchild, x);4（ 6 分） 图的邻接表存储结构的类型定义如下：typedef struct ArcNode

8、 intadjvex;/ 该弧所指向的顶点的位置ArcNode*nextarc;/ 指向下一条弧的指针 ArcNode;/ 定义弧的结点typedef struct VertexTypedata;/ 顶点信息ArcNode*firstarc;/ 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; /定义顶点数组typedef struct AdjListvertices;intvexnum, arcnum;/ 图的当前顶点数和弧数intkind; ALGraph;/ 邻接表类型算法 f4(G, v)是以顶点 v 为起点，对图进行深度优先遍历。请在空缺处填入合适内容，使其成为完整的算法。void f4(ALGraph G, int v) AcrNode *p;visitedv=1;visit(v);广东工业大学试卷用纸，共6 页，第 5 页p = ;while (p) v = p-adjvex;if (!visitedv) ;p = ;五算法设计题 （8 分）假设二叉树T 中结点