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 );
2019韓山師範學院專插本《資料結構》樣卷
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.16...
2023年肇慶學院專插本考試大綱資料結構
2013年肇慶學院本科插班生考試大綱 資料結構 考試性質 普通高等學校本科插班生 又稱專插本 招生考試是由專科畢業生參加的選拔性考試。高等學校根據考生的成績,按照已確定的招生計畫,德 智 體全面衡量,擇優錄取。因此,本科插班生考試應有較高信度 效度 必要的區分度和適當的難度。考試內容及要求 一 考試...
資料結構練習卷
華北科技學院 一 選擇題 每題2 分,共 10 題,總計 20 分 1 下列資料中是非線性資料結構。a 棧 b.佇列 c.完全二叉樹 d.陣列 2 乙個棧的輸入序列為123 n,若輸出序列的第乙個元素是n,輸出第i 1 i n 個元素是 a.不確定b.n i 1c.id.n i 3 下面關於線性表的...