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

...wd......wd......wd...數(shù)據(jù)構(gòu)造習(xí)題集含答案目錄TOC\o"1-2"\h\z\u目錄1選擇題2第一章緒論2第二章線性表4第三章棧和隊(duì)列5第四章串6第五章數(shù)組和廣義表7第六章樹(shù)和二叉樹(shù)7第七章圖9第八章查找11第九章排序12簡(jiǎn)答題15第一章緒論15第二章線性表20第三章棧和隊(duì)列22第四章串24第五章數(shù)組和廣義表24第六章樹(shù)和二叉樹(shù)26第七章圖31第八章查找33第九章排序34編程題36第一章緒論36第二章線性表36第三章棧和隊(duì)列46第四章串46第五章數(shù)組和廣義表46第六章樹(shù)和二叉樹(shù)46第七章圖46第八章查找46第九章排序51選擇題第一章緒論數(shù)據(jù)構(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ù)構(gòu)造這門(mén)學(xué)科的研究?jī)?nèi)容下面選項(xiàng)最準(zhǔn)確的是〔D〕A、研究數(shù)據(jù)對(duì)象和數(shù)據(jù)之間的關(guān)系 B、研究數(shù)據(jù)對(duì)象C、研究數(shù)據(jù)對(duì)象和數(shù)據(jù)的操作 D、研究數(shù)據(jù)對(duì)象、數(shù)據(jù)之間的關(guān)系和操作某班級(jí)的學(xué)生成績(jī)表中查得張三同學(xué)的各科成績(jī)記錄，其中數(shù)據(jù)構(gòu)造考了90分，那么下面關(guān)于數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)描述正確的選項(xiàng)是〔C〕A、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)元素，90分是數(shù)據(jù)項(xiàng)B、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)對(duì)象，90分是數(shù)據(jù)元素C、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)對(duì)象，90分是數(shù)據(jù)項(xiàng)D、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)元素，90分是數(shù)據(jù)元素*數(shù)據(jù)構(gòu)造是指〔A〕。A、數(shù)據(jù)元素的組織形式 B、數(shù)據(jù)類(lèi)型C、數(shù)據(jù)存儲(chǔ)構(gòu)造 D、數(shù)據(jù)定義數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不一樣，稱(chēng)之為〔C〕。A、存儲(chǔ)構(gòu)造 B、邏輯構(gòu)造C、鏈?zhǔn)酱鎯?chǔ)構(gòu)造 D、順序存儲(chǔ)構(gòu)造算法分析的目的是〔C〕A、找出數(shù)據(jù)的合理性 B、研究算法中的輸入和輸出關(guān)系C、分析算法效率以求改進(jìn) D、分析算法的易懂性和文檔型性算法分析的主要方法〔A〕。A、空間復(fù)雜度和時(shí)間復(fù)雜度 B、正確性和簡(jiǎn)明性C、可讀性和文檔性 D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性計(jì)算機(jī)內(nèi)部處理的基本單元是〔B〕A、數(shù)據(jù) B、數(shù)據(jù)元素 C、數(shù)據(jù)項(xiàng) D、數(shù)據(jù)庫(kù)數(shù)據(jù)在計(jì)算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲(chǔ)方式，在存儲(chǔ)空間使用的靈活性上，鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)要〔B〕。A、低 B、高 C、一樣 D、不好說(shuō)算法的時(shí)間復(fù)雜度取決于〔C〕A、問(wèn)題的規(guī)模 B、待處理數(shù)據(jù)的初始狀態(tài)C、問(wèn)題的規(guī)模和待處理數(shù)據(jù)的初始狀態(tài) D、不好說(shuō)數(shù)據(jù)構(gòu)造既研究數(shù)據(jù)的邏輯構(gòu)造，又研究物理構(gòu)造，這種觀點(diǎn)〔B〕。A、正確 B、錯(cuò)誤C、前半句對(duì)，后半句錯(cuò) D、前半句錯(cuò)，后半句對(duì)在數(shù)據(jù)構(gòu)造中，從邏輯上可以把數(shù)據(jù)構(gòu)造分成〔C〕A、動(dòng)態(tài)構(gòu)造和靜態(tài)構(gòu)造 B、緊湊構(gòu)造和非緊湊構(gòu)造C、線性構(gòu)造和非線性構(gòu)造 D、內(nèi)部構(gòu)造和外部構(gòu)造線性表的順序存儲(chǔ)構(gòu)造是一種()的存儲(chǔ)構(gòu)造，線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造是一種〔A〕存儲(chǔ)構(gòu)造。A、隨機(jī)存取 B、順序存取C、索引存取 D、散列存取*以下程序的時(shí)間復(fù)雜度是〔A〕for(i=1;i<=n;++i){for(j=1;j<=n;++j){c[i][j]=0;}}A、O(n2) B、O(n) C、O(2n) D、O(2n2)*以下程序的空間復(fù)雜度是〔A〕for(i=1;i<=n;++i){for(j=1;j<=m;++j){c[i][j]=0;}}A、O(m*n) B、O(m+n) C、O(m-n) D、O(m/n)*求以下程序段的時(shí)間復(fù)雜度(B)for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;A、O(n2)B、O(n)C、O(1)D、O(0)第二章線性表關(guān)于線性表的說(shuō)法不正確的選項(xiàng)是〔D〕A、存在唯一的一個(gè)被稱(chēng)為“第一個(gè)〞的數(shù)據(jù)元素〔開(kāi)場(chǎng)結(jié)點(diǎn)〕B、存在唯一的一個(gè)被稱(chēng)為“最后一個(gè)〞的數(shù)據(jù)元素〔終端結(jié)點(diǎn)〕C、除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)D、除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼關(guān)于順序表的說(shuō)法不正確的選項(xiàng)是〔D〕A、邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰B、可以隨機(jī)存取表中任一元素，方便快捷C、在線性表中插入某一元素時(shí)，往往需要移動(dòng)大量元素D、在線性表中刪除某一元素時(shí)，無(wú)需移動(dòng)大量元素當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)展插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用什么存儲(chǔ)構(gòu)造〔A〕A、順序表 B、單鏈表 C、循環(huán)鏈表 D、雙鏈表在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素〔1<=i<=n〕之前插入一個(gè)元素時(shí)，需向后移動(dòng)多少個(gè)元素。〔C〕A、n-1 B、n-i C、n-i+1 D、n-i-1在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是()。A、單鏈表定義而已 B、指定表的起始位置 C、為雙向鏈表做準(zhǔn)備 D、為循環(huán)鏈表做準(zhǔn)備根據(jù)線性表鏈?zhǔn)酱鎯?chǔ)構(gòu)造中每一個(gè)結(jié)點(diǎn)包含的指針數(shù)，將線性鏈表分成〔C〕A、單鏈表與循環(huán)鏈表 B、單鏈表與十字鏈表 C、單鏈表與雙鏈表 D、循環(huán)鏈表與多鏈表鏈接存儲(chǔ)的特點(diǎn)是利用什么來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系〔A 〕A、引用 B、串聯(lián) C、掛接 D、指派指針p指向單鏈表L中的某結(jié)點(diǎn)，那么刪除其后繼結(jié)點(diǎn)的語(yǔ)句是〔D〕A、p=p.next B、p=null C、p.next=null D、p.next=p.next.next*在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是〔B〕A、p=p.next B、p.next!=nullC、p.next=null D、p.next=p.next.next*在單鏈表p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是〔C〕A、p.next=s;s.next=p.next; B、s.next=p.next;p.next=p.next.next;C、s.next=p.next;p.next=s; D、s.next=p;p.next=s;第三章棧和隊(duì)列棧、隊(duì)列通常采用兩種存儲(chǔ)構(gòu)造，它們是(B)A、散列方式和索引方式B、順序存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造C、鏈表存儲(chǔ)構(gòu)造和數(shù)組D、線性和非線性存儲(chǔ)構(gòu)造一個(gè)棧入棧序列是a,b,c,d,那么棧輸出序列不可能是(C)A、d,c,b,a B、c,d,b,a C、d,c,a,b D、a,b,c,d判斷順序棧〔最多結(jié)點(diǎn)數(shù)為m〕為棧滿的條件是〔D〕A、top==0B、top!=mC、top!=0D、top==m棧存取數(shù)據(jù)原那么〔或棧特點(diǎn)〕是〔B〕A、后進(jìn)后出B、后進(jìn)先出C、先進(jìn)先出D、隨意進(jìn)出*經(jīng)過(guò)以下棧運(yùn)算后，x的值是〔A〕InitStack(s);Push(s,d);Push(s,e);Pop(s,x);Pop(s,x);GetTop(s,x);A、dB、eC、xD、s一個(gè)隊(duì)列的進(jìn)隊(duì)序列為：a，b，c，d，那么出隊(duì)序列是：(A)A、a，b，c，dB、d，c，b，aC、a，d，c，bD、c，b，d，a循環(huán)隊(duì)列為空隊(duì)列的條件是：〔D〕A、Q.front=0 B、Q.〔rear+1)%MaxSize==Q.frontC、Q.rear=0D、Q.rear==Q.front在存儲(chǔ)構(gòu)造上，如果用帶頭節(jié)點(diǎn)單鏈表實(shí)現(xiàn)隊(duì)列〔假定front和rear分別為隊(duì)首和隊(duì)尾指針〕，那么刪除一個(gè)結(jié)點(diǎn)的操作為〔A〕。A、front.next=front.next.next B、rear=rear.nextC、rear=front.next D、front=front.next棧和隊(duì)列共同點(diǎn)是〔C〕A、先進(jìn)后出 B、先進(jìn)先出C、允許在端點(diǎn)處進(jìn)展操作線性表 D、無(wú)共同點(diǎn)插入和刪除只能在一端進(jìn)展的線性表是〔B〕A、循環(huán)隊(duì)列B、棧C、隊(duì)列D、循環(huán)棧插入和刪除分別在兩端端進(jìn)展的線性表是〔C〕A、循環(huán)隊(duì)列B、棧C、隊(duì)列D、循環(huán)棧循環(huán)隊(duì)列為滿隊(duì)列的條件是：〔B〕A、Q.front=0 B、Q.〔rear+1)%MaxSize==Q.frontC、Q.rear=0D、Q.rear==Q.front第四章串關(guān)于串的表達(dá)，錯(cuò)誤的選項(xiàng)是：〔B〕A．串是字符有限序列 B．空串是由空格構(gòu)成的串C．模式匹配是串的重要運(yùn)算D．串有用順序、鏈?zhǔn)絻煞N存儲(chǔ)方式串長(zhǎng)度是指〔B〕A．串所含不同字母數(shù)目B．串所含字符數(shù)目C．串所含不同字符數(shù)目D．串所含非空格字符數(shù)目*假設(shè)串S=〞database〞,其子串?dāng)?shù)目是〔B〕。A．16B．37C．8D．36設(shè)串S1是串S子串，那么求S1在S中定位運(yùn)算稱(chēng)為〔B〕A．求子串B．串匹配C．聯(lián)接D．求串長(zhǎng)設(shè)有串s1=〞welcometozdsoftcolleage!〞和s2=〞so〞,那么s2在s1中的索引位置是〔C〕A．12B．14C．13D．10*假設(shè)串S=“software“,其子串的數(shù)目是〔B〕。A．8B．37C．36D．9第五章數(shù)組和廣義表第六章樹(shù)和二叉樹(shù)假設(shè)在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，那么葉子結(jié)點(diǎn)數(shù)為〔B〕個(gè)。A.15 B.16 C.17 D.47假定一棵三叉樹(shù)的結(jié)點(diǎn)數(shù)為50，那么它的最小高度為〔C〕。A.3 B.4 C.5 D.6在一棵二叉樹(shù)上第4層的結(jié)點(diǎn)數(shù)最多為〔D〕。A.2 B.4 C.6 D.8用順序存儲(chǔ)的方法將完全二叉樹(shù)中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R[1..n]，結(jié)點(diǎn)R[i]假設(shè)有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)〔B〕。A.R[2i+1] B.R[2i] C.R[i/2] D.R[2i-1]設(shè)n,m為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是〔B〕。A.n在m右方 B.n在m左方C.n是m的祖先 D.n是m的子孫下面表達(dá)正確的選項(xiàng)是〔D〕。A.二叉樹(shù)是特殊的樹(shù)B.二叉樹(shù)等價(jià)于度為2的樹(shù)C.完全二叉樹(shù)必為滿二叉樹(shù)D.二叉樹(shù)的左右子樹(shù)有次序之分現(xiàn)有一深度為5的二叉樹(shù)，請(qǐng)問(wèn)其最多有〔D〕個(gè)結(jié)點(diǎn)。A.32 B.5 C.30 D.31現(xiàn)有一深度為4的二叉樹(shù)，請(qǐng)問(wèn)其最多有〔A〕個(gè)結(jié)點(diǎn)。A.15 B.16 C.17 D.6在一棵二叉排序樹(shù)上按〔B〕遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。A.先序 B.中序 C.后序 D.頭序在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，那么n0=〔C〕A.n+1 B.n+2 C.n2+1 D.2n+1由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù)，共有〔B〕種不同的形態(tài)。A.4 B.5 C.6 D.7一棵含有n個(gè)結(jié)點(diǎn)的樹(shù)，〔A〕形態(tài)到達(dá)最大深度。A.單支樹(shù) B.二叉樹(shù) C.三叉樹(shù) D.n叉樹(shù)不含任何結(jié)點(diǎn)的空樹(shù)〔C〕。Ａ.是一棵樹(shù);

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

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

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

