1、精選文檔第一部分  數據結構一、是非推斷題（本題共10分，每小題各1分）（對于下面給出的論述，你認為正確，請在小題后的括號中填入符號，否則，填入符號×）1對算法進行分析的目的是為了提高算法的質量。 （    ）2一般狀況下，雙向鏈表比單向鏈表要占用更多的存儲空間。 （    ）3將插入與刪除操作限制在表的一端的線性表被稱為堆棧。 （    ）4完全二叉樹不肯定是滿二叉樹，滿二叉樹肯定是完全二叉樹。 （    ）5利用二叉樹的前序遍歷序列和后序遍歷序列肯定可以構造出一棵二叉樹。 （

2、60;   ）6鄰接表中邊結點數目為偶數的圖肯定是無向圖。 （    ）7拓撲排序不是檢測有向圖中是否存在回路的惟一方法。 （    ）8接受折半查找的線性表只要求表中元素按值的大小有序排列就可以。 （    ）9對具有n個元素的序列進行插入排序，排序的總趟數為n-1。 （    ）10無論什么狀況，快速排序法比其他排序法的時間效率都要高。 （    ）二、填空題（本題共15分，每小題各1分）1若長度為n的線性表接受挨次存儲結構，當不溢出時，在其第i個位置(1in+1)插入一個新的數據

3、元素之前需要依次移動（      ）個元素的位置。2在非空雙向循環鏈表中由q指的鏈結點前面插入一個p指的鏈結點的過程對應的語句依次為：p->rlink=q; p->llink=q->llink; q->llink=p;  （               ） 。（空白處為一條語句）3在實際應用中，當堆棧的最大長度難以估量時，堆棧最好接受（       ）存儲結構。4若a,b,

4、c,d是初始為空的隊列的輸入序列，則此時該隊列的輸出序列是 （       ）。5若具有n個結點的二叉樹接受二叉鏈表存儲，則鏈表中有（       ）個指針域存放著NULL。6已知二叉樹的前序遍歷序列為ABDCEFG，中序遍歷序列為DBCAFEG，其后序遍歷序列為（      ）。7接受“逐點插入法”建立序列(54,28,16,34,73,62,95,60,26,43)的二叉排序樹后，在該二叉排序樹中查找到數據元素62時一共進行了（     &#

5、160; ）次元素之間的比較。8在一個圖中，全部頂點的度數之和等于全部邊數的（       ）倍。9具有n個頂點的有向圖最多有（      ）條邊。10具有n個頂點的無向連通圖接受鄰接矩陣表示，鄰接矩陣中至少有（      ）個非零元素。11將數據元素2,4,6,8,10,12,14,16,18,20依次存放于一個一維數組中(設數組下標從0開頭)，然后接受折半查找方法查找元素12，被比較過的數組元素的下標依次為（       ）。12若

6、一個待散列存儲的線性表為K=(18,25,63,50,42,32,9,45)，散列函數為H(k)=k MOD 9，則與元素18發生沖突的元素有（       ）個。13若對序列(1,2,5,3,4)接受泡排序法按元素值從小到大進行排序，則整個排序過程中進行的元素之間的比較次數為（      ）。14若對序列(tang, deng, an, wang, shi, bai, fang, liu)接受選擇排序法按字典挨次進行排序，則第三趟排序結束時序列的狀態是（      ）。15

