一、简单题：
1、在单链表中，头结点是必不可少的？。
2、链队列q为空的条件是什么？
3、如果一个二叉树中没有度为1的结点，它是不是完全二叉树？
4、具有n个顶点和n-1条边的无向连通图是否存在环路？
5、判断一个有向图是否存在回路的方法有哪些？
6、在一棵二叉排序树t中，先插入结点n，然后再删除结点n，得到的新的二叉排序树t1，则t 和 t1 相同？
7、在采用线性探测法处理冲突的散列表中，所有同义词存储表中形成局部堆积？
8、有n个顶点的无向图，最少有多少条边？最多有多少条边？
9、若采用冒泡排序对关键字序列，从小到大进行排序，则需要交换的总次数为？
10、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是什么？
11、在有n个叶子结点的哈夫曼树中，其结点总数为多少？
12、如果具有n个顶点的有向图能够进行拓扑排序，那么有向图中最少有多条弧？最多有多少条弧？
13、设一个栈的输入序列为abcd，则所得到的输出序列不可能有哪些？
14、已知一棵二叉树的中序序列为：bdaec，后序序列为：dbeca，则该二叉树的先序序列为？
15、用折半查找法在有序表中查找44时，需进行的比较次数为？
16、假设循环队列以内存地址100~199存储空间，每个队列元素占用2个字节，若队头指针值为188，队尾指针为122，则当前队列中元素个数是多少？
二、简答题：
1、已知一组关键字k=，请判断此序列是否为堆？如果不是，请调整为堆；并给出输出第一个元素后的调整结果序列。
2、假设通信电文使用的字符集为，若这些字符在一篇电文**现的频率分别为：13，35，11，19，8，6。
1）根据各字符在该电文出现频率，构造相应的huffman树。
2）根据你构造的哈夫曼树，给出各字符的哈弗曼编码；
3）求该哈夫曼树的带权路径长度。
3、已知一个无向图g如图所示。
(1)、请写出图 g 的邻结表存储结构；
2)、根据写出的邻结表，求出从v1开始。
的bfs和dfs遍历序列及生成树；
(3)、根据写出的邻结表，画出图g的最小生成树。
4、设散列表的存储空间为[0..6]，设hash函数为h(k) =k mod 7, 采用建立公共溢出区解决冲突，现给定关键字序列为13，6，17，19，13，3，25，28，12，16。
(1)请画出散列表；
(2)求出查找各关键字的比较次数；
(3)计算在等概率情况下，查找成功的平均查找长度。
5、 已知一棵树。
(1) 画出该树转换成二叉树的结果；
(2) 写出该树的先根遍历序列和后根遍历序列；
三、算法设计：
已知二叉树采用二叉链表存储，其结点结构定义为：
typedef struct node
（1）该序列不是堆序。
（2）调整成大顶堆为：34，26，20，18，24，11，14，16，5，9
（3）输出第一个元素后：26，24，20，18，9，11，14，16，5，34
2、(10分) 解：
1）见右图。
2）字母的哈夫曼编码依次为：
0110, 10, 110, 111, 00, 0111和010
3）带权路径长度：wpl=253
3、（15分）解： 略。
4、(8分)解：关键字序列为11，6，17，14，9，3，24，18，23，16。
1) 散列表如图所示，其中双线以下为公共溢出区。
2) 关键字： 11，6，17，14，9，3，24，18，23，16
比较次数： 1， 1，1， 1， 1，2，3， 4， 5， 6
3）平均查找长度：25/10=2.5次。
5、（5分）解：
1) 略。2) 先根遍历序列：abcefijghkd
后根遍历序列：beijfgkhcda
四、算法设计(15分)：
1、（5）答：该算法程序完成将单链表的首结点（即第一个结点）移到链尾（即作为最后一个结点）。或简单地说：将链头移到链尾。
2、（10）解：算法如下。
int depth(bitree t){
int i,j;
if (t){
i = depth(t->lchild);
j = depth(t->rchild);
if ( i >=j ) return (i + 1);
else return (j + 1);
else return 0
//end of depth()
2019考研数据结构辅导
掌握基本概念。1 元素 数据基本单位。2 逻辑结构。定义 元素及关系，与计算机无关，只是实际问题的数学抽象表示。分类 集合 线性结构 树 图。3 存储结构。定义 逻辑结构在计算机中的表示 内存 分类 顺序存储 数组 链式存储 链表 4 算法及效率。常见的基础算法。定义 计算机 解决问题的有限步骤。效...
2019数据结构
下面我们来解析一下知识点。线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入 删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。栈 队列和数组可以考查的知识点相比链表来说要多一些。最基本的，是栈与...
数据结构2019级数据结构大作业
2011级数据结构大作业。1 公园导游图。给出一张某公园的导游图，用图的顶点表示各个景点 景点个数大于等于30 每个景点有属性值 h，t，c 其中h表示游览完成这个顶点给游客带来的happiness，t表示游览这个景点需要的时间，c表示游览这个景点需要的费用，顶点之间的边表示路径 边具有属性值w，表...