數(shù)據(jù)結構考試試題一及參考答案

1、課程名稱：數(shù)據(jù)結構考試時間：姓名：班級：學號：一、選擇題 （每題 2 分，共 20 分）（） 1、二叉樹是非線性數(shù)據(jù)結構，所以_。）順序存儲結構和鏈式存儲結構都能存儲;）它不能用鏈式存儲結構存儲 ;）它不能用順序存儲結構存儲 ;）順序存儲結構和鏈式存儲結構都不能使用（） 2、數(shù)據(jù)在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為 _。A ）隨機存儲結構B）邏輯結構C）順序存儲結構D）鏈式存儲結構（） 3、判定一個棧 ST（最多元素為 m0）為空的條件是 _。A ） ST-top0B）ST-top=0C） ST-topm0D）ST-top=m0（）4、已知圖的鄰接矩陣如下，根據(jù)算

2、法思想，則從頂點0 出發(fā)按深度優(yōu)先遍歷的結點序列是 _。01111011001001A024315610001001100110B. 01365421011010C. 03615420001101D.01342561100010（） 5、用 5 個權值 3, 2, 4, 5, 1 構造的哈夫曼（ Huffman）樹的帶權路徑長度是A）32B）33C）34D）15（）6、給定二叉樹的兩種遍歷序列，分別是：先序遍歷序列：D，A ，C，E，B，H，F(xiàn)， G， I；中序遍歷序列： D，C，B，E，H，A ， G，I， F；則其后序遍歷序列為 _。A ） BHECGIFADB） BHECIGADFC）

3、BHECIGFADD） CHEBIGADF（） 7、有 8 個結點的有向圖最多有 _條邊。A）56B） 28C）14D）112（） 8、對 22 個記錄的有序表作折半查找，當查找失敗時，至少需要比較_次關鍵字。A ）3B）4C）5D）6（ ） 9、對個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數(shù)最多。）從小到大排列好的）從大到小排列好的）元素無序）元素基本有序（ ） 10、下列排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為_。） 希爾排序） 冒泡排序）選擇排序）插入排序二、填空題 （每空 2 分，共 20 分

4、）1、在線性結構中，第一個結點前驅結點，其余每個結點有且只有1 個前驅結點；最后一個結點后續(xù)結點，其余每個結點有且只有1 個后續(xù)結點。2、線性表、棧和隊列都是結構，可以在線性表的位置插入和刪除元素；對于棧只能在插入和刪除元素；對于隊列只能在插入和刪除元素。3、設用一維數(shù)組 A1, ,n來表示一個棧， An 為棧底 (注意 !) ，用整型變量 T 指示當前棧頂位置，AT 為棧頂元素。往棧中推入（PUSH）一個新元素時，變量 T 的值 _；從棧中彈出（ POP）一個元素時，變量T 的值 _。4、由個結點所構成的二叉樹有_種形態(tài)。三、算法閱讀理解題 （每題 10 分，共 30 分）1、分析并寫出下列

