自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題7套

1、全國2008年10月高等教育自學(xué)考試 數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題 課程代碼：02142一、單項選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。 1.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（c） a.動態(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.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2.關(guān)于算法的描述，不正確的是（d） a.算法最終必須由計算機程序?qū)崿F(xiàn) b.所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界 c.健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài) d.算法的優(yōu)劣與算法描述語言無關(guān)

2、3.在單鏈表中，存儲每個結(jié)點需要有兩個域，一個是數(shù)據(jù)域，另一個是指針域，指針域指向該結(jié)點的（b） a.直接前趨 b.直接后繼 c.開始結(jié)點 d.終端結(jié)點4.將兩個各有n個元素的有序表合并成一個有序表，其最少的比較次數(shù)為（a） a.n b.2n-1 c.2n d.n25.棧和隊列共同具有的特點是（c） a.都是先進后出 b.都是先進先出 c.只允許在端點進行操作運算 d.既能先進先出，也能先進后出6.若用一個有6個單元的數(shù)組來實現(xiàn)循環(huán)隊列，rear和front的初值分別為0和3。則從隊列中刪除一個元素，再添加兩個元素后，rear和front的值分別為（b） a.1和5 b.2和4 c.4和2 d

3、.5和17.數(shù)組a0.50.5的每個元素占5個字節(jié)，將其以列為主序存儲在起始地址為1000的內(nèi)存單元中，則元素a55的地址是（a） a.1175 b.1180 c.1205 d.12108.含有n個結(jié)點的二叉樹采用二叉鏈表存儲時，空指針域的個數(shù)為（c） a.n-1 b.n c.n+1 d.n+2 9.在一棵深度為h的完全二叉樹中，所含結(jié)點的個數(shù)不少于（b） a.2h-1-1 b.2(h-1) c.2h-1 d.2h10.一個具有n個頂點的無向連通圖，它所包含的連通分量數(shù)為（d） a.0 b.1 c.n d.不確定11.下列說法中不正確的是（d） a.無向圖的極大連通子圖稱為連通分量 b.連通圖

4、的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點 c.連通圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點 d.有向圖的遍歷不可采用廣度優(yōu)先搜索算法12.對一棵二叉排序樹采用中根遍歷進行輸出的數(shù)據(jù)一定是（a） a.遞增或遞減序列 b.遞減序列 c.無序序列 d.遞增序列13.一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當二分查找值為82的結(jié)點時，查找成功時的比較次數(shù)為（c） a.1 b.2 c.4 d.8 14.一組記錄的關(guān)鍵字為45，80，55，40，42，85，則利用堆排序的方法建立的初始堆為（b） a.80，45，55，40，42，85 b.

5、85，80，55，40，42，45 c.85，80，55，45，42，40 d.85，55，80，42，45，4015.關(guān)于vsam文件存取操作的說法，正確的是（d） a.不能順序存取，只能按關(guān)鍵字隨機存取 b.不能順序存取，不能按關(guān)鍵字隨機存取 c.只能順序存取，不能按關(guān)鍵字隨機存取 d.既能順序存取，也能按關(guān)鍵字隨機存取二、填空題(本大題共13小題，每小題2分，共26分) 請在每小題的空格中填上正確答案。錯填、不填均無分。 16.在任何問題中，數(shù)據(jù)元素都不是孤立的，它們之間總存在某種關(guān)系，通常稱這種關(guān)系為_邏輯結(jié)構(gòu)_。 17.存儲結(jié)點之間通常有四種基本存儲方式，即順序存儲方式、索引存儲方式

6、、_鏈式存儲_和散列存儲方式。 18.在一個長度為n的順序表中第i個元素（1in）之前插入一個元素時，需向后移動_n-i+1_個元素。19.對一棵深度為10的滿二叉樹按層編號，則編號為51的結(jié)點，它的雙親結(jié)點編號為_25_。 20.用s表示入棧操作，x表示出棧操作，若元素入棧順序為1234，為了得到1342的出棧順序，相應(yīng)的s和x操作串為_sxssxsxx_。 21.具有n個葉子結(jié)點的哈夫曼樹，其結(jié)點總數(shù)為_2*n-1_。 22.一棵具有n個結(jié)點的樹，所有非終端結(jié)點的度均為k，則該樹中葉子結(jié)點個數(shù)為_1_。 23.在無向圖g的鄰接矩陣a中，若aij等于0，則aji等于_0_。 24.兩個串是相

