全國2013年10月高等教育自學考試數據結構試題

　　一單項選擇題 ( 本大題共 小題每小題 分共 分 )

　　在每小題列出的四個備選項中只有一個是符合題目要求的請將其代碼填寫在題干的括號內錯選多選或未選均無分

　　 下列各式中按增長率由小至大的順序正確排列的是 ( )

　　A n ! n n / B n / n n logn

　　C n log n n logn n / D logn n n n

　　 若要在單鏈表中的結點 *p 之後插入一個結點 *s 則應執行的語句是 ( )

　　A s>next=p>next; p>next=s; B p>next=s; s>next=p>next;

　　C p>next=s>next; s>next=p; D s>next=p; p>next=s>next;

　　 若要在 O ( )的時間復雜度上實現兩個循環鏈表頭尾相接則應對兩個循環鏈表各設置一個指針分別指向 ( )

　　A 各自的頭結點

　　B 各自的尾結點

　　C 各自的第一個元素結點

　　D 一個表的頭結點另一個表的尾結點

　　 棧的兩種常用存儲結構分別為 ( )

　　A 順序存儲結構和鏈式存儲結構 B 順序存儲結構和散列存儲結構

　　C 鏈式存儲結構和索引存儲結構 D 鏈式存儲結構和散列存儲結構

　　 已知循環隊列的存儲空間為數組 data[] 且當前隊列的頭指針和尾指針的值分別為 和 則該隊列的當前長度為 ( )

　　A B

　　C D

　　 已知在如下定義的鏈串結點中每個字符占 個字節指針占 個字節則該鏈串的存儲密度為

　　typedef struct node {

　　char data[];

　　struct node *next;

　　} LinkStrNode;

　　A / B /

　　C / D /

　　 應用簡單的匹配算法對主串 s= ″ BDBABDABDAB ″與子串 t= ″ BDA ″進行模式匹配在匹配成功時進行的字符比較總次數為 ( )

　　A B

　　C D

　　 二維數組 A[][] 采用列優先的存儲方法若每個元素占 個存儲單元且第 個元素的首地址為 則元素 A[][] 的存儲地址為 ( )

　　A B

　　C D

　　 對廣義表 L=((ab)cd) 進行操作 tail(head(L)) 的結果是 ( )

　　A ( cd ) B (d)

　　C b D (b)

　　 已知一棵樹的前序序列為 ABCDEF 後序序列為 CEDFBA 則對該樹進行層次遍歷得到的序列為 ( )

　　A ABCDEF B ABCEFD

　　C ABFCDE D ABCDFE

　　 一個含 n 個頂點和 e 條弧的有向圖以鄰接矩陣表示法為存儲結構則計算該有向圖中某個頂點出度的時間復雜度為 ( )

　　A O(n) B O(e)

　　C O(n+e) D O(n )

　　 在關鍵字序列 ( ) 中二分查找關鍵字為 和 的結點時所需進行的比較次數分別為 ( )

　　A B

　　C D

　　 下列排序方法中最好與最壞時間復雜度不相同的排序方法是 ( )

　　A 冒泡排序 B 直接選擇排序

　　C 堆排序 D 歸並排序

　　 已知含 個結點的二叉排序樹是一棵完全二叉樹則該二叉排序樹在等概率情況下查找成功的平均查找長度等於 ( )

　　A B

　　C D

　　 在下列各種文件中不能進行順序查找的文件是 ( )

　　A 順序文件 B 索引文件

　　C 散列文件 D 多重表文件

　　二填空題 ( 本大題共 小題每小題 分共 分 )

　　 抽象數據類型是指數據邏輯結構及與之相關的 ___________

　　 已知在結點個數大於 的單循環鏈表中指針 p 指向表中某個結點則下列程序段執行結束時指針 q 指向結點 *p 的 ___________ 結點

　　q=p;

　　while(q>next!=p)q=q>next;

　　 假設 S 和 X 分別表示進棧和出棧操作由輸入序列 ABC 得到輸出序列 BCA 的操作序列為 SSXSXX 則由 a*b+c/d 得到 ab*cd/+ 的操作序列為 ___________

　　 在文本編輯程序中查找某一特定單詞在文本中出現的位置可以利用串的 ___________ 運算

　　 假設以行優先順序將一個 n 階的 對角矩陣壓縮存儲到一維數組 Q 中則數組 Q 的大小至少為 ___________

　　 在含 個結點的完全二叉樹中葉子結點的個數為 ___________

　　 在無向圖中若從頂點 a 到頂點 b 存在 ___________ 則稱 a 與 b 之間是連通的

