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

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