计算机二级C语言公共基础1数据结构全解.ppt

1.7 查找技术 4.为了对有序表进行对分查找，则要求有序表 A) 只能顺序存储 B) 只能链式存储 C) 可以顺序存储也可以链式存储 D) 任何存储方式 1.8 排序技术 排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。1.交换类排序法： （1）冒泡排序法， 最坏情况下，需要比较的次数为n(n-1)/2； （2）快速排序法。 最坏情况下，需要比较的次数为n(n-1)/2； 1.8 排序技术 2.插入类排序法： （1）简单插入排序法， 最坏情况需要n(n-1)/2次比较； （2）希尔排序法， 最坏情况需要O(n1.5)次比较。 1.8 排序技术 3.选择类排序法： （1）简单选择排序法, 最坏情况需要n(n-1)/2次比较； （2）堆排序法， 最坏情况需要O(nlog2n)次比较。 相比以上几种(除希尔排序法外)，堆排序法的时间复杂度最小。 1.8 排序技术 1.对长度为n的线性表排序，在最坏情况下，比较次数不是n(n－1)/2的排序方法是(　　)。 A) 快速排序 B) 冒泡排序 C) 直接插入排序 D) 堆排序 1.8 排序技术 2.下列排序方法中，最坏情况下比较次数最少的是(　　)。 A) 冒泡排序 B) 简单选择排序 C) 直接插入排序 D) 堆排序 1.8 排序技术 3.对长度为n的线性表作快速排序，在最坏情况下，比较次数为 A) n B) n-1 C) n(n-1) D) n(n-1)/2 1.8 排序技术 4.对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为 A) 9 B) 10 C) 45 D) 90 1.8 排序技术 5.在最坏情况下 A) 快速排序的时间复杂度比冒泡排序的时间复杂度要小 B) 快速排序的时间复杂度比希尔排序的时间复杂度要小 C) 希尔排序的时间复杂度比直接插入排序的时间复杂度要小 D) 快速排序的时间复杂度与希尔排序的时间复杂度是一样的 1 栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。入栈运算即在栈顶位置插入一个新元素，退栈运算即是取出栈顶元素赋予指定变量。栈为空时，栈顶指针top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为top=m+1，当top=20时，元素依次存储在单元20：m中，个数为m-19，C选项正确。 * 循环队列是队列的一种顺序存储结构，用队尾指针rear指向队列中的队尾元素，用排头指针指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素，队列初始状态为front=rear=m，当front=15，rear=20时，队列中有5个元素，比较次数为4次，A选项正确。 * 循环队列是队列的一种顺序存储结构，用队尾指针rear指向队列中的队尾元素，用排头指针指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素，队列初始状态为front=rear=m，当front=20，rear=15时，队列中有m-20+15=m-5个元素，比较次数为m-6次，D选项正确。 * 1.5 线性链表 8.下列叙述中正确的是 A) 循环队列属于队列的链式存储结构 B) 双向链表是二叉树的链式存储结构 C) 非线性结构只能采用链式存储结构 D) 有的非线性结构也可以采用顺序存储结构 1.5 线性链表 9.下列叙述中正确的是 A) 在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构 B) 在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构 C) 在链表中，如果每个结点有两个指针域，则该链表一定是线性结构 D) 在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构 1.5 线性链表 10.下列叙述中正确的是 A) 链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构 B) 线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针 C) 线性表的链式存储结构中，每个结点只能有一个指向后件的指针 D) 线性表的链式存储结构中，叶子结点的指针只能是空 1.5 线性链表 11.下列叙述中错误的是 A) 在双向链表中，可以从任何一个结点开始直接遍历到所有结点 B) 在循环链表中，可以从任何一个结点开始直接遍历到所有结点 C) 在线性单链表中，可以从任何一个结点开始直接遍历到所有结点 D) 在二叉链表中，可以从根结点开始遍历到所有结点 1.6 树与二叉树 1.树及其相关概念： 树：是一