02331數(shù)據(jù)結構章節(jié)練習(2020.06.02)

來源：考試資料網(wǎng)

1.填空題表示圖的三種存儲結構為（）、（）和（）。

參考答案：鄰接矩陣；鄰接表；邊集數(shù)組

2.問答題假設表達式有單字母變量和雙目四則運算符構成。試寫一個算法，對以逆波蘭式表示的表達式求值。

3.問答題什么叫動態(tài)查找？什么叫靜態(tài)查找？什么樣的存儲結構適宜于進行靜態(tài)查找？什么樣的存儲結構適宜于進行動態(tài)查找？

參考答案：靜態(tài)查找是指只在數(shù)據(jù)元素集合中查找是否存在關鍵字等于某個給定關鍵字的數(shù)據(jù)元素。動態(tài)查找除包括靜態(tài)查找的要求外，還包括在查...

4.填空題長度為12的有序表采用順序存儲結構，采用折半查找技術，在等概率情況下，查找成功時的平均查找長度是（），查找失敗時的平均查找長度是（）。

參考答案：37/12；62/13

5.問答題 一個帶頭結點的單鏈表如下。

head為頭指針，每個結點按data字段值遞增順序鏈接，r指向一個新結點，下面是將r所指的新結點插入鏈表中的算法，插入后結點仍按data字段值遞增順序鏈接。請補充下圖中劃線空白部分。

6 隊列的應用包含選項中的哪些（）

7.填空題對于一個圖G，若邊集合E（G）為無向邊的集合，則稱該圖為（）。

8.問答題假設二叉樹b采用二叉鏈存儲結構，設計一個算法void findparent（BTNode *b，ElemType x，BTNode *&p）求指定值為x的結點的雙親結點p，提示，根結點的雙親為NULL，若未找到這樣的結點，p亦為NULL。

9 對一棵有100個結點的完全二叉樹按層編號，則編號為49的結點，它的左孩子的編號為（）。

10.判斷題順序存儲結構和鏈式存儲結構是邏輯結構，即元素與元素之間的邏輯關系。