7、等的，當且僅當兩個串的長度相等且_對應(yīng)下標的_的字符都相同。 25.某二叉樹的后根遍歷序列為abd，中根遍歷序列為adb，則它的先根遍歷序列為_adb_。 26.先在所有的記錄中選出鍵值最小的記錄，將它與第一個記錄交換；然后在其余的記錄中再選出最小的記錄與第二個記錄交換，依此類推，直至所有記錄排序完成。這種排序方法稱為_直接選擇排序_。 27.對含有n個結(jié)點e條邊的無向連通圖，利用prim算法生成最小生成樹的時間復(fù)雜度為_ 0（n2）_。 28.對n個元素進行冒泡排序時，最少的比較次數(shù)為_n-1_。 三、應(yīng)用題(本大題共5小題，每小題6分，共30分) 29.設(shè)有編碼為a，b，c，d的4列火車，

8、依次進入一個棧式結(jié)構(gòu)的站臺，試寫出這4列火車開出站臺的所有可能的順序。 (d,c,b,a);(c,b,a,d);(b,a,d,c);(a,d,c,b)30.畫出題30圖所示的二叉樹的二叉鏈表存儲結(jié)構(gòu)。題30圖 p8031.對于題31圖，試給出： （1）鄰接矩陣； p109(m1)（2）鄰接表。 p112題31圖 32.給定表（39，14，22，8，65，28，88，29，67，13，10），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹。 33.用插入排序算法對數(shù)據(jù)序列（47，33，61，82，72，11，25，57）進行排序，寫出整個插入排

9、序的每一趟過程。(33,47)61,82,72,11,25,57(33,47,61)82,72,11,25,57(33,47,61,82)72,11,25,57(33,47,61,72,82)11,25,57(11,33,47,61,72,82)25,57(11,25,33,47,61,72,82)57(11,25,33,47,57,61,72,82)四、算法設(shè)計題(本大題共2小題，每小題7分，共14分) 34.設(shè)兩個數(shù)據(jù)元素均為整型數(shù)據(jù)的線性表a=(a1，a2，an)和b=(b1，b2，bm)。若n=m且ai=bi（i=1，2,，n）則認為a=b；若ai=bi（i=1，2,，j）且aj+1&

