全國年月高等教育自學考試
數據結構導論試題
課程代碼
一單項選擇題(本大題共小題每小題分共分)
在每小題列出的四個備選項中只有一個是符合題目要求的請將其代碼填寫在題後的括號內錯選多選或未選均無分
數據的基本單位是（ ）
A數據項 B數據類型
C數據元素 D數據變量
下列程序的時間復雜度為（ ）
i=s=
while（s<n）
{ i++
s=s+i
}
AO（ ） BO（ ）
CO（n） DO（n）
若某線性表中最常用的操作是在最後一個元素之後插入一個元素和刪除第一個元素則最節省運算時間的存儲方式是（ ）
A單鏈表 B僅有頭指針的單循環鏈表
C雙鏈表 D僅有尾指針的單循環鏈表
從一個長度為n的順序表中刪除第i個元素（≤i≤n）時需向前移動的元素的個數是（ ）
Ani Bni+
Cni Di
順序棧S中top為棧頂指針指向棧頂元素所在的位置elem為存放棧的數組則元素e進棧操作的主要語句為（ ）
Aselem［top］=e Bselem［top+］=e
stop=stop+ stop=stop+
Cstop=stop+ Dstop=stop+
selem［top+］=e selem［top］=e
循環隊列sq中用數組elem［&#;&#;］存放數據元素sqfront指示隊頭元素的前一個位置sqrear指示隊尾元素的當前位置設當前sqfront為sqrear為則當前隊列中的元素個數為（ ）
A B
C D
設有一個階的對稱矩陣A采用壓縮存儲方式以行序為主序存儲a為第一個元素其存儲地址為每個元素占有個存儲地址空間則a的地址為（ ）
A B
C D
含有個結點的二叉樹中度為的結點數為則度為的結點數為（ ）
A B
C D
對一棵有個結點的完全二叉樹按層編號則編號為的結點它的父結點的編號為（ ）
A B
C D
可以惟一地轉化成一棵一般樹的二叉樹的特點是（ ）
A根結點無左孩子 B根結點無右孩子
C根結點有兩個孩子 D根結點沒有孩子
有n個結點的有向完全圖的弧數是（ ）
An Bn
Cn(n) Dn(n+)
設圖的鄰接鏈表如題圖所示則該圖的邊的數目是（ ）
A B
C D
已知一個有序表為（）當二分檢索值為的元素時檢索成功需比較的次數是（ ）
A B
C D
排序算法中第一趟排序後任一元素都不能確定其最終位置的算法是（ ）
A選擇排序 B快速排序
C冒泡排序 D插入排序
排序算法中不穩定的排序是（ ）
A直接插入排序 B冒泡排序
C堆排序 D歸並排序
二填空題(本大題共小題每小題分共分)
請在每小題的空格中填上正確答案錯填不填均無分
在數據結構中數據的邏輯結構分為集合________樹形結構和圖狀結構等四類
通常從正確性易讀性________和高效率等個方面評價算法（包括程序）的質量
順序表的存儲密度為________而鏈表的存儲密度為________
對於棧只能在________插入和刪除元素
在循環隊列中存儲空間為～n設隊頭指針front指向隊頭元素前一個空閒元素隊尾指針指向隊尾元素那麼隊滿標志為front=(rear+)%n隊空標志為________
三個結點可構成________種不同形態的二叉樹
對於一棵具有n個結點的二叉樹當進行鏈接存儲時其二叉鏈表中的指針域的總數為n個其中________個用於鏈接孩子結點
有向圖G用鄰接矩陣A［&#;&#;n&#;&#;n］存儲其第i列的所有元素之和等於頂點Vi的________
對二叉排序樹進行________遍歷可得到排好序的遞增結點序列
采用折半查找方法進行查找的數據序列應為________且________
索引文件只能是________因為索引文件的組織方式是為隨機存取而設計的
在插入和選擇排序中若初始數據基本正序則選用________若初始數據基本反序則選用________
快速排序最好情況下的時間復雜度為________最壞情況下的時間復雜度為________<
From:http://tw.wingwit.com/Article/program/sjjg/201311/23587.html
