数据结构与算法练习题及部分答案

"该文档是一份包含多项选择题和填空题的IT相关练习题目，主要涉及数据结构和算法的知识，包括链表、栈、队列、数组、二叉树以及排序算法。" 1. 单链表的判断条件：题目提到，判断一个含头结点的单链表是否为空的条件是`head->next==NULL`，这表明链表没有下一个节点，因此为空。 2. 循环单链表的尾指针：非空的循环单链表的尾指针`p`满足`p->next==head`，表示尾节点的下一个节点指向头节点，形成循环。 3. 链表的特点：链表不具有随机访问任一元素的特性，因为要访问链表中的某个元素，必须从头开始遍历到相应位置。 4. 链式存储结构与逻辑顺序：链式存储结构中，数据元素间的逻辑顺序是通过链表中结点的指针域中指针链接的次序实现的。 5. 栈的输出序列：栈是一种后进先出（LIFO）的数据结构，所以输入序列A、B、C、D，借助栈可能得到的输出序列不包括D、A、B、C，因为D是最后入栈的，应最先出栈。 6. 队列的输出序列：队列是先进先出（FIFO）的数据结构，所以入队序列1、2、3、4，其出队序列应为1、2、3、4。 7. 数组存储地址计算：数组A[0..5,1..6]按行优先存储，若起始于1000，每个元素占5个单元，那么A[5,5]的地址是1000 + (5-1)*6*5 + (5-1)*5 = 1170。 8. 完全二叉树结点编号：对于编号为49的结点，其左孩子的编号是49*2，由于根结点编号为1，所以编号为49的结点的左孩子编号为98。 9. 快速排序的一次划分结果：以第一个记录为基准，初始关键字为（46，79，56，38，40，84），一次划分可能得到（40，38，46，56，79，84），其中小于基准的放在前面，大于的放在后面。 10. 排序算法的时间复杂度：在初始数据有序的情况下，快速排序的平均时间复杂度会退化为O(n^2)，因为每次划分只能减少一个元素，花费时间反而最多。 填空题： 1. 在长度为n的顺序表中插入一个元素，平均需要移动n/2个元素，这是因为插入位置可能在表的任何位置，平均移动元素的数量是n/2。 2. 冒泡排序在最坏的情况下，即待排序序列完全逆序时，比较次数的最大值是N(N-1)/2。