燕山大学07考研数据结构试题及答案.doc

《燕山大学07考研数据结构试题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、燕山大学07考研数据结构试题及答案：一填空题1如果定点的度记为TD（vi）,那么一个n个定点的图有（1/2）Σ（i=1）TD（vi）条弧。2邻接表是一种链式存储结构，一般由表结点和头结点构成。3一个连通图的生成树含有图中全部n个顶点，但有且仅有n-1条边。4树形结构中数据元素之间存在一对多的关系。5线性链表的节点至少包含两个域，即数据域和指针域。6具有n个结点的完全二叉树的深度为(log2)n+1。（顺序查找的平均查找长度为3/4（n+1））7简单排序算法(即直接插入排序)的平均时间为n2/4，它是一种稳定的排序方法。8设有序表L的长度为132，对给定

2、的k值，用二分法查找与k相等的元素，若查找成功，最少需要比较1次，最多需要比较8次。9有n个结点的哈夫曼树，其叶子结点总数是(n+1)/2。10在含有n个空链域的二叉链表中有n-1个结点。n个结点的二叉链表中有n+1个空链域11树的存储结构有顺序存储结构和链式存储结构二判断题1当用二叉链表作树的存储结构时，树的先序遍历可以由二叉树的先序遍历实现。Y2在线性链表中，逻辑上相邻的数据元素其物理地址也是相邻的。N3对同一组关键字，设定相同的哈希函数，即使采用不同的处理冲突的方法，哈希表的平均查找长度也是相同的。N4线性表的顺序存储结构是一种随即存取的存储结构

3、。Y5栈一般只用顺序存储结构表示，而队列一般只用链式存储结构表示。N6循环队列是一种特殊的线性表，它的每一个元素都有一个前驱和后继。Y7有向图的拓扑排序就是由偏序定义得到拓扑有序的操作。Y8二叉树的先序序列恰好是逆波兰表达式N9深度为k的二叉树至多有2^k+1个结点（k〉=1）N10有向图的逆邻接表是为了方便确定顶点的入度或以顶点vi为头的弧而建立的。Y三解答题1设一棵二叉树结点的先序序列为ABDGCEF，中根序列为BGDAECF，写出该二叉树的结构及其后跟序列。后序遍历的结果为:GDBEFCA2画出给出的邻接矩阵对应的图，并给出邻接表01100000

4、000110003分析下述算法功能StatusA(BiThrTreeT,Status(*Visit)(TElemTypee)){p=T->lchild;while(p!=T){while(p->LTag==Link)p=p->lchild;if(!Visit(p->data))returnERROR;while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);}p=p->rchild;}returnOK;}return采用二叉链表存储结构，Visit是对数据元素操作的应用函数，先序遍历

5、线索二叉树的递归算法，对每个数据元素调用函数Visit4编写在链式存储结构的队列中删除元素的算法。在链式队列中删除元素，即为用链式队列的存储结构进行出队操作。LinkQueueDeQueue(LinkQueueQ,QueueElementType*e){QueueNode*p;if(QueueEmpty(Q))printf(“队列为空，出队操作失败!”);else{p=Q.front->next;*e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);}returnQ

6、;}5设增量序列为5、3、1，初始关键字序列为51、12、55、23、49、7、60、36、72、12写出希尔排序过程及每趟排序结果。当增量为5、3、1时，对51、12、55、23、49、7、60、36、72、12的希尔排序的结果为：第一趟d=5排序后7、12、36、23、12、51、60、55、72、49第二趟d=3排序后7、12、36、23、12、51、49、55、72、60第三趟d=1排序后7、12、12、23、36、49、51、55、60、726设有一森林如图。给出对应的二叉树及该二叉树先根、中根、后根序列。第一步将森林中的每棵树转化为二叉树第

7、二步生成二叉树先序遍历该二叉树：ABCDEFGH中序遍历该二叉树：BDECAGHF后序遍历该二叉树：EDCBHGFA7设关键字序列为7、21、49、72、56，写出平衡二叉树的生成过程，并标明每个结点的平衡因子。7、21、49、72、56的平衡二叉树的生成过程（平衡因子：将该节点的左子树高度减去右子树高度，成为该节点的平衡因子）8试列出图中二种可能的拓扑有序序列，并给出其生成森林。深度优先拓扑序列AFEBDC广度优先拓扑序列ADFCEB9设有序表长度为n，设表中每个记录的查找概率相等，计算查找成功时顺序的平均查找长度å==niiicpASL1=åni1

8、=(n-i+1)=10设散列函数为H（k）-kmod9,一组关键字为7、11、23、49、32