您好,登錄后才能下訂單哦!
常見的Java中數據結構面試題?針對這個問題,這篇文章詳細介紹了相對應的分析和解答,希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
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; }; bool IsLoop(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(int a[],int size1,int b[],int size2) { int i; 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; else if (a[i]<b[mid]) end=mid-1; else start=mid+1; } } return false; }
后來發現有一個 O(n)算法。因為兩個數組都是排好序的。所以只要一次遍歷就行了。首先設兩個下標,分別初始化為兩個數組的起始地址,依次向前推進。推進的規則是比較兩個數組中的數字,小的那個數組的下標向前推進一步,直到任何一個數組的下標到達數組末尾時,如果這時還沒碰到相同的數字,說明數組中沒有相同的數字。
bool findcommon2(int a[], int size1, int b[], int size2) { int i=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(int a[],int size) { int i,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(int a[], int size) { int i,max=0,temp_sum=0; for(i=0;i<size;i++) { temp_sum+=a[i]; if(temp_sum>max) max=temp_sum; else if(temp_sum<0) temp_sum=0; } return max; }
6,按單詞反轉字符串并不是簡單的字符串反轉,而是按給定字符串里的單詞將字符串倒轉過來,就是說字符串里面的單詞還是保持原來的順序,這里的每個單詞用空格分開。
如果只是簡單的將所有字符串翻轉的話,可以遍歷字符串,將第一個字符和最后一個交換,第二個和倒數第二個交換,依次循環。其實按照單詞反轉的話可以在第一遍遍歷的基礎上,再遍歷一遍字符串,對每一個單詞再反轉一次。這樣每個單詞又恢復了原來的順序。
char* reverse_word(const char* str) { int len = strlen(str); char* restr = new char[len+1]; strcpy(restr,str); int i,j; for(i=0,j=len-1;i<j;i++,j--) { char temp=restr[i]; restr[i]=restr[j]; restr[j]=temp; } int k=0; while(k<len) { i=j=k; while(restr[j]!=' ' && restr[j]!='' ) j++; k=j+1; j--; for(;i<j;i++,j--) { char temp=restr[i]; restr[i]=restr[j]; restr[j]=temp; } } return restr; }
如果考慮空間和時間的優化的話,當然可以將上面代碼里兩個字符串交換部分改為異或實現。
例如將
char temp=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 mianwww's Chinese site: http://www.mianwww.com.cn/cn"
子串: "mianwww"
輸出: "nc/nc.moc.mianwww.www//:ptth :etis esenihC s'mianwww si sihT"
一般的方法是先掃描一邊第一個字符串,然后用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]; int i=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 mianwww 's Chinese site: http://www.mianwww.com.cn/cn "; cout<<reverse("This is mianwww's Chinese site: http://www. mianwww.com.cn/cn"," mianwww "); 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(int a[], vector<int>& _st) { _st.push_back(a[0]); for(int i=1;_st[_st.size()-1]!=0;i++) { if(a[i-1]!=a[i]) _st.push_back(a[i]); } }
當然如果可以改變原來的數組的話,可以不用STL,僅需要指針操作就可以了。下面這個程序將修改原來數組的內容。
void static remove_duplicated2(int a[]) { 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 { int ld = Depth(pbs->left); int rd = Depth(pbs->right); return 1 + (ld >rd ? ld : rd); } }
下面是利用遞歸判斷左右子樹的深度是否相差1來判斷是否是平衡二叉樹的函數:
template<typename T> static bool isBalance(BSTreeNode<T>* pbs) { if (pbs==NULL) return true; int dis = 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 = “”; int l = 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必須以分號結尾,且不帶花括號。
關于常見的Java中數據結構面試題問題的解答就分享到這里了,希望以上內容可以對大家有一定的幫助,如果你還有很多疑惑沒有解開,可以關注億速云行業資訊頻道了解更多相關知識。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。