工學(xué)到自考數(shù)據(jù)結(jié)構(gòu)試題和答案

1、全國2001年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331第一部分選擇題(30分)一、 單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。1算法指的是（ D ） A計(jì)算機(jī)程序 B解決問題的計(jì)算方法 C排序算法 D解決問題的有限運(yùn)算序列2線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（ B ） A必須是不連續(xù)的 B連續(xù)與否均可 C必須是連續(xù)的 D和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)3將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（ C） AO（1） BO（n） CO（m） DO（m+n）4由兩個(gè)棧

2、共享一個(gè)向量空間的好處是：（ D ） A減少存取時(shí)間，降低下溢發(fā)生的機(jī)率 B節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率 C減少存取時(shí)間，降低上溢發(fā)生的機(jī)率 D節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率5設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（ B ） Afront=front+1 Bfront=(front+1)%(m-1)Cfront=(front-1)%m Dfront=(front+1)%m6如下陳述中正確的是（ A ） A串是一種特殊的線性表 B串的長(zhǎng)度必須大于零 C串中元素只能是字母 D空串就是空白串7若目標(biāo)串的長(zhǎng)度為

3、n，模式串的長(zhǎng)度為n/3，則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是（ C ） AO（）BO（n）CO（n2）DO（n3）8一個(gè)非空廣義表的表頭（ D ） A不可能是子表 B只能是子表 C只能是原子 D可以是子表或原子9假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表02335 對(duì)應(yīng)的稀疏矩陣是（ A ）10在一棵度為3的樹中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2 的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為( C ) A4 B5 C6 D711在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中,零元素的個(gè)數(shù)為( D ) Ae B2e Cn2e Dn22e12假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示,則刪除

4、與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是( C ) AO(n) BO(e)CO(n+e) DO(n*e)13用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ D ） A選擇排序 B希爾排序 C歸并排序 D快速排序14適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（ C ）A有序表 B分塊有序表 C三叉排序樹 D線性鏈表15不定長(zhǎng)文件是指（ B ）A文

5、件的長(zhǎng)度不固定 B記錄的長(zhǎng)度不固定C字段的長(zhǎng)度不固定 D關(guān)鍵字項(xiàng)的長(zhǎng)度不固定第二部分 非選擇題（共70分）二、填空題（本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯(cuò)填或不填均無分。16數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。17在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為head=p->next->next。18棧頂?shù)奈恢檬请S著進(jìn)棧和退棧操作而變化的。19在串S=“structure”中，以t為首字符的子串有12個(gè)。20假設(shè)一

6、個(gè)9階的上三角矩陣A按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，其中B0存儲(chǔ)矩陣中第1個(gè)元素a1,1,則B31中存放的元素是。21已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有個(gè)葉子結(jié)點(diǎn)。22已知一個(gè)圖的廣度優(yōu)先生成樹如右圖所示，則與此相應(yīng)的廣度優(yōu)先遍歷序列為 abefcdg。23在單鏈表上難以實(shí)現(xiàn)的排序方法有快速排序和堆排序。24在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為2。25多重表文件和倒排文件都?xì)w屬于多關(guān)鍵字文件。三、解答題（本大題共4小題，每小題5分，共20分）26畫出下列廣義表的共享結(jié)構(gòu)圖形表示 P=（z）,(x,y)）,(x,y

7、),x),(z)）27請(qǐng)畫出與下列二叉樹對(duì)應(yīng)的森林。28已知一個(gè)無向圖的頂點(diǎn)集為a,b,c,d,e ,其鄰接矩陣如下所示ab cde(1)畫出該圖的圖形； （2）根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。29已知一個(gè)散列表如下圖所示：3520334859 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函數(shù)為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為：hi=(h(key)+*h1(key)%m =0,1,，m1其中h1(key)=key%11+1回答下列問題：（1）對(duì)表中關(guān)鍵字35，20，33和48進(jìn)行查找時(shí)，所需進(jìn)行

8、的比較次數(shù)各為多少？（2）該散列表在等概率查找時(shí)查找成功的平均查找長(zhǎng)度為多少？四、算法閱讀題（本大題共4小題，每小題5分，共20分）30下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為： comstr(s1,s2)=請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。int comstr(LinkString s1,LinkString s2) /s1和s2為兩個(gè)鏈串的頭指針 while(s1&&s2) if(s1>date<s2>date)return1； if(s1>date>s2>date)return1； if()return1； if()return1； 31

9、閱讀下面的算法 LinkList mynote(LinkList L) /L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L->next) q=L；L=L>next；p=L； S1： while(p>next) p=p>next； S2： p>next=q；q>next=NULL； return L； 請(qǐng)回答下列問題： （1）說明語句S1的功能； （2）說明語句組S2的功能； （3）設(shè)鏈表表示的線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表。32假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間（參見右下圖）， 其類型Queue2定義如下：t

