1、2013 年“數據結構與 C 程序設計 ”代(碼 991) 試題一、單項選擇題(本題共 20 分，每小題各 2 分)1 對于長度為n的線性表，建立其對應的單鏈表的時間復雜度為()。AO(1) ； BO(log2n) ； O(n) ； D O(n2) 。2 一般情況下，在一個雙向鏈表中插入一個新的鏈結點，()。A需要修改4個指針域內的指針；B需要修改3個指針域內的指針；C需要修改2個指針域內的指針；D只需要修改1個指針域內的指針。3 假設用單個字母表示中綴表達式中的一個運算數 (或稱運算對象 ) ，并利用堆棧產生中綴表達式對應的后綴表達式。對于中綴表達式A+B*(C/D-E)，當從左至右掃描到運

2、算數E時，堆棧中的運算符依次是()(注：不包含表達式的分界符)A.+*/- ； B. +*(/-； C. +*-； . +*(- 。4 .若某二叉排序樹的前序遍歷序列為50,20,40,30,80,60,70，則后序遍歷序列為 ( ) 。A.30,40,20,50,70,60,80；B. 30,40,20,70,60,80,50；C.70,60,80,50,30,40,20；D. 70,60,80,30,40,20,50。5 .分別以 6, 3, 8, 12, 5, 7對應葉結點的權值構造的哈夫曼(Huffman)樹的深度為 ( ) 。A.6 ； B . 5 ； C . 4 ； D. 3。6

3、.下列關于圖的敘述中，錯誤的是( )。A根據圖的定義，圖中至少有一個頂點；B 根據圖的定義，圖中至少有一個頂點和一條邊(弧)；C.具有n個頂點的無向圖最多有n(n-1)/2條邊；D .具有n個頂點的有向圖最多有 n(n-1) 條邊(弧)。7 若在有向圖G的拓撲序列中，頂點 vi在頂點vj之前，則下列4種情形中不可能出現的是()。A G 中有弧 ；BG 中沒有弧 ；C G中有一條從頂點vi到頂點vj的路徑；DG 中有一條從頂點 vj 到頂點 vi 的路徑。 8下列關于查找操作的敘述中，錯誤的是 ( )。A 在順序表中查找元素可以采用順序查找法，也可以采用折半查找法

4、；B 在鏈表中查找結點只能采用順序查找法，不能采用折半查找法；C 一般情況下，順序查找法不如折半查找法的時間效率高；D 折半查找的過程可以用一棵稱之為判定樹”的二叉樹來描述。9 .在一棵m階B-樹中，除根結點之外的任何分支結點包含關鍵字的個數至少是()。A m/2-1 ； B. m/2 ； C. m/2-1； D. m/2。10若對序列 (49, 38, 65, 97, 76, 13, 27, 49進行快速)排序，則第一趟排序結束 (即確定了第 1 個分界元素的最終位置 )時，序列的狀態是 ( ) 。A . (13, 27, 49 , 38, 4

5、9, 76, 97, 65)； B . (13, 38, 27, 49 , 49, 76, 97, 65)；C . (13, 38, 49 , 27, 49, 97, 76, 65)； D . (13, 38, 49 , 27, 49, 76, 97, 65)。二、填空題 ( 本題共 20 分，每小題各 2 分)1 非空線性表在采 ( ) 存儲結構的情況下，刪除表的一個數據元素平均需要移動表中近一半元素的位置。2將一個長度為n的單鏈表鏈接到一個長度為m的單鏈表后面，該算法的時間復雜度用大0符號表示為( )。3 若完全二叉樹的葉結點的數目為k，且最下面一層的結點數大于1，則該完全二叉樹的深度為(

6、)。4 若深度為 8 的完全二叉樹的第 7 層有 10 個葉結點，則該二叉樹的結點總數為 ( ) 。5 在具有 n 個頂點的有向圖中，每個頂點的度最大可以達到 ( ) 。6 若對有向圖進行拓撲排序，則能夠得到拓撲序列的條件是 ( ) 。7 已知長度為 10 的順序表中數據元素按值從小到大排列。 若在該表中進行折半查找， 則平均查找長度 (ASL) 是 ( ) 。8 若在一棵 m 階 B- 樹的某個結點中插入一個新的關鍵字值而引起結點產生分裂， 則該結點中原有的關鍵 字值的數目是 ( ) 。9 有一種排序方法可能會出現這種情況： 最后一趟排序開始之前， 序列中所有的元素都不在其最終應該在 的位置

7、上，這種排序方法是 ( ) 。10 若按照泡排序法的思想將序列 (2, 12, 16, 5, 10) 中元素按值從小到大進行排序，整個排序過程中所 進行的元素之間的比較次數為 ( ) 。三、綜合題 ( 本題共 20 分，每小題各 5 分 )1 一般情況下， 當一個算法中需要建立多個堆棧時可以選用下列三種處理方案之一。 問：這三種方案之間 相比較各有什么優點和缺點？(1 )多個堆棧共享一個連續的存儲空間；(2 )分別建立多個采用順序存儲結構的堆棧；(3 )分別建立多個采用鏈式存儲結構的堆棧。2 已知二叉樹采用二叉鏈表存儲結構，根結點指針為T,鏈結點類型定義為：typedef struct nod

8、echar data; /* 數據域 */struct node *lchild, *rchild;/* 指向左、右子樹的指針域 */ *BTREE ； 下面的算法的功能是輸出二叉樹中所有葉結點的數據信息。 請在算法的空白處 ( 符號 處)填入合適內容，使算法完整。void FUNC(BTREE T) if(T!=NULL)if()printf(“ %c”-,dTata);FUNC();FUNC();3 .對給定AOE網(如題三3圖所示)，請完成(1 )分別求出各活動ai(i=1,2,，14)的最早開始時間與最晚開始時間；(以表格形式給出結果)(2 )求出所有關鍵路徑。 (請以圖形方式畫出各關

9、鍵路徑 )(說明：由于題三 3 圖在本網站內無法顯示，可參見指定教材 p280 頁 8-16 題)4 已知要將給定的關鍵字值序列(42, 51, 16, 26, 50, 25, 37, 68, 64, 33, 18)進行散列存儲，并且要求裝填因子(也稱負載因子)a 0.61 ,(1 )請利用除留余數法構造出合適的散列函數；(2 )請畫出利用該散列函數依次將序列中各關鍵字值插入到散列表以后表的狀態。設散列表初始為空， 并且采用線性探測再散列法處理散列沖突。四、算法設計題(本題 15 分) 假設長度為 n 的順序表 A1.n 中每個數據元素為一整數，請寫出按照下列思想將表 中數據元素按值從小到大進

10、行排序的算法：第 1 趟排序將最小值元素放在 A1 中，最大值元素放在An中；第2趟排序將次小值元素放在 A2中，次大值元素放在 An-1中；，依此下去， 直至排序結束。五、填空題 ( 本題共 20 分，每小題各 2 分 )1 已知某等比數列的第一項 a1 為 1 ，公比為 3，下列程序的功能是輸出該數列中小于 1000 的最大項 an 及其對應的 n 。請在程序的空白處 ( 符號 處)填入合適內容，使程序完整。main( ) int n=1, a=1, q=3;while(1)a=a*q;n+; if(a=1000)printf( “ n=%d,a=%d n” , n-1, );2 下列遞歸

11、函數 FUNC2 的功能是判斷整型數組 an 是否為遞增數組，即判斷數組的元素是否按值從小 到大排列。若是一個遞增數組，則函數返回 true ，否則，函數返回 false 。請在函數的空白處 ( 符號 處)填入合適內容，使函數完整。bool FUNC2(int a , int n) if(n=1)return true;if(n=2)return ;return & (an-1=an-2);3下列程序的功能是主函數調用 FUNC3 函數求方陣 a 中兩條對角線上元素之和。 請在程序的空白處 ( 符號 處)填入合適內容，使程序完整。#define N 10void FUNC3(int aNN,

12、int *p, int *q) int i;*p=0;*q=0;for(i=0; iN; i+)*p=*p+(*);*q=*q+(*);main( ) int aNN, i, j, x, y;for(i=0; iN; i+)for(j=0; jN; j+) scanf( “ %d” , *(a+i)+j);FUNC3(a, &x, &y); /* x ， y 中分別存放主對角線與副對角線上的元素之和 */ printf( “ %d, %d n ” , x, y);4 下列程序的功能是先通過鍵盤輸入一正整數，然后調用一遞歸函數 FUNC4 ，該函數將正整數轉換為對 應的數字字符組成的字符串顯示在

13、屏幕上。 例如：若輸入的正整數為 583 ，則屏幕上顯示的是字符串 583 。 請在程序的空白處 ( 符號 處)填入合適內容，使程序完整。#include void FUNC4(int n) int i;i=n/10;if()FUNC4(i);putchar();main( ) int n;printf( 請“輸入一正整數 n ： ” );scanf( “ %d” , &n);printf( 轉“換后的字符串是： ” );FUNC4(n);5.下列程序的功能是將小寫字母轉換成對應的大寫字母后的第2個字母，例如，將a轉換成C,將b轉換成D,其中，y轉換成A，z轉換成B。請在程序的空白處 ( 符號

14、 處)填入合適內容，使程序完整。#include main( ) char ch;while(ch=getchar( )!=n )if(ch=a & ch Z & ch= Z +2)6.下列函數 FUNC6 的功能是刪除字符串 s 中的所有空白字符，包括 Tab 字符、回車符以及換行符 請在函數的空白處 ( 符號 處)填入合適內容，使函數完整。#include #include #include FUNC6(char *s) int i, t;char c80;for(i=0,t=0; si; i+)if(!isspace()c=si;ct= 0;strcpy(s, c);7下列程序的功能是判

