數據結構算法思想總結（精品十二篇）_數據結構算法思想總結

數據結構算法思想總結（精品十二篇）。

?1?數據結構算法思想總結

?2?數據結構算法思想總結

1. 對鏈表設置頭結點的作用是什么?(至少說出兩條好處) 2. 在hq的鏈隊中，設計一個算法求該連隊中結點的個數。 3. 假設有如下的結構定義： struct node {

char data;

struct node * link; }

* p, *pre;

而且pre指向鏈表中非空元素，寫一段程序生成構造p結點，并將其鏈入到pre之后。 4. 求1到n的平方和(利用遞歸函數調用) 5. 為什么要采用循環隊列?

?3?數據結構算法思想總結

第一部分　基本概念

第1章　數據結構基礎

1.1　問題求解分析

1.2　數據結構

1.3　數據結構的分類

1.4　數據的四種基本存儲方法

1.5　數據結構三方面的關系

習題

第2章　算法及算法分析基礎

2.1　算法的基本概念

2.2　算法的描述

2.3　算法分析方法

2.4　程序語言的基本語句與基本結構

2.5　數組與結構

2.6　抽象數據類型的表示與定義

習題

第二部分　簡單數據結構

第3章　線性表

3.1　線性表的定義

3.2　線性表的運算

3.3　線性表的順序存儲結構及實現

3.3.1 線性表的順序存儲結構

3.3.2　順序表的實現

3.4　線性表的鏈式存儲結構及實現

3.4.1　單鏈表

3.4.2　循環鏈袁

3.4.3　雙向鏈表

3.4.4　靜態鏈表

3.4.5　順序表和鏈表的比較

