南京曉莊學院數據結構題庫參考標準答案

數據結構與算法 習題冊 (課后部分參考答案) 《數據結構與算法》課程組 目錄 課后習題部分 第一章 緒論1 第二章 線性表3 第三章 棧和隊列5 第四章 串8 第五章 數組和廣義表10 第六章 樹和二叉樹13 第七章 圖16 第九章 查找20 第十章 排序23 第一章 緒論 一. 填空題 1. 從邏輯關系上講，數據結構的類型主要分為 集合 、線性結構、樹結構和 圖結構。 2. 數據的存儲結構主要有 順序存儲和 鏈式存儲 兩種基本方法，不論哪種存儲結構，都要存儲兩方面的內容：數據元素 和 數據元素之間的關系 。 3. 算法具有五個特性，分別是 有窮性 、 確定性、可行性、 輸入 、 輸出 。 4. 算法設計要求中的健壯性指的是 算法在發生非法操作時可以作出處理的特性。 二. 選擇題 1. 順序存儲結構中數據元素之間的邏輯關系是由 C 表示的，鏈接存儲結構中的數據元素之間的邏輯關系是由 D 表示的。 A 線性結構 B 非線性結構 C 存儲位置 D 指針 2. 假設有如下遺產繼承規則：丈夫和妻子可以相互繼承遺產；子女可以繼承父親或母親的遺產；子女間不能相互繼承。則表示該遺產繼承關系的最合適的數據結構應該是 B 。 A 樹 B 圖 C 線性表 D 集合 3. 算法指的是 A 。 A 對特定問題求解步驟的一種描述，是指令的有限序列。 B 計算機程序 C 解決問題的計算方法 D 數據處理 三. 簡答題 1. 分析以下各程序段，并用大O記號表示其執行時間。 (1) (2) i=1;k=0;i=1;k=0; While(inext; rear->next =s; rear =s;；刪除開始結點的操作順序為q=rear->next->next; rear->next->next=q->next; delete q; 。 二. 選擇題 1.數據在計算機存儲器內表示時物理地址與邏輯地址相同并且是連續的，稱之為： C A存儲結構 B邏輯結構 C順序存儲結構 D鏈式存儲結構 2. 在n個結點的順序表中，算法的時間復雜度是O(1)的操作是： A A 訪問第i個結點(1≤i≤n)和求第i個結點的直接前驅(2≤i≤n) B 在第i個結點后插入一個新結點(1≤i≤n) C 刪除第i個結點(1≤i≤n) D 將n個結點從小到大排序 3. 線性表L在 B 情況下適用于使用鏈式結構實現。 A 需經常修改L中的結點值 B 需不斷對L進行刪除插入 C L中含有大量的結點 D L中結點結構復雜 4. 單鏈表的存儲密度 C A大于1 B等于1 C小于1 D不能確定 三. 判斷題 1. 線性表的邏輯順序和存儲順序總是一致的。 F 2. 線性表的順序存儲結構優于鏈接存儲結構。 F 3. 設p，q是指針，若p=q，則*p=*q。 F 4. 線性結構的基本特征是：每個元素有且僅有一個直接前驅和一個直接后繼。 F 四. 簡答題 1. 分析下列情況下，采用何種存儲結構更好些。 (1)若線性表的總長度基本穩定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素。 (2)如果n個線性表同時并存，并且在處理過程中各表的長度會動態發生變化。 (3)描述一個城市的設計和規劃。 ⑴ 應選用順序存儲結構。很少進行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應選用順序存儲結構。 ⑵ 應選用鏈式存儲結構。鏈表容易實現表容量的擴充，適合表的長度動態發生變化。 ⑶ 應選用鏈式存儲結構。因為一個城市的設計和規劃涉及活動很多，需要經常修改、擴充和刪除各種信息，才能適應不斷發展的需要。而順序表的插入、刪除的效率低，故不合適。 五. 算法設計 1. 已知數組A[n]中的元素為整型，設計算法將其調整為左右兩部分，左邊所有元素為奇數，右邊所有元素為偶數，并要求算法的時間復雜度為O(n)。 2. 線性表存放在整型數組A[arrsize]的前elenum 個單元中，且遞增有序。編寫算法，將元素x插入到線性表的適當位置上，以保持線性表的有序性，并且分析算法的時間復雜度。 int insert (datatype A[],int *elenum,datatype x) /*設elenum為表的最大下標*/ {if (*elenum==arrsize-1) return 0; /*表已滿，無法插入*/ else {i=*elenum; while (i>=0 i--; } A

總結

以上是生活随笔為你收集整理的南京晓庄学院大一第二学期计算机数据结构期末考试试卷及答案,南京晓庄学院数据结构题库参考标准答案...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。