10、ypedef struct DateType dataMaxSize；int front2,rear2；Queue2；對(duì)于i=0或1，fronti和reari分別為第i個(gè)隊(duì)列的頭指針和尾指針。請(qǐng)對(duì)以下算法填空，實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。int EnQueue (Queue2*Q,int i,DateType x) /若第 i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1；否則返回0if(i<0|i>1)return 0； if(Q>reari=Q>frontreturn0； Q>data=x； Q>reari=; return1； 33已知二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，

11、閱讀下面算法。 typedef struct node DateType data；Struct node * next； ListNode；typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inorder (BinTree T) LinkList s； If(T) Inorder(T>lchild)； If (!T>lchild)&&(!T>rchild) s=(ListNode*)malloc(sizeof(ListNode)； s>data=T>data；s>next=

12、Leafhead； Leafhead=s； Inorder(T>rchild)； 對(duì)于如下所示的二叉樹（1）畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)； （2）說明該算法的功能。五、算法設(shè)計(jì)題（本題共10分）34閱讀下列函數(shù)arrange() int arrange(int a,int 1,int h,int x) /1和h分別為數(shù)據(jù)區(qū)的下界和上界int i,j,t； i=1；j=h； while(i<j) while(i<j && aj>=x)j-； while(i<j && aj>=x)i+； if(i<j) t=aj；aj=a

13、i；ai=t； if(ai<x) return i； else return i1； （1）寫出該函數(shù)的功能； （2）寫一個(gè)調(diào)用上述函數(shù)實(shí)現(xiàn)下列功能的算法：對(duì)一整型數(shù)組bn中的元素進(jìn)行重新排列，將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將所有正數(shù)均調(diào)整到數(shù)組的高下標(biāo)端，若有零值，則置于兩者之間，并返回?cái)?shù)組中零元素的個(gè)數(shù)。全國2001年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題參考答案課程代碼：02331一、 單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分） 1D，101112131415二、填空題（本大題共10小題，每小題2分，共20分）16存儲(chǔ)（或存儲(chǔ)結(jié)構(gòu)）17.pnextnext18進(jìn)棧和退棧1

14、91220a4,82138422abefcdg23快速排序、堆排序、希爾排序2425.多關(guān)鍵字三、解答題（本大題共4小題，每小題5分，共20分）26圖1 圖22728該圖的圖形為： 深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc29（）對(duì)關(guān)鍵字35、20、33和48進(jìn)行查找的比較次數(shù)為、； （）平均查找長(zhǎng)度四、算法閱讀題（本大題共4小題，每小題5分，共20分）30S1=S1>nexts2=s2>nexts2(或s2!=NULL或s2&&!s1)s1(或s1!=NULL或s1&&!s2)return 031.（1）查詢鏈表的尾結(jié)點(diǎn) （2）