C

)

。Ａ.它不能用順序存儲(chǔ)構(gòu)造存儲(chǔ);

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

Ｃ.順序存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造都能存儲(chǔ);

Ｄ.順序存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造都不能使用具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為(C)。Ａ.log2(n)

Ｂ.

log2(n)

Ｃ.[

log2(n)

]+1

Ｄ.log2(n)+1

在一棵三元樹(shù)中度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，那么度為0的結(jié)點(diǎn)數(shù)為〔D〕個(gè)。A.4 B.5 C.6 D.7有關(guān)二叉樹(shù)以下說(shuō)法正確的選項(xiàng)是〔B

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

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

C．二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2D．二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2在完全二叉樹(shù)中，假設(shè)一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，那么它沒(méi)〔C

〕。A．左子結(jié)點(diǎn)B．右子結(jié)點(diǎn)C．左子結(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ù)B.

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

每個(gè)結(jié)點(diǎn)只有一棵右子樹(shù)第七章圖圖的深度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的〔A〕。A．先序遍歷B．中序遍歷C．后序遍歷D．層次遍歷一個(gè)圖如以下列圖，假設(shè)從頂點(diǎn)a出發(fā)按深度優(yōu)先遍歷，那么可能得到的一種頂點(diǎn)序列為〔C〕A．a(chǎn)becdfB．a(chǎn)cfebdC．a(chǎn)ebcfdD．a(chǎn)edfcb假設(shè)從無(wú)向圖的任意一個(gè)頂點(diǎn)出發(fā)進(jìn)展一次深度優(yōu)先搜索可以訪問(wèn)圖中所有的頂點(diǎn)，那么該圖一定是〔B〕圖。A．非連通B．連通C．強(qiáng)連通D．有向在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的〔C〕倍。A1/2B1C2D3在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的〔B〕倍。A1/2B1C2D3一個(gè)有N個(gè)頂點(diǎn)的有向圖最多有〔B〕條邊。ANBN(N-1)CN(n-1)/2D2N具有4個(gè)頂點(diǎn)的無(wú)向完全圖有〔A〕條邊。A6B12C18D20具有6個(gè)頂點(diǎn)的無(wú)向圖至少有〔A〕條邊才能確保是一個(gè)連通圖。A5B6C7D8對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向圖，假設(shè)采用鄰接矩陣表示，那么該矩陣大小是〔D〕ANB(N-1)2CN-1DN*N一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少要〔C〕條邊ANBN+1CN-1DN/2*圖的鄰接矩陣如以下列圖，那么從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)果是〔C〕。A．0243156 B．0136542 C．0134256 D．0361542圖的鄰接表以以下列圖所示，那么從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是〔〕，按深度優(yōu)先遍歷的結(jié)果是〔D〕。A．0132B．0231C．0321D．0123圖的鄰接表以以下列圖所示，那么從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是〔〕，按深度優(yōu)先遍歷的結(jié)果是〔〕。A．0132B．0231C．0321D．0123當(dāng)在一個(gè)有序的順序表上查找一個(gè)數(shù)據(jù)時(shí)，既可用折半查找，也可用順序查找，但前者比后者的查找速度〔C〕。A．必定快B．不一定C．在大局部情況下要快D．取決于表遞增還是遞減折半查找有序表〔4，6，10，12，20，30，50，70，88，100〕。假設(shè)查找表中元素58，那么它將依次與表中〔A〕比較大小，查找結(jié)果是失敗。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50第八章查找順序查找法適合于存儲(chǔ)構(gòu)造為〔B〕的線性表。A．散列存儲(chǔ)B．順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C．壓縮存儲(chǔ)D．索引存儲(chǔ)在查找過(guò)程中，假設(shè)同時(shí)還要增、刪工作，這種查找稱(chēng)為〔B〕。A、靜態(tài)查找B、動(dòng)態(tài)查找C、內(nèi)查找D、外查找索引順序表的特點(diǎn)是順序表中的數(shù)據(jù)〔A〕。A、有序B、無(wú)序C、塊間有序D、散列采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為〔C〕A、nB、n/2C、(n+1)/2D、(n-1)/2*將10個(gè)元素散列到1000000個(gè)單元的哈希表，那么〔C〕產(chǎn)生沖突。A、一定會(huì)B、一定不會(huì)C、仍可能會(huì)D、以上都不對(duì)*散列表的地址區(qū)間為0~16，散列函數(shù)H(k)=k%17，采用線性探測(cè)法解決地址沖突，將關(guān)鍵字26、25、72、38、1、18、59依次存儲(chǔ)到散列表中。元素59存放在散列表中的地址為〔A〕A、8B、9C、10D、11設(shè)有序表的關(guān)鍵字序列為{1,3,9,12,32,41,45,62,75,77,82,95,100}，當(dāng)采用二分查找法查找值為82的節(jié)點(diǎn)時(shí)，經(jīng)〔C〕次比較后查找成功。A、1B、2C、3D、4設(shè)有100個(gè)元素，用折半查找法進(jìn)展查找時(shí)，最大、最小比較次數(shù)分別時(shí)〔A〕A、7,1B、6,1C、5,1D、8,1第九章排序?qū)個(gè)不同的記錄按排序碼值從小到大次序重新排列，用冒泡(起泡)排序方法，初始序列在〔A〕情況下，與排序碼值總比較次數(shù)最少。A．按排序碼值從小到大排列B．按排序碼值從大到小排列C．隨機(jī)排列(完全無(wú)序)D．基本按排序碼值升序排列對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列，用冒泡(起泡)排序方法，在〔B〕情況下，與排序碼值總比較次數(shù)最多。A．按排序碼值從小到大排列B．按排序碼值從大到小排列C．隨機(jī)排列(完全無(wú)序)D．基本按排序碼值升序排列對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列，用直接插入排序方法，初始序列在〔A〕情況下，與排序碼值總比較次數(shù)最少。A．按排序碼值從小到大排列B．按排序碼值從大到小排列C．隨機(jī)排列(完全無(wú)序)D．基本按排序碼值升序排列對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列，用直接插入排序方法，初始序列在〔B〕情況下，與排序碼值總比較次數(shù)最多。A．按排序碼值從小到大排列B．按排序碼值從大到小排列C．隨機(jī)排列(完全無(wú)序)D．基本按排序碼值升序排列對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列，用快速排序方法在〔C〕情況下，與排序碼值總比較次數(shù)最少。A．按排序碼值從小到大排列B．按排序碼值從大到小排列C．隨機(jī)排列(完全無(wú)序)D．基本按排序碼值升序排列對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列，用快速排序方法，在〔A〕情況下與排序碼值總比較次數(shù)最多。A．按排序碼值從小到大排列B．按排序碼值從大到小排列C．隨機(jī)排列(完全無(wú)序)D．基本按排序碼值升序排列用冒泡排序方法對(duì)n個(gè)記錄按排序碼值從小到大排序時(shí)，當(dāng)初始序列是按排序碼值從大到小排列時(shí)，與碼值總比較次數(shù)是〔D〕。A．n-1B．nC．n+1D．n(n-1)／2以下排序方法中，與排序碼值總比較次數(shù)與待排序記錄的初始序列排列狀態(tài)無(wú)關(guān)的是(D)。A．直接插入排序B．冒泡排序C．快速排序D．直接選擇排序?qū)?個(gè)不同的整數(shù)進(jìn)展排序，至少需要比較(A)次。A．5B．6C．15D．21將6個(gè)不同的整數(shù)進(jìn)展排序，至多需要比較(C)次。A．5B．6C．15D．21*假設(shè)需要時(shí)間復(fù)雜度在O(nlog2n)內(nèi)，對(duì)整數(shù)數(shù)組進(jìn)展排序，且要求排序方法是穩(wěn)定的，那么可選擇的排序方法是(B)。A．快速排序B．歸并排序C．堆排序D．直接插入排序當(dāng)待排序的整數(shù)是有序序列時(shí)，采用(B)方法比較好，其時(shí)間復(fù)雜度為O(n)。A．快速排序B．冒泡排序C．歸并排序D．直接選擇排序當(dāng)待排序的整數(shù)是有序序列時(shí)，采用〔A〕方法比較差，到達(dá)最壞情況下時(shí)間復(fù)雜度為O(n2)。A．快速排序B．冒泡排序C．歸并排序D．直接選擇排序當(dāng)待排序的整數(shù)是有序序列時(shí)，無(wú)論待排序序列排列是否有序，采用〔D〕方法的時(shí)間復(fù)雜度都是O(n2)。A．快速排序B．冒泡排序C．歸并排序D．直接選擇排序*堆是一種(B)排序。A．插入B．選擇C．交換D．歸并*假設(shè)一組記錄的排序碼值序列為{40，80，50，30，60，70}，利用堆排序方法進(jìn)展排序，初建的大頂堆是(D)。A．80，40，50，30，60，70B．80，70，60，50，40，30C．80，70，50，40，30，60D．80，60，70，30，40，50假設(shè)一組記錄的排序碼值序列為{50，80，30，40，70，60}利用快速排序方法，以第一個(gè)記錄為基準(zhǔn)，得到一趟快速排序的結(jié)果為〔B〕。A．30，40，50，60，70，80B．40，30，50，80，70，60C．50，30，40，70，60，80D．40，50，30，70，60，80*以下幾種排序方法中要求輔助空間最大的是〔C〕。A．堆排序B．直接選擇排序C．歸并排序D．快速排序A[m]中每個(gè)數(shù)組元素距其最終位置不遠(yuǎn)，采用以下(A)排序方法最節(jié)省時(shí)間。A．直接插入B．堆C．快速D．直接選擇*設(shè)有10000個(gè)互不相等的無(wú)序整數(shù)，假設(shè)僅要求找出其中前10個(gè)最大整數(shù)，最好采用〔B〕排序方法。A．歸并B．堆C．快速D．直接選擇*在以下排序方法中不需要對(duì)排序碼值進(jìn)展比較就能進(jìn)展排序的是〔A〕。A：基數(shù)排序B．快速排序C．直接插入排序D．堆排序*給定排序碼值序列為{F，B，J，C，E，A，I，D，C，H}，對(duì)其按字母的字典序列的次序進(jìn)展排列，希爾(Shell)排序的第一趟(d1=5)結(jié)果應(yīng)為〔D〕。A．{B，F(xiàn)，C，J，A，E，D，I，C，H}B．{C，B，D，A，E，F(xiàn)，I，C，J，H}C．{B，F(xiàn)，C，E，A，I，D，C，H，J}D．{A，B，D，C，E，F(xiàn)，I，J，C，H}給定排序碼值序列為{F，B，J，C，E，A，I，D，C，H}，對(duì)其按字母的字典序列的次序進(jìn)展排列，冒泡排序(大數(shù)下沉)的第一趟排序結(jié)果應(yīng)為〔C〕。A．{B，F(xiàn)，C，J，A，E，D，I，C，H}B．{C，B，D，A，E，F(xiàn)，I，C，J，H}C．{B，F(xiàn)，C，E，A，I，D，C，H，J}D．{A，B，D，C，E，F(xiàn)，I，J，C，H}給定排序碼值序列為{F，B，J，C，E，A，I，D，C，H}，對(duì)其按字母的字典序列的次序進(jìn)展排列，快速排序的第一趟排序結(jié)果為〔B〕。A．{B，F(xiàn)，C，J，A，E，D，I，C，H}B．{C，B，D，A，E，F(xiàn)，I，C，J，H}C．{B，F(xiàn)，C，E，A，I，D，C，H，J}D．{A，B，D，C，E，F(xiàn)，I，J，C，H}*給定排序碼值序列為{F，B，J，C，E，A，I，D，C，H}，對(duì)其按字母的字典序列的次序進(jìn)展排列，二路歸并排序的第一趟排序結(jié)果是〔A〕。A．{B，F(xiàn)，C，J，A，E，D，I，C，H}B．{C，B，D，A，E，F(xiàn)，I，C，J，H}C．{B，F(xiàn)，C，E，A，I，D，C，H，J}D．{A，B，D，C，E，F(xiàn)，I，J，C，H}簡(jiǎn)答題第一章緒論請(qǐng)分別給出數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)的含義，并說(shuō)明四者的關(guān)系。數(shù)據(jù)(Data):是對(duì)信息的一種符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)?！惨粋€(gè)得分點(diǎn)〕數(shù)據(jù)元素(DataElement):是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)展考慮和處理，相當(dāng)于表中的一條記錄?！惨粋€(gè)得分點(diǎn)〕數(shù)據(jù)項(xiàng)：相當(dā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)，總共5個(gè)得分點(diǎn)，每段話一個(gè)得分。請(qǐng)給出數(shù)據(jù)的邏輯構(gòu)造的含義，并舉例說(shuō)明數(shù)據(jù)的邏輯構(gòu)造通常有哪些。數(shù)據(jù)的邏輯構(gòu)造：指數(shù)據(jù)元素之間的邏輯關(guān)系。即用自然語(yǔ)言描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的，邏輯構(gòu)造有四種?！惨粋€(gè)得分點(diǎn)〕集合構(gòu)造：僅同屬一個(gè)集合〔構(gòu)造名字0.5個(gè)得分點(diǎn)、舉例0.5得分點(diǎn)〕線性構(gòu)造:一對(duì)一〔1:1)〔構(gòu)造名字0.5個(gè)得分點(diǎn)、舉例0.5得分點(diǎn)〕樹(shù)結(jié)構(gòu):一對(duì)多〔1:n)〔構(gòu)造名字0.5個(gè)得分點(diǎn)、舉例0.5得分點(diǎn)〕圖結(jié)構(gòu):多對(duì)多(m:n)〔構(gòu)造名字0.5個(gè)得分點(diǎn)、舉例0.5得分點(diǎn)〕評(píng)分標(biāo)準(zhǔn)：每段話一個(gè)得分點(diǎn)，總共5個(gè)得分點(diǎn)。什么是數(shù)據(jù)的物理構(gòu)造有哪些物理構(gòu)造數(shù)據(jù)的物理構(gòu)造與邏輯構(gòu)造有什么區(qū)別與聯(lián)系數(shù)據(jù)的物理構(gòu)造：物理構(gòu)造亦稱(chēng)存儲(chǔ)構(gòu)造，是數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示〔或映像〕。它依賴(lài)于計(jì)算機(jī)。〔一個(gè)得分點(diǎn)〕存儲(chǔ)構(gòu)造可分為4大類(lèi)：順序、鏈?zhǔn)?、索引、散列?！补?個(gè)得分點(diǎn)，一個(gè)0.5得分點(diǎn)〕區(qū)別：數(shù)據(jù)的邏輯構(gòu)造屬于用戶視圖，是面向問(wèn)題的，數(shù)據(jù)的存儲(chǔ)構(gòu)造屬于具體實(shí)現(xiàn)的視圖，是面向計(jì)算機(jī)的?！惨粋€(gè)得分點(diǎn)〕聯(lián)系：一種數(shù)據(jù)的邏輯構(gòu)造可以用多種存儲(chǔ)構(gòu)造來(lái)存儲(chǔ)，而采用不同的存儲(chǔ)構(gòu)造其處理的效率往往不同?！惨粋€(gè)得分點(diǎn)〕評(píng)分標(biāo)準(zhǔn)：共5個(gè)得分點(diǎn)，按照每段話各自標(biāo)注的得分點(diǎn)進(jìn)展評(píng)分。求兩個(gè)正整數(shù)m，n中的最大數(shù)MAX的算法〔1〕假設(shè)m>n那么max=m