10、lt;bj+1，（j<nm）,則認為ab。試編寫一個比較a和b的算法，當ab時，輸出1。要求線性表的存儲結(jié)構(gòu)使用鏈接存儲。 35.設(shè)二叉樹的結(jié)點類型定義如下： typedef struct node datatype data; struct node*lchild,*rchild; bitree; bitree*t; 試編寫一個計算二叉樹深度的遞歸算法(int depth(bitree*t)。 int depth(bitree*t)if(!t)return(0);lh=depth(t->lchild);rh=depth(t->rchild);retrun lh>rh?

11、lh+1:rh+1;全國2009年1月高等教育自學(xué)考試 數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題 課程代碼：02142 一、單項選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。 1.數(shù)據(jù)的不可分割的最小標識單位是（a） a.數(shù)據(jù)項 b.數(shù)據(jù)記錄 c.數(shù)據(jù)元素 d.數(shù)據(jù)變量2. for（i=0；i<m；i+）for（j=0；j<t；j+）cij=0；for（i=0；i<m；i+）for（j=0；j<t；j+）for（k=0；k<n；k+）cij=cij+aik*bkj；上列程序的時間

12、復(fù)雜度為( c )a.o(m+n×t)b.o(m+n+t) c.o(m×n×t)d.o(m×t+n）3.若線性表最常用的操作是存取第i個元素及其前趨的值，那么最節(jié)省操作時間的存儲方式是（b） a.單鏈表 b.雙鏈表 c.單循環(huán)鏈表 d.順序表4.設(shè)單鏈表中指針p指向結(jié)點a，要刪除a之后的結(jié)點(若存在)，則修改指針的操作為（a） a.p>next=p>next>next b.p=p>next c.p=p>next>next d.p>next=p5.向一個棧頂指針為hs的鏈棧中插入一個*s結(jié)點時，應(yīng)執(zhí)行的操作為（d）

13、 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.設(shè)循環(huán)隊列的元素存放在一維數(shù)組q030中，隊列非空時，front指示隊頭元素的前一個位置，rear指示隊尾元素。如果隊列中元素的個數(shù)為11，front的值為25，則rear應(yīng)指向的元素是（b） a.q4 b.q5 c.q14 d.q157.定義二維數(shù)組a18，010，起始地址為loc，每個元素占2l個存儲單元，在以行序為主序的存儲方式下，某數(shù)據(jù)元素的地址為loc+50l，則在以列序為主

14、序的存儲方式下，該元素的存儲地址為（c） a.loc+28l b.loc+36l c.loc+50l d.loc+52l8.具有n個結(jié)點的二叉樹，擁有指向孩子結(jié)點的分支數(shù)目是（a） a.n-1 b.n c.n+1 d.2n9.對一棵有100個結(jié)點的完全二叉樹按層序編號，則編號為49的結(jié)點，它的左孩子的編號為（b） a.99 b.98 c.97 d.5010.有m個葉子結(jié)點的哈夫曼樹，其結(jié)點總數(shù)是（a） a.2m-1 b.2m c.2m+1 d.2(m+1)11.有n個結(jié)點的無向圖的邊數(shù)最多為（b） a.n+1 b.n(n-1)/2 c.n(n+1) d.2n(n+1) 12.設(shè)圖的鄰接矩陣為，

15、則該圖為（c） a.有向圖 b.無向圖 c.強連通圖 d.完全圖13.二分查找算法的時間復(fù)雜度是（d） a.o(n2) b.o(nlog2n) c.o(n) d.o(log2n)14.已知8個元素(34，76，45，18，26，54，92，65)，按照依次插入結(jié)點的方法生成一棵二叉排序樹，則該樹的深度為（a） a.4 b.5 c.6 d.715.采用排序算法對n個元素進行排序，其排序趟數(shù)肯定為n-1趟的排序方法是（c） a.插入和快速 b.冒泡和快速 c.選擇和插入 d.選擇和冒泡二、填空題(本大題共13小題，每小題2分，共26分) 請在每小題的空格中填上正確答案。錯填、不填均無分。 16.在

16、數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的存儲結(jié)構(gòu)有順序存儲方式、鏈式存儲方式、_索引_和散列存儲方式等四種。17.作為一個算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其他參數(shù)，稱為_計算量_。 18.在雙鏈表中，存儲一個結(jié)點有三個域，一個是數(shù)據(jù)域，另兩個是指針域，分別指向_前驅(qū)結(jié)點_和_后繼結(jié)點_。 19.在有n個元素的鏈隊列中，入隊和出隊操作的時間復(fù)雜度分別為_0(1)_和_0(1)_。 20.在棧結(jié)構(gòu)中，允許插入的一端稱為_棧頂_;在隊列結(jié)構(gòu)中，允許插入的一端稱為_對頭_。 21.在循環(huán)隊列中，存儲空間為0n-1。設(shè)隊頭指針front指向隊頭元素前一個空閑元素，隊尾指針指向隊尾元素，那么其隊空標志為rea

17、r=front，隊滿標志為_front=rear+1_。 22.深度為k的二叉樹至多有_2k-1_個結(jié)點，最少有_k_個結(jié)點。 23.設(shè)有一稠密圖g，則g采用_索引_存儲結(jié)構(gòu)較省空間。設(shè)有一稀疏圖g，則g采用_鏈式存儲_存儲結(jié)構(gòu)較省空間。 24.在一個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點時，在查找成功的情況下，需平均比較_（1+n）/2_個元素結(jié)點。 25.假定對線性表r059進行分塊檢索，共分為10塊，每塊長度等于6。若檢索索引表和塊均用順序檢索的方法，則檢索每一個元素的平均檢索長度為_1_。 26.文件在外存儲器上的組織結(jié)構(gòu)主要有三種：順序文件、散列文件和索引文件，其中_順序文件_特

18、別適應(yīng)磁帶存儲器，也適應(yīng)磁盤存儲器。 27.在插入排序、冒泡排序、快速排序、歸并排序等排序算法中，占用輔助空間最多的是_歸并排序_。 28.冒泡排序最好的時間復(fù)雜度為_0(n-1)_，平均時間復(fù)雜度為_0（n2）_，是一種穩(wěn)定的排序算法。 三、應(yīng)用題(本大題共5小題，每小題6分，共30分) 29.已知一棵二叉樹的前序序列是abcdefg，中序序列是cbdaegf。請構(gòu)造出該二叉樹，并給出該二叉樹的后序序列。 30.將題30圖所示的由三棵樹組成的森林轉(zhuǎn)化為一棵二叉樹。 (a,b,h,e,c,i,o,f,d,j,p,g,k,q,c,r,m,n)題30圖 31.已知某圖的鄰接表存儲結(jié)構(gòu)如題

19、31圖所示： 題31圖 (1)畫出該圖。 (2)根據(jù)該鄰接表從頂點a出發(fā)，分別寫出按深度優(yōu)先搜索法和廣度優(yōu)先搜索法進行遍歷的結(jié)點序列。深度優(yōu)先搜索法(a,b,c,e,h,g,f,d) 32.假定采用h(k)=kmod7計算散列地址，引用線性探測的開放定址法解決沖突，試在06的散列地址空間中，對關(guān)鍵字序列(38，25，74，63，52，48)構(gòu)造散列表，并求出等概率情況下查找成功的平均查找長度。 asl=333.用快速排序法對數(shù)據(jù)序列(49，38，65，97，16，53，134，27，39)進行排序，寫出其第一趟排序的全過程。(39,38,65,97,16,53,134,27,49)(

20、39,38,49,97,16,53,134,27,65)(39,38,27,97,16,53,134,49,65)(39,38,27,49,16,53,134,97,65)(39,38,27,16,49,53,134,97,65)四、算法設(shè)計題(本大題共2小題，每小題7分，共14分) 34.完善下列折半插入排序算法。 voidbinasort(structnodermaxsize，int n) for(i=2;i<=n;i+) r0=ri;low=1;high=i-1; while(low<=high) mid=(1)_(low+high)/2_; if(r0.key<rmi

21、d.key)high=(2)_mid-1_; elselow=(3)_mid+1_; for(j=i-1;j>=low;j-) (4)_rmid=rj_; rlow=r0; 35.下列算法的功能是求出指定結(jié)點在給定的二叉排序樹中所在的層次。請完善該算法。 void level(bstree root，p) intlevel=0; if(!root) (1)_return (0)_; else level+; while(root>key!=p>key) if(root>key> p>key key) (2)_level(root->lchil

22、d,p)_; else (3)_ level (root->rchild)_; level+; (4)_return(level)_; 全國2009年10月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.在表長為n的順序表上做插入運算，平均要移動的結(jié)點數(shù)為（ c ）a.n/4b.n/3c.n/2d.n2.順序表中有19個元素，第一個元素的地址為200，且每個元素占一個字節(jié)，則第14個元素的存儲地址為（ b ）a.212b.213

23、c.214d.2153.由頂點v1，v2，v3構(gòu)成的圖的鄰接矩陣為，則該圖中頂點v1的出度為（ c ）a.0b.1c.2d.34.元素的進棧次序為a，b，c，d，e，則退棧中不可能的序列是（ c ）a.a，b，c，d，eb.b，c，d，e，ac.e，a，b，c，dd.e，d，c，b，a5.由帶權(quán)為9，2，5，7的四個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（ c ）a.23b.37c.44d.466.在已知尾指針的單循環(huán)鏈表中，插入一個新結(jié)點使之成為首結(jié)點，其算法的時間復(fù)雜度為（ c ）a.o（1）b.o（log2n）c.o（n）d.o(n2)7.已知一個有序表為（13，18，24，35

24、，47，50，62，83，90，115，134），當二分查找值為90的元素時，查找成功時需比較的次數(shù)為（ b ）a.1b.2c.3d.48.在查找順序表各結(jié)點概率相等的情況下，順序按值查找某個元素的算法時間復(fù)雜度為（ b ）a.o(1)b.o(n)c.o()d.o(log2n)9.下列各項鍵值序列中不是堆的為（ c ）a.5，23，16，68，94，72，71，73b.5，16，23，68，94，72，71，73c.5，23，16，73，94，72，71，68d.5，23，16，68，73，71，72，9410.在線性表的下列存儲結(jié)構(gòu)中進行插入、刪除運算，花費時間最多的是（ a ）a.單鏈表b

25、.雙鏈表c.順序表d.單循環(huán)鏈表11.在棧中進行插入和刪除操作的一端稱為（ a ）a.棧頂b.棧底c.任意位置d.指定位置12.用n個值構(gòu)造一棵二叉排序樹，它的最大高度為（ b ）a.n/2b. nc. d.log2n13.冒泡排序的時間復(fù)雜度是（ a ）a.o(n2)b.o(nlog2n)c.o(n)d.o(log2n)14.設(shè)無向圖的鄰接表如題14圖所示，則該圖的邊數(shù)為（ b ）題14圖a.4b.5c.10d.2015.帶表頭結(jié)點鏈隊列的隊頭和隊尾指針分別為front和rear，則判斷隊空的條件為（ a ）a.front=rearb.front!=nullc.rear!=nulld.fro

26、nt=null二、填空題(本大題共13小題，每小題2分，共26分)請在每小題的空格中填上正確答案。錯填、不填均無分。16.下列程序段的時間復(fù)雜度為_0(n)_。i=0；s=0；while（i<n） i+；s=s+i；17.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、_線形結(jié)構(gòu)_、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。18.線性表中所含結(jié)點的個數(shù)稱為_表長_。19.向一個棧頂指針為top的鏈棧中插入一個新結(jié)點*p時，應(yīng)執(zhí)行_p->next=top->next_和top=p操作。20.設(shè)一個順序棧s，元素s1，s2，s3，s4，s5，s6依次進棧，如果6個元素的退棧順序為s2，s3，s4，s6，s5，s1，

27、則順序棧的容量至少為_3_。21.若滿二叉樹的結(jié)點數(shù)為n，則其高度為_log2（n+1）_。22.在一棵具有n個結(jié)點的完全二叉樹中，從樹根起，自上而下、從左到右地給所有結(jié)點編號。若編號為i的結(jié)點有父結(jié)點，那么其父結(jié)點的編號為_i/2_。23.深度為k的二叉樹，結(jié)點數(shù)最多有_2k-1_個。24.某二叉樹的后根遍歷為abkcbpm，則該二叉樹的根為_m_。25.在一個具有n個頂點的無向圖中，頂點的度最大可達_n(n-1)/2_。26.有向圖g的鄰接矩陣為a，如果圖中存在弧<vi，vj>，則aij的值為_1_。27.順序查找算法的平均查找長度為_(n+1)/2_。28.二路歸并排序的平均

28、時間復(fù)雜度為_0(nlog2n)_。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)29.某通訊電文由a，b，c，d，e，f六個字符編碼組成，每個字符編碼在電文中出現(xiàn)的次數(shù)分別是6，5，9，10，20，1，試畫出這六個字符編碼所用的哈夫曼樹。(10,20;1,5,6,9);asl=12330.已知一棵二叉樹的順序存儲結(jié)構(gòu)如題30圖所示，其中表示虛結(jié)點，試構(gòu)造該二叉樹。abgcdhef題30圖(a,b,g,c,d, ,h, , ,e,f)31.題31圖中二叉排序樹的各結(jié)點的值為19，標出各結(jié)點的值。(5,3,6,1,4,7,2,8,9)題31圖32.寫出題32圖所示的有向圖的鄰接矩陣及該圖的所

29、有拓撲排序序列。題32圖0,1,0,1,0,00,0,0,0,1,01,1,0,0,0,00,0,0,0,0,10,0,0,1,0,10,0,0,0,0,0(c,a,b,d,e,d,f)33.寫出鍵值（83，40，63，13，84，35，96，57，39，79，61，15）應(yīng)用二路歸并排序算法從小到大排序后各趟的結(jié)果。 (83),(40),(63),(13),(84),(35),(96),(57),(39),(79),(61),(15) (40,83),(13,63),(35,84),(57,96),(39,79),(15,61)(13,40,63,86),(35,57,84,96),(15,

30、39,61,79) (13,35,40,57,63,84,86,96),(15,39,61,79)(13,15,35,39,40,57,61,63,79,84,86,96)四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)34.若兩棵二叉樹b1和b2皆為空，或者皆不空且b1的左、右子樹和b2的左、右子樹分別相似，則稱二叉樹b1和b2相似。試編寫算法，判別給定兩棵二叉樹是否相似。void f34(bitreptr t1,bitreptr t2)int cont1=0,cont2=0;if(!t1&&!t2)retrun 1;while(t1->t1child|t2-&g

31、t;t2child)if(t1->lchild=t2->lchild)&&( t1->rchild=t2->rchild);else return 0;35.設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試編寫算法實現(xiàn)將x插入到順序表的適當位置上，以保持該表的有序性。void f35(sqlist l,datatype x,int i)if(l.last=maxsize)error;if(i<1)|(i>l.last-1)error;for(j=l.last;j=i;j-)l.dataj=l.dataj-1;l.datai-1=x;l.last=l.la

