全國(guó)10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題及答案

1、做試題,沒答案?上自考365,網(wǎng)校名師為你詳細(xì)解答!全國(guó)2006年10月高等教育自學(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)是（D）A一種數(shù)據(jù)類型B數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C一組性質(zhì)相同的數(shù)據(jù)元素的集合D相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2算法分析的目的是（B）A辨別數(shù)據(jù)結(jié)構(gòu)的合理性B評(píng)價(jià)算法的效率C研究算法中輸入與輸出的關(guān)系D鑒別算法的可讀性3在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（D）A插入B刪除C排序D

2、定位4若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為（B）A3，2，6，1，4，5B3，4，2，1，6，5C1，2，5，3，4，6D5，6，4，2，3，15設(shè)串sl=Data Structures with Java,s2=it，則子串定位函數(shù)index(s1,s2)的值為（D）A15B16C17D186二維數(shù)組A89按行優(yōu)先順序存儲(chǔ)，若數(shù)組元素A23的存儲(chǔ)地址為1087，A47的存儲(chǔ)地址為1153，則數(shù)組元素A67的存儲(chǔ)地址為（A）A1207B1209C1211D12137在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（A）A隊(duì)列B棧C線性表D有序

3、表8在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對(duì)次序關(guān)系（B）A不一定相同B都相同C都不相同D互為逆序9若采用孩子兄弟鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的（C）A層次遍歷算法B前序遍歷算法C中序遍歷算法D后序遍歷算法10若用鄰接矩陣表示一個(gè)有向圖，則其中每一列包含的1的個(gè)數(shù)為（A）A圖中每個(gè)頂點(diǎn)的入度B圖中每個(gè)頂點(diǎn)的出度C圖中弧的條數(shù)D圖中連通分量的數(shù)目11圖的鄰接矩陣表示法適用于表示（C）A無向圖B有向圖C稠密圖D稀疏圖12在對(duì)n個(gè)關(guān)鍵字進(jìn)行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元素，則在進(jìn)行第i趟排序之前，無序區(qū)中關(guān)鍵字元素的個(gè)數(shù)為（D）AiBi+

4、1Cn-iDn-i+113下列排序算法中，其時(shí)間復(fù)雜度和記錄的初始排列無關(guān)的是（B）A插入排序B堆排序C快速排序D冒泡排序14若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關(guān)鍵字b的過程中，先后進(jìn)行比較的關(guān)鍵字依次為（C）Af,c,bBf,d,bCg,c,bDg,d,b15若在文件中查詢年齡在60歲以上的男性及年齡在55歲以上的女性的所有記錄，則查詢條件為（C）A（性別=“男”）OR(年齡> 60)OR（性別=“女”）OR（年齡>55） B（性別=“男”）OR(年齡> 60)AND（性別=“女”）OR（年齡>55）C（