7、設有10000個元素組成的序列，期望盡快選擇出其中前10個(僅挑出前10個!)最大值元，在不轉變已有算法結構的前提下，插入排序法、快速排序法、積累排序法和泡排序法這4種內排序算法中，最合適的是（       ） 。三、綜合題（本題共15分，每小題各5分）1證明：具有n個結點的非空滿二叉樹，其葉結點的數目為(n+1)/2。2已知某帶權連通圖接受鄰接矩陣存儲，鄰接矩陣以三元組表形式給出。鄰接矩陣下三角形部分的元素（不包括主對角線上元素）對應的各三元組分別為 )，µ)，(5,2,4)，(5,3,µ(2,1,7)，(3,1,6)，(3,2,8

8、)，(4,1,9)，(4,2,4)，(4,3,6)，(5,1, (5,4,2)。請分別畫出該連通圖全部可能的最小生成樹。3已知散列函數為H(key)=(key%3) MOD 11，散列地址空間為0.10，并且接受線性探測再散列法處理沖突。請畫出在初始為空的散列表中依次插入22,41,53,8,46,30,1,31,66以后散列表的狀態。四、算法設計題（本題10分）    結點的祖先定義為從根結點到該結點的全部分支上經過的結點。    已知非空二叉排序樹接受二叉鏈表存儲結構，鏈結點構造為 lchild  data rchild,

9、0; 根結點指針為T。請寫一非遞歸算法, 依次打印數據信息為item的結點的祖先結點。設結點的數據信息分別為整數，并且假設該結點的祖先結點存在。其次部分  C語言程序設計五、單項選擇題（本題共20分，每小題各1分）1一個C語言程序是由（     ）。A一個主程序和若干個子程序組成      B函數組成C若干過程組成                    &#

10、160; D若干子程序組成 2當把以下四個表達式用作if語句的把握表達式時，其中有一個選項與其他三個選項的含義不同，這個選項是（     ）。Ak%2           Bk%2=1         C(k%2)!=0      D!k%2=13下列運算符中優先級最低的是（     ）。A+    

11、;         B&&              C?:           D!=4以下能夠正確地定義整型變量a,b和c，并且為其賦初值5的語句是（     ）。Aint a=b=c=5;              &

12、#160;         Bint a,b,c=5;Ca=5,b=5,c=5;                        Da=b=c=5;5若有說明：double y=0.5,z=1.5; int x=10; 則能夠正確使用C語言庫函數的賦值語句是（      ）。Az=exp(y)+fabs(x);   &#

13、160;                By=log10(y)+pow(y);Cz=sqrt(y-z);                         Dx=(int)(atan2(double)x,y)+exp(y-0.2);6以下對二維數組a的正確說明是（     ）。Aint a3

14、;       Bfloat a(3,4);       Cdouble a14;      Dfloat a(3)(4);7若有條件表達式 (exp) ? a+ : b-，則以下表達式中能夠完全等價于表達式(exp)的是（     ）。A(exp=0)       B(exp!=0)          C(exp=1)  &#

15、160;       D(exp!=1)8以下不正確的if語句形式是（     ）。Aif(a>b&&a!=b);                      Bif(a=b) a+=b;Cif(a<b) a+;b+;               

16、60;   Dif(a!=b) scanf(“%d”,&a) else scanf(“%d”,&b);9若有以下語句    int x=3;    do printf(“%dn”,x-=2); while(!(-x);則上面程序段（     ）。A輸出結果是1    B輸出結果是3和0    C輸出結果是1和-2    D是死循環10以下for循環語句的執行次數是（     ）。 

17、   for(x=0,y=0;(y=123)&&(x<4);x+);A執行4次         B執行3次         C是無限循環       D循環次數不定11設有如下程序段：    t=0;    while(printf(“*”)        t+;     &#

18、160;  if(t<3) break;下面給出的4個描述中，正確的是（     ）。A其中循環把握表達式是不合法的          B其中循環把握表達式與0等價C其中循環把握表達式與0等價            D以上說法都不對12C語言允許函數值類型缺省定義，此時該函數值隱含的類型是（     ）。Aint類型    

19、;     Bfloat類型          Clong類型        Ddouble類型13對于C語言而言，以下正確的描述是（     ）。A函數的定義可以嵌套，但函數的調用不行以嵌套B函數的定義不行以嵌套，但函數的調用可以嵌套C函數的定義和函數的調用都不行以嵌套D函數的定義和函數的調用都可以嵌套14以下關于宏替換的敘述中，錯誤的是（     ）。A宏替換不占

20、用運行時間                 B宏名無類型C宏替換只是字符替換                   D宏名必需用大寫字母表示15若已有定義：int k=2; int *p1, *p2; 且p1和p2均已指向變量k，則下面不能正確執行的賦值語句是（     ）。Ak=*p1+*p2;   

21、;      Bp1=p2;          Cp2=k;        Dk=*p1*(*p2);16若已有定義：int a23; 則對a數組的第i行第j列(假設i,j已正確說明并已賦值)元素地址的正確引用為（     ）。A*(a+j)           Ba+j     

22、0;     C(a+i)           D*(a+j)17若有說明：int *p,m=5,n; 則下面給出的4個程序段中，正確的是（     ）。Ap=&n;                              

23、60; Bp=&n;    scanf(“%d”,&p);                          scanf(“%d”,*p);Cscanf(“%d”,&p);                      

24、  Dp=&n;*p=n;                                    *p=m;18已有函數max(a,b)，為了讓函數指針變量p指向函數max，正確的賦值方法是（     ）。Ap=max;        B*p

25、=max;        Cp=max(a,b);       D*p=max(a,b);19以下對結構體變量stu1中成員age的不正確引用的是（     ）。struct student    int age;    int num;stu1,*p;p=&stu1;Astudent.age        Bstu1.age   

26、;      Cp->age         D(*p).age20在C語言中，庫函數fgets(str,n,fp)的功能是（     ）。A從str中讀取至多n個字符到文件fpB從文件fp中讀取長度為n的字符串存入str指向的內存C從文件fp中讀取長度不超過n-1的字符串存入str指向的內存D從文件fp中讀取n個字符串存入str指向的內存六、填空題（本題共15分，每小題各3分）1若運行以下程序時，從鍵盤輸入2473<CR>（<CR

27、>表示回車。下同），則下面程序的運行結果是（     ）。#include <stdio.h>main( )   int c;    while(c=getchar()!=n)        switch(c-2)            case 0:            cas

28、e 1: putchar(c+4);            case 2: putchar(c+4); break;            case 3: putchar(c+3);            default: putchar(c+2); break;         

29、60;     printf(“n”):2當從鍵盤上輸入18<CR>以后，下面程序的運行結果是（      ）。main( )   int x,u,i,j,a8;    scanf(“%d”,&x);    i=0;   do        u=x/2;        a=x%2;  &#

30、160;     i+;         x=u;    while(x>=1);    for(j=i-1;j>=0;j-)        printf(“%d”,aj);3以下程序的運行結果是（     ）。main( )   increment();    increment(); 

31、60; increment();increment()   static int y=0;    y+=1;    printf(“%d”,y);4下面程序的運行結果是（     ）。#include <stdio.h>main( )     static char a=“Language”,b=“programe”;    char *p1,*p2;    int i;    p1=

32、a;    p2=b;    for(i=0;i<=7;i+)        if(*(p1+i)=*(p2+i)            printf(“%c”,*(p1+i);5以下程序用以輸出結構體變量bt所占內存單元的字節數，請在程序的空白處（橫線上方）填上適當內容。struct ps    double i;     char arr20;main( ) 

33、;  struct ps bt;    printf(“bt size is :%dn”, （      ）);七、程序設計題（本題5分）    所謂“水仙花數”是指一個三位數，其各位數字立方之和等于該數本身。例如：153是一個“水仙花數”，由于135333=153。請編寫輸出1000以內全部“水仙花數”的程序。#include <stdio.h>int main(void)  int i, j, k;  for (i = 1; i <= 9; i +) &

34、#160;  for (j = 0; j <= 9; j +)      for (k = 0; k <= 9; k +)               if (i*i*i + j*j*j + k*k*k = 100 * i + 10*j + k)           printf(&qu

35、ot;%dn", 100*i+10*j+k);      八、程序設計題（本題10分）    請編寫一C語言程序，該程序實現對從鍵盤輸入一些字符，逐個把它們送到磁盤上去，直到輸入一個#為止。程序源代碼：#include "stdio.h"main() FILE *fp;char ch,filename10;scanf("%s",filename);if(fp=fopen(filename,"w")=NULL)printf("cannot open

36、 filen");exit(0);ch=getchar();ch=getchar();while(ch!='#')fputc(ch,fp);putchar(ch);ch=getchar();fclose(fp);第一部分  數據結構一、是非推斷題1對算法進行分析的目的是為了提高算法的質量。 （    ）2一般狀況下，雙向鏈表比單向鏈表要占用更多的存儲空間。 （    ）3將插入與刪除操作限制在表的一端的線性表被稱為堆棧。 （    

37、;）4完全二叉樹不肯定是滿二叉樹，滿二叉樹肯定是完全二叉樹。 （    ）5利用二叉樹的前序遍歷序列和后序遍歷序列肯定可以構造出一棵二叉樹。（已知前序和中序，恢復二叉樹）6鄰接表中邊結點數目為偶數的圖肯定是無向圖。（    ） 無向圖肯定是偶數，單偶數不肯定是無向圖7拓撲排序不是檢測有向圖中是否存在回路的惟一方法。 （    ）8接受折半查找的線性表只要求表中元素按值的大小有序排列就可以。 （    ）二叉樹9對具有n個元素的序列進行插

38、入排序，排序的總趟數為n-1。 （    ）10無論什么狀況，快速排序法比其他排序法的時間效率都要高。 （    ）二、填空題1若長度為n的線性表接受挨次存儲結構，當不溢出時，在其第i個位置(1in+1)插入一個新的數據元素之前需要依次移動（ n-i+1     ）個元素的位置。2在非空雙向循環鏈表中由q指的鏈結點前面插入一個p指的鏈結點的過程對應的語句依次為：p->rlink=q; p->llink=q->llink; q->ll

39、ink=p;  （q->llink->rlink->p ） 。（空白處為一條語句）3在實際應用中，當堆棧的最大長度難以估量時，堆棧最好接受（  鏈式   ）存儲結構。4若a,b,c,d是初始為空的隊列的輸入序列，則此時該隊列的輸出序列是 （       ）。5若具有n個結點的二叉樹接受二叉鏈表存儲，則鏈表中有（       ）個指針域存放著NULL。6已知二叉樹的前序遍

40、歷序列為ABDCEFG，中序遍歷序列為DBCAFEG，其后序遍歷序列為（DCBFGEA）。7接受“逐點插入法”建立序列(54,28,16,34,73,62,95,60,26,43)的二叉排序樹后，在該二叉排序樹中查找到數據元素62時一共進行了（  3   ）次元素之間的比較。8在一個圖中，全部頂點的度數之和等于全部邊數的（  2    ）倍。9具有n個頂點的有向圖最多有（      ）條邊。10具有n個頂點的無向連通圖接受鄰接

41、矩陣表示，鄰接矩陣中至少有（      ）個非零元素。11將數據元素2,4,6,8,10,12,14,16,18,20依次存放于一個一維數組中(設數組下標從0開頭)，然后接受折半查找方法查找元素12，被比較過的數組元素的下標依次為（       ）。12若一個待散列存儲的線性表為K=(18,25,63,50,42,32,9,45)，散列函數為H(k)=k MOD 9，則與元素18發生沖突的元素有（    3 

42、0;）個。13若對序列(1,2,5,3,4)接受泡排序法按元素值從小到大進行排序，則整個排序過程中進行的元素之間的比較次數為（  4    ）。14若對序列(tang, deng, an, wang, shi, bai, fang, liu)接受選擇排序法按字典挨次進行排序，則第三趟排序結束時序列的狀態是（      ）。15設有10000個元素組成的序列，期望盡快選擇出其中前10個(僅挑出前10個!)最大值元，在不轉變已有算法結構的前提下，插入排序法、快速排序法、積累排序法

43、和泡排序法這4種內排序算法中，最合適的是（堆排序）。 三、綜合題（本題共15分，每小題各5分）1證明：具有n個結點的非空滿二叉樹，其葉結點的數目為(n+1)/2。   取個中間變量k表層數。2已知某帶權連通圖接受鄰接矩陣存儲，鄰接矩陣以三元組表形式給出。鄰接矩陣下三角形部分的元素（不包括主對角線上元素）對應的各三元組分別為(2,1,7)，(3,1,6)，(3,2,8)，(4,1,9)，(4,2,4)，(4,3,6)，(5,1,µ)，(5,2,4)，(5,3,µ)，(5,4,2)。請分別畫出該連通圖全部可能的最小生成樹。 &#

44、160;4-2 或者 5-2 所以不止一個3已知散列函數為H(key)=(key%3) MOD 11，散列地址空間為0.10，并且接受線性探測再散列法處理沖突。請畫出在初始為空的散列表中依次插入22,41,53,8,46,30,1,31,66以后散列表的狀態。四、算法設計題（本題10分）    結點的祖先定義為從根結點到該結點的全部分支上經過的結點。    已知非空二叉排序樹接受二叉鏈表存儲結構，鏈結點構造為 lchild  data rchild,  根結點指針為T。請寫一

45、非遞歸算法, 依次打印數據信息為item的結點的祖先結點。設結點的數據信息分別為整數，并且假設該結點的祖先結點存在。先找item父節點p，再找p父節點打印完設為p，再找其父節點。只要有關系就靠這關系找！ 其次部分  C語言程序設計五、單項選擇題（本題共20分，每小題各1分）1一個C語言程序是由（  a   ）。A一個主程序和若干個子程序組成      B函數組成C若干過程組成       

46、;               D若干子程序組成2當把以下四個表達式用作if語句的把握表達式時，其中有一個選項與其他三個選項的含義不同，這個選項是（   a  ）。Ak%2           Bk%2=1       

47、  C(k%2)!=0      D!k%2=13下列運算符中優先級最低的是（  c   ）。A+             B&&              C?: 

48、0;         D!=4以下能夠正確地定義整型變量a,b和c，并且為其賦初值5的語句是（ a    ）。Aint a=b=c=5;                        Bint a,b,c=5;Ca=5,b=5,c

49、=5;                        Da=b=c=5;5若有說明：double y=0.5,z=1.5; int x=10; 則能夠正確使用C語言庫函數的賦值語句是（      ）。Az=exp(y)+fabs(x);     &#

50、160;              By=log10(y)+pow(y);Cz=sqrt(y-z);                         Dx=(int)(atan2(double)x,y)+exp

51、(y-0.2);6以下對二維數組a的正確說明是（   c  ）。Aint a3;       Bfloat a(3,4);       Cdouble a14;      Dfloat a(3)(4);7若有條件表達式 (exp) ? a+ : b-，則以下表達式中能夠完全等價于表達式(exp)的是（    

52、 ）。A(exp=0)       B(exp!=0)          C(exp=1)          D(exp!=1)8以下不正確的if語句形式是（     ）。Aif(a>b&&a!=b);    

53、;                  Bif(a=b) a+=b;Cif(a<b) a+;b+;                   Dif(a!=b) scanf(“%d”,&a) else scanf(“%d”,

54、&b);9若有以下語句    int x=3;    do printf(“%dn”,x-=2); while(!(-x);則上面程序段（     ）。A輸出結果是1    B輸出結果是3和0    C輸出結果是1和-2    D是死循環10以下for循環語句的執行次數是（     ）。&#

55、160;   for(x=0,y=0;(y=123)&&(x<4);x+);A執行4次         B執行3次         C是無限循環       D循環次數不定11設有如下程序段：    t=0;    w

56、hile(printf(“*”)        t+;        if(t<3) break;下面給出的4個描述中，正確的是（     ）。A其中循環把握表達式是不合法的          B其中循環把握表達式與0等價C其中循環把握表達式與0等價   

57、;         D以上說法都不對12C語言允許函數值類型缺省定義，此時該函數值隱含的類型是（     ）。Aint類型         Bfloat類型          Clong類型      

58、0; Ddouble類型13對于C語言而言，以下正確的描述是（     ）。A函數的定義可以嵌套，但函數的調用不行以嵌套B函數的定義不行以嵌套，但函數的調用可以嵌套C函數的定義和函數的調用都不行以嵌套D函數的定義和函數的調用都可以嵌套14以下關于宏替換的敘述中，錯誤的是（     ）。A宏替換不占用運行時間               &

59、#160; B宏名無類型C宏替換只是字符替換                   D宏名必需用大寫字母表示15若已有定義：int k=2; int *p1, *p2; 且p1和p2均已指向變量k，則下面不能正確執行的賦值語句是（     ）。Ak=*p1+*p2;       &

60、#160; Bp1=p2;          Cp2=k;        Dk=*p1*(*p2);16若已有定義：int a23; 則對a數組的第i行第j列(假設i,j已正確說明并已賦值)元素地址的正確引用為（     ）。A*(a+j)          

61、 Ba+j           C(a+i)           D*(a+j)17若有說明：int *p,m=5,n; 則下面給出的4個程序段中，正確的是（     ）。Ap=&n;          

62、0;                     Bp=&n;    scanf(“%d”,&p);                    

63、;      scanf(“%d”,*p);Cscanf(“%d”,&p);                        Dp=&n;*p=n;           

64、60;                        *p=m;18已有函數max(a,b)，為了讓函數指針變量p指向函數max，正確的賦值方法是（     ）。Ap=max;        B*p=max;  

65、;      Cp=max(a,b);       D*p=max(a,b);19以下對結構體變量stu1中成員age的不正確引用的是（     ）。struct student    int age;    int num;stu1,*p;p=&stu1;Astudent.age    &

66、#160;   Bstu1.age         Cp->age         D(*p).age20在C語言中，庫函數fgets(str,n,fp)的功能是（     ）。A從str中讀取至多n個字符到文件fpB從文件fp中讀取長度為n的字符串存入str指向的內存C從文件fp中讀取長度不超過n-1的字符串存入str指向的內存D

67、從文件fp中讀取n個字符串存入str指向的內存六、填空題（本題共15分，每小題各3分）1若運行以下程序時，從鍵盤輸入2473<CR>（<CR>表示回車。下同），則下面程序的運行結果是（     ）。#include <stdio.h>main( )   int c;    while(c=getchar()!=n)        switch(c-2)            case 0: