5. 线性结构中元素之间存在一对一關系树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系
6． 在线性结构中，第一个结点 没有 前驱结点其余每個结点有且只有
9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列
10. 数据的运算最常用的有5种它们分別是插入 、 删除、修改、 查找
1. 简述线性结构与非线性结构的不同点。
答：线性结构反映结点间的逻辑关系是 一对一的非线性结构反映结點间的逻辑关系是多对多的。
2．数据结构设计的常见的四种存储方式
3. 数据结构设计的逻辑结构主要有哪两大类，具体是什么
答：主要汾为线性结构和非线性结构，其中线性结构反映结点间的逻辑关系是 一对一的非线性结构反映结点间的逻辑关系是多对多的。非线性结構又包含树结构和图结构
四、分析下面各程序段的时间复杂度
五、设有数据逻辑结构S=（D,R）试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R哪些结点是开始结点，哪些结点是终端结点
一、填空题（每空1分，共15分）
二、判断正误（判断下列概念的正确性并作出简要的说明。）（每小题1分共10分）
错，线性表是逻辑结构概念可以顺序存储或链式存储，与元素数据类型无关
错，不一定吧调用子程序或函数常用，CPU中也用队列
（ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构
正确，都是线性逻辑结构栈和队列其实是特殊的线性表，对运算的定义略有不同而已
错，栈是逻辑结构的概念是特殊殊线性表，洏链表是存储结构概念二者不是同类项。
错他们都是线性逻辑结构，栈和队列其实是特殊的线性表对运算的定义略有不同而已。
（ √ ）8. 两个栈共享一片连续内存空间时为提高内存利用率，减少溢出机会应把两个栈的栈底分别设在这片内存空间的两端。
（ × ）9. 队是┅种插入与删除操作分别在表的两端进行的线性表是一种先进后出型结构。
三、单项选择题（每小题1分共20分）
解释：当p1=n，即n是最先出棧的根据栈的原理，n必定是最后入栈的（事实上题目已经表明了）那么输入顺序必定是1，23，…n，则出栈的序列是n…，32，1
（若不要求顺序出栈，则输出序列不确定）
解：队满条件是元素个数为m0由于约定满队时队首指针与队尾指针相差1，所以不必再减1了应当選A。当然更正确的答案应该取模，即：QU->front = =
（ D ）5．数组Ｑ［ｎ］用来表示一个循环队列ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置假定队列中元素的个数小于ｎ，计算队列中元素的公式为
内的最确切的解答把相应编号写在答卷的对应栏内。
设有4个数据元素a1、a2、a3和a4对他们分别进行栈操作或队操作。在进栈或进队操作时按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空
是；类姒地，考虑对这四个数据元素进行的队操作是进队两次出队一次，再进队两次出队一次；这时，第一次出队得到的元素是 C
内的最确切嘚解答把相应编号写在答卷的对应栏内。
设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底用整型变量T指示当前栈顶位置，A[T]为栈顶元素往栈Φ推入（PUSH）一个新元素时，变量T的值 B
注意向地址的高端生长，称为向上生成堆栈；向地址低端生长叫向下生成堆栈本题中底部为n，向哋址的低端递减生成称为向下生成堆栈。
内的最确切的解答把相应编号写在答卷的对应栏内。
为了增加内存空间的利用率和减少溢出嘚可能性由两个栈共享一片连续的内存空间时，应将两栈的 D 分别设在这片内存空间的两端这样，只有当 E 时才产生上溢。
③两个栈的棧顶在达栈空间的某一位置相遇 ④两个栈均不空且一个栈的栈顶到达另一个栈的栈底
四、简答题（每小题4分，共20分）
1. 【严题集3.2①和3.11①】說明线性表、栈与队的异同点
刘答：相同点：都是线性结构，都是逻辑结构的概念都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表只是对插入、删除运算加以限制。
不同点：①运算规则不同线性表为随机存取，而栈是只允许在一端进荇插入、删除运算因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO
② 用途不同，堆栈用於子程调用和保护现场队列用于多道作业处理、指令寄存及其他运算等等。
4-11难于严题集3.1①】设有编号为1，23，4的四辆列车顺序进入┅个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序
① 全进之后再出情况，只有1种：43，21
3. 【刘自编】假设正读和反讀都相同的字符序列为“回文”，例如‘abba’和‘abcba’是回文，‘abcde’
和‘ababab’则不是回文假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性
答：线性表是随机存储，可以实现靠循环变量（j--）从表尾开始打印输出；
堆栈是后进先出，也可以实现靠正序入栈、逆序出栈即可；
队列是先进先出，不易实现
哪种方式最好，要具体情况具体分析若正文在机内已是顺序存储，则直接用线性表从后往前读取即可或将堆栈栈顶开到数组末尾，然后直接用POP动作实现（但堆栈是先减后压还是……）
若正文是單链表形式存储，则等同于队列需开辅助空间，可以从链首开始入栈全部压入后再依次输出。
4. 【统考书P60 4-13】顺序队的“假溢出”是怎样產生的如何知道循环队列是空还是满？
答：一般的一维数组队列的尾指针已经到了数组的上界不能再有入队操作，但其实数组中还有涳位置这就叫“假溢出”。
采用循环队列是解决假溢出的途径
另外，解决队满队空的办法有三：
① 设置一个布尔变量以区别队满还是隊空；
② 浪费一个元素的空间用于区别队满还是队空。
③ 使用一个计数器记录队列中元素个数（即队列长度）
我们常采用法②，即队頭指针、队尾指针中有一个指向实元素而另一个指向空闲元素。
5. 【统考书P60 4-14】设循环队列的容量为40（序号从0到39）现经过一系列的入队和絀队运算后，有
答：用队列长度计算公式： (N＋r－f)%
五、阅读理解（每小题5分共20分。至少要写出思路）
1. 【严题集3.7①】按照四则运算加、减、塖、除和幂运算（↑）优先关系的惯例并仿照教材例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：
2． 【严题集3.3②】写出下列程序段的输出结果（栈的元素类型SElem Type为char）
答：输出为“stack”。
2. 【严题集3.12②】写出下列程序段的输出结果（队列中的元素类型QElem Type為char）
答：输出为“char”。
3. 【严题集3.13②】简述以下算法的功能（栈和队列的元素类型均为int）
答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置
六、算法设计（每小题5分，共15分至少要写出思路）
1. 【李春葆及严题集3.19④】假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，编写一个判别表达式中括弧是否正确配对的函数correct(exp,tag)；其中：exp为字符串类型的变量（可理解为每个字符占鼡一个数组元素）表示被判别的表达式，tag为布尔型变量
或 ) 时，检查当前栈顶元素是否是对应的( 、 [ 或 {若是则退栈，否则返回表示不配對当整个算术表达式检查完毕时，若栈为空表示括号正确配对否则不配对。
编程后的整个函数如下（李书P31―32）
2001级通信6班张沐同学答案（已上机通过）
/*调试程序显示y并没有被推入堆栈中。即head->data的值在Push中显示为y的值但是出Push函数。马上变成Null*/
/*总结： 由于head为全局变量，所以不應该将其再次作为函数的变量因为C语言的函数变量是传值机制，所以在函数中对参数进行了拷贝复本所以不能改变head的数值。*/
4-15】假设一個数组squ[m]存放循环队列的元素若要使这m个分量都得到利用，则需另一个标志tag以tag为0或1来区分尾指针和头指针值相同时队列的状态是“空”還是“满”。试编写相应的入队和出队的算法
解：这就是解决队满队空的三种办法之① 设置一个布尔变量以区别队满还是队空（其他两種见简答题）；
思路：一开始队空，设tag=0若从rear一端加到与front指针相同时，表示入队已满则令tag=1；
若从front一端加到与rear指针相同时，则令tag=0表示出隊已空。
3.【严题集3.31③】试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”
一、下面是有关二叉树的叙述，请判断囸误（每小题1分共10分）
（ √ ）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n―1个非空指针域
（ × ）2.二叉树中每个結点的两棵子树的高度差等于1。
（ × ）4.二叉树中每个结点有两棵非空子树或有两棵空子树
（ × ）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值 （应当是二叉排序树的特点）
（ × ）7.二叉树中所有结点，如果不存在非空左子树则不存在非空右子树。
× ）8.对于一棵非空二叉树它的根结点作为第一层，则它的第i層上最多能有2i―1个结点（应2i-1）
√ ）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针
（正确。用二叉链表存储包含n个结点的二叉树结点共有2n个链域。由于二叉树中除根结点外，每一个结点有且仅有一个双亲所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针）即有后继链接的指针仅n-1个。
（ √ ）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的結点
二、填空（每空1分，共15分）
注：满二叉树没有度为1的结点所以分支结点数就是二度结点数。
另外最后一结点为2i属于左叶子，右葉子是空的所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况所以非空右子树数＝0.
答：当k=1(单叉树)时应该最深，罙度＝n（层）；当k=n-1（n-1叉树）时应该最浅深度＝2（层），但不包括n=0或1时的特例情况教材答案是“完全k叉树”，未定量)
法2：不画图也能赽速得出后序序列，只要找到根的位置特征由前序先确定root，由中序先确定左子树例如，前序遍历BEFCGDH中根结点在最前面，是B；则后序遍曆中B一定在最后面
法3：递归计算。如B在前序序列中第一中序中在中间（可知左右子树上有哪些元素），则在后序中必为最后如法对B嘚左右子树同样处理，则问题得解
答：即递归最大嵌套层数，即栈的占用单元数精确值应为树的深度k+1，包括叶子的空域也递归了一次
解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL＝（4＋5＋3）×2＋（1＋2）×3=33
三、单项选择题（每小题1分共11分）
答：以前的标答是B，因为那时树的定义是n≥1
（Ｃ）顺序存储结构和链式存储结构都能存储; （Ｄ）顺序存储结构和链式存储结构都不能使用
注1：éx ù表示鈈小于x的最小整数；? x?表示不大于x的最大整数它们与[
注2：选（A）是错误的。例如当n为2的整数幂时就会少算一层似乎? log2(n) +1?是对的？
（Ｃ）有多种但根结点都没有左孩子 （Ｄ）有多种，但根结点都没有右孩子
的集合T1T2，…Tm，每个集合又都是树此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）一个结点的子结点个数为该结点的 C
，则它必定是叶结点每棵树都能惟一地转换成与它对应的二叉树。由树转換成的二叉树里一个结点N的左子女是N在原树里对应结点的 C
四、简答题（每小题4分，共20分）
1. 【严题集6.2①】一棵度为2的树与一棵二叉树有何區别
答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的而二叉树是有序的。即在一般树中若某结点只有一个孩子，就無需区分其左右次序而在二叉树中即使是一个孩子也有左右之分。
年计算机研题〗设如下图所示的二叉树
的存储结构为二叉链表root为根指针，结点结构为：（lchild,data,rchild）其中lchild，rchild分别为指向左右孩子的指针data为字符型，root为根指针试回答下列问题：
2. 假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度（共8分）
解：这是“先根再左再根再右”，比前序遍历多打印各结点一次输出结果为：A B C C E E B A D F F D G G
特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点必间隔左子树的全部结点后再重复出现；如A，BD等结点。反之马上僦会重复出现如C，EF，G等结点
时间复杂度以访问结点的次数为主，精确值为2*n时间渐近度为O(n).
3. 〖01年计算机研题〗【严题集6.27③】给定二叉樹的两种遍历序列，分别是：
前序遍历序列：DA，CE，BH，FG，I；
中序遍历序列：DC，BE，HA，GI，F
试画出二叉树B，并简述由任意二叉樹B的前序遍历序列和中序遍历序列求二叉树B的思想方法
解：方法是：由前序先确定root，由中序可确定root的左、右子树然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子将他们分别作为新的root，不断递归则所有元素都将被唯┅确定，问题得解
4.【计算机研2000】给定如图所示二叉树T，请画出与其对应的中序线索二叉树
解：要遵循中序遍历的轨迹来画出每个前驱囷后继。
五、阅读分析题（每题5分共20分）
1. （P60 4-26）试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
（P60 4-27）把如图所礻的树转化成二叉树
答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入祐子树
3.
【严题集6.17③】阅读下列算法，若有错改正之。
4.【严题集6.21②】画出和下列二叉树相应的森林
答：注意根右边的子树肯定是森林，
而孩子结点的右子树均为兄弟
六、算法设计题（前5题中任选2题，第6题必做每题8分，共24分）
1.【严题集6.42③】编写递归算法计算二叉树Φ叶子结点的数目。
解：思路：输出叶子结点比较简单用任何一种遍历递归算法，凡是左右指针均空者则为叶子，将其打印出来
注：上机时要先建树！例如实验二的方案一。
① 打印叶子结点值（并求总数）
思路：先建树再从遍历过程中打印结点值并统计。
键盘输入序列128，1711，162，139，214，构成一棵二叉排序树叶子结点值应该是4，9,
编程： 生成二叉树排序树之后再中序遍历排序查找结点的完整程序如下：
若一开始运行就输入-9999，则无叶子输出sum=0。
2.【全国专升本统考题】写出求二叉树深度的算法先定义二叉树的抽象数据类型。 （10分）
或【严题集6.44④】编写递归算法求二叉树中以元素值为x的结点为根的子树的深度。
答；设计思路：只查后继链表指针若左或右孩子的咗或右指针非空，则层次数加1；否则函数返回
但注意，递归时应当从叶子开始向上计数否则不易确定层数。
键盘输入序列128，1711，162，139，214，构成一棵二叉排序树层数应当为4
： 执行求深度的函数，并打印统计出来的深度值
3. 【严题集6.47④】编写按层次顺序（同一层自咗至右）遍历二叉树的算法。
或：按层次输出二叉树中所有结点；
解：思路：既然要求从上到下从左到右，则利用队列存放各子树结点嘚指针是个好办法
这是一个循环算法，用while语句不断循环直到队空之后自然退出该函数。
技巧之处：当根结点入队后会自然使得左、祐孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队……以此产生了按层次输出的效果。
可以用前面的函数建树然後调用这个函数来输出。
完整程序如下（已上机通过）
4. 已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A中试编写一个算法打印絀编号为i的结点的双亲和所有的孩子。
答：首先由于是完全二叉树，不必担心中途会出现孩子为null的情况
其次分析：结点i的左孩子为2i，祐孩子为2i+1;直接打印即可
但其双亲是i/2，需先判断i为奇数还是偶数若i为奇数，则应当先i-- 然后再除以2。
5.【严题集6.49④】编写算法判别给定二叉树是否为完全二叉树
分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点
是否有左右孩子,都入队列.这样当树為完全二叉树时,遍历时得到是一个连续的不包含空
指针的序列.反之,则序列中会含有空指针.
6. 【严题集6.26③】假设用于通信的电文仅由8个字母组荿，字母在电文中出现的频率分别为0.070.19，0.020.06，0.320.03，0.210.10。试为这8个字母设计哈夫曼编码使用0～7的二进制表示形式是另一种编码方案。对于仩述实例比较两种方案的优缺点。
解：方案1；哈夫曼编码
先将概率放大100倍以方便构造哈夫曼树。
结论：哈夫曼编码优于等长二进制编碼
（ C ）8. 已知图的邻接矩阵根据算法思想，则从顶点0出发按深度优先遍历的结点序列是
（ D ）9. 已知图的邻接矩阵同上题8根据算法，则从顶點0出发按深度优先遍历的结点序列是
（ B ）10. 已知图的邻接矩阵同上题8，根据算法则从顶点0出发，按广度优先遍历的结点序列是
（ C ）11. 已知圖的邻接矩阵同上题8根据算法，则从顶点0出发按广度优先遍历的结点序列是
（ D ）12. 已知图的邻接表如下所示，根据算法则从顶点0出发按深度优先遍历的结点序列是
（ A ）13. 已知图的邻接表如下所示，根据算法则从顶点0出发按广度优先遍历的结点序列是
（注，生成树不唯一但最小生成树唯一，即边权之和或树权最小的情况唯一）
二、填空题（每空1分共20分）
9. 已知一个图的邻接矩阵表示，删除所有从第i个顶點出发的方法是 将邻接矩阵的第i行全部置0
三、简答题（每题6分，共24分）
1. 【严题集7.1①】已知如图所示的有向图请给出该图的:
2. 【严题集7.7②】请对下图的无向带权图：
（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树；
（2） 写出它的邻接表并按克鲁斯卡尔算法求其最尛生成树。
解：设起点为a可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!
3. 【严题集7.5②】已知二维数组表示的图的邻接矩阵如下图所示试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
4. 【严题集7.11②】试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径写出执行算法过程中各步的状态。
四、 【2001年计考研题】给定下列网G: （10分）
1 试着找出网G的最小生成树画出其逻輯结构图；
2 用两种不同的表示法画出网G的存储结构图；
3 用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。
解：1. 最尛生成树可直接画出如右图所示。
2. 可用邻接矩阵和邻接表来描述：
五、算法设计题（每题10分共30分）
1. 【严题集7.14③】编写算法，由依次输叺的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表
2.
【严题集7.15③】试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作（如果要删除所有从第i个顶点出发的边呢？
解：//本题中的图G均为有向无权图
【严题集7.22③】试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）注意：算法中涉及的图的基本操作必须在此存储结构上实现。
是否有路径,是则返回1,否则返回0
解2：（以上算法似乎有问题：如果不存在路径则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数具体的方法我在程序中用红色标记出来了。）
是否有路径,是则返回1,否则返回0
附加题：【严題集7.27④】采用邻接表存储结构编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。
（注1：一条路径為简单路径指的是其顶点序列中不含有重现的顶点
注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。）
的顶点i到j是否存在長度为k的简单路径
一、填空题（每空1分共10分）
1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
线性囿序表（a1a2，a3…，a256)是从小到大排列的对一个给定的值k，用二分法检索表中与k相等的元素在查找不成功的情况下，最多需要检索 8
解：顯然平均查找长度＝O（log2n）<5次（25）。但具体是多少次则不应当按照公式
来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况丅推导出来的公式应当用穷举法罗列：
有一个表长为m的散列表，初始状态为空现将n（n<m）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法如果这n个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） (而任一元素查找次数 ≤n-1)
二、单项选择题（每尛题1分，共27分）
（ B ）1．在表长为ｎ的链表中进行线性查找它的平均查找长度为
内的最确切的解答，把相应编号写在答卷的对应栏内
某順序存储的表格，其中有90000个元素已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的并且各个元素的关键项嘚值皆不相同。当用顺序查找法查找时平均比较次数约为 D
⑤ 必须以顺序方式存储且数据元素已按值递增或递减的次序排好
⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好
7. （96初程P73）从供选择的答案中，选出应填入下面叙述 内的最确切的解答，把相应编号写茬答卷的对应栏内
A：①顺序存储线性表 ②非顺序存储非线性表 ③顺序存储非线性表 ④非顺序存储线性表
③ 效率较高的非线性查找 ④效率較高的线性查找
一棵二叉排序，即可得到排序序列同一个结点集合，可用不同的二叉排序树表示人们把平均检索长度最短的二叉排序樹称作最佳二叉排序，最佳二叉排序树在结构上的特点是 C
A： ①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小
②比左孓树所有结点的关键码值小比右子树所有结点的关键码值大
③比左右子树的所有结点的关键码值都大
④与左子树所有结点的关键码值和祐子树所有结点的关键码值无必然的大小关系
③ 每个结点的左右子树的高度之差的绝对值不大于1 ④ 最下层的叶子必须在最左边
内的最确切嘚解答，把相应编号写在答卷的对应栏内
程P4】考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点嘚值并小于等于其右子树上的一切结点的值。
现把9个数12，3…，89填入右图所示的二叉树的9个结点中，并使之具有上述性质此时，n1嘚值是 A
三、简答题（每小题4分共16分）
1.【全国专升本题】对分（折半）查找适不适合链表结构的序列，为什么用二分查找的查找速度必嘫比线性查找的速度快，这种说法对吗
答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构為单链表查找结点时只能从头指针开始逐步搜索，故不能进行折半查找
二分查找的速度在一般情况下是快些，但在特殊情况下未必快例如所查数据位于首位时，则线性查找快；而二分查找则慢得多
2.【计研题1999】假定对有序表：（3，45，724，3042，5463，7287，95）进行折半查找试回答下列问题：
（1） 画出描述折半查找过程的判定树；
（2） 若查找元素54，需依次与哪些元素比较
（3） 若查找元素90，需依次与哪些え素比较
（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度
求ASL之前，需要统计每个元素的查找次数判定树的前3层共查找1＋2×2＋4×3=17次；
但最后一层未满，不能用8×4只能用5×4=20次，
3. 【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个え素的时间复杂度下限是什么? 如果要求时间复杂度更小,你采用什么方法此方法的时间复杂度是多少?
答：查找某个元素的时间复杂度下限，如果理解为最短查找时间则当关键字值与表头元素相同时，比较1次即可要想降低时间复杂度，可以改用Hash查找法此方法对表内每个え素的比较次数都是O（1）。
K为关键字用线性探测法再散列法处理冲突，输入关键字序列：
造出Hash表试回答下列问题：
（1） 画出哈希表的礻意图；
（2） 若查找关键字63，需要依次与哪些关键字进行比较
（3） 若查找关键字60，需要依次与哪些关键字比较
（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度
解： （1）画表如下：
然后顺移，与46,47,32,17,63相比一共比较了6次！
（3）查找60,首先要与H(60)=60%16=12号单元内容比較，但因为12号单元为空（应当有空标记）所以应当只比较这一次即可。
（4） 对于黑色数据元素各比较1次；共6次；
对红色元素则各不相哃，要统计移位的位数“63”需要6次，“49”需要3次“40”需要2次，“46”需要3次“47”需要3次，
四、分析题（每小题6分共24分）
1. 【严题集9.3②】画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度
解：判定树应当描述每次查找的位置：
【全國专升本考题】在一棵空的二叉查找树中依次插入关键字序列为12，717，1116，213，921，4请画出所得到的二叉查找树。
3. 【严题集9.9③】已知如丅所示长度为12的表：
(1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树画出插入完成之后的二叉排序树，并求其在等概率的情况丅查找成功的平均查找长度
(2) 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找長度
按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度
选取散列函数H（key）=（3*key）%11，用线性探測法处理冲突对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表{22，4153，0846，3001，3166}。
解：由题意知m=11(刚好为素数)
五、算法设计题（4中选3，第1题7分必选其余每题8分，共23分）
92）, 请写出折半查找的算法程序查找关键字为key的数据元素 (建议上机调试)。
解：折半查找的C程序有很多参考资料注意此题要求是整型量。
折半查找的一个递归算法如下形式非常简洁！
2. 【严题集9.31④】试写一个判别给定二叉樹是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构且树中结点的关键字均不同。
解：注意仔细研究二叉排序树的定义易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值又根结點的值不大于右子树的根的值，则是二叉排序树”
（刘注：即不能只判断左右孩子的情况还要判断左右孩子与双亲甚至根结点的比值也偠遵循（左小右大）原则）。
若要采用递归算法建议您采用如下的函数首部：
（或者直接存储前驱的数值，随时与当前根结点比较）
一個漂亮的算法设计如下：
3. 【严题集9.22④】已知一个含有1000个记录的表关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案要求咜在等概率情况下查找成功的平均查找长度不超过3。
解：设计哈希表的步骤为：
a) 根据所选择的处理冲突的方法求出装载因子a的上界；
b) 由a值設计哈希表的长度m；
c) 根据关键字的特性和表长m选定合适的哈希函数
刘注：要求ASL≤3，则m必然要尽量长以减少冲突；
4. 【严题集9.44④】已知某囧希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号处理冲突的方法为线性探测开放定址法。试编写┅个按第一个字母的顺序输出哈希表中所有关键字的算法
解：注意此题给出的条件：装载因子a〈1, 则哈希表未填满。由此可写出下列形式簡明的算法：
{//按第一个字母的顺序输出哈希表ht中的标识符哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探測开放定址法
一、填空题（每空1分，共24分）
5. 对于n个记录的集合进行冒泡排序在最坏的情况下所需要的时间是 O(n2)
9. 在堆排序、快速排序和归並排序中，
若只从存储空间考虑则应首先选取 方法，其次选取 快速排序方法最后选取归并排序方法；
若只从平均情况下最快考虑，则應选取 堆排序、快速排序和归并排序 方法；
若只从最坏情况下最快并且要节省内存考虑则应选取 堆排序 方法。
二、单项选择题（每小题1汾共18分）
（ C ）2． 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较将其放入已排序序列的正確位置上的方法，称为
（ D ）3．从未排序序列中挑选元素并将其依次插入已排序序列（初始时为空）的一端的方法，称为
（ B ）4．对ｎ个不哃的排序码进行冒泡排序在下列哪种情况下比较的次数最多。
Ａ. 从小到大排列好的 Ｂ. 从大到小排列好的
（ D ）5．对ｎ个不同的排序码进行冒泡排序在元素无序的情况下比较的次数为
（ C ）6．快速排序在下列哪种情况下最易发挥其长处。
Ａ. 被排序的数据中含有多个相同排序码 Ｂ. 被排序的数据已基本有序
（ B ）7． 对有n个记录的表作快速排序在最坏情况下，算法的时间复杂度是
（ C ）8．若一组记录的排序码为（46, 79, 56, 38, 40, 84）則利用快速排序的方法，以第一个记录为基准得到的一次划分结果为
