全國(guó)2003年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題

1、.全國(guó)2003年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題 一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分。在每小題的四個(gè)備選答案中，選出一個(gè)正確答案，并將正確答案的序號(hào)填在題干的括號(hào)內(nèi)) 1.下面程序段的時(shí)間復(fù)雜度是( ) 。 for(i=0;i<n;i+) for(j=1;j<m;j+) Aij=0； A.O(n) B.O(m+n+1) C.O(m+n) D.O(m*n) 2.在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)“刪除x的后繼”的語句是( ) 。 A.p=p->next; B.p->next=p->next->next;C.p->next=p;

2、 D.p=p->next->next; 3.在頭指針為head且表長(zhǎng)大于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若p->next->next= head,則( ) 。 A.p指向頭結(jié)點(diǎn) B.p指向尾結(jié)點(diǎn) C.*p的直接后繼是頭結(jié)點(diǎn) D.*P的直接后繼是尾結(jié)點(diǎn)4.判定“帶頭結(jié)點(diǎn)的鏈隊(duì)列為空”的條件是( ) 。 A.Q.front=NULL B.Q.rear=NULL C.Q.front=Q.rear D.Q.front!=Q.rear5.設(shè)有兩個(gè)串T和P，求P在T中首次出現(xiàn)的位置的串運(yùn)算稱作( ) 。A.聯(lián)接 B.求子串 C.字符定位 D.子串定位6.廣義表A=(a,(

3、b),(),(c,d,e)的長(zhǎng)度為( ) 。A.4 B.5 C.6 D.7 7.一棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為( ) 。A.3 B.4 C.5 D.6 8.已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為( ) 。 A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 9.無向圖中一個(gè)頂點(diǎn)的度是指圖中( ) 。A.通過該頂點(diǎn)的簡(jiǎn)單路徑數(shù) B.與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù) C.通過該頂點(diǎn)的回路數(shù) D.與該頂點(diǎn)連通的頂點(diǎn)數(shù) 10.已知一個(gè)圖如下所示，從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先遍歷可能得到的序列為( ) 。 A.a c e f b d B.a c b d f

4、e C.a c b d e f D.a c d b f e 11.在下列排序方法中，平均時(shí)間性能為O(nlogn)且空間性能最好的是( B )。 A.快速排序 B.堆排序 C.歸并排序 D.基數(shù)排序 12.已知一組關(guān)鍵字為25,48,36,72,79,82,23,40,16,35，其中每相鄰兩個(gè)為有序子序列。對(duì)這些子序列進(jìn)行一趟兩兩歸并的結(jié)果是( ) 。A.25,36,48,72,23,40,79,82,16,35B.25,36,48,72,16,23,40,79,82,35 C.25,36,48,72,16,23,35,40,79,82 D.16,23,25,35,36,40,48,72,7

5、9,82 13.設(shè)順序存儲(chǔ)的線性表共有123個(gè)元素，按分塊查找的要求等分成3塊。若對(duì)索引表采用順序查找來確定塊，并在確定的塊中進(jìn)行順序查找，則在查找概率相等的情況下，分塊查找成功時(shí)的平均查找長(zhǎng)度為( B ) 。A.21 B.23 C.41 D.62 14.索引非順序文件的特點(diǎn)是( ) 。 A.主文件無序，索引表有序 B.主文件有序，索引表無序 C.主文件有序，索引表有序 D.主文件無序，索引表無序 15.倒排文件的主要優(yōu)點(diǎn)是( ) 。A.便于進(jìn)行插入和刪除運(yùn)算 B.便于進(jìn)行文件的恢復(fù) C.便于進(jìn)行多關(guān)鍵字查詢 D.節(jié)省存儲(chǔ)空間 二、填空題(本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1

6、分，共20分) 16.抽象數(shù)據(jù)類型的特點(diǎn)是將_數(shù)據(jù)_和_運(yùn)算_封裝在一起，從而現(xiàn)實(shí)信息隱藏。 17.從順序表中刪除一個(gè)元素時(shí)，表中所有在被刪元素之后的元素均需_前移_一個(gè)位置。 18.在隊(duì)列中，允許進(jìn)行插入操作的一端稱為_隊(duì)尾_，允許進(jìn)行刪除操作的一端稱為_隊(duì)頭_。 19.如圖兩個(gè)棧共享一個(gè)向量空間，top1和top2分別為指向兩個(gè)棧頂元素的指針，則“棧滿” 的判定條件是_top1=top2-1_。 20.設(shè)S1="good",S2=" ",S3="book"，則S1，S2和S3依次聯(lián)接后的結(jié)果是_ good book_。 21.假設(shè)

7、三維數(shù)組A1098按行優(yōu)先順序存儲(chǔ)，若每個(gè)元素占3個(gè)存儲(chǔ)單元，且首地址為100，則元素A987的存儲(chǔ)地址是_2257_。 22.已知在一棵含有n個(gè)結(jié)點(diǎn)的樹中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)，則該樹中含有的葉子結(jié)點(diǎn)的數(shù)目為_（(n-1)/k）*(k-1)+1_或 n - (n-1)/k_。 23.能夠成功完全拓?fù)渑判虻膱D一定是一個(gè)_有向無環(huán)圖_。 24.如果在排序前，關(guān)鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用_堆排序_較為適當(dāng)。 25.假設(shè)哈希表的表長(zhǎng)為m，哈希函數(shù)為H(key)，若用線性探查法解決沖突，則探查地址序列的形式表達(dá)為_hi=(H(key)+I)/m_。

