山大網(wǎng)絡(luò)教育《數(shù)據(jù)結(jié)構(gòu)》(-C-卷)

《數(shù)據(jù)結(jié)構(gòu)》模擬卷一、單項(xiàng)選擇題1．?dāng)?shù)據(jù)結(jié)構(gòu)是（）。A．一種數(shù)據(jù)類型B．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C．一組性質(zhì)相同的數(shù)據(jù)元素的集合D．相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2．算法分析的目的是（B）。A．辨別數(shù)據(jù)結(jié)構(gòu)的合理性B．評(píng)價(jià)算法的效率C．研究算法中輸入與輸出的關(guān)系D．鑒別算法的可讀性3．在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（D）。A．插入 B．刪除C．排序 D．定位4．若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為（B）。A．3，2，6，1，4，5 B．3，4，2，1，6，5C．1，2，5，3，4，6 D．5，6，4，2，3，15．設(shè)串sl=″DataStructureswithJava″,s2=″it″，則子串定位函數(shù)index(s1,s2)的值為（D）。A．15 B．16C．17 D．186．二維數(shù)組A[8][9]按行優(yōu)先順序存儲(chǔ)，若數(shù)組元素A[2][3]的存儲(chǔ)地址為1087，A[4][7]的存儲(chǔ)地址為1153，則數(shù)組元素A[6][7]的存儲(chǔ)地址為（A）。A．1207 B．1209C．1211 D．12137．在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（A）。A．隊(duì)列 B．棧C．線性表 D．有序表8．在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對(duì)次序關(guān)系（B）。A．不一定相同 B．都相同C．都不相同 D．互為逆序9．若采用孩子兄弟鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的（C）。A．層次遍歷算法 B．前序遍歷算法C．中序遍歷算法 D．后序遍歷算法10．若用鄰接矩陣表示一個(gè)有向圖，則其中每一列包含的″1″的個(gè)數(shù)為（A）。A．圖中每個(gè)頂點(diǎn)的入度 B．圖中每個(gè)頂點(diǎn)的出度C．圖中弧的條數(shù) D．圖中連通分量的數(shù)目11．圖的鄰接矩陣表示法適用于表示（C）。A．無(wú)向圖 B．有向圖C．稠密圖 D．稀疏圖12．在對(duì)n個(gè)關(guān)鍵字進(jìn)行直接選擇排序的過(guò)程中，每一趟都要從無(wú)序區(qū)選出最小關(guān)鍵字元素，則在進(jìn)行第i趟排序之前，無(wú)序區(qū)中關(guān)鍵字元素的個(gè)數(shù)為（D）。A．i B．i+1C．n-i D．n-i+1二、填空題1．棧是_操作受限___的線性表，其運(yùn)算遵循_后進(jìn)先出__的原則。2．__棧_是限定僅在表尾進(jìn)行插入或刪除操作的線性表。3.一個(gè)棧的輸入序列是：1，2，3則不可能的棧輸出序列是_312__。4．二叉樹由_(1)根節(jié)點(diǎn)__，__(2)左子樹_，_(3)右子樹__三個(gè)基本單元組成。5．在二叉樹中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是__p->lchild==null&&p->rchild==null____。6．具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為__9____。7．已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹有___10___個(gè)葉子結(jié)點(diǎn)。8．若不考慮基數(shù)排序，則在排序過(guò)程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的__比較____和記錄的__移動(dòng)___。}//結(jié)束ThrTreeInsert2．答案：[題目分析]在后序序列中，若結(jié)點(diǎn)p有右子女，則右子女是其前驅(qū)，若無(wú)右子女而有左子女，則左子女是其前驅(qū)。若結(jié)點(diǎn)p左右子女均無(wú)，設(shè)其中序左線索指向某祖先結(jié)點(diǎn)f（p是f右子樹中按中序遍歷的第一個(gè)結(jié)點(diǎn)），若f有左子女，則其左子女是結(jié)點(diǎn)p在后序下的前驅(qū)；若f無(wú)左子女，則順其前驅(qū)找雙親的雙親，一直繼續(xù)到雙親有左子女（這時(shí)左子女是p的前驅(qū)）。還有一種情況，若p是中序遍歷的第一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)p在中序和后序下均無(wú)前驅(qū)。BiThrTreeInPostPre(BiThrTreet,p)//在中序線索二叉樹t中，求指定結(jié)點(diǎn)p在后序下的前驅(qū)結(jié)點(diǎn)q{BiThrTreeq;if(p->rtag==0)q=p->rchild;//若p有右子女，則右子女是其后序前驅(qū)elseif(p->ltag==0)q=p->lchild;//若p無(wú)右子女而有左子女，左子女是其后序前驅(qū)。elseif(p->lchild==null)q=null;//p是中序序列第一結(jié)點(diǎn)，無(wú)后序前驅(qū)else//順左線索向上找p的祖先，若存在，再找祖先的左子女{while(p->ltag==1&&p->lchild!=null)p=p->lchild;if(p->ltag==0)q=p->lchild;