天津大學(xué)20春《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)2答案

1、天津大學(xué)20春數(shù)據(jù)結(jié)構(gòu)在線作業(yè)2答案設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是()。A.P，A，C，S，Q，D，F(xiàn)，X，R，H，M，YB.H，C，Q，P，A，M，S，R，D，F(xiàn)，X，YC.F，H，C，D，P，A，M，Q，R，S，Y，XD.A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為()。A.5，3，4，6，1，2B.3，2，5，6，4，1C.3，1，2，5，4，6D.1，5，4，6，2，3數(shù)組的邏輯結(jié)構(gòu)不同于下列()的邏輯結(jié)構(gòu)。A.隊列B.線性

2、表C.樹D.棧設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ敚瑒t刪除棧頂元素的操作序列為()。A.top=top->nextB.top=top-1C.top=top+1D.top->next=top一個有n個頂點(diǎn)的無向圖最多有()條邊。A.n(n-1)/2B.n(n-1)C.nD.2n設(shè)一個順序有序表A1:14中有14個元素，則采用二分法查找元素A4的過程中比較元素的順序為()。A.A7，A5，A3，A4B.A7，A3，A5，A4C.A1，A2，A3，A4D.A1，A14，A7，A4有一個長度為12的有序表，按二分查找法對該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為()

3、。A.43/12B.39/12C.37/12D.35/12在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為()。A.O(nlog2n)B.O(n2)C.O(n)D.O(1og2n)設(shè)散列表中有m個存儲單元，散列函數(shù)H(key)=key%p，則p最好選擇()。A.小于等于m的最大素數(shù)B.小于等于m的最大奇數(shù)C.小于等于m的最大合數(shù)D.小于等于m的最大偶數(shù)設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為()。A.N2+N3B.N2-1C.N1+N3D.N1-1堆的形狀是一棵()。A.滿二叉樹B.平衡

4、二叉樹C.完全二叉樹D.二叉排序樹采用線性探測法解決沖突問題，所產(chǎn)生的一系列后繼散列地址()。A.必須小于等于原散列地址B.必須大于等于原散列地址C.地址大小沒有具體限制D.可以大于或小于但不能等于原散列地址在一個圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的()倍。A.4B.2C.1/2D.1樹最適合用來表示()。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間無聯(lián)系的數(shù)據(jù)D.元素之間具有分支層次關(guān)系的數(shù)據(jù)設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點(diǎn)，2個度數(shù)為2的結(jié)點(diǎn)，2個度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有()個度數(shù)為0的結(jié)點(diǎn)。A.8B.7C.6D.5設(shè)某散列表的長度為100，散列函數(shù)H(k)=k% P，則P通常

5、情況下最好選擇()。A.99B.97C.93D.91對于一個有向圖，若一個頂點(diǎn)的入度為k1，出度為k2，則對應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為()。A.k2B.k1-k2C.k1+k2D.k1設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是()。A.head=0B.head->next=headC.head->next=0D.head!=0隊列是一種()的線性表。A.只能插入B.只能刪除C.先進(jìn)后出D.先進(jìn)先出設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有()個結(jié)點(diǎn)。A.n+lB.2n+lC.2n-1D.2n設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，

6、R)，其中D=1，2，3，4，R=r，r=，則數(shù)據(jù)結(jié)構(gòu)A是()。A.集合B.線性結(jié)構(gòu)C.樹型結(jié)構(gòu)D.圖型結(jié)構(gòu)下述幾種排序方法中，要求內(nèi)存量最大的是()。A.選擇排序B.插入排序C.快速排序D.歸并排序一組記錄的關(guān)鍵碼為(46，79，56，38，40，84)，則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為()。A.40，38，46，84，56，79B.40，38，46，79，56，84C.40，38，46，56，79，84D.38，40，46，56，79，84設(shè)有一個10階的下三角矩陣A(包括對角線)，按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)

7、的存儲空間，則A54地址與A00的地址之差為()。A.55B.28C.19D.10任何一個無向連通圖的最小生成樹()。A.有一棵或多棵B.可能不存在C.只有一棵D.一定有多棵設(shè)順序表的長度為n，則順序查找的平均比較次數(shù)為()。A.n/2B.nC.(n-1)/2D.(n+1)/2把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是()。A.有多種，但根結(jié)點(diǎn)都沒有左孩子B.有多種，但根結(jié)點(diǎn)都沒有右孩子C.有多種D.唯一的二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以()。A.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲B.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用C.它不能用順序存儲結(jié)構(gòu)存儲D.它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲采用順序查找方法查找長

8、度為n的線性表時，每個元素的平均查找長度為()。A.n/2B.nC.(n-1)/2D.(n+1)/2用某種排序方法對線性表(25，84，21，47，15，27，68，35，20)進(jìn)行排序時，元素序列的變化情況如下： 25，84，21，47，15，27，68，35，20; 20，15，21，25，47，27，68，35，84; 15，20，21，25，35，27，47，68，84; 15，20，21，25，27，35，47，68，84。則所采用的排序方法是()。A.選擇排序B.快速排序C.歸并排序D.希爾排序二叉樹中第i(i1)層上的結(jié)點(diǎn)數(shù)最多有()個。A.2i-1B.2的i-1次方C.2的i次

9、方D.2i設(shè)指針q指向單鏈表中結(jié)點(diǎn)A，指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A和結(jié)點(diǎn)B插入結(jié)點(diǎn)X的操作序列為()。A.s->next=p->next;p->next=-sB.q->next=s;s->next=pC.p->next=s;s->next=qD.p->next=s->next;s->next=p設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為()。A.s->left=p;s->right=p->right;p->

10、right=s;p->right->left=sB.s->left=p;s->right=p->right;p->right->left=s;p->right=sC.p->right=s;s->left=p;p->right->left=s;s->right=p->rightD.p->right=s;p->right->left=s;s->left=p;s->right=p->right樹的基本遍歷策略可分為先根遍歷和后根遍歷;二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后

11、序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對應(yīng)的二叉樹。結(jié)論()是正確的。A.樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同B.樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同C.樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同D.以上都不對有8個結(jié)點(diǎn)的無向圖最多有()條邊。A.56B.28C.14D.112快速排序方法在()情況下最不利于發(fā)揮其長處。A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)已基本有序C.要排序的數(shù)據(jù)中含有多個相同值D.要排序的數(shù)據(jù)個數(shù)為奇數(shù)用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印出相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是()。A.逆拓樸有序的B.無序的C.拓樸有序的D.不確定的在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的()倍。A.4B.2C.1/2D.1下述幾種排序方法中，平均查找長度最小的是()。A.選擇排序B.插入排序C.快速排序D.歸并排序二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均()根結(jié)點(diǎn)的值。A.>B.=C.D.!= 參考答案：B參考答案：B參考答案：C參考答案：A參考答案：A參考答案：B參考答案：C參考答案：D參考答案：A參考