32、st+1;全國2010年1月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.下述文件中適合于磁帶存儲的是（ a ）a.順序文件b.索引文件c.散列文件d.多關(guān)鍵字文件2.某二叉樹的后根遍歷序列為dabec，中根遍歷序列為debac，則先根遍歷序列為（ d ）a.acbedb.becabc.deabcd.cedba3.含有n個結(jié)點的二叉樹用二叉鏈表表示時，空指針域個數(shù)為( c )a.n-1b.nc.n+1d.n+24.在一個圖中，所有頂

33、點的度數(shù)之和與圖的邊數(shù)的比是( b )a.12b.11c.21d.415.長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)頭指針，則出隊操作的時間復(fù)雜度為( c )a.o(1)b.o(1og2n)c.o(n)d.o(n2)6.下述幾種排序方法中，要求內(nèi)存量最大的是( c )a.插入排序b.快速排序c.歸并排序d.選擇排序7.對n個不同值進行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為( d )a.n-1b.nc.n+1d.n(n-1)28.對線性表進行二分查找時，要求線性表必須( c )a.以順序方式存儲b.以鏈式方式存儲c.以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列d.以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排列

34、9.在表長為n的順序表上做刪除運算，其平均時間復(fù)雜度為( a )a.o(1)b.o(n)c.o(nlog2n)d.o(n2)10.當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大容量為( b )a.n-2b.n-1c.nd.n+111.有關(guān)插入排序的敘述，錯誤的是( c )a.插入排序在最壞情況下需要o(n2)時間b.插入排序在最佳情況可在o(n)時間內(nèi)完成c.插入排序平均需要o(nlog2n)時間d.插入排序的空間復(fù)雜度為o(1)12.有關(guān)樹的敘述正確的是( b )a.每一個內(nèi)部結(jié)點至少有一個兄弟b.每一個葉結(jié)點均有父結(jié)點c.有的樹沒有子樹d.每個樹至少有一個根結(jié)點與一個葉結(jié)點。13.循