15、將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn) （3）返回的線性表為（a2,a3,an,a1）32.(i1)%2(或1i)Q>reari(Q>reari)%Maxsize33.(1)LeafheadFHGD （2）中序遍歷二叉樹，按遍歷序列中葉子結(jié)點(diǎn)數(shù)據(jù)域的值構(gòu)建一個(gè)以Leafhead為頭指針的逆序單鏈表（或按二叉樹中葉子結(jié)點(diǎn)數(shù)據(jù)自右至左鏈接成一個(gè)鏈表）。五、算法設(shè)計(jì)題（本題共10分） 34（1）該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a中的元素并返回分界值i，使所有x的元素均落在a1.i上，使所有x的元素均落在ai1.h上。 （2）int f(int b,int n) 或 int f(int

16、b,int n) int p,q； int p,q； p=arrange(b,0,n1,0)； p=arrange(b,0,n1,1)； q= arrange(b,p+1,n1,1)； q= arrange(b,0,p,0)； return qp； return pq； 2003.1數(shù)據(jù)結(jié)構(gòu)試題 一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分。在每小題的四個(gè)備選答案中，選出一個(gè)正確答案，并將正確答案的序號(hào)填在題干的括號(hào)內(nèi)) 1.下面程序段的時(shí)間復(fù)雜度是( D ) for(i=0;i&lt;n;i+) for(j=1;j&lt;m;j+) Aij=0； A.O(n) B.

17、O(m+n+1) C.O(m+n) D.O(m*n)2.在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)“刪除x的后繼”的語句是( B ) A.p=p-&gt;next; B.p-&gt;next=p-&gt;next-&gt;next;C.p-&gt;next=p; D.p=p-&gt;next-&gt;next; 3.在頭指針為head且表長(zhǎng)大于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若p-&gt;next-&gt;next= head,則( D ) A.p指向頭結(jié)點(diǎn) B.p指向尾結(jié)點(diǎn) C.*p的直接后繼是頭結(jié)點(diǎn) D.*P

18、的直接后繼是尾結(jié)點(diǎn)4.判定“帶頭結(jié)點(diǎn)的鏈隊(duì)列為空”的條件是( C ) A.Q.front=NULL B.Q.rear=NULL C.Q.front=Q.rear D.Q.front!=Q.rear5.設(shè)有兩個(gè)串T和P，求P在T中首次出現(xiàn)的位置的串運(yùn)算稱作( D ) A.聯(lián)接 B.求子串 C.字符定位 D.子串定位6.廣義表A=(a,(b),(),(c,d,e)的長(zhǎng)度為( A ) A.4 B.5 C.6 D.77.一棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為( C ) A.3 B.4 C.5 D.6 8.已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為( D ) A.DEBAFC

19、 B.DEFBCA C.DEBCFA D.DEBFCA9.無向圖中一個(gè)頂點(diǎn)的度是指圖中( B ) A.通過該頂點(diǎn)的簡(jiǎn)單路徑數(shù) B.與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)C.通過該頂點(diǎn)的回路數(shù) D.與該頂點(diǎn)連通的頂點(diǎn)數(shù) 10.已知一個(gè)圖如下所示，從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先遍歷可能得到的序列為( C ) A.a c e f b d B.a c b d f e C.a c b d e f D.a c d b f e 11.在下列排序方法中，平均時(shí)間性能為O(nlogn)且空間性能最好的是( B ) A.快速排序 B.堆排序 C.歸并排序 D.基數(shù)排序 12.已知一組關(guān)鍵字為25,48,36,72,79,82,23,4

20、0,16,35，其中每相鄰兩個(gè)為有序子序列。對(duì)這些子序列進(jìn)行一趟兩兩歸并的結(jié)果是( A ) A.25,36,48,72,23,40,79,82,16,35 B.25,36,48,72,16,23,40,79,82,35 C.25,36,48,72,16,23,35,40,79,82 D.16,23,25,35,36,40,48,72,79,82 13.設(shè)順序存儲(chǔ)的線性表共有123個(gè)元素，按分塊查找的要求等分成3塊。若對(duì)索引表采用順序查找來確定塊，并在確定的塊中進(jìn)行順序查找，則在查找概率相等的情況下，分塊查找成功時(shí)的平均查找長(zhǎng)度為( B ) A.21 B.23 C.41 D.62 14.索引非順

