數(shù)據(jù)結(jié)構(gòu)模擬卷

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)練習(xí)題一、單項(xiàng)選擇題1. 若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上( ) A. 操作的有限集合 B. 映象的有限集合C. 類(lèi)型的有限集合 D. 關(guān)系的有限集合2. 在長(zhǎng)度為n的順序表中刪除第i個(gè)元素(1in)時(shí)，元素移動(dòng)的次數(shù)為( )A. n-i+1 B. iC. i+1 D. n-i3. 若不帶頭結(jié)點(diǎn)的單鏈表的指針為head，則該鏈表為空的判定條件是( )A. head=NULL B. head-next=NULLC. head!

2、=NULL D. head-next=head4. 引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是( )A. 出隊(duì) B. 入隊(duì)C. 取隊(duì)頭元素 D. 取隊(duì)尾元素5. 若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則不可能出現(xiàn)的出棧序列是( )A. 2，4，3，1，5，6 B. 3，2，4，1，6，5C. 4，3，2，1，5，6 D. 2，3，5，1，6，46. 字符串通常采用的兩種存儲(chǔ)方式是( )A. 散列存儲(chǔ)和索引存儲(chǔ) B. 索引存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)C. 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ) D. 散列存儲(chǔ)和順序存儲(chǔ)7. 數(shù)據(jù)結(jié)構(gòu)是（）A一種數(shù)據(jù)類(lèi)型B數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C一組性質(zhì)相同的數(shù)據(jù)元素的集合D相互之間存在

3、一種或多種特定關(guān)系的數(shù)據(jù)元素的集合8. 算法分析的目的是（）A辨別數(shù)據(jù)結(jié)構(gòu)的合理性B評(píng)價(jià)算法的效率C研究算法中輸入與輸出的關(guān)系D鑒別算法的可讀性9. 在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（）A插入B刪除C排序D定位10. 下列圖示的順序存儲(chǔ)結(jié)構(gòu)表示的二叉樹(shù)是( )11. 設(shè)串sl=Data Structures with Java,s2=it，則子串定位函數(shù)index(s1,s2)的值為(）A15B16C17D1812. 二維數(shù)組A89按行優(yōu)先順序存儲(chǔ)，若數(shù)組元素A23的存儲(chǔ)地址為1087，A47的存儲(chǔ)地址為1153，則數(shù)組元素A67的存儲(chǔ)地址為（）A1213B1209C1

4、211D120713. 在按中序遍歷二叉樹(shù)的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（）A隊(duì)列B棧C線性表D有序表14. 在任意一棵二叉樹(shù)的前序序列和后序序列中，各葉子之間的相對(duì)次序關(guān)系（）A不一定相同B都相同C都不相同D互為逆序15. 若采用孩子兄弟鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu)，則樹(shù)的后序遍歷應(yīng)采用二叉樹(shù)的（）A層次遍歷算法B前序遍歷算法C中序遍歷算法D后序遍歷算法16. 若用鄰接矩陣表示一個(gè)有向圖，則其中每一列包含的1的個(gè)數(shù)為（）A圖中每個(gè)頂點(diǎn)的入度B圖中每個(gè)頂點(diǎn)的出度C圖中弧的條數(shù)D圖中連通分量的數(shù)目17. 圖的鄰接矩陣表示法適用于表示（）A無(wú)向圖B有向圖C稠密圖D稀疏圖18. 若有序表的關(guān)鍵字序列為（

