【渝粤教育】国家开放大学2018年秋季 0008-22T简明现代汉语 参考试题
編號：0025 座位號：
18-19學年第1學期期末考試
數(shù)據(jù)結(jié)構(gòu) 試題（開卷）
一、選擇題：（每題4分，共20分）
1．以下（ ）不是隊列的基本運算。
A．從隊尾插入一個新元素
B．判斷一個隊列是否為空
C．從隊列中刪除第i個元素
D．讀取隊首元素的值
2．假定一個順序隊列的隊首和隊尾指針分別為front和rear，存放該隊列的數(shù)組長度為N，則判斷隊空的條件為( )。
A．（front+1）% N == rear
B．（rear+1）% N == front
C． front == 0
D． front == rear
3．棧的插入和刪除操作在＿＿＿進行．
Ａ．棧頂 Ｂ．棧底
Ｃ．任意位置 Ｄ．指定位置
4．在一棵高度為４的二叉樹，最多含有＿＿個結(jié)點。
A．8 B．12
C．16 D．15
5．根據(jù)下列二叉樹遍歷的結(jié)果為C,D,B,G,F,E,A，則此遍歷為＿＿。
A A．前序
B E B．中序
C D F C．后序
G D．層次
二、填空題：（每空１分，共２０分）
1．在線性結(jié)構(gòu)，樹結(jié)構(gòu)和圖結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點分別存在著________、 ________和________的聯(lián)系。
2．在循環(huán)雙向鏈表中表頭結(jié)點的左指針域指向________結(jié)點，表尾結(jié)點的右指針域指向________結(jié)點。
3．對于一棵具有n個結(jié)點的二叉樹，若一個結(jié)點的編號為i（1≤i≤n），則它的左孩子結(jié)點的編號為_______，右孩子結(jié)點的編號為_______。
4．假定一棵樹的廣義表表示為Ａ（Ｂ（Ｃ，Ｄ（Ｅ，Ｆ，Ｇ），Ｈ（Ｉ，Ｊ））），則度為３,２,１,０的結(jié)點數(shù)分別為______、______、______和______個。
5．在一棵二叉排序樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定_____該結(jié)點的值，右子樹上所有結(jié)點的值一定_____該結(jié)點的值。
一個具有4個頂點的無向完全圖中，包含有_______條邊，在一個具有n個頂點的有向完全圖中，包含有_______條邊。
7．在一棵高度為5的理想平衡樹中，最少含有_______個結(jié)點，最多含有_______個結(jié)點。
8．對于一個具有n個頂點和e條邊的有向圖和無向圖，若采用邊集數(shù)組表示，則存于數(shù)組中的邊數(shù)分別為________和________。
9．假定一組記錄的排序碼為（４６,７９,５６,３８,４０,８４），則利用堆排序方法建立的初始堆為___________________________________。
三、問答題：（共30分）
已知一個圖的頂點集V和邊集G分別為：
V={0，1，2，3，4，5，6，7}
E={(0,1)8, (0,2)5, (0,3)2, (1,5)6, (2,3)25, (2,4)13, (3,5)9, (3,6)10, (4,6)4, (5,7)20}
按照克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。（10分）
２．已知一個后綴算術(shù)表達式為：6 3 20 5／＊8－6＊＋＠ （10分）
(1) 寫出對應的中綴算術(shù)表達式
(2) 畫出在進行后綴表達式求值的過程中數(shù)值棧的變化
３．已知一組元素的排序碼為（36，25，48，12，65，20），用直接插入排序法每次向前面有序表插入一個元素后的排列結(jié)果。（10分）
四、算法填空，在畫有橫線的地方填寫合適的內(nèi)容
（共10分）
求二叉樹深度的遞歸算法如下：
int BTreeDepths(BtreeNode* BT)
{
if(BT==NULL)
return;
else
{
int dep1=_____________________;（4分）
int dep1=BtreeDepth(BT->right);
if (dep1>dep2)
return __________; （3分）
else
return __________; （3分）
}
}
五、閱讀算法，寫出執(zhí)行后的結(jié)果（10分）
Queue Q;
InitQueue(Q);
int a[4]={5,8,12,15};
for(int i=0;i<4;i++) QInsert(Q,a[i]);
QInsert(Q,Qdelete(Q));
QInsert(Q,30);
QInsert(Q,Qdelete(Q)+10);
while(!QueueEmpty(Q)) cout<<QDelete(Q)<<’’;
結(jié)果為：_________________________________。
六、編寫算法（１０分）
已知一棵具有n個結(jié)點的完全二叉樹被順序存儲于一維數(shù)組的Ａ[1]～Ａ[n]元素中，試編寫一個算法打印編號為i的結(jié)點的雙親和孩子．
Void Request(int A[],int n,int i)
總結(jié)
以上是生活随笔為你收集整理的【渝粤教育】国家开放大学2018年秋季 0008-22T简明现代汉语 参考试题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： iOS16.0.2值得升级吗iOS16.
- 下一篇： 【渝粤教育】国家开放大学2018年秋季