學習使我快樂
- 判斷題
- 選擇題
- 函式題
判斷題
1-1 對于順序存盤的長度為N的線性表，訪問結點和增加結點的時間復雜度分別對應為O(1)和O(N)，
- T
- F
1-2 若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和洗掉運算，則利用順序表存盤最節省時間，
- T
- F
1-3 對于順序存盤的長度為N的線性表，洗掉第一個元素和插入最后一個元素的時間復雜度分別對應為O(1)和O(N)，
-
T
-
F
1-4 若用鏈表來表示一個線性表，則表中元素的地址一定是連續的，
-
T
-
F
選擇題
2-1 在N個結點的順序表中，演算法的時間復雜度為O(1)的操作是：
A. 訪問第i個結點（1≤i≤N）和求第i個結點的直接前驅（2≤i≤N）
B. 在第i個結點后插入一個新結點（1≤i≤N）
C. 洗掉第i個結點（1≤i≤N）
D. 將N個結點從小到大排序
2-2 對于順序存盤的長度為N的線性表，訪問結點和增加結點的時間復雜度為：
A. O(1), O(1)
B. O(1), O(N)
C. O(N), O(1)
D. O(N), O(N)
2-3 若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和洗掉運算，則利用哪種存盤方式最節省時間？
A. 雙鏈表
B. 單回圈鏈表
C. 帶頭結點的雙回圈鏈表
D. 順序表
2-4 順序表中第一個元素的存盤地址是100，每個元素的長度為2，則第5個元素的地址是（ ），
A. 100
B. 105
C. 108
D. 110
2-5 下列函式中，哪兩個函式具有相同的增長速度：
A. 2N和N?N
B. N和2/N
C. N?2logN和NlogN?2
D. NlogN?2和NlogN
2-6 演算法的時間復雜度取決于（ ），
A. 問題的規模
B. 待處理資料的初態
C. 計算機的配置
D. A和B
2-7 已知兩個長度分別為m和n的升序鏈表，若將它們合并為一個長度為m+n的降序鏈表，則最壞情況下的時間復雜度是（ ），
A. O(n)
B. O(mn)
C. O(min(m,n))
D. O(max(m,n))
2-8 下列代碼的時間復雜度是：
for(i=0; i<N; i++)
for(j=0; j<N; j+=1000)
printf("%d,%d\n", i, j);
A. O(N×j)
B. O(N)
C. O(N2)
D. O(NlogN)
2-9 下面程式段的時間復雜度是 ( )
i ＝ 0；
while（i<=n）
i = i * 3；
A. O(2n)
B. O(n)
C. O(n?2)
D. O(log?3n)
2-10 程式段
FOR i:=n-1 DOWNTO 1 DO
FOR j:=1 TO i DO
IF A[j]>A[j+1]
THEN A[j]與A[j+1]對換；
其中 n為正整數，則最后一行的陳述句頻度在最壞情況下是（ ）
A. O（n）
B. O(nlogn)
C. O(n3)
D.O(n?2)
2-11 下列敘述中正確的是
A. 程式執行的效率與資料的存盤結構密切相關
B. 程式執行的效率只取決于程式的控制結構
C. 程式執行的效率只取決于所處理的資料量
D. 以上說法均錯誤
函式題
6-2 多項式求值
本題要求實作一個函式，計算階數為n，系數為a[0] … a[n]的多項式f(x)=∑ ni=0(a[i] × xi) 在x點的值，
函式介面定義：
double f( int n, double a[], double x );
其中n是多項式的階數，a[]中存盤系數，x是給定點，函式須回傳多項式f(x)的值，
裁判測驗程式樣例：
#include <stdio.h>
#define MAXN 10
double f( int n, double a[], double x );
int main()
{
int n, i;
double a[MAXN], x;
scanf("%d %lf", &n, &x);
for ( i=0; i<=n; i++ )
scanf(“%lf”, &a[i]);
printf("%.1f\n", f(n, a, x));
return 0;
}
/* 你的代碼將被嵌在這里 */
輸入樣例：
2 1.1
1 2.5 -38.7
輸出樣例：
-43.1
代碼：
double f( int n, double a[], double x ){
double ans;
for (int i = 0; i <= n; ++i) {
ans+=a[i]*pow(x,i);
}
return ans;
}
**6-3 使用函式判斷完全平方數 **
本題要求實作一個判斷整數是否為完全平方數的簡單函式，
函式介面定義：
int IsSquare( int n );
其中n是用戶傳入的引數，在長整型范圍內，如果n是完全平方數，則函式IsSquare必須回傳1，否則回傳0，
裁判測驗程式樣例：
#include <stdio.h>
#include <math.h>
int IsSquare( int n );
int main()
{
int n;
scanf("%d", &n);
if ( IsSquare(n) ) printf("YES\n");
else printf("NO\n");
return 0;
}
/* 你的代碼將被嵌在這里 */
輸入樣例1：
10
輸出樣例1：
NO
輸入樣例2：
100
輸出樣例2：
YES
代碼
int IsSquare( int n )
{
int h =pow(n,0.5);
if(pow(h,2)==n)return 1;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/225344.html
標籤：其他