5、b,c,d,e,f,g,q,r,s,t），則在二分查找關(guān)鍵字b的過(guò)程中，先后進(jìn)行比較的關(guān)鍵字依次為（）Af,c,bBf,d,bCg,c,bDg,d,b19. 下面程序段的時(shí)間復(fù)雜度為( ) s=0； for(i=1；in；i+) for(j=1；jnext=s-next；s-next=p；B.s-next=p；q-next=s-next；C.p-next=s-next；s-next=q；D.s-next=q；p-next=s-next；21. 在計(jì)算機(jī)內(nèi)實(shí)現(xiàn)遞歸算法時(shí)所需的輔助數(shù)據(jù)結(jié)構(gòu)是( )A.棧B.隊(duì)列C.樹(shù)D.圖22. 通常將鏈串的結(jié)點(diǎn)大小設(shè)置為大于1是為了( )A.提高串匹配效率B.提

6、高存儲(chǔ)密度C.便于插入操作D.便于刪除操作23. 帶行邏輯的三元組表是稀疏矩陣的一種( )A.順序存儲(chǔ)結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D.散列存儲(chǔ)結(jié)構(gòu)24. 用二叉鏈表表示具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)時(shí)，值為空的指針域的個(gè)數(shù)為( )A.n-1B.nC.n+lD.2n25. 為便于判別有向圖中是否存在回路，可借助于( )A.廣度優(yōu)先搜索算法B.最小生成樹(shù)算法C.最短路徑算法D.拓?fù)渑判蛩惴?6. 連通網(wǎng)的最小生成樹(shù)是其所有生成樹(shù)中( )A.頂點(diǎn)集最小的生成樹(shù)B.邊集最小的生成樹(shù)C.頂點(diǎn)權(quán)值之和最小的生成樹(shù)D.邊的權(quán)值之和最小的生成樹(shù)27. 按排序過(guò)程中依據(jù)的原則分類(lèi)，快速排序?qū)儆? )A.插入類(lèi)的排

7、序方法B.選擇類(lèi)的排序方法C.交換類(lèi)的排序方法D.歸并類(lèi)的排序方法28. 在長(zhǎng)度為32的有序表中進(jìn)行二分查找時(shí)，所需進(jìn)行的關(guān)鍵字比較次數(shù)最多為( )A.4B.5C.6D.729. 假設(shè)在構(gòu)建散列表時(shí)，采用線性探測(cè)解決沖突。若連續(xù)插入的n個(gè)關(guān)鍵字都是同義詞，則查找其中最后插入的關(guān)鍵字時(shí)，所需進(jìn)行的比較次數(shù)為( )A.n-1B.nC.n+lD.n+230. 若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關(guān)鍵字b的過(guò)程中，先后進(jìn)行比較的關(guān)鍵字依次為（）Af,c,bBf,d,bCg,c,bDg,d,b二、填空題1. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的_。2

8、. 已知雙向循環(huán)鏈表結(jié)點(diǎn)中，域prior指向前一結(jié)點(diǎn)，域next指向后一結(jié)點(diǎn)，則刪除當(dāng)前結(jié)點(diǎn)指針p的前驅(qū)結(jié)點(diǎn)(存在)應(yīng)執(zhí)行的語(yǔ)句是_。3. 棧下溢是指在_時(shí)進(jìn)行出棧操作，棧上溢是指在_時(shí)進(jìn)行入棧操作。4. 已知substr(s,i,len)函數(shù)的功能是返回串s中第i個(gè)字符開(kāi)始長(zhǎng)度為len的子串，strlen(s)函數(shù)的功能是返回串s的長(zhǎng)度。若s=”ABCDEFGHIJK,t=”ABCD,執(zhí)行運(yùn)算substr(s,strlen(t), strlen(t)后的返回值為_(kāi)。5. 已知完全二叉樹(shù)T的第5層只有7個(gè)結(jié)點(diǎn)，則該樹(shù)共有_個(gè)葉子結(jié)點(diǎn)6. 在有向圖中，以頂點(diǎn)v為終點(diǎn)的弧的數(shù)目稱為v的_,以頂點(diǎn)v

9、為源點(diǎn)的弧的數(shù)目稱為v的_。7. 假設(shè)以數(shù)組seqnm存放循環(huán)隊(duì)列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和元素的個(gè)數(shù)。寫(xiě)出一般情況下隊(duì)頭元素位置的表達(dá)式。如果用變量front和quelen分別指示循環(huán)隊(duì)列中隊(duì)頭元素的位置和元素的個(gè)數(shù)，則寫(xiě)出一般情況下隊(duì)尾元素位置的表達(dá)式。8. 已知二叉樹(shù)如下，寫(xiě)出它的先序序列、中序序列和后序序列BFGDCEA9. 稱算法的時(shí)間復(fù)雜度為O(f(n)，其含義是指算法的執(zhí)行時(shí)間和_的數(shù)量級(jí)相同。10. 在一個(gè)長(zhǎng)度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)，刪除*p結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)。11. 假設(shè)為循環(huán)隊(duì)列分配的向量空間

