國家開放大學電大《數(shù)據(jù)結構》《離散數(shù)學》網(wǎng)絡課形考網(wǎng)考作業(yè)(合集)答案

《國家開放大學電大《數(shù)據(jù)結構》《離散數(shù)學》網(wǎng)絡課形考網(wǎng)考作業(yè)(合集)答案》由會員分享，可在線閱讀，更多相關《國家開放大學電大《數(shù)據(jù)結構》《離散數(shù)學》網(wǎng)絡課形考網(wǎng)考作業(yè)(合集)答案（60頁珍藏版）》請在裝配圖網(wǎng)上搜索。

國家開放大學電大《數(shù)據(jù)結構》《離散數(shù)學》網(wǎng)絡課形考網(wǎng)考作業(yè)（合集）答案 《數(shù)據(jù)結枸〉網(wǎng)絡課答案 形考任務］ 一、單項逸擇題（每小題3分，共60分） 題目1 把數(shù)據(jù)存儲到計算機中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結構稱為（）。 選擇一項： A. 算法的具體實現(xiàn) B. 邏輯結構 C. 給相關變量分配存儲單元 D. 物理結構 題目2 下列說法中，不正確的是（）。 選擇一項： A. 數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標識單位 B. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位 C. 數(shù)據(jù)項可由若干個數(shù)據(jù)元素構成 D. 數(shù)據(jù)可有若干個數(shù)據(jù)元素構成 題目3 一個存儲結點存儲一個（）. 選擇一項： A. 數(shù)據(jù)項 B. 數(shù)據(jù)類型 C. 順元素 D. 數(shù)據(jù)結構 題目4 數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的（） 選擇一項： A. 存儲結構 B. 物理結構 C. 邏輯靖構 D. 物理和存儲結構 ）。 在線性表的順序結構中，以下說法正確的是（ 選擇一項： A. 進行數(shù)據(jù)元素的插入、刪除效率較高 B. 數(shù)據(jù)元素是不能隨機訪問的 C. 邏輯上相鄰的元素在物理位置上不一定相鄰 D. 邏輯上相鄰的元素在物理位置上也相鄰 題目6 對鏈表，以下敘述中正確的是（ ）。 選擇一項： A. 可以通過下標對鏈表進行直接訪問 B. 插入刪除元素的操作一定要要移動結點 C. 不能隨機訪問任一結點 D. 結點占用的存儲空間是連續(xù)的 題目7 下列的敘述中，不屬于算法特性的是（ ）. 選擇一項： A. 可行性 B. 有窮性 C. 可讀性 D. 輸入性 題目8 算法的時間復雜度與（）有關。 選擇一項： A. 所使用的計算機 B. 計算機的操作系統(tǒng) C. 數(shù)據(jù)結構 D. 算法本身 題目9 設有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），插入一個元素.則移 動元素個數(shù)為（）- 選擇一項： A. n-i-1 C. n~i+l D. n-i 題目10 設有一個長度為n的順序表，要刪除第i個元素移動元素的個數(shù)為（）. 選擇一項： A. i B. n-i-1 C. n-i D. n-i+1 題目11 在一個單鏈表中，P、q分別指向表中兩個相鄰的結點，且q所指結點是P所指結點的直接后繼，現(xiàn)要刪除q所指結點, 可用語句（）。 選擇一項： A. p->next=q->next B. p->next=q C. p=q->next D. q->next=NULL 題目12 在一個單鏈表中P所指結點之后插入一個s所指的結點時，可執(zhí)行（）- 選擇一項： A. p->next=s->next; B. s->next=p->next; p->next=s; C. p=s->next D. p->next= s; s->next= p->next 題目13 非空的單向循環(huán)鏈表的尾結點滿足（）（設頭指針為head,指針p指向尾結點）。 選擇一項： A. p->next=NULL B. p->next=4iead C. p= head D. p=NULL 題目14 鏈表不具有的特點是（）- 選擇一項： A. 邏輯上相鄰的元素在物理位置上不一定相鄰 B. 不必事先估計存儲空間 C. 可隨機訪問任一元素 D. 插入刪除不需要移動元素 題目15 帶頭結點的鏈表為空的判斷條件是（）（設頭指針為head）。 選擇一項： A. head->next=head B. head->next=NULL C. head =NULL D. head!=NULL 題目16 在一個長度為n的順序表中為了刪除第5個元素，由第6個元素開始從后到前依次移動了 15個元素。則原順序表的 長度為（） 選擇一項： A. 21 B. 25 C. 20 D. 19 題目17 有關線性表的正確說法是（）。 選擇一項： A. 除了f 和最后f 元素外，其余元素都有f 且僅有一個直接前驅和一個直接后魅 B. 每個元素都有一個直接前驅和一個直接后繼 C. 表中的元素必須按由小到大或由大到下排序 D. 線性表至少要求一個元素 題目18 向一個有127個元素的順序表中插入一個新元素，并保持原來的順序不變，平均要移動（）個元素。 選擇一項： A. 7 B. 63 C. 63.5 D. 8 題目19 一個順序表第一個元素的存儲地址是90,每個元素的長度為2,則第6個元素的地址是（）。 選擇一項： A. 102 B. 106 C. 100 D. 98 題目20 在一個不帶頭結點的單循環(huán)鏈表中，P、q分別指向表中第一個結點和尾結點，現(xiàn)要刪除第一個結點，且P、q仍 然分別指向新表中第一個結點和尾結點?？捎玫恼Z句是p=p->next;和（ ）. 選擇一項： A. p->next=q B. q->next=p C. p=q->next D. q=p 二、判斷題（每小題2分，14題，共28分） 題目21 數(shù)據(jù)元素可以有一個或多個數(shù)據(jù)項組成。 選擇一項： 對 錯 題目22 數(shù)據(jù)元素之間的抽象關系稱為物理結構。 選擇一項： 對 錯 題目23 數(shù)據(jù)的邏輯結構在計算機中的表示稱為邏輯結構。 選擇一項： 對 錯 數(shù)據(jù)的邏輯結構是與存儲該結構的計算機相關的。 選擇一項： 對 錯 題目25 數(shù)據(jù)結構中，元素之間存在多對多的關系稱為樹狀結構。 選擇一項： 對 錯 題目26 通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結構抽象成線性結構。 選擇一項： 對 錯 題目27 通常可以把某城市中各公交站點間的線路圖抽象成樹型結構。 選擇一項： 對 錯 題目28 設有一個不帶頭結點的單向循環(huán)鏈表，結點的指針域為next,指針p指向尾結點，現(xiàn)要使p指向第一個結點，可 用語句 p=p->next: o 選擇一項： 對 錯 題目29 設有一個單向鏈表，結點的指針域為next,頭指針為head, p指向尾結點，為了使該單向鏈表改為單向循環(huán)鏈表, 可用語句 p->next=head。 選擇一項： 對 錯 題目30 設有一個單向循環(huán)鏈表，結點的指針域為next,頭指針為head,指針p指向表中某結點，若邏輯表達式p- >next=head;的結果為真，則p所指結點為尾結點。 選擇一項： 對 錯 題目31 要在一個單向鏈表中P所指向的結點之后插入一個s所指向的新結點，若鏈表中結點的指針域為next,可執(zhí)行 p->next=s; s->next= p->next：的操作。 選擇一項： 對 錯 題目32 要在一個單向鏈表中刪除P所指向的結點，已知q指向P所指結點的直接前驅結點，若鏈表中結點的指針域為 next,則可執(zhí)行 q-〉next= p-〉next； 選擇一項： 對 錯 題目33 要在一個帶頭結點的單向循環(huán)鏈表中刪除頭結點，得到一個新的不帶頭結點的單向循環(huán)鏈表，若結點的指針域為 next,頭指針為 head,尾指針為 p,則可執(zhí)行 head=head-> next： p->next=head：。 選擇一項： 對 錯 題目34 設有一個單向循環(huán)鏈表，頭指針為head,鏈表中結點的指針域為next, p指向尾結點的直接前驅結點，若要刪除 尾結點，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作p->next=head：。 選擇一項： 對 錯 三、程序填空題（每小題6分，共12分.請點擊正確選項，然后拖拽至相應的方框上） 題目35 設線性表以不帶頭結點的單向鏈表存儲，鏈表頭指針為head,以下程序的功能是輸出鏈表中各結點中的數(shù)據(jù)域 data,完成程序中空格部分。 ^define NULL 0 void main() ( NODE *head ,*p : P=head; /*p為工作指針*/ do p->data v (printf( "％d\n”， : p=p->next 5 3 p!=NULL V }while : } p->datap=p->next p!=NULL 題目36 設有一個頭指針為head的不帶頭結點單向鏈表，p、q是指向鏈表中結點類型的指針變量，p指向鏈表中結點a, (設鏈表中沒有結點的數(shù)據(jù)域與結點a的數(shù)據(jù)域相同)，寫出相關語句 (1) 使該單向鏈表成為單向循環(huán)鏈表 (2) 插入結點s,使它成為a結點的直接前驅 q=p： x=p->data; :q->next!=NULL 寸 while ) q=q->nexl; q->next=head; q=p： p=p->next; while(p->data!=x) ( q=P； p=p->next y s->next=p; q->next=s 疝任務2 一、單項選擇題(每小題2分，共50分) 題目1 若讓元素1，2, 3依次進棧，則出棧順序不可能為() 選擇一項： A. 3, 1, 2 B. 3, 2, 1 C. 2, 1, 3 D. 1, 3, 2 題目2 一個隊列的入隊序列是1, 2, 3, 4。則隊列的輸出序列是（） 選擇一項： A. 1, 4, 3, 2 B. 4, 3, 2, 1 C. 3, 2, 4, 1 D. 1, 2, 3, 4 題目3 向順序棧中壓入新元素時，應當（）。 選擇一項： A. 先后次序無關緊要 B. 先存入元素，再移動棧頂指針 C. 同時進行 D. 先移動棧頂指針，入元素 題目4 在一個棧頂指針為top的鏈棧中.將一個p指針所指的結點入棧，應執(zhí)行（） 選擇一項： A. p->next=top->next:top->next=p: B. p->next=top->next;top=top->next; C. p->next=top:top=p: D. top->next=p： 題目5 在一個棧頂指針為top的鏈棧中刪除一個結點時，用x保存被刪結點的值，則執(zhí)行（）。 選擇一項： A. x=top->data;top=top->next; B. top=top->next;x=top->data: C. x=top->data： D. x=top：top=top->next; 判斷一個順序隊列（最多元素為m）為空的條件是（）。 選擇一項： A. front==rear B. front=rear+l C. rear=m-l D. rear=m 題目7 判斷一個循環(huán)隊列為滿的條件是（） 選擇一項： A. rear=MaxSize B. （rear+1）%MaxSize==front C. front=rear+l D. rear%MaxSize= =front 題目8 判斷棧滿（元素個數(shù)最多n個）的條件是（）。 選擇一項： A. top=n-l B. top=-l C. top!=0 D. top==0 題目9 設有一個20階的對稱矩陣A （第一個元素為al,l）,采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維 數(shù)組B中（數(shù)組下標從1開始），則矩陣元素a6, 2在一維數(shù)組B中的下標是（）。 選擇一項： A. 17 B. 28 C. 21 D. 23 題目10 在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入緩沖 區(qū)中，而打印機則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應該是一個（）結構。 選擇一項： A.數(shù)組 B.堆棧 C. 線性表 D. 隊列 題目11 一個遞歸算法必須包括（）。 選擇一項： A. 終止條件和迭代部分 B. 遞歸部分 C. 迭代部分 D. 終止條件和遂歸部分 題目12 在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則刪除一個結點的運算為（）。 選擇一項： A. f =f->next; B. r=r->next; C. r=f->next; D. f=r->next; 題目13 在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則插入s所指結點的運算為（）。 選擇一項： A. r->next=s;r=s; B. s->next=f;f=s; C. s->next=r;r=s; D. f->next=s;f=s; 題目14 數(shù)組a經(jīng)初始化char a[ ]= "English” ：a[7]中存放的是（）。 選擇一項： A. ”h” B. 字符h C. 字符申的紿束符 D. 變量h 題目15 設主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（）<, 選擇一項： A. BCd B. ABC C. Bed D. Abe 題目16 字符串 al=*AEIJING*, a2=*AEI*, a3="AEFANG", a4="AEFI”中最大的是（）。 選擇一項： A. a4 B. al C. a3 D. a2 題目17 兩個字符串相等的條件是（）o 選擇一項： A. 兩串包含的字符相同 B. 兩串的長度相等 C. 兩串的長度相等，并且兩串包含的字符相同 D. 兩串的長度相等，并且對應位置上的字符相同 題目18 一維數(shù)組A采用順序存儲結構，每個元素占用6個字節(jié)，第6個元素的存儲地址為100,則該數(shù)組的首地址是（） 選擇一項： A. 70 B. 28 C. 90 D. 64 題目19 一個非空廣義表的表頭（）. 選擇一項： A. 只能是原子 B. 可以是子表成原子 C. 不可能是原子 D. 只能是子表 題目20 對稀疏矩陣進行壓縮存儲，可采用三元組表，一個10行8列的稀疏矩陣A,其相應的三元組表共有6個元素，矩陣A 共有()個零元素。 選擇一項： A. 10 B. 74 C. 8 D. 72 題目21 對稀疏矩陣進行壓縮存儲，可采用三元組表，一個10行8列的稀疏矩陣A共有73個零元素，A的右下角元素為6,其 相應的三元組表中的第7個元素是( K 選擇一項： A. (10, 8, 6) B. (10, 8, 7) C. (7, 8, 10) D. (7, 10, 8) 題目22 對一個棧頂指針為top的鏈棧進行入棧操作，通過指針變量p生成入棧結點，并給該 結點賦值a,則執(zhí)行: p=(struct node *)malloc(sizeof (struct node) ;p->data=a:和 ( ) 選擇一項： A. p->next=top: top=p; B. top->next=p：p=top; C. p->next=top;p=top; D. top=top->next:p=top; 題目23 頭指針為head的帶頭結點的單向鏈表為空的判定條件是()為真。 選擇一項： A. head=NULL B. head->next=^iULL C. head->next!=NULL D. head->next!=NULL 設有一個對稱短陣A,采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始）, B數(shù)組共有55個元素，則該矩陣是（）階的對稱矩陣。 選擇一項： A. 10 B. 5 C. 15 D. 20 題目25 數(shù)組a經(jīng)初始化char a[ ]= "English” ；a[l]中存放的是（）。 選擇一項： A. ”n” B. B. 新n C. 字符E 二、判斷題（每小題2分，16題，共32分） 題目26 設有一個鏈棧，棧頂指針為hs,現(xiàn)有一個s所指向的結點要入棧，則可執(zhí)行操作。hs=s： s-> next=hs; 選擇一項： 對 錯 題目27 設有一個非空的鏈棧，棧頂指針為hs,要進行出棧操作，用x保存出棧結點的值，棧 結點的指針域為next，則可執(zhí)行hs=hs->next ：x=hs->data： 選擇一項： 對 錯 題目28 有一個鏈棧，棧頂指針為h,現(xiàn)有一個p所指向的結點要入棧，則可執(zhí)行操作p->next=h; 和 h=p： 選擇一項： 對 題目29 設有一個非空的鏈棧，棧頂指針為hs,要進行出棧操作，用x保存出棧結點的值.棧結點的指針域為next,數(shù) 據(jù)域為 data.則可執(zhí)行 hs= hs->next; x= hs->data: 選擇一項： 對 錯 題目30 在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結點的指針域為next,則插入所指結點的操作為r- >next=s： r=s： 選擇一項： 對 錯 題目31 在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結點的指針域為next, s指向一個要入隊的結點，則入隊操作 為 r=s： r->next=s； 選擇一?項： 對 錯 題目32 在一個不帶頭結點的非空鏈隊中，f和r分別為隊頭和隊尾指針，隊結點的數(shù)據(jù)域為data,指針域為next,若要 進行出隊操作，并用變量x存放出隊元素的數(shù)據(jù)值，則相關操作為x=f->daia: f=f->next; 選擇一項： 對 錯 題目33 對稀疏矩陣進行壓縮存儲，可采用三元組表，一個6行7列的稀疏矩陣A相應的三元組表共有8個元素，則矩陣A共有 34個零元素。 選擇一項： 對 錯 題目34 循環(huán)隊列的最大存儲空間為MaxSize,隊頭指針為f,隊尾指針為r,當（r+1） %MaxSize=f時表明隊列已滿。 選擇一項： 錯 題目35 循環(huán)隊列的隊頭指針為f,隊尾指針為r,當r= =f時表明隊列已滿。 選擇一項： 對 錯 題目36 空串的長度是0：空格串的長度是空格字符的個數(shù)。 選擇一項： 對 錯 題目37 對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的行下標、列下標、和非零元素值三項 信息。 選擇一項： 對 錯 題目38 循環(huán)隊列的引入，目的是為了克服假上溢。 選擇一項： 對 錯 題目39 設有n階對稱矩陣A,用一維數(shù)組s壓縮存儲A的下三角元素，s的下標從零開始，元素s[26]相應于A中的元素為a 7,5。 選擇一項： 對 錯 題目40 循環(huán)隊列的最大存儲空間為MaxSize=6,采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針 front=4,當隊尾指針rear=3時隊滿。 p= (struct node*) ma Hoc p->data=x; 錯 題目41 循環(huán)隊列的最大存儒空間為MaxSize=6,采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針 front=4.隊尾指針rear=3時，隊列中共有5個元素。 選擇一項： 對 錯 三、程序選擇填空逝(每小題9分，共18分.請點擊正確選項，然后拖拽至相應的方框上) 題目42 以下函數(shù)為鏈棧的進棧操作，x是要進棧的結點的數(shù)據(jù)域，top為棧頂指針 struct node ( ElemType data; struct node *next; }； struct node *top ; void Push(ElemType x) { struct node *p: A. sizeof (struct node) 力 A. sizeof (struct node) top=p p->next=top 題目43 以下函數(shù)為鏈隊列的入隊操作，乂為要入隊的結點的數(shù)據(jù)域的值，front、rear分別鏈隊列的隊頭、隊尾指針 struct node { ElemType data; struct node *next; }； struct node *front, *rear： void InQueue（ElemType x） { struct node *p: （sizeof （struct node）寸 \ p= （struct node*） malloc : p->data=x; p->next=NULL; rear->next=p 寸 么 =■ p V rear= : } 商孩3 一、單項選擇題（每小題2分，共38分） 題目1 假定一棵二叉樹中，雙分支結點數(shù)為15,單分支結點數(shù)為30,則葉子結點數(shù)為（） 選擇一項： A. 47 B. 16 C. 17 D. 15 題目2 二叉樹第k層上最多有（）個結點。 選擇一項： A. 2k-l B. 2k-l C. 2k-l D. 2k 題目3 將含有150個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點的編號為1,則編號 為69的結點的雙親結點的編號為（）。 B. 35 C. 34 D. 33 題目4 如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構造出的二叉樹的帶權路徑長度最小，則該樹稱為（） 選擇一項： A. 二叉樹 B. 哈夫受樹 C. 完全二叉樹 D. 平衡二叉樹 題目5 在一棵度具有5層的滿二叉樹中結點總數(shù)為（）= 選擇一項： A. 16 B. 32 C. 31 D. 33 題目6 一棵完全二叉樹共有6層，且第6層上有6個結點，該樹共有（）個結點。 選擇一項： A. 31 B. 37 C. 38 D. 72 題目7 利用3、6、8、12這四個值作為葉子結點的權，生成一棵哈夫曼樹，該樹中所有葉子結點中的最長帶權路徑長度為（ ）. 選擇一項： A. 18 B. 16 C. 30 D. 12 題目8 在一棵樹中，（）沒有前驅結點。 選擇一項： A. 樹根結點 B. 葉結點 C. 空結點 D. 分支結點 題目9 設一棵采用鏈式存儲的二叉樹，除葉結點外每個結點度數(shù)都為2,該樹結點中共有20個指針域為空，則該樹有（ ）個葉結點。 選擇一項： A. 9 B. 10 C. 21 D. 22 題目10 在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（）倍。 選擇一項： A. 2 B. 1 C. 4 D. 1/2 題目11 鄰接表是圖的一種（）. 選擇一項： A. 鏈式存儲結枸 B. 順序存儲結構 C. 散列存儲結構 D. 索引存儲結構 題目12 圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。 選擇一項： A. 先序 B. 后序 C. 層次 D.中序 題目13 已知下圖所示的一個圖，若從頂點VI出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（）。 選擇一項： A. V1V2V4V5V8V3V6V7 B. V1V3V6V7V2V4V5V8 C. V1V2V4V8V3V5V6V7 D. V1V2V4V8V5V3V6V7 題目14 已知如下圖所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。 選擇一項： A. aedfcb B. abecdf C. aebcfd D. aecbdf 題目15 圖狀結構中數(shù)據(jù)元素的位置之間存在（ ）的關系。 選擇一項： A. 一對多 B. 多對多 C. 每一個元素都有一個且只有一個直接前驅和一個直接后繼 D. 一對一 題目16 在一棵二叉樹中，若編號為i的結點存在右孩子，則右孩子的順序編號為（ ） 選擇一項： A. 2i+l B. 2i-l C. 2i D. 2i+2 題目17 一棵具有16個結點的完全二叉樹，共有（ ）層。（設根結點在第一層） A. 7 B. 5 C. 6 D. 4 題目18 對二叉捶序樹進行（ ）遍歷，可以使遍歷所得到的序列是有序序列。 選擇一項： A. 按層次 B. 中序 C. 前序 D. 后序 題目19 已知一個圖的邊數(shù)為m,則該圖的所有頂點的度數(shù)之和為（ ）。 選擇一項： A. m/2 B. m C. 2b D. 2m+l 二、判斷鹿（每小題1分，共10分） 題目20 一棵二叉樹的葉結點（終端結點）數(shù)為5,單分支結點數(shù)為2,該樹共有11個結點。 選擇一項： 對 錯 題目21 一棵有14個結點的完全二叉樹，則它的最高層上有7個結點。 選擇一項： 對 錯 題目22 一棵二叉樹有6個葉結點，則該樹總共有11個結點。 錯 題目23 根據(jù)搜索方法的不同，圖的遍歷有.先序：中序：后序三種方法。 選擇一項： 對 錯 題目24 對于一棵具有n個結點的二叉樹.其相應的鏈式存儲結構中共有n-1個指針域空。 選擇一項： 對 錯 題目25 設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為奇數(shù)，該葉結點的雙親結點的編號為10,該完全二叉樹 一共有21個結點。 選擇一項： 對 錯 題目26 設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為偶數(shù)，該葉結點的雙親結點的編號為9,該完全二叉樹 一共有19個結點。 選擇一項： 對 錯 題目27 按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有深度優(yōu)先遍歷和深度優(yōu)先遍兩種方法。 選擇一項： 對 錯 題目28 一棵有8個權重值構造的哈夫曼數(shù)，共有17個結點。 選擇一項： 對 題目29 一棵有7個葉結點的二義樹，其1度結點數(shù)的個數(shù)為2,則該樹共有15個結點。 選擇一項: 三、程序填空題（每空6分，共12分?請點擊正確選項，然后拖拽至相應的方根上） 題目30 以下程序是后序遍歷二義樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域分別為left和 right,數(shù)據(jù)域data為字符型，BT指向根結點）。完成程序中空格部分。 結果是 d.e.b.f.c.a 以下程序是中序遍歷二義樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域分別為left和 right,數(shù)據(jù)域data為字符型，BT指向根結點）。 void Inorder (struct BTreeNode *BT) ( if(BT!=NULL)( lnorder(BT->left);} printf("%c",BT?Adata) / ; lnorder(BT->right) y ; } 利用上述程序對右圖進行中序遍歷，結果是 d.b.e.a.f.c 四、綜合應用題（每小題8分，5題，共40分） 題目32 （1 ）以3,4,5 , 8 , 9 ,作為口埠點的權，構造一棵咯夫曼樹.該樹的帶權路徑長度為B 9 A, 64 B.65 C.62 D. 66 （2）權重為3的葉結點的哈夫曼編碼為C # ?. A. 010 B.0101 C.000 D.0111 題目33 （1 ）以2,3,4,7 , 8 , W乍為口理點的權，構造一棵咕夫曼樹，岫的帶權路徑長度為B = 力 A. 66 B.80 C. 62 D. 87 （2）權重值為4的葉結點的哈夫曼編碼為C# /? A. 0001 B 1110 C.001 D. 110 題目34 （1） 已知某二叉樹的后序遍歷序列是debca,中序遍歷序列是dbeac,該二叉樹的根結點是DS “ A. e B. c C. b D. a （2） 先序遍歷序列是c= y? A. e.b.c.d.a B.c,a,b,,d,e C. a.b.d.e.c D. a.c.b.d.e, 題目35 ⑴已知某二叉樹的先序遍歷序列是aecdb,中序遍歷序列是eadcb,該二叉樹的根結點是DS ； A. e B.C C.b （2 ）后序遍歷序列為A $ ?. A. e.d.b.c.a B. c,a,b“d.e C. a.b.d.e.c D. a.c.b.d.e, 題目36 （1）以給定權重值5, 6, 17, 18, 25, 30,為葉結點，建立一棵哈夫曼樹，該樹的中序遍歷序列為B A. 5, 11, 28, 6, 17, 58, 30, 101, 18, 43, 25 B.5, 11, 6, 28, 17, 58, 30, 101, 18, 43, 25 C. 5, 11, 6, 28, 101, 58, 30, 17, 18, 43, 25 D.5, 11, 6, 28, 17, 58, 30, 101, 18, 25, 43 （2）權重值為6的葉結點的哈夫曼為D t A. 1001 B. 011 C.001 D.0001 切任務4 一、單項選擇題（每小題2分，共40分） 題目1 對線性表進行二分查找時，要求線性表必須（）o 選擇一項： A. 以鏈接存儲方式 B. 以鏈接存儲方式，且數(shù)據(jù)元素有序 C. 以順序存儲方式 D. 以順序存儲方式，且數(shù)據(jù)元素有序 題目2 采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（）. 選擇一項： A. n B. （n-l）/2 C. n/2 D. （n+l）/2 有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）. 選擇一項： A. 29/9 B. 29/10 C. 26/10 D. 31/10 題目4 已知一個有序表為{11, 22, 33,44, 55, 66, 77,88,99},則順序查找元素55需要比較（）次。 選擇一項： A. 6 B. 3 C. 5 D. 4 題目5 有數(shù)據(jù)（53,30,37,12,45,24,96},從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應該選擇的序 列是（）。 選擇一項： A. 12, 24, 30, 37, 45, 53, 96 B. 30, 24, 12, 37, 45, 96, 53 C. 45, 24, 53, 12, 37, 96, 30 D. 37,24,12,30,53,45,96 題目6 對于順序存儲的有序表（5, 12, 20, 26, 37,42,46, 50,64）,若采用折半查找，則查找元素26的比較次數(shù)是（）。 選擇一項： A. 4 B. 6 C. 3 D. 5 題目7 在所有的捶序方法中，關鍵字比較的次數(shù)與記錄初始排列秩序無關的是（）<> 選擇一項： A.希爾排序 b.直^#排序 C. 冒泡排序 D. 直接插入排序 題目8 從未捶序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已捶序序列的正確的位置上，此方法稱 為（）＜, 選擇一項： A. 插入排序 B. 選擇排序 C. 歸并排序 D. 交換排序 題目9 依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（）＜＞ 選擇一項： A. 交換排序 B. 歸并排序 C. 插入排序 D. 選擇排序 題目10 當兩個元素出現(xiàn)逆序的時候就交換位置，這種排序方法稱為（）。 選擇一項： A. 選拜排序 B. 插入排序 C. 歸并排序 D. 薄排序 題目11 每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間，其中左區(qū)間中記錄的關鍵字均小于等于基準記錄的關鍵字，右區(qū)間中 記錄的關鍵字均大于等于基準記錄的關鍵字，這種排序稱為（）。 選擇一項： A. 插入捶序 B. 快速拜序 C. 堆排序 D. 歸并排序 一組記錄的關鍵字序列為（46,20,30,79, 56, 38, 40, 84, 90,110）,利用快速排序，以第一個關鍵字為分割元素, 經(jīng)過一次劃分后結果為（） 選擇一項： A. 40, 20,30,38, 46, 56, 79, 84,90,110 B. 20, 30 38, 40, 46, 56, 79. 84, 90, 100 C. 20,30,40, 38. 46. 79, 56. 84,90,100 D. 30,20,40, 38, 46, 84, 56, 79,90, 100 題目13 在有序表（10,14, 34, 43, 47, 64, 75, 80. 90｝中，用折半查找法查找值80時，經(jīng)（ ）次比較后查找成功。 選擇一項： A. 5 B. 3 C. 2 D. 4 題目14 對序列（49, 38, 65, 97, 76, 13, 47, 50）采用直接插入排序法進行排序，要把第七個元素47插入到已排序中， 為尋找插入的合適位置需要進行（）次元素間的比較。 選擇一項： A. 3 B. 4 C. 6 D. 5 題目15 排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（）捧序。 選擇一項： A. 插入 B. 快速 C. 歸并 D. 選擇 題目16 一組記錄的關鍵字序列為（26, 59. 36, 18, 20, 25）,利用堆排序的方法建立的初始小根堆為（）。 選擇一項： A. 26, 18, 59, 20, 36, 25 B. 18, 20, 25, 69, 26, 36 C. 18, 20. 36, 59, 26, 25 D. 26, 59, 36, 18, 20. 25 題目17 一組記錄的關鍵字序列為(25, 48. 16, 35. 79, 82, 23, 40, 36, 72),其中，含有5個長度為2的有序表，按歸 并排序的方法對該序列進行一趟歸并后的結果為()<> 選擇一項： A. 16, 25, 35, 48, 79, 23, 36, 40, 82, 72 B. 16, 25, 36, 48, 23, 40, 79, 82, 36, 72 C. 16, 25, 48, 35. 79, 82, 23, 36, 40. 72 D. 16, 25, 35, 48, 79, 82, 23, 36, 40, 72 題目18 已知10個數(shù)據(jù)元素為(54, 28, 16, 34, 73, 62, 95, 60, 26, 43),對該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后 的序列為()。 選擇一項： A. 16, 28, 34, 54, 62, 60, 73, 26, 43, 95 B. 28, 16, 34, 54, 62, 73, 60, 26, 43, 95 C. 16, 28, 34, 54, 73, 62, 60. 26, 43, 95 D. 28, 16, 34, 54, 62, 60, 73, 26, 43, 95 題目19 一組記錄的關鍵字序列為(46. 79. 56, 38. 40, 84),利用快速排序，以第一個關鍵字為分割元素，經(jīng)過一次劃分 后結果為(). 選擇一項： A. 40, 38, 46, 84, 56, 79 B. 40, 38, 46, 79, 56, 84 C. 38, 40, 46, 56, 79, 84 D. 40, 38, 46, 56, 79, 84 題目20 一組記錄的關鍵字序列為(80,57,41,39,46,47),利用堆排序(堆頂元素是最小元素)的方法建立的初始堆為( ). 選擇一項： A. 39, 80, 46, 47, 41, 57 B. 39, 46, 41, 57, 80, 47 C. 41, 39, 46, 47, 57, 80 D. 39, 47, 46, 80. 41, 57 二、程序填空題(每題10分，2J8,共20分.請點擊正確選項，然后拖拽至相應的方框上) 題目21 以下函數(shù)是二又排序樹的查找算法，若二又樹為空，則返回根結點的指針，否則，返回值是指向樹結點的結構指 針P (查找成功P指向查到的樹結點，不成功P指向為NULL)完成程序中的空格 typedef struct Bnode { int key; struct Bnode *left; struct Bnode *right; ) Bnode; Bnode *BSearch(Bnode *bt, int k) r bt用于接收二叉排序倒的根結點的指針，k用以接收要直找的關鍵字*/ ( Bnode *p; if(bt== NULL 寸) return (bt); P=bt; while(p->key!= k 寸) ( if(kkey) p=p->left 寸； else p=p->right y ; if(p==NULL) break; } return( p v ; ) 題目22 以下程序是折半插入排序的算法 設待排序的記錄序列存放在a[l],???a[n]中，以a[0]作為輔助工作單元，程序是要把a[i]插入到已經(jīng)有序的序 void binsort (NODE a[ ]jnt n) { intxjj.sKm; for (i=2 ; i<= n 寸;i++ ) { a(0]=ali]; x= a[i].key; S=1； j=i-1； while (s<=j) { m=| (s+jy2 I ? for (k=k1;k>=j+1;k--) a[k+l] v =a[k]; a[j+1]=a[Oj; } } 三、綜合題(每小題8分，共40分) 題目23 (1)設查找表為(1,10,11,14,23,27,29,55,68)，畫出對上述直找表進行折半直找所對應的判定樹，為了成功查 找到元素14,需要依次與元素C = V進行比較。 A. 23.10.1.14 B.23.29.27.14 C. 23.10,11.14 D.23.29.55,14 (2 )在等概率條件下，成功查找的平均比較次數(shù)為B # V。 A. 24/9 B. 25/9 C.3 D.2.5 題目24 2 - (47、80、57、3gkr46 )、^sisiiMU^ B " < 《磊島沖洲池婀、M沖洲-米曲食3*斗厚)。 >? 39-4L57.847.46 B.3g.4BCDp47.57 0- 3g.47.46.84L57 D.39.4L5700P46.47 Q 淳任A " < - A4M7.46.8P57 B.4L5746.8P47 C.4L57.8P47.46 D.4L8P4647.57 s 25 (1)咨冰電囤倒(56公.7言4含.占6).絲魚港廁贛>? 、潛白—>竺少on爵油 翌c ” < ; >? 46.5L56.54m 二。6 B. 56.5L54.46.7二06 0-46.5L54.56.7L106 0. 56.5L46.54.71M6 -e —Baucis ( 6.470?57、39kr46 .3。)、座理1JJ%4 藻3,卅成K(2.2s*s 籍&*一 0 A?(3p57. 6P8P47.39.4L46 ) B.(47. 6P57?000. 3P39BM6 ) C.(4L 57. 6P8P30.3g.47.46 ) 0. (47. 573 8P30.3941 .46 ) 筒IE26 (1) 涔冰漏40囤涅(36念.46.28.3。?74)湘丑>5廖贛>、H普府*葉慰弟、的心—壽竺冷5B3器油 畫浸D " < A3T 28 ~ 46 ~ 36 ~ 69 ~74 B.2S03?36 ~ 46 ~ 69 ~ 74 92W 3CL46L6 ~ 69 ~ 74 0- 3T 28 ~ 36k6 ~ 69 L4 (2) ? >? 36.28.3。46念.74 w 3646.28.2P69-74 ?0- 38.36.3。.46 念.74 D.2B.36..3P46.6W74 S 27 (--、4。、65\3 ? 35 ? 951任迷前一港圓巖教圳研? 座3&性d)曹醐涉00 < - A 35 40 65 45 35 95 B 35 4。65 43 45 95 935 4043 45 65 95 D? 35 40 45 43 65 95 （2 ）對上述序511利用直接插入排序，逐次插入過程中，共進行了 D U /次元素間的比較? A. 8 B. 11 C.9 D 10 《離散數(shù)學》網(wǎng)絡課答案 瞬任務］ 5選擇題 題目1 若集合A={ a, {a}, {1, 2}},則下列表述正確的是（）. 選擇一項： A. （1 , 2}玷 B. {a,間}3 。C.{a}c^ D. 0G/I 題目2 若集合A={2, a, { a }, 4},則下列表述正確的是（）. 選擇一項： A?{a}Q射 B. 0ez C. {2}ezi D. {a, （a jjezi 題目3 設集合 A={1 ,2,3, 4}上的二元關系 R=K1, 1〉, <2, 2>, <2, 3>, <4, 4>}, S=l, 1>, <2, 2>, <2, 3>, <3, 2>, <4, 4>},則S 是1?的（ ）閉包. 選擇一項： A. 傳遞 B. 咐 C. 自反和傳遞 D. 自反 題目4 設集合 A={1, 2, 3}, B={3, 4, 5}, C={5, 6, 7},則 AUB-C =（）. 選擇一項： A. {1, 2, 3, 5} B. （4, 5, 6, 7} C. （2, 3, 4, 5} D. （1, 2, 3, 4） 題目5 如果R1和R2是A上的自反關系，則R1UR2, R1AR2, R1-R2中自反關系有（ ）個. 選擇一項： A. 1 B. 3 C. 2 D. 0 題目6 集合A={1, 2, 3, 4}上的關系R={|x=y且x, ye A},則R的性質為（ ）. 選擇一項： A. 不是對稱的 B. 反自反 C. 不是自反的 D. 傳遞的 題目7 若集合A={1, 2}, B={1, 2, （1, 2}},則下列表述正確的是（）. 選擇一項： A. 83,且住 B. AU3 ,且腥 8 C. 4U饑且住矽 D. MZieS 題目8 設A={a, b, c}, B={1. 2],作f： A-B,則不同的函數(shù)個數(shù)為（ ）. 選擇一項： A. 3 B. 2 C. 8 D. 6 題目9 設入={1, 2, 3, 4, 5, 6, 7, 8）, R是A上的整除關系，B=（2, 4, 6},則集合B的最大元、最小元、上界、下界依 次為（）. 選擇一項： A. 6、 2、 6、 2 B. 2、 2 C. 8、 1、 6、 1 D. 8、2、8、2 題目10 設集合A =(1 , 2, 3}上的函數(shù)分別為： f = 1, 2>, <2, 1>, <3, 3, g = (<1, 3>, <2, 2>, <3, 2>], h = 1, 3>, <2, 1>, <3, !>}, 則 h =( ). 選擇一項： A. Pf B. gof C. gog D. fg 判9HK 題目11 設入={1, 2}上的二元關系為/Kx, y>|xA, yA, x+y =10},則R的自反閉包為Kl, 1>, <2, 2>}.( ) 選擇一項： 對 錯 題目12 空集的藉集是空集.( ) 選擇一項： 對 錯 題目13 設入=氐 b}, B={1, 2), C={a, b},從 A 到 B 的函數(shù) f=(, },從 B 到 C 的函數(shù) g={, <2, a >}, 則 g f ={<1, 2 >, <2, 1 >}.( ) 選擇一項： 對 題目14 設集合 A={1, 2, 3, 4}, B={2, 4, 6, 8),下列關系 f = 1, 8>, <2, 6>, <3, 4>, <4, 2,>}可以構成函數(shù) f：.() 選擇一項： 對 錯 題目15 設集合 A={1, 2, 3}, B={2, 3, 4}, C=(3, 4, 5},則 AA(C-B )= (1, 2, 3, 5}.( ) 選擇一項： 對 錯 題目16 如果R1和R2是A上的自反關系，則、R1UR2、R1C1R2是自反的.( ) 選擇一項： 對 錯 題目17 設集合A= {a, b, c, d}, A上的二元關系R=Ka, b>, , , , <1, 2>, <3, 3>},則R是對稱的關系.( ) 選擇一項： 對 錯 題目20 設集合 A={1, 2f 3, 4 }, B={6, 8, 12}, A 到B 的二元關系 R=那么 R-l = 6, 3>, <8,4>}.( ) 選擇一項： 對 錯 電任務2 g選擇題 題目1 無向完全圖K4是（ ）. 選擇一項： A. 樹 B. 歐拉圖 C. 漢密爾頓圖 D. 非平面圖 題目2 已知一棵無向樹T中有8個頂點，4度、3度、2度的分支點各一個，T的樹葉數(shù)為（）. 選擇一項： A. 4 B. 8 C. 3 D. 5 題目3 設無向圖G的鄰接矩陣為 0 1 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 1 1 1 0 1 0 則G的邊數(shù)為（ 選擇一項： A. 7 B. 14 C. 6 D. 1 題目4 如圖一所示，以下說法正確的是（）. 選擇一項： A. ((a, e) , (b, c)}是邊割集 B. ((a, e)｝是邊割集 C. ((d, e)｝是邊割集 D. {(a, e)｝是割邊 題目5 以下結論正確的是(). 選擇一項： A. 有n個結點n-l條邊的無向圖都是樹 B. 無向完全圖都是平面圖 C. 樹的每條邊都是割邊 D. 無向完全圖都是歐拉圖 題目6 若G是一個歐拉圖，則G一定是(). 選擇一項： A. 漢密爾頓圖 B. 連通圖 C. 平面圖 D. 對偶圖 題目7 設圖G=. ve\\則下列結論成立的是(). 選擇一項： A.云&駒=平卜 B ydeg(v) = || rsr C. deg(v)=2|E| D. deg(v)=|5| 題目8 圖G如圖三所示，以下說法正確的是(). 選擇一項： A. (b, d｝是點割集 B. ｛c｝是點割集 C. ｛b, c｝是點割集 D. a是割點 設有向圖(a)、(b)、(c)與(d)如圖五所示，姻下列結論成立的是(). 選