《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)題題庫

一、單項選擇題（本大題共71小題，每小題2分，共142分）1、一個對象序列的排序碼為{46，79，56，38，40，84}，采用快速排序以位于最左位置的對象為基準而得到的第一次劃分結(jié)果為（C）。（A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}標準答案：C）2、廣義表（（a）,a）的表頭是（C）。（）A．a(chǎn)B．bC．(a)D．((a))標準答案：C3、數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是（C）。（）A．80B．100C．240D．270標準答案：C4、在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行（）。（A．HL=p；p->next=HL；）B．p->next=HL；HL=p；C．p->next=HL；p=HL；D．p->next=HL->next；HL->next=p；標準答案：B5、一個具有n個頂點的無向完全圖的邊數(shù)為（）。（）A．(n+1)/2B．n(n-1)/2C．n(n-1)D．n(n+1)標準答案：B6、如果待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則稱該排序是不穩(wěn)定的。下列選項中，（）就是不穩(wěn)定的排序方法。（）A．起泡排序B．歸并排序C．直接插入法排序D．簡單選擇排序標準答案：D7、按照二叉樹的定義，具有3個結(jié)點的二叉樹有（）種。（）A．3B．4C．5D．6標準答案：C8、設(shè)有1000個元素，用二分法查找時，最大比較次數(shù)是（）。（）A．1B．7C．10D．25標準答案：C9、樹適合用來表示（）。（A．有序數(shù)據(jù)元素B．無序數(shù)據(jù)元素）C．元素之間具有分支層次關(guān)系的數(shù)據(jù)D．元素之間無聯(lián)系的數(shù)據(jù)標準答案：C10、設(shè)有兩個串p和q，求p在q中首次出現(xiàn)的位置的運算稱作（）。（）A．連接B．模式匹配C．求子串D．求串長標準答案：B11、將含100個結(jié)點的完全二叉樹從根這一層開始，每層上從左到右依次對結(jié)點編號，根結(jié)點的編號為1。編號為49的結(jié)點X的雙親編號為（）。（）A．23B．24C．25D．無法確定標準答案：A12、串的長度是（）。（A．串中不同字符的個數(shù)B．串中不同字母的個數(shù)）C．串中所含字符的個數(shù)且字符個數(shù)大于0D．串中所含字符的個數(shù)標準答案：D13、已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（）。（）A．a(chǎn)cbedB．decabC．deabcD．cedba標準答案：D14、順序表中邏輯上相鄰的節(jié)點其物理位置也（）。（）A．一定相鄰B．不必相鄰C．按某種規(guī)律排列D．無要求標準答案：A15、數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（）以及它們之間的相互關(guān)系。（A．理想結(jié)構(gòu)，物理結(jié)構(gòu)）B．理想結(jié)構(gòu)，抽象結(jié)構(gòu)C．物理結(jié)構(gòu)，邏輯結(jié)構(gòu)D．抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)標準答案：C16、由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。（）A．24B．48C．53D．72標準答案：C17、某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。（）A．空或只有一個結(jié)點B．高度等于其結(jié)點數(shù)C．任一結(jié)點無左孩子D．任一結(jié)點無右孩子標準答案：B18、下列排序算法中，（）排序在每趟結(jié)束后不一定能選出一個元素放到其排好序的最終位置上。（）A．選擇B．冒泡C．歸并D．堆標準答案：C19、廣義表(a,b,c,d)的表尾是（）。（）A．a(chǎn)B．bC．(a,b)D．(b,c,d)標準答案：D20、具有65個結(jié)點的完全二叉樹其深度為（）。（A．8）B．7C．6D．5標準答案：B21、在內(nèi)部排序中，排序時不穩(wěn)定的有（）。（）A．插入排序B．冒泡排序C．快速排序D．歸并排序標準答案：C22、向堆中插入一個元素的時間復(fù)雜度為（）。（）A．O(log2n)B．O(n)C．O(1)D．O(nlog2n)標準答案：A23、在一個單鏈表HL中，若要在指針q所指的結(jié)點的后面插入一個由指針p所指的結(jié)點，則執(zhí)行（）。（）A．q->next=p->next；p->next=q；B．p->next=q->next；q=p；C．q->next=p->next；p->next=q；D．p->