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