8.設無向圖的頂點個數為n,則該圖最多有( )條邊。
a. n-1 b. n(n-1)/2 c.n(n+1)/2 d. 0
9. 在乙個長度為n的線性表中順序查詢值為x的元素時,在等概率的情況下查詢成功時的平均查詢長度為
a. n b. n/2 c. (n+1)/2 d. (n-1)/2
10.深度為5的二叉樹至多有個結點。
a.16b.32c.31d.10
11. 堆的形狀是一棵
a. 二叉排序樹 b.滿二叉樹 c. 完全二叉樹 d. 平衡二叉樹
12.下列關於資料結構的敘述中,正確的是
a. 陣列是同型別值的集合
b. 樹是一種線性結構
c. 遞迴演算法的程式結構比迭代演算法的程式結構更為精煉
d. 用一維陣列儲存二叉樹,總是以先序遍歷的順序儲存各結點
13. 在具有 n(n>1) 個結點的完全二叉樹中,結點 i(2*i>n) 的左孩子結點是
a. 2*i b. 2*i+1 c. 不存在 d. 2*i-1
14. 在有n個結點的二叉樹中,值為非空的鏈域的個數為()。
a.n-1b.2*n-1 c.n+1 d.2*n+1
15. 若對乙個已排好序的序列進行排序,在下列四種方法中,哪種比較好( )。
a. 冒泡法 b. 直接選擇法 c. 直接插入法 d. 歸併法
16. 設單鏈表中指標p指向結點a,若a的後繼結點存在,則刪除該後繼結點需要修改指標的操作為( )。
a.p->next=p->next->next b.p=p->next
c.p=p->next->nextd.p->next=p
17. 佇列操作的原則是( )。
a. 先進先出 b. 後進先出 c. 只能進行插入 d. 只能進行刪除
18. 對樹進行層次遍歷時,通常是採用( )作為輔助來實現演算法的。
a.棧 b. 佇列 c. 樹 d. 圖
19是順序儲存方式的優點。
a. 儲存密度大 b. 插入運算方便
c. 刪除運算方便 d. 可方便地用於各種邏輯結構的儲存表示
20. 陣列a[5][6]的每個元素佔5個單元,將其按行優先次序儲存在起始位址為1000的連續的記憶體單元中,則元素a[5,5]的位址為( )。
a.1140 b.1145 c.1120 d.1125
二、判斷題(每題1分,共10分)。
以下各種說法,你認為對的在前面括號打√,錯誤的打×。
()1.佇列只能採用鏈式儲存方式。
()2.二叉樹的度一定是2。
()3.線性結構也是一種樹結構。
()4.有向圖用鄰接表表示後,頂點i的入度等於該頂點對應的單鏈表的元素個數。
()5.滿二叉樹一定有偶數個結點。
()6.直接插入排序的關鍵碼比較次數與初始排列有關。
()7.順序儲存方式只能用於儲存線性結構。
( )8. 給出不同的輸入序列建造二叉排序樹,一定得到不同的二叉排序樹。
()9.在對鏈佇列作出隊操作時,不會改變front指標的值。
( )10. 堆排序是不穩定排序。
三、填空題(每空2分,共18分)。
1.中綴算式(3+4)*2 /(8-5)所對應的字尾算式為
2. 某演算法的時間複雜度為(5*n2+1000*n*log2n+4*n-8)/(10*n),其數量級表示為
3. 用1000個結點構造的二叉樹,最少層,最多層。
4. 假定乙個線性表為(12,23,74,55,63,40,82,36),若按key % 3條件進行劃分,使得同一餘數的元素成為乙個子表,則得到的三個子表分別為和
5. 假定一棵二叉樹廣義表表示為a(b(c),d(e,f)),其中序遍歷序列為層次遍歷序列為
四、程式填空題(每個語句2分,共12分)
1.下面是向以bst為樹根指標的二叉搜尋樹上插入值為item的結點的遞迴演算法。請將缺失語句填上。
2.下面是向單鏈表的末尾新增乙個元素的演算法。請將缺失的語句填上。
void insertrear( lnode*& hl, const elemtype& item )
newptr->data = item;
if ( hl == null ) hl = newptr;
else
}五、演算法設計題(20分)
1.編寫演算法函式,把順序表list原地置逆。(10分)
順序表的資料結構如下:
typedef struct seqlist;
函式原形為:void fnreverse( seqlist &list );
2.二叉樹採用左右孩子指標儲存結構:
struct treenode;
請編寫乙個遞迴函式,要在一棵樹t中,找出值是x的結點的兄弟結點。(10分)
函式原形如下:
struct treenode *fngetbrother( struct treenode *t, int x );
韓山師範學院優秀教材評獎辦法
第一章總則 第一條 教材建設是高等學校的一項重要教學基本建設。為了鼓勵教師及科技人員編寫教材的積極性,促進我院的教材建設,確保教學質量的提高和科學技術的發展,特制定本條例。第二條 本條例中所指教材系由本院教師在職期間獨立編寫或者作為主編 副主編編寫,並由出版社正式出版的教材 包括基本教材 教學參考書...
正溴丁烷的製備韓山師範學院
一 實驗目的 1 了解由醇製備溴代烴的原理合成方法。2 初步掌握回流及其氣體吸收裝置和分液漏斗的使用。二 實驗原理 主反應式 nabr h 2so 4hbr nahso 4n c 4h 9oh hbr h 2so 4 n c 4h 9br h 2o 可能的副反應 ch 3ch 2ch 2ch 2oh...
韓山師範學院學生社會實踐調研報告
系別物理與電子工 程係調研題目 調查的物件範圍調查的時間地點 班級20121231 姓名姚家捷 學號2012123105 指導教師 評分 大埕小學三下鄉 暑假社會實踐報告 小學生暑假期間潮州市大埕小學 一段路,一段旅程,一段再也放不下的回憶。第一次三下鄉,總覺得每天都是一次驚心動魄的冒險,每一天都充...