西南財(cái)經(jīng)大學(xué)2019-2020學(xué)期數(shù)據(jù)結(jié)構(gòu)試卷

第2頁共3頁 2019-2020-1學(xué)期第1頁共4頁西南財(cái)經(jīng)大學(xué)試卷(A卷)考試科目：數(shù)據(jù)結(jié)構(gòu)_本年級(jí)層次 教學(xué)班 姓名： 學(xué)號(hào)：記分表試題號(hào)一二三四五六總分考分閱卷人注意：1、本次考試為A卷考試，考試時(shí)間120分鐘。2、請將答案依次寫在專用答題紙上。3、全卷共一部分，滿分為100分。一、單項(xiàng)選擇題（共15題，每題2分，共計(jì)30分）1、算法指的是（）。A、計(jì)算機(jī)程序B、解決問題的計(jì)算方法C、排序算法D、解決問題的有限運(yùn)算序列2、若進(jìn)棧序列為1、2、3、4、5，若允許出棧操作可以在任意可能的時(shí)刻進(jìn)行，則以下不可能的出棧序列是（）。A、3、4、2、5、1 B、2、5、4、1、3 C、2、3、1、5、4 D、3、5、4、2、13、在一個(gè)長度為n的順序表中向第i個(gè)元素(0<i<n+1)之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)（）個(gè)元素。 A、n-i B、n-i+1 C、n-i-1 D、idatanext4、假定一個(gè)鏈表隊(duì)列的隊(duì)首和隊(duì)尾指針分別用front和rear表示，每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為：當(dāng)出隊(duì)時(shí)所進(jìn)行的指針操作為（） A、front=front–>next B、rear=rear–>next C、front–>next=rear;rear=rear–>next D、front=front–>next