10、為Q20，若隊(duì)列的長(zhǎng)度和隊(duì)頭指針值分別為13和17，則當(dāng)前尾指針的值為_(kāi)。12. 一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi),深度為10的滿二叉樹(shù)有_個(gè)結(jié)點(diǎn)。13. 含n個(gè)頂點(diǎn)的無(wú)向連通圖中至少含有_條邊。14. .已知有向圖G的定義如下： G=(V，E) V=a，b，c，d，e E=， ， (1)畫(huà)出G的圖形； (2)寫(xiě)出G的全部拓?fù)湫蛄小?5. 線性表的鏈接存儲(chǔ)比順序存儲(chǔ)的優(yōu)點(diǎn)是：_操作不需移動(dòng)結(jié)點(diǎn)。16. 孩子兄弟鏈表表示的樹(shù)結(jié)構(gòu)，其后根遍歷結(jié)果同二叉樹(shù)的_.一致。17. 哈夫曼樹(shù)又稱_.其定義是_18 隊(duì)列是一種_線性表，而棧是_線性表。19. 畫(huà)出與如圖所示森林對(duì)應(yīng)的二叉樹(shù)。20.下列

11、線索化的樹(shù)稱為_(kāi)，畫(huà)出中序線素二叉樹(shù)的線索表示。BACDEFGH21. 填寫(xiě)語(yǔ)句完成對(duì)順序表的初始化#define LIST_INIT_SIZE 100typedef struct ElemType *elem; /存儲(chǔ)空間起始地址int length; /線性表長(zhǎng)度int listSize; /分配容量 SqList;Status initList_Sq(SqList &l)l.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!l.elem) exit ERROR;_;_;return OK;22.一般而言，若二叉樹(shù)的結(jié)

12、點(diǎn)，其左子樹(shù)的所有結(jié)點(diǎn)小于根結(jié)點(diǎn)，而右子樹(shù)的所有結(jié)點(diǎn)大于根結(jié)點(diǎn)，則二叉樹(shù)稱為_(kāi); 如果結(jié)點(diǎn)的左子樹(shù)深度和右子樹(shù)深度之差的絕對(duì)值不超過(guò)1，則二叉樹(shù)稱為_(kāi).三、解答題1. 已知二叉樹(shù)的先序序列和中序序列分別為HDACBGFE和ADCBHFEG。（1）畫(huà)出該二叉樹(shù)；（2）畫(huà)出與（1）求得的二叉樹(shù)對(duì)應(yīng)的森林。2. 從空樹(shù)起，依次插入關(guān)鍵字37，50，42，18，48，12，56，30，23，構(gòu)造一棵二叉排序樹(shù)。（1）畫(huà)出該二叉排序樹(shù)；（2）畫(huà)出從（1）所得樹(shù)中刪除關(guān)鍵字為37的結(jié)點(diǎn)之后的二叉排序樹(shù)。3. 已知用有序鏈表存儲(chǔ)整數(shù)集合的元素。閱讀算法f3，并回答下列問(wèn)題：（1）寫(xiě)出執(zhí)行f3（a,b）的返回

