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

2、=NULL D. head-next=head4. 引起循環隊列隊頭位置發生變化的操作是( )A. 出隊 B. 入隊C. 取隊頭元素 D. 取隊尾元素5. 若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則不可能出現的出棧序列是( )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. 字符串通常采用的兩種存儲方式是( )A. 散列存儲和索引存儲 B. 索引存儲和鏈式存儲C. 順序存儲和鏈式存儲 D. 散列存儲和順序存儲7. 數據結構是（）A一種數據類型B數據的存儲結構C一組性質相同的數據元素的集合D相互之間存在

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

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

5、b,c,d,e,f,g,q,r,s,t），則在二分查找關鍵字b的過程中，先后進行比較的關鍵字依次為（）Af,c,bBf,d,bCg,c,bDg,d,b19. 下面程序段的時間復雜度為( ) 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. 在計算機內實現遞歸算法時所需的輔助數據結構是( )A.棧B.隊列C.樹D.圖22. 通常將鏈串的結點大小設置為大于1是為了( )A.提高串匹配效率B.提

6、高存儲密度C.便于插入操作D.便于刪除操作23. 帶行邏輯的三元組表是稀疏矩陣的一種( )A.順序存儲結構B.鏈式存儲結構C.索引存儲結構D.散列存儲結構24. 用二叉鏈表表示具有n個結點的二叉樹時，值為空的指針域的個數為( )A.n-1B.nC.n+lD.2n25. 為便于判別有向圖中是否存在回路，可借助于( )A.廣度優先搜索算法B.最小生成樹算法C.最短路徑算法D.拓撲排序算法26. 連通網的最小生成樹是其所有生成樹中( )A.頂點集最小的生成樹B.邊集最小的生成樹C.頂點權值之和最小的生成樹D.邊的權值之和最小的生成樹27. 按排序過程中依據的原則分類，快速排序屬于( )A.插入類的排

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

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

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

10、為Q20，若隊列的長度和隊頭指針值分別為13和17，則當前尾指針的值為_。12. 一棵含999個結點的完全二叉樹的深度為_,深度為10的滿二叉樹有_個結點。13. 含n個頂點的無向連通圖中至少含有_條邊。14. .已知有向圖G的定義如下： G=(V，E) V=a，b，c，d，e E=， ， (1)畫出G的圖形； (2)寫出G的全部拓撲序列。15. 線性表的鏈接存儲比順序存儲的優點是：_操作不需移動結點。16. 孩子兄弟鏈表表示的樹結構，其后根遍歷結果同二叉樹的_.一致。17. 哈夫曼樹又稱_.其定義是_18 隊列是一種_線性表，而棧是_線性表。19. 畫出與如圖所示森林對應的二叉樹。20.下列

11、線索化的樹稱為_，畫出中序線素二叉樹的線索表示。BACDEFGH21. 填寫語句完成對順序表的初始化#define LIST_INIT_SIZE 100typedef struct ElemType *elem; /存儲空間起始地址int length; /線性表長度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.一般而言，若二叉樹的結

12、點，其左子樹的所有結點小于根結點，而右子樹的所有結點大于根結點，則二叉樹稱為_; 如果結點的左子樹深度和右子樹深度之差的絕對值不超過1，則二叉樹稱為_.三、解答題1. 已知二叉樹的先序序列和中序序列分別為HDACBGFE和ADCBHFEG。（1）畫出該二叉樹；（2）畫出與（1）求得的二叉樹對應的森林。2. 從空樹起，依次插入關鍵字37，50，42，18，48，12，56，30，23，構造一棵二叉排序樹。（1）畫出該二叉排序樹；（2）畫出從（1）所得樹中刪除關鍵字為37的結點之后的二叉排序樹。3. 已知用有序鏈表存儲整數集合的元素。閱讀算法f3，并回答下列問題：（1）寫出執行f3（a,b）的返回

13、值，其中a和b分別為指向存儲集合2，4，5，7，9，12和2，4，5，7，9, 12的鏈表的頭指針；（2）簡述算法f3的功能；（3）寫出算法f3的時間復雜度。 int f3(LinkList ha,LinkList hb) /LinkList是帶有頭結點的單鏈表 /ha和hb分別為指向存儲兩個有序整數集合的鏈表的頭指針 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. 已知稀疏矩陣采用三元組表表示，其形式說明如下： #define MaxSize 100/稀疏矩陣的最大行數 typedef struct int i,j,v;/行號、列號、元素值TriTupleNode; typedef structTriTupleNode dataMaxSize;int m,n,t;/矩陣的行數、列數和非零元個數RTriTupleTable;下列算法f4的功能是，以行優先的順序輸入稀疏矩陣的非零元（行號、列號、元素值），建立稀疏矩陣的三元組表存儲結構。請在空缺處填入合適內容，使其成為一個完整的算法。（注：矩陣的行、列下標均從1起計）void f4(RTriTu

15、pleTable &R) int i,k;scanf(%d %d %d,&R-m,&R-n,&R-t);k=1; /k指示當前輸入的非零元的行號for(i=0; ；i+) scanf(%d %d %d, ， ，_; 5. 已知二叉樹的存儲結構為二叉鏈表，其類型定義如下：typedef struct NodeType DataType data; struct NodeType *lchild,*rchild; BinTNode,*BinTree;閱讀算法f5，并回答下列問題：(1)對于如圖所示的二叉樹，畫出執行算法f5的結果；（2）簡述算法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. 已知圖的鄰接表表示的形式說明如下：#define MaxNum 50 /圖的最大頂點數typedef struct node int adjvex; /鄰接點域 struct node *next; /鏈指針域 EdgeNode; /邊表結點結構描述ty

17、pedef struct char vertex; /頂點域 EdgeNode *firstedge; /邊表頭指針 VertexNode; /頂點表結點結構描述typedef struct VertexNode adjlistMaxNum; /鄰接表 int n, e; /圖中當前的頂點數和邊數 ALGraph; /鄰接表結構描述 下列算法輸出圖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. 存儲結構（或存儲映像）2. p-prior=p-prior-prior;p-prior-next=p;3.棧空，棧滿4.”DEFG”5.116. 入度,出度7. 隊尾元素：（rear-quelen+1+m）% m隊頭元素：(front+quelen-1)%m8. 后序序列：BDCEGFA9. f(n)10. O(n),O(1)11. 1012. 10，102313. n-114.abecd,aebcd,eabcd15. 插入和刪除元素16. 中序遍歷17. 最優二叉樹,所有葉子結點的帶權路徑長度之和為最小18. 先進先出，后進先出19.ABCDEFGHIJ20.后序線索二叉樹21. l.