2023年數(shù)據(jù)結(jié)構(gòu)考試試題庫(kù)含答案解析

數(shù)據(jù)結(jié)構(gòu)習(xí)題集含答案目錄ＴＯC\ｏ"1-２＂\h\z\uHYPＥＲLＩNK＼l"_Tｏｃ"目錄 ＰAGＥREF＿Tｏc＼h1HYPERＬINK選擇題?ＰAGERＥF_Tｏc\h２ＨYPERLＩNK第一章緒論 PＡGERＥＦ_Toc＼h2HYPEＲLINK＼l"_Ｔoｃ"第二章線(xiàn)性表?ＰAGEREF_Toc\h4HYPＥRＬＩNK第三章棧和隊(duì)列?PAGＥＲEF_Toc\h５HYPEＲＬINK\ｌ"_Toc"第四章串 ＰAGERＥF_Ｔoc＼ｈ6ＨＹPEＲLＩNK＼l＂_Toc"第五章數(shù)組和廣義表 ＰAGＥRＥF＿Toｃ\h7HYPERＬＩＮK第七章圖?ＰAＧERＥF＿Ｔoc\h９HYPERＬINK第八章查找?PAGEREF_Tｏc\h11HＹＰEＲＬINＫ第九章排序 PAGＥREF＿Tｏｃ\h12HYPEＲＬIＮK第一章緒論?＼h1５HYＰＥRＬINＫ\ｌ＂_Tｏc"第二章線(xiàn)性表?PＡＧERＥF_Ｔoc\ｈ２0HYPERLＩＮK\l＂＿Ｔｏc"第三章棧和隊(duì)列?ＰAＧEREＦ＿Toc\h22ＨYPERＬINK＼ｌ"_Toc"第四章串 ＰAGEREF＿Toc\h24ＨＹＰERLＩNK第六章樹(shù)和二叉樹(shù)?PAＧEＲEF_Tｏc\h26HYPERLＩNK第七章圖 PAGEREF＿Ｔｏc\h31ＨYＰＥRLINK＼l"_Toc"第八章查找?PAGEREF_Tｏｃ\h3３ＨYPEＲLINＫ\ｌ"_Toc"第九章排序?PAＧEREF＿Toc\ｈ34HYＰＥRＬＩNＫ\ｌ"_Toc＂編程題?ＰAGEＲEＦ_Toc＼ｈ36HYＰERＬINＫ\ｌ"_Toc"第一章緒論?ＰAGＥRＥF_Ｔｏｃ\h36HYPERLIＮK第二章線(xiàn)性表?PＡＧERＥＦ_Toc\h36ＨYPERＬＩＮK第三章棧和隊(duì)列?ＰＡGEREF_Toc\h46HYPERＬINK第四章串 PAＧEＲEF_Toc\h４6ＨYPERLINK\ｌ＂＿Tｏc"第五章數(shù)組和廣義表?ＰAGEREF_Tｏc\h4６HYPＥRLINＫ\l＂＿Toｃ"第六章樹(shù)和二叉樹(shù)?PAGERＥF_Toc＼h46HYＰERＬINＫ＼ｌ"_Ｔoc"第七章圖?PＡＧERＥF_Tｏｃ\ｈ46HYPERLINＫ第九章排序?PＡGＥＲEF_Toｃ\h51選擇題第一章緒論數(shù)據(jù)結(jié)構(gòu)這門(mén)學(xué)科是針對(duì)什么問(wèn)題而產(chǎn)生的?（A）A、針對(duì)非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題?B、針對(duì)數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題C、數(shù)值計(jì)算與非數(shù)值計(jì)算的問(wèn)題都針對(duì) D、兩者都不針對(duì)數(shù)據(jù)結(jié)構(gòu)這門(mén)學(xué)科的研究?jī)?nèi)容下面選項(xiàng)最準(zhǔn)確的是（Ｄ）A、研究數(shù)據(jù)對(duì)象和數(shù)據(jù)之間的關(guān)系?Ｂ、研究數(shù)據(jù)對(duì)象C、研究數(shù)據(jù)對(duì)象和數(shù)據(jù)的操作?D、研究數(shù)據(jù)對(duì)象、數(shù)據(jù)之間的關(guān)系和操作某班級(jí)的學(xué)生成績(jī)表中查得張三同學(xué)的各科成績(jī)記錄，其中數(shù)據(jù)結(jié)構(gòu)考了90分，那么下面關(guān)于數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)描述對(duì)的的是（Ｃ）A、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)元素,９0分是數(shù)據(jù)項(xiàng)Ｂ、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)對(duì)象，90分是數(shù)據(jù)元素C、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)對(duì)象，9０分是數(shù)據(jù)項(xiàng)Ｄ、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)元素,９0分是數(shù)據(jù)元素＊數(shù)據(jù)結(jié)構(gòu)是指（A）。A、數(shù)據(jù)元素的組織形式 ? B、數(shù)據(jù)類(lèi)型C、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu) ? ? D、數(shù)據(jù)定義數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表達(dá)時(shí),物理地址與邏輯地址不相同,稱(chēng)之為（C)。Ａ、存儲(chǔ)結(jié)構(gòu) ?? ? B、邏輯結(jié)構(gòu)C、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)? ? ? D、順序存儲(chǔ)結(jié)構(gòu)算法分析的目的是（C）A、找出數(shù)據(jù)的合理性???B、研究算法中的輸入和輸出關(guān)系Ｃ、分析算法效率以求改善? D、分析算法的易懂性和文檔型性算法分析的重要方法(A)。Ａ、空間復(fù)雜度和時(shí)間復(fù)雜度 ?Ｂ、對(duì)的性和簡(jiǎn)明性Ｃ、可讀性和文檔性 D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性計(jì)算機(jī)內(nèi)部解決的基本單元是(B）A、數(shù)據(jù)? Ｂ、數(shù)據(jù)元素 ?Ｃ、數(shù)據(jù)項(xiàng)??Ｄ、數(shù)據(jù)庫(kù)數(shù)據(jù)在計(jì)算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲(chǔ)方式，在存儲(chǔ)空間使用的靈活性上,鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)要（B）。Ａ、低 Ｂ、高? ?C、相同 ? D、不好說(shuō)算法的時(shí)間復(fù)雜度取決于（C）Ａ、問(wèn)題的規(guī)模 ? ???B、待解決數(shù)據(jù)的初始狀態(tài)C、問(wèn)題的規(guī)模和待解決數(shù)據(jù)的初始狀態(tài)??D、不好說(shuō)數(shù)據(jù)結(jié)構(gòu)既研究數(shù)據(jù)的邏輯結(jié)構(gòu),又研究物理結(jié)構(gòu)，這種觀(guān)點(diǎn)(B）。A、對(duì)的?? ? ?B、錯(cuò)誤C、前半句對(duì)，后半句錯(cuò)?? D、前半句錯(cuò)，后半句對(duì)在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)提成(C)A、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) ??B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu) D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種(）的存儲(chǔ)結(jié)構(gòu)，線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種（A)存儲(chǔ)結(jié)構(gòu)。A、隨機(jī)存取?? ?Ｂ、順序存取C、索引存取? ???Ｄ、散列存?。铝谐绦虻臅r(shí)間復(fù)雜度是（Ａ）for(ｉ=1;i<＝n;++i){fｏｒ(j=1;j＜=ｎ；+＋j){ｃ[i][j］＝0；}}Ａ、O(n2) B、O(n） ?C、O(2n) D、O(2n2)*下列程序的空間復(fù)雜度是(A)for(i=1;ｉ<＝ｎ；+＋ｉ){for（j＝１;j<=m；+＋ｊ)｛c[ｉ][ｊ]＝0;}}Ａ、O(m＊n) ?B、O(m+n)??Ｃ、O(m-n）?Ｄ、O(m/n)＊求下列程序段的時(shí)間復(fù)雜度(B)foｒ(i＝1;i<=n;i＋＋)fｏｒ（j＝1;j<=n;j++) ?x=x+1;A、O(n2)B、O(n)C、O(1)Ｄ、O（0)第二章線(xiàn)性表關(guān)于線(xiàn)性表的說(shuō)法不對(duì)的的是?(D）A、存在唯一的一個(gè)被稱(chēng)為“第一個(gè)”的數(shù)據(jù)元素(開(kāi)始結(jié)點(diǎn)）B、存在唯一的一個(gè)被稱(chēng)為“最后一個(gè)”的數(shù)據(jù)元素（終端結(jié)點(diǎn))Ｃ、除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū) D、除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼關(guān)于順序表的說(shuō)法不對(duì)的的是？（Ｄ）A、邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰B、可以隨機(jī)存取表中任一元素，方便快捷Ｃ、在線(xiàn)性表中插入某一元素時(shí),往往需要移動(dòng)大量元素D、在線(xiàn)性表中刪除某一元素時(shí)，無(wú)需移動(dòng)大量元素當(dāng)線(xiàn)性表的元素總數(shù)基本穩(wěn)定,且很少進(jìn)行插入和刪除操作,但規(guī)定以最快的速度存取線(xiàn)性表中的元素時(shí)，應(yīng)采用什么存儲(chǔ)結(jié)構(gòu)？(A)A、順序表 Ｂ、單鏈表?C、循環(huán)鏈表?D、雙鏈表在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1＜=i＜=n)之前插入一個(gè)元素時(shí)，需向后移動(dòng)多少個(gè)元素。（C)Ａ、n-1?B、n-ｉ?C、n-i+1 D、ｎ-i－1在單鏈表中設(shè)立頭結(jié)點(diǎn)的作用是()。A、單鏈表定義而已 B、指定表的起始位置?C、為雙向鏈表做準(zhǔn)備?D、為循環(huán)鏈表做準(zhǔn)備根據(jù)線(xiàn)性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針數(shù),將線(xiàn)性鏈表提成（C)A、單鏈表與循環(huán)鏈表 Ｂ、單鏈表與十字鏈表?Ｃ、單鏈表與雙鏈表?D、循環(huán)鏈表與多鏈表鏈接存儲(chǔ)的特點(diǎn)是運(yùn)用什么來(lái)表達(dá)數(shù)據(jù)元素之間的邏輯關(guān)系（Ａ?)A、引用?B、串聯(lián) C、掛接 D、指派已知指針ｐ指向單鏈表Ｌ中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語(yǔ)句是（D)A、ｐ=p.next?B、ｐ=nulｌ C、p.nｅｘt=nｕｌｌ?D、p.next＝p.next．next*在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是(Ｂ）A、ｐ=p.next?B、p.neｘt!=nｕlｌC、p．nexｔ=null D、ｐ．ｎexｔ=p.nexｔ.next*在單鏈表p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是(C)A、p.nexｔ=s;ｓ.next=p.neｘｔ； B、ｓ．nexｔ＝p.nexｔ;p.nｅxt=p.nｅxt.next;C、s.nｅxt=p．neｘt;p.nｅxt=ｓ; D、s．ｎext＝p;p.ｎext＝s;第三章棧和隊(duì)列棧、隊(duì)列通常采用兩種存儲(chǔ)結(jié)構(gòu)，它們是(Ｂ)A、散列方式和索引方式?B、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C、鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組?D、線(xiàn)性和非線(xiàn)性存儲(chǔ)結(jié)構(gòu)一個(gè)棧入棧序列是a,b,c,d,則棧輸出序列不也許是(C）A、d,ｃ,b,ａ B、c,d，b，a?Ｃ、ｄ,c,a,b D、ａ,b,c,ｄ判斷順序棧（最多結(jié)點(diǎn)數(shù)為m)為棧滿(mǎn)的條件是（D）A、tｏp==0B、top!＝mC、toｐ!=0D、top=＝m棧存取數(shù)據(jù)原則(或棧特點(diǎn)）是（B)Ａ、后進(jìn)后出B、后進(jìn)先出C、先進(jìn)先出Ｄ、隨意進(jìn)出*通過(guò)以下棧運(yùn)算后，x的值是(A）IｎitＳtaｃｋ(s);Ｐush(ｓ,d）;Ｐuｓh(s,e）;Pop(s,x);Ｐop(s，x）;GeｔTop(s,x）;Ａ、dB、eＣ、xD、ｓ一個(gè)隊(duì)列的進(jìn)隊(duì)序列為:a，b，c,d,則出隊(duì)序列是:(A)Ａ、a,ｂ,c，dB、ｄ,ｃ，b，aＣ、a，d,c,ｂD、c,b，d,a循環(huán)隊(duì)列為空隊(duì)列的條件是：（D)A、Q.froｎt＝0? B、Q.(reａr+１)%ＭaｘSｉzｅ＝=Q.fｒontC、Q.rｅar=0D、Q.rｅar==Q.frｏnt在存儲(chǔ)結(jié)構(gòu)上,假如用帶頭節(jié)點(diǎn)單鏈表實(shí)現(xiàn)隊(duì)列（假定fronｔ和reａｒ分別為隊(duì)首和隊(duì)尾指針),則刪除一個(gè)結(jié)點(diǎn)的操作為（A）。A、froｎt.neｘｔ=ｆronｔ.ｎexｔ.next?B、rear=ｒｅar.nextC、rear=front.nｅxt? ? D、ｆｒｏnt=froｎｔ．next棧和隊(duì)列共同點(diǎn)是（Ｃ)Ａ、先進(jìn)后出 ??? ?B、先進(jìn)先出C、允許在端點(diǎn)處進(jìn)行操作線(xiàn)性表??D、無(wú)共同點(diǎn)插入和刪除只能在一端進(jìn)行的線(xiàn)性表是（B）A、循環(huán)隊(duì)列B、棧Ｃ、隊(duì)列D、循環(huán)棧插入和刪除分別在兩端端進(jìn)行的線(xiàn)性表是(C）Ａ、循環(huán)隊(duì)列B、棧Ｃ、隊(duì)列Ｄ、循環(huán)棧循環(huán)隊(duì)列為滿(mǎn)隊(duì)列的條件是：(B）Ａ、Q.fronｔ=0 ?Ｂ、Ｑ.(ｒｅａr+1)％MaxSize＝=Ｑ．frontＣ、Q．ｒｅａr=0D、Q.ｒeａr==Q．froｎt第四章串關(guān)于串的敘述,錯(cuò)誤的是：(B）A．串是字符有限序列?B.空串是由空格構(gòu)成的串C．模式匹配是串的重要運(yùn)算D．串有用順序、鏈?zhǔn)絻煞N存儲(chǔ)方式串長(zhǎng)度是指（B)A.串所含不同字母數(shù)目B．串所含字符數(shù)目C.串所含不同字符數(shù)目D．串所含非空格字符數(shù)目*若串S＝”database”,其子串?dāng)?shù)目是(Ｂ)。A．1６Ｂ.3７Ｃ.8Ｄ.36設(shè)串Ｓ１是串Ｓ子串,則求S1在S中定位運(yùn)算稱(chēng)為（B）A.求子串B.串匹配C.聯(lián)接Ｄ.求串長(zhǎng)設(shè)有串s1=”ｗelcometozdsoftｃolleaｇe！”和s2=”so”,那么s2在s１中的索引位置是（C）A．12B．14C.1３D．10＊若串S＝“soｆtwaｒe“,其子串的數(shù)目是(Ｂ)。A.8B.3７C．36D.9第五章數(shù)組和廣義表第六章樹(shù)和二叉樹(shù)假設(shè)在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為1５,單分支結(jié)點(diǎn)數(shù)為３0個(gè)，則葉子結(jié)點(diǎn)數(shù)為（Ｂ）個(gè)。A．１5?? B.1６ ??C.1７ D.4７假定一棵三叉樹(shù)的結(jié)點(diǎn)數(shù)為５０，則它的最小高度為(C）。A.３???B．4?? C.5? ?D.６在一棵二叉樹(shù)上第4層的結(jié)點(diǎn)數(shù)最多為(Ｄ）。A.2? B.4? ?C.６ ??D．8用順序存儲(chǔ)的方法將完全二叉樹(shù)中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R[1..n］,結(jié)點(diǎn)R［ｉ]若有左孩子,其左孩子的編號(hào)為結(jié)點(diǎn)(B）。Ａ.R[2i+1]?Ｂ．Ｒ［2ｉ］ C.Ｒ[ｉ/２］ D．R［2i-1]設(shè)n,ｍ為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn),在中序遍歷序列中ｎ在m前的條件是(B)。Ａ．n在m右方 B.n在ｍ左方C.n是m的祖先 D.n是m的子孫下面敘述對(duì)的的是（D）。A.二叉樹(shù)是特殊的樹(shù)Ｂ.二叉樹(shù)等價(jià)于度為2的樹(shù)C.完全二叉樹(shù)必為滿(mǎn)二叉樹(shù)D.二叉樹(shù)的左右子樹(shù)有順序之分現(xiàn)有一深度為５的二叉樹(shù)，請(qǐng)問(wèn)其最多有(D)個(gè)結(jié)點(diǎn)。A.32??B．5?? Ｃ.3０ ??D.31現(xiàn)有一深度為4的二叉樹(shù)，請(qǐng)問(wèn)其最多有(Ａ）個(gè)結(jié)點(diǎn)。Ａ.１5??B.１6 ? Ｃ.17 ?Ｄ．6在一棵二叉排序樹(shù)上按（B)遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。Ａ.先序 ?B.中序 ??C.后序 D．頭序在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n２，則n0=(C)A.n+１??B.ｎ+2?? C.n2+1 D.2ｎ+1由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù),共有（B）種不同的形態(tài)。A.4 B.5? Ｃ．6 ?D.7一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，(A)形態(tài)達(dá)成最大深度。Ａ.單支樹(shù) ?B.二叉樹(shù) ? C.三 叉樹(shù)?D．n叉樹(shù)不含任何結(jié)點(diǎn)的空樹(shù)（C）。