35、環(huán)隊列存儲在數(shù)組元素a0至am中，則入隊時的操作為( d )a.rear=rear+1b.rear=(rear+1)(m-1)c.rear=(rear+1)md.rear=(rear+1)(m+1)14.關(guān)于串的的敘述，不正確的是( b )a.串是字符的有限序列b.空串是由空格構(gòu)成的串c.替換是串的一種重要運算d.串既可以采用順序存儲，也可以采用鏈式存儲15.對稱矩陣ann，a11為首元素，將下三角(包括對角線)元素以行優(yōu)先順序存儲到一維數(shù)組元素t1至tn(n+1)2中，則任一上三角元素aij存于tk中，下標k為( a )a.i(i-1)2+jb.j(j-1)2+ic.i(j-i)2+1d.j

36、(i-1)2+l二、填空題(本大題共13小題，每小題2分，共26分)請在每小題的空格中填上正確答案。錯填、不填均無分。16.下列程序段的時間復(fù)雜度為_0(n3)_。for(i=1；i<=n；i+)for(j=1；j<=n；j+)for(k=1；k<=n；k+)s=i+j+k；17.在數(shù)據(jù)結(jié)構(gòu)中，各個結(jié)點按邏輯關(guān)系互相纏繞，任意兩個結(jié)點可以鄰接的結(jié)構(gòu)稱為_圖狀結(jié)構(gòu)_。18.在單鏈表中，存儲每個結(jié)點有兩個域，一個是數(shù)據(jù)域，另一個是指針域，指針域指向該結(jié)點_后繼結(jié)點_的。19.在棧結(jié)構(gòu)中，允許插入的一端稱為_棧頂_。20.從一個長度為n的順序表中刪除第i個元素(1in)時，需向前移

