蜂考数据结构答案
1.什么是数据结构?
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。结构包括逻辑结构和物理结构。
数据的逻辑结构包括4种
(1)集合：数据元素之间除了有相同的数据类型再没有其他的关系
(2)线性结构：数据元素之间是一对一的关系 ——线性表、栈、队列
(3)树形结构：数据元素之间是一对多的关系
(4)图状结构：数据元素之间是多对多的关系。
物理结构包括顺序存储结构和链式存储结构。
2.解释一下顺序存储与链式存储
顺序存储结构是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。链式存储结构是用任意的存储空间来存储数据元素，不可以进行随机访问，访问效率较低。
3.头指针和头结点的区别?
头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。 头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。
4.线性结构的特点
(1)集合中必存在唯一的一个"第一个元素";
(2)集合中必存在唯一的一个"最后的元素";
(3)除最后元素之外，其它数据元素均有唯一的"后继";
(4)除第一元素之外，其它数据元素均有唯一的"前驱"。
5.数组和链表的区别?
从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况。链表能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。
从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。链表是链式存储结构，存储空间不是必须连续的，可以是任意的，访问必须从前往后依次进行，访问效率较数组来说比较低。
如果从第i个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是O(n)，而单链表来说只需要在第一次寻找i的位置时时间复杂度为O(n)，其余的插入和删除操作时间复杂度均为O(1)，提高了插入和删除的效率。
计算机学科专业基础综合数据结构-内部排序
(总分80,考试时间90分钟)
一、单项选择题
1. 对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15)；则采用的是____排序。
A. 选择 B. 快速
C. 希尔 D. 冒泡
2. 下列4个序列中，哪一个是堆____。
A. 75，65，30，15，25，45，20，10
B. 75，65，45，10，30，25，20，15
C. 75，45，65，30，15，25，20，10
D. 75，45，65，10，25，30，20，15
3. 一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为____。
A. (38，40，46，56，79，84)
B. (40，38，46，79，56，84)
C. (40，38，46，56，79，84)
D. (40，38，46，84，56，79)
4. 数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中____的两趟排序后的结果。
A. 选择排序 B. 冒泡排序
C. 插入排序 D. 堆排序
5. 对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为____。
(1)84 47 25 15 21 (2)1 5 47 25 84 21
(3)15 21 25 84 47 (4)1 5 21 25 47 84
则采用的排序是____。
A. 选择 B. 冒泡
C. 快速 D. 插入
6. 若用冒泡排序对关键字序列{18，16，14，12，10，8}，进行从小到大的排序，所需进行的关键字比较总次数是____。
A. 10 B. 15
C. 21 D. 34
7. 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为____。
《数据结构与算法》实验报告
一、 需求分析
问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
基本要求：
（l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
（2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。数据测试：
二．概要设计
1. 程序所需的抽象数据类型的定义：
typedef int BOOL; //说明BOOL是int的别名
typedef struct StudentData { int num; //存放关键字
}
Data; typedef struct LinkList { int Length; //数组长度
Data Record[MAXSIZE]; //用数组存放所有的随机数
} LinkList int RandArray[MAXSIZE]; //定义长度为MAXSIZE的随机数组
void RandomNum() //随机生成函数
void InitLinkList(LinkList* L) //初始化链表
BOOL LT(int i, int j,int* CmpNum) //比较i和j 的大小
数据结构--内部排序算法
1、下列排序算法中，_____________排序在某趟结束后不一定能选出一个元素放到其最终的位置上。
（1）选择 （2）冒泡 （3）归并 （4）堆
2、下列排序算法中，依次将待排序列中的元素和前面有序序列合并为一个新的有序序列的排序算法是___________________。
（1）直接插入排序 （2）冒泡排序 (3)快速排序 （4）直接选择排序
3、下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是______________。
（1）直接插入排序列 （2）快速排序 （3）直接选择排序 （4）堆排序
4、依次将待排序序列中的元素和有序子序列合并一个新的有序子序列的算法是______________。
（1）快速排序 （2）插入排序 （3）冒泡排序 （4）堆排序
5、已知数据表A中每个元素距其最终位置不远，则采用_____________排序算法最节省时间。
（1）堆排序 （2）插入排序 （3）快速排序 （4）直接选择排序
6、下列排序算法中，_______________算法可能会出现下面情况，在最后一趟开始之前，所有元素都不在其最终的位置上。
（1）堆排序 （2）冒泡排序 （3）快速排序 （4）插入排序
7、数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用____________排序算法最节省时间。
（1）堆排序 （2）希尔排序 （3）快速排序 （4）直接选择排序
8、下列算法中，____________每一趟都能选出一个元素放在其最终位置上，并且是不稳定的。
（1）冒泡排序 （2）希尔排序 （3）直接选择排序列 （4）直接插入排序
9、下列排序算法中，某一趟结束后未必能选出一个元素放在其最位置上的是__________________。
