二、简答

1. 什么是数据结构？按数据关系如何分类？列举出所学的数据结构，并分类。（7分）

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合

     按数据间存在的关系数据结构通常分为四类。

⑴ 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

⑵ 线性结构：结构中的数据元素之间存在着一对一的线性关系。

⑶ 树形结构：结构中的数据元素之间存在着一对多的层次关系。

⑷ 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。

线性表 栈 队列 树 二叉树 图 查找表 排序表

按逻辑分

1. 静态查找表与动态查找表的区别是什么？列举四种静态查找表，说明不等概率的有序表查找时，应该选用哪一种。（7分）

  操作不同  动态查找表 查询检索插入和删除  区别在于动态查找表可以插入删除

            静态查找表  查询检索

 简单查找 折半查找 索引查找 不等概率的静态查找树

选用 静态数表

1. 简述树的存储方法有哪些，树是如何转换成二叉树的。（6分）

   双亲表示 孩子表示 孩子兄弟表示

   孩子兄弟表示转换

1. 树的有几种存储形式分别叙述，树和森林是如何转换二叉树的。

    三种

   孩子兄弟表示转换

   森林里每棵树都转换为二叉树 特点是没有右孩子 用另外一棵树接到右孩子上

1. 设有2000个无序的元素，希望用最快速度挑选出其中前10个最大的元素。分析在以下的排序方法中，采用哪种方法最好?为什么?

     快速排序，堆排序，归并排序，基数排序的Shell排序。

    用选择排序最快 堆排序是选择排序

1. 线性表的顺序存储结构与链式存储结构在操作上的特点是什么？

顺序：优点：可随机存取表中任一元素。因为有下标可以操作可以快速的定位到指定位置的元素，但是不知道位置的话也需要顺序遍历。

缺点：插入或删除操作时，需大量移动元素。合适在很少进行插入和删除运算的情况下。

链式：优点：插入和删除不需要移动插入时只需要对插入位置后的一个元素进行操作，不需要大量的移动元素。空间有效利用高。

缺点：大量访问操作时不如顺序存储结构，因为每次都需要从头开始遍历整个线性表直到找到相应的元素为止。

1. 当你为解决某一问题而选择数据结构时，应从哪几个方面考虑？

逻辑结构 物理结构 操作的快慢 效率

1. 对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？

   链式存储结构  因为线性表长度动态改变，总数也变化，链式结构适合插入删除，不需要大量移动元素。

1. 顺序队列的假溢出是怎么产生的？如何知道循环队列是空还是满？

一般一维数组队列的尾指针已经到了队尾上界，不能再有入队的操作。但其实数组中还有空位置，但元素还加不进去，这就产生了假溢出。

通过计数，count
有元素入队时，count++
队空：count==0
队满：count==maxsize

1. 试描述数据结构中抽象数据类型的概念与程序设计语言中数据类型的概念的区别。

   抽象数据类型（ADT）是一个数据结构以及定义在该结构上的一组操作的总称

1. 对于线性表的两种存储结构（顺序 链式），若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种数据结构？试说明理由。

    顺序存储结构   因为很少进行插入删除

1. 二叉树中度为0的结点数与度为2的结点数关系论证。

设二叉树中总结点个数为n，分枝总数为B, 叶结点数为n0，度为2的结点数为n2，一度结点为n1 则

n=n0+n1+n2   ①

B=n-1        ②

B=n1+2n2     ③

将②代入③得

n=n1+2n2+1   ④

将④代入①得

n0=n2+1

1. 若较频繁地对一个线性表进行插入和删除操作,该线性表宜采用何种存储结构?为什么?

    链式存储  链式存储方便进行插入删除

14.如果一棵哈夫曼树T有n0个叶子结点，那么，树T有多少个结点？要求给出求解过程。

   构造n0-1 次

15．假设二叉树包含的结点数据为1,3,7,2,12。

(1)画出两棵高度最大的二叉树;

(2)画出两棵完全二叉树,要求每个双亲结点的值大于其他孩子结点的值。

16．对于稠密图和稀疏图,采用邻接矩阵和邻接表哪个更好些?？

   邻接矩阵表示稠密图很方便

   邻接表表示稀疏图

1. 在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动,从而认为该排序算法是不稳定的,这种说法对吗?为什么?

这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前后发生了变化，而题中叙述和排序中稳定性的定义无关

  

1. 有n个顶点的无向连通图至少有多少条边?有n个顶点的有向强连通图至少有多少条边?试举例说明?

  N-1条

1. 以下概念的区别:拓扑排序与冒泡排序。 （7 ）

   拓扑排序，是有向图的顶点依照弧的走向，找出一个全序集的过程，主要是根据与顶点连接的弧来确定顶点序列；

冒泡排序是借助交换思想通过比较相邻结点关键字大小进行排序的算法。

1. 什么是算法?算法的5个特性是什么?试根据这些特性解释算法与程序的区别。

  解决问题的方法和步骤

  五大特性:1.有穷性2.确定性3.可行性 4.有输入5.有输出

区别：1.算法是执行时候运行的有穷性，程序只是一段实现算法的代码。

2.算法对于特定的输入有特定的输出，程序提供了确定算法结果的平台。
      3.算法需要考虑设计的可能，程序则具体是实现算法上的设计。

4.算法有输入，算法的输入依靠程序的平台提供。

5.算法有输出

21．说明在线性表的链式存储结构中,头指针与头结点之间的根本区别;头结点与首元结点的关系。

  头指针指链表的指针,若链表有头结点则是链表的头结点的指针,头指针具有标识作用,故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的,放在第一元素结点之前,其数据域一般无意义(当然有些情况下也可存放链表的长度、用做监视哨等等),有头结点后,对在第一元素结点前插入结点和删除第一结点,其操作与对其它结点的操作统一了。而且无论链表是否为空,头指针均不为空。

首元结点也就是第一元素结点,它是头结点后边的第一个结点。

1. 在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动,从而认为该排序算法是不稳定的,这种说法对吗?为什么?

  有相同题

1. 什么是算法?算法的5个特性是什么?试根据这些特性解释算法与程序的区别。

   有同题

24．为什么在单循环链表中设置尾指针比设置头指针更好?

   带头指针的循环链表需要遍历整个数组才能找到尾结点，而带尾指针的循环链表只需要.next就能找到头指针。

25．使用二叉链表表示法，画出下图所示二叉树的存储表示。

（7分）

1. 在结点个数为n(n>1)的各棵树中,高度最小的树的高度是多少?它有多少个叶结点?多少个分支结点?高度最大的树的高度是多少?它有多少个叶结点?多少个分支结点?（7分）

    高度最小的树的高度是1,有2层，有n-1个叶结点，1个分支结点;

高度最大的树的高度是n-1,有n层，有1个叶结点，n-1个分支结点

27．若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，查找不成功，即表中没有关键字等于给定值k的记录；两者在等概率时，平均查找长度是否相同?说明原因。（6分）

 相同 因为所有

如果k值在数据之间 查不了很多次

如果超界  查找概率相同

28．在n个结点的顺序表中删除一个结点需平均移动多少个结点？具体移动次数取决于什么条件？（6分）

29．给定集合{15,3,14,2,6,9,16,17}，构造相应的哈夫曼树，计算它的带权路径长度。

30．若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，查找成功，且表中有若干个关键字等于给定值k的记录，一次查找要求找出所有记录，两者在等概率时，平均查找长度是否相同?说明原因。（7分）

  不相同 顺序表相同的都挨着 有序的挨着