21、序文件的特點(diǎn)是( A ) A.主文件無序，索引表有序 B.主文件有序，索引表無序 C.主文件有序，索引表有序 D.主文件無序，索引表無序 15.倒排文件的主要優(yōu)點(diǎn)是( C ) A.便于進(jìn)行插入和刪除運(yùn)算 B.便于進(jìn)行文件的恢復(fù) C.便于進(jìn)行多關(guān)鍵字查詢 D.節(jié)省存儲(chǔ)空間 二、填空題(本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分) 16.抽象數(shù)據(jù)類型的特點(diǎn)是將_數(shù)據(jù)_和_運(yùn)算_封裝在一起，從而現(xiàn)實(shí)信息隱藏。 17.從順序表中刪除一個(gè)元素時(shí)，表中所有在被刪元素之后的元素均需_前移_一個(gè)位置。 18.在隊(duì)列中，允許進(jìn)行插入操作的一端稱為_隊(duì)尾_，允許進(jìn)行刪除操作的一端稱為_隊(duì)頭

22、_。 19.如圖兩個(gè)棧共享一個(gè)向量空間，top1和top2分別為指向兩個(gè)棧頂元素的指針，則“棧滿” 的判定條件是_top1=top2-1_。 20.設(shè)S1=&quot;good&quot;,S2=&quot; &quot;,S3=&quot;book&quot;，則S1，S2和S3依次聯(lián)接后的結(jié)果是_ good book_。 21.假設(shè)三維數(shù)組A1098按行優(yōu)先順序存儲(chǔ)，若每個(gè)元素占3個(gè)存儲(chǔ)單元，且首地址為100，則元素A987的存儲(chǔ)地址是_2257_。 22.已知在一棵含有n個(gè)結(jié)點(diǎn)的樹中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)，則該樹中含有的葉

23、子結(jié)點(diǎn)的數(shù)目為_（(n-1)/k）*(k-1)+1_或 n - (n-1)/k_。 23.能夠成功完全拓?fù)渑判虻膱D一定是一個(gè)_有向無環(huán)圖_。 24.如果在排序前，關(guān)鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用_堆排序_較為適當(dāng)。 25.假設(shè)哈希表的表長(zhǎng)為m，哈希函數(shù)為H(key)，若用線性探查法解決沖突，則探查地址序列的形式表達(dá)為_hi=(H(key)+I)/m_。 三、解答題(本大題共4小題，每小題5分，共20分) 26.假設(shè)通信電文使用的字符集為a,b,c,d,e,f，名字符在電文中出現(xiàn)的頻度分別為：34，5，12，23，8，18，試為這6個(gè)字符設(shè)計(jì)哈夫曼編碼。請(qǐng)先畫出你所

24、構(gòu)造的哈夫曼樹(要求樹中左孩子結(jié)點(diǎn)的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值)，然后分別寫出每個(gè)字符對(duì)應(yīng)的編碼。27.已知一個(gè)圖如下所示，其頂點(diǎn)按a、b、c、d、e、f順序存放在鄰接表的頂點(diǎn)表中，請(qǐng)畫出該圖的鄰接表，使得按此鄰接表進(jìn)行深度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbefd，進(jìn)行廣度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbdfe。答案：28.已知兩個(gè)4×5的稀疏矩陣的三元組表分別如下： 0 1 4 16 0 1 1 32 1 2 2 18 1 2 2 22 2 3 4 25 2 2 5 69 3 4 2 28 3 3 4 25 4 4 2 51 請(qǐng)畫出這兩個(gè)稀疏矩陣之和的三元組表。 解: 29.從空樹起，

