数据结构问题解答.pdfVIP

4、若有 n 个元素的序列近似有序，即除掉少数 K 个元素后是有序序列且 Kn ，在冒泡排 序、快速排序、直接插入排序、堆排序方法中，请给出哪些方法不适合，哪些方法最快最适 合，简述原因。 【参考解答】在待排序列近似有序的情况下， 快速排序、 堆排序都不太适合， 直接插入排序、 2 冒泡排序比较快。因为在这种情况下，快速排序接近最坏情况，时间复杂度接近 O(n ) ，堆 排序的时间复杂度仍然是 O(nlogn) ，相反，由于比较和移动次数较少，直接插入排序和冒 泡排序的时间复杂度接近 O(n) （这里假设冒泡排序在一趟排序没有交换发生时结束。） 五、编写一程序，实现在链式存储方式下的模式匹配。 设主串 s 和子串 t 分别以单链表存储， t 和 s 中每个字符均用一结点表示（如图）。即 求：子串 t 在主串 s 中第一次出现的位置指针。 data Next 【分析】思路类似简单模式匹配算法，但是，链表不像数组那样方便（ i=i-j+2 ）回溯，所 以应该增加一个指针变量（如下程序中的指针变量 ps ），记录每一趟开始匹配的起点。 【参考解答】 采用简单模式匹配算法的思路， 为方便回溯， 增加一个指针变量记录每一趟匹 配开始的位置。 // 字符结点结构 struct LNode { char data ; LNode * next ; }; // 链式存储的字符串类型（相当于不带头结点的单链表） typedef LNode * LString ; // 字符串模式匹配 // 在主串 s 中查找子串 t首次出现的位置，并返回指示该位置的指针 LString LSIndex (const LString s, const LString t) { // 从主串 s每个字符结点 ps 开始匹配子串 t LString ps = s; // 记录主串中开始匹配的起始位置 LString pi = ps; LString pj = t; while (pi pj) { if (pi- data == pj- data ) { pi = pi- next ; pj = pj- next ; } else { // 失配时回溯到主串的下一个字符 ps = ps- next ; pi = ps; pj = t; } } // 如果匹配成功返回主串中匹配的起始位置 if (pj == NULL) return ps; else return NULL; } 1．分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递 增序列的表按递增顺序排序，给出最省时间与最费时间的算法名称，简述原 因。 【参考解答】对初始状态为递增序列的表按递增顺序排序，（ 1）直接插入排序最省时间。 因为算法此时总的比较次数为 n-1 ，移动次数为 0 ，为最好情况，是最省时间的。