东软数据结构复习试题

东软数据结构期末复习资料1.2.根据数据的逻辑结构，可将数据结构分为哪几类？每一类的特性是什么？答:（1）集合：集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其他关系，它们之间的关系称为是松散性的。（2）线性结构：数据元素之间存在”一对一”的关系。即若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前趋和一个后继。（3）树形结构：数据元素之间存在”一对多”的关系。即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。（4）图形结构：数据元素之间存在“多对多”的关系。即若结构非空，则在这种数据结构中任何结点都可以有多个前驱和后继。3.什么是顺序表？什么是链表?比较二者的优缺点。答：（1）顺序表：所谓顺序表就是顺序存储的线性表。顺序存储是用一组地址连续的存储单元依次存放线性表中各个数据元素的存储结构。（2）链表：采用链式存储方式存储的线性表称为链表，链表中每一个结点包含存放数据元素值的数据域和存放指向逻辑上相邻结点的指针域。若一个结点中只包含一个指针域，则称此链表为单链表。（3）优缺点：顺序表是最简单的数据组织方法，具有易用，空间开销小以及可对数据元素进行高效随机存取的优点，但也具有不便于进行插入和删除操作和需预先分配存储空间的缺点，它是静态数据存储方式的理想选择。链表具有的优缺点正好与顺序表相反，链表适用于经常进行插入和删除操作的线性表，但也具有不便于按位序号进行存取操作，只能进行顺序存储的缺点，它是动态数据存储方式的理想选择。4.什么是栈？什么是队列？试分别举两个应用实例。答:（1）栈是一种特殊的线性表，但栈的插入和删除操作只允许在表的尾端进行。例，网页访问历史的记录保存，文本编辑器中undo序列的保存。（2）队列是一种特殊的线性表，队列只允许在表尾插入数据元素，在表头删除数据元素，所以队列也是一种操作受限的特殊的线性表，它具有先进先出或后进后出的特性。例，操作系统中的各种数据缓冲区的先进先出管理，应用系统中各种任务请求的排队管理。5.什么是算法？算法具有哪五种性质？算法设计的目标有哪些？答：（1）算法是对特定问题求解步骤的一种描述。（2）性质：有穷性，确定性，有效性，输入，输出。（3）目标：正确性，可读性，健壮性，高效性6.二叉树的概念。答：二叉树是由n(n=0)个结点所构成的有限集合。当n=0时，这个集合为空，此时的二叉树为空树；当n0时，这个集合是由一个根结点和两个互不相交的分别称为左子树和右子树的二叉树构成。7.简述冒泡排序的思想。答：将待排序的数组看成从上到下排放，把关键字值较小的记录看成“较轻的”，关键字值较大的记录看成“较重的”，较小关键字值的记录好像水中的气泡一样，向上浮：较大关键字值的记录如水中的石块向下沉，当所有的气泡都浮到了相应的位置，并且所有的石块都沉到了水中，排序就结束了。8.简述直接选择排序的思想。答：在第一趟中，从n个记录中找出关键字值最小的记录与第一个记录交换：在第二趟中，从第二个记录开始的n-1个记录中再选出关键字值最小的记录与第二个记录交换：以此类推，在第i趟中，从第i个记录开始的n-i+1个记录中选出关键字值最小的记录与第i个记录交换，直到整个序列按关键字值有序为止。9.简述二分查找的思想。答：首先取整个有序表的中间记录的关键字值与给定值相比较，若相等，则查找成功：否则以位于中间位置的数据元素为分界点，将查找表分成左右两个子表，并判断待查找的关键字值key是在左子表还是在右子表，再在左或右子表中重复上述步骤，直到找到关键字值为key的记录或子表长度为0。