25、依次插入關(guān)鍵字40，8，90，15，62，95，12，23，56，32，構(gòu)造一棵二叉排序樹。 (1)畫出該二叉排序樹 (2)畫出刪去該樹中元素值為90的結(jié)點(diǎn)之后的二叉排序樹。四、算法閱讀題(本大題共4小題，每小題5分，共20分) 30.如圖所示，利用同一循環(huán)向量空間實(shí)現(xiàn)兩個(gè)隊(duì)列，其類型Queue2定義如下： typedef struct DataType dataMaxSize; int front2,length2; Queue2; 對(duì)于i=0或1,fronti和lengthi分別為第i個(gè)隊(duì)列的頭指針和長(zhǎng)度域。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，實(shí)現(xiàn)第i個(gè)循環(huán)隊(duì)列的入隊(duì)操作。 int EnQueue(

26、Queue2*Q,int i,DataType x) /若第i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1，否則返回0if(i&lt;0|i&gt;1)return 0; if( (1) ) return 0; Q-&gt;data (2) =x; Q-&gt;length (3) +; return 1; 解: (1) (Q-&gt;fronti+Q-&gt;lengthi%Maxsize=Q-&gt;front(i+1)%2 (2) (Q-&gt;fronti+-&gt;lengthi%Maxsize (3) I 31.某二叉

27、樹的線索鏈表存儲(chǔ)結(jié)構(gòu)如圖(b)所示，其中p為指向根結(jié)點(diǎn)的指針，圖(a)為結(jié)點(diǎn)結(jié)構(gòu)。閱讀下列算法，并回答問題：(1)寫出執(zhí)行函數(shù)調(diào)用f(p)的輸出結(jié)果； (2)簡(jiǎn)述函數(shù)f的功能。 void f(BinThrTree t) while(t) printf(t-&gt;data); if(t-&gt;lchild) t=t-&gt;lchild; else t=t-&gt;rchild; 答案（1）ABDFCEGH (2) 先根遍歷32.下列函數(shù)FindCycle(G,i)的功能是，對(duì)一個(gè)采用鄰接表作存儲(chǔ)結(jié)構(gòu)的有向圖G，利用深度優(yōu)先搜索策略尋找一條經(jīng)過頂點(diǎn)vi的簡(jiǎn)單回

28、路。數(shù)組cycle_path用于保存搜索過程中形成的回路，cycle_pathk=j(j0)表示在回路中頂點(diǎn)vk的下一個(gè)頂點(diǎn)是vj。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。 vertex firstedge 已知鄰接表的頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為： adjvex next 邊表結(jié)點(diǎn)EdgeNode結(jié)構(gòu)為： int cycle_pathMaxNum; int FindCycle(ALGraph*G,int i) /若回路存在，則返回1，否則返回0 int j; for(j=0;j&lt;G-&gt;n;j+)cycle_pathj=-1; return DFSPath(G,i,i

29、); int DFSPath(ALGraph*G,int j,int i) EdgeNode *p; int cycled=0; for(p=G-&gt;adjlistj.firstedge;p&&!cycled;p=p-&gt;next) cycle_pathj=p-&gt;adjvex; if( (1 ) )cycled=1;/已找到回路 else if(cycle_pathp-&gt;adjvex=-1)cycled= (2) ; return (3) (1) (2) (3) 32題答案： （1）p-&gt;adjvex=i (2)

30、DFSpath(G,p-&gt;adjvex,i) (3)cycled33.閱讀下列函數(shù)algo,并回答問題。 (1)假設(shè)整型數(shù)組A1.8中的元素依次為(3，8，9，1，7，4，2，6)。執(zhí)行函數(shù)調(diào)用algo(A,8)時(shí)，外層while的循環(huán)體執(zhí)行多少次?函數(shù)的返回值是多少? (2)簡(jiǎn)述函數(shù)algo(L,n)的功能。 int algo(int L,intn) int i=0,j,s=1,t=n; while (i!=(n+1)/2) int x=Ls； i=s;j=t; while(i&lt;j) while(i&lt;j && Lj&gt;=x

31、)j-; Li=Lj; while(i&lt;j && Li&lt;=x)i+; Lj=Li; Li=x; if(i&lt;(n+1)/2)s=i+1; else t=i-1; if(i=0)return 0; else return Li; (1) (2) (3) 33題答案： （1）外循環(huán)執(zhí)行4次，函數(shù)返回值為3。 （2）將A1至A8中不小于A1的元素進(jìn)行遞增排序，如調(diào)用algo(A,8)時(shí)最終排序結(jié)果為2 1 3 4 6 7 8 9 五、算法設(shè)計(jì)題(本大題共10分) 34.假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表作非遞減有序線性表的存儲(chǔ)結(jié)構(gòu)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度

32、為O(n)的算法，刪除表中所有數(shù)值相同的多余元素，并釋放結(jié)點(diǎn)空間。例如： (7，10，10，21，30，42，42，42，51，70) 經(jīng)算法操作后變?yōu)?(7，10，21，30，42，51，70) 34題答案： Exam4(Linklist,L) listnode *p,*q; p=L-&gt;next; while(p!=L)q=p-&gt;next; while(q&&q-&gt;data=p-&gt;data) p-&gt;next=q-&gt;next; free(q); q=p-&gt;next; p-&

33、gt;next; 2003年10月全國數(shù)據(jù)結(jié)構(gòu)試題（2006-7-25 2:07:00）1.計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為(   b   )A.數(shù)據(jù)                            B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)  

