2002年下半年全國(guó)高等教育自學(xué)考試

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論

（課程代號(hào)：2142）

一、單項(xiàng)選擇題（在下列每小題四個(gè)備選答案中選出一個(gè)正確答案，并將其字母標(biāo)號(hào)填入題干的括號(hào)內(nèi)。每小題2分，共30分）

1.下列數(shù)據(jù)組織形式中，( )的結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一個(gè)"鎖鏈"。
A.集合     B.樹形結(jié)構(gòu)     C.線性結(jié)構(gòu)     D.圖狀結(jié)構(gòu)

2.數(shù)據(jù)結(jié)構(gòu)可以形式化地定義為(S，△)，其中S指某種邏輯結(jié)構(gòu)，△是指( )
A. S上的算法     B. S的存儲(chǔ)結(jié)構(gòu)
C. 在S上的一個(gè)基本運(yùn)算集     D. 在S上的所有數(shù)據(jù)元素

3.下列說(shuō)法正確的是( )
A.線性表的邏輯順序與存儲(chǔ)順序總是一致的
B.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，要求內(nèi)存中可用的存儲(chǔ)單元可以是連續(xù)的，也可以不連續(xù)
C.線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
D.每種數(shù)據(jù)結(jié)構(gòu)都具有插入、刪除和查找三種基本運(yùn)算

4.設(shè)非空單鏈表的數(shù)據(jù)域?yàn)閐ata，指針域?yàn)閚ext，指針p指向單鏈表中第i個(gè)結(jié)點(diǎn)，s指向已生成的新結(jié)點(diǎn)，現(xiàn)將s結(jié)點(diǎn)插入到單鏈表中，使其成為第i個(gè)結(jié)點(diǎn)，下列算法段能正確完成上述要求的是( )
A. s－＞next=p－＞next; p－＞next=s;
B. p－＞next=s; s－＞next=p－＞next;
C. s－＞next=p－＞next; p－＞next=s; 交換p－＞data和s－＞data;
D. p=s; s－＞next=p;

5.稀疏矩陣一般采用( )方法壓縮存儲(chǔ)。
A.三維數(shù)組     B.單鏈表     C.三元組表     D.散列表

6.樹若用雙親鏈表表示，則( )
A.可容易地實(shí)現(xiàn)求雙親及子孫的運(yùn)算
B.求雙親及子孫的運(yùn)算均較困難
C.可容易地實(shí)現(xiàn)求雙親運(yùn)算，但求子孫運(yùn)算較困難
D.可容易地實(shí)現(xiàn)求子孫運(yùn)算，但求雙親運(yùn)算較困難

7.將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，則對(duì)編號(hào)為25的結(jié)點(diǎn)x，該結(jié)點(diǎn)( )
A.無(wú)左、右孩子     B.有左孩子，無(wú)右孩子
C.有右孩子，無(wú)左孩子     D.有左、右孩子

8.用鄰接表作為有向圖G的存儲(chǔ)結(jié)構(gòu)。設(shè)有n個(gè)頂點(diǎn)、e條弧，則拓?fù)渑判虻臅r(shí)間復(fù)雜度為( )
A. O(n)     B. O(n+e)     C. O(e)     D. O(n*e)

9.如果從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問(wèn)所有頂點(diǎn)，則該圖一定是( )
A.完全圖     B.連通圖     C.有回路     D.一棵樹

10.采用線性探測(cè)法解決沖突問(wèn)題，所產(chǎn)生的一系列后繼散列地址( )
A.必須大于等于原散列地址
B.必須小于等于原散列地址
C.可以大于或小于但不能等于原散列地址
D.地址大小沒(méi)有具體限制

11.在對(duì)查找表的查找過(guò)程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。這種方式主要適合于( )
A.靜態(tài)查找表     B.動(dòng)態(tài)查找表
C.靜態(tài)查找表與動(dòng)態(tài)查找表     D.兩種表都不適合

12.由索引集、順序集和數(shù)據(jù)集三部分組成的文件稱為( )
A. VSAM文件     B.散列文件     C.順序文件     D.索引文件

13.下列有關(guān)散列文件的說(shuō)法中不正確的是( )
A.散列文件具有隨機(jī)存放的優(yōu)點(diǎn)
B.散列文件只能按關(guān)鍵字存取
C.散列文件需要索引區(qū)
D.散列文件的記錄不需要進(jìn)行排序

14.一組記錄的鍵值為(12，38，35，25，74，50，63，90)，按2路歸并排序方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為( )
A. 12，38，25，35，50，74，63，90    B. 12，38，35，25，74，50，63，90
C. 12，25，35，38，50，74，63，90    D. 12，35，38，25，63，50，74，90

