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

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

Ａ．是一棵樹;

Ｂ.是一棵二叉樹;

Ｃ.是一棵樹也是一棵二叉樹;

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

Ｃ

)

。

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

Ｂ.它不能用鏈式存儲結(jié)構(gòu)存儲;

C.順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都能存儲;

Ｄ.順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都不能使用

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

Ａ.lｏg2(n）

Ｂ.

lｏg２(n)

Ｃ.[

lｏg2（n）

]+1

D.loｇ2(n)+1

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

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

）

A.二叉樹的度為2

?B．一棵二叉樹的度可以小于2

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

)。

Ａ.左子結(jié)點

?? Ｂ．右子結(jié)點

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

）

A.每個結(jié)點至多有兩棵子樹的樹??Ｂ．

哈夫曼樹

C.每個結(jié)點至多有兩棵子樹的有序樹 D．

每個結(jié)點只有一棵右子樹

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

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