國開電大2023年春季期末考試《數(shù)據(jù)結(jié)構(gòu)》試題(試卷代號(hào)1252)

國家開放大學(xué)2023年春季學(xué)期開放?？破谀┛荚嚨诘陧搰议_放大學(xué)2023年春季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)(本)試題一、單項(xiàng)選擇題(把合適的選項(xiàng)編號(hào)填寫在括號(hào)內(nèi)。每小題3分,共45分)1.線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)都是按數(shù)據(jù)的()來分類的。A.存儲(chǔ)結(jié)構(gòu)B.物理和存儲(chǔ)結(jié)構(gòu)C.物理結(jié)構(gòu)D.邏輯結(jié)構(gòu)2.在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為().A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)3.設(shè)有一個(gè)長度為n的順序表,要?jiǎng)h除第i個(gè)元素,則需移動(dòng)元素的個(gè)數(shù)為()。A.iB.n-i-1C.n-iD.n-i+14.設(shè)有一個(gè)長度為10的順序表,要在第3個(gè)元素之后插入一個(gè)元素,則需移動(dòng)元素的個(gè)數(shù)為().A.3B.6C.7D.85.一個(gè)隊(duì)列的人隊(duì)序列是10,20,30,40。則隊(duì)列的輸出序列是().A.40,30,20,10B.10,20,30,40C.10.40,30,20D.30,20,40,106.在一棵二叉樹中(其根結(jié)點(diǎn)編號(hào)為1),若編號(hào)為8的結(jié)點(diǎn)存在右孩子,則該右孩子的順序編號(hào)為()。A.18B.16C.15D.177.隊(duì)列的出隊(duì)操作在()進(jìn)行。A.隊(duì)頭B.隊(duì)尾C.任意位置D.指定位置8.串函數(shù)index(a,b)的功能是進(jìn)行()。A.求子串B.串連接C.模式匹配D.求串長9.一個(gè)非空廣義表的表頭元素()。A.不可能是原子B.只能是子表C.只能是原子D.可以是子表或原子10.鏈表所具備的特點(diǎn)之一是()。A.可以隨機(jī)訪問任一結(jié)點(diǎn)B.需要占用連續(xù)的存儲(chǔ)空間.C.插人元素的操作不需要移動(dòng)元索D.刪除元素的操作需要移動(dòng)元素11.樹中所有結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度加()。A.1B.0C.2D.-1在一個(gè)無向圖G中,所有邊數(shù)之和等于的所有頂點(diǎn)的度數(shù)之和()倍。A.1/2B.1C.2D.413.對(duì)于一個(gè)具有4個(gè)頂點(diǎn)和5條邊的無向圖,若采用鄰接表表示,則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為()。A.4B.5C.8D.1014.有一個(gè)長度為5的線性表,按順序查找某關(guān)鍵字,在等概率情況下查找成功的平均比較次數(shù)為()。A.2B.2.5C.3D.3.515.假定一組記錄的排序碼為(46,79,56,38,40,80),對(duì)其進(jìn)行歸并排序的過程中,第二趟歸并后的結(jié)果為()。A.46,79,56,38,40,80B.46,79,38,56,40,80C.38,46,56,79,40,80D.38,40,46,56,79,80得分|評(píng)卷人二.判斷題(根據(jù)敘述正確與香在其后面的括號(hào)內(nèi)打?qū)μ?hào)“V"或打叉號(hào)"X"。每小題2分,共30分)16.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。()17.數(shù)據(jù)結(jié)構(gòu)中,元素之間存在一對(duì)多的關(guān)系稱為圖狀結(jié)構(gòu)。()18.設(shè)有一個(gè)單向鏈表,結(jié)點(diǎn)的指針城為next,頭指針為head,p指向尾結(jié)點(diǎn),為了使該單向鏈表改為單向循環(huán)鏈表,可用語句p->next=head.()19.線性表用關(guān)鍵字的順序方式存儲(chǔ)，可以用二分法查找。()20.往棧中插人元素的操作方式是:先寫人元素,后移動(dòng)棧頂指針。()21.棧是限定在表的一端進(jìn)行插人和刪除操作的線性表,又稱為先進(jìn)后出表。()22.遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來實(shí)現(xiàn)對(duì)它的操作。()23.串是一種特殊的線性表,其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是字符。()24.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元索的行號(hào).列號(hào)和元素值三項(xiàng)信息。()25.二叉樹只能采用二叉鏈表來存儲(chǔ)。()26.完全二叉樹中沒有度為1的結(jié)點(diǎn)。()27.圖的生成樹是惟一的。()28.對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。()29.在有序順序存儲(chǔ)的線性表中查找一個(gè)元素,用折半查找速度一定比順序查找快。()30.對(duì)n個(gè)元素進(jìn)行冒泡法排序,最多需要進(jìn)行n-1趟冒泡。()三、綜合應(yīng)用及程序設(shè)計(jì)題(每小題5分,共25分)31.在下面空格處填寫一條語句,以使下面的鏈?zhǔn)疥?duì)列全部元素出隊(duì)的算法完整。intwrite(LinkQueue*q){QueueNode*p;.if(q->front==q->rear)/*隊(duì)空*/{printf(“隊(duì)空!無元素可取");exit(0);.{while(q->front->enxt!=NULL){p=q->front->next;q一>front->next=p->next;/*出隊(duì)*/printf("%4d",p->data);free(p);/*釋放已出隊(duì)結(jié)點(diǎn)*/{____________/*隊(duì)空時(shí),頭尾指針指向頭結(jié)點(diǎn)*/}程序中空格部分的選項(xiàng)為:A.q->front=q->rear;B.q=q一>next;C.q->rear=q->front;D.p=p->next;32.以下程序是先序遍歷二叉樹的遞歸算法的程序,完成程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為left和right,數(shù)據(jù)域data為字符型,BT指向根結(jié)點(diǎn)).voidPreorder(structBTreeNode*BT){if(BT!=NULL){____________________;Preorder(BT-->-left);Preorder(BT-->right);}}A.printf("%c",BT->left)B.print("%c",BT->right)C.printf("%c",BT->-data)D.printf("%d",BT->data)33.一組記錄的關(guān)鍵字序列為(6,9,7,4,5,8),利用堆排序(堆頂元素是最小元素)的方法建立初始堆是如下哪個(gè)圖?()34.以下利用直接插人排序算法對(duì)存放在a[0],a[1],●●●,a[n-1]中,長度為n的記錄序列按關(guān)鍵字key由小到大排序,完成程序中空格部分。voiddisort(NODEa[].intn){inti,j;NODEtemp;for(i=1;i<nji++){temp=a[i];j=i-1;while(j>=0&&temp.key<a[i].key){a[j+1]=a[j];____________________;}a[j+1]=temp;}}程序中空格部分的選項(xiàng)為:A.j++B.i++C.j--D.i--35.設(shè)數(shù)據(jù)序列為:{53,30,37,12,45,24,96}.(1)從空二叉樹開始逐個(gè)插人該數(shù)據(jù)序列來形成二叉排序樹,若希望高度最小，應(yīng)該選擇:的序列是()。(本小題3分)A.45,24,53,12,37,96,30B.37,24,12,30,53,45,96C.12,24,30,37,45,53,96D.30,24,12,37,45,96,53(2)用鏈接地址法將該數(shù)據(jù)序列構(gòu)造哈希表,哈希函數(shù)為H(key)=keymod13,則散列地址為1的鏈中有()個(gè)記錄。(本小題2分)A.0B.1C.2D.3

國家開放大學(xué)2023年春季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)(本)試題答案及評(píng)分標(biāo)準(zhǔn)(供參考)一、單項(xiàng)選擇題(每小題3分,共45分)1.D2.D3.C4.C5.B6.D7.A8.C9.D10.C11.A12.A13.D.14.C15.C二、判斷題(每小題2分,共30分)16.V17.X18.V19.X.20.x21.V22.V23