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(log2n) C. O(nlog2n) D. O(n2)
二、填空題(每空2分,共26分)
1.定義在線性表上的初始化、查找、插入和刪除運(yùn)算中, 是引用型運(yùn)算。
2.線性表(a0,a1,a2,…,an) (n≥1)中,每個(gè)元素占c個(gè)存儲(chǔ)單元,m為a0的首地址,則按順序存儲(chǔ)方式存儲(chǔ)線性表,an的存儲(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分)