答案西安交通大學(xué)2020春《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)

.在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為()。A.O(n)B.O(1og2n)C.O(nlog2n)D.O(n2)答案：B.設(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->next;s->next=pD.p->next=s;s->next=q答案：B.字符串的長(zhǎng)度是指()。A.串中不同字符的個(gè)數(shù)B.串中不同字母的個(gè)數(shù)C.串中所含字符的個(gè)數(shù)D.串中不同數(shù)字的個(gè)數(shù)答案：C.設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有()個(gè)表頭結(jié)點(diǎn)。A.2nB.nC.n/2D.n(n-1)答案：B.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)()。A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改答案：D.下列程序段的時(shí)間復(fù)雜度為()。I=0,s=0;while(s<n){s=s+i;i++;}A.O(n1/2)B.O(n1/3)C.O(n)D.O(n2)答案：A.如果要求頻繁的對(duì)線性表進(jìn)行插入和刪除操作，則線性表應(yīng)該采用()存儲(chǔ)結(jié)構(gòu)。A.散列.順序C.鏈?zhǔn)紻.任意答案：C.設(shè)一棵完全二叉樹中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為()。A.8B.7C.6D.5答案：B.設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列()存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單向鏈表B.單向循環(huán)鏈表口雙向鏈表口.雙向循環(huán)鏈表答案：D10.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)?()A.隊(duì)列B.棧C.線性表D.二叉樹答案：D.每個(gè)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，所有存儲(chǔ)結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)的存儲(chǔ)空間里，這種存儲(chǔ)結(jié)構(gòu)稱為()結(jié)構(gòu)。A.順序結(jié)構(gòu)B.鏈?zhǔn)浇Y(jié)構(gòu)C.索引結(jié)構(gòu)D.散列結(jié)構(gòu)答案：A.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為()。A.q=p->next;p->data=q->data;p->next=q->next;free(q)B.q=p->next;q->data=p->data;p->next=q->next;free(q)C.q=p->next;p->next=q->next;free(q)D.q=p->next;p->data=q->data;free(q)答案：A.設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為()。A.O(n)B.O(nlog2n)C.O(1)D.O(n2)答案：C14.由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為()。A.24B.71C.48D.53答案：B15.對(duì)一棵二叉排序樹進(jìn)行()遍歷，可以得到該二叉樹的多有結(jié)點(diǎn)按值從小到大排列的序列。A.前序B.中序C.后序D.按層次答案：B.若目標(biāo)串的長(zhǎng)度為n,模式串的長(zhǎng)度為[n/3],則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是()。A.O(1)B.O(n)C.O(nA2)D.O(nA3)答案：C.在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，打印機(jī)依次從該緩沖區(qū)中取出數(shù)據(jù)打印，則該緩沖區(qū)的結(jié)構(gòu)應(yīng)該是()。A.線性表B.數(shù)組C.堆棧D.隊(duì)列答案：D18.線性鏈表各結(jié)點(diǎn)之間的地址()。A.必須連續(xù)B.一定不連續(xù)C.部分地址必須連續(xù)D.連續(xù)與否無所謂答案：D.在二叉排序樹中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為()。A.O(1)B.O(n)C.O(log2n)D.O(n2)答案：B.設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為()。A.p->right=s;s->left=p;p->right->left=s;s->right=p->rightB.s->left=p;s->right=p->right;p->right=s;p->right->left=sC.p->right=s;p->right->left=s;s->left=p;s->right=p->rightD.s->left=p;s->right=p->right;p->right->left=s;p->right=s答案：D.設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為()。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，8答案：C.將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為()。A.O(1)B.O(n)C.O(m)D.O(m+n)答案：C.對(duì)于線性表(7，34，55，25，64，46，20，10)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%9作為散列函數(shù)，則散列地址為1的元素有()個(gè)。A.1B.2C.3D.4答案：D.下列各個(gè)排序算法中，要求輔助空間最大的是()。A.希爾排序法B.快速排序法C.堆排序法D.二路歸并排序法答案：D25.對(duì)待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對(duì)兩個(gè)子序列施加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。這樣的排序方法是()。A.直接選擇排序B.直接插入排序C.快速排序D.起泡排序答案：C.一個(gè)棧的輸入序列為123...n，若輸出序列的第一個(gè)元素是n，輸出i(1<=i<=n)個(gè)元素是()。A.不確定B.n-i+1C.iD.n-i答案：B.鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是()。A.插入操作更加方便B.通常不會(huì)出現(xiàn)棧滿的情況C.不會(huì)出現(xiàn)棧空的情況D.刪除操作更加方便答案：B.程序段如下：s=i=0;do{i=i+1;s=s+i;}while(i二n);其時(shí)間復(fù)雜度為()。A.O(n)B.O(nlog2n)C.O(n2)D.O(n3/2)答案：A.一個(gè)具有n個(gè)頂點(diǎn)的無向圖最多有()條邊。A.nX(n-1)/2B.nX(n-1)C.nX(n+1)/2D.n2答案：A.數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)()。A.55B.45C.36D.16答案：B.快速排序是排序算法中平均性能最好的一種排序。()A.錯(cuò)誤B.正確答案：B.有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。()A.錯(cuò)誤B.正確答案：A33.順序查找法適用于存儲(chǔ)結(jié)構(gòu)為順序或鏈接存儲(chǔ)的線性表。()A.錯(cuò)誤B.正確答案：B34.對(duì)具有n個(gè)元素的序列來采用冒泡排序法進(jìn)行排序，排序的趟數(shù)為n-1。()A.錯(cuò)誤B.正確答案：A35.順序表用一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)，因此順序表是一維數(shù)組。()A.錯(cuò)誤B.正確答案：A36.棧和隊(duì)列都是順序存取的的線性表，但它們對(duì)存取位置的限制不同。()A.錯(cuò)誤B.正確答案：B.入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。()答案：B.在B+樹中查找和在B-樹中查找的過程完全相同。()A.錯(cuò)誤B.正確答案：A39.圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問過。()A.錯(cuò)誤B.正確答案：B40.為度量一個(gè)搜索算法的性能，需要在時(shí)間和空間方面進(jìn)行權(quán)衡。()A.錯(cuò)誤B.正確答案：B41.單鏈表形式的隊(duì)列，頭指針F指向隊(duì)列的第一個(gè)結(jié)點(diǎn)，尾指針R指向隊(duì)列的最后一個(gè)結(jié)點(diǎn)。()A.錯(cuò)誤B.正確答案：B.磁帶是順序存取的外存儲(chǔ)設(shè)備。()A.錯(cuò)誤B.正確答案：B.圖可以沒有邊，但不能沒有頂點(diǎn)。()答案：B.分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。()A.錯(cuò)