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