　　 如果排序過程不改變 ___________ 之間的相對次序則稱該排序方法是穩定的

　　 索引順序查找適宜對 ___________ 的順序表進行查找

　　 文件的檢索操作可按檢索條件不同分為下列四種詢問它們是簡單詢問范圍詢問函數詢問及 ___________

　　三解答題 ( 本大題共 小題每小題 分共 分 )

　　 畫出下圖所示二叉樹的中序線索鏈表的存儲表示

　　

　　 已知圖 G= ( V E )其中

　　V={abcde}

　　E={(ab)(bd)(cb)(cd)(de)(ea)(ec)}

　　( )畫出圖 G ;

　　( )畫出圖 G 的鄰接表

　　( )

　　( )

　　 已知自頂向下的二路歸並排序的算法如下所示按此算法對關鍵字序列( )進行排序列出算法執行過程中前 次調用 Merge 函數進行歸並之後的關鍵字序列

　　void MergeSorDC(SeqList R int low int high)

　　{// 用分治法對 R[lowhigh] 進行二路歸並排序 }

　　int mid;

　　if (low

　　mid=(low+high)/2; // 分解

　　MergeSortDC(R, low, mid); // 遞歸地對 R[low..mid] 排序

　　MergeSortDC(R,mid+1,high); // 遞歸地對 R[mid+1..high] 排序

　　Merge(R, low, mid, high); // 組合，將兩個有序區歸並為一個有序區

　　}

　　} //MergeSortDC

　　29 .由於元素的插入先後次序不同，所構成的二叉排序樹可能有多種形態。tW.wingwit.cOM請畫出 4 棵含 1 ， 2 ， 3 ， 4 ， 5 ， 6 六個元素且以 1 為根、深度為 4 的二叉排序樹。

　　四、算法閱讀題 ( 本大題共 4 小題，每小題 5 分，共 20 分 )

　　30 . L 為一個帶頭結點的循環鏈表。函數 f30 的功能是刪除 L 中數據域 data 的值大於 c 的所有結點，並由這些結點組建成一個新的帶頭結點的循環鏈表，其頭指針作為函數的返回值。請在空缺處填入合適的內容，使其成為一個完整的算法。

　　LinkList f30(LinkList L, int c)

　　{

　　LinkList Lc,p,pre;

　　pre=L;

　　p= (1) ;

　　Lc=(LinkList) malloc(sizeof(ListNode));

　　Lc->next=Lc;

　　while(p!=L)

　　if(p->data>c)

　　{

　　pre->next=p->next;

　　(2) ;

　　Lc->next=p;

　　p=pre->next;

　　}

　　else

　　{

　　pre=p;

　　(3) ;

　　}

　　return Lc;

　　}

　　(1)

　　(2)

　　(3)

　　31 . 設棧 S=(1,2,3,4,5,6,7), 其中 7 為棧頂元素。

　　( 1 )寫出調用 f31(&S) 後的 S ;

　　( 2 )簡述函數 f31 中第 1 個循環語句的功能。

　　void f31 (Stack *S)

　　{

　　Queue Q;

　　Stack T;

　　int i=0;

　　InitQueue(&Q);

　　InitStack(&T);

　　while(!StackEmpty(S))

　　if ((i=!t)!=0) Push(&T,Pop(S));

　　else EnQueue(&Q, Pop(S));

　　while(!StackEmpty(&T))

　　Push(S,PoP(&T));

　　while(!QieueEmpty(&Q))

　　Push(S,DeQueue(&Q));

　　}

　　(1)

　　(2)

　　32 .圖的鄰接矩陣表示描述如下：

　　#define MaxNum 20 // 圖的最大頂點數

　　typedef struct {

　　char vexs[MaxNum]; // 字符類型的頂點表

　　int edges[MaxNum][MaxNum]; // 鄰接矩陣

　　int n, e; // 圖的頂點數和邊數

　　} MGraph; // 圖的鄰接矩陣結構描述

　　閱讀下列算法，並回答問題：

　　( 1 )對於下列圖 G 的鄰接矩陣，寫出函數調用 f32(&G,3) 的返回值;

　　

　　( 2 )簡述函數 f32 的功能;

　　( 3 )寫出函數 f32 的時間復雜度。

　　int f32(MGraph *G, int i)

　　{

　　int d=0,j;

　　for(j=0;jn;j++)

　　{

　　if (G->edges[i][j]) d++;

From:http://tw.wingwit.com/Article/program/sjjg/201311/23381.html