【正文】 ____和__________等兩種物理結構。正確的打√，錯誤的打X)1．如果某數據結構的每一個元素都最多只有一個直接前驅，則必為線性表。模擬試題8一、選擇題(每小題1分，共8分)1．設一數列的順序為1，2，3，4，5，通過棧結構不可能排成的順序數列為( ) (A)3，2，5，4，1 (B)1，5，4，2，3 (C)2，4，3，5，1 (D)4，5，3，2，12．二叉樹的第3層最少有( )個結點。 Struct LinkNode *lchild。 }3．已知一個單鏈表的表首指針為h，每個結點含元素值data和下一結點的地址next。 kalength。插入成功返回1，否則返回0。 /* 隊首元素的下標 */ int rear。(5分)4．已知下圖是一個無向團。5．一個1010的三角矩陣a采用列優(yōu)先壓縮存儲后，如果首元素a[0][0]是第1個元素，那么a[4][2]是第______________個元素。（ ）5．二叉排序樹中，任一結點的值都大于或等于其孩子的值。 (A)40 (B)19 (C)20 (D)2l5．在具有N個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾指針，則判斷隊滿的條件為( )。(8分)2．已知二叉樹結點數據結構如下，編寫算法，在一棵二叉樹中查找值為x的葉子結點，若找到返回該結點的指針，找不到則返回空指針。 for(i=0。Node *sm(Node *T){Node *p。_______________=e。(5分)4．已知有序表(4，11，13，19，26，28，33，39，42)，采用折半查找。( )8．一個圖可以沒有邊，但不能沒有頂點。8．設有1000個元素，用折半法查找時，最大比較次數是_____________。 (A)5 (B)10 (C)15 (D)207．一個無向連通圖有5個頂點8條邊，則其生成樹將要去掉( )條邊。3．在含有n個元素的堆中增加一個元素，且調整為堆。②若對表中元素先排序構成有序表，試求在等概率情況下對此有序表進行折半查找成功的平均查找長度。( )4．若有一個葉子結點是某子樹的中序遍歷的最后一個結點，則它必須是該子樹的先序遍歷的最后一個結點。 2．計算機軟件系統(tǒng)中有兩種處理字符串長度的方法，一種是采用_____________另一種是采用_________。 6．串的長度是( )。 (C) pnext=s。 (A) pnext=s。jt。(10分)模擬試題5一、選擇題(30分)1．下列程序的時間復雜度為( )for(i=0。8．高度為h(≥0)的二叉樹，至少有__________個結點，最多有________個結點。f一＞next＝p一＞next。( )4．一棵滿二叉樹同時又是一棵平衡樹。 (A)O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2) 7．采用鏈結構存儲線性表時，其地址( )。 (A)先序 (B)中序 (C)后序 (D)按層次5．在下列4棵樹中，哪一棵是完全二叉樹( )。( )4．有向圖的鄰接矩陣的第i行的所有元素之和等于第i列的所有元素之和。 3．給定有序表D＝{15，17，18，22，35，60，88，93}，用折半查找法在D中查找18，試用圖示法表示查找過程。j) if(R[j]R[j1]){ temp=R[j1]。7．有向圖G用鄰接矩陣A[1…m，1…m ]存儲，其第i行的所有元素值之和等于頂點vi的__________________。 （A） （B） （C） （D）7．對下圖v4的度為( )。( )6．用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間與圖中結點的個數有關，而與圖的邊數無關。四、算法設計(30分)1．某百貨公司倉庫中有一批電視機，按其價格從低到高的次序構成一個單鏈表存于計算機中，鏈表的每個結點指出同樣價格的若干臺，現在又新到m臺價格為n元的電視機入庫，試編寫倉庫電視機鏈表增加電視機的算法。8．下列算法實現二叉樹排序樹上的查找，請在空格處填上適當的語句，完成上述功能。 (A)n(n一1)／2 (D)n(n—1) (C)n2 (D) n2 19．設有100個元素，用折半查找時，最大比較次數為( )，最小比較次數為（ ）。( )模擬試題2一、選擇題(20分)1．數據結構是研究數據的( )以及它們之間的相互關系。( )3．在堆中執(zhí)行INSERT與DELETEMIN運算都只需O(log2n)時間。 (3)畫出二叉樹的后序線索化樹。 } if(j==tlen) return(itlen)。 (A)D一＞Lchild＝NULL (B)D一＞1tag＝1 (C)D一＞Rchild＝NULL (D)D一＞1tag＝0二、填空題(每空2分，共22分)1．對于一個以順序實現的循環(huán)隊列Q[0…m—1]，隊首、隊尾指針分別為f和r，其判空的條件是____________，判滿的條件是______________。模擬試題1一、選擇題(20分)1．組成數據的基本單位是( )。 (A)3 (B)4 (C)5 (D)110．線索化二叉樹中某結點D，沒有左孩子的主要條件是( )。 j=_________________。 (2)寫出按先序、中序、后序遍歷該二叉樹所得的結點序列。( )2．二叉排序樹的左、右子樹都是二叉排序樹。( )10．作為解決一類特定問題的算法，不能沒有輸入運算項。 (A)O(1og2n) (B)O(n2) (C)O(ne) (D)O(e log2 e)8．具有n個頂點的完全有向圖的邊數為( )。7．按________________遍歷二叉樹，可以得到按值遞增的關鍵碼序列，在下圖中所示的二叉樹中，檢索關鍵碼85的過程中，需與85進行比較的關健碼序列為________________。4．簡述堆排序的基本思想，對鍵值集合{72，73，71，23，94，16，05，68}對應的二叉樹進行進堆，并寫出具體步驟。( )5．對于n個記錄的集合進行冒泡排序，在最壞情況下的時間復雜度是0(n2)。 (A)‘STRUCTURE’ (B)‘DATA’ (C)‘ASTRUCTURE’ (D)‘DATA STRUCTURE’5．下列哪種排序需要的附加存儲開(A)快速排序 (B?堆排序 (C)歸并排序 (D)插人排序6．對任何一棵樹T，設分別是度為0，1，…，m的結點，則（ ）。6．具有128個結點的完全二叉樹的深度為_______________。j=______________。 2．線性表有順序表和鏈表兩種存儲結構，簡述各自關于運算實現的優(yōu)缺點。( )2．先序遍歷一棵一又搜索樹所得的結點訪問序列不可能是鎂值遞增序列、( )3．若有一個葉子結點是某子樹的中序遍歷的最后一個結點，則它必須是該子樹的先序遍歷的最后一個結點。 (A)快速排序 (B)堆排序 (c)歸并排序 (D)計數排序4．若按( )列出二叉排序樹中所存儲的元素，則恰好是集合中所有元素從小到大的排序。j) s=s+1。( )3．在堆中執(zhí)行INSERT與DELETEMIN運算都只需O(log2n)時間。(三、填空題(每空2分．共22分)1．在雙向循環(huán)表中，在p所指的結點之后插入指針f所指的結點，其操作為____________＝p。7．設一棵二叉樹共用50個葉子結點(終端結點)，則它共有__________個度為2的結點。（注，）(10分)3．設計一個算法，求出指定結點在給定的二叉樹中所在的層次。i++)for(j=0。(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)5．在雙向循環(huán)鏈表中，在p所指的結點之后插入s指針所指的結點，其操作是( )。 pnextprior=s。 pnext=s。(A)4 (D)5 (L)6 (D)7二、填空題(22分，前4題每空2分，第5題每空1分)1．若要在一個單鏈表的*p結點之前插入一個*s結點時，可執(zhí)行下列操作snext=____________； pnext=s；t=pdata；pdata=____________；sdata=____________。( )3．設有兩個串p和q．其中q是p的子串，把q在p中首次出現的位置作為q在p中的位置的算法稱為匹配。①試按表中元素的次序依次插入一棵初始為空的二叉排序樹，字符之間以字典順序比較大?。嫵鰧亩媾判驑?，且求出在等概率情況下查找成功的平均查找長度。2．試設計一個算法，求出指定結點在給定的二叉樹中的層次。 (A) front==rear (B) (rear+1)%MAXSIZE==front (C) frontrear==1 (D) rear%MAXSIZE==front6.—個55的對稱矩陣采用壓縮存儲，需要存儲( )個元素。7．二叉排序樹采用____________序遍歷可以得到結點的有序序列。( )6．設一棵二叉樹共用50個葉子結點(終端結點)，則共有49個度為1的結點7．一個有序的單鏈表采用折半查找法比順序查找效率高得多。(5分)(2)基于你給出的鄰接矩陣，求從頂點6出發(fā)的深度優(yōu)先遍歷。stop++。}Node。(5分)int strc(char s[], char t[]){ int i。}六、編程題(共15分)1．編寫算法對一個整型數組中的元素進行位置調整，將所有負數放在下標較低的一端，將所有正數放在下標較高的一端，所有的0在中間。 (A)A，B，C，D，E (B)B，C，D，E，A (C)E，A，B，C，D (D)E，D，C，B，A 3．在所有排序方法中，關鍵碼的比較次數與記錄的初始排列無關的是( (A)快速排序 (B)冒泡排序 (C)直接插入排序 (D)直接選擇排序4．設一棵二叉樹共用20個度為2的結點，則葉子結點共有( )個。( )4．有向圖的鄰接矩陣的第i行的所有元素之和等于第i列的所有元素之和。4．順序存儲的隊列如果不采用循環(huán)方式，則會出現下列問題：_________________。(5分)3．已知5個結點的權值分別是4，6，1，13，7，試畫出這些結點構成的Huffman樹。 int front。如果找不到值為x的元素，則新元素成為順序表的最后一個元素。 for(k=0。 return 1。(8分)Typedef struct LinkNode{ int data。}Node。 (A)13 (B)401 (C)402 (D)403二、判斷題(每題1分，共8分。（ ）8．對于二叉排序樹，根元素肯定是值最大的元素。8．一個具有n個結點的線性表采用堆排序，在建堆之后還要進行__________次堆調整。(1)從頂點D開始，寫出各頂點加人生成樹的次序。for(i= ____________________ 。完成以下程序。 p=pnext) if(pdata==e) ________________。 return。}SQ。(A)3 (B)4 (C)7 （D）8 8．已知某算法的執(zhí)行時間為，n為問題規(guī)模，則該算法的時間復雜度是( )。( )7．一個稀疏矩陣采用三元組法存儲不可能是((5,3,7),(5,4,4),(5,3,5))。6．快速排序法在最差的情況下的時間復雜廢是______________。(1)畫出該無向圖的鄰接矩陣。struct LinkNode *next。 ________________ = pnext。i2=n1。(7分)typedef struct{ int elem[100]。 }xlength=_________________。}Node。 (A)n—l (D)2n一1 (C)n十1 (D)2n十17．某二叉樹的中序序列和后序序列正好相反，則該二叉樹一定是( )的二叉樹。( ) 4．如果一個串中的所有字符均在另一個串中出現，則說明前者是后者的子串。 2．對于一個以順序實現的循環(huán)隊列Q[0…M1]，隊首、隊尾指針分別為f和r，隊列判空的條件是________________。9．直接選擇排序算法在最好情況下所做的交換元素的次數為________________。 ／* 查找區(qū)間初始化 *／int m。(每空2分)void SqList_Intersect(SqList A, SqList B, SqList amp。 j++。二叉樹類型定義如下。