試卷01

天津金海通軟件筆試題

• 選擇題(4*4=16)

1. 對于雙向循環鏈表,在p指針所指的結點之后插入s指針所指結點的操作應為

1. p->next=s; ?s->pri=p; ?p->next->pri=s; ?s->next=p->next
2. p->next=s; ?p->next->pri=s; ?s->pri=p; ?s->next=p->next
3. s->pri =p; ?s->next=p->next; ?p->next=s; ?p->next->pri=s
4. s->pri=p; ?s->next=p->next; ?p->next->pri=s; ?p->next=s;

1. 以下程序的輸出結果是（ ?）

void main()

{

char st[20] = “hello\0\t\\\”;

printf(“%d %d \n”, strlen(st), sizeof(st));

return;

}

????????A.9 9 B．5 20 C．13 20 D．20 20

1. 若入棧序列的元素順序為A,B,C,D,E,判斷下列哪一個出棧序列是不可能的。

1. A、B、C、D、E
2. B、C、D、E、A
3. E、A、B、C、D
4. D、C、B、A、E

1. 將長度為n的單鏈表鏈接在長度為m的單鏈表后面，其算法的時間復雜度采用大O形式表示應該是（）

1. O(1)
2. O(n)
3. O(m)
4. O(n+m)

二、填空題(5*3+6=21)

1. 有一個有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當折半查找值為82的結點時，__________4_____________________次比較后查找成功。
2. 用P表示入棧操作，D表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的P和D的操作串為_________________PDPPDPDD__________________________
3. 頭文件中的 ifndef/define/endif 干什么用____防止頭文件的重復包含______
4. Makefile根據文件的___________時間戳___________判斷文件是否需要重新編譯
5. 折半查找的前提條件____________________序列有序_______________
6. 假設以數組seqn[m]存放循環隊列的元素,設變量rear和front分別指示循環隊列中隊尾的位置和隊頭的位置。(6)
   1. 如何判斷隊列為空、已滿
   2. 如果計算隊列中元素的個數

• 簡答題(4*5=20)

1. 寫出下列序列一次快速排序的結果：[3, 1, 4, 1, 5, 9, 2, 6]
2. 思考如何用兩個棧實現一個隊列，簡述思路即可
3. 已知一棵二叉樹的先序和中序遍歷序列：先序:A、B、C、D、E、F、G、H、I、J中序:C、B、A、E、F、D、I、H、J、G畫出該二叉樹
4. 簡述make工具的使用方式

四、編程題（43）

1. 有如下定義的

struct Node{

int Value; //該 node 的值

struct Node * Next；//指向下一個 Node

}

請寫一個函數，能夠將輸入的 Struct node 插入已有鏈表的末尾（7）

Void InserNode(struct Node* pList, struct Node* pInsertNode)

{}

1. 寫出折半查找的代碼（8）
2. 現已知單鏈表的頭結點struct node *H; 寫一個代碼將單向鏈表逆置（10）
   1. 將原來的第一個結點變成最后一個結點
   2. 保存原來的第二個結點
   3. 循環頭插(還需要再有一個指針保存下一個要頭插結點的地址)
3. 實現順序棧的結構體、創建、入棧的代碼（7）
4. 現在有一個簡單的工程項目，由main.c fun.c fun1.c和fun.h四個文件組成(且當前目錄下只有這四個文件)。其main.c中包含主函數和fun.h的頭文件，fun.c和fun1.c中為功能函數的實現，fun.h中為fun.c和fun1.c中功能函數的聲明 。請寫一個Makefile實現這幾個文件的編譯，提示Makefile提供的自動變量：$@所有目標、$^所有依賴、$<第一個依賴（11）
   
   
   

試卷02

藍際網絡筆試題

一、選擇題（4*5=20)
1.下列關于存儲結構和邏輯結構描述正確的是（? )
?a)存儲結構和程序具體實現的語言沒有關系
?b)算法的實現需要考慮邏輯結構
?c)邏輯結構就是實際的存儲結構
?d)算法的實現依賴于存儲結構
2.一個棧的入棧序列是 a , b , c , d , e ，則棧的不可能的輸出序列是（? )
?a ) edcba?
?b ) decba?
?c ) dceab?
?d ) abcde?
3.一個算法的時間復雜度為 T ( n )=2n^3+3n^2+4n+5log2n+2，則該 T ( n ）應記為
(? )
?a ) O ( n )
?b ) O ( n ^3)
?c ) O ( n ^4)
?d ) O (log2n)
4.在一個完全二叉樹中，編號為 i 的節點存在左孩子，則左孩子的編號是，設根節點編號為0(? ?)
?a )2i
?b )2i-1
?c )2i+1
?d )2i+2
5.在鏈表指針為 p 的結點之后插入指針為 s 的結點，正確的操作是哪一項？(? ?)
?a ) p.next = s ; s.next = p.next ;

?b ) s.next = p.next ; p.next = s ;

?c ) p.next = s ; p.next = s.next ;

?d ) p.next = s.next ; p.next = s ;
二、簡答題（40)
1.畫二叉樹寫出先序遍歷，后序： DBAEGHFIC 中序： DEBACGFHI (10)
2.算法的設計要求（5）
3.求下列結構體的大小，寫出求解過程（默認64位操作系統對齊）(10)

typedef struct{char name[20];struct{int day;char sex;short year;}p1;struct{short month;long num;}p2;
}LibraryRecord;

4.用兩個棧實現一個隊列的功能？簡述算法和思路（10)

5.求下列共用體的大小（默認64位操作系統）(5)
?

UnionA
{int arr[5];long int a;
};

三、編程題（40)
1.寫出程序刪除單鏈表中的所有節點（10)
2.寫程序，雙向循環鏈表的結構體，及其頭節點的創建和任意位置插入函數。(10)

3.折半查找的前提條件是什么？寫出折半查找的代碼（10)
4.寫出一個循環隊列的結構體，該隊列元素最多是 m 個。(10)
?a )寫出如何判斷該隊列為空的函數
?b )寫出如何判斷該隊列為滿的函數
?c )寫出計算當前隊列中的元素個數的函數