数据结构期末复习题库

《数据结构期末复习题库》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1.、选择题1)（无序或有序）顺序表中插入元素的时间复杂度：__O(n)__。2)带头结点的链表，如何判断其是否为空链表：__head->data=0___。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针.3)数组形式存放的队列，其大小为n，最多可存放多少个元素（即在具有n个单元的循环队列中，队满时共有多少个元素）：_n-1_。常用空闲单元法（人为浪费一个单元，则队满特征可改为front=(rear+1)%N）：即front和rear之一指向实元素，另一指向

2、空闲元素。4)栈操作的原则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。5)树的前驱结点：在一棵树中，每个结点称为它的每棵子树的根结点的前驱结点（即该结点的上层的那个结点(直接前驱)）。如孩子的前驱结点是双亲结点6)二叉树存储是用二叉链表，二叉树的空指针域与非空指针域的关系：具有n个结点的二叉链表中，共有2n个指针域。其中有n-1个非空链表，用来指示结点的左孩子和右孩子，其余的n+1个指针域为空。7)折半（二分）查找的平均查找长度：当n很大时，ASL=log2(n+1)-1可以作为二分查找成功时的平均查找长度。8)有向图的度的

3、计算：即顶点的度的计算。入度和出度：顶点v的入度是以v为终点的有向边的条数,记作ID(v)；顶点v的出度是以v为始点的有向边的条数,记作OD(v)；在有向图中,顶点的度等于该顶点的入度与出度之和。9)列出各种排序中，最坏的时间复杂度：平均时间最差最佳辅助空间稳定性直接插入O(n2)O(n2)O(n)O(1)稳定起泡排序O(n2)O(n2)O(n)O(1)稳定直接选择O(n2)O(n2)O(n2)O(1)不稳定希尔排序O(n1.5)O(1)不稳定快速排序O(nlog2n)O(n2)同平均O(log2n)不稳定堆排序O(nlog2n)同平均同平均O(1)不稳定归并排序

4、O(nlog2n)同平均同平均O(n)稳定基数排序O(d(n+r))同平均同平均O(n+r)稳定在最坏情况下，快速排序法的时间复杂度为O(n2)，变为排序最慢的方法。10)顺序存储与链式存储的优缺点：2、判断题1)数组与元素之间的关系：若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*（i-1）2)链式的物理结构与逻辑结构的相

5、关判断：链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。3)循环单链表队列是否一定需要头指针和尾指针：一个队列需要两个分别指示队头和队尾的指针（头指针和尾指针）才能唯一确定；解决假溢出的途径———采用循环队列。1)递归法的优点是：递归可以代替循环，但是，不是所有的可计算问题都可由递归转换为循环。递归清晰易懂，易于设计算法，具有较高的开发效率，所设计的程序具有更好可读性和可维护性。2)广义表：广义表是线性表的推广，也称为列表（lists）记为：LS=(a1,a2,……，an)在广义表中约定：①　第一个元素是表头，而其余元素

6、组成的表称为表尾；②　用小写字母表示原子类型，用大写字母表示列表。③　ai区别于线性表中只限于是单个元素，而在广义表中或者是单个元素或者是一个广义表，分别称为广义表的原子和子表。注意：a.为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。b.广义表是递归定义的。因为在描述广义表时又用到了广义表的概念。3)堆排序（选择排序中的一种，考堆排序的操作）：堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序.。堆

7、排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？第二个问题解决方法——筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。4)二叉树遍历的时间复杂度：三种遍历具有相同的时间复杂度和空间复杂度。若二叉树的结点个数为n，则算法的时间复杂度为O（n）。5)邻接矩阵的大小有什么决定：邻接矩阵表示各个顶点之间关系，设图A=(V,E)有n个顶点，则图的邻接矩阵是一个

8、二维数组A