13、值，其中a和b分別為指向存儲(chǔ)集合2，4，5，7，9，12和2，4，5，7，9, 12的鏈表的頭指針；（2）簡(jiǎn)述算法f3的功能；（3）寫(xiě)出算法f3的時(shí)間復(fù)雜度。 int f3(LinkList ha,LinkList hb) /LinkList是帶有頭結(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

14、 0; 4. 已知稀疏矩陣采用三元組表表示，其形式說(shuō)明如下： #define MaxSize 100/稀疏矩陣的最大行數(shù) typedef struct int i,j,v;/行號(hào)、列號(hào)、元素值TriTupleNode; typedef structTriTupleNode dataMaxSize;int m,n,t;/矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)RTriTupleTable;下列算法f4的功能是，以行優(yōu)先的順序輸入稀疏矩陣的非零元（行號(hào)、列號(hào)、元素值），建立稀疏矩陣的三元組表存儲(chǔ)結(jié)構(gòu)。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為一個(gè)完整的算法。（注：矩陣的行、列下標(biāo)均從1起計(jì)）void f4(RTriTu

15、pleTable &R) int i,k;scanf(%d %d %d,&R-m,&R-n,&R-t);k=1; /k指示當(dāng)前輸入的非零元的行號(hào)for(i=0; ；i+) scanf(%d %d %d, ， ，_; 5. 已知二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，其類(lèi)型定義如下：typedef struct NodeType DataType data; struct NodeType *lchild,*rchild; BinTNode,*BinTree;閱讀算法f5，并回答下列問(wèn)題：(1)對(duì)于如圖所示的二叉樹(shù)，畫(huà)出執(zhí)行算法f5的結(jié)果；（2）簡(jiǎn)述算法f5的功能。BinTree f5(BinTree bt

16、1) BinTree bt2; if(bt1=NULL) bt2=NULL; else bt2=(BinTNode *)malloc(sizeof(BinTNode); bt2-data=bt1-data; bt2-rchild=f5(bt1-lchild); bt2-lchild=f5(bt1-rchild); return bt2; 6. 已知圖的鄰接表表示的形式說(shuō)明如下：#define MaxNum 50 /圖的最大頂點(diǎn)數(shù)typedef struct node int adjvex; /鄰接點(diǎn)域 struct node *next; /鏈指針域 EdgeNode; /邊表結(jié)點(diǎn)結(jié)構(gòu)描述ty

17、pedef struct char vertex; /頂點(diǎn)域 EdgeNode *firstedge; /邊表頭指針 VertexNode; /頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)描述typedef struct VertexNode adjlistMaxNum; /鄰接表 int n, e; /圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù) ALGraph; /鄰接表結(jié)構(gòu)描述 下列算法輸出圖G的深度優(yōu)先生成樹(shù)(或森林)的邊。閱讀算法，并在空缺處填入合適的內(nèi)容，使其成為一個(gè)完整的算法。typedef enum FALSE, TRUE Boolean;Boolean visitedMaxNum;void DFSForest(ALGraph

18、*G) int i; for(i=0;in;i+) visitedi= (1) ; for(i=0;in;i+) if (!visitedi) DFSTree(G,i);void DFSTree(ALGraph *G, int i) EdgeNode *p; visitedi=TRUE; p=G-adjlisti. firstedge; while(p!=NULL) if(!visitedp-adjvex) printf(,G-adjlisti. vertex, G-adjlistp-adjvex. vertex); (2) ; (3) ; 參考答案二。填空題1. 存儲(chǔ)結(jié)構(gòu)（或存儲(chǔ)映像）2. p-prior=p-prior-prior;p-prior-next=p;3.棧空，棧滿4.”DEFG”5.116. 入度,出度7. 隊(duì)尾元素：（rear-quelen+1+m）% m隊(duì)頭元素：(front+quelen-1)%m8. 后序序列：BDCEGFA9. f(n)10. O(n),O(1)11. 1012. 10，102313. n-114.abecd,aebcd,eabcd15. 插入和刪除元素16. 中序遍歷17. 最優(yōu)二叉樹(shù),所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和為最小18. 先進(jìn)先出，后進(jìn)先出19.ABCDEFGHIJ20.后序線索二叉樹(shù)21. l.