一
for(i= for(j=1;j A[i][j]=0; A.O(n) B.O(m+n+1) C.O(m+n) D.O(m*n) 2.在單鏈表中，指針p指向元素為x的結點，實現“刪除x的後繼”的語句是( ) A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 3.在頭指針為head且表長大於1的單循環鏈表中，指針p指向表中某個結點，若p->next->next= head,則( ) A.p指向頭結點 B.p指向尾結點 C.*p的直接後繼是頭結點 D.*P的直接後繼是尾結點 4.判定“帶頭結點的鏈隊列為空”的條件是( ) A.Q.front==NULL B.Q.rear==NULL C.Q.front==Q.rear D.Q.front!=Q.rear 5.設有兩個串T和P，求P在T中首次出現的位置的串運算稱作( ) A.聯接 B.求子串 C.字符定位 D.子串定位 6.廣義表A=(a,(b),(),(c,d,e))的長度為( ) A.4 B.5 C.6 D.7 7.一棵含18個結點的二叉樹的高度至少為( ) A.3 B.4 C.5 D.6 8.已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則後序序列為( ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 9.無向圖中一個頂點的度是指圖中( ) A.通過該頂點的簡單路徑數 B.與該頂點相鄰接的頂點數 C.通過該頂點的回路數 D.與該頂點連通的頂點數 10.已知一個圖如下所示，從頂點a出發進行廣度優先遍歷可能得到的序列為( ) A.a c e f b d B.a c b d f e C.a c b d e f D.a c d b f e 11.在下列排序方法中，平均時間性能為O(nlogn)且空間性能最好的是( ) A.快速排序 B.堆排序 C.歸並排序 D.基數排序 12.已知一組關鍵字為{25,48,36,72,79,82,23,40,16,35}，其中每相鄰兩個為有序子序列。tW.wiNGWIt.cOM對這些子序列進行一趟兩兩歸並的結果是( ) 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.設順序存儲的線性表共有123個元素，按分塊查找的要求等分成3塊。若對索引表采用順序查找來確定塊，並在確定的塊中進行順序查找，則在查找概率相等的情況下，分塊查找成功時的平均查找長度為( ) A.21 B.23 C.41 D.62 14.索引非順序文件的特點是( ) A.主文件無序，索引表有序 B.主文件有序，索引表無序 C.主文件有序，索引表有序 D.主文件無序，索引表無序 15.倒排文件的主要優點是( ) A.便於進行插入和刪除運算 B.便於進行文件的恢復 C.便於進行多關鍵字查詢 D.節省存儲空間 二、填空題 (本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分) 16.抽象數據類型的特點是將____________和____________封裝在一起，從而現實信息隱藏。 17.從順序表中刪除一個元素時，表中所有在被刪元素之後的元素均需____________一個位置。 18.在隊列中，允許進行插入操作的一端稱為____________，允許進行刪除操作的一端稱為____________。 19.如圖兩個棧共享一個向量空間，top1和top分別為指向兩個棧頂元素的指針，則“棧滿”的判定條件是____________。
20.設S1="good",S2=" ",S3="book"，則S1，S2和S3依次聯接後的結果是____________。 21.假設三維數組A[10][9][8]按行優先順序存儲，若每個元素占3個存儲單元，且首地址為100，則元素A[9][8][7]的存儲地址是____________。 22.已知在一棵含有n個結點的樹中，只有度為k的分支結點和度為0的葉子結點，則該樹中含有的葉子結點的數目為____________。 23.能夠成功完全拓撲排序的圖一定是一個____________。 24.如果在排序前，關鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用____________較為適當。 25.假設哈希表的表長為m，哈希函數為H(key)，若用線性探查法解決沖突，則探查地址序列的形式表達為____________。 三、解答題 (本大題共4小題，每小題5分，共20分) 26.假設通信電文使用的字符集為{a,b,c,d,e,f}，名字符在電文中出現的頻度分別為：34，5，12，23，8，18，試為這6個字符設計哈夫曼編碼。請先畫出你所構造的哈夫曼樹(要求樹中左孩子結點的權值小於右孩子結點的權值)，然後分別寫出每個字符對應的編碼。 27.已知一個圖如下所示，其頂點按a、b、c、d、e、f順序存放在鄰接表的頂點表中，請畫出該圖的鄰接表，使得按此鄰接表進行深度優先遍歷時得到的頂點序列為acbefd，進行廣度優先遍歷時得到的頂點序列為acbdfe。
28.已知兩個4×5的稀疏矩陣的三元組表分別如下： 0 1 4 16 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 請畫出這兩個稀疏矩陣之和的三元組表。 29.從空樹起，依次插入關鍵字40，8，90，15，62，95，12，23，56，32，構造一棵二叉排序樹。 (1)畫出該二叉排序樹 (2)畫出刪去該樹中元素值為90的結點之後的二叉排序樹。 四、算法閱讀題 (本大題共4小題，每小題5分，共20分) 30.如圖所示，利用同一循環向量空間實現兩個隊列，其類型Queue2定義如下：
typedef struct { DataType data[MaxSize]; int front[2],length[2]; } Queue2; 對於 i=0或1,front[i]和length[i]分別為第i個隊列的頭指針和長度域。請在空缺處填入合適的內容，實現第i個循環隊列的入隊操作。 int EnQueue(Queue2*Q,int i,DataType x) {//若第i個隊列不滿，則元素x入隊列，並返回1，否則返回0 if(i<0||i>1)return 0; if( (1) ) return 0; Q->data[ (2) ]=x; Q->length[ (3) ]++; return 1; } (1) (2) (3) 31.某二叉樹的線索鏈表存儲結構如圖(b)所示，其中p為指向根結點的指針，圖(a)為結點結構。閱讀下列算法，並回答問題： (1)寫出執行函數調用f(p)的輸出結果; (2)簡述函數f的功能。
{ while(t) { printf(t->data); if(t->lchild) t=t->lchild; else t=t->rchild; } } (1) (2) 32.下列函數FindCycle(G,i)的功能是，對一個采用鄰接表作存儲結構的有向圖G，利用深度優先搜索策略尋找一條經過頂點v i 的簡單回路。數組cycle_path用於保存搜索過程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中頂點v k 的下一個頂點是v j 。請在空缺處填入合適的內容，使其成為一個完整的算法。 vertex firstedge 已知鄰接表的頂點表結點結構為： adjvex next 邊表結點 EdgeNode結構為： int cycle_path[MaxNum]; int FindCycle(ALGraph*G,int i) {//若回路存在，則返回1，否則返回0 int j; for(j=0;j return DFSPath(G,i,i); } int DFSPath(ALGraph*G,int j,int i) { EdgeNode *p; int cycled=0; for(p=G->adjlist[j].firstedge;p&&!cycled;p=p->next) { cycle_path[j]=p->adjvex; if( (1 ) )cycled=1;//已找到回路 else if(cycle_path[p->adjvex]==-1)cycled= (2) ; } return (3) } (1) (2) (3) 33.閱讀下列函數algo,並回答問題。 (1)假設整型數組A[1..8]中的元素依次為(3，8，9，1，7，4，2，6)。執行函數調用algo(A,8)時，外層while的循環體執行多少次?函數的返回值是多少? (2)簡述函數algo(L,n)的功能。 int algo(int L[],intn) { int i=0,j,s=1,t=n; while (i!=(n+1)/2) { int x=L[s]; i=s;j=t; while(i
From:http://tw.wingwit.com/Article/program/sjjg/201311/23385.html