15.用快速排序方法對(duì)包含有n個(gè)關(guān)鍵的序列進(jìn)行排序，最壞情況下執(zhí)行的時(shí)間雜度為( )
A. O(n) B. O(log₂n)     C. O(nlog₂n)     D. O(n²)

二、填空題(每空2分，共26分)

1.定義在線性表上的初始化、查找、插入和刪除運(yùn)算中，          是引用型運(yùn)算。

2.線性表(a₀,a₁,a₂,…,a_n) (n≥1)中，每個(gè)元素占c個(gè)存儲(chǔ)單元，m為a₀的首地址，則按順序存儲(chǔ)方式存儲(chǔ)線性表，a_n的存儲(chǔ)地址是          。

3.在棧的順序?qū)崿F(xiàn)中，設(shè)棧頂指針為top，棧空的條件為          。

4.隊(duì)列中允許進(jìn)行插入的一端稱為          。

5.深度為90的滿二叉樹上，第11層有          個(gè)結(jié)點(diǎn)。

6.給定n個(gè)值構(gòu)造哈夫曼樹。根據(jù)哈夫曼算法，初始森林中共有n棵二叉樹，經(jīng)過(guò)          次合并后才能使森林中的二叉樹的數(shù)目由n棵減少到只剩下一棵最終的哈夫曼樹。

7.設(shè)無(wú)向圖G的頂點(diǎn)數(shù)為n，則G最少有          條邊。

8.通常采用拉鏈法、線性探測(cè)法、多重散列法、二次探測(cè)法、公共溢出區(qū)法等解決散列地址沖突問(wèn)題，若要避免"堆積"現(xiàn)象發(fā)生應(yīng)采用          法。

9.對(duì)有序表(25，30，32，38，47，54，62，68，90，95)用二分查找法查找32，則所需的比較次數(shù)為          。

10.樹型結(jié)構(gòu)結(jié)點(diǎn)間通過(guò)"父子"關(guān)系相互關(guān)聯(lián)，這種相互關(guān)聯(lián)構(gòu)成了數(shù)據(jù)間的          關(guān)系。

11.文件的檢索有順序存取、直接存取和          三種方式。

12.第i趟在n-i+l (i=1，2，…，n-l)個(gè)記錄中選取鍵值最小的記錄作為有序序列的第i個(gè)記錄。這樣的排序方法稱為          。

13.在堆排序和快速排序中，若原始記錄已基本有序，則較適合選用          。

三、應(yīng)用題（共30分）

1.設(shè)有字符串為 3 * - y - a / y ∧ 2 ，試?yán)脳懗鰧⑵滢D(zhuǎn)換為 3 y - * a y 2 ∧ / - 的操作步驟。假定用 X 代表掃描該字符串過(guò)程中順序取一個(gè)字符進(jìn)棧的操作，用 S 代表從棧中取出一個(gè)字符加入到新字符串尾的出棧操作。例如，ABC 變?yōu)?BCA 的操作步驟為 XXSXSS 。（5分）

2.現(xiàn)有某二叉樹，按先根遍歷的序列為ABDEFCGH，按中根遍歷的序列為DEFBGHCA，試畫出此二叉樹。(6分)

3.給定表（19，22，18，15，30，20，42，35，16），按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉排序樹。（6分）

4.已知序列（70，83，100，65，10，32，7，9），請(qǐng)給出采用直接插入排序法對(duì)該序列作升序排序時(shí)的每一趟的結(jié)果。（7分）

5.已知無(wú)向圖G的鄰接表如下，請(qǐng)畫出其所有的連通分量。（6分）

四、設(shè)計(jì)題（共14分）

1.設(shè)字符串僅由圓括號(hào)“（”和“）”，方括號(hào)“[”和“]”，花括號(hào)“{”和“}”組成，利用鏈棧的操作編寫一個(gè)檢查括號(hào)是否正確配對(duì)的算法：int Matcher(LStackTP *ls)。例如，[{{（）}[]}（）{[]}]是正確的，而{（{（）[]}）}]）}則不正確。設(shè)鏈棧定義如下：（6分）

typedef struct node
{   char data;
    struct node *next;
} LStackTp;

2.利用一維數(shù)組a可以對(duì)n個(gè)整數(shù)進(jìn)行排序，其中一種排序算法的處理思想是：將n個(gè)整數(shù)分別作為數(shù)組a的n個(gè)元素值，每次（即第i次）從元素a[i]到a[n]中挑出最小的一個(gè)元素a[k](i≤k≤n)，然后將a[k]與a[i]換位。這樣反復(fù)n-1次完成排序。編寫實(shí)現(xiàn)上述算法的函數(shù)：void sort(int a[],int n)。（8分）