34、;                      D.數(shù)據(jù)類型2.在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度是(  b    )A.O(1)             

35、               B.O(n)C.O(nlogn)                        D.O(n2)3.隊(duì)和棧的主要區(qū)別是(  d   

36、 )A.邏輯結(jié)構(gòu)不同                            B.存儲(chǔ)結(jié)構(gòu)不同C.所包含的運(yùn)算個(gè)數(shù)不同                &

37、#160;   D.限定插入和刪除的位置不同4.鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是(  d    )A.插入操作更加方便                        B.刪除操作更加方便C.不會(huì)出現(xiàn)下溢的情況     

38、               D.不會(huì)出現(xiàn)上溢的情況5.采用兩類不同存儲(chǔ)結(jié)構(gòu)的字符串可分別簡(jiǎn)稱為(   b   )A.主串和子串                      

39、;      B.順序串和鏈串C.目標(biāo)串和模式串                        D.變量串和常量串6.在目標(biāo)串T0.n-1=xwxxyxy中，對(duì)模式串P0.m-1=xy進(jìn)行子串定位操作的結(jié)果是(  c    )A.0

40、0;                       B.2C.3                        D.57.已知廣義表

41、的表頭為a，表尾為(b,c)，則此廣義表為(  b    )A.(a,(b,c)                        B.(a,b,c)C.(a),b,c)           &

42、#160;            D.(a,b,c)8.二維數(shù)組A按行優(yōu)先順序存儲(chǔ)，其中每個(gè)元素占1個(gè)存儲(chǔ)單元。若A11的存儲(chǔ)地址為420，A33的存儲(chǔ)地址為446，則A55的存儲(chǔ)地址為(   c   )A.470                 &

43、#160;      B.471C.472                        D.4739.二叉樹中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為(   d   )A.8      

44、0;                  B.15C.16                        D.3210.下列編碼中屬前綴碼的是(  a 

45、   )A.1,01,000,001                        B.1,01,011,010C.0,10,110,11                

46、         D.0,1,00,1111.如果某圖的鄰接矩陣是對(duì)角線元素均為零的上三角矩陣，則此圖是(    d  )A.有向完全圖                        B.連通圖C.強(qiáng)連通圖&#

47、160;                       D.有向無環(huán)圖12.對(duì)n個(gè)關(guān)鍵字的序列進(jìn)行快速排序，平均情況下的空間復(fù)雜度為(    d  )A.O(1)            

48、60;           B.O(logn)C.O(n)                        D.O(n logn)13.對(duì)表長(zhǎng)為n的順序表進(jìn)行順序查找，在查找概率相等的情況下，查找成功的平均查找長(zhǎng)度為(  

49、 n/2   )A.                         B. C.                  &#

50、160;     D.n14.對(duì)于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是(  d    )A.35和41                        B.23和39C.15和44    &

51、#160;                   D.25和5115.稠密索引是在索引表中(      )A.為每個(gè)記錄建立一個(gè)索引項(xiàng)           B.為每個(gè)頁塊建立一個(gè)索引項(xiàng)C.為每組記錄建立一個(gè)索引項(xiàng)  

