一、简答题(每题5分共40分)

1、.一、 简答题(每题5分，共40分)摘要：定义二叉树的宽度为二叉树一层中结点个数的最大值，试编写一算法求二叉树的宽度。 . (2) 若查找关键字31，需要依次与10、24、17和31进行比较 .关键词：点,算法,24类别：专题技术来源：牛档搜索（Niudown.COM）本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！;一、 简答题(每题5分，共40分)1. 向一个长度为n的向量的

2、第i个元素(1in+1)之前插入一个元素时，需向后移动多少个元素？2. 设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a30, 58的存储地址为多少？3. 设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，请具体写出这四辆列车开出车站的任意5种可能的顺序。4. 说明线性表、栈、队的异同点。5. 由3个结点构成的树有几种形态？由3个结点构成的二叉树呢？6. 某完全二叉树共有701个结点，请问其树叶有多少个？7. 已知一棵二叉树的前序序列和中序序列分别为：ABDEGCFH和DBGEACHF，则该二叉树的后序序列是什么？ 8. 若初始

3、记录基本有序，则选用哪些排序方法比较适合？若初始记录基本无序，则最好选用哪些排序方法？请解释理由（排序方法各列举一种即可）。二、综合题（每题10分，共30分）1. 现有一个具有五个元素的线性表L=23，17，47，05，31，若它以链接方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，请指出该线性表的首元结点的起始地址，并填写下表中各个指针分量的值。 2. 已知一组关键字为（10， 24， 32， 17， 31， 30， 46， 47， 40， 63， 49），设哈希函数H（key）key MOD 7。请解答：（1） 写出用链地址法处理冲突构造所得的

4、哈希表；（2） 若查找关键字31，需要依次与哪些关键字进行比较？（3） 若查找关键字60，需要依次与哪些关键字比较？（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。3. 对关键码值为35，11，52，69，6，17，76，64，82的序列执行直接选择排序算法，请画出执行过程中每个中间状态和结束时的状态。三、 算法设计题（每题15分，共30分）1. 编程：统计单链表中数据元素为0的个数。 2. 编程：统计二叉树中数据元素为1的个数。3. 定义二叉树的宽度为二叉树一层中结点个数的最大值，试编写一算法求二叉树的宽度。一、 简答题(每题5分，共40分)1. 向一个长度为n的向量的第i

5、个元素(1in+1)之前插入一个元素时，需向后移动多少个元素？n-i+12. 设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为多少？答：考虑0行0列，（58列×61行30行）×2字节基址2048=91843. 设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，请写出这四辆列车开出车站的任意5种可能的顺序。至少有14种。 全进之后再出情况，只有1种：4，3，2，1 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 进2个之后再出的情况，有5种，2,4,3,1 2

6、,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,34. 说明线性表、栈、队的异同点。刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 用途不同，堆栈用于子程调用和保护现场，队列用于指令寄存及其他运

7、算等等。5.由个结点构成的树有几种形态？由个结点构成的二叉树呢？答：树有2种形态，二叉树则有5种形态。6. 某完全二叉树共有701个结点，请问其树叶有多少个？ 351(个)， N/2取上限7. 已知一棵二叉树的前序序列和中序序列分别为：ABDEGCFH和DBGEACHF，则该二叉树的后序序列是什么？该二叉树的后序序列是 D G E B H F C A8. 假设一有序表中有23个元素，现进行折半查找，则平均查找长度是多少？ 平均查找长度ASL3.879. 用5个权值 3, 2, 4, 5, 1 构造的哈夫曼（Huffman）树的带权路径长度是多少？ WPL3310. 若初始记录基本有序，则选用哪

8、些排序方法比较适合？若初始记录基本无序，则最好选用哪些排序方法？请解释理由（排序方法各列举两种即可）。答： 基本有序时可选用直接插入、简单选择、堆排序、锦标赛排序、冒泡排序、归并排序、(希尔排序)等方法，其中插入排序和冒泡应该是最快的。因为只有比较动作，无需移动元素。此时平均时间复杂度为O(n)； 无序的情况下最好选用快速排序、希尔排序、简单选择排序等，这些算法的共同特点是，通过“振荡”让数值相差不大但位置差异很大的元素尽快到位。二、综合题（每题10分，共30分）1. 现有一个具有五个元素的线性表L=23，17，47，05，31，若它以链接方式存储在下列100119号地址空间中，每个结点由数据

9、（占2个字节）和指针（占2个字节）组成，请指出该线性表的首元结点的起始地址，并填写下表中各个指针分量的值。答：首元结点的起始地址为108。2. 已知一组关键字为（10， 24， 32， 17， 31， 30， 46， 47， 40， 63， 49），设哈希函数H（key）key MOD 7。请解答：（1） 写出用链地址法处理冲突构造所得的哈希表；（2） 若查找关键字31，需要依次与哪些关键字进行比较？（3） 若查找关键字60，需要依次与哪些关键字比较？（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。(1) 哈希表如下：(2) 若查找关键字31，需要依次与10、24、17和31

10、进行比较（3） 若查找关键字60，需要先查4单元，与32、46比较，再查指针为空则返回。（4）ASL1. 823. 对关键码值为35，11，52，69，6，17，76，64，82的序列执行直接选择排序算法，请画出执行过程中每个中间状态和结束时的状态。三、 算法设计题（任选两题，每题15分，共30分）1. 编程：统计单链表中数据元素为0的个数。 #include<stdlib.h>typedef struct liuyuint data;struct liuyu *link;test;test*head,*p;void count() /*单链表的统计*/int k=0;p=head

11、;while (p) /* 只要没到最后一个元素的末尾，就不停地“顺藤摸瓜”判断并统计*/ if(p->data=0)k+;p=p->link; printf("%dn",k); 2. 编程：统计二叉树中数据元素为1的个数。解：无论用先序、中序或后序遍历算法均可。此题以先序为例。#include<stdio.h>#include<stdlib.h>typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuyu *root,*p;int k=0; /*建树过程略*/DLR(test*root)if(!root)return(