37、動_n-1+1_個元素。21.一個棧的輸入序列是1，2，3，n，輸出序列的第一個元素是n，則第i個輸出元素為_n-i+1_。22.循環(huán)隊列被定義為結(jié)構(gòu)類型，含有三個域：data、front和rear，則循環(huán)隊列sq為空的條件是_sq.front=sq.rear_。23.一個10階對稱矩陣a，采用行優(yōu)先順序壓縮存儲上三角元素，a00為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a45的地址為_19_。24.對于一棵滿二叉樹，若有m個葉子，則樹中結(jié)點數(shù)為_2m-1_。25.含有n個頂點和n-1條邊的連通圖g采用_鄰接矩陣_存儲結(jié)構(gòu)較省空間。26.在圖中，第一個頂點和最后一個頂點相同

38、的路徑稱為_連通圖_。27.動態(tài)查找中兩個元素x，y存入同一個散列表時，x、y鍵值相同，則這種情況稱為_沖突_。28.堆排序需_1_個記錄大小的輔助存儲空間。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)29.有一字符串的次序為-3*y+ay！2，試利用棧將輸出次序改變?yōu)?y*-ay！2+，試寫出進棧和退棧的操作步驟。(用push(x)表示x進棧，pop(x)表示x退棧)push(-3);pop(3);push(*y);pop(-*y);push(+a);pop(a);push(/y);pop(y);push(!);pop(!);push(2);pop(/2);pop(+);30.已知一棵