〔2〕假設(shè)m<=n那么max=n請(qǐng)根據(jù)上述算法解釋一下算法的組成要素有哪些，分別是什么。算法由操作、控制構(gòu)造、數(shù)據(jù)構(gòu)造3要素組成操作包含：算術(shù)運(yùn)算、關(guān)系比較、邏輯運(yùn)算、數(shù)據(jù)傳送〔輸入、輸出、賦值〕〔一個(gè)得分點(diǎn)〕例子中有關(guān)系比較和賦值計(jì)算的操作?！惨粋€(gè)得分點(diǎn)〕控制構(gòu)造包含：順序構(gòu)造、選擇構(gòu)造、循環(huán)構(gòu)造〔一個(gè)得分點(diǎn)〕例子中有選擇構(gòu)造〔一個(gè)得分點(diǎn)〕數(shù)據(jù)構(gòu)造：算法操作的對(duì)象是數(shù)據(jù)，數(shù)據(jù)間的邏輯關(guān)系、數(shù)據(jù)的存儲(chǔ)方式及處理方式就是數(shù)據(jù)構(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)，每段話一個(gè)得分點(diǎn)。簡(jiǎn)述算法的基本性質(zhì)1〕輸入：0個(gè)或多個(gè)輸入2〕輸出：1個(gè)或多個(gè)輸出3〕有窮性：算法必須在有限步內(nèi)完畢4〕確定性：組成算法的操作必須清晰無(wú)二義性5〕可行性：組成算法的操作必須能夠在計(jì)算機(jī)上實(shí)現(xiàn)評(píng)分標(biāo)準(zhǔn)，此題共5個(gè)得分點(diǎn)，每個(gè)要點(diǎn)一分。簡(jiǎn)述算法的設(shè)計(jì)要求1、正確性〔correctness〕2、可讀性〔readability〕3、強(qiáng)健性〔robustness〕4、通用性〔generality〕5、效率與存儲(chǔ)的要求〔執(zhí)行算法所消耗的存儲(chǔ)空間、執(zhí)行算法所消耗的時(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)所消耗的時(shí)間。2〕算法實(shí)現(xiàn)所消耗的存儲(chǔ)空間，其中主要考慮輔助存儲(chǔ)空間。3〕算法應(yīng)易于理解、易于編碼、易于調(diào)試等。評(píng)分標(biāo)準(zhǔn)，此題共3個(gè)得分點(diǎn)，每個(gè)要點(diǎn)一分。請(qǐng)簡(jiǎn)述數(shù)據(jù)構(gòu)造所研究的三種基本構(gòu)造，以及數(shù)據(jù)元素間的關(guān)系。線性構(gòu)造：數(shù)據(jù)元素之間一對(duì)一的關(guān)系。〔2分〕樹(shù)形構(gòu)造：數(shù)據(jù)元素之間一對(duì)多的關(guān)系?！?.5分〕圖形構(gòu)造：數(shù)據(jù)元素之間多對(duì)多的關(guān)系?！?.5分〕請(qǐng)問(wèn)算法的分析和評(píng)價(jià)的兩個(gè)標(biāo)準(zhǔn)，以及各自作用。時(shí)間復(fù)雜度：評(píng)估算法運(yùn)行所需時(shí)間?！?.5+1分〕空間復(fù)雜度：評(píng)估算法運(yùn)行時(shí)所需最大存儲(chǔ)空間?！?.5+1分〕請(qǐng)說(shuō)出三種邏輯數(shù)據(jù)構(gòu)造，以及他們的特點(diǎn)?！?分〕〔1〕線性構(gòu)造：數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和一個(gè)后繼數(shù)據(jù)元素?！?分〕〔2〕樹(shù)構(gòu)造：每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素，可有零個(gè)或假設(shè)干個(gè)后繼數(shù)據(jù)元素?！?.5分〕〔3〕圖構(gòu)造：每個(gè)數(shù)據(jù)元素可有零個(gè)或假設(shè)干個(gè)前驅(qū)數(shù)據(jù)元素，零個(gè)或假設(shè)干個(gè)后繼數(shù)據(jù)元素。〔1.5分〕評(píng)價(jià)算法的主要標(biāo)準(zhǔn)是什么〔1〕算法實(shí)現(xiàn)所消耗的時(shí)間〔2分〕〔2〕算法實(shí)現(xiàn)所消耗的存儲(chǔ)空間，其中主要考慮輔助存儲(chǔ)空間?！?分〕〔3〕算法應(yīng)易于理解、易于編碼、易于調(diào)試?！?分〕請(qǐng)說(shuō)出三種邏輯數(shù)據(jù)構(gòu)造，并分別畫(huà)圖表示它們?！瞐,2分，b,c各1.5分〕算法的基本性質(zhì)有哪些并簡(jiǎn)述每個(gè)特性。(5分)〔1〕有窮性——.....〔1分〕〔2〕確定性——.....〔1分〕〔3〕可行性——.....〔1分〕〔4〕輸入性——.....〔1分〕〔5〕輸出性——.....〔1分〕通常從那幾個(gè)方面來(lái)評(píng)價(jià)算法的質(zhì)量?(5分)通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：正確性、可讀性、強(qiáng)健性和高效性?！采僖粋€(gè)扣1分〕請(qǐng)描述線性數(shù)據(jù)構(gòu)造的兩種存儲(chǔ)方式，并說(shuō)出其各有什么特點(diǎn)。順序存儲(chǔ)：連續(xù)存儲(chǔ)，易于定位，不易于插入和刪除?！?+1.5分〕鏈?zhǔn)酱鎯?chǔ)：非連續(xù)存儲(chǔ)，不易于定位，易于插入和刪除。〔1+1.5分〕請(qǐng)問(wèn)算法的分析和評(píng)價(jià)的兩種方法，它們關(guān)注點(diǎn)各有什么不同〔簡(jiǎn)單〕空間效率：關(guān)注算法對(duì)內(nèi)存的占用度。〔1+1.5分〕時(shí)間效率：關(guān)注算法的運(yùn)算速度?！?+1.5分〕第二章線性表請(qǐng)問(wèn)如果要插入一個(gè)數(shù)據(jù)到一個(gè)線性表中，順序表和鏈表哪個(gè)的效率高為什么鏈表的效率高〔2分〕，因?yàn)轫樞虮硪苿?dòng)插入位置后的每一個(gè)元素的位置給新數(shù)據(jù)騰位置〔1.5分〕。鏈表只需要將前一個(gè)數(shù)據(jù)的指針指向新數(shù)據(jù)并將新數(shù)據(jù)的指針指向后一個(gè)數(shù)據(jù)即可〔1.5分〕。線性表有哪些特點(diǎn)1〕除第一個(gè)和最后一個(gè)數(shù)據(jù)元素外，每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和一個(gè)后繼數(shù)據(jù)元素；〔2分〕2〕第一個(gè)數(shù)據(jù)元素沒(méi)有前驅(qū)數(shù)據(jù)元素；〔1.5分〕3〕最后一個(gè)數(shù)據(jù)元素沒(méi)有后繼數(shù)據(jù)元素。〔1.5分〕順序存儲(chǔ)構(gòu)造的優(yōu)缺點(diǎn)有哪些?(中等)順序存儲(chǔ)構(gòu)造的優(yōu)點(diǎn):〔2.5分〕存儲(chǔ)空間連續(xù)邏輯相鄰，物理相鄰可隨機(jī)存取任一元素缺點(diǎn):〔2.5分〕插入、刪除操作需要移動(dòng)大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴(kuò)大單鏈?zhǔn)酱鎯?chǔ)構(gòu)造的優(yōu)缺點(diǎn)有哪些?(中等)單鏈?zhǔn)酱鎯?chǔ)構(gòu)造的優(yōu)點(diǎn):〔2.5分〕不需預(yù)先分配空間，空間利用充分插入、刪除操作簡(jiǎn)單,無(wú)需移動(dòng)大量的元素表容量易于擴(kuò)大缺點(diǎn):〔2.5分〕每個(gè)數(shù)據(jù)元素，除存儲(chǔ)本身信息外，還需空間存儲(chǔ)其直接后繼的信息邏輯相鄰，物理不一定相鄰不可隨機(jī)存取任一元素,只能從鏈表頭依次查找.有順序表A=(a0,a1,a2,...a8,a9,…a19)，要在a8,a9之間插入一個(gè)元素a20，請(qǐng)描述其操作(思想)步驟。(中等)插入思想或步驟：根據(jù)順序表的存儲(chǔ)特點(diǎn)，要在表中某位置10插入一新數(shù)據(jù)元素,那么要進(jìn)展如下兩步操作：〔1〕、從位置10到表尾位置的所有數(shù)據(jù)元素均要從后至前依次向后移一個(gè)存儲(chǔ)位置，為新插入結(jié)點(diǎn)騰出第10個(gè)位置?！?分〕〔2〕、將新結(jié)點(diǎn)插入到空余位置10處。2分〕〔3〕表長(zhǎng)度加1.〔1分〕有順序表A=(a0,a1,a2,...a8,a9,…a19)，要?jiǎng)h除一個(gè)元素a9，請(qǐng)描述其操作(思想)步驟。(中等)〔1〕然后將從位置11到表尾的所有數(shù)據(jù)元素依次向前移一個(gè)存儲(chǔ)位置?！?分〕〔2〕表長(zhǎng)度減1.〔2分〕請(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ù)x插入到空余位置i處?！?分〕〔3〕表長(zhǎng)度加1.〔1分〕請(qǐng)描述在順序表中刪除第i個(gè)位置的數(shù)據(jù)的過(guò)程?！?〕然后將從位置i到表尾的所有數(shù)據(jù)元素依次向前移一個(gè)存儲(chǔ)位置?！?分〕〔2〕表長(zhǎng)度減1.〔2分〕請(qǐng)描述在一個(gè)單鏈表中插入一個(gè)數(shù)據(jù)q的插入過(guò)程。找到將插入數(shù)據(jù)位置的前一個(gè)結(jié)點(diǎn)p;〔1分〕q的next值等于p的next值;〔2分〕〔3〕p的next值等于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分〕〔3〕將被刪除數(shù)據(jù)原來(lái)的next指針指向null;〔1分〕第三章棧和隊(duì)列請(qǐng)簡(jiǎn)述線性表、棧和隊(duì)列三者之間的聯(lián)系?！埠?jiǎn)單〕〔1〕線性表、棧和隊(duì)列都屬于線性構(gòu)造。〔2分〕〔2〕棧和隊(duì)列都是特殊的線性表，并且都有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)方式?！?分〕〔3〕棧是一種先進(jìn)后出的線性表，隊(duì)列是一種先進(jìn)先出的線性表〔2分〕在計(jì)算機(jī)進(jìn)展運(yùn)算時(shí)，需要把十進(jìn)制轉(zhuǎn)換為二進(jìn)制。請(qǐng)問(wèn)答：這種數(shù)制轉(zhuǎn)換可以借助于哪種數(shù)據(jù)構(gòu)造實(shí)現(xiàn)、及原因。答:棧?！?分〕原因：〔3分〕在進(jìn)展數(shù)值轉(zhuǎn)換時(shí)，其實(shí)質(zhì)是求余的過(guò)程，并且余數(shù)的倒序序列正是所求結(jié)果。棧是一種先進(jìn)后出的線性構(gòu)造，能夠滿足這種操作。有一字符序列abcde依次按照某一線性構(gòu)造存儲(chǔ)，請(qǐng)答復(fù)以下問(wèn)題： 〔1〕、如果該線性構(gòu)造是隊(duì)列，那么，寫(xiě)出出隊(duì)序列。 〔2〕、如果該線性構(gòu)造是棧，那么，輸出序列可能是d,c,e,a,b嗎，為什么 〔3〕、如果該線性構(gòu)造是棧，且輸出序列是abcde。請(qǐng)寫(xiě)出操作過(guò)程。〔push(x)：表示把x壓入棧內(nèi)；pop(x)：表示把x彈出?！?答：〔1〕、abcde〔1分〕〔2〕、不可能，因?yàn)椋篸是第一出棧字符，說(shuō)明a,b已別壓入棧內(nèi)；并且壓入棧的次序?yàn)閍bcde；由以上得出：ab出棧的順序只能是b、a，而不是a、b。所以，出棧序列d,c,e,a,b是不可能的。〔2分〕〔3〕、〔2分〕push(a)，pop(a)push(b)，pop(b)push(c)，pop(c)push(d)，pop(d)push(e)，pop(e)簡(jiǎn)述棧和隊(duì)列的異同點(diǎn)。一樣點(diǎn)：棧和隊(duì)列都是只允許在表的端點(diǎn)處進(jìn)展插入、刪除操作的線性表?！?分〕不同點(diǎn)：棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是后進(jìn)先出?！?分〕假設(shè)依次讀入數(shù)據(jù)元素序列1、2、3，進(jìn)棧的過(guò)程中允許出棧，試寫(xiě)出各種可能的出棧序列。答:123、132、213、231、321〔各1分〕如果入棧序列有ＡＢＣ組成,請(qǐng)問(wèn)輸出序列可能有哪些?(較難)輸出序列有5種：CBA,BCA,BAC,ACB,ABC〔各1分〕如果有abcde五個(gè)數(shù)據(jù)依次全部存入，如果采用隊(duì)列和棧來(lái)進(jìn)展存儲(chǔ)，依次取出分別將獲得什么內(nèi)容?！埠?jiǎn)單〕隊(duì)列：abcde〔2.5分〕棧:edcba〔2.5分〕設(shè)將整數(shù)1，2，3，4依次進(jìn)棧，能否得到1423出棧序列和1432?并說(shuō)明為什么不能得到或者如何得到?！仓械取巢荒艿玫?423，但可以得到1432〔2分〕因?yàn)橐玫?必須將所有數(shù)據(jù)入棧，這樣將只能依次獲取到1432不能獲得1423。采用push、pop、push、push、push、pop、pop、pop可以獲得1432?！?分〕循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么如何判斷它的空和滿(可不考)循環(huán)隊(duì)列的優(yōu)點(diǎn)是可以抑制順序隊(duì)列的"假上溢"現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分的利用?！?分〕采用犧牲一個(gè)元素空間的方法，循環(huán)隊(duì)列隊(duì)空的條件是front==rear，循環(huán)隊(duì)列隊(duì)滿的條件是：(rear+1)%M==front?！?分〕第四章串對(duì)于字符串S=’abcde’，請(qǐng)問(wèn)：〔簡(jiǎn)單〕〔1〕字符串S的長(zhǎng)度是多少〔2〕字符串S的子串有幾個(gè)，并列出所有子串答：〔1〕、5〔1分〕〔2〕、16，〔1分〕所有字串：’a’、’b’、’c’、’d’、’e’、’ab’、’bc’、’cd’、’de’、’abc’、’bcd’、’cde’、’abcd’、’bcde’、’abcde’、Φ?！?分〕對(duì)于字符串S=’12345’，請(qǐng)問(wèn)：〔簡(jiǎn)單〕〔1〕字符串S的長(zhǎng)度是多少〔2〕字符串S的子串有幾個(gè)，并列出所有子串答：〔1〕、5〔1分〕〔2〕、16，〔1分〕所有字串：’1’、’2’、’3’、’4’、’5’、’12’、’23’、’34’、’45’、’123’、’234’、’345’、’1234’、’2345’、’12345’、Φ。〔3分〕請(qǐng)問(wèn)答：什么串的模式匹配模式匹配算法有幾種〔簡(jiǎn)單〕答：串的模式匹配是指子串的定位運(yùn)算，即在主串中查找子串第一次出現(xiàn)的位置。模式匹配算法有兩種：簡(jiǎn)單匹配算法(Brute-Force)、KMP算法?！苍擃}共4個(gè)得分點(diǎn)，答對(duì)串匹配定義或大意基本一樣，得2分；答對(duì)兩種匹配算，得2分，答錯(cuò)或少答一個(gè)扣1分〕第五章數(shù)組和廣義表在數(shù)據(jù)構(gòu)造中，數(shù)組是最基本的構(gòu)造，請(qǐng)完成以下要求：〔1〕、定義一個(gè)能容納5個(gè)整型元素的數(shù)組iAry，且元素的值為10、20、30、40、50?！?〕、*畫(huà)出數(shù)組iAry的順序存儲(chǔ)構(gòu)造?！惨?guī)定：整型長(zhǎng)度為兩個(gè)字節(jié)〕〔1〕、intiAry[5]={10、20、30、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)成的有限集合?！?個(gè)得分點(diǎn)〕特點(diǎn)：1〕數(shù)組中各元素具有統(tǒng)一的類(lèi)型；〔1個(gè)得分點(diǎn)〕2〕數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變?！?個(gè)得分點(diǎn)〕3數(shù)組的基本操作比較簡(jiǎn)單，除了構(gòu)造的初始化和銷(xiāo)毀之外，只有存取元素和修改元素值的操作?！?個(gè)得分點(diǎn)〕分類(lèi)：按維度可分為一維數(shù)組、二維數(shù)組、多維數(shù)組〔1個(gè)得分點(diǎn)〕一個(gè)二維數(shù)組A如下所示?！草^難〕〔1〕請(qǐng)按照行優(yōu)先、列優(yōu)先的方式進(jìn)展順序存儲(chǔ)，給出順序存儲(chǔ)的序列〔2個(gè)得分點(diǎn)〕行優(yōu)先：a11a12a13a21a22a23列優(yōu)先：a11a21a12a22a13a23〔2〕假設(shè)a11在內(nèi)存中存儲(chǔ)的地址為α，每個(gè)元素的存儲(chǔ)空間大小為L(zhǎng)，那么按照行優(yōu)先的方式和列優(yōu)先的方式分別存儲(chǔ)，其中a22的地址loc(a22)分別為多少〔2個(gè)得分點(diǎn)〕行優(yōu)先：loc(a22)=α+4L列優(yōu)先：loc(a22)=α+3L〔3〕對(duì)于數(shù)組，除了順序存儲(chǔ)外，還有沒(méi)有其他存儲(chǔ)方式?jīng)]有填無(wú)，假設(shè)有，請(qǐng)說(shuō)明。有，鏈?zhǔn)酱鎯?chǔ)，如以以下列圖所示〔1個(gè)得分點(diǎn)〕第六章樹(shù)和二叉樹(shù)有一樹(shù)，如以以下列圖所示：〔簡(jiǎn)單〕請(qǐng)答復(fù)以下問(wèn)題：〔1〕樹(shù)的葉子結(jié)點(diǎn)及其度?！?〕非終端結(jié)點(diǎn)及其度?！?〕樹(shù)的深度。答：〔1〕、葉子結(jié)點(diǎn)有：D、E、F、G，它們的度都為零?！?分〕〔2〕、非終端結(jié)點(diǎn)有：A度為3，B度為2，C度為1。〔2分〕〔3〕、樹(shù)的深度為3?！?分〕請(qǐng)答復(fù)：樹(shù)與二叉樹(shù)有什么區(qū)別〔中等〕答：區(qū)別有兩點(diǎn)：(1)二叉樹(shù)的一個(gè)結(jié)點(diǎn)至多有兩個(gè)子樹(shù)，樹(shù)那么不然?！?.5分〕(2)二叉樹(shù)一個(gè)結(jié)點(diǎn)的子樹(shù)有左右之分，而樹(shù)的子樹(shù)沒(méi)有次序?！?.5分〕有一棵具有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)。請(qǐng)問(wèn)：該滿二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)目是多少，并寫(xiě)出分析推理過(guò)程?！仓械取炒穑?n+1)/2?！?分〕分析過(guò)程：滿二叉樹(shù)中只有度為2和度為0的結(jié)點(diǎn)，故設(shè)葉子結(jié)點(diǎn)數(shù)目為：n0，度為2結(jié)點(diǎn)數(shù)目為：n2。又由于n0=n2+1，n=n2+n0，所以可得出：n0=(n+1)/2。〔3分〕有一棵二叉樹(shù)，如以以下列圖所示：〔簡(jiǎn)單〕請(qǐng)問(wèn)答以下問(wèn)題：〔1〕、用先序遍歷法遍歷該二叉樹(shù)，那么遍歷結(jié)果是什么〔2〕、用中序遍歷法遍歷該二叉樹(shù)，那么遍歷結(jié)果是什么〔3〕、用后序遍歷法遍歷該二叉樹(shù)，那么遍歷結(jié)果是什么答：〔1〕、ABDCEF〔2〕、DBAECF〔3〕、DBEFCA(錯(cuò)一個(gè)扣1.5分)請(qǐng)問(wèn)如下二叉樹(shù)，如果采用前序\中序\后序遍歷結(jié)果是什么〔中等〕前序:ABDECF;中序:DBEAFC;后序:DEBFCA;(錯(cuò)一個(gè)扣1.5分)有如下一顆樹(shù)其前序\中序\后序遍歷結(jié)果是什么?(中等)其前序遍歷結(jié)果是：ABDGCEF其中序遍歷結(jié)果是：DGBAECF其后序遍歷結(jié)果是：GDBEFCA(錯(cuò)一個(gè)扣1.5分)假定用于通信的電文由8個(gè)字符A、B、C、D、E、F、G、H組成，各字母在電文中出現(xiàn)概率為5％、25％、4％、7％、9％、12％、30％、8％?，F(xiàn)在把字符出現(xiàn)概率擴(kuò)大100倍后，作為這8個(gè)字母對(duì)應(yīng)的權(quán)值〔5，25，4，7，9，12，30，8〕。以這些權(quán)值構(gòu)成的霍夫曼樹(shù)，如以以下列圖所示：請(qǐng)問(wèn)答以下問(wèn)題：〔中等〕〔1〕、參考霍夫曼樹(shù)，給字符A、B、C、D、E、F、G、H進(jìn)展編碼?！矊?xiě)出這8個(gè)字符的霍夫曼編碼〕〔2〕、如果發(fā)送的電文信息為“HECDB〞，那么，發(fā)送的數(shù)據(jù)是什么?！不蛘哒f(shuō)發(fā)送的編碼序列是什么〕答：〔1〕、A:0011，B:01，C:0010， D:1010，E:000， F:100，G:11，H:1011〔3分〕〔2〕、10110000010101001〔2分〕請(qǐng)簡(jiǎn)述滿二叉樹(shù)、完全二叉樹(shù)的聯(lián)系。答：〔1〕、它們都是特殊的二叉樹(shù)，遵循著二叉樹(shù)的性質(zhì)?！?.5分〕〔2〕、滿二叉樹(shù)是指每一層結(jié)點(diǎn)數(shù)都到達(dá)了最大值，所有葉子結(jié)點(diǎn)均在最大層上；而完全二叉樹(shù)是遵循著滿二叉樹(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分〕度為3的節(jié)點(diǎn)有A,D;〔1.5分〕這顆樹(shù)的度為4,〔1分〕樹(shù)的深度是4.〔1分〕請(qǐng)畫(huà)出深度為4的滿二叉樹(shù)(較難)請(qǐng)畫(huà)出深度為4的完全二叉樹(shù)(較難)給定一組權(quán)值{6，2，3，9，6}根據(jù)哈夫曼算法構(gòu)造哈夫曼樹(shù).(難)將6、2、3、9、6看成是有5棵樹(shù)的森林(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn))；2)在森林中選出兩個(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ù)參加森林；3)在森林中選出兩個(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)值最小的6，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)值最小的11，15樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和26；從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)參加森林；第七章圖什么叫圖G的生成樹(shù)答：連通圖G的一個(gè)子圖如果是一棵包含G的所有頂點(diǎn)的樹(shù),那么該子圖稱(chēng)為G的生成樹(shù)。寫(xiě)出下面圖的鄰接矩陣答案用鄰接表表示以以下列圖的存儲(chǔ)構(gòu)造答案如下的有向圖=1\*GB3①每個(gè)頂點(diǎn)的入度和出度；=2\*GB3②鄰接矩陣；=3\*GB3③鄰接表；答案第八章查找什么是查找、靜態(tài)查找以及動(dòng)態(tài)查找并說(shuō)出關(guān)于靜態(tài)查找的幾種算法〔簡(jiǎn)單〕查找：給定一個(gè)值K，在含有n個(gè)記錄的文件中進(jìn)展搜索，尋找一個(gè)關(guān)鍵字值等于K的記錄，如找到那么輸出該記錄，否那么輸出查找不成功的信息?！?個(gè)得分點(diǎn)〕靜態(tài)查找：只查找，不改變集合內(nèi)的數(shù)據(jù)元素?！?.5個(gè)得分點(diǎn)〕動(dòng)態(tài)查找：既查找，又改變〔增減〕集合內(nèi)的數(shù)據(jù)元素〔0.5個(gè)得分點(diǎn)〕靜態(tài)查找的算法有：順序、二分、分塊查找〔3個(gè)得分點(diǎn)〕請(qǐng)答復(fù)出四種查找方法，以及對(duì)查找方法評(píng)價(jià)的標(biāo)準(zhǔn)是什么〔簡(jiǎn)單〕答：順序查找、二分查找〔折半查找法〕、索引查找、哈希表查找?！?分〕查找方法評(píng)價(jià)的標(biāo)準(zhǔn)是：平均查找長(zhǎng)度〔1分〕請(qǐng)答復(fù)出二分查找與順序查找各自的優(yōu)缺點(diǎn)〔簡(jiǎn)單〕1〕順序查找優(yōu)點(diǎn)：算法簡(jiǎn)單，且對(duì)順序構(gòu)造或鏈表構(gòu)造均適用?！?個(gè)得分點(diǎn)〕缺點(diǎn)：查找性能較低，平均查找長(zhǎng)度大〔1個(gè)得分點(diǎn)〕2〕二分查找1〕優(yōu)點(diǎn)：查找效率高，平均查找長(zhǎng)度小?！?個(gè)得分點(diǎn)〕2〕缺點(diǎn)：a.查找表需按關(guān)鍵字排序〔有序表〕?！?個(gè)得分點(diǎn)〕b.二分查找只適用順序存儲(chǔ)構(gòu)造。為保持表的有序性，在順序構(gòu)造里插入和刪除都必須移動(dòng)大量的結(jié)點(diǎn)?！?個(gè)得分點(diǎn)〕第九章排序有一組數(shù)據(jù){64,5,7,98,6,24},請(qǐng)列出直接選擇排序(升序)的過(guò)程.(難)初始序列 64 5 7 98 6 24第1次排序 [5] 64 7 98 6 24第2次排序 [5 6] 7 98 64 24第3次排序 [5 6 7] 98 64 24第4次排序 [5 6 7 24] 64 98第5次排序 [5 6 7 24 64] 98最終結(jié)果 [5 6 7 24 64 98]有一組數(shù)據(jù){64,5,7,98,6,24},請(qǐng)列出冒泡排序(升序)的過(guò)程.(難)初始序列 64 5 7 98 6 24第1次排序 5 7 64 6 24 [98]第2次排序 5 7 6 24 [64 98]第3次排序 5 6 7 [24 64 98]第4次排序 5 6 [7 24 64 98]第5次排序 5 [6 7 24 64 98]最終結(jié)果 [5 6 7 24 64 98]有一組數(shù)據(jù){64,5,7,98,6,24},請(qǐng)列出直接插入排序(升序)的過(guò)程.(難)初始序列 [64]5 7986 24第1次排序 [5 64]7986 24第2次排序 [57 64]986 24第3次排序 [57 6498]6 24第4次排序 [567 6498] 24第5次排序 [567 24 6498]有關(guān)鍵字序列〔16，15，18，16，17，18，20，13〕，現(xiàn)采用直接插入排序?qū)﹃P(guān)鍵字按遞增序排列，請(qǐng)畫(huà)出具體過(guò)程〔難〕初始序列 [16]，15，18，16，17，18，20，13第1次排序[15，16]，18，16，17，18，20，13第2次排序 [15，16，18]，16，17，18，20，13第3次排序 [15，16，16，18]，17，18，20，13第4次排序 [15，16，16，17，18]，18，20，13第5次排序 [15，16，16，17，18，18]，20，13第6次排序 [15，16，16，17，18，18，20]，13第7次排序 [13，15，16，16，17，18，18，20]有關(guān)鍵字序列〔16，15，18，16，17，18，20，13〕，現(xiàn)采用冒泡排序?qū)﹃P(guān)鍵字按遞增序排列，請(qǐng)畫(huà)出具體過(guò)程〔難〕初始序列 1615181617182013第1次排序15161617181813[20]第2次排序 151616171813[1820]第3次排序 1516161713[181820]第4次排序 15，16，16，13，[17，18，18，20]第5次排序 15，16，13，[16，17，18，18，20]第6次排序 15，13，[16，16，17，18，18，20]第7次排序 13，[15，16，16，17，18，18，20]有關(guān)鍵字序列〔16，15，18，16，17，18，20，13〕，現(xiàn)采用直接選擇排序?qū)﹃P(guān)鍵字按遞增序排列，請(qǐng)畫(huà)出具體過(guò)程〔難〕初始序列 16，15，18，16，17，18，20，13第1次排序[13]，15，18，16，17，18，20，16第2次排序[13，15]，18，16，17，18，20，16第3次排序[13，15，16]，18，17，18，20，16第4次排序[13，15，16，16]，17，18，20，18第5次排序[13，15，16，16，17]，18，20，18第6次排序[13，15，16，16，17，18]，20，18第7次排序[13，15，16，16，17，18，18]，20編程題第一章緒論第二章線性表某個(gè)班級(jí)的學(xué)生信息表如下表所示，請(qǐng)使用順序表構(gòu)造編程實(shí)現(xiàn)將學(xué)生信息〔120010101、楊三〕插入到表中第一條的位置。學(xué)號(hào)〔ID〕姓名(Name)120010102李華120010103王麗具體要求：編寫(xiě)代碼定義順序表構(gòu)造，完成該信息表已有數(shù)據(jù)的初始化工作，最后完成數(shù)據(jù)的插入。classStudent{//兩個(gè)得分點(diǎn)publicStringno; //學(xué)生學(xué)號(hào)publicStringname; //學(xué)生姓名 publicStudent(Stringno,Stringname){this.no=no; =name; }}publicclassLineList{ //LineList為線性表名intlength=35; //表長(zhǎng)度〔1個(gè)得分點(diǎn)〕Studentdata[]=newStudent[length];//順序表數(shù)組1個(gè)得分點(diǎn) intcurlen=0; //實(shí)際表長(zhǎng)〔1個(gè)得分點(diǎn)〕 //插入方法publicbooleaninsert(inti,Studentstu){ //插入位置正確與否判斷〔1個(gè)得分點(diǎn)〕if(i<1||i>this.curlen+1||this.curlen>=this.length){ returnfalse;} //從第i個(gè)位置開(kāi)場(chǎng)順序表所有結(jié)點(diǎn)均后移一個(gè)位置〔1個(gè)得分點(diǎn)〕 intn=this.curlen; for(;n>=i;n--) data[n]=data[n-1]; //插入新結(jié)點(diǎn)stu〔1個(gè)得分點(diǎn)〕 data[n]=stu; this.curlen++;〔1個(gè)得分點(diǎn)〕 returntrue; } publicstaticvoidmain(String[]args){ //初始化數(shù)據(jù)〔2個(gè)得分點(diǎn)〕 LineListlst=newLineList(); Studentstu1=newStudent("120010102","李華"); Studentstu2=newStudent("120010103","王麗");lst.data[0]=stu1;lst.data[1]=stu2; //進(jìn)展插入操作〔1個(gè)得分點(diǎn)〕 Studentstu3=newStudent("120010101","楊三"); lst.insert(1,stu3); }}評(píng)分標(biāo)準(zhǔn)：總共15個(gè)得分點(diǎn)，其中程序標(biāo)準(zhǔn)、語(yǔ)法〔3個(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)使用順序表構(gòu)造編程實(shí)現(xiàn)將圖書(shū)信息〔10101、鹿鼎記〕插入到表中第一條的位置。圖書(shū)號(hào)〔ID〕書(shū)名(Name)10102神雕俠侶10103鴛鴦刀具體要求：編寫(xiě)代碼定義順序表構(gòu)造，完成該信息表已有數(shù)據(jù)的初始化工作，最后完成數(shù)據(jù)的插入。classBook{//兩個(gè)得分點(diǎn)publicStringno; //圖書(shū)編號(hào)publicStringname; //圖書(shū)名稱(chēng) publicBook(Stringno,Stringname){this.no=no; =name; }}publicclassLineList{ //LineList為線性表名intlength=35; //表長(zhǎng)度〔1個(gè)得分點(diǎn)〕Bookdata[]=newBook[length];//順序表數(shù)組1個(gè)得分點(diǎn) intcurlen=0; //實(shí)際表長(zhǎng)〔1個(gè)得分點(diǎn)〕 //插入方法publicbooleaninsert(inti,Bookbook){ //插入位置正確與否判斷〔1個(gè)得分點(diǎn)〕if(i<1||i>this.curlen+1||this.curlen>=this.length){ returnfalse;} //從第i個(gè)位置開(kāi)場(chǎng)順序表所有結(jié)點(diǎn)均后移一個(gè)位置〔1個(gè)得分點(diǎn)〕 intn=this.curlen; for(;n>=i;n--) data[n]=data[n-1]; //插入新結(jié)點(diǎn)book〔1個(gè)得分點(diǎn)〕 data[n]=book; this.curlen++;〔1個(gè)得分點(diǎn)〕 returntrue; } publicstaticvoidmain(String[]args){ //初始化數(shù)據(jù)〔2個(gè)得分點(diǎn)〕 LineListlst=newLineList(); Bookbook1=newBook("10102","神雕俠侶"); Bookbook2=newBook("10103","鴛鴦刀");lst.data[0]=book1;lst.data[1]=book2; //進(jìn)展插入操作〔1個(gè)得分點(diǎn)〕 Bookbook3=newBook("10101","鹿鼎記"); lst.insert(1,book3); }}評(píng)分標(biāo)準(zhǔn)：總共15個(gè)得分點(diǎn)，其中程序標(biāo)準(zhǔn)、語(yǔ)法〔3個(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)使用順序表構(gòu)造編程實(shí)現(xiàn)將課程信息〔10101、數(shù)據(jù)構(gòu)造〕插入到表中第一條的位置。課程號(hào)〔ID〕課程名(Name)10102軟件工程10103UML具體要求：編寫(xiě)代碼定義順序表構(gòu)造，完成該信息表已有數(shù)據(jù)的初始化工作，最后完成數(shù)據(jù)的插入。classLession{//兩個(gè)得分點(diǎn)publicStringno; //課程編號(hào)publicStringname; //課程名稱(chēng) publicLession(Stringno,Stringname){this.no=no; =name; }}publicclassLineList{ //LineList為線性表名intlength=35; //表長(zhǎng)度〔1個(gè)得分點(diǎn)〕Lessiondata[]=newLession[length];//順序表數(shù)組1個(gè)得分點(diǎn) intcurlen=0; //實(shí)際表長(zhǎng)〔1個(gè)得分點(diǎn)〕 //插入方法publicbooleaninsert(inti,Lessionlession){ //插入位置正確與否判斷〔1個(gè)得分點(diǎn)〕if(i<1||i>this.curlen+1||this.curlen>=this.length){ returnfalse;} //從第i個(gè)位置開(kāi)場(chǎng)順序表所有結(jié)點(diǎn)均后移一個(gè)位置〔1個(gè)得分點(diǎn)〕 intn=this.curlen; for(;n>=i;n--) data[n]=data[n-1]; //插入新結(jié)點(diǎn)lession〔1個(gè)得分點(diǎn)〕 data[n]=lession; this.curlen++;〔1個(gè)得分點(diǎn)〕 returntrue; } publicstaticvoidmain(String[]args){ //初始化數(shù)據(jù)〔2個(gè)得分點(diǎn)〕 LineListlst=newLineList(); Lessionlession1=newLession("10102","軟件工程"); Lessionlession2=newLession("10103","UML");lst.data[0]=lession1;lst.data[1]=lession2; //進(jìn)展插入操作〔1個(gè)得分點(diǎn)〕 Lessionlession3=newLession("10101","數(shù)據(jù)構(gòu)造"); lst.insert(1,lession3); }}評(píng)分標(biāo)準(zhǔn)：總共15個(gè)得分點(diǎn)，其中程序標(biāo)準(zhǔn)、語(yǔ)法〔3個(gè)得分點(diǎn)，語(yǔ)法有問(wèn)題但不影響程序邏輯，按0.5得分點(diǎn)每一處扣分，扣完為止〕，程序邏輯12個(gè)得分點(diǎn)〔按照程序代碼各處標(biāo)注分?jǐn)?shù)進(jìn)展打分〕某個(gè)班級(jí)的學(xué)生信息表如下表所示，請(qǐng)使用順序表構(gòu)造編程實(shí)現(xiàn)將表中第一條學(xué)生信息刪除。學(xué)號(hào)〔ID〕姓名(Name)120010101楊三120010102李華具體要求：編寫(xiě)代碼定義順序表構(gòu)造，完成該信息表已有數(shù)據(jù)的初始化工作，最后完成數(shù)據(jù)的刪除。classStudent{//2個(gè)得分點(diǎn)publicStringno; //學(xué)生學(xué)號(hào)publicStringname; //學(xué)生姓名 publicStudent(Stringno,Stringname){this.no=no; =name; }}publicclassLineList{ //LineList為線性表名intlength=35; //表長(zhǎng)度〔1個(gè)得分點(diǎn)〕Studentdata[]=newStudent[length];//順序表數(shù)組1個(gè)得分點(diǎn) intcurlen=0; //實(shí)際表長(zhǎng)〔1個(gè)得分點(diǎn)〕 //刪除方法 publicStudentdelete(inti){ //刪除位置正確與否判斷〔1個(gè)得分點(diǎn)〕 if(i<1||i>this.curlen){ System.out.println("刪除位置有誤！"); returnnull; } //保存刪除前第i個(gè)數(shù)據(jù)元素〔這行代碼可有可無(wú)，不計(jì)分〕 Studentstu=this.data[i-1]; //從第i+1個(gè)位置開(kāi)場(chǎng)依次向前移一個(gè)位置〔1個(gè)得分點(diǎn)〕 for(intn=i;n<this.curlen;n++){ data[n-1]=data[n]; } data[this.curlen-1]=null;//〔1個(gè)得分點(diǎn)〕 this.curlen--;//〔1個(gè)得分點(diǎn)〕 returnstu; } publicstaticvoidmain(String[]args){ //初始化數(shù)據(jù)〔2個(gè)得分點(diǎn)〕 LineListlst=newLineList(); Studentstu1=newStudent("120010101","楊三"); Studentstu2=newStudent("120010102","李華");lst.data[0]=stu1;lst.data[1]=stu2; //進(jìn)展刪除操作〔1個(gè)得分點(diǎn)〕 lst.delete(1); }}評(píng)分標(biāo)準(zhǔn)：總共15個(gè)得分點(diǎn)，其中程序標(biāo)準(zhǔn)、語(yǔ)法〔3個(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)使用順序表構(gòu)造編程實(shí)現(xiàn)將表中第一條圖