在有n個結點的有序單鏈表中插入一個新結點，鏈表仍然保持有序的時間？答案是錯的，你是對的。本課題主要研究有序單鏈表的插入操作和算法分析。對數(shù)據(jù)結構的任何操作都不能改變其原始結構特征。因此，在將新節(jié)點插入

在有n個結點的有序單鏈表中插入一個新結點，鏈表仍然保持有序的時間？

答案是錯的，你是對的。本課題主要研究有序單鏈表的插入操作和算法分析。

對數(shù)據(jù)結構的任何操作都不能改變其原始結構特征。因此，在將新節(jié)點插入有序列表之后，仍然需要保持其順序。插入操作的關鍵是找到插入位置，主要的時間也花在找到插入位置上。對于N個節(jié)點的單鏈表，有n1個可能的插入位置，即在第一個節(jié)點之前和每個節(jié)點之后。在第一個節(jié)點前插入并比較一次；在第一個節(jié)點后插入并比較兩次，在第n個節(jié)點后插入搜索次數(shù)。如果每個掩碼上的插入概率相等，即[*]，則在有序單鏈表上查找插入位置的平均比較次數(shù)為：[*

從一個具有n個節(jié)點的單鏈表中查找其值等于x的節(jié)點，在查找成功的情況下，平均需要比較幾個結點，說下原因？

要從具有n個節(jié)點的單鏈表中查找值等于x的節(jié)點，如果搜索成功，比較的平均數(shù)目是（n1）/2個節(jié)點。

由于單鏈表只能執(zhí)行單向順序搜索，因此以從第一個節(jié)點開始的搜索為例，需要比較的節(jié)點數(shù)f（m）=m才能找到第m個節(jié)點。搜索成功的最佳情況是第一次搜索成功，只比較一個節(jié)點，最壞情況是最后一次搜索成功，需要比較n個節(jié)點。

總共有n個案例，要比較的平均節(jié)點是（1，2，3。。。（n-1）n）/n=（n 1）/2。