【導(dǎo)讀】1．棧的主要特點是；隊列的主要特點是。為；在給定值為x的結(jié)點后插入一個新的結(jié)點的時間復(fù)雜度為。4．設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組s[0?n*(n-1)/2]中，若按行序為主存儲，則A[i][j]對應(yīng)的s中的存儲位置為。1/n轉(zhuǎn)化成遞歸函數(shù)，其遞歸出口是f=1當n=1時，遞歸體是。7．具有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為。8．對一個滿二叉樹，m個樹葉，n個結(jié)點，深度為h，則n=。10．在各種查找方法中，平均查找長度與結(jié)點個數(shù)無關(guān)的查找方法是。11．快速排序在最壞情況下的時間復(fù)雜度為。13．直接存取文件是用方法組織的。14．-18在內(nèi)存中的補碼形式是10010011。15．若a=3,b=4,c=5,d=6,則執(zhí)行完如下表達式&&(c=d)后，a=3，b=. ，Pn，若P1=n，則Pi為（）。9．快速排序方法在（）情況下最不利于發(fā)揮其長處。1．設(shè)有一組關(guān)鍵字{19，01，23，14，55，20，84，27，68，11，10，77}采用哈希函數(shù)：。間中對該關(guān)鍵字序列構(gòu)造哈希表。該程序填寫完整。

　　

【正文】 組關(guān)鍵字構(gòu)造哈希表，并求在關(guān)鍵字的查找概率相等的前提下查找成功的平均查找長度。（要求：直接寫出哈希表格，查找長度表示為分數(shù)形式）（ 10 分） 6，對長度為 n 的記錄序列進行快速排序時，所需要的比較次數(shù)依賴于這幾個元素的初始序列。點 n=8 時，在最好的情況下共需要進行多少次比較？（要求：寫出每一趟的劃分 情況和比較次數(shù)。）（ 10 分） 四，算法設(shè)計題（共 10 分） 試編寫一個在帶有頭結(jié)點的雙向循環(huán)鏈表中為 x 的結(jié)點之前，插入值為 y 的結(jié)點的算法。（要求：用 C 語言描述，結(jié)點類型定義為 dlnode） Status InsertPriorL(DlinkList amp。L) 五、程序填空題 ： C=5/9（ F32），其中表示 C 攝氏溫度， F 表示華氏溫度。要求輸出從華氏 0176。 到華氏 300176。 ，每隔 20176。 一個值。 main() {int upper,step。 float fahr=,celsius。 upper=300。step=20。 while( fahr upper) {celsius= *(fahr32) 。 printf(“%f%f\n”,fahr,celsius)。 fahr+=step 。 } } 。 include main() {int a ,b,max。 printf(“please input:\n”)。 scanf(“%d%d”, amp。a,amp。b )。 if(ab) max=a。 else max=b。 printf(the max is :%d\n“,max)。 } 3. 輸入一行字符，分別統(tǒng)計出其中英文字母、空格、數(shù)字和其他字符的個數(shù)。 include main() {char c。 int letters=0,space=0,digit=0,other=0。 printf(“please input characters\ n”)。 while((c=getchar())! =?\n?) {if(c=?a?amp。amp。c=?z?|| c=?A? amp。amp。 c=?Z? ) letters++ 。 else if(c= =? ?) space++ 。 else if (c=?0?amp。amp。C=?9?) digit++ 。 else other++ 。 } printf(“%d%d%d%d\n”,letter,space,digit,other)。 } 4 程序讀入 20 個整數(shù)，統(tǒng)計非負數(shù)的個數(shù)，并計算非負數(shù)的和。 include main() {int i， a[20],s,count。 s=0。count=0。 for(i=0。i20。i++) scanf(“%d”, amp。a[i] )。 for(i=0。i20。i++) {if(a[i]0) continue 。 s+=a[i]。 count++。 } printf(“s=%d\t count=%d\n”,s,count)。 } 3 3 矩形對角線元素之和。 mian（） {float a[3][3],sum=0。 int i,j。 print(“please input the matrix:\n”)。 for(i=0。i3。i++) for(j=0。j3。j++) scanf(“%f”, amp。a[i][j] )。 for(i=0。i3。i++) sum= sum+((i= =1)?(a[i][i]+a[i][2i])/2: a[i][i]+a[i][2i]) 。 prinf(“the result is :%f\n”,sum)。 } 六、讀程序?qū)懡Y(jié)果 1. include “” main() {int a,b,c。 printf(“please input:\n”)。 scanf(“%d,%d,%d”,amp。a,amp。b,amp。c)。 if(ab) if(bc) printf(“max=%d\n”,c)。 else printf(“max=%d\n”,b)。 else if(ac) printf(“max=%d\n”,c)。 else printf(“max=%d\n”,a)。 } 本程序的功能為 從鍵盤上接收三個整數(shù)，并輸出其中最大的數(shù) 。 2. include main() {int count,num,total。 count=0。total=0。 while(count10) {count++。 printf(“enter the NO.%d=”,count) scanf(“%d”,amp。num)。 total+=num。 } printf(“Total=%\n”,total)。 } 本程序若輸入 0 1 2 3 4 5 6 7 8 9 十個數(shù)，輸出的結(jié)果是 45 。 3. include int a[2][3]={{1,2,3},{4,5,6}}。 main() {int i,j,b[3][2]。 for(i=0。i=1。i++) for(j=0。j=2。j++) b[j][i]=a[i][j]。 for(i=0。i=2。i++) for(j=0。j=1。j++) printf(“%d”,b[i][j])。 } 本程序的輸出結(jié)果為 1 4 2 5 3 6 。 4. include main() {int a [10]={1,2,3,4,5,6,7,8,9,0}。 int *p,i。 printf(“\n”)。 for(p=a。p(a+10)。p++) printf(“%d”,*p)。 printf(“\n”)。 } 本程序的輸出的結(jié)果是 1 2 3 4 5 6 7 8 9 0 。 七、編程題 (共 10 分 ) 請編寫一個完整的程序，要求輸入一個整型 3 4 矩陣，求其中最大元素的值并輸出。 main() { int a[3][4],i,j,max。 for(i=0。i3。i++) for(j=0。j4。j++) scanf(”%d”,amp。a[i][j])。 max=a[0][0]。 for(i=0。i3。i++) for(j=0。j4。j++) if(a[i][j]max) max=a[i][j]。 printf(“max=%d”,max)。 }