8、三、解答題(本大題共4小題，每小題5分，共20分) 26.假設(shè)通信電文使用的字符集為a,b,c,d,e,f，名字符在電文中出現(xiàn)的頻度分別為：34，5，12，23，8，18，試為這6個(gè)字符設(shè)計(jì)哈夫曼編碼。請(qǐng)先畫出你所構(gòu)造的哈夫曼樹(要求樹中左孩子結(jié)點(diǎn)的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值)，然后分別寫出每個(gè)字符對(duì)應(yīng)的編碼。 27.已知一個(gè)圖如下所示，其頂點(diǎn)按a、b、c、d、e、f順序存放在鄰接表的頂點(diǎn)表中，請(qǐng)畫出該圖的鄰接表，使得按此鄰接表進(jìn)行深度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbefd，進(jìn)行廣度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbdfe。 答案： 28.已知兩個(gè)45的稀疏矩陣的三元組表分別如下： 0 1 4 1

9、6 0 1 1 32 1 2 2 18 1 2 2 22 2 3 4 25 2 2 5 69 3 4 2 28 3 3 4 25 4 4 2 51 請(qǐng)畫出這兩個(gè)稀疏矩陣之和的三元組表。 解: 29.從空樹起，依次插入關(guān)鍵字40，8，90，15，62，95，12，23，56，32，構(gòu)造一棵二叉排序樹。 (1)畫出該二叉排序樹 (2)畫出刪去該樹中元素值為90的結(jié)點(diǎn)之后的二叉排序樹。 四、算法閱讀題(本大題共4小題，每小題5分，共20分) 30.如圖所示，利用同一循環(huán)向量空間實(shí)現(xiàn)兩個(gè)隊(duì)列，其類型Queue2定義如下： typedef struct DataType dataMaxSize; int

10、 front2,length2; Queue2; 對(duì)于i=0或1,fronti和lengthi分別為第i個(gè)隊(duì)列的頭指針和長(zhǎng)度域。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，實(shí)現(xiàn)第i個(gè)循環(huán)隊(duì)列的入隊(duì)操作。 int EnQueue(Queue2*Q,int i,DataType x) /若第i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1，否則返回0if(i<0|i>1)return 0; if( (1) ) return 0; Q->data (2) =x; Q->length (3) +; return 1; 解: (1) (Q->fronti+Q->lengthi%Maxsize=Q

11、->front(i+1)%2 (2) (Q->fronti+->lengthi%Maxsize (3) I 31.某二叉樹的線索鏈表存儲(chǔ)結(jié)構(gòu)如圖(b)所示，其中p為指向根結(jié)點(diǎn)的指針，圖(a)為結(jié)點(diǎn)結(jié)構(gòu)。 閱讀下列算法，并回答問題：(1)寫出執(zhí)行函數(shù)調(diào)用f(p)的輸出結(jié)果； (2)簡(jiǎn)述函數(shù)f的功能。 void f(BinThrTree t) while(t) printf(t->data); if(t->lchild) t=t->lchild; else t=t->rchild; 答案（1）ABDFCEGH (2) 先根遍歷32.下列函數(shù)FindCycl

12、e(G,i)的功能是，對(duì)一個(gè)采用鄰接表作存儲(chǔ)結(jié)構(gòu)的有向圖G，利用深度優(yōu)先搜索策略尋找一條經(jīng)過頂點(diǎn)vi的簡(jiǎn)單回路。數(shù)組cycle_path用于保存搜索過程中形成的回路，cycle_pathk=j(j0)表示在回路中頂點(diǎn)vk的下一個(gè)頂點(diǎn)是vj。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。 vertex firstedge 已知鄰接表的頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為： adjvex next 邊表結(jié)點(diǎn)EdgeNode結(jié)構(gòu)為： int cycle_pathMaxNum; int FindCycle(ALGraph*G,int i) /若回路存在，則返回1，否則返回0 int j; for(j=0;j<G

13、->n;j+)cycle_pathj=-1; return DFSPath(G,i,i); int DFSPath(ALGraph*G,int j,int i) EdgeNode *p; int cycled=0; for(p=G->adjlistj.firstedge;p&!cycled;p=p->next) cycle_pathj=p->adjvex; if( (1 ) )cycled=1;/已找到回路 else if(cycle_pathp->adjvex=-1)cycled= (2) ; return (3) (1) (2) (3) 32題答案： （1）p

14、->adjvex=i (2)DFSpath(G,p->adjvex,i) (3)cycled33.閱讀下列函數(shù)algo,并回答問題。 (1)假設(shè)整型數(shù)組A1.8中的元素依次為(3，8，9，1，7，4，2，6)。執(zhí)行函數(shù)調(diào)用algo(A,8)時(shí)，外層while的循環(huán)體執(zhí)行多少次?函數(shù)的返回值是多少? (2)簡(jiǎn)述函數(shù)algo(L,n)的功能。 int algo(int L,intn) int i=0,j,s=1,t=n; while (i!=(n+1)/2) int x=Ls； i=s;j=t; while(i<j) while(i<j & Lj>=x)j-; Li=

15、Lj; while(i<j & Li<=x)i+; Lj=Li; Li=x; if(i<(n+1)/2)s=i+1; else t=i-1; if(i=0)return 0; else return Li; (1) (2) (3) 33題答案： （1）外循環(huán)執(zhí)行4次，函數(shù)返回值為3。 （2）將A1至A8中不小于A1的元素進(jìn)行遞增排序，如調(diào)用algo(A,8)時(shí)最終排序結(jié)果為2 1 3 4 6 7 8 9 五、算法設(shè)計(jì)題(本大題共10分) 34.假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表作非遞減有序線性表的存儲(chǔ)結(jié)構(gòu)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n)的算法，刪除表中所有數(shù)值相同的多余元素，并釋放結(jié)點(diǎn)空間。