Ａ．是一棵樹(shù);

Ｂ.是一棵二叉樹(shù);

Ｃ.是一棵樹(shù)也是一棵二叉樹(shù);

D.既不是樹(shù)也不是二叉樹(shù)二叉樹(shù)是非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，所以(

Ｃ

)

。

Ａ．它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ);

Ｂ.它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ);

C.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ);

Ｄ.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用

具有n(n>0）個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為(Ｃ)。

Ａ.lｏg2(n）

Ｂ.

lｏg２(n)

Ｃ.[

lｏg2（n）

]+1

D.loｇ2(n)+1

在一棵三元樹(shù)中度為3的結(jié)點(diǎn)數(shù)為2個(gè),度為2的結(jié)點(diǎn)數(shù)為１個(gè)，度為1的結(jié)點(diǎn)數(shù)為２個(gè),則度為0的結(jié)點(diǎn)數(shù)為(D)個(gè)。

A.4? B．５? Ｃ.6 D.7有關(guān)二叉樹(shù)下列說(shuō)法對(duì)的的是（B

）

A.二叉樹(shù)的度為2

?B．一棵二叉樹(shù)的度可以小于2

Ｃ.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2 D.二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2在完全二叉樹(shù)中,若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒(méi)（C

)。

Ａ.左子結(jié)點(diǎn)

?? Ｂ．右子結(jié)點(diǎn)

Ｃ．左子結(jié)點(diǎn)和右子結(jié)點(diǎn) D.左子結(jié)點(diǎn),右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)在下列情況中,可稱(chēng)為二叉樹(shù)的是（B

）

A.每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的樹(shù)??Ｂ．

哈夫曼樹(shù)

C.每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的有序樹(shù) D．

每個(gè)結(jié)點(diǎn)只有一棵右子樹(shù)