15、斷輸入的字符串是否是“回文 ”。(注：按順序讀與按逆序讀都一樣的字符串被稱為“回文 ”，例如： abcdcba) 。請在程序的空白處 ( 符號 處)填入合適內容，使程序完整。#include #include main( ) char ch81, *p=ch, *q;gets(p);q=p+;while()if(*p=*q)p+; q-;elsebreak;if(pq)printf( 該“字符串不是回文！ n” );elseprintf( 該“字符串是回文！ n” );8 下列程序的功能是：對于字符類型變量ch=108 ，保留中間兩位，而將高、低 3 位清零。請在程序的空白處 ( 符號 處)填

16、入合適內容，使程序完整。main( ) char ch;ch=108;ch=;printf(“ %d” , ch);9 設 file 為存放了整型數據的二進制文件。下列程序的功能是從該文件中讀入第 3 個數據輸出到屏幕上。 請在程序的空白處 ( 符號 處)填入合適內容，使程序完整。#include main( ) FILE *fp;int number;fp=fopen( “ file ” , “ rb ” );fseek(fp, , SEEK_SET);fread(, 1, fp);printf( “ %d” , number);fclose(fp);10 下列程序的功能是將一個磁盤中的二進

17、制文件復制到另一個磁盤中。兩個文件的文件名隨命令行一起 輸入，輸入時原有文件的文件名在前，新復制文件的文件名在后。請在程序的空白處 ( 符號 處)填入合適內容，使程序完整。#include main(int argc, char *argv ) FILE *old, *new;if(argc!=3)printf(“ You forgot to enter a filename!n ” );exit(0);if(old=fopen()=NULL)printf(“ Cannot open infile! n ” );exit(0);if(new=fopen()=NULL)printf(“ Cann

