1、2007年燕山大学计算机专业基础综合（数据结构）真题试卷及答案与解析 一、填空题 1 如果顶点的度记为 TD(vi)，那么一个 n个顶点的图有 _条弧。 2 邻接表是一种链式存储结构，一般由 _构成。 3 一个连通图的生成树含有图中全部 n个顶点，但有且仅有 _条边。 4 树形结构中数据元素之间存在 _的关系。 5 线性链表的节点至少包含两个域，即 _。 6 具有 n个结点的完全二叉树的深度为 _。 7 简单排序算法 (即直接插 入排序 )的平均时间为 _，它是一种 _的排序方法。 8 设有序表 L的长度为 132对给定的 k值，用二分法查找与 k相等的元素，若查找成功，最少需要比较 _次，最
2、多需要比较 _次。 9 有 n个结点的哈夫曼树，其叶子结点总数是 _。 10 在含有 n个空链域的二叉链表中有 _个结点， n个结点的二又链表中有个空链域。 11 树的存储结构有 _结构和 _结构。 二、判断题 12 当用二叉链表作树的存储结构时，树的先序遍 历可以由二叉树的先序遍历实现。 （ A）正确 （ B）错误 13 在线性链表中，逻辑上相邻的数据元素其物理地址也是相邻的。 （ A）正确 （ B）错误 14 对同一组关键字，设定相同的哈希函数，即使采用不同的处理冲突的方法，哈希表的平均查找长度也是相同的。 （ A）正确 （ B）错误 15 线性表的顺序存储结构是一种随机存取的存储结构。
3、（ A）正确 （ B）错误 16 栈一般只用顺序存储结构表示，而队列一般只用链式存储结构表示。 （ A）正确 （ B）错误 17 循环队列是一种特殊的线 性表，它的每一个元素都有一个前驱和后继。 （ A）正确 （ B）错误 18 有向图的拓扑排序就是由偏序定义得到拓扑有序的操作。 （ A）正确 （ B）错误 19 二叉树的先序序列恰好是逆波兰表达式。 （ A）正确 （ B）错误 20 深度为 k的二叉树至多有 2k+1(k1)个结点。 （ A）正确 （ B）错误 21 有向图的逆邻接表是为了方便确定顶点的人度或以顶点 vi为头的弧而建立的。 （ A）正确 （ B）错误 三、简答题 22 设一棵
4、二：疋树结点的先根序列为 ABDGCEF，中根序列为 BGDAECF，写出该二又树的结构及其后根序列。 23 画出给出的邻接矩阵对应的图，并给出邻接表。 0 1 1 0 O O 0 0 0 0 0 1 1 0 0 0 24 分析下述算法功能 Status A(BiThrTree T， Status(*Visit)(TglemType e) pT一 lchild； while(p!一 T) while(p一 LTag=Link)p=p-lChild； if(!Visit(pdata)return ERRoR； while(p一 RTag一 =Thread&p-rchild!=T) p=p-rch
5、ild； Visit(pdata)； p=p-rchild； return OK； 25 编写在链式存储结构的队列中删除元素的算法。 26 设增量序列为 5、 3、 1，初始关键字序列为 51、 12、 55、 23、 49、 7、 60、 36、72、 12，写出希尔排序过程及每趟排序结果。 27 设关键字序列为 7、 21、 49、 72、 56，写出平衡二叉树的生成过程，并标明每个结点的平衡因子。 28 设用于通讯的电文仅由 7个字母组成，字母在电文中出现的频率为 0 29，0 19， 0 10， 0 04， 0 07， 0 12， 0 21，给出哈夫曼树的构造过程，及 7个字母的哈夫曼
6、编码。 29 设顺序表中的数据元素递增有序，编写一算法将元素 X插人到顺序表的适当位置上，并保证该表的有序性。 2007年燕山大学计算机专业基础综合（数据结构）真题试卷答案与解析 一、填空题 1 【正确答案】 2 【正确答案】 数据域和指针域 3 【正确答案】 n-1 4 【正确答案】 一对多 5 【正确答案】 数据域和指针域 6 【正确答案】 7 【正确答案】 O(n+1)/2,稳定 8 【正确答案】 1， 8 9 【正确答案】 (n+1) 2 10 【正确答案】 n-1， n+1 11 【正确答案】 顺序存储，链式存储 二、判断题 12 【正确答案】 A 13 【正确答案】 B 14 【正
7、确答案】 B 15 【正确答案】 A 16 【正确答案】 B 17 【正确答案】 A 18 【正确答案】 A 19 【正确答案】 B 20 【正确答案】 B 21 【正确答案】 A 三、简答题 22 【正确答案】 后序遍历的结果为： GDBEFCA。 23 【正确答案】 24 【正确答案】 采用二叉链表存储结构， Visit是对数据元素操作的应用函数，先序遍历线索二叉树的递归算法，对每个数据元素调用函数 Visit。 25 【正确答案】 在链式队列中删除元素，即为用链式队列的存储结构进行出队操作。 LinkQueue DeQueue(LinkQueue Q， QueueElementType*
8、e) QueueNode*P； if(QueueEmpty(Q) printf(“队列为空，出队操作失败 ! n”)； else p=Q front-next； *e=p-data Q front-next=p-next； if(Q rear=p) Q rear=Q front； free(P)； return Q； 26 【正确答案】 当增量为 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、 72。 27 【正确答案】 28 【正确答案】 29 【正确答案】
