02331數(shù)據(jù)結(jié)構(gòu)2003年01月試卷

02331數(shù)據(jù)結(jié)構(gòu)試題第6頁共6頁全國2003年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331一、單項選擇題(本大題共15小題，每小題2分，共30分。在每小題的四個備選答案中，選出一個正確答案，并將正確答案的序號填在題干的括號內(nèi))1.下面程序段的時間復(fù)雜度是()for(i=0;i<n;i++)for(j=1;j<m;j++)A[i][j]=0；A.O(n)B.O(m+n+1)C.O(m+n)D.O(m*n)2.在單鏈表中，指針p指向元素為x的結(jié)點，實現(xiàn)“刪除x的后繼”的語句是()A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;3.在頭指針為head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個結(jié)點，若p->next->next=

head,則()A.p指向頭結(jié)點B.p指向尾結(jié)點C.*p的直接后繼是頭結(jié)點D.*P的直接后繼是尾結(jié)點4.判定“帶頭結(jié)點的鏈隊列為空”的條件是()A.Q.front==NULLB.Q.rear==NULLC.Q.front==Q.rearD.Q.front!=Q.rear5.設(shè)有兩個串T和P，求P在T中首次出現(xiàn)的位置的串運算稱作()A.聯(lián)接B.求子串C.字符定位D.子串定位6.廣義表A=(a,(b),(),(c,d,e))的長度為()A.4B.5C.6D.77.一棵含18個結(jié)點的二叉樹的高度至少為()A.3B.4C.5D.68.已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為()A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA9.無向圖中一個頂點的度是指圖中()A.通過該頂點的簡單路徑數(shù)B.與該頂點相鄰接的頂點數(shù)C.通過該頂點的回路數(shù)D.與該頂點連通的頂點數(shù)10.已知一個圖如下所示，從頂點a出發(fā)進(jìn)行廣度優(yōu)先遍歷可能得到的序列為()A.acefbdB.acbdfeC.acbdefD.acdbfe11.在下列排序方法中，平均時間性能為O(nlogn)且空間性能最好的是()A.快速排序B.堆排序C.歸并排序D.基數(shù)排序12.已知一組關(guān)鍵字為{25,48,36,72,79,82,23,40,16,35}，其中每相鄰兩個為有序子序列。對這些子序列進(jìn)行一趟兩兩歸并的結(jié)果是()A.{25,36,48,72,23,40,79,82,16,35}B.{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,79,82}13.設(shè)順序存儲的線性表共有123個元素，按分塊查找的要求等分成3塊。若對索引表采用順序查找來確定塊，并在確定的塊中進(jìn)行順序查找，則在查找概率相等的情況下，分塊查找成功時的平均查找長度為()A.21B.23C.41D.6214.索引非順序文件的特點是()A.主文件無序，索引表有序B.主文件有序，索引表無序C.主文件有序，索引表有序D.主文件無序，索引表無序15.倒排文件的主要優(yōu)點是()A.便于進(jìn)行插入和刪除運算B.便于進(jìn)行文件的恢復(fù)C.便于進(jìn)行多關(guān)鍵字查詢D.節(jié)省存儲空間二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)16.抽象數(shù)據(jù)類型的特點是將____________和____________封裝在一起，從而現(xiàn)實信息隱藏。17.從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需____________一個位置。18.在隊列中，允許進(jìn)行插入操作的一端稱為____________，允許進(jìn)行刪除操作的一端稱為____________。19.如圖兩個棧共享一個向量空間，top1和top分別為指向兩個棧頂元素的指針，則“棧滿”的判定條件是____________。20.設(shè)S1="good",S2="",S3="book"，則S1，S2和S3依次聯(lián)接后的結(jié)果是____________。21.假設(shè)三維數(shù)組A[10][9][8]按行優(yōu)先順序存儲，若每個元素占3個存儲單元，且首地址為100，則元素A[9][8][7]的存儲地址是____________。22.已知在一棵含有n個結(jié)點的樹中，只有度為k的分支結(jié)點和度為0的葉子結(jié)點，則該樹中含有的葉子結(jié)點的數(shù)目為____________。23.能夠成功完全拓?fù)渑判虻膱D一定是一個____________。24.如果在排序前，關(guān)鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用____________較為適當(dāng)。25.假設(shè)哈希表的表長為m，哈希函數(shù)為H(key)，若用線性探查法解決沖突，則探查地址序列的形式表達(dá)為____________。三、解答題(本大題共4小題，每小題5分，共20分)26.假設(shè)通信電文使用的字符集為{a,b,c,d,e,f}，名字符在電文中出現(xiàn)的頻度分別為：34，5，12，23，8，18，試為這6個字符設(shè)計哈夫曼編碼。請先畫出你所構(gòu)造的哈夫曼樹(要求樹中左孩子結(jié)點的權(quán)值小于右孩子結(jié)點的權(quán)值)，然后分別寫出每個字符對應(yīng)的編碼。27.已知一個圖如下所示，其頂點按a、b、c、d、e、f順序存放在鄰接表的頂點表中，請畫出該圖的鄰接表，使得按此鄰接表進(jìn)行深度優(yōu)先遍歷時得到的頂點序列為acbefd，進(jìn)行廣度優(yōu)先遍歷時得到的頂點序列為acbdfe。28.已知兩個4×5的稀疏矩陣的三元組表分別如下：014160113212218122－22234－2522569342283342544251請畫出這兩個稀疏矩陣之和的三元組表。29.從空樹起，依次插入關(guān)鍵字40，8，90，15，62，95，12，23，56，32，構(gòu)造一棵二叉排序樹。(1)畫出該二叉排序樹(2)畫出刪去該樹中元素值為90的結(jié)點之后的二叉排序樹。四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.如圖所示，利用同一循環(huán)向量空間實現(xiàn)兩個隊列，其類型Queue2定義如下：typedefstruct{DataTypedata[MaxSize];intfront[2],length[2];}Queue2;對于i=0或1,front[i]和length[i]分別為第i個隊列的頭指針和長度域。請在空缺處填入合適的內(nèi)容，實現(xiàn)第i個循環(huán)隊列的入隊操作。intEnQueue(Queue2*Q,inti,DataTypex){//若第i個隊列不滿，則元素x入隊列，并返回1，否則返回0if(i<0||i>1)return0;if((1))return0;Q->data[(2)]=x;Q->length[(3)]++;return1;}(1)(2)(3)31.某二叉樹的線索鏈表存儲結(jié)構(gòu)如圖(b)所示，其中p為指向根結(jié)點的指針，圖(a)為結(jié)點結(jié)構(gòu)。閱讀下列算法，并回答問題：(1)寫出執(zhí)行函數(shù)調(diào)用f(p)的輸出結(jié)果；(2)簡述函數(shù)f的功能。voidf(BinThrTreet){while(t){printf(t->data);if(t->lchild)t=t->lchild;elset=t->rchild;}}(1)(2)32.下列函數(shù)FindCycle(G,i)的功能是，對一個采用鄰接表作存儲結(jié)構(gòu)的有向圖G，利用深度優(yōu)先搜索策略尋找一條經(jīng)過頂點vi的簡單回路。數(shù)組cycle_path用于保存搜索過程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中頂點vk的下一個頂點是vj。請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。vertexfirstedge已知鄰接表的頂點表結(jié)點結(jié)構(gòu)為：adjvexnext邊表結(jié)點EdgeNode結(jié)構(gòu)為：intcycle_path[MaxNum];intFindCycle(ALGraph*G,inti){//若回路存在，則返回1，否則返回0intj;for(j=0;j<G->n;j++)cycle_path[j]=-1;returnDFSPath(G,i,i);}intDFSPath(ALGraph*G,intj,inti){EdgeNode*p;intcycled=0;for(p=G->adjlist[j].firstedge;p&&!cycled;p=p->next){cycle_path[j]=p->adjvex;if((1))cycled=1;//已找到回路elseif(cycle_path[p->adjvex]==-1)cycled=(2);}return(3)}(1)(2)(3)33.閱讀下列函數(shù)algo,并回答問題。(1)假設(shè)整型數(shù)組A[1..8]中的元素依次為(3，8，9，1，7，4，2，6)。執(zhí)行函數(shù)調(diào)用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=L[s]；i=s;j=t;while(i<j){while(i<j&&L[j]>=x)j--;L[i]=L[j];while(i<j&&L[i]<=x)i++;L[j]=L[i];}L[i]=x;if(i<(n+