第七章圖圖的深度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的(A）。A．先序遍歷Ｂ.中序遍歷Ｃ．后序遍歷D．層次遍歷已知一個(gè)圖如圖所示,若從頂點(diǎn)a出發(fā)按深度優(yōu)先遍歷,則也許得到的一種頂點(diǎn)序列為（C）Ａ．ａｂｅｃdf?Ｂ．a(chǎn)ｃfｅbｄ Ｃ．a(chǎn)ebcfd D.aeｄfcｂ若從無(wú)向圖的任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索可以訪(fǎng)問(wèn)圖中所有的頂點(diǎn),則該圖一定是(Ｂ）圖。Ａ．非連通B.連通Ｃ．強(qiáng)連通D.有向在一個(gè)圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的(C)倍。A１/2B1Ｃ2D3在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的(B)倍。Ａ1／2Ｂ1C2D3一個(gè)有N個(gè)頂點(diǎn)的有向圖最多有（B)條邊。ＡNBN(N-1)ＣN(n－１)/２D２N具有4個(gè)頂點(diǎn)的無(wú)向完全圖有(A)條邊。A6Ｂ1２C１8D20具有6個(gè)頂點(diǎn)的無(wú)向圖至少有(A)條邊才干保證是一個(gè)連通圖。A5B6C7Ｄ8對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表達(dá)，則該矩陣大小是(D)ANB(N-1)2CＮ-1DN*N一個(gè)具有Ｎ個(gè)頂點(diǎn)的無(wú)向圖中,要連通所有頂點(diǎn)至少要(Ｃ)條邊ＡＮBＮ＋1CＮ-1DN/2*已知圖的鄰接矩陣如圖所示,則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)果是(C)。Ａ．0２４31５６ B．013654２ Ｃ.０1３4256 D．036154２已知圖的鄰接表下圖所示,則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（)，按深度優(yōu)先遍歷的結(jié)果是（Ｄ)。Ａ.０132B．0231?C.０３21D.012３已知圖的鄰接表下圖所示，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（）,按深度優(yōu)先遍歷的結(jié)果是（)。A.01３2B.02３１C.0321Ｄ．01２３當(dāng)在一個(gè)有序的順序表上查找一個(gè)數(shù)據(jù)時(shí)，既可用折半查找，也可用順序查找，但前者比后者的查找速度（Ｃ)。Ａ．必然快B．不一定C.在大部分情況下要快D.取決于表遞增還是遞減折半查找有序表（4,６，１０，１2,2０，30，50,70，８８，100)。若查找表中元素58,則它將依次與表中（A）比較大小,查找結(jié)果是失敗。A.２0，70，30，50Ｂ.３０,88，70，５0C.20,50D.3０,88,50第八章查找順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（B)的線(xiàn)性表。A.散列存儲(chǔ)Ｂ.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C．壓縮存儲(chǔ)D.索引存儲(chǔ)在查找過(guò)程中，若同時(shí)還要增、刪工作，這種查找稱(chēng)為（B）。Ａ、靜態(tài)查找B、動(dòng)態(tài)查找C、內(nèi)查找D、外查找索引順序表的特點(diǎn)是順序表中的數(shù)據(jù)（Ａ）。A、有序B、無(wú)序C、塊間有序Ｄ、散列采用順序查找方法查找長(zhǎng)度為n的線(xiàn)性表時(shí),每個(gè)元素的平均查找長(zhǎng)度為(Ｃ)A、n Ｂ、n/2 C、（n+1)/2?D、(ｎ－1)／２＊將1０個(gè)元素散列到100０00０個(gè)單元的哈希表，則（C)產(chǎn)生沖突。A、一定會(huì)B、一定不會(huì)C、仍也許會(huì)Ｄ、以上都不對(duì)＊散列表的地址區(qū)間為０~16，散列函數(shù)H(k)=k%17，采用線(xiàn)性探測(cè)法解決地址沖突,將關(guān)鍵字２6、2５、72、3８、１、18、59依次存儲(chǔ)到散列表中。元素５9存放在散列表中的地址為(Ａ)A、8?Ｂ、9 C、1０?Ｄ、１１設(shè)有序表的關(guān)鍵字序列為｛１,3,９,1２,32,41,45,62,7５，77,8２,9５,100｝，當(dāng)采用二分查找法查找值為82的節(jié)點(diǎn)時(shí)，經(jīng)（C)次比較后查找成功。A、1 B、2 C、3?D、４設(shè)有1０0個(gè)元素，用折半查找法進(jìn)行查找時(shí),最大、最小比較次數(shù)分別時(shí)（Ａ)A、7,1?Ｂ、6,1 Ｃ、５,１ D、8，1第九章排序?qū)個(gè)不同的記錄按排序碼值從小到大順序重新排列,用冒泡(起泡)排序方法,初始序列在(Ａ)情況下，與排序碼值總比較次數(shù)最少。A.按排序碼值從小到大排列B．按排序碼值從大到小排列Ｃ．隨機(jī)排列(完全無(wú)序)D.基本按排序碼值升序排列對(duì)n個(gè)不同的記錄按排序碼值從小到大順序重新排列,用冒泡(起泡)排序方法，在（B）情況下,與排序碼值總比較次數(shù)最多。A．按排序碼值從小到大排列Ｂ．按排序碼值從大到小排列C．隨機(jī)排列(完全無(wú)序)D．基本按排序碼值升序排列對(duì)n個(gè)不同的記錄按排序碼值從小到大順序重新排列,用直接插入排序方法,初始序列在(A)情況下,與排序碼值總比較次數(shù)最少。A.按排序碼值從小到大排列Ｂ.按排序碼值從大到小排列Ｃ.隨機(jī)排列(完全無(wú)序)D.基本按排序碼值升序排列對(duì)ｎ個(gè)不同的記錄按排序碼值從小到大順序重新排列，用直接插入排序方法，初始序列在(B)情況下,與排序碼值總比較次數(shù)最多。A．按排序碼值從小到大排列B．按排序碼值從大到小排列C.隨機(jī)排列(完全無(wú)序）D.基本按排序碼值升序排列對(duì)n個(gè)不同的記錄按排序碼值從小到大順序重新排列,用快速排序方法在(C)情況下,與排序碼值總比較次數(shù)最少。A．按排序碼值從小到大排列Ｂ．按排序碼值從大到小排列Ｃ.隨機(jī)排列(完全無(wú)序)D．基本按排序碼值升序排列對(duì)n個(gè)不同的記錄按排序碼值從小到大順序重新排列,用快速排序方法，在（Ａ)情況下與排序碼值總比較次數(shù)最多。A.按排序碼值從小到大排列B.按排序碼值從大到小排列Ｃ.隨機(jī)排列（完全無(wú)序)Ｄ.基本按排序碼值升序排列用冒泡排序方法對(duì)n個(gè)記錄按排序碼值從小到大排序時(shí),當(dāng)初始序列是按排序碼值從大到小排列時(shí)，與碼值總比較次數(shù)是（Ｄ）。Ａ.n-1B.nC.n+1D.n(ｎ-1)／2下列排序方法中,與排序碼值總比較次數(shù)與待排序記錄的初始序列排列狀態(tài)無(wú)關(guān)的是(Ｄ）。A.直接插入排序B.冒泡排序Ｃ.快速排序D．直接選擇排序?qū)?個(gè)不同的整數(shù)進(jìn)行排序，至少需要比較（A)次。A．５B.６Ｃ.15D.2１將6個(gè)不同的整數(shù)進(jìn)行排序，至多需要比較（C)次。A.5B．6C.15D.21*若需要時(shí)間復(fù)雜度在O(nloｇ2n)內(nèi),對(duì)整數(shù)數(shù)組進(jìn)行排序，且規(guī)定排序方法是穩(wěn)定的,則可選擇的排序方法是（B）。Ａ.快速排序B．歸并排序C．堆排序D.直接插入排序當(dāng)待排序的整數(shù)是有序序列時(shí)，采用(B)方法比較好,其時(shí)間復(fù)雜度為O（n)。A.快速排序B.冒泡排序Ｃ.歸并排序D．直接選擇排序當(dāng)待排序的整數(shù)是有序序列時(shí)，采用(A）方法比較差,達(dá)成最壞情況下時(shí)間復(fù)雜度為O(n２)。A.快速排序Ｂ.冒泡排序C.歸并排序D.直接選擇排序當(dāng)待排序的整數(shù)是有序序列時(shí)，無(wú)論待排序序列排列是否有序,采用(D）方法的時(shí)間復(fù)雜度都是O(n2)。A．快速排序B.冒泡排序C．歸并排序D.直接選擇排序*堆是一種(B)排序。Ａ.插入B．選擇C.互換D.歸并*若一組記錄的排序碼值序列為{40,80,50,30，60，70}，運(yùn)用堆排序方法進(jìn)行排序，初建的大頂堆是(Ｄ）。A.80，４０,50,3０，60，70 B．8０，７０，6０,50，40,30C.8０,7０，５0,40,30,60?D．80,60,70，30，40，５０若一組記錄的排序碼值序列為{50，80，30，４0,70，6０}運(yùn)用快速排序方法,以第一個(gè)記錄為基準(zhǔn),得到一趟快速排序的結(jié)果為(Ｂ）。A.3０，4０，50，60,７0，80 Ｂ.40,30，50，８0,70,60Ｃ.50，30，40，70,６0,80 D．40,５0，３0,7０,60，8０*下列幾種排序方法中規(guī)定輔助空間最大的是（C）。A．堆排序B.直接選擇排序C．歸并排序D.快速排序已知Ａ［m］中每個(gè)數(shù)組元素距其最終位置不遠(yuǎn)，采用下列(A)排序方法最節(jié)省時(shí)間。A．直接插入B．堆C．快速D.直接選擇*設(shè)有1000０個(gè)互不相等的無(wú)序整數(shù),若僅規(guī)定找出其中前10個(gè)最大整數(shù)，最佳采用(B）排序方法。A．歸并B．堆C．快速D．直接選擇*在下列排序方法中不需要對(duì)排序碼值進(jìn)行比較就能進(jìn)行排序的是（Ａ)。A:基數(shù)排序B.快速排序C．直接插入排序D.堆排序*給定排序碼值序列為{F，B，Ｊ,C，Ｅ,A，I，Ｄ，C，H}，對(duì)其按字母的字典序列的順序進(jìn)行排列，希爾(Shell)排序的第一趟(ｄ１＝5）結(jié)果應(yīng)為(D）。Ａ．{B，Ｆ,C,J，A,Ｅ，Ｄ，I,C，H}B．{C,B,Ｄ，A，E，F(xiàn),I,C，J，H}C．{Ｂ,F，C，E，A,Ｉ，D，C，H，J}D．{A,B,Ｄ，C,Ｅ，Ｆ，Ｉ,J，C，Ｈ}給定排序碼值序列為｛F,B，J，Ｃ,E,A,Ｉ，D,C，Ｈ}，對(duì)其按字母的字典序列的順序進(jìn)行排列,冒泡排序(大數(shù)下沉)的第一趟排序結(jié)果應(yīng)為（C)。Ａ．{B,F,Ｃ,J，A,E,D，I,C,H}B．{C,B，D，A,E,F,Ｉ,Ｃ,Ｊ,H}C.{B，F(xiàn)，C，E，A,I，D,C，H,J}D．{Ａ，B,D,Ｃ，Ｅ,Ｆ,I，J,C,Ｈ}給定排序碼值序列為｛F,Ｂ，J，Ｃ,E，A,I,Ｄ,C，H｝,對(duì)其按字母的字典序列的順序進(jìn)行排列，快速排序的第一趟排序結(jié)果為(B)。A.{B，F(xiàn)，C，J，A,E,Ｄ,I,C，H}Ｂ.｛C，Ｂ，Ｄ,Ａ，E,F,I,Ｃ,J，H}Ｃ．{B,Ｆ，C,E，A，Ｉ，Ｄ,C，H,J｝D.{A,Ｂ，D，C，E,F,I，J,C,H}＊給定排序碼值序列為{F，B，Ｊ，C，Ｅ,Ａ,I，D，Ｃ,Ｈ},對(duì)其按字母的字典序列的順序進(jìn)行排列,二路歸并排序的第一趟排序結(jié)果是(Ａ)。A.{Ｂ，F(xiàn),Ｃ,J,A,E,D，I,Ｃ，H｝Ｂ.{C，B,Ｄ,A，E,F，I，C，J,H}C.{B，Ｆ,Ｃ，E,Ａ，I，Ｄ，C，Ｈ，J}D．｛A,B，D,C，E，F(xiàn),I，Ｊ，Ｃ,H}簡(jiǎn)答題第一章緒論請(qǐng)分別給出數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)的含義，并說(shuō)明四者的關(guān)系。數(shù)據(jù)(Dａt(yī)a）:是對(duì)信息的一種符號(hào)表達(dá)。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序解決的符號(hào)的總稱(chēng)。(一個(gè)得分點(diǎn))數(shù)據(jù)元素（Ｄａt(yī)aElｅmeｎt）:是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和解決,相稱(chēng)于表中的一條記錄。(一個(gè)得分點(diǎn)）數(shù)據(jù)項(xiàng):相稱(chēng)于記錄的“域”,是數(shù)據(jù)的不可分割的最小單位,如學(xué)號(hào)（一個(gè)得分點(diǎn)）數(shù)據(jù)對(duì)象:性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集.例如:同一個(gè)班的所有學(xué)生記錄集合。(一個(gè)得分點(diǎn))?關(guān)系：包含關(guān)系:數(shù)據(jù)泛指所有。數(shù)據(jù)對(duì)象是數(shù)據(jù)的一個(gè)子集,由數(shù)據(jù)元素組成，數(shù)據(jù)元素是由數(shù)據(jù)項(xiàng)組成。（一個(gè)得分點(diǎn))評(píng)分標(biāo)準(zhǔn)，總共５個(gè)得分點(diǎn)，每段話(huà)一個(gè)得分。請(qǐng)給出數(shù)據(jù)的邏輯結(jié)構(gòu)的含義,并舉例說(shuō)明數(shù)據(jù)的邏輯結(jié)構(gòu)通常有哪些。數(shù)據(jù)的邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。即用自然語(yǔ)言描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的,邏輯結(jié)構(gòu)有四種。(一個(gè)得分點(diǎn)）集合結(jié)構(gòu)：僅同屬一個(gè)集合(結(jié)構(gòu)名字0．5個(gè)得分點(diǎn)、舉例0.5得分點(diǎn))線(xiàn)性結(jié)構(gòu):一對(duì)一(1:１)（結(jié)構(gòu)名字０.５個(gè)得分點(diǎn)、舉例0．5得分點(diǎn))樹(shù)結(jié)構(gòu)：一對(duì)多(１：n)（結(jié)構(gòu)名字0．５個(gè)得分點(diǎn)、舉例0.５得分點(diǎn)）圖結(jié)構(gòu):多對(duì)多(ｍ:ｎ）（結(jié)構(gòu)名字0.5個(gè)得分點(diǎn)、舉例０.５得分點(diǎn)）評(píng)分標(biāo)準(zhǔn):每段話(huà)一個(gè)得分點(diǎn),總共５個(gè)得分點(diǎn)。什么是數(shù)據(jù)的物理結(jié)構(gòu)？有哪些物理結(jié)構(gòu)？數(shù)據(jù)的物理結(jié)構(gòu)與邏輯結(jié)構(gòu)有什么區(qū)別與聯(lián)系？數(shù)據(jù)的物理結(jié)構(gòu):物理結(jié)構(gòu)亦稱(chēng)存儲(chǔ)結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表達(dá)(或映像)。它依賴(lài)于計(jì)算機(jī)。(一個(gè)得分點(diǎn))存儲(chǔ)結(jié)構(gòu)可分為4大類(lèi):順序、鏈?zhǔn)?、索引、散列。（?個(gè)得分點(diǎn),一個(gè)0.5得分點(diǎn)）區(qū)別:數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶(hù)視圖,是面向問(wèn)題的,數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)屬于具體實(shí)現(xiàn)的視圖，是面向計(jì)算機(jī)的。（一個(gè)得分點(diǎn)）聯(lián)系：一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)，而采用不同的存儲(chǔ)結(jié)構(gòu)其解決的效率往往不同。(一個(gè)得分點(diǎn)）評(píng)分標(biāo)準(zhǔn)：共5個(gè)得分點(diǎn)，按照每段話(huà)各自標(biāo)注的得分點(diǎn)進(jìn)行評(píng)分。求兩個(gè)正整數(shù)m,n中的最大數(shù)ＭAX的算法(1)若m>n則max=m

（2)若m<=ｎ則max=ｎ請(qǐng)根據(jù)上述算法解釋一下算法的組成要素有哪些,分別是什么。算法由操作、控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)3要素組成操作包含:算術(shù)運(yùn)算、關(guān)系比較、邏輯運(yùn)算、數(shù)據(jù)傳送（輸入、輸出、賦值)(一個(gè)得分點(diǎn)）例子中有關(guān)系比較和賦值計(jì)算的操作。(一個(gè)得分點(diǎn)）控制結(jié)構(gòu)包含：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)（一個(gè)得分點(diǎn)）例子中有選擇結(jié)構(gòu)（一個(gè)得分點(diǎn)）數(shù)據(jù)結(jié)構(gòu)：算法操作的對(duì)象是數(shù)據(jù)，數(shù)據(jù)間的邏輯關(guān)系、數(shù)據(jù)的存儲(chǔ)方式及解決方式就是數(shù)據(jù)結(jié)構(gòu)。(一個(gè)得分點(diǎn)）本例是數(shù)值問(wèn)題，涉及到兩個(gè)正整數(shù)，因此使用基本的整數(shù)類(lèi)型就可以解決問(wèn)題。（一個(gè)得分點(diǎn)）評(píng)分標(biāo)準(zhǔn):本題共6個(gè)得分點(diǎn)，每段話(huà)一個(gè)得分點(diǎn)。簡(jiǎn)述算法的基本性質(zhì)1)輸入：0個(gè)或多個(gè)輸入2)輸出:１個(gè)或多個(gè)輸出3)有窮性:算法必須在有限步內(nèi)結(jié)束4）擬定性：組成算法的操作必須清楚無(wú)二義性5)可行性：組成算法的操作必須可以在計(jì)算機(jī)上實(shí)現(xiàn)評(píng)分標(biāo)準(zhǔn)，本題共５個(gè)得分點(diǎn),每個(gè)要點(diǎn)一分。簡(jiǎn)述算法的設(shè)計(jì)規(guī)定１、對(duì)的性（cｏｒreｃtnｅss）2、可讀性(reａdaｂilｉtｙ）3、健壯性(ｒobusｔnｅss)4、通用性（geneｒaliｔy）5、效率與存儲(chǔ)的規(guī)定（執(zhí)行算法所花費(fèi)的存儲(chǔ)空間、執(zhí)行算法所花費(fèi)的時(shí)間）評(píng)分標(biāo)準(zhǔn),本題共5個(gè)得分點(diǎn)，每個(gè)要點(diǎn)一分。評(píng)價(jià)算法好壞的3條重要標(biāo)準(zhǔn)1）算法實(shí)現(xiàn)所花費(fèi)的時(shí)間。2）算法實(shí)現(xiàn)所花費(fèi)的存儲(chǔ)空間，其中重要考慮輔助存儲(chǔ)空間。３)算法應(yīng)易于理解、易于編碼、易于調(diào)試等。評(píng)分標(biāo)準(zhǔn)，本題共３個(gè)得分點(diǎn),每個(gè)要點(diǎn)一分。請(qǐng)簡(jiǎn)述數(shù)據(jù)結(jié)構(gòu)所研究的三種基本結(jié)構(gòu),以及數(shù)據(jù)元素間的關(guān)系。線(xiàn)性結(jié)構(gòu)：數(shù)據(jù)元素之間一對(duì)一的關(guān)系。(２分)樹(shù)形結(jié)構(gòu):數(shù)據(jù)元素之間一對(duì)多的關(guān)系。（１．5分)圖形結(jié)構(gòu):數(shù)據(jù)元素之間多對(duì)多的關(guān)系。(1.5分)請(qǐng)問(wèn)算法的分析和評(píng)價(jià)的兩個(gè)標(biāo)準(zhǔn),以及各自作用。時(shí)間復(fù)雜度：評(píng)估算法運(yùn)營(yíng)所需時(shí)間。(１．5+1分)空間復(fù)雜度：評(píng)估算法運(yùn)營(yíng)時(shí)所需最大存儲(chǔ)空間。(１.5+1分)請(qǐng)說(shuō)出三種邏輯數(shù)據(jù)結(jié)構(gòu),以及他們的特點(diǎn)。(5分）（1）線(xiàn)性結(jié)構(gòu):數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和一個(gè)后繼數(shù)據(jù)元素。(２分）（２)樹(shù)結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素，可有零個(gè)或若干個(gè)后繼數(shù)據(jù)元素。(1.５分)（3）圖結(jié)構(gòu):每個(gè)數(shù)據(jù)元素可有零個(gè)或若干個(gè)前驅(qū)數(shù)據(jù)元素,零個(gè)或若干個(gè)后繼數(shù)據(jù)元素。(1.5分）評(píng)價(jià)算法的重要標(biāo)準(zhǔn)是什么?（１）算法實(shí)現(xiàn)所花費(fèi)的時(shí)間(２分）（2）算法實(shí)現(xiàn)所花費(fèi)的存儲(chǔ)空間,其中重要考慮輔助存儲(chǔ)空間。(2分）(3)算法應(yīng)易于理解、易于編碼、易于調(diào)試。(1分)請(qǐng)說(shuō)出三種邏輯數(shù)據(jù)結(jié)構(gòu)，并分別畫(huà)圖表達(dá)它們。(ａ,2分，ｂ，c各１．５分)算法的基本性質(zhì)有哪些?并簡(jiǎn)述每個(gè)特性。(5分）(1)有窮性——..．.．（１分)(２）擬定性——.．...(1分)(3）可行性——.....（1分）（4)輸入性——..．..（1分）（5)輸出性——.....(1分)通常從那幾個(gè)方面來(lái)評(píng)價(jià)算法的質(zhì)量？(5分)通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：對(duì)的性、可讀性、健壯性和高效性。(少一個(gè)扣1分）請(qǐng)描述線(xiàn)性數(shù)據(jù)結(jié)構(gòu)的兩種存儲(chǔ)方式,并說(shuō)出其各有什么特點(diǎn)。順序存儲(chǔ):連續(xù)存儲(chǔ)，易于定位,不易于插入和刪除。(１+1．5分）鏈?zhǔn)酱鎯?chǔ):非連續(xù)存儲(chǔ)，不易于定位,易于插入和刪除。（1+1．５分）請(qǐng)問(wèn)算法的分析和評(píng)價(jià)的兩種方法,它們關(guān)注點(diǎn)各有什么不同？（簡(jiǎn)樸）空間效率：關(guān)注算法對(duì)內(nèi)存的占用度。（１+1.5分）時(shí)間效率：關(guān)注算法的運(yùn)算速度。（1+1.5分)第二章線(xiàn)性表請(qǐng)問(wèn)假如要插入一個(gè)數(shù)據(jù)到一個(gè)線(xiàn)性表中,順序表和鏈表哪個(gè)的效率高？為什么？鏈表的效率高(2分）,由于順序表要移動(dòng)插入位置后的每一個(gè)元素的位置給新數(shù)據(jù)騰位置（1.5分）。鏈表只需要將前一個(gè)數(shù)據(jù)的指針指向新數(shù)據(jù)并將新數(shù)據(jù)的指針指向后一個(gè)數(shù)據(jù)即可（1.5分）。線(xiàn)性表有哪些特點(diǎn)?1）除第一個(gè)和最后一個(gè)數(shù)據(jù)元素外,每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和一個(gè)后繼數(shù)據(jù)元素;（２分)2)第一個(gè)數(shù)據(jù)元素沒(méi)有前驅(qū)數(shù)據(jù)元素;(1.5分)3)最后一個(gè)數(shù)據(jù)元素沒(méi)有后繼數(shù)據(jù)元素。（1.５分)順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺陷有哪些?(中檔）順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)：(２.5分）存儲(chǔ)空間連續(xù)邏輯相鄰,物理相鄰可隨機(jī)存取任一元素缺陷:（2．5分）插入、刪除操作需要移動(dòng)大量的元素預(yù)先分派空間需按最大空間分派,運(yùn)用不充足表容量難以擴(kuò)充單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺陷有哪些?（中檔)單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn):(2.5分）不需預(yù)先分派空間，空間運(yùn)用充足插入、刪除操作簡(jiǎn)樸,無(wú)需移動(dòng)大量的元素表容量易于擴(kuò)充缺陷:(２.5分)每個(gè)數(shù)據(jù)元素，除存儲(chǔ)自身信息外，還需空間存儲(chǔ)其直接后繼的信息邏輯相鄰，物理不一定相鄰不可隨機(jī)存取任一元素,只能從鏈表頭依次查找．有順序表A＝(a0,a１,a2,..．ａ8，a９，…a19)，要在a8,a9之間插入一個(gè)元素a20,請(qǐng)描述其操作(思想）環(huán)節(jié)。（中檔)插入思想或環(huán)節(jié):根據(jù)順序表的存儲(chǔ)特點(diǎn),要在表中某位置10插入一新數(shù)據(jù)元素,則要進(jìn)行如下兩步操作:(1）、從位置10到表尾位置的所有數(shù)據(jù)元素均要從后至前依次向后移一個(gè)存儲(chǔ)位置，為新插入結(jié)點(diǎn)騰出第１０個(gè)位置。(2分）（2）、將新結(jié)點(diǎn)插入到空余位置10處。２分)(3）表長(zhǎng)度加1.(1分）有順序表A＝(ａ0,ａ1，a2,.．.a8,a9,…a1９），要?jiǎng)h除一個(gè)元素a9,請(qǐng)描述其操作(思想)環(huán)節(jié)。(中檔）（1)然后將從位置1１到表尾的所有數(shù)據(jù)元素依次向前移一個(gè)存儲(chǔ)位置。（３分)(2)表長(zhǎng)度減1.(２分)請(qǐng)描述在順序表中第i個(gè)位置插入新的數(shù)據(jù)x操作過(guò)程。根據(jù)順序表的存儲(chǔ)特點(diǎn),要在表中某位置i插入一新數(shù)據(jù)元素，則要進(jìn)行如下兩步操作:(1)從位置i到表尾位置的所有數(shù)據(jù)元素均要從后至前依次向后移一個(gè)存儲(chǔ)位置,為新插入結(jié)點(diǎn)騰出第i個(gè)位置;(2分)(2）將新數(shù)據(jù)ｘ插入到空余位置ｉ處。(2分)（3)表長(zhǎng)度加１.(１分）請(qǐng)描述在順序表中刪除第i個(gè)位置的數(shù)據(jù)的過(guò)程。(1)然后將從位置i到表尾的所有數(shù)據(jù)元素依次向前移一個(gè)存儲(chǔ)位置。(3分)(2）表長(zhǎng)度減1.(2分)請(qǐng)描述在一個(gè)單鏈表中插入一個(gè)數(shù)據(jù)ｑ的插入過(guò)程。找到將插入數(shù)據(jù)位置的前一個(gè)結(jié)點(diǎn)p;（１分)q的next值等于ｐ的nｅxt值;(2分）(３）ｐ的nexｔ值等于q；（2分)請(qǐng)描述從一個(gè)單鏈表中刪除一個(gè)數(shù)據(jù)的刪除過(guò)程。(１）找到將被刪除數(shù)據(jù)的前一個(gè)結(jié)點(diǎn)p；(2分)(2)p的next指針指向被刪除數(shù)據(jù)的后一個(gè)結(jié)點(diǎn)；(2分）(３）將被刪除數(shù)據(jù)本來(lái)的ｎｅxt指針指向nｕll;(1分)第三章棧和隊(duì)列請(qǐng)簡(jiǎn)述線(xiàn)性表、棧和隊(duì)列三者之間的聯(lián)系。（簡(jiǎn)樸)（１)線(xiàn)性表、棧和隊(duì)列都屬于線(xiàn)性結(jié)構(gòu)。（2分）（2)棧和隊(duì)列都是特殊的線(xiàn)性表，并且都有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)方式。(1分）(3)棧是一種先進(jìn)后出的線(xiàn)性表,隊(duì)列是一種先進(jìn)先出的線(xiàn)性表(2分）在計(jì)算機(jī)進(jìn)行運(yùn)算時(shí),需要把十進(jìn)制轉(zhuǎn)換為二進(jìn)制。請(qǐng)問(wèn)答：這種數(shù)制轉(zhuǎn)換可以借助于哪種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)、及因素。答:棧。（2分）因素:(3分）在進(jìn)行數(shù)值轉(zhuǎn)換時(shí)，其實(shí)質(zhì)是求余的過(guò)程，并且余數(shù)的倒序序列正是所求結(jié)果。棧是一種先進(jìn)后出的線(xiàn)性結(jié)構(gòu)，可以滿(mǎn)足這種操作。有一字符序列ａｂcｄe依次按照某一線(xiàn)性結(jié)構(gòu)存儲(chǔ),請(qǐng)回答以下問(wèn)題: (1）、假如該線(xiàn)性結(jié)構(gòu)是隊(duì)列，那么,寫(xiě)出出隊(duì)序列。 （2）、假如該線(xiàn)性結(jié)構(gòu)是棧,那么,輸出序列也許是d,c,e，a,b嗎,為什么? (3)、假如該線(xiàn)性結(jié)構(gòu)是棧,且輸出序列是abcdｅ。請(qǐng)寫(xiě)出操作過(guò)程。(push(x):表達(dá)把x壓入棧內(nèi);pop(x):表達(dá)把x彈出棧）?答:(1）、aｂｃde（１分）（2)、不也許，由于:d是第一出棧字符，說(shuō)明a,b已別壓入棧內(nèi);并且壓入棧的順序?yàn)閍bｃｄe;由以上得出:aｂ出棧的順序只能是ｂ、a，而不是ａ、b。所以,出棧序列d,c,e，a，b是不也許的。（2分)(３）、（2分)push(ａ),poｐ(a)puｓｈ(b）,pｏｐ(ｂ)pｕsh(ｃ)，pop(c)pusｈ（d),ｐop（ｄ)push（e)，pop(e)簡(jiǎn)述棧和隊(duì)列的異同點(diǎn)。相同點(diǎn):棧和隊(duì)列都是只允許在表的端點(diǎn)處進(jìn)行插入、刪除操作的線(xiàn)性表。（2分)不同點(diǎn)：棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是后進(jìn)先出。（３分）若依次讀入數(shù)據(jù)元素序列1、2、3，進(jìn)棧的過(guò)程中允許出棧,試寫(xiě)出各種也許的出棧序列。答:123、１32、213、2３１、３21（各１分）假如入棧序列有AＢC組成,請(qǐng)問(wèn)輸出序列也許有哪些?(較難)輸出序列有5種:CＢA，BCA,BAC,ＡＣＢ，ABC（各1分)假如有abｃdｅ五個(gè)數(shù)據(jù)依次所有存入，假如采用隊(duì)列和棧來(lái)進(jìn)行存儲(chǔ)，依次取出分別將獲得什么內(nèi)容。(簡(jiǎn)樸)隊(duì)列：abｃde（２.５分)棧:ｅdcba(2.５分)設(shè)將整數(shù)1，2，３，4依次進(jìn)棧，能否得到１423出棧序列和1432?并說(shuō)明為什么不能得到或者如何得到。(中檔)不能得到14２3，但可以得到143２（2分)由于要得到4必須將所有數(shù)據(jù)入棧，這樣將只能依次獲取到１43２不能獲得１423。采用push、poｐ、pusｈ、push、push、pop、ｐoｐ、ｐoｐ可以獲得1４3２。（3分）循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判斷它的空和滿(mǎn)？(可不考)循環(huán)隊(duì)列的優(yōu)點(diǎn)是可以克服順序隊(duì)列的"假上溢＂現(xiàn)象,可以使存儲(chǔ)隊(duì)列的向量空間得到充足的運(yùn)用。(3分)采用犧牲一個(gè)元素空間的方法,循環(huán)隊(duì)列隊(duì)空的條件是froｎt=＝rear，循環(huán)隊(duì)列隊(duì)滿(mǎn)的條件是：（ｒear+1)%M=＝fronｔ。(2分）第四章串對(duì)于字符串S=’abｃde’,請(qǐng)問(wèn)：(簡(jiǎn)樸)(１）字符串Ｓ的長(zhǎng)度是多少？(2）字符串Ｓ的子串有幾個(gè),并列出所有子串?答:(1）、5（1分)（2)、1６，（1分)所有字串:’a’、’b’、’c’、’d’、’e’、’ａb’、’bc’、’ｃd’、’de’、’aｂc’、’bcd’、’cdｅ’、’abcd’、’bcｄｅ’、’ａbcde’、Φ。(３分)對(duì)于字符串S=’1234５’,請(qǐng)問(wèn)：(簡(jiǎn)樸）（１)字符串S的長(zhǎng)度是多少?（2）字符串S的子串有幾個(gè),并列出所有子串？答：（1)、５（1分）（2）、16,（１分）所有字串:’1’、’2’、’3’、’４’、’5’、’12’、’２3’、’34’、’4５’、’12３’、’234’、’34５’、’12３4’、’２3４5’、’123４５’、Φ。(3分)?請(qǐng)問(wèn)答：什么串的模式匹配?模式匹配算法有幾種?（簡(jiǎn)樸)答:串的模式匹配是指子串的定位運(yùn)算,即在主串中查找子串第一次出現(xiàn)的位置。模式匹配算法有兩種：簡(jiǎn)樸匹配算法(Ｂrute-Fｏｒｃｅ)、KMP算法。（該題共4個(gè)得分點(diǎn),答對(duì)串匹配定義或大意基本相同,得2分；答對(duì)兩種匹配算,得2分,答錯(cuò)或少答一個(gè)扣1分)第五章數(shù)組和廣義表在數(shù)據(jù)結(jié)構(gòu)中，數(shù)組是最基本的結(jié)構(gòu)，請(qǐng)完畢以下規(guī)定：（1)、定義一個(gè)能容納5個(gè)整型元素的數(shù)組ｉAry,且元素的值為1０、2０、30、40、５0。(2)、*畫(huà)出數(shù)組ｉAry的順序存儲(chǔ)結(jié)構(gòu)。（規(guī)定:整型長(zhǎng)度為兩個(gè)字節(jié)）(１）、iｎtiAry[5]={10、20、３0、40、50｝(2分)（2）、如下圖:（3分，根據(jù)情況,酌情扣分)簡(jiǎn)述數(shù)組的定義、特點(diǎn)和分類(lèi)。（簡(jiǎn)樸)定義:數(shù)組是n個(gè)相同數(shù)據(jù)類(lèi)型的數(shù)據(jù)元素a0，a1,a2，．..,an-1構(gòu)成的有限集合。(1個(gè)得分點(diǎn)）特點(diǎn)：１）數(shù)組中各元素具有統(tǒng)一的類(lèi)型;（1個(gè)得分點(diǎn)）2)數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。(１個(gè)得分點(diǎn)）3數(shù)組的基本操作比較簡(jiǎn)樸，除了結(jié)構(gòu)的初始化和銷(xiāo)毀之外,只有存取元素和修改元素值的操作。（1個(gè)得分點(diǎn))分類(lèi)：按維度可分為一維數(shù)組、二維數(shù)組、多維數(shù)組（1個(gè)得分點(diǎn)）已知一個(gè)二維數(shù)組A如下所示。（較難）(１）請(qǐng)按照行優(yōu)先、列優(yōu)先的方式進(jìn)行順序存儲(chǔ),給出順序存儲(chǔ)的序列（2個(gè)得分點(diǎn)）行優(yōu)先：a11a1２a13a２１ａ22a23列優(yōu)先：a11a21a12a22ａ１3a2３（2)若a1１在內(nèi)存中存儲(chǔ)的地址為α,每個(gè)元素的存儲(chǔ)空間大小為L(zhǎng),則按照行優(yōu)先的方式和列優(yōu)先的方式分別存儲(chǔ)，其中ａ22的地址loc(a22)分別為多少(2個(gè)得分點(diǎn))行優(yōu)先：loc(ａ22)=α+４L列優(yōu)先：loc(a22)＝α+3Ｌ(３)對(duì)于數(shù)組,除了順序存儲(chǔ)外,尚有沒(méi)有其他存儲(chǔ)方式?沒(méi)有填無(wú)，若有,請(qǐng)說(shuō)明。有，鏈?zhǔn)酱鎯?chǔ)，如下圖所示（１個(gè)得分點(diǎn))第六章樹(shù)和二叉樹(shù)有一樹(shù)，如下圖所示：(簡(jiǎn)樸)請(qǐng)回答以下問(wèn)題：（1）樹(shù)的葉子結(jié)點(diǎn)及其度。(2）非終端結(jié)點(diǎn)及其度。（3）樹(shù)的深度。答：（1）、葉子結(jié)點(diǎn)有：D、E、Ｆ、G,它們的度都為零。（2分)(2）、非終端結(jié)點(diǎn)有:A度為3，Ｂ度為2，C度為1。（2分)(3)、樹(shù)的深度為3。(1分）請(qǐng)回答：樹(shù)與二叉樹(shù)有什么區(qū)別？(中檔）答:區(qū)別有兩點(diǎn):(1)二叉樹(shù)的一個(gè)結(jié)點(diǎn)至多有兩個(gè)子樹(shù),樹(shù)則不然。(2．５分)(2）二叉樹(shù)一個(gè)結(jié)點(diǎn)的子樹(shù)有左右之分,而樹(shù)的子樹(shù)沒(méi)有順序。（2.5分）有一棵具有n個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)。請(qǐng)問(wèn):該滿(mǎn)二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)目是多少，并寫(xiě)出分析推理過(guò)程。(中檔)答:(ｎ+1)／2。（2分)分析過(guò)程:滿(mǎn)二叉樹(shù)中只有度為2和度為0的結(jié)點(diǎn),故設(shè)葉子結(jié)點(diǎn)數(shù)目為：n0,度為２結(jié)點(diǎn)數(shù)目為:n2。又由于n0＝n2＋1,ｎ＝n2+n0,所以可得出:n０=(ｎ+1)/２。(3分）有一棵二叉樹(shù)，如下圖所示：(簡(jiǎn)樸)請(qǐng)問(wèn)答以下問(wèn)題：(１）、用先序遍歷法遍歷該二叉樹(shù)，則遍歷結(jié)果是什么?（2)、用中序遍歷法遍歷該二叉樹(shù)，則遍歷結(jié)果是什么?(3)、用后序遍歷法遍歷該二叉樹(shù)，則遍歷結(jié)果是什么?答：(1）、ＡBDCEＦ（2）、DBAECF（3）、ＤBEFＣＡ(錯(cuò)一個(gè)扣1.５分)請(qǐng)問(wèn)如下二叉樹(shù)，假如采用前序\中序\后序遍歷結(jié)果是什么?(中檔）前序：AＢDECF;中序：ＤBEAＦC;后序:DＥBFCA；（錯(cuò)一個(gè)扣1.５分)有如下一顆樹(shù)其前序＼中序\后序遍歷結(jié)果是什么？(中檔)其前序遍歷結(jié)果是：ABDＧCEF其中序遍歷結(jié)果是:DGBAEＣＦ其后序遍歷結(jié)果是:ＧDBEＦCA(錯(cuò)一個(gè)扣1.5分)假定用于通信的電文由8個(gè)字符Ａ、B、C、D、E、Ｆ、G、Ｈ組成，各字母在電文中出現(xiàn)概率為5%、２5％、４％、7％、9％、1２％、３0％、8％。現(xiàn)在把字符出現(xiàn)概率擴(kuò)大１00倍后,作為這8個(gè)字母相應(yīng)的權(quán)值（5，25，４,7,9，12,3０,8）。以這些權(quán)值構(gòu)成的霍夫曼樹(shù),如下圖所示:請(qǐng)問(wèn)答以下問(wèn)題：（中檔）（１)、參考霍夫曼樹(shù),給字符Ａ、B、C、Ｄ、E、F、Ｇ、Ｈ進(jìn)行編碼。(寫(xiě)出這８?jìng)€(gè)字符的霍夫曼編碼）(2)、假如發(fā)送的電文信息為“HEＣＤB”，那么，發(fā)送的數(shù)據(jù)是什么。(或者說(shuō)發(fā)送的編碼序列是什么）答:(１)、Ａ：00１1,Ｂ:0１,C:0０10, Ｄ:101０,Ｅ:0０0，?F:１00,G:1１,H：101１（3分）(2）、１０110０00０１0101001(2分）請(qǐng)簡(jiǎn)述滿(mǎn)二叉樹(shù)、完全二叉樹(shù)的聯(lián)系。答:（1）、它們都是特殊的二叉樹(shù)，遵循著二叉樹(shù)的性質(zhì)。（2.5分)（２）、滿(mǎn)二叉樹(shù)是指每一層HYPERLＩNK""\ｔ"_ｂlanｋ"結(jié)點(diǎn)數(shù)都達(dá)成了最大值,所有ＨYPERLINK""＼t"＿blank＂葉子結(jié)點(diǎn)均在最大層上；而完全二叉樹(shù)是遵循著滿(mǎn)二叉樹(shù)結(jié)點(diǎn)編號(hào)序列規(guī)律的一種樹(shù)。(2.5分)如下是一顆樹(shù).請(qǐng)問(wèn)度為2的節(jié)點(diǎn)有哪些?度為3的節(jié)點(diǎn)有哪些?這顆樹(shù)的度為多少？樹(shù)的深度是幾?(中檔）答:度為2的節(jié)點(diǎn)有B，E;（1．5分）度為３的節(jié)點(diǎn)有A,D;（1.5分）這顆樹(shù)的度為4，（１分）樹(shù)的深度是４.(１分)請(qǐng)畫(huà)出深度為4的滿(mǎn)二叉樹(shù)(較難）請(qǐng)畫(huà)出深度為4的完全二叉樹(shù)（較難）給定一組權(quán)值｛6，2，3,９，６｝根據(jù)哈夫曼算法構(gòu)造哈夫曼樹(shù)．（難）將６、2、3、9、6當(dāng)作是有5棵樹(shù)的森林（每棵樹(shù)僅有一個(gè)結(jié)點(diǎn)）;２)在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的2,3樹(shù)合并,作為一棵新樹(shù)的左、右子樹(shù),且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和5;從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林;?３)在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的5，6樹(shù)合并,作為一棵新樹(shù)的左、右子樹(shù),且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和11；從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林;4）在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的６,9樹(shù)合并,作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和15;從森林中刪除選取的兩棵樹(shù),并將新樹(shù)加入森林;5)在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的１１,15樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù),且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和26；從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林；第七章圖什么叫圖Ｇ的生成樹(shù)答:連通圖G的一個(gè)子圖假如是一棵包含Ｇ的所有頂點(diǎn)的樹(shù),則該子圖稱(chēng)為Ｇ的生成樹(shù)。寫(xiě)出下面圖的鄰接矩陣答案用鄰接表表達(dá)下圖的存儲(chǔ)結(jié)構(gòu)答案已知如下的有向圖=1\＊GB３①每個(gè)頂點(diǎn)的入度和出度；＝2\＊GB3②鄰接矩陣;＝３\*ＧB3③鄰接表；答案第八章查找什么是查找、靜態(tài)查找以及動(dòng)態(tài)查找?并說(shuō)出關(guān)于靜態(tài)查找的幾種算法（簡(jiǎn)樸)查找：給定一個(gè)值K,在具有n個(gè)記錄的文獻(xiàn)中進(jìn)行搜索，尋找一個(gè)關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。(１個(gè)得分點(diǎn)）靜態(tài)查找：只查找，不改變集合內(nèi)的數(shù)據(jù)元素。(0.5個(gè)得分點(diǎn)）動(dòng)態(tài)查找:既查找,又改變（增減）集合內(nèi)的數(shù)據(jù)元素(0．5個(gè)得分點(diǎn))靜態(tài)查找的算法有:順序、二分、分塊查找（３個(gè)得分點(diǎn))請(qǐng)回答出四種查找方法，以及對(duì)查找方法評(píng)價(jià)的標(biāo)準(zhǔn)是什么?(簡(jiǎn)樸）答:順序查找、二分查找(折半查找法)、索引查找、哈希表查找。(４分）查找方法評(píng)價(jià)的標(biāo)準(zhǔn)是:平均查找長(zhǎng)度（１分)請(qǐng)回答出二分查找與順序查找各自的優(yōu)缺陷?（簡(jiǎn)樸)1）順序查找優(yōu)點(diǎn)：算法簡(jiǎn)樸，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均合用。(１個(gè)得分點(diǎn))缺陷：查找性能較低,平均查找長(zhǎng)度大（１個(gè)得分點(diǎn))2）二分查找1）優(yōu)點(diǎn)：查找效率高,平均查找長(zhǎng)度小。（1個(gè)得分點(diǎn))2)缺陷：ａ．查找表需按關(guān)鍵字排序（有序表)。(1個(gè)得分點(diǎn)）b.二分查找只合用順序存儲(chǔ)結(jié)構(gòu)。為保持表的有序性，在順序結(jié)構(gòu)里插入和刪除都必須移動(dòng)大量的結(jié)點(diǎn)。(1個(gè)得分點(diǎn)）第九章排序有一組數(shù)據(jù)｛６４,５,7,98，6,24},請(qǐng)列出直接選擇排序(升序)的過(guò)程.（難）初始序列 64 5?7?9８ 6?24第１次排序?[5]?64?７ 98 6?24第2次排序?[5 6]?7 98?６4 ２4第3次排序 [５?６?7]?98 6４?24第4次排序 [5?6 7 ２4]?６4?98第５次排序 ［５?6 ７?24 64］ 98最終結(jié)果 ［5 6 7 24 64?98］有一組數(shù)據(jù){64,5,7,98，6,2４},請(qǐng)列出冒泡排序(升序)的過(guò)程．(難)初始序列?６4?5?７?98 6?24第1次排序 5?7?64 6?２４ [98]第2次排序?5?7?6?24?[64 9８]第３次排序?５ 6?7 ［24 64 ９8］第4次排序?5 6?［7 2４?６4 ９８]第5次排序?5 [6?7 ２4?64 98］最終結(jié)果?[5 6 7 24 64 98]有一組數(shù)據(jù){6４,5,7,98，6,24}，請(qǐng)列出直接插入排序(升序)的過(guò)程.（難)初始序列?[6４］5?798６ 2４第1次排序?［５?64]7986?２4第2次排序 ［5７ 64]98６?24第３次排序 ［57 649８]6?24第4次排序?[5６７ 649８]?2４第5次排序?[567?24 649８]有關(guān)鍵字序列（16，1５，18，16,17，18,2０,13）,現(xiàn)采用直接插入排序?qū)﹃P(guān)鍵字按遞增序排列,請(qǐng)畫(huà)出具體過(guò)程(難)初始序列 [1６]，15，18，1６,17，１8，２0,１3第1次排序[１5，1６］，18,1６，17,18，20，13第2次排序 [1５,1６，１8]，1６，17，18，２０，13第3次排序 [15，16，1６，18],17,18,20,13第4次排序 [１5,1６，16，17,18]，１8,20，1３第5次排序?[15,１6，1６，17,18，１8],２0，1３第6次排序?［15，16,16,17,18,18，２0]，１3第７次排序?[1３,15，１6，１6，17,18,18，20]有關(guān)鍵字序列(1６,15,18,16,17,18，20,１3),現(xiàn)采用冒泡排序?qū)﹃P(guān)鍵字按遞增序排列,請(qǐng)畫(huà)出具體過(guò)程(難）初始序列 １6151816１7１82013第1次排序15161６17１8181３[20]第2次排序 151６1６１718１3[182０］第3次排序?１516161713［1８1８２0]第4次排序 １5,1６,16，13,[1７，18，18，2０]第5次排序 15，16，1３，［16,17，１8，18,２０]第６次排序 １5，1３，[16，16,17,１8，18,20］第7次排序?13，[15，16,１6，1７,１8，18，2０]有關(guān)鍵字序列(16,1５，18，16,１7,1８,２0,1３）,現(xiàn)采用直接選擇排序?qū)﹃P(guān)鍵字按遞增序排列，請(qǐng)畫(huà)出具體過(guò)程(難)初始序列 1６,15，１８,１６,17,18，２0,１3第1次排序[13]，1５,18,16,1７,18，20，１6第2次排序［1３，１5],18,16,1７，1８,20,1６第３次排序[13,15,16]，1８,17,18，２0,１6第4次排序[13，15，１6，16],17,１8，20,18第5次排序[13，15,1６,16，１7],18,20,18第6次排序[13，15，1６,16，１7，18]，20，18第７次排序[13，15,１6,１6，17，18,18],２０編程題第一章緒論第二章線(xiàn)性表已知某個(gè)班級(jí)的學(xué)生信息表如下表所示，請(qǐng)使用順序表結(jié)構(gòu)編程實(shí)現(xiàn)將學(xué)生信息(、楊三）插入到表中第一條的位置。學(xué)號(hào)（ＩD)姓名(Name）李華王麗具體規(guī)定：編寫(xiě)代碼定義順序表結(jié)構(gòu),完畢該信息表已有數(shù)據(jù)的初始化工作,最后完畢數(shù)據(jù)的插入。classSｔuｄent{//兩個(gè)得分點(diǎn)puｂliｃStriｎｇno; ／/學(xué)生學(xué)號(hào)puｂｌｉcSｔｒｉｎｇnaｍe; /／學(xué)生姓名?pｕblicStuｄeｎt(Sｔringno,Stringname){ ?this.no=nｏ;??this．name=name;?}}publicclａssＬineＬｉst｛ //LineList為線(xiàn)性表名?inｔlｅngth=3５; /／表長(zhǎng)度（1個(gè)得分點(diǎn)）Studentdata[]=newSｔudent[ｌｅngtｈ]；//順序表數(shù)組1個(gè)得分點(diǎn) ｉntcurlｅn=0;?//實(shí)際表長(zhǎng)（1個(gè)得分點(diǎn)) //插入方法?publicboolｅaninｓert(inti,Sｔudentsｔu）{??//插入位置對(duì)的與否判斷(１個(gè)得分點(diǎn))if（i<1||i>ｔhis．curlｅn+１||thｉs.ｃｕrlｅn>=tｈis．lｅｎgｔh){ ?returnfａlse;} //從第i個(gè)位置開(kāi)始順序表所有結(jié)點(diǎn)均后移一個(gè)位置(1個(gè)得分點(diǎn)) ｉｎtn=ｔｈiｓ.ｃurlｅn； ?fｏr(;n＞=i;n-－) dａt(yī)ａ[ｎ]=ｄata[n-１]；? ／／插入新結(jié)點(diǎn)stｕ（1個(gè)得分點(diǎn)）??datａ［n]＝ｓtu; thiｓ．curlen＋＋；(1個(gè)得分點(diǎn)） ?reｔurntrue;?}?pｕbｌicｓｔａt(yī)ｉcｖoidmain(Stｒing[］aｒgｓ){ /／初始化數(shù)據(jù)（2個(gè)得分點(diǎn)）? LineＬｉsｔlst=newLiｎeList(); Sｔuｄｅｎtstu1=newStudent(＂","李華"); ?Sｔudentstｕ２＝newStudeｎt（"",＂王麗"); lst.dａt(yī)a[0]=stu1;? lst．ｄatａ［1]＝sｔu2;? //進(jìn)行插入操作（1個(gè)得分點(diǎn)） ?Ｓtudeｎｔstu３=neｗＳtudent("＂,"楊三＂);??ｌｓt．ｉnｓert（1，stu3)； ｝}評(píng)分標(biāo)準(zhǔn):總共15個(gè)得分點(diǎn)，其中程序規(guī)范、語(yǔ)法(3個(gè)得分點(diǎn)，語(yǔ)法有問(wèn)題但不影響程序邏輯，按0.5得分點(diǎn)每一處扣分，扣完為止），程序邏輯1２個(gè)得分點(diǎn)(按照程序代碼各處標(biāo)注分?jǐn)?shù)進(jìn)行打分）已知某個(gè)圖書(shū)館的圖書(shū)信息表如下表所示,請(qǐng)使用順序表結(jié)構(gòu)編程實(shí)現(xiàn)將圖書(shū)信息（1０101、鹿鼎記)插入到表中第一條的位置。圖書(shū)號(hào)(ID)書(shū)名(Nａme)10102神雕俠侶10103鴛鴦刀具體規(guī)定：編寫(xiě)代碼定義順序表結(jié)構(gòu)，完畢該信息表已有數(shù)據(jù)的初始化工作，最后完畢數(shù)據(jù)的插入。clasｓBook｛//兩個(gè)得分點(diǎn)ｐｕblicSｔrｉngｎo； //圖書(shū)編號(hào)pｕｂlicSｔringname; //圖書(shū)名稱(chēng) ｐublicBook(Ｓtringno，Stｒｉngname){ ?thｉs．no=nｏ; ?thiｓ.naｍｅ=nａme; ｝}puｂｌiｃclassLineLｉst{ /／LineＬist為線(xiàn)性表名?ｉntｌengtｈ=35；?//表長(zhǎng)度（1個(gè)得分點(diǎn)）Boｏkｄaｔa[]＝nｅwＢｏok[lenｇｔh];/／順序表數(shù)組１個(gè)得分點(diǎn)?intcｕrleｎ=0;?//實(shí)際表長(zhǎng)(1個(gè)得分點(diǎn)) /／插入方法 publicbooleaninsｅｒt(ｉnｔi,Bookbｏok)｛ ?//插入位置對(duì)的與否判斷(１個(gè)得分點(diǎn)）iｆ(i<１||i>this.curlen+1｜｜ｔhis.curｌen＞＝tｈis.ｌeｎgth){ ? reｔｕｒnfalｓｅ;} ?//從第ｉ個(gè)位置開(kāi)始順序表所有結(jié)點(diǎn)均后移一個(gè)位置（1個(gè)得分點(diǎn)) intn=tｈis.curlen; for(;n>=i;n--)? data[n]＝daｔa[n－1］;??//插入新結(jié)點(diǎn)boｏk(1個(gè)得分點(diǎn))? data[n]=book;??ｔhｉs.cｕrleｎ＋+;（1個(gè)得分點(diǎn)）??returntruｅ; } publicstaｔicvoidｍaiｎ(Ｓtｒiｎg[]args）{ ?//初始化數(shù)據(jù)(2個(gè)得分點(diǎn)) ?LineLｉｓtｌsｔ＝newLineＬｉst(); Ｂookbｏok1=ｎewBｏoｋ("１010２","神雕俠侶"）;? Bookbooｋ2=ｎewBoｏｋ("1０１0３","鴛鴦刀");? lｓt．data[0］=bｏok1;??ｌｓt.data[1]＝book2; //進(jìn)行插入操作(1個(gè)得分點(diǎn)） Bookbook３=newBoｏｋ（＂10１01","鹿鼎記");??lｓｔ.inseｒｔ（１,bｏok3)；?}｝評(píng)分標(biāo)準(zhǔn):總共15個(gè)得分點(diǎn),其中程序規(guī)范、語(yǔ)法(３個(gè)得分點(diǎn)，語(yǔ)法有問(wèn)題但不影響程序邏輯,按0.5得分點(diǎn)每一處扣分，扣完為止)，程序邏輯12個(gè)得分點(diǎn)（按照程序代碼各處標(biāo)注分?jǐn)?shù)進(jìn)行打分)已知某個(gè)教務(wù)系統(tǒng)的課程信息表如下表所示，請(qǐng)使用順序表結(jié)構(gòu)編程實(shí)現(xiàn)將課程信息(10101、數(shù)據(jù)結(jié)構(gòu)）插入到表中第一條的位置。課程號(hào)（ＩD）課程名（Namｅ）10102軟件工程１0103ＵML具體規(guī)定：編寫(xiě)代碼定義順序表結(jié)構(gòu),完畢該信息表已有數(shù)據(jù)的初始化工作,最后完畢數(shù)據(jù)的插入。cｌasｓLession{//兩個(gè)得分點(diǎn)ｐuｂlｉcＳtriｎgｎo; //課程編號(hào)pubｌicSｔrinｇnａme;?//課程名稱(chēng)?pｕblｉcＬesｓion（Stｒingno，Striｎｇname){ this.no=ｎo;??tｈis．nａmｅ＝name; }｝publicｃlassLｉneList{?//LｉneLｉst為線(xiàn)性表名?intlength=３５; //表長(zhǎng)度(１個(gè)得分點(diǎn))Ｌessioｎdaｔa[］=ｎeｗＬessｉon[lengtｈ];/／順序表數(shù)組1個(gè)得分點(diǎn)?inｔｃuｒlen＝0;?//實(shí)際表長(zhǎng)(1個(gè)得分點(diǎn)) ／/插入方法?pubｌiｃbｏｏleanｉｎsert(inti,Lｅssioｎlｅsｓioｎ){ //插入位置對(duì)的與否判斷（1個(gè)得分點(diǎn)）ｉf（i＜１||i>ｔhis.ｃurlｅn＋１｜|this.curlen>＝ｔhiｓ.length){?? ｒeｔｕrnfalse;}? /／從第i個(gè)位置開(kāi)始順序表所有結(jié)點(diǎn)均后移一個(gè)位置（１個(gè)得分點(diǎn))? iｎtｎ=ｔhｉs.curlen; for(;n＞=i；n-－) ? data[n］=data[n－1];? /／插入新結(jié)點(diǎn)lesｓｉon（1個(gè)得分點(diǎn)) daｔa［n]＝lesｓion;??this.curｌｅn++;(1個(gè)得分點(diǎn))? returntruｅ；?｝ ｐuｂlicｓtaticvoiｄｍaｉn(Ｓtrinｇ[］args){? //初始化數(shù)據(jù)（２個(gè)得分點(diǎn)) LineListlsｔ=newLinｅList();? Ｌｅssiｏnｌeｓsｉon１=newLessｉｏｎ(＂1010２","軟件工程＂)；? Ｌessionｌｅssiｏn2=newLｅssioｎ("1０1０3"，＂UＭL"); ?lst.ｄａt(yī)a［０］=lessiｏn1; ｌsｔ.data［1］=ｌeｓsｉｏn2;? //進(jìn)行插入操作(1個(gè)得分點(diǎn)）??Lesｓｉonｌession3=newLｅssion（"10101＂，＂數(shù)據(jù)結(jié)構(gòu)＂）;??lst.iｎsert(１,lession3)； }}評(píng)分標(biāo)準(zhǔn):總共15個(gè)得分點(diǎn)，其中程序規(guī)范、語(yǔ)法(3個(gè)得分點(diǎn),語(yǔ)法有問(wèn)題但不影響程序邏輯，按0.5得分點(diǎn)每一處扣分，扣完為止），程序邏輯１２個(gè)得分點(diǎn)(按照程序代碼各處標(biāo)注分?jǐn)?shù)進(jìn)行打分)已知某個(gè)班級(jí)的學(xué)生信息表如下表所示,請(qǐng)使用順序表結(jié)構(gòu)編程實(shí)現(xiàn)將表中第一條學(xué)生信息刪除。學(xué)號(hào)（ＩD）姓名(Nａmｅ)楊三李華具體規(guī)定:編寫(xiě)代碼定義順序表結(jié)構(gòu)，完畢該信息表已有數(shù)據(jù)的初始化工作,最后完畢數(shù)據(jù)的刪除。ｃｌassＳtuｄeｎt{／/2個(gè)得分點(diǎn)publicStrｉngno;?//學(xué)生學(xué)號(hào)pubｌicStrｉngｎaｍｅ；?//學(xué)生姓名 publicSｔudent(Sｔriｎgno,Stringnａme){ ?thｉs．nｏ＝nｏ;??tｈis.nａme=ｎame;?}}publiｃclaｓｓLineＬist{ //LinｅLｉst為線(xiàn)性表名 inｔlｅｎｇｔh＝3５;?//表長(zhǎng)度（1個(gè)得分點(diǎn)）Ｓｔudentdata[]＝newStuｄent［lengtｈ];//順序表數(shù)組1個(gè)得分點(diǎn) ｉntcurlen=0;?//實(shí)際表長(zhǎng)（1個(gè)得分點(diǎn))?／/刪除方法 pｕbliｃStudeｎtdelｅte(ｉnti)｛ ?//刪除位置對(duì)的與否判斷（1個(gè)得分點(diǎn)）? ｉf(ｉ<１||i>ｔhｉｓ．cｕrｌeｎ){ ??Ｓｙstem．out．println(＂刪除位置有誤！＂)；? ?rｅｔurnｎｕll；? ｝ ／/保存刪除前第i個(gè)數(shù)據(jù)元素（這行代碼可有可無(wú)，不計(jì)分）? Ｓtudentsｔu＝tｈis.data[i-1]; //從第i＋１個(gè)位置開(kāi)始依次向前移一個(gè)位置(1個(gè)得分點(diǎn)） ?ｆor(ｉnｔｎ=i;n<this.ｃuｒlen;n++){? ?ｄata［n-1］＝datａ[n］; ｝??ｄata[this．ｃｕrlｅn-1]=nｕll；／/(1個(gè)得分點(diǎn)）??thiｓ．ｃurlｅn－-;//（１個(gè)得分點(diǎn)) ｒeturnstu; } ｐubliｃstatｉcｖｏｉdmaｉn(Striｎg［]aｒｇs）{? //初始化數(shù)據(jù)(2個(gè)得分點(diǎn)) ?LｉnｅＬiｓtlst＝ｎewLｉnｅLiｓt();??Ｓtuｄｅntstｕ1=nｅwStuｄent（"","楊三"）； ?Studentsｔu2=neｗSｔudｅｎt(""，"李華");??lst．ｄａt(yī)a[0]＝stｕ1； lｓt.datａ［1]＝stu２;??//進(jìn)行刪除操作（1個(gè)得分點(diǎn)） ?lsｔ.delete(1); }}評(píng)分標(biāo)準(zhǔn)：總共15個(gè)得分點(diǎn),其中程序規(guī)范、語(yǔ)法（３個(gè)得分點(diǎn)，語(yǔ)法有問(wèn)題但不影響程序邏輯,按0.5得分點(diǎn)每一處扣分,扣完為止),程序邏輯12個(gè)得分點(diǎn)(按照程序代碼各處標(biāo)注分?jǐn)?shù)進(jìn)行打分）已知某個(gè)圖書(shū)館的圖書(shū)信息表如下表所示，請(qǐng)使用順序表結(jié)構(gòu)編程實(shí)現(xiàn)將表中第一條圖書(shū)信息刪除。書(shū)號(hào)(ID)書(shū)名（Ｎame）10101鹿鼎記10102鴛鴦刀具體規(guī)定:編寫(xiě)代碼定義順序表結(jié)構(gòu)，完畢該信息表已有數(shù)據(jù)的初始化工作,最后完畢數(shù)據(jù)的刪除。cｌaｓsBｏok{//2個(gè)得分點(diǎn)pｕbｌicSｔringno;?//圖書(shū)書(shū)號(hào)ｐｕｂlｉcＳｔriｎｇｎａme; //圖書(shū)書(shū)名?ｐublicBook（Sｔringnｏ,Stringname){??this.no=ｎo;??=naｍe; }}pｕbｌicclａssLiｎeＬist{ ／／LinｅLｉst為線(xiàn)性表名 intｌengtｈ=35; //表長(zhǎng)度(1個(gè)得分點(diǎn)）Ｂoｏｋdａｔa[]=newBoｏk［ｌengtｈ］;/／順序表數(shù)組1個(gè)得分點(diǎn) intcurlen=0; //實(shí)際表長(zhǎng)（１個(gè)得分點(diǎn)) ／/刪除方法 puｂliｃBookｄelete（iｎti)｛ ?//刪除位置對(duì)的與否判斷（１個(gè)得分點(diǎn)）? iｆ(i<1||i＞thｉｓ.ｃurleｎ)｛? Ｓysteｍ.oｕt.pｒinｔln("刪除位置有誤！"）； ??returnnull; } ?//保存刪除前第ｉ個(gè)數(shù)據(jù)元素(這行代碼可有可無(wú)，不計(jì)分)??Bookbook=tｈｉｓ.da