18、ot open outfi n ” );exit(0);while(!feof(old)fputc(fgetc(old), new);fclose(old); fclose(new);六、簡答題(本題共 20 分，每小題各 5 分)1在 C 語言中，函數調用時數據的傳遞通常有哪幾種方式？2在 C 語言中，指針可以做哪些運算？3 共用體 (union) 具有哪些基本特征？ 4使用文件的基本操作步驟是怎樣的？七、程序設計題(本題 15 分) 請編寫一程序，該程序的功能是找出并且刪除一維整型數組 a100 中的最小值元素。要求： 1 數組各元素通過鍵盤輸入獲得初值；2 所有對數組元素的引用必須通過指

19、針完成。八、程序設計題(本題 20 分)請僅編寫出一 C 語言函數 char *maxword(char *s, char *t)，該函數的功能是求出字符串 s 與字符串t 的最長公共單詞 (這里， 假設兩個字符串均由英文字母和空格字符組成)；若找到這樣的公共單詞， 函數返回該單詞，否則，函數返回 NULL 。例如：若 s=“This is C programming text ” ， t= “This is a text for C programming” ，則函數返回“ programming ”。要求： 1 函數中不得設置保存單詞的存儲空間；2 給出函數之前請用文字簡要敘述函數的基本思

20、想。2013年數據結構與C程序設計”代碼991)試題參考答案一、單項選擇題1C 2 A 3 D 4 B 5 C 6 B 7 D 8 A 9 C 10 D二、填空題1 順序 2 O(m) 3 log2k+1 4 235 5 2(n-1) 6 該有向圖中不存在 回路 7 2.9 8 m-1 9 插入排序法 10 9三、綜合題 1答：(1)多個堆棧共享一個連續的存儲空間，可以充分利用存儲空間，只有在整個存儲空間都用完時 才能產生溢出，其缺點是當一個堆棧溢出時需要向左、右棧查詢有無空閑單元。若有，則需要移動相應元 素和修改相關的棧底和棧頂指針的位置。當各個堆棧接近溢出時，查詢空閑單元、

