1、精品自學(xué)考試資料推薦9全國 2018年 10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼： 02331一、單項選擇題（本大題共 15小題，每小題 2 分，共 30分） 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選 均無分。1數(shù)據(jù)結(jié)構(gòu)是（ ）A 一種數(shù)據(jù)類型B數(shù)據(jù)的存儲結(jié)構(gòu)C一組性質(zhì)相同的數(shù)據(jù)元素的集合D 相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2算法分析的目的是（ ）A 辨別數(shù)據(jù)結(jié)構(gòu)的合理性B評價算法的效率C研究算法中輸入與輸出的關(guān)系D鑒別算法的可讀性3在線性表的下列運(yùn)算中，不 改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（）A 插入B刪除C排序D 定

2、位4若進(jìn)棧序列為 1，2， 3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為（）A 3 ， 2，6，1，4，5B3，4，2，1，6，5C1，2，5，3，4，6D5，6，4，2，3，15設(shè)串 slData Structures with Java ,s2=it則子串定位函數(shù) index（s1,s2） 的值為（）A 15B16C17D186二維數(shù)組 A89 按行優(yōu)先順序存儲，若數(shù)組元素 A23 的存儲地址為 1087，A47 的存儲地址為 1153，則數(shù)組 元素 A67 的存儲地址為（ ）B 1209A 1207C 1211D 12137在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)

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

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

5、OR（年齡55）C（性別=“男”） AND（年齡 60）OR （性別=“女”）AND （年齡 55）D（性別=“男”）AND（年齡> 60）AND （性別=“女”）AND （年齡 >55）二、填空題（本大題共 10小題，每小題 2分，共 20 分）請在每小題的空格中填上正確答案。錯填、不填均無分。16稱算法的時間復(fù)雜度為 O（f（n） ，其含義是指算法的執(zhí)行時間和 的數(shù)量級相同。17在一個長度為 n 的單鏈表 L 中，刪除鏈表中 *p 的前驅(qū)結(jié)點(diǎn)的時間復(fù)雜度為 。18假設(shè)為循環(huán)隊列分配的向量空間為Q20 ，若隊列的長度和隊頭指針值分別為 13 和 17，則當(dāng)前尾指針的值為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 個結(jié)點(diǎn)的完全二叉樹的深度為 。22含 n 個頂點(diǎn)的無向連通圖中至少含有 條邊。23對表長為 9000 的索引順序表進(jìn)行分塊查找，假設(shè)每一塊的長度均為 15，且以順序查找確定塊，則在各記錄的 查找概率均相等的情況下，其查找成功的平均查找長度為 。24若對關(guān)鍵字序列（ 43，02，80，4

7、8，26，57，15，73，21，24，66）進(jìn)行一趟增量為 3 的希爾排序，則得到的 結(jié)果為 。25 ISAM 文件由主索引、 、和主文件組成。三、解答題（本大題共 4小題，每小題 5 分，共 20分）26某廣義表的表頭和表尾均為（ a,（b,c），畫出該廣義表的圖形表示。27已知二叉樹的先序序列和中序序列分別為HDACBGFE 和 ADCBHFEG 。（ 1）畫出該二叉樹；（ 2）畫出與（ 1）求得的二叉樹對應(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）寫出遍歷過程中得到的

8、從頂點(diǎn)C 到其它各頂點(diǎn)的帶權(quán)路徑及其長度。（1）（2）29從空樹起，依次插入關(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已知用有序鏈表存儲整數(shù)集合的元素。閱讀算法f30 ，并回答下列問題：（1）寫出執(zhí)行 f30（ a,b）的返回值，其中 a和 b 分別為指向存儲集合 2，4，5，7，9，12和2，4，5，7，9的鏈 表的頭指針；（ 2）簡述算法 f30 的功能；（ 3）寫出算法 f3

9、0 的時間復(fù)雜度。int f30（LinkList ha,LinkList hb）/LinkList 是帶有頭結(jié)點(diǎn)的單鏈表/ha 和 hb 分別為指向存儲兩個有序整數(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已知稀疏矩陣采用帶

10、行表的三元組表表示，其形式說明如下：#define MaxRow 100 /稀疏矩陣的最大行數(shù)typedef struct int i,j,v; /行號、列號、元素值TriTupleNode;typedef structTriTupleNode dataMaxSize;int RowTabMaxRow+1;/行表int m,n,t;/矩陣的行數(shù)、列數(shù)和非零元個數(shù)RTriTupleTable;下列算法 f31 的功能是，以行優(yōu)先的順序輸入稀疏矩陣的非零元(行號、列號、元素值) ，建立稀疏矩陣的帶行表的三元組表存儲結(jié)構(gòu)。請在空缺處填入合適內(nèi)容，使其成為一個完整的算法。 (注：矩陣的行、列下標(biāo)均從

11、1 起計)void f31(RTriTupleTable *R) int i,k;scanf( %d %d %d ,&R->m,&R->n,&R->t);R->RowTab1=0;k=1; /k 指示當(dāng)前輸入的非零元的行號for(i=0; ； i+) scanf( %d %d %d , ， ， &R->datai.v);while(k<R->datai.i) ；R->RowTabk=i;32已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，其類型定義如下：typedef struct NodeType DataType data;s

12、truct NodeType *lchild,*rchild;BinTNode,*BinTree;閱讀算法 F32，并回答下列問題：(1) 對于如圖所示的二叉樹，畫出執(zhí)行算法 f32 的結(jié)果；2)簡述算法 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-

13、>rchild); return bt2;(1)(2) 33假設(shè)有向圖采用鄰接表表示法，其定義如下： typedef struct VertexNode adjlistMaxVertexNum;int n,e; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) ALGraph;/ 鄰接表類型vertexfirstedge邊表結(jié)點(diǎn) EdgeNode 結(jié)構(gòu)為：adjvexnextindegree/p 為指向邊表結(jié)點(diǎn)的指針/Q 為隊列/求各頂點(diǎn)的入度，并置于入度向量列算法 f33 的功能是，對以鄰接表表示的有向圖進(jìn)行拓?fù)渑判颉?)閱讀算法 f33，并在空缺處填入 合適的內(nèi)容，使其成為一個完 整的算法；2)對于如圖所示

14、的鄰接表，將執(zhí)行算法 f33 后的 topo 結(jié)果填入 給定的數(shù)組中。void f33(ALGraph G , int topo ) int i,j,k,count=0;int indegreeMaxVertexNum; EdgeNode *p;Queue Q;FindIndegree(G, 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(!(-inde