39、二叉樹的先根遍歷序列為abcdeghf，中根遍歷序列為cbedagfh，畫出該二叉樹。(a,b,g,c,d,h,e,f)31.題31圖中二叉排序樹的各結(jié)點的值為3240，標出各結(jié)點的值。題31圖(36,32,38,35,37,33,39,34,40)32.下述矩陣表示一個無向網(wǎng)，畫出該無向網(wǎng)，并構(gòu)造出其最小生成樹。(1,3,2,5,6,4)33.什么是堆?寫出對應(yīng)于序列(10，20，7，75，41，67，3，9，30，45)的初始堆(堆頂元素取最小值)。堆是一鍵值序列k1,k2,kn,對所有i=1,2,n/2，滿足ki<k(2i)且ki<k(2i+1)的序列。(3,9,10,20,

40、41,67,775,30,45)四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)34.二叉樹按二叉鏈表形式存儲，編寫一個算法判別給定的二叉樹是否為完全二叉樹。void countleaf(bitreptr t)int count=0;if(!t)if(t->lchild)count+;if(t->rchild)count+;countleaf(l->lchild,count):countleaf(l->rchild,count):return （count+1）;void f34(list l)int i=0;n=countleaf(t);while(l->

41、next)i+;l=l->next;if(i=n)return 1;return 0;35.試寫出直接插入排序算法。void straightsort(list r)for(i=2;i=n;i+)r0=ri;j=i-1;while(r0.key<rj.key)rj+1=rj;j-;rj+1=r0;全國2007年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1關(guān)于棧和隊列的說法中正確的是（ ）a棧和隊列都是線性結(jié)構(gòu)

42、b.棧是線性結(jié)構(gòu)，隊列不是線性結(jié)構(gòu)c.棧不是線性結(jié)構(gòu)，隊列是線性結(jié)構(gòu)d.棧和隊列都不是線性結(jié)構(gòu)2關(guān)于存儲相同數(shù)據(jù)元素的說法中正確的是（ ）a順序存儲比鏈式存儲少占空間b.順序存儲比鏈式存儲多占空間c.順序存儲和鏈式存儲都要求占用整塊存儲空間d.鏈式存儲比順序存儲難于擴充空間3從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為0個或1個的數(shù)據(jù)結(jié)構(gòu)只能是（ ）a線性結(jié)構(gòu)b.樹形結(jié)構(gòu)c.線性結(jié)構(gòu)和樹型結(jié)構(gòu)d.線性結(jié)構(gòu)和圖狀結(jié)構(gòu)4已知一個單鏈表中，指針q指向指針p的前趨結(jié)點，若在指針q所指結(jié)點和指針p所指結(jié)點之間插入指針s所指結(jié)點，則需執(zhí)行（ ）aqnext=s；pnext=s；b.qnext=s；snext=p；

43、c.qnext=s；qnext=p；d.qnext=s；snext=q；5在長度為n的線性表中刪除一個指針p所指結(jié)點的時間復(fù)雜度是（ ）ao(n)b.o(1)c.o(log2n)d.o(n2)6設(shè)一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現(xiàn)的是（ ）aa，b，c，db.a，b，d，cc.d，c，b，ad.c，d，a，b7關(guān)于串的敘述中，正確的是（ ）a空串是只含有零個字符的串b.空串是只含有空格字符的串c.空串是含有零個字符或含有空格字符的串d.串是含有一個或多個字符的有窮序列8在具有m個單元的循環(huán)隊列中，隊頭指針為front，隊尾指針為rear，則隊滿

44、的條件是（ ）afront=rearb.(front+1)%m=rearc.rear+1=frontd.(rear+1)%m=front9設(shè)有二維數(shù)組ann表示如下：， 則aii（0in-1）的值為（ ）ai*(i-1)/2b.i*(i+1)/2c.(i+2)*(i+1)/2d.i2/210高度為h的完全二叉樹中，結(jié)點數(shù)最多為（ ）a2h-1b.2h+1c.2h-1d.2h11由m棵結(jié)點數(shù)為n的樹組成的森林，將其轉(zhuǎn)化為一棵二叉樹，則該二叉樹中根結(jié)點的右子樹上具有的結(jié)點個數(shù)是（ ）amnb.mn-1c.n(m-1)d.m(n-1)12在一個具有n個頂點的無向圖中，每個頂點度的最大值為（ ）anb

45、.n-1c.n+1d.2(n-1)13關(guān)于無向圖的鄰接矩陣的說法中正確的是（ ）a矩陣中非全零元素的行數(shù)等于圖中的頂點數(shù)b.第i行上與第i列上非零元素總和等于頂點vi的度數(shù)c.矩陣中的非零元素個數(shù)等于圖的邊數(shù)d.第i行上非零元素個數(shù)和第i列上非零元素個數(shù)一定相等14設(shè)一組記錄的關(guān)鍵字key值為62，50，14，28，19，35，47，56，83，散列函數(shù)為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點個數(shù)是（ ）a1b.23d.415設(shè)有一組初始關(guān)鍵字值序列為（49，81，55，36，44，88），則利用快速排序的方法，以第一個關(guān)鍵字值為基準得到的一次劃分為（ ）

