華南農(nóng)業(yè)大學(xué)期中測驗(yàn)
2004學(xué)年第二學(xué)期　 考試科目：　數(shù)據(jù)結(jié)構(gòu)　　　
考試類型：（開卷/閉卷）　　　考試時(shí)間：　120  　分鐘
學(xué)號                  姓名                 年級專業(yè)                     

單選題（每題2分，共 30 分）
研究數(shù)據(jù)結(jié)構(gòu)就是研究（ ）
A．	數(shù)據(jù)的邏輯結(jié)構(gòu)
B．	數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
C．	數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)
D．	數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其數(shù)據(jù)在運(yùn)算上的實(shí)現(xiàn)
鏈表不具有的特點(diǎn)是（  ）。
A.	可隨機(jī)訪問任一個(gè)元素       B. 插入刪除不B.	需要移動(dòng)元素
C. 不必事先估計(jì)存儲(chǔ)空間       D. 所需空間與線性表的長度成正比
設(shè)一個(gè)棧的輸入序列是A、B、C、D，下列出棧序列中不正確的是（  ）
A．ABCD   B. DCBA    C.  ACDB     D. DABC
一棵深度為7（根的層次號為0）的完全二叉樹有（   ）個(gè)葉子結(jié)點(diǎn)。
A.  256     B. 255     C. 128      D. 127
二維數(shù)組A[4][5]采用行序?yàn)橹餍蚍绞酱鎯?chǔ)，每個(gè)數(shù)據(jù)元素占4個(gè)存 儲(chǔ)單元，且A[2][2]的存儲(chǔ)地址是1000，則A[3][3]的地址是（ ）
A．1005     B. 1006    C. 1024     D. 1026.
若循環(huán)隊(duì)列用數(shù)組A[0,m-1]存放元素，其頭尾指針分別為front 和rear，則當(dāng)前隊(duì)列的長度是（  ）。
A. (rear-front+m)%m             B. rear-front+1
C. rear-front-1                  D. (rear-front)%m 
7．將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)編號為0，則編號位39的結(jié)點(diǎn)的左孩子的編號為（ ）。
A．78    B. 79     C.  80       D.  81
8．利用逐點(diǎn)插入法建立序列（50，72，85，75，20，45，35，30，26）對應(yīng)的二叉排序樹以后，查找元素45要進(jìn)行（  ）元素的比較。
A．3次   B. 4次    C. 7次     D. 9次
9．以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)，是非線性數(shù)據(jù)結(jié)構(gòu)（）
A. 樹     B. 字符串    C. 隊(duì)    D. 棧
10. 兩種常用的稀疏矩陣壓縮存儲(chǔ)方式是（   ）。
A. 二維數(shù)組和三維數(shù)組         B. 三元組和散列
C. 三元組表和十字鏈表         D. 散列和十字鏈表


判斷題（每題2分，共10分）
線性表的每一個(gè)結(jié)點(diǎn)都有一個(gè)前驅(qū)和一個(gè)后繼。
一維數(shù)組實(shí)質(zhì)是線性表的一種。
順序存儲(chǔ)結(jié)構(gòu)只能用來存放線性結(jié)構(gòu)；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用來存放非線性結(jié)構(gòu)。
任意一棵樹均可轉(zhuǎn)換成二叉樹，再進(jìn)行存儲(chǔ)。
將一新結(jié)點(diǎn)插入二叉排序樹中，該結(jié)點(diǎn)既可以成為葉子結(jié)點(diǎn)也可以成為非葉子結(jié)點(diǎn)。

完成算法設(shè)計(jì)（每空3,共18分）
2．	單鏈表的刪除
typedef  struct Node
{ DataType info;
  struct Node *link;			
} *PNode,*LinkList;

int  delete_link( LinkList llist, DataType x )
/* 在llist帶有頭結(jié)點(diǎn)的單鏈表中刪除第一個(gè)值為x的結(jié)點(diǎn) */
    { PNode p, q;      	
	           ⑴           ;     /*找值為x的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的存儲(chǔ)位置 */
      while( p->link != NULL && p->link->info != x )
       	    ⑵    	;
      if( p->link == NULL )  			/* 沒找到值為x的結(jié)點(diǎn) */
		 { printf(”Not exist!\n ”);
           return(0);
		}
	  else 
{	q = p->link;	  			/* 找到值為x的結(jié)點(diǎn) */
       		       ⑶               ; 	/* 刪除該結(jié)點(diǎn) */
       		       ⑷               ;      
           return(1); 
		}
 }
3．	進(jìn)隊(duì)列?
#define MAXNUM 100
struct SeqQueue
{ DataType a[Maxnum];
 int f,r;
};
typedef struct SeqQueue *PSeqQueue;
void  enQueue_seq( PSeqQueue paqu, DataType x )
/* 在隊(duì)列中插入一元素x */
{
  if(            ⑸                )
      printf( "Full queue.\n" );
  else
	{
	  paqu->q[paqu->r] = x;
	            ⑹                ;
	 }
}



構(gòu)造題（共8分x2=16分）

1．	假設(shè)一顆二叉樹的前序遍歷序列為 ABDFCE ，2．	中序遍歷序列DFBACE。
要求：（1）畫出該樹(5分)
     （2）寫出該樹的后序遍歷序列(5分)。
3．	用給出的一組字符A，4．	B，5．	C，6．	D，7．	E的權(quán)值是{3，8．	4，9．	5，10．	6，11．	8}，12．	按權(quán)值左小右大建立一棵哈夫曼樹(6分)，13．	并給出每個(gè)字符的哈夫曼編碼(2分)。
算法設(shè)計(jì)題（26分）
1．設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)將由q所指向的新結(jié)點(diǎn)插入到單鏈表中指針p所指向的結(jié)點(diǎn)前。（12分）


2．設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，類型定義如下：
struct node
{ int data;
  struct node *lchild,*rchild;
};
其中data域中存放一個(gè)整數(shù)。設(shè)計(jì)一個(gè)算法，求此二叉樹中data域的值為最小的結(jié)點(diǎn)。（14分）
    
華南農(nóng)業(yè)大學(xué)測驗(yàn)答題紙
2004學(xué)年第二學(xué)期　 考試科目：　數(shù)據(jù)結(jié)構(gòu)　　　
考試類型：（閉卷）　　　考試時(shí)間：　120  　分鐘
學(xué)號                  姓名                 年級專業(yè)                     

 
題號	一	二	三  	四	五	總分	   
得分							   
評閱人		 

1、	單選題（每題2分，2、	共 30 分）
 
題號	 1	2	3	4	5	6	7	8	9	10	   
答案											 
3、	判斷題（每題2分，4、	共10分，5、	正確√、錯(cuò)誤╳）
 
題號	 1	2	3	4	5	   
答案						 
6、	完成算法設(shè)計(jì)（每空3,共18分）


⑴                                   
⑵                                   
⑶                                   
⑷                                   
⑸                                   
⑹                                   
四、構(gòu)造題（共16分）