1.棧和隊列的共同特點是（只允許在端點處插入和刪除元素）
4.棧通常采用的兩種存儲結構是（線性存儲結構和鏈表存儲結構）
5.下列關于棧的敘述正確的是（D）
A.棧是非線性結構?B.棧是一種樹狀結構?C.棧具有先進先出的特征?D.棧有
后進先出的特征
6.鏈表不具有的特點是（B）A.不必事先估計存儲空間 ???B.可隨機訪問任一
元素
C.插入刪除不需要移動元素 ??D.所需空間與線性表長度成正比
7.用鏈表表示線性表的優點是（便于插入和刪除操作）
8.在單鏈表中，增加頭結點的目的是（方便運算的實現）
9.循環鏈表的主要優點是（從表中任一結點出發都能訪問到整個鏈表）
10.線性表?L＝（a1,a2,a3,……ai,……an），下列說法正確的是（D）
A.每個元素都有一個直接前件和直接后件 ?B.線性表中至少要有一個元
素
C.表中諸元素的排列順序必須是由小到大或由大到小
D.除第一個和最后一個元素外，?其余每個元素都有一個且只有一個直接
前件和直接后件
11.線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（ D）
A.必須是連續的 B.部分地址必須是連續的?C.一定是不連續的 D.連續不連續
都可以
12.線性表的順序存儲結構和線性表的鏈式存儲結構分別是（隨機存取的存儲
結構、順序存取的存儲結構）
13.樹是結點的集合，它的根結點數目是（有且只有?1）
14.在深度為?5?的滿二叉樹中， 葉子結點的個數為（31）
15.具有?3 個結點的二叉樹有（5 種形態）
16.設一棵二叉樹中有?3 個葉子結點，?有?8 個度為?1?的結點， 則該二叉樹中總
的結點數為（13）
17.已知二叉樹后序遍歷序列是?dabec，中序遍歷序列是?debac，它的前序遍歷
序列是（cedba）
18.已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH?和DBGEACHF，
則該二叉樹的后序遍歷為（DGEBHFCA）
19.若某二叉樹的前序遍歷訪問順序是?abdgcefh，中序遍歷訪問順序是
dgbaechf，則其后序遍歷的結點訪問順序是（gdbehfca）
20.數據庫保護分為： 安全性控制、 ?完整性控制 、并發性控制和數據的恢復。
1.?在計算機中，算法是指（解題方案的準確而完整的描述）
2.在下列選項中，哪個不是一個算法一般應該具有的基本特征（無窮性）
說明：?算法的四個基本特征是：?可行性、確定性、有窮性和擁有足夠的情報。
3.?算法一般都可以用哪幾種控制結構組合而成（順序、選擇、循環）
4.算法的時間復雜度是指（算法執行過程中所需要的基本運算次數）
5.?算法的空間復雜度是指（執行過程中所需要的存儲空間）
6.?算法分析的目的是（分析算法的效率以求改進）
7. ?下列敘述正確的是（C）
A?．算法的執行效率與數據的存儲結構無關
B?．算法的空間復雜度是指算法程序中指令（或語句）的條數
C?．算法的有窮性是指算法必須能在執行有限個步驟之后終止
D?．算法的時間復雜度是指執行算法程序所需要的時間
8.數據結構作為計算機的一門學科，主要研究數據的邏輯結構、 對各種數據
結構進行的運算，以及（數據的存儲結構）
9. ?數據結構中，?與所使用的計算機無關的是數據的（C）
A?．存儲結構 ?B?．物理結構 ??C?．邏輯結構 ??D?．物理和存儲結構
10. ?下列敘述中， 錯誤的是（B）
A?．數據的存儲結構與數據處理的效率密切相關
B?．數據的存儲結構與數據處理的效率無關
C?．數據的存儲結構在計算機中所占的空間不一定是連續的
D?．一種數據的邏輯結構可以有多種存儲結構
11.?數據的存儲結構是指（數據的邏輯結構在計算機中的表示）
12. ?數據的邏輯結構是指（反映數據元素之間邏輯關系的數據結構）
13. ?根據數據結構中各數據元素之間前后件關系的復雜程度，?一般將數據結
構分為（線性結構和非線性結構）
14. ?下列數據結構具有記憶功能的是（C）A．隊列?B．循環隊列?C．棧?D．順
序表
15. ?下列數據結構中，按先進后出原則組織數據的是（B）
A?．線性鏈表 ?B?．棧??????C?．循環鏈表????D?．順序表
16.?遞歸算法一般需要利用（隊列）實現。
17. ?下列關于棧的敘述中正確的是（D）A?．在棧中只能插入數據?B?．在棧中
只能刪除數據
C?．棧是先進先出的線性表??????D?．棧是先進后出的線性表
20.??由兩個棧共享一個存儲空間的好處是（節省存儲空間，降低上溢發生的
機率）
21. ?應用程序在執行過程中，需要通過打印機輸出數據時，?一般先形成一個??打印作業，將其存放在硬盤中的一個指定（隊列）中，當打印機空閑時，就
會按先來先服務的方式從中取出待打印的作業進行打印。
22.下列關于隊列的敘述中正確的是（C）A?．在隊列中只能插入數據 B?．在
隊列中只能刪除數據 ?C?．隊列是先進先出的線性表??????D?．隊列是先進
后出的線性表
23.下列敘述中，正確的是（D）A?．線性鏈表中的各元素在存儲空間中的位
置必須是連續的
B?．線性鏈表中的表頭元素一定存儲在其他元素的前面 C?．線性鏈表中的各?元素在存儲空間中的位置不一定是連續的，?但表頭元素一定存儲在其他元素?的前面 D．線性鏈表中的各元素在存儲空間中的位置不一定是連續的，?且各
元素的存儲順序也是任意的
24.下列敘述中正確的是（A）A?．線性表是線性結構 ??B?．棧與隊列是非線
性結構
C?．線性鏈表是非線性結構 ????????????????D?．二叉樹是線性結構
25. ?線性表?L?＝（a1,a2,a3,……ai,……an），下列說法正確的是（D）
A?．每個元素都有一個直接前件和直接后件 ??B?．線性表中至少要有一個元
素
C?．表中諸元素的排列順序必須是由小到大或由大到小?D?．除第一個元素和
最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件
26.線性表若采用鏈式存儲結構時，?要求內存中可用存儲單元的地址（連續不
連續都可以）
27.?鏈表不具有的特點是（B）A?．不必事先估計存儲空間??????B?．可隨機
訪問任一元素
C?．插入刪除不需要移動元素??????D?．所需空間與線性表長度成正比
28. ?非空的循環單鏈表?head?的尾結點（由?p 所指向），滿足（p->next=head）
29.與單向鏈表相比，雙向鏈表的優點之一是（更容易訪問相鄰結點）
30.?在（D）中，只要指出表中任何一個結點的位置，就可以從它出發依次
訪問到表中其他所有結點。A．線性單鏈表??????B．雙向鏈表??????C．線
性鏈表??????D?．循環鏈表
31. ?以下數據結構屬于非線性數據結構的是（C）A．隊列 ???B．線性表?C．二
叉樹???D?．棧
32.樹是結點的集合，它的根結點數目是（有且只有?1）
33.具有?3 個結點的二叉樹有（5 種形態）
34.?在一棵二叉樹上第?8 層的結點數最多是（128） 注：?2K-?1
35. ?在深度為?5?的滿二叉樹中， 葉子結點的個數為（16） 注：?2n-?1
36. ?在深度為?5?的滿二叉樹中， 共有（31）個結點。??注：?2n－1
37.設一棵完全二叉樹共有?699 個結點， 則在該二叉樹中的葉子結點數為
（350）
說明：完全二叉樹總結點數為?N，若?N 為奇數，?則葉子結點數為（N+1）/2；
若?N 為偶數， 則葉子結點數為?N/2。
38. ?設有下列二叉樹，對此二叉樹中序遍歷的結果是（B）
A?．ABCDEF
B?．DBEAFC
C?．ABDECF
D?．DEBFCA
39.已知二叉樹后序遍歷序列是?dabec，中序遍歷序列?debac，它的前序遍歷序
列是（cedba）
40. ?已知一棵二叉樹前序遍歷和中序遍歷分別為?ABDEGCFH 和
DBGEACHF，則該二叉樹的后序遍歷為（DGEBHFCA）
41.若某二叉樹的前序遍歷訪問順序是?abdgcefh，中序遍歷訪問順序是
dgbaechf，則其后序遍歷的結點訪問順序是（gdbehfca）
42. ?串的長度是（串中所含字符的個數）
43.設有兩個串?p 和?q，求?q 在?p?中首次出現位置的運算稱做（模式匹配）
44. N 個頂點的連通圖中邊的條數至少為（N-1）
45.N 個頂點的強連通圖的邊數至少有（N）
46.對長度為?n?的線性表進行順序查找，在最壞情況下所需要的比較次數為
（N）
47.?最簡單的交換排序方法是（冒泡排序）
48.假設線性表的長度為?n，則在最壞情況下，冒泡排序需要的比較次數為
（n(n-1)/2）
49.?在待排序的元素序列基本有序的前提下，效率最高的排序方法是（冒泡
排序）
50.?在最壞情況下，下列順序方法中時間復雜度最小的是（堆排序）
51.?希爾排序法屬于（插入類排序）
52.?堆排序法屬于（選擇類排序）
53.?在下列幾種排序方法中，要求內存量最大的是（歸并排序）
54. ?已知數據表?A?中每個元素距其最終位置不遠，為節省時間， 應采用（直
接插入排序）
55. ?算法的基本特征是可行性、確定性、 有窮性 ?和擁有足夠的情報。
1.一個算法通常由兩種基本要素組成： 一是對數據對象的運算和操作，二是
算法的控制結構。
1. ?算法的復雜度主要包括時間復雜度和 空間 復雜度。
2. ?實現算法所需的存儲單元多少和算法的工作量大小分別稱為算法的空間
復雜度和時間復雜度 。
3.所謂數據處理是指對數據集合中的各元素以各種方式進行運算， 包括插入、
刪除、查找、更改等運算，也包括對數據元素進行分析。
4.數據結構是指相互有關聯的 數據元素?的集合。
5.數據結構分為邏輯結構與存儲結構，線性鏈表屬于 存儲結構 。
6.數據結構包括數據的 邏輯 結構和數據的存儲結構。
7.?數據結構包括數據的邏輯結構、數據的 存儲結構?以及對數據的操作運
算。
8.數據元素之間的任何關系都可以用 前趨和后繼 關系來描述。
9.數據的邏輯結構有線性結構和非線性結構兩大類。
10.常用的存儲結構有順序、鏈接、??索引 等存儲結構。
11.?順序存儲方法是把邏輯上相鄰的結點存儲在物理位置??相鄰?的存儲單
元中。
12. ?棧的基本運算有三種：入棧、退棧與讀棧頂元素?。
13. ?隊列主要有兩種基本運算：入隊運算與?退隊運算 。
14. ?在實際應用中，帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存
儲結點，這種帶鏈的棧稱為?可利用棧 。
15.棧和隊列通常采用的存儲結構是?鏈式存儲和順序存儲 ?。
16.當線性表采用順序存儲結構實現存儲時，其主要特點是?邏輯結構中相鄰
的結點在存儲結構中仍相鄰?。
17. ?循環隊列主要有兩種基本運算：入隊運算與退隊運算。?每進行一次入隊
運算，隊尾指針就?進?1?。
18.當循環隊列非空且隊尾指針等于對頭指針時， 說明循環隊列已滿，不能進
行入隊運算。這種情況稱為?上溢 ?。
19.當循環隊列為空時，?不能進行退隊運算，這種情況稱為?下溢 。
20. ?在一個容量為?25?的循環隊列中， 若頭指針 front=16，尾指針?rear=9?，則?該循環隊列中共有?18 ?個元素。 注：當?rear<front?時，元素個數＝總容量-
（front－rear）；
當?rear>front?時，元素個數＝rear－front。
1.判斷鏈表是否存在環型鏈表問題：判斷一個鏈表是否存在環，例如下面這
個鏈表就存在一個環：
例如?N1->N2->N3->N4->N5->N2 就是一個有環的鏈表，環的開始結點是?N5?這里有一個比較簡單的解法。設置兩個指針?p1，p2。每次循環?p1?向前走一?步，?p2?向前走兩步。直到?p2 碰到?NULL 指針或者兩個指針相等結束循環。
如果兩個指針相等則說明存在環。
struct link
{
int data;
link* next;
};
boolIsLoop(link* head)
{
link* p1=head, *p2 = head;
if (head ==NULL || head->next ==NULL)
{
return false;
}
do{
p1= p1->next;
p2 = p2->next->next;
} while(p2 && p2->next && p1!=p2);
if(p1 == p2)
return true;
else
return false;
}
2,鏈表反轉 單向鏈表的反轉是一個經常被問到的一個面試題， 也是一個非常
基礎的問題。比如一個鏈表是這樣的：??1->2->3->4->5?通過反轉后成為
5->4->3->2->1。最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲
遍歷過程中當前指針指向的下一個元素，然后將當前節點元素的指針反轉
后，利用已經存儲的指針往后面繼續遍歷。源代碼如下：
struct linka?{
int data;
linka* next;
};
void reverse(linka*& head)
{
if(head ==NULL)
return;
linka*pre, *cur,?*ne;
pre=head;
cur=head->next;
while(cur)
{
ne = cur->next;
cur->next = pre;
pre =?cur;
cur =?ne;
}
head->next = NULL;
head =?pre;
}
還有一種利用遞歸的方法。這種方法的基本思想是在反轉當前節點之前先調?用遞歸函數反轉后續節點。源代碼如下。不過這個方法有一個缺點，就是在?反轉后的最后一個結點會形成一個環，所以必須將函數的返回的節點的?next??域置為?NULL。因為要改變?head 指針，?所以我用了引用。算法的源代碼如下：
linka* reverse(linka* p,linka*& head)
{
if(p == NULL || p->next == NULL)
{
head=p;
return p;
}
else
{
linka* tmp = reverse(p->next,head);
tmp->next = p;
return p;
}
}
3,判斷兩個數組中是否存在相同的數字 給定兩個排好序的數組， 怎樣高效得
判斷這兩個數組中存在相同的數字？
這個問題首先想到的是一個?O(nlogn)的算法。就是任意挑選一個數組，遍歷?這個數組的所有元素，遍歷過程中，在另一個數組中對第一個數組中的每個
元素進行?binary search。用 C++實現代碼如下：
bool findcommon(inta[],int size1,intb[],int size2)
{
inti;
for(i=0;i<size1;i++)
{
int start=0,end=size2-1,mid;
while(start<=end)
{
mid=(start+end)/2;
if(a[i]==b[mid])
return true;
elseif?(a[i]<b[mid])
end=mid-1;
else
start=mid+1;
}
}
return false;
}
后來發現有一個 O(n)算法。因為兩個數組都是排好序的。所以只要一次遍歷?就行了。首先設兩個下標，分別初始化為兩個數組的起始地址，依次向前推?進。推進的規則是比較兩個數組中的數字，小的那個數組的下標向前推進一?步，直到任何一個數組的下標到達數組末尾時，如果這時還沒碰到相同的數
字，說明數組中沒有相同的數字。
bool findcommon2(inta[], int size1,intb[], int size2)
{
inti=0,j=0;
while(i<size1 &&?j<size2)
{
if(a[i]==b[j])
return true;
if(a[i]>b[j])
j++;
if(a[i]<b[j])
i++;
}
return false;
}
4,最大子序列?問題：
給定一整數序列?A1?， A2，... An ??（可能有負數），求?A1~An?的一個子序列
Ai~Aj，使得?Ai?到?Aj?的和最大
例如：
整數序列-2,?11, -4,?13, -5, 2, -5, -3,?12, -9?的最大子序列的和為?21。
對于這個問題，最簡單也是最容易想到的那就是窮舉所有子序列的方法。利?用三重循環，依次求出所有子序列的和然后取最大的那個。當然算法復雜度?會達到?O(n^3)。顯然這種方法不是最優的，?下面給出一個算法復雜度為?O(n)??的線性算法實現，算法的來源于?Programming Pearls?一書。?在給出線性算法?之前，先來看一個對窮舉算法進行優化的算法，它的算法復雜度為?O(n^2)?。?其實這個算法只是對對窮舉算法稍微做了一些修改：其實子序列的和我們并?不需要每次都重新計算一遍。假設?Sum(i,?j)是?A[i] ... A[j]的和，那么?Sum(i,?j+1)
= Sum(i,?j) + A[j+1]。利用這一個遞推，我們就可以得到下面這個算法：
int max_sub(inta[],int size)
{
inti,j,v,max=a[0];
for(i=0;i<size;i++)
{
v=0;
for(j=i;j<size;j++)
{
v=v+a[j];//Sum(i,?j+1) = Sum(i,?j) + A[j+1]
if(v>max)
max=v;
}
}
return max;
}
那怎樣才能達到線性復雜度呢？這里運用動態規劃的思想。先看一下源代碼
實現：
int max_sub2(inta[], int size)
{
inti,max=0,temp_sum=0;
for(i=0;i<size;i++)
{
temp_sum+=a[i];
if(temp_sum>max)
max=temp_sum;
elseif(temp_sum<0)
temp_sum=0;
}
return max;
}
6,按單詞反轉字符串 ?并不是簡單的字符串反轉，而是按給定字符串里的單?詞將字符串倒轉過來，就是說字符串里面的單詞還是保持原來的順序，這里
的每個單詞用空格分開。例如：
Here is
經過反轉后變為：
如果只是簡單的將所有字符串翻轉的話，可以遍歷字符串，將第一個字符和?最后一個交換，第二個和倒數第二個交換，依次循環。其實按照單詞反轉的?話可以在第一遍遍歷的基礎上，再遍歷一遍字符串，對每一個單詞再反轉一
次。這樣每個單詞又恢復了原來的順序。
char* reverse_word(const char* str)
{
int len = strlen(str);
char* restr = new char[len+1];
strcpy(restr,str);
inti,j;
for(i=0,j=len-1;i<j;i++,j--)
{
chartemp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
}
intk=0;
while(k<len)
{
i=j=k;
while(restr[j]!=' ' && restr[j]!='' )
j++;
k=j+1;
j--;
for(;i<j;i++,j--)
{
chartemp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
}
}
return restr;
}
如果考慮空間和時間的優化的話，當然可以將上面代碼里兩個字符串交換部
分改為異或實現。
例如將
chartemp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
改為
restr[i]^=restr[j];
restr[j]^=restr[i];
restr[i]^=restr[j];
7,字符串反轉 ?我沒有記錯的話是一道?MSN?的筆試題，網上無意中看到的，?拿來做了一下。題目是這樣的，給定一個字符串，?一個這個字符串的子串，
將第一個字符串反轉，但保留子串的順序不變。例如：
輸入：第一個字符串: "This is fishsky's Chinese site:
子串: "fishsky"
輸出：??"nc/nc.moc.fishsky.
一般的方法是先掃描一邊第一個字符串，然后用?stack 把它反轉，同時記錄 下子串出現的位置。然后再掃描一遍把記錄下來的子串再用?stack 反轉。我 用的方法是用一遍掃描數組的方法。掃描中如果發現子串，就將子串倒過來
壓入堆棧。
最后再將堆棧里的字符彈出，這樣子串又恢復了原來的順序。源代碼如下：
#include <iostream>
#include <cassert>
#include <stack>
using namespace std;
//reverse the string 's1' except the substring'token'.
const char* reverse(const char* s1,const char* token)
{
assert(s1 && token);
stack<char> stack1;
const char* ptoken = token,?*head = s1,?*rear =?s1;
while (*head?!=?'')
{
while(*head!= '' && *ptoken ==?*head)
{
ptoken++;
head++;
}
if(*ptoken == '')//contain the token
{
const char* p;
for(p=head-1;p>=rear;p--)
stack1.push(*p);
ptoken = token;
rear = head;
}
else
{
stack1.push(*rear);
head=++rear;
ptoken = token;
}
}
char * return_v = new char[strlen(s1)+1];
inti=0;
while(!stack1.empty())
{
return_v[i++] = stack1.top();
stack1.pop();
}
return_v[i]='';
return return_v;
}
int main(int argc, char* argv[])
{cout<<"This is fishsky's Chinese site:
";
cout<<reverse("This is fishsky's Chinese site:
fishsky.com.cn/cn"," fishsky ");
return 0;
}
8,?刪除數組中重復的數字 ?問題： 一個動態長度可變的數字序列，以數字
0 為結束標志，要求將重復的數字用一個數字代替，例如：
將數組?1,1,1,2,2,2,2,2,7,7,1,5,5,5,0 ?轉變成?1,2,7,1,5,0 ?問題比較簡單，要注意
的是這個數組是動態的。所以避免麻煩我還是用了?STL?的?vector。
#include <iostream>
#include <vector>
using namespace?std;
//remove the duplicated numbers in an intger array, the array was end?with?0;
//e.g.?1,1,1,2,2,5,4,4,4,4,1,0 --->1,2,5,4,1,0
void static remove_duplicated(inta[], vector<int>& _st)
{
_st.push_back(a[0]);
for(inti=1;_st[_st.size()-1]!=0;i++)
{
if(a[i-1]!=a[i])
_st.push_back(a[i]);
}
}
當然如果可以改變原來的數組的話，可以不用?STL，僅需要指針操作就可以
了。下面這個程序將修改原來數組的內容。
void static remove_duplicated2(inta[])
{
if(a[0]==0 || a==NULL)
return;
int insert=1,current=1;
while(a[current]!=0)
{
if(a[current]!=a[current-1])
{
a[insert]=a[current];
insert++;
current++;
}
else
current++;
}
a[insert]=0;
}
9,如何判斷一棵二叉樹是否是平衡二叉樹 ?問題：判斷一個二叉排序樹是否
是平衡二叉樹 解決方案：
根據平衡二叉樹的定義，如果任意節點的左右子樹的深度相差不超過?1，那
這棵樹就是平衡二叉樹。
首先編寫一個計算二叉樹深度的函數，利用遞歸實現。
template<typename T>
static int Depth(BSTreeNode<T>* pbs)
{
if (pbs==NULL)
return 0;
else
{
intld = Depth(pbs->left);
intrd = Depth(pbs->right);
return?1 + (ld >rd? ld?: rd);
}
}
下面是利用遞歸判斷左右子樹的深度是否相差?1 來判斷是否是平衡二叉樹的
函數：
template<typename T>
static boolisBalance(BSTreeNode<T>* pbs)
{
if (pbs==NULL)
return true;
intdis = Depth(pbs->left) - Depth(pbs->right);
if (dis>1 || dis<-1?)
return false;
else
return isBalance(pbs->left) && isBalance(pbs->right);
4.abstract class Something?{
private abstract String doSomething ();
}
該段代碼有錯嗎？
答案: ?錯。?abstract?的?methods 不能以?private 修飾。 abstract?的?methods 就是讓子
類?implement(實現)具體細節的，怎么可以用?private 把?abstract method?封鎖起來
呢? (同理， abstract method?前不能加?final)。
5.看看下面的代碼段錯在哪里？
public class Something?{
void doSomething ()?{
private String?s =?"";
intl = s.length();
}
}
答案: ?錯。局部變量前不能放置任何訪問修飾符 (private，public，和?protected)。
final 可以用來修飾局部變量
(final 如同?abstract 和?strictfp，都是非訪問修飾符，strictfp?只能修飾?class?和?method
而非?variable)。
6. ?下面該段代碼是否有錯，若是有錯錯在哪里？
abstract class Name?{
private String name;
public abstract boolean isStupidName(String name)?{}
}
答案: ?錯。?abstract method 必須以分號結尾，且不帶花括號。
——Seaborn)
輸出形式)