52、60;        D.為每個(gè)字段建立一個(gè)索引項(xiàng)二、填空題（每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分）16.當(dāng)問題的規(guī)模n趨向無窮大時(shí)，算法執(zhí)行時(shí)間T(n)的數(shù)量級(jí)被稱為算法的_(_時(shí)間復(fù)雜度_)_。17.在鏈表的結(jié)點(diǎn)中，數(shù)據(jù)元素所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)量之比稱作_(存儲(chǔ)密度)_。date next18.已知鏈棧的結(jié)點(diǎn)結(jié)構(gòu)為             棧頂指針為

53、top，則實(shí)現(xiàn)將指針p所指結(jié)點(diǎn)插入棧頂?shù)恼Z句依次為_和_。19.空串的長(zhǎng)度是_0_；空格串的長(zhǎng)度是_(空格的數(shù)目_)_。20.假設(shè)一個(gè)6階的下三角矩陣B按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組A中，其中A0存儲(chǔ)矩陣的第一個(gè)元素b11,則A14存儲(chǔ)的元素是_b63_。21.在一棵度為3的樹中，度為2的結(jié)點(diǎn)個(gè)數(shù)是1，度為0的結(jié)點(diǎn)個(gè)數(shù)是6，則度為3的結(jié)點(diǎn)個(gè)數(shù)是_2_。22.如圖所示的有向無環(huán)圖可以排出_種不同的拓?fù)湫蛄小?23.利用篩選法將關(guān)鍵字序列(37，66，48，29，31，75)建成的大根堆為(_75,66,48,29,31,37_)。24.對(duì)長(zhǎng)度為20的有序表進(jìn)行二分查找的判定樹的高度為_5_。25

