數據結構演算法題目

1. 數據結構與演算法選擇題！

第一題，DFS（深度優先遍歷）是一個遞歸演算法，在遍歷的過程中，先訪問的點被壓入棧底（棧是先進後出），再說：拓撲有序是指如果點U到點V有一條弧，則在拓撲序列中U一定在V之前。深度優先演算法搜索路徑恰恰是一條弧，棧的輸出是從最後一個被訪問點開始輸出，最後一個輸出的點是第一個被訪問的點。所以是逆的拓撲有序序列
第二題：無向圖路徑長度是指兩個頂點之間弧的條數，如果兩頂點路徑長度有2條弧，則有3個頂點例如A——B——C；
第三題：A：極小連通圖是一棵生成樹，只有N-1條邊，但是連通分量可能有N條邊，例如極小連通圖A—— B——C，連通分量「A」——B——C——「A」(這里的最後一個「A」跟第一個「A」一致）：；
B:你查下極大強連通子圖概念就明白了；
C:你看看第二題的例子就明白了，AC之間沒有弧，但他們是一個拓撲序列；
D：例如：環形圖就不滿足，比如長方形，四個頂點，兩種遍歷都能訪問到每個頂點，但不是完全圖

2. 數據結構:設計一個高效演算法，將順序表中的所有元素逆置，要求演算法空間復雜度為O(1)。

設計一個高效演算法，將順序表中的所有元素逆置，要求演算法空間復雜度為O(1)掃描順序表L的前半部分元素L.data[i] (0<=i<L.length/2)，將其與後半部分的對應元素L.data[L.length-1-i]進行交換即可。

順序表的存儲只要確定了起始位置，表中任一元素的地址都通過下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L是元素佔用存儲單元的長度。

(2)數據結構演算法題目擴展閱讀：

數據的物理結構是數據結構在計算機中的表示，它包括數據元素的機內表示和關系的機內表示。由於具體實現的方法有順序、鏈接、索引、散列等多種。

數據元素的機內用二進制位（bit）的位串表示數據元素。當數據元素有若干個數據項組成時，位串中與各個數據項對應的子位串稱為數據域（data field）。

3. 數據結構與演算法題需要回答

《數據結構與演算法》模擬題
一、填空題：（共15分）（每空一分）
按照排序時，存放數據的設備，排序可分為<1> 排序和<2> 排序。內部排序和外部排序
圖的常用的兩種存儲結構是<3> 和<4> 。鄰接矩陣和鄰接表
數據結構中的三種基本的結構形式是<5> 線性結構 和<6> 樹型結構 、圖型結構<7> 。
一個高度為6的二元樹，最多有<8> 63 個結點。
線性查找的時間復雜度為：<9> O(n^2) ，折半查找的時間復雜度為：<10> O(nlogn) 、堆分類的時間復雜度為：<11> O(nlogn) 。
在採用散列法進行查找時，為了減少沖突的機會，散列函數必須具有較好的隨機性，在我們介紹的幾種散列函數構造法中，隨機性最好的是<12> 隨機數 法、最簡單的構造方法是除留余數法<13> 。
線性表的三種存儲結構是：數組、<14> 鏈表 、<15> 靜態鏈表 。
二、回答下列問題：（共30分）
現有如右圖的樹，回答如下問題：看不見圖
根結點有：
葉結點有：
具有最大度的結點：
結點的祖先是：
結點的後代是：
棧存放在數組A[m]中，棧底位置是m-1。試問：
棧空的條件是什麼？top=m-1
棧滿的條件是什麼？top=-1
數據結構和抽象數據型的區別與聯系：
數據結構（data structure)—是相互之間存在一種或多種特定關系的數據元素的集合。數據元素相互之間的關系稱為結構。
抽象數據類型（ADT）：是指一個數學模型（數據結構）以及定義在該模型（數據結構）上的一組操作。