5、程序段的輸出結果（隊列中的元素類型為char）。void main( )Queue Q; / Queue表示隊列InitQueue (Q);Char x= e ,y= c;EnQueue (Q, h/EnQueue);表示入隊操作EnQueue (Q, r );EnQueue (Q, y);DeQueue (Q,x); / DeQueue表示出隊操作EnQueue (Q,x);DeQueue (Q,x);EnQueue (Q, a );while(!QueueEmpty(Q)DeQueue (Q,y);printf(y);Printf(x);2、設如下圖所示的二叉樹（ lchild,data,

6、rchild ）。其中二叉樹 BTREE，執(zhí)行算法BTREE 的存儲結構為二叉鏈表， root 為根指針，結點結構為： lchild ，rchild 分別為指向左右孩子的指針， data為字符型， 對traversal(root)，試分析算法作用并指出算法執(zhí)行后的輸出結果。樹的結點類型定義如下：Astruct nodeBDCFGchar data;Estruct node *lchild, rchild;所用算法如下：voidtraversal(structnode*root)if (root)printf(“ %coot”,-data);rtraversal(root-lchild);pri

7、ntf(“ %c” ,-data);roottraversal(root-rchild);3、下面程序實現(xiàn)了對輸入數(shù)據(jù)進行直接插入排序的過程，并輸出排序后的結果請在 _處給出所缺失的內容。typedef structInt key;int other_data;RecordType;voidInsSort(RecordTyper,int length)/* 對記錄數(shù)組 r 做直接插入排序， length 為數(shù)組中待排序記錄的數(shù)目*/int i,j;for (i=2;i=length;i+)（1）;/* 設置哨兵 */j=i-1;（2）； /* 尋找插入位置 */rj+1= rj;j=j-1;（

8、3）;/* 將待插入記錄插入到已排序的序列中*/void main()int i,j;RecordType r20;int len;printf( 請輸入待排序記錄的長度:);scanf(%d,&len);for(i=1;i=len;i+)printf( 請輸入第 %d 個記錄元素 :,i);scanf(%d,&j);（4）;/* 將輸入的數(shù)據(jù)保存到結構體中的數(shù)據(jù)域中*/for(i=1;i=len;i+)printf(%d,ri.key);printf(n);InsSort(r,len);for(i=1;i=len;i+)printf(%d , （ 5） ); /* 輸出排序后的數(shù)據(jù) */ p

9、rintf(n);四、算法設計題 （每題 15 分，共 30 分）1、下面給出了單鏈表的結構體類型定義，請編寫算法，由鍵盤輸入一組數(shù)據(jù)，用尾插法建立一個單鏈表并輸出鏈表中的數(shù)據(jù)。編寫算法時，給出算法的功能說明和一定數(shù)量的注釋。typedef char ElemType;typedef struct Node/* 結點類型定義*/ElemType data;struct Node* next;Node, *LinkList;/* LinkList為結構指針類型*/2、 編寫簡單選擇排序算法程序。實現(xiàn)對鍵盤輸入的一組數(shù)據(jù)進行排序并輸出結果。編寫算法時，給出算法的功能說明和一定數(shù)量的注釋。參考答案一

10、、選擇題（每空2 分，共 20 分）1、A；2、C；3、B； 4、D；5、B；6、 C；7、A；8、C；9、B；10、D。二、填空題（每空2 分，共 20 分）1、沒有、沒有；2、線性、任何、棧頂、隊首、隊尾；3、減少一，增加一；4、 5三、算法閱讀理解題（每題10，共 30 分）1、答：輸出為“char”。與答案“ char”中的字符位置對應，并且字符正確，每寫出一個正確的字符計2.5 分。2、答：該算法是二叉樹的先序和中序遍歷合成算法，執(zhí)行后得到先序序列：ABCCEEBADFFDGG與答案“ ABCCEEBADFFDGG”中的字符位置對應，并且字符正確，按寫出的正確字符分別計分，其中前八個

11、字符每寫正確一個計0.5 分，后六個字符每寫正確一個計1 分。3、 1）r0=ri2）while (r0.keynext=NULL;void CreateFromTail(LinkList L)Node *r, *s;char c;intflag =1;r=L;while(flag)/* 設置一個標志，初值為1，當輸入 $ 時， flag 為 0，建表結束 */*r 指針動態(tài)指向鏈表的當前表尾，以便于做尾插入，其初值指向頭結點/* 循環(huán)輸入表中元素值，將建立新結點s 插入表尾 */*/c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data

12、=c;r-next=s;r=s;elseflag=0;r-next=NULL;/* 將最后一個結點的next 鏈域置為空，表示鏈表的結束*/void main()LinkList l;Node *p;init_linklist(&l);printf( 用尾插法建立單鏈表,請輸入鏈表數(shù)據(jù),以 $結束 !n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;單鏈表初始化函數(shù)計 3 分，其中函數(shù)的格式計 1 分，生成鏈表計 1 分，鏈表初始化計 1 分；建立單鏈表函數(shù)計 7 分，其中函數(shù)的格式計 2 分，變

13、量初始化計 1 分，建立鏈表計 4 分；主函數(shù)計 5 分，其中變量初始化計 1 分，調用單鏈表初始化函數(shù)計 1 分，調用建立鏈表函數(shù)計 1 分，輸出單鏈表計 2 分。2、簡單選擇排序程序#include #include typedef int KeyType;typedef int OtherType;typedef structKeyType key;OtherType other_data;RecordType;voidSelectSort(RecordType r, int length)/* 對記錄數(shù)組r 做簡單選擇排序，length 為數(shù)組的長度 */int i,j,k;int n

14、;RecordType x;n=length;for ( i=1 ; i= n-1; +i)k=i;for ( j=i+1 ; j= n ; +j)if (rj.key rk.key )k=j;if ( k!=i)x= ri;ri= rk;rk=x; /* SelectSort*/void main()int i,j;RecordType r20;int len;printf( 請輸入待排序記錄的長度:);scanf(%d,&len);for(i=1;i=len;i+)printf( 請輸入第 %d 個記錄元素 :,i);scanf(%d,&j);ri.key = j;for(i=1;i=len;i+)printf