1.下列敘述中正確的是
A)算法的空間複雜度是指算法程序中指令的條數
B)壓縮數據存儲空間不會降低算法的空間複雜度
C)算法的空間複雜度與算法所處理的數據存儲空間有關
D)算法的空間複雜度是指算法程序控制結構的複雜程度
C【解析】算法的空間複雜度是指算法在執行過程中所需要的內存空間。算法執行期間所需的存儲空間包括3個部分:輸入數據所佔的存儲空間;程序本身所佔的存儲空間;算法執行過程中所需要的額外空間。
2.為了降低算法的空間複雜度,要求算法儘量採用原地工作(in place)。所謂原地工作是指
A)執行算法時不使用額外空間
B)執行算法時不使用任何存儲空間
C)執行算法時所使用的額外空間隨算法所處理的數據空間大小的變化而變化
D)執行算法時所使用的額外空間固定(即不隨算法所處理的數據空間大小的變化而變化)
D【解析】對於算法的空間複雜度,如果額外空間量相對於問題規模(即輸入數據所佔的存儲空間)來說是常數,即額外空間量不隨問題規模的變化而變化,則稱該算法是原地工作的。
1.下列敘述中正確的是
A)算法的空間複雜度是指算法程序中指令的條數
B)壓縮數據存儲空間不會降低算法的空間複雜度
C)算法的空間複雜度與算法所處理的數據存儲空間有關
D)算法的空間複雜度是指算法程序控制結構的複雜程度
C【解析】算法的空間複雜度是指算法在執行過程中所需要的內存空間。算法執行期間所需的存儲空間包括3個部分:輸入數據所佔的存儲空間;程序本身所佔的存儲空間;算法執行過程中所需要的額外空間。
2.為了降低算法的空間複雜度,要求算法儘量採用原地工作(in place)。所謂原地工作是指
A)執行算法時不使用額外空間
B)執行算法時不使用任何存儲空間
C)執行算法時所使用的額外空間隨算法所處理的數據空間大小的變化而變化
D)執行算法時所使用的額外空間固定(即不隨算法所處理的數據空間大小的變化而變化)
D【解析】對於算法的空間複雜度,如果額外空間量相對於問題規模(即輸入數據所佔的存儲空間)來說是常數,即額外空間量不隨問題規模的變化而變化,則稱該算法是原地工作的。
3.下列敘述中正確的是
A)算法的複雜度與問題的規模無關
B)算法的優化主要通過程序的編制技巧來實現
C)對數據進行壓縮存儲會降低算法的空間複雜度
D)數值型算法只需考慮計算結果的可靠性
C【解析】在許多實際問題中,為了減少算法所佔的存儲空間,通產採用壓縮存儲技術,以便儘量減少不必要的額外空間。
4.下列敘述中正確的是
A)數據的存儲結構會影響算法的效率
B)算法設計只需考慮結果的可靠性
C)算法複雜度是指算法控制結構的複雜程度
D)算法複雜度是用算法中指令的條數來度量的
A【解析】採用不同的存儲結構,其數據處理的效率是不同的。因此,在進行數據處理時,選擇合適的存儲結構很重要。
1.下列敘述中正確的是
A)算法的空間複雜度是指算法程序中指令的條數
B)壓縮數據存儲空間不會降低算法的空間複雜度
C)算法的空間複雜度與算法所處理的數據存儲空間有關
D)算法的空間複雜度是指算法程序控制結構的複雜程度
C【解析】算法的空間複雜度是指算法在執行過程中所需要的內存空間。算法執行期間所需的存儲空間包括3個部分:輸入數據所佔的存儲空間;程序本身所佔的存儲空間;算法執行過程中所需要的額外空間。
2.為了降低算法的空間複雜度,要求算法儘量採用原地工作(in place)。所謂原地工作是指
A)執行算法時不使用額外空間
B)執行算法時不使用任何存儲空間
C)執行算法時所使用的額外空間隨算法所處理的數據空間大小的變化而變化
D)執行算法時所使用的額外空間固定(即不隨算法所處理的數據空間大小的變化而變化)
D【解析】對於算法的空間複雜度,如果額外空間量相對於問題規模(即輸入數據所佔的存儲空間)來說是常數,即額外空間量不隨問題規模的變化而變化,則稱該算法是原地工作的。
3.下列敘述中正確的是
A)算法的複雜度與問題的規模無關
B)算法的優化主要通過程序的編制技巧來實現
C)對數據進行壓縮存儲會降低算法的空間複雜度
D)數值型算法只需考慮計算結果的可靠性
C【解析】在許多實際問題中,為了減少算法所佔的存儲空間,通產採用壓縮存儲技術,以便儘量減少不必要的額外空間。
4.下列敘述中正確的是
A)數據的存儲結構會影響算法的效率
B)算法設計只需考慮結果的可靠性
C)算法複雜度是指算法控制結構的複雜程度
D)算法複雜度是用算法中指令的條數來度量的
A【解析】採用不同的存儲結構,其數據處理的效率是不同的。因此,在進行數據處理時,選擇合適的存儲結構很重要。
5.下列敘述中錯誤的是
A)數據結構中的數據元素可以是另一數據結構
B)數據結構中的數據元素不能是另一數據結構
C)空數據結構可以是線性結構也可以是非線性結構
D)非空數據結構可以沒有根結點
B【解析】數據元素是一個含義很廣泛的概念,它是數據的“基本單位”,在計算機中通常作為一個整體進行考慮和處理。數據元素可以是一個數據也可以是被抽象出的具有一定結構數據集合,所以數據結構中的數據元素可以是另一數據結構。滿足有且只有一個根結點並且每一個結點最多有一個前件,也最多有一個後件的非空的數據結構認為是線性結構,不滿足條件的結構為非線性結構。空數據結構可以是線性結構也可以是非線性結構。非空數據結構可以沒有根結點,如非性線結構“圖”就沒有根結點。
6.設有序線性表的長度為n,則在有序線性表中進行二分查找,最壞情況下的比較次數為
A)n(n-1)/2
B)n
C)nlog2n
D)log2n
D【解析】有序線性表的長度為n,設被查找元素為x,則二分查找的方法如下:將x與線性表的中間項比較:若中間項的值等於x,則說明查到,查找結束;若x小於中間項的值,則在線性表的前半部分(即中間項以前的部分)以相同的方法進行查找;若x大於中間項的值,則在線性表的後半部分(即中間項以後的部分)以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0(說明線性表中沒有這個元素)為止。對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。
1.下列敘述中正確的是
A)算法的空間複雜度是指算法程序中指令的條數
B)壓縮數據存儲空間不會降低算法的空間複雜度
C)算法的空間複雜度與算法所處理的數據存儲空間有關
D)算法的空間複雜度是指算法程序控制結構的複雜程度
C【解析】算法的空間複雜度是指算法在執行過程中所需要的內存空間。算法執行期間所需的存儲空間包括3個部分:輸入數據所佔的存儲空間;程序本身所佔的存儲空間;算法執行過程中所需要的額外空間。
2.為了降低算法的空間複雜度,要求算法儘量採用原地工作(in place)。所謂原地工作是指
A)執行算法時不使用額外空間
B)執行算法時不使用任何存儲空間
C)執行算法時所使用的額外空間隨算法所處理的數據空間大小的變化而變化
D)執行算法時所使用的額外空間固定(即不隨算法所處理的數據空間大小的變化而變化)
D【解析】對於算法的空間複雜度,如果額外空間量相對於問題規模(即輸入數據所佔的存儲空間)來說是常數,即額外空間量不隨問題規模的變化而變化,則稱該算法是原地工作的。
3.下列敘述中正確的是
A)算法的複雜度與問題的規模無關
B)算法的優化主要通過程序的編制技巧來實現
C)對數據進行壓縮存儲會降低算法的空間複雜度
D)數值型算法只需考慮計算結果的可靠性
C【解析】在許多實際問題中,為了減少算法所佔的存儲空間,通產採用壓縮存儲技術,以便儘量減少不必要的額外空間。
4.下列敘述中正確的是
A)數據的存儲結構會影響算法的效率
B)算法設計只需考慮結果的可靠性
C)算法複雜度是指算法控制結構的複雜程度
D)算法複雜度是用算法中指令的條數來度量的
A【解析】採用不同的存儲結構,其數據處理的效率是不同的。因此,在進行數據處理時,選擇合適的存儲結構很重要。
5.下列敘述中錯誤的是
A)數據結構中的數據元素可以是另一數據結構
B)數據結構中的數據元素不能是另一數據結構
C)空數據結構可以是線性結構也可以是非線性結構
D)非空數據結構可以沒有根結點
B【解析】數據元素是一個含義很廣泛的概念,它是數據的“基本單位”,在計算機中通常作為一個整體進行考慮和處理。數據元素可以是一個數據也可以是被抽象出的具有一定結構數據集合,所以數據結構中的數據元素可以是另一數據結構。滿足有且只有一個根結點並且每一個結點最多有一個前件,也最多有一個後件的非空的數據結構認為是線性結構,不滿足條件的結構為非線性結構。空數據結構可以是線性結構也可以是非線性結構。非空數據結構可以沒有根結點,如非性線結構“圖”就沒有根結點。
6.設有序線性表的長度為n,則在有序線性表中進行二分查找,最壞情況下的比較次數為
A)n(n-1)/2
B)n
C)nlog2n
D)log2n
D【解析】有序線性表的長度為n,設被查找元素為x,則二分查找的方法如下:將x與線性表的中間項比較:若中間項的值等於x,則說明查到,查找結束;若x小於中間項的值,則在線性表的前半部分(即中間項以前的部分)以相同的方法進行查找;若x大於中間項的值,則在線性表的後半部分(即中間項以後的部分)以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0(說明線性表中沒有這個元素)為止。對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。
7.在長度為97的順序有序表中作二分查找,最多需要的比較次數為
A)48
B)96
C)7
D)6
C【解析】對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。本題中n=97,最多需要的比較次數為log297,6<log297<7,故需要比較7次。
8..設表的長度為n。下列查找算法中,在最壞情況下,比較次數最少的是
A)順序查找
B)尋找最大項
C)尋找最小項
D)有序表的二分查找
D【解析】在最壞情況下的比較次數:順序查找為n,尋找最大項和最小項均為n-1,有序表的二分查找為log2n。
1.下列敘述中正確的是
A)算法的空間複雜度是指算法程序中指令的條數
B)壓縮數據存儲空間不會降低算法的空間複雜度
C)算法的空間複雜度與算法所處理的數據存儲空間有關
D)算法的空間複雜度是指算法程序控制結構的複雜程度
C【解析】算法的空間複雜度是指算法在執行過程中所需要的內存空間。算法執行期間所需的存儲空間包括3個部分:輸入數據所佔的存儲空間;程序本身所佔的存儲空間;算法執行過程中所需要的額外空間。
2.為了降低算法的空間複雜度,要求算法儘量採用原地工作(in place)。所謂原地工作是指
A)執行算法時不使用額外空間
B)執行算法時不使用任何存儲空間
C)執行算法時所使用的額外空間隨算法所處理的數據空間大小的變化而變化
D)執行算法時所使用的額外空間固定(即不隨算法所處理的數據空間大小的變化而變化)
D【解析】對於算法的空間複雜度,如果額外空間量相對於問題規模(即輸入數據所佔的存儲空間)來說是常數,即額外空間量不隨問題規模的變化而變化,則稱該算法是原地工作的。
3.下列敘述中正確的是
A)算法的複雜度與問題的規模無關
B)算法的優化主要通過程序的編制技巧來實現
C)對數據進行壓縮存儲會降低算法的空間複雜度
D)數值型算法只需考慮計算結果的可靠性
C【解析】在許多實際問題中,為了減少算法所佔的存儲空間,通產採用壓縮存儲技術,以便儘量減少不必要的額外空間。
4.下列敘述中正確的是
A)數據的存儲結構會影響算法的效率
B)算法設計只需考慮結果的可靠性
C)算法複雜度是指算法控制結構的複雜程度
D)算法複雜度是用算法中指令的條數來度量的
A【解析】採用不同的存儲結構,其數據處理的效率是不同的。因此,在進行數據處理時,選擇合適的存儲結構很重要。
5.下列敘述中錯誤的是
A)數據結構中的數據元素可以是另一數據結構
B)數據結構中的數據元素不能是另一數據結構
C)空數據結構可以是線性結構也可以是非線性結構
D)非空數據結構可以沒有根結點
B【解析】數據元素是一個含義很廣泛的概念,它是數據的“基本單位”,在計算機中通常作為一個整體進行考慮和處理。數據元素可以是一個數據也可以是被抽象出的具有一定結構數據集合,所以數據結構中的數據元素可以是另一數據結構。滿足有且只有一個根結點並且每一個結點最多有一個前件,也最多有一個後件的非空的數據結構認為是線性結構,不滿足條件的結構為非線性結構。空數據結構可以是線性結構也可以是非線性結構。非空數據結構可以沒有根結點,如非性線結構“圖”就沒有根結點。
6.設有序線性表的長度為n,則在有序線性表中進行二分查找,最壞情況下的比較次數為
A)n(n-1)/2
B)n
C)nlog2n
D)log2n
D【解析】有序線性表的長度為n,設被查找元素為x,則二分查找的方法如下:將x與線性表的中間項比較:若中間項的值等於x,則說明查到,查找結束;若x小於中間項的值,則在線性表的前半部分(即中間項以前的部分)以相同的方法進行查找;若x大於中間項的值,則在線性表的後半部分(即中間項以後的部分)以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0(說明線性表中沒有這個元素)為止。對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。
7.在長度為97的順序有序表中作二分查找,最多需要的比較次數為
A)48
B)96
C)7
D)6
C【解析】對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。本題中n=97,最多需要的比較次數為log297,6<log297<7,故需要比較7次。
8..設表的長度為n。下列查找算法中,在最壞情況下,比較次數最少的是
A)順序查找
B)尋找最大項
C)尋找最小項
D)有序表的二分查找
D【解析】在最壞情況下的比較次數:順序查找為n,尋找最大項和最小項均為n-1,有序表的二分查找為log2n。
9.設順序表的長度為40,對該表進行冒泡排序。在最壞情況下需要的比較次數為
A)40
B)41
C)780
D)820
C【解析】對長度為n的線性表排序,在最壞情況下,冒泡排序需要經過n/2遍的從前住後的掃描和n/2遍的從後住前的掃描,需要比較的次數為n(n-1)/2。本題中n=40,故比較次數為40×(40-1)÷2=780。
10.在快速排序法中,每經過一次數據交換(或移動)後
A)只能消除一個逆序
B)能消除多個逆序
C)不會產生新的逆序
D)消除的逆序個數一定比新產生的逆序個數多
B【解析】在一個排列中,如果一對數的前後位置與大小順序相反,即前面的數大於後面的數,那麼它們就稱為一個逆序。快速排序的思想是:從線性表中選取一個元素,設為T,將線性表中後面小於T的元素移到前面,而前面大於T的元素移到後面,結果就將線性表分成兩部分(稱兩個子表),T插入到其分割線的位置處,這個過程稱為線性表的分割,然後再用同樣的方法對分割出的子表再進行同樣的分割。快速排序不是對兩個相鄰元素進行比較,可以實線通過一次交換而消除多個逆序,但由於均與T(基準元素)比較,也可能會產生新的逆序。
1.下列敘述中正確的是
A)算法的空間複雜度是指算法程序中指令的條數
B)壓縮數據存儲空間不會降低算法的空間複雜度
C)算法的空間複雜度與算法所處理的數據存儲空間有關
D)算法的空間複雜度是指算法程序控制結構的複雜程度
C【解析】算法的空間複雜度是指算法在執行過程中所需要的內存空間。算法執行期間所需的存儲空間包括3個部分:輸入數據所佔的存儲空間;程序本身所佔的存儲空間;算法執行過程中所需要的額外空間。
2.為了降低算法的空間複雜度,要求算法儘量採用原地工作(in place)。所謂原地工作是指
A)執行算法時不使用額外空間
B)執行算法時不使用任何存儲空間
C)執行算法時所使用的額外空間隨算法所處理的數據空間大小的變化而變化
D)執行算法時所使用的額外空間固定(即不隨算法所處理的數據空間大小的變化而變化)
D【解析】對於算法的空間複雜度,如果額外空間量相對於問題規模(即輸入數據所佔的存儲空間)來說是常數,即額外空間量不隨問題規模的變化而變化,則稱該算法是原地工作的。
3.下列敘述中正確的是
A)算法的複雜度與問題的規模無關
B)算法的優化主要通過程序的編制技巧來實現
C)對數據進行壓縮存儲會降低算法的空間複雜度
D)數值型算法只需考慮計算結果的可靠性
C【解析】在許多實際問題中,為了減少算法所佔的存儲空間,通產採用壓縮存儲技術,以便儘量減少不必要的額外空間。
4.下列敘述中正確的是
A)數據的存儲結構會影響算法的效率
B)算法設計只需考慮結果的可靠性
C)算法複雜度是指算法控制結構的複雜程度
D)算法複雜度是用算法中指令的條數來度量的
A【解析】採用不同的存儲結構,其數據處理的效率是不同的。因此,在進行數據處理時,選擇合適的存儲結構很重要。
5.下列敘述中錯誤的是
A)數據結構中的數據元素可以是另一數據結構
B)數據結構中的數據元素不能是另一數據結構
C)空數據結構可以是線性結構也可以是非線性結構
D)非空數據結構可以沒有根結點
B【解析】數據元素是一個含義很廣泛的概念,它是數據的“基本單位”,在計算機中通常作為一個整體進行考慮和處理。數據元素可以是一個數據也可以是被抽象出的具有一定結構數據集合,所以數據結構中的數據元素可以是另一數據結構。滿足有且只有一個根結點並且每一個結點最多有一個前件,也最多有一個後件的非空的數據結構認為是線性結構,不滿足條件的結構為非線性結構。空數據結構可以是線性結構也可以是非線性結構。非空數據結構可以沒有根結點,如非性線結構“圖”就沒有根結點。
6.設有序線性表的長度為n,則在有序線性表中進行二分查找,最壞情況下的比較次數為
A)n(n-1)/2
B)n
C)nlog2n
D)log2n
D【解析】有序線性表的長度為n,設被查找元素為x,則二分查找的方法如下:將x與線性表的中間項比較:若中間項的值等於x,則說明查到,查找結束;若x小於中間項的值,則在線性表的前半部分(即中間項以前的部分)以相同的方法進行查找;若x大於中間項的值,則在線性表的後半部分(即中間項以後的部分)以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0(說明線性表中沒有這個元素)為止。對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。
7.在長度為97的順序有序表中作二分查找,最多需要的比較次數為
A)48
B)96
C)7
D)6
C【解析】對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。本題中n=97,最多需要的比較次數為log297,6<log297<7,故需要比較7次。
8..設表的長度為n。下列查找算法中,在最壞情況下,比較次數最少的是
A)順序查找
B)尋找最大項
C)尋找最小項
D)有序表的二分查找
D【解析】在最壞情況下的比較次數:順序查找為n,尋找最大項和最小項均為n-1,有序表的二分查找為log2n。
9.設順序表的長度為40,對該表進行冒泡排序。在最壞情況下需要的比較次數為
A)40
B)41
C)780
D)820
C【解析】對長度為n的線性表排序,在最壞情況下,冒泡排序需要經過n/2遍的從前住後的掃描和n/2遍的從後住前的掃描,需要比較的次數為n(n-1)/2。本題中n=40,故比較次數為40×(40-1)÷2=780。
10.在快速排序法中,每經過一次數據交換(或移動)後
A)只能消除一個逆序
B)能消除多個逆序
C)不會產生新的逆序
D)消除的逆序個數一定比新產生的逆序個數多
B【解析】在一個排列中,如果一對數的前後位置與大小順序相反,即前面的數大於後面的數,那麼它們就稱為一個逆序。快速排序的思想是:從線性表中選取一個元素,設為T,將線性表中後面小於T的元素移到前面,而前面大於T的元素移到後面,結果就將線性表分成兩部分(稱兩個子表),T插入到其分割線的位置處,這個過程稱為線性表的分割,然後再用同樣的方法對分割出的子表再進行同樣的分割。快速排序不是對兩個相鄰元素進行比較,可以實線通過一次交換而消除多個逆序,但由於均與T(基準元素)比較,也可能會產生新的逆序。
11.設表的長度為15。則在最壞情況下,快速排序所需要的比較次數為
A)75
B)55
C)15
D)105
D【解析】快速排序在最壞情況下需要進行n(n-1)/2次比較,但實際的排序效率要比冒泡排序高得多。本題中n=15,15×(15-1)÷2=105。
12.設順序表的長度為16,對該表進行簡單插入排序。在最壞情況下需要的比較次數為
A)120
B)60
C)30
D)15
A【解析】簡單插入排序在最壞情況下,即初始排序序列是逆序的情況下,比較次數為n(n-1)/2,移動次數為n(n-1)/2。本題中n=16,16×(16-1)÷2=8×15=120。
1.下列敘述中正確的是
A)算法的空間複雜度是指算法程序中指令的條數
B)壓縮數據存儲空間不會降低算法的空間複雜度
C)算法的空間複雜度與算法所處理的數據存儲空間有關
D)算法的空間複雜度是指算法程序控制結構的複雜程度
C【解析】算法的空間複雜度是指算法在執行過程中所需要的內存空間。算法執行期間所需的存儲空間包括3個部分:輸入數據所佔的存儲空間;程序本身所佔的存儲空間;算法執行過程中所需要的額外空間。
2.為了降低算法的空間複雜度,要求算法儘量採用原地工作(in place)。所謂原地工作是指
A)執行算法時不使用額外空間
B)執行算法時不使用任何存儲空間
C)執行算法時所使用的額外空間隨算法所處理的數據空間大小的變化而變化
D)執行算法時所使用的額外空間固定(即不隨算法所處理的數據空間大小的變化而變化)
D【解析】對於算法的空間複雜度,如果額外空間量相對於問題規模(即輸入數據所佔的存儲空間)來說是常數,即額外空間量不隨問題規模的變化而變化,則稱該算法是原地工作的。
3.下列敘述中正確的是
A)算法的複雜度與問題的規模無關
B)算法的優化主要通過程序的編制技巧來實現
C)對數據進行壓縮存儲會降低算法的空間複雜度
D)數值型算法只需考慮計算結果的可靠性
C【解析】在許多實際問題中,為了減少算法所佔的存儲空間,通產採用壓縮存儲技術,以便儘量減少不必要的額外空間。
4.下列敘述中正確的是
A)數據的存儲結構會影響算法的效率
B)算法設計只需考慮結果的可靠性
C)算法複雜度是指算法控制結構的複雜程度
D)算法複雜度是用算法中指令的條數來度量的
A【解析】採用不同的存儲結構,其數據處理的效率是不同的。因此,在進行數據處理時,選擇合適的存儲結構很重要。
5.下列敘述中錯誤的是
A)數據結構中的數據元素可以是另一數據結構
B)數據結構中的數據元素不能是另一數據結構
C)空數據結構可以是線性結構也可以是非線性結構
D)非空數據結構可以沒有根結點
B【解析】數據元素是一個含義很廣泛的概念,它是數據的“基本單位”,在計算機中通常作為一個整體進行考慮和處理。數據元素可以是一個數據也可以是被抽象出的具有一定結構數據集合,所以數據結構中的數據元素可以是另一數據結構。滿足有且只有一個根結點並且每一個結點最多有一個前件,也最多有一個後件的非空的數據結構認為是線性結構,不滿足條件的結構為非線性結構。空數據結構可以是線性結構也可以是非線性結構。非空數據結構可以沒有根結點,如非性線結構“圖”就沒有根結點。
6.設有序線性表的長度為n,則在有序線性表中進行二分查找,最壞情況下的比較次數為
A)n(n-1)/2
B)n
C)nlog2n
D)log2n
D【解析】有序線性表的長度為n,設被查找元素為x,則二分查找的方法如下:將x與線性表的中間項比較:若中間項的值等於x,則說明查到,查找結束;若x小於中間項的值,則在線性表的前半部分(即中間項以前的部分)以相同的方法進行查找;若x大於中間項的值,則在線性表的後半部分(即中間項以後的部分)以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0(說明線性表中沒有這個元素)為止。對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。
7.在長度為97的順序有序表中作二分查找,最多需要的比較次數為
A)48
B)96
C)7
D)6
C【解析】對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。本題中n=97,最多需要的比較次數為log297,6<log297<7,故需要比較7次。
8..設表的長度為n。下列查找算法中,在最壞情況下,比較次數最少的是
A)順序查找
B)尋找最大項
C)尋找最小項
D)有序表的二分查找
D【解析】在最壞情況下的比較次數:順序查找為n,尋找最大項和最小項均為n-1,有序表的二分查找為log2n。
9.設順序表的長度為40,對該表進行冒泡排序。在最壞情況下需要的比較次數為
A)40
B)41
C)780
D)820
C【解析】對長度為n的線性表排序,在最壞情況下,冒泡排序需要經過n/2遍的從前住後的掃描和n/2遍的從後住前的掃描,需要比較的次數為n(n-1)/2。本題中n=40,故比較次數為40×(40-1)÷2=780。
10.在快速排序法中,每經過一次數據交換(或移動)後
A)只能消除一個逆序
B)能消除多個逆序
C)不會產生新的逆序
D)消除的逆序個數一定比新產生的逆序個數多
B【解析】在一個排列中,如果一對數的前後位置與大小順序相反,即前面的數大於後面的數,那麼它們就稱為一個逆序。快速排序的思想是:從線性表中選取一個元素,設為T,將線性表中後面小於T的元素移到前面,而前面大於T的元素移到後面,結果就將線性表分成兩部分(稱兩個子表),T插入到其分割線的位置處,這個過程稱為線性表的分割,然後再用同樣的方法對分割出的子表再進行同樣的分割。快速排序不是對兩個相鄰元素進行比較,可以實線通過一次交換而消除多個逆序,但由於均與T(基準元素)比較,也可能會產生新的逆序。
11.設表的長度為15。則在最壞情況下,快速排序所需要的比較次數為
A)75
B)55
C)15
D)105
D【解析】快速排序在最壞情況下需要進行n(n-1)/2次比較,但實際的排序效率要比冒泡排序高得多。本題中n=15,15×(15-1)÷2=105。
12.設順序表的長度為16,對該表進行簡單插入排序。在最壞情況下需要的比較次數為
A)120
B)60
C)30
D)15
A【解析】簡單插入排序在最壞情況下,即初始排序序列是逆序的情況下,比較次數為n(n-1)/2,移動次數為n(n-1)/2。本題中n=16,16×(16-1)÷2=8×15=120。
13.在希爾排序法中,每經過一次數據交換後
A)不會產生新的逆序
B)只能消除一個逆序
C)能消除多個逆序
D)消除的逆序個數一定比新產生的逆序個數多
C【解析】希爾排序法的基本思想是:將整個無序序列分割成若干小的子序列分別進行插入排序。在子序列中每進行一次比較就有可能移去整個線性表中的多個逆序,從而改善整個排序過程的性能。
14.下列序列中不滿足堆條件的是
A)(98,95,93,94,89,90,76,80,55,49)
B)(98,95,93,94,89,85,76,64,55,49)
C)(98,95,93,94,89,90,76,64,55,49)
D)(98,95,93,96,89,85,76,64,55,49)
D【解析】根據堆的定義,n個元素的序列(h1,h2,…hn),當且僅當hi≤h2i且hi≤h2i+1時為小頂堆,當且僅當hi≥h2i且hi≥h2i+1時為大頂堆。D項中,h2=95,h4=96,h2<h4,但h5=89,h2>h5,不滿足小頂堆和大頂堆條件。
1.下列敘述中正確的是
A)算法的空間複雜度是指算法程序中指令的條數
B)壓縮數據存儲空間不會降低算法的空間複雜度
C)算法的空間複雜度與算法所處理的數據存儲空間有關
D)算法的空間複雜度是指算法程序控制結構的複雜程度
C【解析】算法的空間複雜度是指算法在執行過程中所需要的內存空間。算法執行期間所需的存儲空間包括3個部分:輸入數據所佔的存儲空間;程序本身所佔的存儲空間;算法執行過程中所需要的額外空間。
2.為了降低算法的空間複雜度,要求算法儘量採用原地工作(in place)。所謂原地工作是指
A)執行算法時不使用額外空間
B)執行算法時不使用任何存儲空間
C)執行算法時所使用的額外空間隨算法所處理的數據空間大小的變化而變化
D)執行算法時所使用的額外空間固定(即不隨算法所處理的數據空間大小的變化而變化)
D【解析】對於算法的空間複雜度,如果額外空間量相對於問題規模(即輸入數據所佔的存儲空間)來說是常數,即額外空間量不隨問題規模的變化而變化,則稱該算法是原地工作的。
3.下列敘述中正確的是
A)算法的複雜度與問題的規模無關
B)算法的優化主要通過程序的編制技巧來實現
C)對數據進行壓縮存儲會降低算法的空間複雜度
D)數值型算法只需考慮計算結果的可靠性
C【解析】在許多實際問題中,為了減少算法所佔的存儲空間,通產採用壓縮存儲技術,以便儘量減少不必要的額外空間。
4.下列敘述中正確的是
A)數據的存儲結構會影響算法的效率
B)算法設計只需考慮結果的可靠性
C)算法複雜度是指算法控制結構的複雜程度
D)算法複雜度是用算法中指令的條數來度量的
A【解析】採用不同的存儲結構,其數據處理的效率是不同的。因此,在進行數據處理時,選擇合適的存儲結構很重要。
5.下列敘述中錯誤的是
A)數據結構中的數據元素可以是另一數據結構
B)數據結構中的數據元素不能是另一數據結構
C)空數據結構可以是線性結構也可以是非線性結構
D)非空數據結構可以沒有根結點
B【解析】數據元素是一個含義很廣泛的概念,它是數據的“基本單位”,在計算機中通常作為一個整體進行考慮和處理。數據元素可以是一個數據也可以是被抽象出的具有一定結構數據集合,所以數據結構中的數據元素可以是另一數據結構。滿足有且只有一個根結點並且每一個結點最多有一個前件,也最多有一個後件的非空的數據結構認為是線性結構,不滿足條件的結構為非線性結構。空數據結構可以是線性結構也可以是非線性結構。非空數據結構可以沒有根結點,如非性線結構“圖”就沒有根結點。
6.設有序線性表的長度為n,則在有序線性表中進行二分查找,最壞情況下的比較次數為
A)n(n-1)/2
B)n
C)nlog2n
D)log2n
D【解析】有序線性表的長度為n,設被查找元素為x,則二分查找的方法如下:將x與線性表的中間項比較:若中間項的值等於x,則說明查到,查找結束;若x小於中間項的值,則在線性表的前半部分(即中間項以前的部分)以相同的方法進行查找;若x大於中間項的值,則在線性表的後半部分(即中間項以後的部分)以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0(說明線性表中沒有這個元素)為止。對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。
7.在長度為97的順序有序表中作二分查找,最多需要的比較次數為
A)48
B)96
C)7
D)6
C【解析】對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。本題中n=97,最多需要的比較次數為log297,6<log297<7,故需要比較7次。
8..設表的長度為n。下列查找算法中,在最壞情況下,比較次數最少的是
A)順序查找
B)尋找最大項
C)尋找最小項
D)有序表的二分查找
D【解析】在最壞情況下的比較次數:順序查找為n,尋找最大項和最小項均為n-1,有序表的二分查找為log2n。
9.設順序表的長度為40,對該表進行冒泡排序。在最壞情況下需要的比較次數為
A)40
B)41
C)780
D)820
C【解析】對長度為n的線性表排序,在最壞情況下,冒泡排序需要經過n/2遍的從前住後的掃描和n/2遍的從後住前的掃描,需要比較的次數為n(n-1)/2。本題中n=40,故比較次數為40×(40-1)÷2=780。
10.在快速排序法中,每經過一次數據交換(或移動)後
A)只能消除一個逆序
B)能消除多個逆序
C)不會產生新的逆序
D)消除的逆序個數一定比新產生的逆序個數多
B【解析】在一個排列中,如果一對數的前後位置與大小順序相反,即前面的數大於後面的數,那麼它們就稱為一個逆序。快速排序的思想是:從線性表中選取一個元素,設為T,將線性表中後面小於T的元素移到前面,而前面大於T的元素移到後面,結果就將線性表分成兩部分(稱兩個子表),T插入到其分割線的位置處,這個過程稱為線性表的分割,然後再用同樣的方法對分割出的子表再進行同樣的分割。快速排序不是對兩個相鄰元素進行比較,可以實線通過一次交換而消除多個逆序,但由於均與T(基準元素)比較,也可能會產生新的逆序。
11.設表的長度為15。則在最壞情況下,快速排序所需要的比較次數為
A)75
B)55
C)15
D)105
D【解析】快速排序在最壞情況下需要進行n(n-1)/2次比較,但實際的排序效率要比冒泡排序高得多。本題中n=15,15×(15-1)÷2=105。
12.設順序表的長度為16,對該表進行簡單插入排序。在最壞情況下需要的比較次數為
A)120
B)60
C)30
D)15
A【解析】簡單插入排序在最壞情況下,即初始排序序列是逆序的情況下,比較次數為n(n-1)/2,移動次數為n(n-1)/2。本題中n=16,16×(16-1)÷2=8×15=120。
13.在希爾排序法中,每經過一次數據交換後
A)不會產生新的逆序
B)只能消除一個逆序
C)能消除多個逆序
D)消除的逆序個數一定比新產生的逆序個數多
C【解析】希爾排序法的基本思想是:將整個無序序列分割成若干小的子序列分別進行插入排序。在子序列中每進行一次比較就有可能移去整個線性表中的多個逆序,從而改善整個排序過程的性能。
14.下列序列中不滿足堆條件的是
A)(98,95,93,94,89,90,76,80,55,49)
B)(98,95,93,94,89,85,76,64,55,49)
C)(98,95,93,94,89,90,76,64,55,49)
D)(98,95,93,96,89,85,76,64,55,49)
D【解析】根據堆的定義,n個元素的序列(h1,h2,…hn),當且僅當hi≤h2i且hi≤h2i+1時為小頂堆,當且僅當hi≥h2i且hi≥h2i+1時為大頂堆。D項中,h2=95,h4=96,h2<h4,但h5=89,h2>h5,不滿足小頂堆和大頂堆條件。
15.在最壞情況下,堆排序的時間複雜度是
A)O(log2n)
B)O(nlog2n)
C)O(n2)
D)O(n1.5)
B【解析】堆排序的方法對於規模較小的線性表並不合適,但對於較大規模的線性表來說是很有效的。在最壞情況下,堆排序需要比較次數為nlog2n,時間複雜度為O(nlog2n)。
16下列敘述中正確的是
A)數據庫的數據項之間無聯繫
B)數據庫中任意兩個表之間一定不存在聯繫
C)數據庫的數據項之間存在聯繫
D)數據庫的數據項之間以及兩個表之間都不存在聯繫
C【解析】數據庫的數據項之間以及表之間都存在聯繫。
1.下列敘述中正確的是
A)算法的空間複雜度是指算法程序中指令的條數
B)壓縮數據存儲空間不會降低算法的空間複雜度
C)算法的空間複雜度與算法所處理的數據存儲空間有關
D)算法的空間複雜度是指算法程序控制結構的複雜程度
C【解析】算法的空間複雜度是指算法在執行過程中所需要的內存空間。算法執行期間所需的存儲空間包括3個部分:輸入數據所佔的存儲空間;程序本身所佔的存儲空間;算法執行過程中所需要的額外空間。
2.為了降低算法的空間複雜度,要求算法儘量採用原地工作(in place)。所謂原地工作是指
A)執行算法時不使用額外空間
B)執行算法時不使用任何存儲空間
C)執行算法時所使用的額外空間隨算法所處理的數據空間大小的變化而變化
D)執行算法時所使用的額外空間固定(即不隨算法所處理的數據空間大小的變化而變化)
D【解析】對於算法的空間複雜度,如果額外空間量相對於問題規模(即輸入數據所佔的存儲空間)來說是常數,即額外空間量不隨問題規模的變化而變化,則稱該算法是原地工作的。
3.下列敘述中正確的是
A)算法的複雜度與問題的規模無關
B)算法的優化主要通過程序的編制技巧來實現
C)對數據進行壓縮存儲會降低算法的空間複雜度
D)數值型算法只需考慮計算結果的可靠性
C【解析】在許多實際問題中,為了減少算法所佔的存儲空間,通產採用壓縮存儲技術,以便儘量減少不必要的額外空間。
4.下列敘述中正確的是
A)數據的存儲結構會影響算法的效率
B)算法設計只需考慮結果的可靠性
C)算法複雜度是指算法控制結構的複雜程度
D)算法複雜度是用算法中指令的條數來度量的
A【解析】採用不同的存儲結構,其數據處理的效率是不同的。因此,在進行數據處理時,選擇合適的存儲結構很重要。
5.下列敘述中錯誤的是
A)數據結構中的數據元素可以是另一數據結構
B)數據結構中的數據元素不能是另一數據結構
C)空數據結構可以是線性結構也可以是非線性結構
D)非空數據結構可以沒有根結點
B【解析】數據元素是一個含義很廣泛的概念,它是數據的“基本單位”,在計算機中通常作為一個整體進行考慮和處理。數據元素可以是一個數據也可以是被抽象出的具有一定結構數據集合,所以數據結構中的數據元素可以是另一數據結構。滿足有且只有一個根結點並且每一個結點最多有一個前件,也最多有一個後件的非空的數據結構認為是線性結構,不滿足條件的結構為非線性結構。空數據結構可以是線性結構也可以是非線性結構。非空數據結構可以沒有根結點,如非性線結構“圖”就沒有根結點。
6.設有序線性表的長度為n,則在有序線性表中進行二分查找,最壞情況下的比較次數為
A)n(n-1)/2
B)n
C)nlog2n
D)log2n
D【解析】有序線性表的長度為n,設被查找元素為x,則二分查找的方法如下:將x與線性表的中間項比較:若中間項的值等於x,則說明查到,查找結束;若x小於中間項的值,則在線性表的前半部分(即中間項以前的部分)以相同的方法進行查找;若x大於中間項的值,則在線性表的後半部分(即中間項以後的部分)以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0(說明線性表中沒有這個元素)為止。對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。
7.在長度為97的順序有序表中作二分查找,最多需要的比較次數為
A)48
B)96
C)7
D)6
C【解析】對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。本題中n=97,最多需要的比較次數為log297,6<log297<7,故需要比較7次。
8..設表的長度為n。下列查找算法中,在最壞情況下,比較次數最少的是
A)順序查找
B)尋找最大項
C)尋找最小項
D)有序表的二分查找
D【解析】在最壞情況下的比較次數:順序查找為n,尋找最大項和最小項均為n-1,有序表的二分查找為log2n。
9.設順序表的長度為40,對該表進行冒泡排序。在最壞情況下需要的比較次數為
A)40
B)41
C)780
D)820
C【解析】對長度為n的線性表排序,在最壞情況下,冒泡排序需要經過n/2遍的從前住後的掃描和n/2遍的從後住前的掃描,需要比較的次數為n(n-1)/2。本題中n=40,故比較次數為40×(40-1)÷2=780。
10.在快速排序法中,每經過一次數據交換(或移動)後
A)只能消除一個逆序
B)能消除多個逆序
C)不會產生新的逆序
D)消除的逆序個數一定比新產生的逆序個數多
B【解析】在一個排列中,如果一對數的前後位置與大小順序相反,即前面的數大於後面的數,那麼它們就稱為一個逆序。快速排序的思想是:從線性表中選取一個元素,設為T,將線性表中後面小於T的元素移到前面,而前面大於T的元素移到後面,結果就將線性表分成兩部分(稱兩個子表),T插入到其分割線的位置處,這個過程稱為線性表的分割,然後再用同樣的方法對分割出的子表再進行同樣的分割。快速排序不是對兩個相鄰元素進行比較,可以實線通過一次交換而消除多個逆序,但由於均與T(基準元素)比較,也可能會產生新的逆序。
11.設表的長度為15。則在最壞情況下,快速排序所需要的比較次數為
A)75
B)55
C)15
D)105
D【解析】快速排序在最壞情況下需要進行n(n-1)/2次比較,但實際的排序效率要比冒泡排序高得多。本題中n=15,15×(15-1)÷2=105。
12.設順序表的長度為16,對該表進行簡單插入排序。在最壞情況下需要的比較次數為
A)120
B)60
C)30
D)15
A【解析】簡單插入排序在最壞情況下,即初始排序序列是逆序的情況下,比較次數為n(n-1)/2,移動次數為n(n-1)/2。本題中n=16,16×(16-1)÷2=8×15=120。
13.在希爾排序法中,每經過一次數據交換後
A)不會產生新的逆序
B)只能消除一個逆序
C)能消除多個逆序
D)消除的逆序個數一定比新產生的逆序個數多
C【解析】希爾排序法的基本思想是:將整個無序序列分割成若干小的子序列分別進行插入排序。在子序列中每進行一次比較就有可能移去整個線性表中的多個逆序,從而改善整個排序過程的性能。
14.下列序列中不滿足堆條件的是
A)(98,95,93,94,89,90,76,80,55,49)
B)(98,95,93,94,89,85,76,64,55,49)
C)(98,95,93,94,89,90,76,64,55,49)
D)(98,95,93,96,89,85,76,64,55,49)
D【解析】根據堆的定義,n個元素的序列(h1,h2,…hn),當且僅當hi≤h2i且hi≤h2i+1時為小頂堆,當且僅當hi≥h2i且hi≥h2i+1時為大頂堆。D項中,h2=95,h4=96,h2<h4,但h5=89,h2>h5,不滿足小頂堆和大頂堆條件。
15.在最壞情況下,堆排序的時間複雜度是
A)O(log2n)
B)O(nlog2n)
C)O(n2)
D)O(n1.5)
B【解析】堆排序的方法對於規模較小的線性表並不合適,但對於較大規模的線性表來說是很有效的。在最壞情況下,堆排序需要比較次數為nlog2n,時間複雜度為O(nlog2n)。
16下列敘述中正確的是
A)數據庫的數據項之間無聯繫
B)數據庫中任意兩個表之間一定不存在聯繫
C)數據庫的數據項之間存在聯繫
D)數據庫的數據項之間以及兩個表之間都不存在聯繫
C【解析】數據庫的數據項之間以及表之間都存在聯繫。
17.能夠減少相同數據重複存儲的是
A)記錄
B)字段
C)文件
D)數據庫
D【解析】數據庫表的一行稱為一個記錄,一列稱一個字段。文件管理階段不能保證相同數據重複存儲。在數據庫系統階段使用數據庫管理數據,可大大減少相同數據重複存儲。
18.數據庫管理系統是
A)一種操作系統在
B)操作系統的一部分
C)一種編譯程序
D)操作系統支持下的系統軟件
D【解析】數據庫管理系統是數據庫系統的核心,它位於用戶和操作系統之間,從軟件分類的角度來說,屬於系統軟件。
1.下列敘述中正確的是
A)算法的空間複雜度是指算法程序中指令的條數
B)壓縮數據存儲空間不會降低算法的空間複雜度
C)算法的空間複雜度與算法所處理的數據存儲空間有關
D)算法的空間複雜度是指算法程序控制結構的複雜程度
C【解析】算法的空間複雜度是指算法在執行過程中所需要的內存空間。算法執行期間所需的存儲空間包括3個部分:輸入數據所佔的存儲空間;程序本身所佔的存儲空間;算法執行過程中所需要的額外空間。
2.為了降低算法的空間複雜度,要求算法儘量採用原地工作(in place)。所謂原地工作是指
A)執行算法時不使用額外空間
B)執行算法時不使用任何存儲空間
C)執行算法時所使用的額外空間隨算法所處理的數據空間大小的變化而變化
D)執行算法時所使用的額外空間固定(即不隨算法所處理的數據空間大小的變化而變化)
D【解析】對於算法的空間複雜度,如果額外空間量相對於問題規模(即輸入數據所佔的存儲空間)來說是常數,即額外空間量不隨問題規模的變化而變化,則稱該算法是原地工作的。
3.下列敘述中正確的是
A)算法的複雜度與問題的規模無關
B)算法的優化主要通過程序的編制技巧來實現
C)對數據進行壓縮存儲會降低算法的空間複雜度
D)數值型算法只需考慮計算結果的可靠性
C【解析】在許多實際問題中,為了減少算法所佔的存儲空間,通產採用壓縮存儲技術,以便儘量減少不必要的額外空間。
4.下列敘述中正確的是
A)數據的存儲結構會影響算法的效率
B)算法設計只需考慮結果的可靠性
C)算法複雜度是指算法控制結構的複雜程度
D)算法複雜度是用算法中指令的條數來度量的
A【解析】採用不同的存儲結構,其數據處理的效率是不同的。因此,在進行數據處理時,選擇合適的存儲結構很重要。
5.下列敘述中錯誤的是
A)數據結構中的數據元素可以是另一數據結構
B)數據結構中的數據元素不能是另一數據結構
C)空數據結構可以是線性結構也可以是非線性結構
D)非空數據結構可以沒有根結點
B【解析】數據元素是一個含義很廣泛的概念,它是數據的“基本單位”,在計算機中通常作為一個整體進行考慮和處理。數據元素可以是一個數據也可以是被抽象出的具有一定結構數據集合,所以數據結構中的數據元素可以是另一數據結構。滿足有且只有一個根結點並且每一個結點最多有一個前件,也最多有一個後件的非空的數據結構認為是線性結構,不滿足條件的結構為非線性結構。空數據結構可以是線性結構也可以是非線性結構。非空數據結構可以沒有根結點,如非性線結構“圖”就沒有根結點。
6.設有序線性表的長度為n,則在有序線性表中進行二分查找,最壞情況下的比較次數為
A)n(n-1)/2
B)n
C)nlog2n
D)log2n
D【解析】有序線性表的長度為n,設被查找元素為x,則二分查找的方法如下:將x與線性表的中間項比較:若中間項的值等於x,則說明查到,查找結束;若x小於中間項的值,則在線性表的前半部分(即中間項以前的部分)以相同的方法進行查找;若x大於中間項的值,則在線性表的後半部分(即中間項以後的部分)以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0(說明線性表中沒有這個元素)為止。對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。
7.在長度為97的順序有序表中作二分查找,最多需要的比較次數為
A)48
B)96
C)7
D)6
C【解析】對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。本題中n=97,最多需要的比較次數為log297,6<log297<7,故需要比較7次。
8..設表的長度為n。下列查找算法中,在最壞情況下,比較次數最少的是
A)順序查找
B)尋找最大項
C)尋找最小項
D)有序表的二分查找
D【解析】在最壞情況下的比較次數:順序查找為n,尋找最大項和最小項均為n-1,有序表的二分查找為log2n。
9.設順序表的長度為40,對該表進行冒泡排序。在最壞情況下需要的比較次數為
A)40
B)41
C)780
D)820
C【解析】對長度為n的線性表排序,在最壞情況下,冒泡排序需要經過n/2遍的從前住後的掃描和n/2遍的從後住前的掃描,需要比較的次數為n(n-1)/2。本題中n=40,故比較次數為40×(40-1)÷2=780。
10.在快速排序法中,每經過一次數據交換(或移動)後
A)只能消除一個逆序
B)能消除多個逆序
C)不會產生新的逆序
D)消除的逆序個數一定比新產生的逆序個數多
B【解析】在一個排列中,如果一對數的前後位置與大小順序相反,即前面的數大於後面的數,那麼它們就稱為一個逆序。快速排序的思想是:從線性表中選取一個元素,設為T,將線性表中後面小於T的元素移到前面,而前面大於T的元素移到後面,結果就將線性表分成兩部分(稱兩個子表),T插入到其分割線的位置處,這個過程稱為線性表的分割,然後再用同樣的方法對分割出的子表再進行同樣的分割。快速排序不是對兩個相鄰元素進行比較,可以實線通過一次交換而消除多個逆序,但由於均與T(基準元素)比較,也可能會產生新的逆序。
11.設表的長度為15。則在最壞情況下,快速排序所需要的比較次數為
A)75
B)55
C)15
D)105
D【解析】快速排序在最壞情況下需要進行n(n-1)/2次比較,但實際的排序效率要比冒泡排序高得多。本題中n=15,15×(15-1)÷2=105。
12.設順序表的長度為16,對該表進行簡單插入排序。在最壞情況下需要的比較次數為
A)120
B)60
C)30
D)15
A【解析】簡單插入排序在最壞情況下,即初始排序序列是逆序的情況下,比較次數為n(n-1)/2,移動次數為n(n-1)/2。本題中n=16,16×(16-1)÷2=8×15=120。
13.在希爾排序法中,每經過一次數據交換後
A)不會產生新的逆序
B)只能消除一個逆序
C)能消除多個逆序
D)消除的逆序個數一定比新產生的逆序個數多
C【解析】希爾排序法的基本思想是:將整個無序序列分割成若干小的子序列分別進行插入排序。在子序列中每進行一次比較就有可能移去整個線性表中的多個逆序,從而改善整個排序過程的性能。
14.下列序列中不滿足堆條件的是
A)(98,95,93,94,89,90,76,80,55,49)
B)(98,95,93,94,89,85,76,64,55,49)
C)(98,95,93,94,89,90,76,64,55,49)
D)(98,95,93,96,89,85,76,64,55,49)
D【解析】根據堆的定義,n個元素的序列(h1,h2,…hn),當且僅當hi≤h2i且hi≤h2i+1時為小頂堆,當且僅當hi≥h2i且hi≥h2i+1時為大頂堆。D項中,h2=95,h4=96,h2<h4,但h5=89,h2>h5,不滿足小頂堆和大頂堆條件。
15.在最壞情況下,堆排序的時間複雜度是
A)O(log2n)
B)O(nlog2n)
C)O(n2)
D)O(n1.5)
B【解析】堆排序的方法對於規模較小的線性表並不合適,但對於較大規模的線性表來說是很有效的。在最壞情況下,堆排序需要比較次數為nlog2n,時間複雜度為O(nlog2n)。
16下列敘述中正確的是
A)數據庫的數據項之間無聯繫
B)數據庫中任意兩個表之間一定不存在聯繫
C)數據庫的數據項之間存在聯繫
D)數據庫的數據項之間以及兩個表之間都不存在聯繫
C【解析】數據庫的數據項之間以及表之間都存在聯繫。
17.能夠減少相同數據重複存儲的是
A)記錄
B)字段
C)文件
D)數據庫
D【解析】數據庫表的一行稱為一個記錄,一列稱一個字段。文件管理階段不能保證相同數據重複存儲。在數據庫系統階段使用數據庫管理數據,可大大減少相同數據重複存儲。
18.數據庫管理系統是
A)一種操作系統在
B)操作系統的一部分
C)一種編譯程序
D)操作系統支持下的系統軟件
D【解析】數據庫管理系統是數據庫系統的核心,它位於用戶和操作系統之間,從軟件分類的角度來說,屬於系統軟件。
19.數據庫管理系統的基本功能不包括
A)數據庫定義
B)數據庫和網絡中其他系統的通信
C)數據庫的建立和維護
D)數據庫訪問
B【解析】數據庫管理系統的功能包括數據模式定義、數據存取的物理構建、數據操縱、數據完整性安全性的定義與檢查、數據庫的併發控制與故障恢復、數據的服務。
20.數據庫系統中完成查詢操作使用的語言是
A)數據操縱語言
B)數據定義語言
C)數據控制語言
D)數據併發語言
A【解析】數據庫管理系統提供了相應的數據語言:
數據定義語言(DDL):該語言負責數據的模式定義與數據的物理存取構建。
數據操縱語言(DML):該語言負責數據的操縱,包括查詢與增、刪、改等操作。
數據控制語言(DCL):該語言負責數據完整性、安全性的定義與檢查以及併發控制、故障恢復等功能。