5、性別=“男”）AND(年齡> 60)OR（性別=“女”）AND（年齡>55）D（性別=“男”）AND(年齡> 60)AND（性別=“女”）AND（年齡>55）二、填空題（本大題共10小題，每小題2分，共20分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。16稱算法的時(shí)間復(fù)雜度為O(f(n)，其含義是指算法的執(zhí)行時(shí)間和 f(n) 的數(shù)量級(jí)相同。17在一個(gè)長(zhǎng)度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(n) 。18假設(shè)為循環(huán)隊(duì)列分配的向量空間為Q20，若隊(duì)列的長(zhǎng)度和隊(duì)頭指針值分別為13和17，則當(dāng)前尾指針的值為 10 。19設(shè)s=

6、I AM A ATHLETE,t=GOOD，則執(zhí)行下列串操作序列之后得到的sub1為_。substr (sub1,s,5,2)；substr(sub2,s,6,8); strcpy(t1,t);strcat(t1,sub2); strcat(sub1,t1);20廣義表的深度是指_。21一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_。22含n個(gè)頂點(diǎn)的無向連通圖中至少含有_條邊。23對(duì)表長(zhǎng)為9000的索引順序表進(jìn)行分塊查找，假設(shè)每一塊的長(zhǎng)度均為15，且以順序查找確定塊，則在各記錄的查找概率均相等的情況下，其查找成功的平均查找長(zhǎng)度為_。24若對(duì)關(guān)鍵字序列（43，02，80，48，26，57，15，73，

7、21，24，66）進(jìn)行一趟增量為3的希爾排序，則得到的結(jié)果為_。25ISAM文件由主索引、_、_和主文件組成。三、解答題（本大題共4小題，每小題5分，共20分）26某廣義表的表頭和表尾均為（a,(b,c)），畫出該廣義表的圖形表示。27已知二叉樹的先序序列和中序序列分別為HDACBGFE和ADCBHFEG。（1）畫出該二叉樹；（2）畫出與（1）求得的二叉樹對(duì)應(yīng)的森林。（1）（2）28已知帶權(quán)圖的鄰接表如下所示，其中邊表結(jié)點(diǎn)的結(jié)構(gòu)為：依此鄰接表從頂點(diǎn)C出發(fā)進(jìn)行深度優(yōu)先遍歷。（1）畫出由此得到的深度優(yōu)先生成樹；（2）寫出遍歷過程中得到的從頂點(diǎn)C到其它各頂點(diǎn)的帶權(quán)路徑及其長(zhǎng)度。（1）（2）29從空樹

8、起，依次插入關(guān)鍵字37，50，42，18，48，12，56，30，23，構(gòu)造一棵二叉排序樹。（1）畫出該二叉排序樹；（2）畫出從（1）所得樹中刪除關(guān)鍵字為37的結(jié)點(diǎn)之后的二叉排序樹。（1）（2）四、算法閱讀題（本大題共4小題，每小題5分，共20分）30已知用有序鏈表存儲(chǔ)整數(shù)集合的元素。閱讀算法f30，并回答下列問題：（1）寫出執(zhí)行f30（a,b）的返回值，其中a和b分別為指向存儲(chǔ)集合2，4，5，7，9，12和2，4，5，7，9的鏈表的頭指針；（2）簡(jiǎn)述算法f30的功能；（3）寫出算法f30的時(shí)間復(fù)雜度。 int f30(LinkList ha,LinkList hb) /LinkList是帶有

9、頭結(jié)點(diǎn)的單鏈表 /ha和hb分別為指向存儲(chǔ)兩個(gè)有序整數(shù)集合的鏈表的頭指針 LinkList pa,pb; pa=ha->next; pb=hb->next; while(pa && pb && pa->data=pb->data) pa=pa->next;pb=pb->next; if(pa=NULL && pb=NULL) return 1; else return 0; (1)(2)(3)31已知稀疏矩陣采用帶行表的三元組表表示，其形式說明如下： #define MaxRow 100/稀疏矩陣的最大行數(shù) t

10、ypedef struct int i,j,v;/行號(hào)、列號(hào)、元素值TriTupleNode; typedef structTriTupleNode dataMaxSize;int RowTabMaxRow+1;/行表int m,n,t;/矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)RTriTupleTable;下列算法f31的功能是，以行優(yōu)先的順序輸入稀疏矩陣的非零元（行號(hào)、列號(hào)、元素值），建立稀疏矩陣的帶行表的三元組表存儲(chǔ)結(jié)構(gòu)。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為一個(gè)完整的算法。（注：矩陣的行、列下標(biāo)均從1起計(jì)）void f31(RTriTupleTable *R) int i,k;scanf(%d %d %

11、d,&R->m,&R->n,&R->t);R->RowTab1=0;k=1; /k指示當(dāng)前輸入的非零元的行號(hào)for(i=0; ；i+) scanf(%d %d %d, ， ，&R->datai.v); while(k<R->datai.i) ； R->RowTabk=i; 32已知二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，其類型定義如下：typedef struct NodeType DataType data; struct NodeType *lchild,*rchild; BinTNode,*BinTree;閱讀算法F32

12、，并回答下列問題：(1)對(duì)于如圖所示的二叉樹，畫出執(zhí)行算法f32的結(jié)果；（2）簡(jiǎn)述算法f32的功能。BinTree f32(BinTree bt1) BinTree bt2; if(bt1=NULL) bt2=NULL; else bt2=(BinTNode *)malloc(sizeof(BinTNode); bt2->data=bt1->data; bt2->rchild=f32(bt1->lchild); bt2->lchild=f32(bt1->rchild); return bt2; (1)(2)33假設(shè)有向圖采用鄰接表表示法，其定義如下：type

13、def struct VertexNode adjlistMaxVertexNum;int n,e; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) ALGraph; /鄰接表類型vertex firstedge其中頂點(diǎn)表結(jié)點(diǎn)VertexNode結(jié)構(gòu)為：adjvex next邊表結(jié)點(diǎn)EdgeNode結(jié)構(gòu)為： 下列算法f33的功能是，對(duì)以鄰接表表示的有向圖進(jìn)行拓?fù)渑判颉?（1）閱讀算法f33，并在空缺處填入合適的內(nèi)容，使其成為一個(gè)完整的算法； （2）對(duì)于如圖所示的鄰接表，將執(zhí)行算法f33后的topo 結(jié)果填入給定的數(shù)組中。 void f33(ALGraph G, int topo ) int i,j,k,count=0

14、; int indegreeMaxVertexNum; EdgeNode *p; /p為指向邊表結(jié)點(diǎn)的指針 Queue Q; /Q為隊(duì)列 FindIndegree(G, indegree); /求各頂點(diǎn)的入度，并置于入度向量indegree InitQueue(&Q); for(i=0;i<G.n;i+) if(!indegreei)EnQueue(&Q,i); while(!QueueEmpty(&Q) j= ; topoj=+count; for(p=G.adjlistj.firstedge;p;p=->next) k=p->adjvex; if(!(-ind