對(duì)外經(jīng)濟(jì)貿(mào)易大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試試卷(B卷)

學(xué)號(hào)___________班級(jí)___________

對(duì)外經(jīng)濟(jì)貿(mào)大學(xué)數(shù)據(jù)結(jié)構(gòu)期考試試卷（）本試卷適用于：信息管理與信息系統(tǒng)專業(yè)姓名___________成績(jī)___________一、填題（每小題,共20分）1性結(jié)構(gòu)中元素之間存在關(guān)系樹形結(jié)構(gòu)中元素之間存在關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系。2．在線性構(gòu)中，第一個(gè)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有個(gè)后續(xù)結(jié)點(diǎn)。3．在具有n單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有個(gè)元素4．帶有一頭結(jié)點(diǎn)的單鏈表head為空的條件是5．在hq鏈隊(duì)列中，判定只有一個(gè)結(jié)點(diǎn)的條件是6于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表在已知所指向結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是7.兩個(gè)串相等的充分必要條件是

且8.設(shè)s='I_AM_A_TEACHER其長(zhǎng)度是9．一棵二樹的第I（）層最多有個(gè)結(jié)點(diǎn)；一棵有n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹共有個(gè)葉子和非終端結(jié)點(diǎn)10在無向圖的鄰接矩陣A中，若A[i][j]等于1，則A[j][i]于11．已知一個(gè)圖的鄰接矩陣表示，刪除所有從第I個(gè)結(jié)點(diǎn)出發(fā)的邊方法是二、選題（每小題,共40分）1．在數(shù)據(jù)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成①。A．動(dòng)態(tài)構(gòu)和靜態(tài)結(jié)構(gòu)B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C．線性結(jié)構(gòu)和非線性結(jié)構(gòu)D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2性表的順序存儲(chǔ)結(jié)構(gòu)是一種①的存儲(chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種②的存儲(chǔ)結(jié)構(gòu)。A．隨機(jī)取B．順序存取C．索引存取D．散列存取3.設(shè)有兩個(gè)串pq求q在p首次出現(xiàn)的位置的運(yùn)算稱作A．連接B模式匹配C求子串D求串長(zhǎng)4．算法分的兩個(gè)主要方面是。A．空間雜性和時(shí)間復(fù)雜性B．正確性和簡(jiǎn)明性C．可讀性和文檔性D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性5．每種結(jié)都具備三個(gè)基本運(yùn)算：插入、刪除和查找，這種說法①A．正確B．不正確6．棧的特是，隊(duì)列的特點(diǎn)是。A．先進(jìn)出．先進(jìn)后出7．判定一循環(huán)隊(duì)列QU（最多元素為）為滿隊(duì)列的條件是。

A．QU.front==（QU.rear+1）%m0B．?。ǎ?m0C．QU.front==D．QU.front！8．不帶頭點(diǎn)的單鏈表head為空的判定條件是A．head=NULLB．->next=NULLC．D．9．在循環(huán)鏈表p所指結(jié)點(diǎn)之后插入s指結(jié)點(diǎn)的操作是A．pright=s;sleft=p;prightleft=s;sright;B．prightleft=s;sC．right=s;prightleft=s;D．right;pleft=s;p10一個(gè)具有個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)在查找成功的情況下，需平均比較_結(jié)點(diǎn)。A．nB．n/2．(n1)/2D．11.二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說法A正確B錯(cuò)誤12.設(shè)高度為的二叉樹上只有度為0和度為的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為A2hB2h-1C2h+1Dh+113.某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問順序是AbdgcefhaBgdbecfhaCbdgaechfDgdbehfca14.樹最適合用來表示A有序數(shù)據(jù)元素B無序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無聯(lián)系的數(shù)據(jù)15.線索二叉樹是一種_結(jié)構(gòu)A邏輯B邏輯和存儲(chǔ)C物理D線性16具有6頂點(diǎn)的無向圖至少應(yīng)有條邊才能確保是一個(gè)連通圖A．5B．6C．7D．817采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的：A．先序歷B．中序遍歷C．后序遍歷D．按層遍歷18判斷一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用：A．求關(guān)路徑的方法C．廣度優(yōu)先遍歷算法三、每題5分20分1．2．3．4．四、寫法（分1．刪除順表中第i個(gè)元素的算法

B．最短路徑的方法D．深度優(yōu)先遍歷算法

&L,i,&e)2．順序棧入棧算法Push(SqStack3．鏈隊(duì)列出隊(duì)列算法QelemType&e)4．已知兩整數(shù)