21、移動元素和修改棧底棧 頂指針位置的操作頻繁，計算復雜，并且耗費時間。(2 )每個堆棧僅用一個順序存儲空間時， 操作簡便。 但難以確定初始分配存儲空間的大小， 空間分配少了， 容易產生溢出，空間分配多了，容易造成空間浪費；并且各個堆棧不能共享空間。(3 )一般情況下，分別建立多個鏈接堆棧不考慮堆棧的溢出(僅受用戶內存空間限制)，缺點是堆棧中各元素要通過指針鏈接，比順序存儲結構多占用存儲空間。2 (T-lchild=NULL & T-rchild=NULL)T-lchildT-rchild3(由于圖表顯示限制，此題答案見指定教材 (數據結構教程 第二版 (2012 年 4 月第 7 次印刷 ) 第

22、 418 頁 8-16 題)4(1) .根據a二散列表中存入的元素數/散列表的長度，得到表的長度為 18，因此，合適的散列函數應該為 H(k)=k MOD 17 。(2) .(由于圖表顯示限制， 此題答案見指定教材 (數據結構教程 第二版 (201 2 年4月第 7次印刷) 第 428 頁 9-15 題)四、算法設計題SORT(int A , int n) int ,i, j, min, max, temp;i=1;while(i=n/2)min=i;max=i;for(j=i+1;jn-i+1;j+)if(AjAmax) max=j;*/ /* 確定某趟排序的最小值元素和最大值元素 if(m

23、in!=i)temp=Amin; Amin=Ai; Ai=temp; /* 交換 Amin 與 Ai 的位置 */ if(max!=n-i+1) if(max=i)temp=Amin; Amin=An-i+1; An-i+1=temp; /*交換 Amin 與 An-i+1 的位置 */elsetemp=Amax; Amax=An-i+1; An-i+1=temp; /* 交換 Amax 與 An-i+1 的位置 */ i+;1 break a/q2an-1=an-2 FUNC2(a, n-1)3n%10+ O5 ch-=30 ch-=266 *(s+i) t+7strlen(p)-1 pq8

24、ch & 24a. ”“ wb ”五、填空題 i!=0argv2,(*(a+i)+i) (*(a+i)+N-i-1) 49 4 &number 10argv1,“ rb六、簡答題1答：通常有下列三種方式：(1) 參數傳遞方式：函數調用時根據實參傳遞給形參內容的不同又分為值傳遞與地址傳遞兩種。(2) 通過 return 語句傳遞數據：被調用函數可以通過 return 語句將函數值傳遞給調用函數。(3) 利用全局變量傳遞數據。 2答：指針可以進行下列三種運算：(1) 指針加 / 減一個整數。表示以當前指針所指單元的地址為起點的后或前整數個數據的地址。(2) 指針減指針。表示兩個地址之間的數據個數。

25、 (指針加指針為非法運算)(3) 比較。表示同類型的兩個指針所指對象在地址位置上的關系。 3答：共用體具有以下三個特征：(1) 共用體變量的成員共用一塊存儲空間，共用體變量所占用的字節數等于最長成員所占用的字節數；(2) 共用體不能在定義時進行初始化；(3) 共用體中的成員每次只能有一個起作用，當存入新成員時，原來的成員失效，其值被覆蓋。 4答：使用文件的基本操作一般有下列五個步驟：(1) 在程序中包含頭文件 stdio.h(2) 定義文件指針。例如： FILE *fp;(3) 打開文件，使文件指針與磁盤中的實際存儲的數據文件建立關聯。例如： fp=fopen( “ test.txt ” , “ r ” );(4) 對文件進行讀寫操作。例如： fread(f, 4, 2, fp);(5) 文件使用完畢后，關閉文件。例如： fclose(fp);七、程序設計題#include main( ) int a100, i, *p, k=0;p=a;for(i=0; i100; i+)scanf( “ %d” , p+i); /* 對數組進行數據輸入 */for(i=1; i*(p+i) k=i;for(i=k; i99; i+) *(p+i)