54、.在多重表文件中，次關(guān)鍵字索引的組織方式是將_的記錄鏈接成一個(gè)鏈表。26.對(duì)于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個(gè)指向鏈表中某結(jié)點(diǎn)的指針p，能否將p所指結(jié)點(diǎn)的數(shù)據(jù)元素與其確實(shí)存在的直接前驅(qū)交換?請(qǐng)對(duì)每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。 date next單鏈表和單循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)為prior date next雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為 (1)單鏈表: (不可以,無法找到前驅(qū)接點(diǎn))(2)單循環(huán)鏈表(可以:q=p->next;while(q->next!=p)q=q->next;q->da

55、ta<->p->data;(3)雙向鏈表(可以:p->prior->data<->p->data;)27.假設(shè)通信電文使用的字符集為a,b,c,d,e,f,g，字符的哈夫曼編碼依次為：0110，10，110，111，00，0111和010。(1)請(qǐng)根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點(diǎn)中標(biāo)注相應(yīng)字符；(2)若這些字符在電文中出現(xiàn)的頻度分別為：3，35，13，15，20，5和9，求該哈夫曼樹的帶權(quán)路徑長(zhǎng)度。28.當(dāng)采用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，也可將鄰接表中的頂點(diǎn)表由順序結(jié)構(gòu)改為鏈表結(jié)構(gòu)。(1)請(qǐng)分別畫出這種鄰接表的頂點(diǎn)鏈表結(jié)點(diǎn)和邊表結(jié)點(diǎn)，并說

56、明結(jié)點(diǎn)中各個(gè)域的作用；(2)對(duì)如圖所示的有向圖畫出這種鄰接表。29.已知4階B-樹如圖所示。(1)分別畫出將關(guān)鍵字23和89相繼插入之后的B-樹。(2)畫出從插入之前的B-樹中刪除關(guān)鍵字51之后的B-樹。四、算法閱讀題(每小題5分，共20分)30.閱讀下列函數(shù)algo,并回答問題：(1)假設(shè)隊(duì)列q中的元素為(2,4,5,7,8),其中“2”為隊(duì)頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q)后的隊(duì)列q；(2)簡(jiǎn)述算法algo的功能。void algo(Queue *Q)  Stack S;  InitStack(&S

57、);  while (!QueueEmpty(Q)    Push(&S, DeQueue(Q);  while (! StackEmpty(&S)    nQueue(Q,Pop(&S);(1)87542(2) 隊(duì)列倒置31.閱讀下列函數(shù)F，并回答問題：(1)已知如圖所示的二叉樹以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，rt為指向根結(jié)點(diǎn)的指針。寫出執(zhí)行函數(shù)調(diào)用F(rt)的輸出結(jié)果。(2)說明函數(shù)F的功能。void

58、0;F(BinTree T)  Stack S;  if(T)      InitStack(&S);    Push(&S,NULL);    while(T)          printf("%c", T->data);  

59、;    if(T->rchild) Push(&S,T->rchild);      if(T->lchild)T=T->lchild;      else T=Pop(&S);      (1)(2)前序遍歷二叉數(shù)vertex firstedge32.已知鄰接表的頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為 adjvex&

60、#160;next邊表結(jié)點(diǎn)EdgeNode的結(jié)構(gòu)為下列算法計(jì)算有向圖G中頂點(diǎn)vi的入度。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。int FindDegree(ALGraph *G,int i)/ALGraph為圖的鄰接表類型  int dgree, j;  EdgeNode *p;  degree=    (1)        for(j=0;j&

61、lt;G->n;j+)      p=G->adjlistj. firstedge;    while (      (2)       )         if(     (3) 

62、60;   )           degree+;      break;          p=p->next;        return degree;(1)degree=0;(2)p(3)p-&

63、gt;adj=vidata next33.已知單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為下列算法對(duì)帶頭結(jié)點(diǎn)的單鏈表L進(jìn)行簡(jiǎn)單選擇排序，使得L中的元素按值從小到大排列。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為完整的算法。void SelectSort(LinkedList L)  LinkedList p,q,min;  DataType rcd;  p=   (1)      while(p!=NULL)  

64、;   min=p;    q=p->next;    while(q!=NULL)      if(    (2)    )min=q;      q=q->next;        if(

65、60;  (3)     )      rcd=p->data;      p->data=min->data;      min->data=rcd;           (4)   

66、   (1)L->next(2)q->data<min->data(3)p!=min(4)p=p->next五、算法設(shè)計(jì)題(本題10分)34.設(shè)線性表A=(a1,a2,a3,an)以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。編寫一個(gè)函數(shù)，對(duì)A進(jìn)行調(diào)整，使得當(dāng)n為奇數(shù)時(shí)A=(a2,a4,an-1,a1,a3,an)，當(dāng)n為偶數(shù)時(shí)A=(a2,a4,an,a1,a3,an-1)。typedef struct node int x; struct node *next; NO

67、DE; typedef NODE * LinkList;void adjust( LinkList header ) NODE *pTmp = header;   /用來保存偶數(shù)鏈表尾指針 NODE *pCur = header->next; /鏈表遍歷指針 NODE *pOddHdr = header->next;/奇數(shù)鏈表頭指針 NODE&#

68、160;*pOddTail = header->next;/奇數(shù)鏈表尾指針 int bIsOdd = true; /奇數(shù)結(jié)點(diǎn)標(biāo)志，第一個(gè)結(jié)點(diǎn)是奇數(shù)結(jié)點(diǎn) if( NULL = pCur )/空鏈表，不需要處理  return; while( pCur->next != NULL )/從第二個(gè)結(jié)點(diǎn)開始遍歷   pCur = pCur->next

69、;  bIsOdd = !bIsOdd;  if( bIsOdd )                   /（這步錯(cuò)誤，未將原鏈表的接點(diǎn)連接）  /奇數(shù)結(jié)點(diǎn)，加入奇數(shù)鏈表表尾   pOddTail->next = pCur;  

70、60;pOddTail = pCur;    else  /偶數(shù)結(jié)點(diǎn)，加入偶數(shù)鏈表表尾   pTmp->next = pCur;   pTmp = pCur;    pOddTail->next = NULL;/奇數(shù)鏈表表尾結(jié)點(diǎn)的next置空  pTmp->next = pOddHdr;/奇數(shù)鏈表插入偶數(shù)鏈表表尾（這步錯(cuò)誤，未考慮最后接點(diǎn)的奇偶性。） return;全國2004年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331 一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分成（）A內(nèi)部結(jié)構(gòu)