2007年10月自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題真題

浙浙02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第6頁(yè)（共6頁(yè)）200710月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分( )C.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)2.for（i=0；i<m；i++）for（j=0；j<n；j++）A［［=i*；上面算法的時(shí)間復(fù)雜度( A.O(m2)C.O(m×n)

D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)B.O(n2)D.O(m+n）設(shè)順序表有9個(gè)元素，則在第3個(gè)元素前插入一個(gè)元素所需移動(dòng)元素的個(gè)數(shù)( )A.5 B.6C.7 D.9pp→llink和p→rlink表示，則同樣表示p指針?biāo)赶蚪Y(jié)點(diǎn)的表達(dá)式( )p→llink

p→rlink一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的存儲(chǔ)地是( )A.110C.100

B.108D.120設(shè)有一個(gè)棧，按ABCD的順序進(jìn)棧，則可能為出棧序列的( )A.DCBAC.DBAC

B.CDABD.DCAB在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top為棧頂指針，則當(dāng)做出棧處理時(shí)變化( )A.top++C.top不變除根結(jié)點(diǎn)外，樹(shù)上每個(gè)結(jié)( )可有任意多個(gè)孩子、一個(gè)雙C.可有一個(gè)孩子、任意多個(gè)雙親9.題9圖中樹(shù)的度( )

B.top--D.top=0D.只有一個(gè)孩子、一個(gè)雙親A.2B.3C.5D.8 9圖10.有4個(gè)頂點(diǎn)的無(wú)向完全圖的邊數(shù)( )A.6C.16

0 1 1

B.12D.20設(shè)圖的鄰接矩陣為0 0 1，則該圖( ) 0 1 有向圖C.

無(wú)向圖D.在對(duì)查找表的查找過(guò)程中若被查找的數(shù)據(jù)元素不存在則把該數(shù)據(jù)元素插入到集合中這種方式主要適合( )A.靜態(tài)查找表C.靜態(tài)查找表與動(dòng)態(tài)查找表

B.動(dòng)態(tài)查找表D.靜態(tài)查找表或動(dòng)態(tài)查找表用散列函數(shù)求元素在散列表中的存儲(chǔ)位置時(shí)，可能會(huì)出現(xiàn)不同的關(guān)鍵字得到相同散列數(shù)值的沖突現(xiàn)象?？捎糜诮鉀Q上述問(wèn)題的( )A.線性探測(cè)法C.平方取中法

B.除留余數(shù)法D.折疊法排序算法中，第一趟排序后，任一元素確定其最終位置的算法( A.選擇排序 B.插入排序C.冒泡排序 D.快速排序在排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空的一端的方法，稱( )C.插入排序

歸并排序D.二、填空題(本大題共13小題，每小題2分，共26分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。如果操作不改變?cè)壿嫿Y(jié)構(gòu)“值，而只是從中提取某些信息作為運(yùn)算結(jié)果，則稱該運(yùn)算型運(yùn)算。設(shè)有指針head指向不帶表頭結(jié)點(diǎn)的單鏈表用next表示結(jié)點(diǎn)的一個(gè)鏈域指針p指向與鏈表中結(jié)點(diǎn)同類型的一個(gè)新結(jié)點(diǎn)?，F(xiàn)要將指針p指向的結(jié)點(diǎn)插入表中，使之成為第一個(gè)點(diǎn)，則所需的操作為next=hea”和 。單鏈表中邏輯上相鄰的兩個(gè)元素在物理位置相鄰。n的數(shù)組中刪除第i個(gè)元素（1≤i≤n）時(shí)，需要向前移動(dòng)的元素的個(gè)數(shù)是 。設(shè)、C是二叉樹(shù)中的兩個(gè)結(jié)點(diǎn)，若F是C的祖先結(jié)點(diǎn)，則在采用后根遍歷方法遍歷二叉樹(shù)時(shí)，F(xiàn)和C的位置關(guān)系為必定在C。若用后根遍歷法遍歷題21圖所示的二叉樹(shù)，其輸出序列。題21圖具有n個(gè)頂點(diǎn)的連通圖至少需條邊。在無(wú)向圖G的鄰接矩陣A中，若A［［］等于1，則A［［］等 。設(shè)順序表的表長(zhǎng)為n，且查找每個(gè)元素的概率相等，則采用順序查找法查找表中任一素，在查找成功時(shí)的平均查找長(zhǎng)度。在索引順序表上的查找分兩個(gè)階段：一是查，二是查找塊。文件的基本運(yùn)算有檢索和修改兩類。而檢索又有三種方式，它們存取、接存取和按關(guān)鍵字存取。27.在對(duì)一組關(guān)鍵字為（54，38，96，23，15，72，60，45，83）的記錄采用直接選擇排法進(jìn)行排序時(shí)，整個(gè)排序過(guò)程需進(jìn)趟才能夠完成。冒泡排序是一種穩(wěn)定排序方法。該排序方法的時(shí)間復(fù)雜度。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)29圖中二叉樹(shù)的先根、中根、后根遍歷序列。題29圖設(shè)要將序列按字母升序排序，請(qǐng)分別畫(huà)出采用堆排31.如題31圖所示，輸入元素為A，B，C，在棧的輸出端得到一個(gè)輸出序列ABC，試寫(xiě)出在棧的輸入端三個(gè)可能的輸入序列。題31圖已知無(wú)向圖G的鄰接矩陣如題32的訪問(wèn)序列。題32圖20的有序表進(jìn)行二分查找，試畫(huà)出它的一棵判定樹(shù)。四、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分)下面程序段為刪除循環(huán)鏈表中第一個(gè)info域值等于x34圖所示：題34圖structnode{intinfo;structnode*link;}intDelete(structnode*head,intx){structnode*p,*q;/*p:當(dāng)前處理的結(jié)點(diǎn)；q：p的前驅(qū)結(jié)點(diǎn)*/if(!head)return(0);if(head→link==head){if(head→info==x){free(head);head=NULL；return(x)}return(0);}p=head;q=head;while(q→link!=head)q=(1) ;while(p→link!=head){if(p→info==x){(2) ;if(p==head)head=(3) free(p);return(x);}else{q=p;}}return(0);