资源描述：
《一、简答题(每题5分，共40分)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、一、简答题(每题5分，共40分)摘要：定义二叉树的宽度为二叉树一层中结点个数的最大值，试编写一算法求二叉树的宽度。....(2)若查找关键字31，需要依次与10、24、17和31进行比较...关键词：点,算法,24类别：专题技术来源：牛档搜索（Niudown.COM） 本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！一、简答题(每
2、题5分，共40分)1.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动多少个元素？2.设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[30,58]的存储地址为多少？3.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，请具体写出这四辆列车开出车站的任意5种可能的顺序。4.说明线性表、栈、队的异同点。5.由3个结点构成的树有几种形态？由3个结点构成的二叉树呢？6.某完全二叉树共有701个结点，请问其树叶有多少个？7.已知一棵二叉树的前序序列和中
3、序序列分别为：ABDEGCFH和DBGEACHF，则该二叉树的后序序列是什么？8.若初始记录基本有序，则选用哪些排序方法比较适合？若初始记录基本无序，则最好选用哪些排序方法？请解释理由（排序方法各列举一种即可）。二、综合题（每题10分，共30分）1.现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，请指出该线性表的首元结点的起始地址，并填写下表中各个指针分量的值。2.已知一组关键字为（10，24，32，17，31，30，46，
4、47，40，63，49），设哈希函数H（key）＝keyMOD7。请解答：（1）写出用链地址法处理冲突构造所得的哈希表；（2）若查找关键字31，需要依次与哪些关键字进行比较？（3）若查找关键字60，需要依次与哪些关键字比较？（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。3.对关键码值为{35，11，52，69，6，17，76，64，82}的序列执行直接选择排序算法，请画出执行过程中每个中间状态和结束时的状态。三、算法设计题（每题15分，共30分）1.编程：统计单链表中数据元素为0的个数。2.编程：统计二叉树中数据元素为1的个数。
5、3.定义二叉树的宽度为二叉树一层中结点个数的最大值，试编写一算法求二叉树的宽度。一、简答题(每题5分，共40分)1.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动多少个元素？n-i+12.设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为多少？答：考虑0行0列，（58列×61行＋30行）×2字节＋基址2048=91843.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，请写出这四辆列车开出车站的任意5种可能的顺序。至
6、少有14种。①全进之后再出情况，只有1种：4，3，2，1②进3个之后再出的情况，有3种，3,4,2,13,2,4,13,2,1,4③进2个之后再出的情况，有5种，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,34.说明线性表、栈、队的异同点。刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：①运算规则不同，线性表为随机
7、存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。②用途不同，堆栈用于子程调用和保护现场，队列用于指令寄存及其他运算等等。5.由３个结点构成的树有几种形态？由３个结点构成的二叉树呢？答：树有2种形态，二叉树则有5种形态。6.某完全二叉树共有701个结点，请问其树叶有多少个？351(个)，[N/2]取上限7.已知一棵二叉树的前序序列和中序序列分别为：ABDEGCFH和DBGEACHF，则该二叉树的后序序列是什么？该二叉树的后序序列是DGEBHFCA8.假设
8、一有序表中有23个元素，现进行折半查找，则平均查找长度是多少？平均查找长度ASL＝3.879.用5个权值{3,2,4,5,1}构造的哈夫