;front–>next=rear5、向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（）。 A、hs->next=s; B、s->next=hs;hs=s; C、s->next=hs->next;hs->next=s; D、s->next=hs;hs=hs->next;6、對于順序存儲(chǔ)的有序表{5，12，20，26，37，42，46，50，64}，若采用折半查找，則查找元素26的比較次數(shù)為（）。 A、2 B、3 C、4 D、57、線索二叉樹中，結(jié)點(diǎn)p沒有左子數(shù)的充要條件是（）。A、p->lc=NULL B、p->ltag=1 C、p->lc=NULL且p->ltag=1 D、以上都不對8、 若根據(jù)查找表（23，44，36，48，52，73，64，58）建立哈希表，采用h(K)=K%7計(jì)算哈希地址，則哈希地址等于3的元素個(gè)數(shù)為（）。 A、1 B、2 C、3 D、49、若一個(gè)元素序列基本有序，則選用（）方法較快。A、直接插入排序B、簡單選擇排序 C、堆排序D、快速排序10、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其元素地址（）。A、必須是連續(xù)的B、一定是不連續(xù)的 C、部分地址是連續(xù)的D、連續(xù)與否均可11、對一組數(shù)據(jù)（86，48，26，15，23）排序，數(shù)據(jù)的排列次序在排序過程中的變化為： ①8648261523 ②1548268623③1523268648④1523264886這個(gè)排序過程采用的排序方法是（）。A、冒泡 B、選擇 C、快速 D、插入12、在數(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.線性結(jié)構(gòu)和非線性結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)13、已知函數(shù)SubString(s,i,j)的功能是返回串s中從第i個(gè)字符起長度為j的子串，函數(shù)SCopy(s,t)的功能為復(fù)制串t到s。若字符串S=”SCIENCESTUDY”，則調(diào)用函數(shù)SCopy(P,Sub(S,1,7))后得到（）。A、P=”SCIENCE”B、P=”STUDY” C、S=”SCIENCE”D、S=”STUDY”14、若將一個(gè)10×10階的對稱矩陣壓縮存儲(chǔ)到一個(gè)一維數(shù)組中，則該一維數(shù)組的大小應(yīng)該是（）。A、55 B、56 C、45 D、4615、根據(jù)堆定義，下面的4個(gè)序列中，（）是堆。 A、75，65，30，15，25，45，20，10 B、75，65，45，10，30，25，20，15 C、75，45，65，30，15，25，20，10 D、75，45，65，10，25，30，20，15二、是非題（下列敘述正確的寫上T，否則，寫上F。共10題，每題1分，共計(jì)10分）1、數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面。（）2、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。（）3、線性表簡稱為“順序表”。（）4、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲(chǔ)，也可以鏈?zhǔn)酱鎯?chǔ)。非線性的數(shù)據(jù)結(jié)構(gòu)只能連接存儲(chǔ)。（）5、從單鏈表的任一結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。（）6、滿二叉樹一定是完全二叉樹。（）7、在有向圖G中，<V2,V1>和<V1,V2>是兩條不同的邊。（）8、在有序的順序表和有序的鏈表上，均可使用折半查找來提高查找效率。（）9、若二叉樹的中序遍歷序列與后序遍歷序列相同，則該二叉樹一定是任何結(jié)點(diǎn)都沒有右子樹。（）10、如果某種排序方法是不穩(wěn)定的，那么該排序方法不具有實(shí)用價(jià)值。（）三、填空題（共10空，每空1分，共計(jì)10分）1、每次從無序表中順序取出一個(gè)元素，把這個(gè)元素插入到有序表中的適當(dāng)位置，此種排序方法叫做【1】排序；每次從無序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做【2】排序。2、如果經(jīng)常對線性表進(jìn)行插入和刪除運(yùn)算，則最好采用 【3】 存儲(chǔ)結(jié)構(gòu)。3、數(shù)據(jù)結(jié)構(gòu)按結(jié)點(diǎn)間的關(guān)系，可分為4中邏輯結(jié)構(gòu)，它們分別是 【4】 、 【5】 、 【6】 和 【7】 。4、假定一個(gè)順序循環(huán)隊(duì)列的存儲(chǔ)空間長度為QueueSize，隊(duì)首和隊(duì)尾指針分別用front和rear表示，如果采用少用一個(gè)存儲(chǔ)空間的方式來區(qū)分循環(huán)隊(duì)列是隊(duì)空還是隊(duì)滿，則判斷隊(duì)空的條件是 【8】 ；判斷隊(duì)滿的條件是 【9】 。5、已知二維數(shù)組A[5][3]，其每個(gè)元素占2個(gè)存儲(chǔ)單元，并且A[0][0]的存儲(chǔ)地址為1000。則元素A[3][2]的存儲(chǔ)地址為 【10】 。四、算法填空題（每空2分，共20分）1、下列算法片段是矩陣快速轉(zhuǎn)置算法，請?jiān)趧澗€的位置填入適當(dāng)?shù)膬?nèi)容。 #defineARRAYSIZE1024 typedefstruct{ introw,col;/*非零元素的行號(hào)和列號(hào)*/ DataTypevalue;/*非零元素的值*/}TriType;typedefstruct{ triTypeitems[ARRAYSIZE+1];/*非零元三元組，item[0]未用*/ introws,cols;/*稀疏矩陣的行數(shù)、列數(shù)*/intnums;/*稀疏矩陣的非零元素個(gè)數(shù)*/}TriArray; FastTransMatrix(TriArrayTA,TriArrayTB){/*TA為轉(zhuǎn)置前的三元組屬性表，TB為轉(zhuǎn)置后的三元組順序表*/ inti,j=0,k=0; intpos[ARRATSIZE+1],num[ARRATSIZE+1]; if(TA.nums) { for(i=1;i<=TA.cols;i++) num[i]=0; for(i=1;i<=TA.nums;i++)/*求TA中每一列非零元個(gè)數(shù)*/ 【1】; pos[1]=1; for(i=2;i<=TA.cols;i++)/*計(jì)算第i列第一個(gè)非零元的位置 【2】;for(i=1;i<=TA.nums;i++){ j=TA.items[i].col; k=pos[j]; TB.items[k].row=TA.items[i].col; TB.items[k].col=TA.item[i].row;TB.items[k].value=TA.items[i].value;【3】;}}TB.rows=TA.cols;TB.cols=TA.rows;}2、下列算法片段預(yù)實(shí)現(xiàn)的功能是：對有序表ST進(jìn)行折半查找，成功時(shí)返回記錄在表中的位置，失敗時(shí)返回0。請?jiān)趧澗€的位置填入適當(dāng)?shù)膬?nèi)容。 typedefstruct{ keytypekey; }ElemType；typedefstruct{ ElemType*elem;/*數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)按實(shí)際長度分配，0號(hào)空間留空*/ intlength;/*表長度*/}SSTable; intSearch_Bin(SSTableST,keytypekey) {/*在表R中查找關(guān)鍵字k*/ intlow=1,high=ST.length; while(【4】) {mid=(low+high)/2;if(key=ST.elem[mid].key)return【5】;/*找到待查元素*/elseif(key>ST.elem[mid].key)【6】;/*繼續(xù)在前一半查找*/else【7】; /*繼續(xù)在后一半查找*/}return0; /*順序表中不存在待查元素*/ } 3、下列算法片段是直接插入排序算法。請?jiān)趧澗€的位置填入適當(dāng)?shù)膬?nèi)容。 voidInsertSort(SqListL){/*對順序表L作直接插入排序 for(i=2;i<=L.length;i++) if(L.r[i].key<L.r[i-1].key)/*若<,則將L.r[i]插入有序子表*/ { L.r[0]=L.r[i]; /*復(fù)制為哨兵*/【8】;for(j=i-2;【9】;j--) L.r[j+1]=L.r[j];/*記錄后移*/【10】;/*插入到正確位置*/ } } 五、算法應(yīng)用題（共15分）1、模式匹配的KMP算法應(yīng)用設(shè)目標(biāo)為s=”abcaabbabcabaacbacba”，模式p=”abcabaa”。(1)計(jì)算模式p的next[j]函數(shù)值。（3分）(2)不寫出KMP算