3.5　線性表的`應用

習題

第4章　棧和隊列

4.1 棧

4.1.1 問題的提出

4.1.2　定義及其操作

4.1.3　棧的存儲結構及實現

4.1.4　棧的應用舉例：表達式求值

4.2 隊列

4.2.1 問題的提出

4.2.2　隊列的定義及操作

4.2.3　隊列的存儲結構及實現

4.2.4　隊列的應用舉例

習題

第5章　矩陣和廣義表

5.1　矩陣的存儲

5.2　特殊矩陣

5.3　稀疏矩陣

5.4　廣義表

習題

第三部分　復雜數據結構

第6章　二叉樹和樹

6.1 二叉樹的定義和性質

6.1.1　二叉樹的定義及相關術語

6.1.2　特殊二叉樹

6.1.3　二叉樹的性質

6.2　二叉樹的存儲結構

6.2.1 二叉樹的順序存儲表示

6.2.2　二叉樹的鏈式存儲表示

6.3　二叉樹的遍歷

6.3.1 問題的提出

6.3.2　二叉樹的遍歷算法

6.3.3　二叉樹遍歷的非遞歸實現

6.3.4　遍歷算法的應用

6.4　二叉樹的線索化

6.4.1 線索二叉樹的定義

6.4.2　線索二叉樹的結構

6.4.3　二叉樹的線索化算法

6.4.4　線索二叉樹基本操作的實現

6.5　二叉樹的應用——哈夫曼樹

……

第7章　圖

第8章　散列結構

第9章　集合結構

第四部分　算法與數據結構應用

?4?數據結構算法思想總結

實驗報告;課程名稱：數據結構班級：軟件工程實驗成績：;1206;實驗名稱：打印機隊列模擬學號：4848批;程序的設計;實驗編號：實驗一姓名：實驗日期：5月2;一、實驗目的;對隊列的理解;對STL中的queue的使用;實驗仿真一個網絡打印過程;二、實驗內容與實驗步驟流程圖;這個任務隊列的測試使用STL隊列適配器;具體地說,每一行中包含的信息是

這個任務隊列的測試使用STL隊列適配器。程序要求完成模擬的實現共享打印機。這個打印機使用先進先出隊列。仿真是通過讀取和處理事件數據文件的列表。一個有效的數據文件中的每一行包含信息打印作業和提交這份工作的時間。

具體地說,每一行中包含的信息是提交工作的時間(以秒為單位),和在頁面的工作長及工作的計算機的名稱。在模擬的開始,每個這些事件的每一個應該被程序所讀，存儲在繼承工作負載隊列。程序應該通過循環遞增計數器或while-loop模擬時間的流逝。程序應該將計數器初始化為零,然后依次增加1秒。當模擬等于當前時間的打印作業的提交時間在工作隊列的前面，一個打印作業完成。當這一切發生的時候,從工作隊列取出這個事件,然后把它放在另一個隊列對象。這個隊列對象存儲已完成的打印作業。當程序仿真其他的打印工作的時候，這些工作在隊列等待。

#include “simulator.h”

protected:

queue waiting;

priority_queue priority_waiting;

public:

fifo(int seconds_per_page);

void simulate(string file);

};

bool operator < (event evtleft,event evtright);

using namespace std;

fifo::fifo(int seconds_per_page):simulator(seconds_per_page){ }

void fifo::simulate(string file){

int finish_time = 0;

float agg_latency = 0;

int totaljob =0;

event evt;

if(file.find(“arbitrary”)!= string::npos){

string outfile =“arbitrary.out”;

ofstream osf(outfile.c_str());

loadworkload(file);

osf<

for(int time =1;!waiting.empty()||!workload.empty();time++){ while(!workload.empty() && time ==

workload.front().arrival_time()){

evt= workload.front();

osf<

workload.pop();

}

if(!waiting.empty() && time >= finish_time){

totaljob ++;

evt = waiting.front();

agg_latency += time - evt.arrival_time();

osf<

finish_time = time + evt.getjob().getnumpages() * seconds_per_page;

}

}

osf<

osf<

osf<

return;

}

if(file.find(“bigfirst”) != string::npos){

string outfile = “bigfirst.out”;

ofstream osf(outfile.c_str());

loadworkload(file);

=1;!priority_waiting.empty()||!workload.empty();time++){

while(!workload.empty() && time ==

workload.front().arrival_time()){

evt= workload.front();

osf<

workload.pop();

}

if(!priority_waiting.empty() && time >= finish_time){

totaljob ++;

evt = priority_();

agg_latency += time - evt.arrival_time();

osf<

finish_time = time + evt.getjob().getnumpages() * seconds_per_page; }

}

osf<

osf<

osf<

return;

}

cerr<

cerr<

bool operator < (event evtleft,event evtright){

return evtleft.getjob().getnumpages() <

evtright.getjob().getnumpages();

經測試，功能較為完整。代碼流程簡圖如下：

通過這次實驗，我了解了有關隊列方面的知識。掌握了隊列的邏輯結構，抽象數據類型，隊列的存儲方式等。運用先進先出表，仿真了網絡打印隊列。這都使我對數據結構的學習有了新的認識與幫助。在實驗過程中，我也遇到了許多困難，從開始時對隊列運算的不熟悉，到逐漸查找資料，從而完成了實驗;六、附錄;-《數據結構與算法分析》以及網上資料;

逐漸查找資料，從而完成了實驗。在今后的學習中，我將繼續努力，加強對堆棧，隊列等知識的學習，以達到精益求精。

?5?數據結構算法思想總結

21、在計算機中，組成一個字節的二進制位位數是( 8 )。

22、下列關于ASCII編碼的敘述中，正確的是( 所有大寫英文字母的ASCII碼值都大于小寫英文字母‘a’的ASCⅡ碼值)

23、下列選項屬于“計算機安全設置”的是( 停掉Guest賬號 )。

24、CPU主要技術性能指標有( 字長、主頻和運算速度 )。

25、下列設備組中，完全屬于輸入設備的一組是( 繪圖儀，鍵盤，鼠標器 )

26、計算機系統軟件中，最基本、最核心的軟件是( 操作系統 )。

27、下列軟件中，屬于系統軟件的是( Windows Vista )。

28、下列關于計算機病毒的敘述中，正確的是( 反病毒軟件必須隨著新病毒的出現而升級，提高查、殺病毒的功能 )。

29、如果刪除一個非零無符號二進制偶整數后的2個O，則此數的值為原數( 1/4 )

30、高級程序設計語言的特點是( 高級語言數據結構豐富 )。

31、計算機硬件能直接識別、執行的語言是( 機器語言 )

32、計算機的系統總線是計算機各部件間傳遞信息的公共通道，它分(數據總線、控制總線和地址總線)。

33、微機硬件系統中最核心的部件是( CPU )

34、用“綜合業務數字網”(又稱“一線通”)接人因特網的優點是上網通話兩不誤，它的英文縮寫是(ISDN)

35、當電源關閉后，下列關于存儲器的說法中，正確的是(存儲在ROM中的數據不會丟失 )

36、計算機指令由兩部分組成，它們是(操作碼和操作數)

37、有一域名為bit. edu. cn，根據域名代碼的規定，此域名表示(教育機構)。

38、能保存網頁地址的文件夾是( 收藏夾 )

39、按電子計算機傳統的分代方法，第一代至第四代計算機依次是(電子管計算機，晶體管計算機、小、中規模集成電路計算機，大規模和超大規模集成電路計算機)

40、假設某臺式計算機的內存儲器容量為256MB,硬盤容量為40GB，硬盤的容量是內在容量的(160倍)

?6?數據結構算法思想總結

當我開始學習數據結構時，我對這門學科充滿了興趣和好奇。作為一名計算機科學專業的學生，我知道數據結構是編程的核心，掌握數據結構將有助于提高我的編程能力和解決問題的能力。在這篇文章中，我將分享我的學習數據結構的經歷和心得體會。

首先，我選擇了一門數據結構的入門課程，開始了我的學習之旅。在學習過程中，我很快就發現數據結構并非簡單的概念和算法，而是實際應用中常用的工具。數據結構的應用場景和實際問題的解決方式，讓我感受到了數據結構的魅力和實用性。

在學習每個數據結構時，我遇到了很多挑戰。例如，在掌握二叉樹和圖的數據結構時，我遇到了許多關于數據結構和算法的問題。我意識到，理解數據結構和算法需要時間和實踐。我通過閱讀教材、做練習和參與編程項目，逐漸掌握了每個數據結構的基本概念、實現和應用。

學習數據結構也讓我學會了如何系統地學習一門學科。我學會了如何閱讀和理解數據結構教材，如何提出問題并尋找解決方案。在學習過程中，我也意識到了自己的不足和需要改進的地方，例如對算法的理解和實現能力。

回顧我的學習數據結構的經歷，我深刻地認識到數據結構的重要性，以及掌握數據結構對提高編程能力和解決問題的重要性。此外，我也學到了如何系統地學習一門學科，如何通過實踐和思考來提高自己的能力。這些經驗將對我未來的學習和職業生涯產生積極的影響。

總之，學習數據結構是一個充滿挑戰和收獲的過程。通過學習數據結構，我不僅提高了自己的編程能力，還學會了如何系統地學習一門學科，以及如何通過實踐和思考來提高自己的能力。我相信，這些經驗將對我未來的學習和職業生涯產生積極的影響。

?7?數據結構算法思想總結

一個有趣的問題經常出現，那就是兩個看似不同的程序，到底哪個更好呢?

要回答這個問題, 我們必須知道程序和代表程序的算法有很大的區別. 算法是一個通用的, 解決問題的一條條的指令. 提供一個解決任何具有指定輸入的實例問題方法, 算法產生期望的結果. 一個程序, 另一方面, 是將算法用某一門編程語言代碼實現. 有很多的程序實現的同一算法, 取決于程序員和編程語言的使用.

進一步的探究這種差異, 考察下面的函數代碼. 這個函數解決一個簡單的問題, 計算前n個自然數的和. 解決方案遍歷這 n 個整數, 相加后賦值到累加器.

for i in range(1,n+1):

接下來看下面的代碼. 第一眼看上去感覺很奇怪, 但是深入理解之后你將發現這個函數和上面的函數完成同樣的工作. T原因是這個函數不是那么明顯，代碼難看. 我們沒有使用好的變量名導致可讀性很差, 并且還聲明了沒有必要聲明的變量.

for bill in range(1,tom+1):

到底哪段代碼更好呢.問題的答案取決于你的標準.如果你只關注可讀性，函數sumOfN 肯定比 foo 好. 事實上, 你可能在你的編程啟蒙課上見到過很多教你編寫可讀性好和易于理解的程序的例子. 然而在這里, 我們還對算法感興趣.

作為替代空間的需求, 我們基于它們執行時間來分析和比較算法. 這種度量有時候被稱為算法的“執行時間”或”運行時間“. 我們測量 sumOfN 函數執行時間的一種方法是做個基準分析. 在Python, 我們可以通過一個函數針對我們所使用的系統上標記程序的起始和結束時刻. 在 time 模塊有一個被稱為 time 的函數，將返回系統的當前時間. 通過兩次調用這個函數, 起始和結束, 然后計算差值, 我們可以得到準確的執行時間.

def sumOfN2(n):

for i in range(1,n+1):

Listing 1 展示了sumOfN 函數在求和前后的時間開銷. 測試結果如下:

>>>for i in range(5):

print(”Sum is %d required %10.7f seconds“%sumOfN(10000))

Sum is 50005000 required?0.0018950 seconds

Sum is 50005000 required?0.0018620 seconds

Sum is 50005000 required?0.0019171 seconds

Sum is 50005000 required?0.0019162 seconds

Sum is 50005000 required?0.0019360 seconds

我們發現時間相當的一致并且都平均花費 0.0019 秒執行程序. 那么假如我們將n增大到 100,000 會怎樣呢?

>>>for i in range(5):

print(”Sum is %d required %10.7f seconds“%sumOfN(100000))

Sum is 5000050000 required?0.0199420 seconds

Sum is 5000050000 required?0.0180972 seconds

Sum is 5000050000 required?0.0194821 seconds

Sum is 5000050000 required?0.0178988 seconds

Sum is 5000050000 required?0.0188949 seconds

>>>

再次, 時間更長, 非常的一致,平均10倍的時間. 將 n 增大到 1,000,000 我們達到:

>>>for i in range(5):

print(”Sum is %d required %10.7f seconds“%sumOfN(1000000))

Sum is 500000500000 required?0.1948988 seconds

Sum is 500000500000 required?0.1850290 seconds

Sum is 500000500000 required?0.1809771 seconds

Sum is 500000500000 required?0.1729250 seconds

Sum is 500000500000 required?0.1646299 seconds

>>>

在這種情況下,平均執行時間又一次被證實是之前的10倍.

現在來看一下 Listing 2, 提出了一個不同的解決求和問題的方法. 這個函數, sumOfN3, 運用了一個等式：∑ni = (n+1)n/2來計算前 n 個自然數取代循環計算.

def sumOfN3(n):

如果我們針對 sumOfN3 做一些測試, 使用5種不同的n值(10,000, 100,000, 1,000,000, 10,000,000, and 100,000,000), 我們得到下面的結果:

Sum is 50005000 required 0.00000095 seconds

Sum is 5000050000 required 0.00000191 seconds

Sum is 500000500000 required 0.00000095 seconds

Sum is 50000005000000 required 0.00000095 seconds

Sum is 5000000050000000 required 0.00000119 seconds

對于這個輸出，有兩個方面需要注意. 第一, 上面程序的運行時間比前面的任意一個的運行時間都短. 第二, 無論n為多大執行時間都是一致的.

但是這個標準真正地告訴我們什么?直觀地說, 我們可以看到，迭代的解決方案似乎是因為一些程序步驟被重復而做更多的工作. 這是它占用更多運行時間可能的原因. 當我們增加 n的時候循環方案執行時間也在增加. 然而,有一個問題. 如果我們跑相同的功能在不同的計算機或使用不同的編程語言,我們可能會得到不同的結果. 如果是老式計算機將可能在 sumOfN3上執行更多的時間.

我們需要一種更好的方式來描述這些算法的執行時間，

，

基準的方法計算實際的執行時間。它并不真的為我們提供了一個有用的測量，因為它是依賴于特定的機器，當前時間，編譯，和編程語言。相反，我們要有一個特性，是獨立于程序或計算機的使用。這一方法將獨立地判斷使用的算法是有用的，可以用來在實現算法比較。

一個展示算法不同的數量級的例子是經典的字符串易位問題. 一個字符串和另一個字符串如果僅僅是字母的位置發生改變我們就稱為易位. 例如, 'heart' 和 'earth' 就互為易位. 字符串'python'和 'typhon' 也是. 為簡化問題的討論,我們假設字符串中的字符為26個英文字母并且兩個字符串的長度相同. 我們的目標是寫一個boolean 類型的函數來判斷兩個給定的字符串是否互為易位.

對于易位問題，我們的第一個解決方案是檢測第一個字符串的每一個字母是否在第二個字符串中. 如果成功檢測所有的字母, 那么兩個字符串是易位的. 檢查一個字母成功后將使用 Python的特殊值 None 取代. 然而, 因為在 Python 中string是不可變的, 第一步將字符串轉換成 list. 看下面的代碼：

def anagramSolution1(s1,s2):

while pos1 < len(s1) and stillOK:

while pos2 < len(alist) and not found:

if s1[pos1] == alist[pos2]:

if found:

print(anagramSolution1('abcd','dcba'))

另一個解決方案基于的思想是：即使兩個字符串 s1 和 s2 不同, t它們易位當且僅當它們包含完全相同的字母集合. 因此, 如果我們首先將兩個字符串的字符按照字典排序, 如果兩個字符串易位，那么我們將得到完全一樣的兩個字符串. 在 Python 我們可以使用list的內建方法 sort 來簡單的實現排序.看下面的代碼：

def anagramSolution2(s1,s2):

while pos < len(s1) and matches:

if alist1[pos]==alist2[pos]:

print(anagramSolution2('abcde','edcba'))

第一眼看上去，你可能認為程序的時間復雜度為O(n), 因為只有一個簡單的比較n個字母的循環. 然而, 兩次調用 Python sort 函數都沒有考慮開銷. 以后我們會介紹, 排序將花費的時間復雜度為 O(n2) 或 O(nlogn), 于是排序相比循環占主導地位.

一個 brute force 計數方法是枚舉出所有的可能性. 對于這個問題, 我們可以使用 s1 的字母簡單地生成所有的可能字符串并看 s2 是否出現. 然而,這種方法有一個難點. 我們列舉出s1的所有可能性,第一個字母有 n 種可能,第二個位置有n-1種可能, 第三個位置有n-2種可能,……. 總共的可能性為：n*(n-1)*(n-1)*3*2*1 = n!.已經證明 n!遞增非常快,當n非常大的時候, n! 遞增速度超過 2n .

最后一個解決方案是基于這樣的一個事實：任意兩個易位的字符串都有相同的'a'的數目,相同的'b'的數目,相同的'c'的數目……. 為了判斷兩個字符串是否易位,我們首先計算每一個字母的次數. 因為只有26個可能的字母, 我們可以使用一個list來保存26個計數, 每一個保存可能的字母. 每次當我們看到一個特別的字母，我們就增加對應的計數. 最后, 如果兩個list的對應計數完全相同, 兩個字符串就是易位的. 看下面的代碼：

def anagramSolution4(s1,s2):

for i in range(len(s1)):

for i in range(len(s2)):

while j<26 and stillOK:

if c1[j]==c2[j]:

print(anagramSolution4('apple','pleap'))

依然, 這種解決方案包含大量的循環. 然而, 與第一種方案不同, 它們都沒有被嵌入. 前兩個循環方案都在n的基礎上計算字母. 第三個方案的循環, 比較兩個字符串中counts的數目, 只需要 26 步 因為一個字符串只有26種可能的字母. 累加在一起我們得到 T(n)=2n+26 步. 即是 O(n). 我們找到了這個問題的線性時間解法.

離開這個例子之前，我們需要說的是空間開銷.雖然最后的解決方案能夠在線性時間內運行，它能成功必須要通過使用額外的存儲保持兩個列表中的字符數。換句話說，該算法使用了空間換時間.

這是一種常見的情況. 在許多場合，你需要做出決定的時間和空間之間的權衡。在目前的情況下，額外空間量是不顯著的。然而，如果下面的字母有數百萬字，就必須更多的關注空間開銷。作為一個計算機科學家，當在選定算法的時候，主要由你來決定如何利用計算機資源來解決一個特定的問題.

?8?數據結構算法思想總結

1、填空題。(每小題2分，本題滿分20分)

(1) C++語言中，數組是按行優先順序存儲的，假設定義了一個二維數組A[20][30]，每個元素占兩個字節，其起始地址為2140，則二維數組A的最后一個數據元素的地址為 2140+2*(30*20-1) = 3338(3338,3339) 。

(2) 若A，B是兩個單鏈表，鏈表長度分別為n和m，其元素值遞增有序，將A和B歸并成一個按元素值遞增有序的單鏈表，并要求輔助空間為O(1)，則實現該功能的算法的時間復雜度為 O(m+n) 。

(3) 快速排序的平均時間復雜度是______________。

(4) 假設有一個包含9個元素的最小堆，存放在數組A中，則一定比A[3]大的元素有個;一定比A[3]小的元素有個。(元素從第0個位置開始存放)

(5) 廣義表(((A)),(B,C), D, ((A), ((E,F)))) 的長度是，深度是。

(6) 有10個元素的有序表，采用折半查找，需要比較4次才可找到的元素個數為。 (7)當兩個棧共享一存儲區時，棧利用一維數組A[n]表示，兩棧頂指針為top[0]與top[1]，則棧滿時的判斷條件為___top[0]+1=top[1]_ 或者 top[0] = top[1]+1 ___。 (8) 假設計算斐波那契數的'函數Fib(long n)定義如下：

long Fib(long n){ if(n<=1) return n;

else return Fib(n-1)+Fib(n-2) }

計算Fib(5)時的遞歸調用樹(即指明函數調用關系的樹)的高度是___4 _____。假設葉子結點所在的高度為0。

(9) 完全二叉樹按照層次次序，自頂向下，同層從左到右順序從0開始編號時，編號為i的結點的左子結點的編號為___2*i+1______。

(10) 假設用子女—兄弟鏈表方式表示森林，對應的二叉樹的根結點是p，那么森林的第三棵樹的根結點在二叉樹中對應的結點是： ___p->rightchild->rightchild____________。假

2、選擇題。(每小題2分，本題滿分20分)

(1) 如果能夠在只知道指針p指向鏈表中任一結點，不知道頭指針的情況下，將結點*p從鏈

表中刪除，則這個鏈表結構應該是： ( B,C )(多選題) A. 單鏈表 B. 循環鏈表 C. 雙向鏈表 D. 帶頭結點的單鏈表 (2) 以下哪種矩陣壓縮存儲后會失去隨機存取的功能?( A )

A. 稀疏矩陣 B. 對稱矩陣 C. 對角矩陣 D. 上三角矩陣

(3) 下面哪一方法可以判斷出一個有向圖是否有環(回路)：( B ) (選A，B也對)

A. 廣度優先遍歷 B. 拓撲排序 C. 求最短路徑 D.求關鍵路徑 (4) n個結點的線索二叉樹(沒有頭結點)上含有的線索數為( B )

A. 2n B. n-l C. n+l D. n

(5) 循環隊列存儲在數組A[0..m]中，則入隊時隊尾指針rear的操作為( D )

A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)

(6) 使用加權規則得到改進的Union操作WeightedUnion，其目的是： ( B )

A. 提高Union操作的時間性能 B. 提高Find操作的時間性能 C. 減少Union操作的空間存儲 D. 減少Find操作的空間存儲

?9?數據結構算法思想總結

數據結構筆試題匯總

第一篇 筆試題目

Intel今年筆試題

●第一道是一個編譯器優化的題目，條件大致說在ZF為0或者不為0的情況下，分別有兩條移位指令可以移

進去。然后出了兩個小題，要你優化。

●第二道是N個人圍成一圈報數，報到某一個數的就出局，問你最后剩下來的那個人的'號碼。編程題。

●第三道大致如下：

以下礁齔絳蚰母齙performance高，并解釋為什么。

a)

extern int foo(void);

int main

{

int i;

for(i=0;i<10000;i++) foo();

return i;

}

b)

extern int foo(void);

int i;

int main()

{

for(i=0;i<10000;i++) foo();

return i;

}

●智力題

將如下圖形(邊長相等，即突出的都是正方形)割成幾塊，再拼成一個正方形，要求最少最少。

---

| |

--- ---

| |

--- ---

| |

---

● ee試卷考的是電磁場波導,拉式變化,電容器等內容

●下面的程序是否正確，如正確，給出結果，否則，說明理由。

#include

struct A{

int i;

char j;

char * ptr;

long Array[100];

char b[2];

char * c;

};

#define PRINT_ME (char *)&(((struct A *)0)->c)

void main()

{

printf(“%d”, PRINT_ME);

}

● Intel EE的IQ測試題

有10堆蘋果，每一堆10個

其中一堆每個240g

其它每堆都是250g/個

有一把稱

請你只稱一次把那一堆240的蘋果找出來

● Intel 的虛擬函數指針那道題

#include

class CBase

{

public:

virtual void foo()

{ cout<

}

virtual void bar()

{

cout<

}

};

class CChild : public CBase

{

public:

virtual void foo()

{ cout<

}

virtual void bar()

{

cout<

}

};

int * get(void);

void main()

{ int c;

void (CBase::* pVirtualPointer)(void);

CBase base;

CChild child;

pVirtualPointer = CBase::foo;

(base.*pVirtualPointer)();

(child.*pVirtualPointer)();

pVirtualPointer = CBase::bar;

(base.*pVirtualPointer)();

(child.*pVirtualPointer)();

cin>>c;

}

●補充一下

1、何時調用拷貝構造函數 (根據一個object創建另一個object,clone)

2、構造函數是否有返回類型

●述職報告之家YS575.cOm內容組內部知識競賽題庫:
• 黨員轉正思想匯報四篇2000?|?大學黨員轉正思想匯報四篇?|?數據核查方案?|?十二的歌詞?|?數據結構算法思想總結?|?數據結構算法思想總結

3、一個4word(word=4bytes)的cache，問以下程序段cache命中率

(a)for( int i=0; i

for(int j=0; j< N; j++)

sum+= a[i][j];

(b)for( int i=0; i

for(int j=0; j< N; j++)

sum+= a[j][i];

4、以下結構是否正確，why?

u8應該是無符號8位的意思吧

struct{

u8 a;

u16 b;

u8 c;

u8 d;

u16 e;

u8 f;

};

5、一個4×4矩陣，已知每列的和(缺第一列)和每行的和，問第一列的和，

6、用偽匯編代碼說明Switch語句的jump table的原理。

7、STDCALL的含義。(sigh,記反了，應該是從右到左調用)

● Intel今年在電子科技大學的筆試題

試題分CS和EE兩套，做EE題的同學必須做CS題(但其中關于編譯的題不用做)

EE的題目

1、電路設計時，什么情況下需要進行信號完整性分析?

2、用一個歐姆表怎么判斷出三極管的e、b、c極?

3、簡述Nyquist帶通采樣定理

4、你能想到的最大的影子是什么?

5、24個人要求排成6排，每排5人，如何排?

6、將1～9填入下圖所示的圓圈中，使3邊和相等，有多少種填法?

?10?數據結構算法思想總結

一、單選題(每題 2 分，共20分)

1. 棧和隊列的共同特點是( )。

A.只允許在端點處插入和刪除元素

B.都是先進后出

C.都是先進先出

D.沒有共同點

2. 用鏈接方式存儲的隊列，在進行插入運算時( ).

A. 僅修改頭指針 B. 頭、尾指針都要修改

C. 僅修改尾指針 D.頭、尾指針可能都要修改

3. 以下數據結構中哪一個是非線性結構?( )

A. 隊列 B. 棧 C. 線性表 D. 二叉樹

4. 設有一個二維數組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在

676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置?腳注(10)表示用10進制表示。

A.688 B.678 C.692 D.696

5. 樹最適合用來表示( )。

A.有序數據元素 B.無序數據元素

C.元素之間具有分支層次關系的數據 D.元素之間無聯系的數據

6. 二叉樹的第k層的結點數最多為( ).

kk-1 A.2-1 B.2K+1 C.2K-1 D. 2

7. 若有18個元素的有序表存放在一維數組A[19]中，第一個元素放A[1]中，現進行二

分查找，則查找A〔3〕的比較序列的下標依次為( )

A. 1，2，3 B. 9，5，2，3

C. 9，5，3 D. 9，4，2，3

8. 對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為

A. O(1) B. O(n) C. O(1og2n) D. O(n2)

9. 對于線性表(7，34，55，25，64，46，20，10)進行散列存儲時，若選用H(K)

=K %9作為散列函數，則散列地址為1的元素有( )個，

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

10. 設有6個結點的無向圖，該圖至少應有( )條邊才能確保是一個連通圖。

A.5 B.6 C.7 D.8

二、填空題(每空1分，共26分)

1. 通常從四個方面評價算法的質量：_________、_________、_________和_________。

2. 一個算法的時間復雜度為(n3+n2log2n+14n)/n2，其數量級表示為________。

3. 假定一棵樹的.廣義表表示為A(C，D(E，F，G)，H(I，J))，則樹中所含的結點數

為__________個，樹的深度為___________，樹的度為_________。

4. 后綴算式9 2 3 +- 10 2 / -的值為__________。中綴算式(3+4X)-2Y/3對應的后綴算式

為_______________________________。

5. 若用鏈表存儲一棵二叉樹時，每個結點除數據域外，還有指向左孩子和右孩子的兩個指

針。在這種存儲結構中，n個結點的二叉樹共有________個指針域，其中有________個指針域是存放了地址，有________________個指針是空指針。

6. 對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點

分別有_______個和________個。

7. AOV網是一種___________________的圖。

8. 在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有

向完全圖中，包含有________條邊。

9. 假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進行劃分，使得同一余數的元

素成為一個子表，則得到的四個子表分別為____________________________、___________________、_______________________和__________________________。

10. 向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度

___________。

11. 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為________，整個堆排序

過程的時間復雜度為________。

12. 在快速排序、堆排序、歸并排序中，_________排序是穩定的。

三、計算題(每題 6 分，共24分)

1. 在如下數組A中鏈接存儲了一個線性表，表頭指針為A [0].next，試寫出該線性表。

data next 2.

3. 已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7};

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。

4. 畫出向小根堆中加入數據4, 2, 5, 8, 3時，每加入一個數據后堆的變化。

四、閱讀算法(每題7分，共14分)

1. LinkList mynote(LinkList L)

{//L是不帶頭結點的單鏈表的頭指針

if(L&&L->next){

q=L;L=L->next;p=L;

S1： while(p->next) p=p->next;

S2： p->next=q;q->next=NULL;

}

return L;

}

請回答下列問題：

(1)說明語句S1的功能;

(2)說明語句組S2的功能;

(3)設鏈表表示的線性表為(a1,a2

, ?,an),寫出算法執行后的返回值所表示的線性表。

2. void ABC(BTNode * BT)

{

if BT {

ABC (BT->left);

ABC (BT->right);

cout

}

}

該算法的功能是：

五、算法填空(共8分)

二叉搜索樹的查找遞歸算法:

bool Find(BTreeNode* BST,ElemType& item)

{

if (BST==NULL)

return false; //查找失敗

else {

if (item==BST->data){

item=BST->data;//查找成功

return ___________;}

else if(itemdata)

return Find(______________,item); else return Find(_______________,item); }//if

}

六、編寫算法(共8分)

統計出單鏈表HL中結點的值等于給定值X的結點數。 int CountX(LNode* HL,ElemType x)

?11?數據結構算法思想總結

概述

本次實驗是針對數據結構課程的一項重要實踐活動。通過完成這個實驗，我們將深入了解和掌握各類數據結構的運作原理和實際應用。在實驗過程中，我們通過編寫代碼、構建數據結構和進行算法分析等方式，對數據的存儲、檢索和處理等操作進行了全面的探索和研究。

實驗內容

本次實驗主要涉及以下幾個方面的內容：

1. 數組

數組是最簡單和最常用的一種數據結構。我們實現了基本的數組初始化、賦值和讀取操作，還研究了各種不同類型的數組和多維數組的使用情況。通過這一部分的實驗，我們深入理解了數組在內存中的存儲和訪問機制。

2. 鏈表

鏈表是一種動態數據結構，它的靈活性和高效性使得它在很多場景下比數組更加適用。我們實現了單鏈表和雙鏈表，并比較了它們在插入和刪除操作上的效率差異。通過這部分實驗，我們深入了解了鏈表的結構和運作原理，以及如何通過指針來操作鏈表。

3. 棧和隊列

棧和隊列是兩種非常常見的數據結構，它們在很多算法和應用中都起到了關鍵作用。我們實現了基本的棧和隊列，并比較了它們在插入和刪除操作上的效率差異。通過這部分實驗，我們深入理解了棧和隊列的特性以及它們的應用場景。

4. 樹

樹是一種非常重要和復雜的數據結構，它在很多高級算法和數據處理中都起到了關鍵作用。我們實現了二叉樹和二叉搜索樹，并研究了它們的遍歷和搜索算法。通過這部分實驗，我們深入了解了樹的結構和運作原理，以及如何通過遞歸和迭代等方式來解決樹相關的問題。

實驗過程

在實驗過程中，我們首先通過理論學習來了解各種數據結構的概念和特性。然后，我們使用編程語言來實現這些數據結構，并編寫測試用例來驗證它們的正確性和性能。在編碼和調試過程中，我們遇到了很多問題，但通過團隊合作和老師的指導，最終成功解決了這些問題。

實驗結果

經過實驗，我們成功實現了各種數據結構，并通過多次測試驗證了它們的正確性和性能。我們還分別對數組、鏈表、棧和隊列、樹的各種操作進行了算法分析和性能測試。從實驗結果可以看出，不同的數據結構在不同的場景中具有不同的優勢和劣勢，我們可以根據實際需求選擇最適合的數據結構來提高程序的效率和性能。

實驗總結

通過本次實驗，我們對數據結構的概念和原理有了更加深入的理解，并學會了如何使用編程語言來實現和應用各種數據結構。實驗過程中，我們也鍛煉了問題分析和解決的能力，以及團隊合作和溝通的能力。這些都對我們今后的學習和工作具有重要意義。

通過本次數據結構實驗，我們不僅掌握了各種數據結構的運作原理和實際應用，還提高了我們的編程和算法設計能力。這將對我們今后的學習和工作產生積極影響。我們將繼續學習和深入研究數據結構，為未來的科學研究和技術創新做出貢獻。

?12?數據結構算法思想總結

關系表中的每一橫行稱為一個

A) 元組

B) 字段

C) 屬性

D) 碼

正確答案: A

在下列C語言程序中，可以用做變量名的是( B )。

A) 1

B) a1

C) int

D) *p

C語言提供的合法數據關鍵字是( A )。

A) float

B) Sagned

C) Integer

D) Char

以下符號中不能用作用戶標識符的符號是( B )。

A)_256 B)void

C)scanf D)Struct

若k為int型變量，則以下語句( C )。

k=8567;

printf(“|%-06d|\n”,k);

A)輸出格式描述不合法 B)輸出為|008567|

C)輸出為|8567| D)輸出為|-08567|

sizeof(float)是( B )。

A)一個雙精度表達式 B)一個整型表達式

C)一種函數調用 D)一個不合法的表達式

在C語言中, int、char和short三種類型數據在內存中所占用的字節數( D )。

A)由用戶自己定義 B)均為2個字節

C)是任意的 D)由所用機器的機器字長決定

判斷char型變量c1是否為小寫字母的正確表達式為 ( D )。

A) ‘a’<=c1<=’z’ B) (c1>=A. &&(c1<=’z')

C) (‘a’>=c1)||(‘z’<=c1) D) (c1>=’a')&&(c1<=’z')

以下敘述中正確的是( B )。

A.a是實型變量,C語言允許進行以下賦值a=10,因此可以這樣說：實型變量中允許存放整型值

B.在賦值表達式中,賦值號右邊即可以是變量也可以是任意表達式

C.執行表達式a=b后,在內存中a和b存儲單元中的原有值都將被改變,a的值已由原值改變為b的值,b的值由原值變為0

D.已有a=3,b=5當執行了表達式a=b,b=a之后,已使a中的值為5,b中的值為3

表達式18/4*sqrt (4.0)/8值的數據類型為( C )。

A)int B)float C)double D)不確定

推薦閱讀: 排序算法思想總結(收藏十四篇) 數據產品經理述職報告（精品四篇） 數據更正申請書（精品16篇） 大學生的思想總結（精品十二篇） 共青團團員年度思想總結（精品十二篇）

更多精彩數據結構算法思想總結內容，請訪問我們為您準備的專題：數據結構算法思想總結

熱門標簽: 算法崗自我評價 完美的結構作文 花卉結構化 數據述職報告 述職報告數據 十二月份總結