46、a36，44，49，55，81，88b.44，36，49，55，81，88c.44，36，49，81，55，88d.44，36，49，55，88，81二、填空題(本大題共13小題，每小題2分，共26分)請在每小題的空格中填上正確答案。錯填、不填均無分。16在數(shù)據(jù)結(jié)構(gòu)中，各個結(jié)點按邏輯關(guān)系互相纏繞，任意兩個結(jié)點可以鄰接的結(jié)構(gòu)稱為_。17每個存儲結(jié)點只含一個數(shù)據(jù)元素，所有存儲結(jié)點連續(xù)存放。此外增設(shè)一個索引表，索引表中的索引指示各存儲結(jié)點的存儲位置或位置區(qū)間端點。按這種方式組織起來的存儲結(jié)構(gòu)稱為_。18在順序表上讀表元算法的時間復(fù)雜度為_。19雙鏈表中前驅(qū)指針為prior，后繼指針為next，在指針

47、p所指結(jié)點前插入指針s所指的結(jié)點，需執(zhí)行下列語句：snext=p;sprior=pprior;pprior=s;_;20設(shè)數(shù)組a0.80.8的起始元素位置為a，每個元素占2 l個存儲單元，按行序為主序存儲。若元素aij的存儲位置為a+66 l，則元素aji的存儲位置為_。21有4個結(jié)點且深度為4的二叉樹的形態(tài)共有_種。22某二叉樹的先根遍歷序列為ijklmno，中根遍歷序列為jlkinmo，則該二叉樹中根結(jié)點的右孩子是_。23第一個頂點和最后一個頂點相同的路徑稱為回路或者環(huán)，除第一個頂點和最后一個頂點外，其余頂點都不重復(fù)的回路，稱為_。24一個具有10個頂點的完全無向圖中有_條邊。25一棵平衡

48、二叉樹中任一結(jié)點的平衡因子只可能是_。26二分查找的時間復(fù)雜度為_。27二路歸并排序算法的時間復(fù)雜度為_。28文件的基本存取單位是_。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)29有一字符串序列為5*-x-y/x+2，利用棧的運算將其輸出結(jié)果變?yōu)?x-*yx+/-2，試寫出該操作的入棧和出棧過程（采用push(a)表示a入棧，pop(a)表示a出棧）。30某二叉樹的先根遍歷序列為abijcdfghe，中根遍歷序列為ijbadgfhce，試畫出該二叉樹，并寫出它的后序遍歷序列。31用冒泡排序算法對數(shù)據(jù)序列（49，38，65，97，76，134，27，49）進行排序，寫出整個冒泡排序的每一

49、趟過程。32題32圖所示二叉樹是否為平衡二叉樹？若是，說明理由；若不是，將其轉(zhuǎn)換為平衡二叉樹。題32圖33已知連通網(wǎng)的鄰接矩陣a=， 試畫出它所表示的連通網(wǎng)并畫出該連通網(wǎng)的最小生成樹。四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)34設(shè)單鏈表的結(jié)點結(jié)構(gòu)如下：struct nodedatatype data;struct node*next;試編寫一個函數(shù)int count(struct node *head,datatype x)統(tǒng)計單鏈表中數(shù)據(jù)域為x的結(jié)點個數(shù)。35試寫出直接插入排序算法。全國2007年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項選擇題(本大題共

50、15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成( )a.線性結(jié)構(gòu)和非線性結(jié)構(gòu)b.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)c.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)d.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2.for（i=0；i<m；i+）for（j=0；j<n；j+）aij=i*j；上面算法的時間復(fù)雜度為( )a.o(m2)b.o(n2)c.o(m×n)d.o(m+n）3.設(shè)順序表有9個元素，則在第3個元素前插入一個元素所需移動元素的個數(shù)為( )a.5b.6c.7d.94.設(shè)p為指向雙向循環(huán)鏈表中某個結(jié)點的指針，p所指向的結(jié)點的兩個鏈域分別用pllink和prlink表示，則同樣表示p指針所指向結(jié)點的表達式是( )a.pllink b.prlinkc.pllinkllinkd.pllinkrlink5.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的存儲地址是( )a. 110b. 108c. 100d. 1206.設(shè)有一個棧，按a、b、c、d的順序進棧，則可能為出棧序列的是( )a.dcbab.cdabc.dbac d.dcab7.在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top為棧頂指針，則當做出