练习。1. 内存中一片连续空间（不妨假设地址从1到m），提供给两个栈s1和s2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。
2. 叙述前序和中序遍历二叉树的步骤；一棵前序序列为1,2,3,4的二叉树，其中序序列可能是4,1,2,3吗？设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树。
3. 设有一个关键码的输入序列 ,
(1) 从空树开始构造平衡二叉搜索树， 画出每加入一个新结点时二叉树的形态。若发生
不平衡， 指明需做的平衡旋转的类型及平衡旋转的结果。
2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度。
4. 设散列表为ht[0..12],即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：
h0(key)=key%13; 注：％是求余数运算（＝mod）
hi=(hi-1+rev(key+1)%11+1)%13; i=1,2,3,…，m-1
其中，函数rev（x）表示颠倒10进制数x的各位，如rev(37)=73,rev(7)=7等。若插
入的关键码序列为。
(1)试画出插入这8个关键码后的散列表。
2)计算搜索成功的平均搜索长度asl。
5. 下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。
6. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：
（1）归并排序每归并一次书写一个次序。
（2）快速排序每划分一次书写一个次序。
（3）堆排序先建成一个最大堆，然后每从堆顶取下一个元素后，将堆调整一次。
7. 假设用于通讯的电文由 5个字母组成，a b c d e f ，字母在电文中的出现频率分别为 0.09，0.
12，0.07，0.22，0.
23，0.27，画出哈夫曼树，并写出各个字符的哈夫曼编码。（左子树根节点值不大于右子树根节点值）
8. 已知序列（50，72，43，85，75，20，35，45，65，30），请以顺序插入方式构造二叉排序树，并画出删除结点72之后的二叉排序树。
9. 已知带权无向图g的邻接矩阵是a。
1) 画出图g；
2) 分别画出一颗从v1出发的深度优先生成树和广度优先生成树；
3) 画出一棵最小生成树。
10. 图的深度优先搜索类似于bfs,不同之处在于使用栈代替bfs中的队列，进出队列的操作改为入出栈的操作。即当一个顶点的一个邻接点被搜索后，下一个搜索的出发点应该是最近入栈(栈顶)的顶点。
用深度优先搜索方法搜索下图，设初始出发点为1,1) 画出搜索过程中栈的变化。
2) 写出顶点的访问次序（当从某顶点出发搜索他的邻接点时，请按邻接点序号递增序搜索，以使答案唯一）。
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...