全國1月高等教育自學考試數(shù)據(jù)結構試題及答案解析

1、全國2018年1月高等教育自學考試數(shù)據(jù)結構試題課程代碼：02331一、單項選擇題(本大題共15小題，每小題2分，共30分。在每小題的四個備選答案中，選出一個正確答案，并將正確答案的序號填在題干的括號內).下面程序段的時間復雜度是()for(i=0;in;i+)for(j=1;jnext;B.p-next=p-next-next;C.p-next=p;D.p=p-next-next;.在頭指針為head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個結點，若p-next-next=headJ()A.p指向頭結點B.p指向尾結點C.*p的直接后繼是頭結點D.*P的直接后繼是尾結點.判定“帶頭結點的鏈

2、隊列為空”的條件是()A.Q.front=NULLB.Q.rear=NULLC.Q.front=Q.rearD.Q.front!=Q.rear.設有兩個串T和P,求P在T中首次出現(xiàn)的位置的串運算稱作()A.聯(lián)接B.求子串C.字符定位D.子串定位.廣義表A=(a,(b),(),(c,d,e)的長度為()A.4B.5C.6D.7.一棵含18個結點的二叉樹的高度至少為()A.3B.4C.5D.6.已知二叉樹的先序序列為ABDECF,中序序列為DBEAFC,則后序序列為()A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA.無向圖中一個頂點的度是指圖中()A.通過該頂點的簡單路徑數(shù)B.與

3、該頂點相鄰接的頂點數(shù)C.通過該頂點的回路數(shù)D.與該頂點連通的頂點數(shù).已知一個圖如下所示，從頂點a出發(fā)進行廣度優(yōu)先遍歷可能得到的序列為()A.acefbdB.acbdfeC.acbdefD.acdbfe題10圖.在下列排序方法中，平均時間性能為O（nlogn）且空間性能最好的是（）A.快速排序B.堆排序C.歸并排序D.基數(shù)排序.已知一組關鍵字為25,48,36,72,79,82,23,40,16,35,其中每相鄰兩個為有序子序列。對這些子序列進行一趟兩兩歸并的結果是（）A.25,36,48,72,23,40,79,82,16,35B.25,36,48,72,16,23,40,79,82,35C.

4、25,36,48,72,16,23,35,40,79,82D.16,23,25,35,36,40,48,72,79,82.設順序存儲的線性表共有123個元素，按分塊查找的要求等分成3塊。若對索引表采用順序查找來確定塊，并在確定的塊中進行順序查找，則在查找概率相等的情況下，分塊查找成功時的平均查找長度為（）D.62）B.主文件有序，索引表無序D.主文件無序，索引表無序）B.便于進行文件的恢復D.節(jié)省存儲空間A.21B.23C.41.索引非順序文件的特點是（A.主文件無序，索引表有序C.主文件有序，索引表有序.倒排文件的主要優(yōu)點是（A.便于進行插入和刪除運算C.便于進行多關鍵字查詢、填空題（本大題

5、共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）.抽象數(shù)據(jù)類型的特點是將和封裝在一起，從而現(xiàn)實信息隱藏。.從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需一個位置。.在隊列中，允許進行插入操作的一端稱為,允許進行刪除操作的一端稱為.如圖兩個棧共享一個向量空間，top1和top分別為指向兩個棧頂元素的指針，則“棧滿”的判定條件是。題19圖.設S1=good,S2=,S3=book,貝US1,S2和S3依次聯(lián)接后的結果是。.假設三維數(shù)組A1098按行優(yōu)先順序存儲，若每個元素占3個存儲單元，且首地址為100,則元素A987的存儲地址是。.已知在一棵含有n個結點的樹中，只有度為

6、k的分支結點和度為0的葉子結點，則該樹中含有的葉子結點的數(shù)目為。.能夠成功完全拓撲排序的圖一定是一個。.如果在排序前，關鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用較為適當。.假設哈希表的表長為m,哈希函數(shù)為H（key）,若用線性探查法解決沖突，則探查地址序列的形式表達為O三、解答題（本大題共4小題，每小題5分，共20分）.假設通信電文使用的字符集為a,b,c,d,e,f,名字符在電文中出現(xiàn)的頻度分別為：34,5,12,23,8,18,試為這6個字符設計哈夫曼編碼。請先畫出你所構造的哈夫曼樹(要求樹中左孩子結點的權值小于右孩子結點的權值)，然后分別寫出每個字符對應的編碼。.已知

7、一個圖如下所示，其頂點按a、b、c、d、e、f順序存放在鄰接表的頂點表中，請畫出該圖的鄰接表，使得按此鄰接表進行深度優(yōu)先遍歷時得到的頂點序列為acbefd,進行廣度優(yōu)先遍歷時得到的頂點序列為acbdfe。.已知兩個4X5的稀疏矩陣的三元組表分別如下:01132122-2222569334254425129.從空樹起，依次插入關鍵字 序樹。題30圖請畫出這兩個稀疏矩陣之和的三元組表。40,8,90,15,62,95,12,23,56,32,構造一棵二叉排(1)畫出該二叉排序樹(2)畫出刪去該樹中元素值為90的結點之后的二叉排序樹。四、算法閱讀題(本大題共4小題，每小題5分，共20分)Queue2

8、定義如下:30.如圖所示，利用同一循環(huán)向量空間實現(xiàn)兩個隊列，其類型typedefstructDataTypedataMaxSize;intfront2,length2;Queue2;對于i=0或1,fronti和lengthi分別為第i個隊列的頭指針和長度域。請在空缺處填入合適的內容，實現(xiàn)第i個循環(huán)隊列的入隊操作。intEnQueue(Queue2*Q,inti,DataTypex)若第i個隊列不滿，則元素x入隊列，并返回1,否則返回0if(i1)return0;if(1一)return0;Q-data=x;Q-length(3)+;return1;(2)31.某二叉樹的線索鏈表存儲結構如圖(

9、b)所示，其中p為指向根結點的指針，圖(a)為結點結構。閱讀下列算法，并回答問題：(1)寫出執(zhí)行函數(shù)調用f(p)的輸出結果;(2)簡述函數(shù)f的功能。voidf(BinThrTreet)題露圖while(t)printf(t-data);if(t-lchild)t=t-lchild;elset=t-rchild;(2)32.下列函數(shù)FindCycle(G,i)的功能是，對一個采用鄰接表作存儲結構的有向圖G,利用深度優(yōu)先搜索策略尋找一條經(jīng)過頂點Vi的簡單回路。數(shù)組cycle_path用于保存搜索過程中形成的回路，cycle_pathk=j(j0)表示在回路中頂點Vk的下一個頂點是vj。請在空缺處填

10、入合適的內容，使其成為一個完整的算法。vertexfirstedgeadjvexnext已知鄰接表的頂點表結點結構為:邊表結點EdgeNode結構為：intcycle_pathMaxNum;intFindCycle(ALGraph*G,inti)若回路存在，則返回1,否則返回0intj;for(j=0;jn;j+)cycle_pathj=-1;returnDFSPath(G,i,i);intDFSPath(ALGraph*G,intj,inti)EdgeNode*p;intcycled=0;for(p=G-adjlistj.firstedge;p&!cycled;p=p-next)cycle_

11、pathj=p-adjvex;if(1)cycled=1;/已找到回路elseif(cycle_pathp-adjvex=-1)cycled=(2);return(3)(2)33.閱讀下列函數(shù)algo,并回答問題。(1)假設整型數(shù)組A1.8中的元素依次為(3,8,9,1,7,4,2,6)。執(zhí)行函數(shù)調用algo(A,8)時，外層while的循環(huán)體執(zhí)行多少次？函數(shù)的返回值是多少？(2)簡述函數(shù)algo(L,n)的功能。intalgo(intL,intn)inti=0,j,s=1,t=n;while(i!=(n+1)/2)intx=Ls;i=s;j=t;while(ij)while(i=x)j-;Li=Lj;while(ij&Li=x)i+;Lj=Li;Li=x;if(i(n+1)/2)s=i+1;elset=i-1;if(i=0