《數(shù)據(jù)結(jié)構(gòu)》

1、數(shù)據(jù)結(jié)構(gòu)課程的性質(zhì)與設(shè)置目的一 數(shù)據(jù)結(jié)構(gòu)課程的性質(zhì)和特點(diǎn)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)軟件專(zhuān)業(yè)的一門(mén)重點(diǎn)基礎(chǔ)課，是學(xué)生進(jìn)一步學(xué)習(xí)后繼課程的必要的基礎(chǔ)知識(shí)，是從事軟件設(shè)計(jì)專(zhuān)業(yè)人員的技能訓(xùn)練素材。計(jì)算機(jī)各個(gè)領(lǐng)域以及有關(guān)專(zhuān)業(yè)都要使用本課程的數(shù)據(jù)結(jié)構(gòu)、算法和相關(guān)結(jié)論。例如：語(yǔ)言編譯要使用棧、散列表和語(yǔ)法樹(shù)；操作系統(tǒng)要使用隊(duì)列、棧、存儲(chǔ)管理和目錄樹(shù)；數(shù)據(jù)庫(kù)管理系統(tǒng)要使用線(xiàn)性表、多鏈表、排序、查找和索引樹(shù)；人工智能要使用集合、廣義表、搜索樹(shù)和有向圖等。數(shù)據(jù)結(jié)構(gòu)課程在學(xué)生的知識(shí)學(xué)習(xí)和技能培養(yǎng)兩個(gè)方面都處于關(guān)鍵性的位置。二 數(shù)據(jù)結(jié)構(gòu)課程的目標(biāo)1 知識(shí)方面：從抽象的邏輯結(jié)構(gòu)到存儲(chǔ)結(jié)構(gòu)在機(jī)內(nèi)實(shí)現(xiàn)兩個(gè)層次上，系統(tǒng)的學(xué)習(xí)和掌握常用

2、的數(shù)據(jù)結(jié)構(gòu)，線(xiàn)性表、棧、隊(duì)列、數(shù)組、二叉樹(shù)、線(xiàn)索樹(shù)、圖、查找表、散列表和文件等數(shù)據(jù)結(jié)構(gòu)及其存儲(chǔ)方法的不同實(shí)現(xiàn)。鍛煉和提高學(xué)生的抽象思維能力，為后繼課程積累必要的基礎(chǔ)知識(shí)。2 技能方面：系統(tǒng)地、抽象地學(xué)習(xí)總結(jié)出各種數(shù)據(jù)結(jié)構(gòu)下的基本算法，通過(guò)對(duì)算法的描述、各種實(shí)現(xiàn)方法以及對(duì)比、算法復(fù)雜度分析等，提高學(xué)生分析問(wèn)題、解決問(wèn)題的能力；提高學(xué)生選擇數(shù)據(jù)結(jié)構(gòu)和算法的思維技巧；鍛煉和實(shí)踐學(xué)生編寫(xiě)軟件的基本技能。三 課程要求：1 從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)算三個(gè)方面去掌握線(xiàn)性表、棧、隊(duì)列、串、數(shù)組、樹(shù)、圖、和文件等常用的數(shù)據(jù)結(jié)構(gòu)。2 掌握在各種常用的數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)的排序和查找運(yùn)算。3 對(duì)算法的時(shí)間和

3、空間復(fù)雜度有一定的分析能力。4 針對(duì)簡(jiǎn)單的實(shí)際應(yīng)用問(wèn)題，應(yīng)能選擇合適的數(shù)據(jù)結(jié)構(gòu)以及有效地算法解決之。5 課程本身要求學(xué)生有抽象性思維、數(shù)理邏輯演繹、高級(jí)語(yǔ)言的數(shù)據(jù)類(lèi)型定義、算法設(shè)計(jì)和必要的數(shù)學(xué)、英語(yǔ)基礎(chǔ)。四 相關(guān)課程的聯(lián)系1 前導(dǎo)課程：高等數(shù)學(xué)、C或C+語(yǔ)言、大學(xué)英語(yǔ)等。2 后繼課程：數(shù)據(jù)庫(kù)原理、操作系統(tǒng)等相關(guān)課程。 第一章 概 論一. 基本要求重點(diǎn)、難點(diǎn)對(duì)本章的學(xué)習(xí)，主要是要熟悉各名詞和術(shù)語(yǔ)的含義；掌握各種基本概念，特別是數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)運(yùn)算3方面的內(nèi)容及這3方面的相互關(guān)系；熟悉C語(yǔ)言的書(shū)寫(xiě)規(guī)范，理解算法的5個(gè)要素的確切含義，即有窮性、確定性、可行性及有輸入、有輸出，從而掌

4、握計(jì)算語(yǔ)句頻度和估計(jì)算法時(shí)間復(fù)雜度的方法等，為學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)打下基礎(chǔ)。二. 考核目標(biāo)和考核要求要求達(dá)到識(shí)記層次的有：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)等的基本概念；數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)運(yùn)算的含義及其相互關(guān)系；數(shù)據(jù)結(jié)構(gòu)的兩大邏輯結(jié)構(gòu)和四種常用的存儲(chǔ)表示方法；數(shù)據(jù)結(jié)構(gòu)在各種軟件系統(tǒng)中所起的作用；選擇合適的數(shù)據(jù)結(jié)構(gòu)是解決應(yīng)用問(wèn)題的關(guān)鍵步驟。要求達(dá)到理解層次有：算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度、最壞情況下的時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度等概念；算法的時(shí)間復(fù)雜度不僅僅依賴(lài)于問(wèn)題的規(guī)模，也取決于輸入實(shí)例的初始狀態(tài)；算法描述和算法分析的方法，對(duì)于一般算法能力分析出時(shí)間復(fù)雜度。要求達(dá)到簡(jiǎn)單應(yīng)用的有：時(shí)

5、間復(fù)雜度的算法三. 練習(xí)題1. 單項(xiàng)選擇題1.1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）A） 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)B） 線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)C） 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D） 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)1.2線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種（ ）的存儲(chǔ)結(jié)構(gòu)A） 順序存取B） 索引存取C） 隨機(jī)存取D） 散列存取1.3邏輯關(guān)系是指數(shù)據(jù)元素的（ ）A） 關(guān)聯(lián)B） 存儲(chǔ)方式C） 結(jié)構(gòu)D） 數(shù)據(jù)項(xiàng)1.4下列時(shí)間復(fù)雜度中最壞的是（ ）A） O（1）B） O（n）C） O（log2n）D） O（n2）1.5下列時(shí)間復(fù)雜度最好的是（ ）A） O（1）B） O（n）C） O（log2n）D） O（n2）1.6下列算法是時(shí)間

6、復(fù)雜度是（ ） for(i=0;in;i+) for(j=0;jn;j+) cij=i+j;A） O（1）B） O（n）C） O（log2n）D） O（n2）1.7算法分析的兩個(gè)主要方面是（ ）A） 正確性和簡(jiǎn)明性B） 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C） 可讀性和可維護(hù)性D） 時(shí)間復(fù)雜性和空間復(fù)雜性1.8線(xiàn)性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元地址（ ）A） 不一定連續(xù)的B） 部分地址必須是連續(xù)的C） 必須是連續(xù)的D） 一定是不連續(xù)的1.9算法指的是（ ）A） 計(jì)算機(jī)程序B） 解決問(wèn)題的計(jì)算方法C） 排序算法D） 解決問(wèn)題的有限運(yùn)算序列1.10數(shù)據(jù)的基本單位是（ ）A） 文件B） 數(shù)據(jù)元

7、素C） 符號(hào)D） 關(guān)鍵字2. 填空題2.1數(shù)據(jù)結(jié)構(gòu)一般包括 、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)算三個(gè)方面的內(nèi)容。2.2從數(shù)據(jù)結(jié)構(gòu)S中找出滿(mǎn)足條件的結(jié)點(diǎn)在S中的位置的運(yùn)算是 2.3從數(shù)據(jù)結(jié)構(gòu)S中讀出結(jié)構(gòu)中指定位置上的內(nèi)容的運(yùn)算是 2.4從數(shù)據(jù)結(jié)構(gòu)S中的某指定位置上增加一個(gè)結(jié)點(diǎn)的運(yùn)算是 2.5從數(shù)據(jù)結(jié)構(gòu)S中撤消結(jié)構(gòu)中指定位置上結(jié)點(diǎn)的運(yùn)算是 2.6從數(shù)據(jù)結(jié)構(gòu)S中修改結(jié)構(gòu)中某指定結(jié)點(diǎn)內(nèi)容的運(yùn)算是 2.7數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）可以用順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、 及散列存儲(chǔ)等四種存儲(chǔ)方法表示。2.8選用算法除了首先考慮“正確性”外，主要考慮 、執(zhí)行算法所需要的存儲(chǔ)空間、算法易于理解，易于編程，易于調(diào)試2.9數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)

8、的物理結(jié)構(gòu)和 以及它們之間的相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算2.10數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。3. 簡(jiǎn)答題3.1簡(jiǎn)述數(shù)據(jù)與數(shù)據(jù)元素的關(guān)系與區(qū)別3.2簡(jiǎn)述數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類(lèi)型、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、線(xiàn)性結(jié)構(gòu)、非線(xiàn)性結(jié)構(gòu)的概念3.3簡(jiǎn)述順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在表示數(shù)據(jù)元素之間關(guān)系上的主要區(qū)別3.4通常從哪幾個(gè)方面評(píng)價(jià)算法的質(zhì)量4. 應(yīng)用題4.1求下述算法的時(shí)間復(fù)雜度f(wàn)or(i=1;i=n;i+) y=y+1; for(j=1;j=2*n;j+) x=x+1;4.2求下述算法的時(shí)間復(fù)雜度x=1;sum=0;for(i=1;inext=head

9、C） head-next=NULLD） head=NULL1.3對(duì)順序存儲(chǔ)的線(xiàn)性表，設(shè)其長(zhǎng)度為n，在任何位置上刪除操作都是等概率的。刪除一個(gè)元素時(shí)大約要移動(dòng)表中元素的個(gè)數(shù)是（ ）A） n/2B） （n+1）/2C） n-1D） （n-1）/21.4鏈表不具有的特點(diǎn)是（ ）A） 可隨機(jī)訪(fǎng)問(wèn)任一元素B） 插入刪除不需要移動(dòng)元素C） 不必事先估計(jì)存儲(chǔ)空間D） 所需空間與線(xiàn)性表長(zhǎng)度成正比1.5 L是線(xiàn)性表，已知Length（L）的值是5，經(jīng)運(yùn)算Delete（L，2），后Length（L）的值是（ ）A） 5B） 0C） 4D） 61.6在一個(gè)單鏈表中，若刪除p指向結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行的操作為（ ）A

10、） q=p-next；p-next=p-next-next；dispose（q）；B） p=p-next；q=p-next；p=q-next；dispose（q）；C） q=p-next-next；p=p-next；dispose（q）；A） p=p-next-next；q=p-next；dispose（q）；1.7在線(xiàn)性表中，哪些元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼（ ）A） 首元素B） 尾元素C） 中間的元素D） 所有的元素1.8在單循環(huán)鏈表中，已知q指向p指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q，p所指結(jié)點(diǎn)之間插入一個(gè)s所指向的新結(jié)點(diǎn)，則執(zhí)行的操作是（ ）A）q-next=s，s-next=p；B）p-

11、next=s；s-next=q；C）s-next=p-next；p-next=s；D）p-next=s-next；s-next=p；2 填空題2.1在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素之前插入一個(gè)元素時(shí)，需要后移 個(gè)元素2.2在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素需要向前移動(dòng) 個(gè)元素2.3順序表中邏輯相鄰的元素，在物理位置上 2.4在用p指針訪(fǎng)問(wèn)單鏈表時(shí)，判斷表沒(méi)有訪(fǎng)問(wèn)結(jié)束的條件是 2.5線(xiàn)性表a的元素長(zhǎng)度為L(zhǎng)，在順序存儲(chǔ)結(jié)構(gòu)下Loc（ai）=Loc（a1）+ 2.6在單鏈表中除首結(jié)點(diǎn)外，任意結(jié)點(diǎn)的存儲(chǔ)位置都由 結(jié)點(diǎn)中的指針表示2.7在單鏈表中，設(shè)置表頭結(jié)點(diǎn)的作用是插入或刪除首結(jié)點(diǎn)時(shí)不必對(duì) 進(jìn)行

12、處理2.8循環(huán)鏈表S是空表的條件是 2.9雙向鏈表S是空表的條件是 3 簡(jiǎn)答題3.1線(xiàn)性表有兩種存儲(chǔ)結(jié)構(gòu)，即順序表和鏈表，這兩種存儲(chǔ)表示各有什么優(yōu)缺點(diǎn)？3.2在鏈表結(jié)構(gòu)中，頭結(jié)點(diǎn)與開(kāi)始結(jié)點(diǎn)有什么區(qū)別？3.3哪些鏈表從尾指針出發(fā)可以訪(fǎng)問(wèn)到鏈表中的任意位置？4 算法設(shè)計(jì)4.1在順序表中第i個(gè)位置上插入元素xvoid InsertList(SeqList *L,DataType x,int i) /將新結(jié)點(diǎn)x插入L所指的順序表的第i個(gè)結(jié)點(diǎn)ai的位置上 int j; if(iL-length+1) Error(“position error”); /非法位置，退出運(yùn)行 if(L-length=List

13、Size) Error(“overflow”); /表空間溢出，退出運(yùn)行 for(_;j=i-1;j-) L-dataj+1=_； L-datai-1=x; L-length+;4.2將順序表中位置為i的元素刪除void DeleteList(SeqList *L,int i) /從L所指的順序表中刪除第i個(gè)結(jié)點(diǎn)ai int j; if(iL-length) Error(“position error”);/非法位置 for（j=i;_;j+） L-dataj-1=_;L-length-; /表長(zhǎng)減小4.3頭插法建立單鏈表LinkList CreateListF(void)/返回單鏈表的頭指針

14、 char ch; LinkList head; /頭指針 ListNode *s; /工作指針 head=NULL; /鏈表開(kāi)始為空 ch=getchar( ); /讀第一個(gè)字符 while(ch!=n) s=_; s-data=ch; /將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中 s-next=_; head=s; ch=getchar( ); /讀入下一個(gè)字符 return head; /返回頭指針4.4尾插法建立單鏈表LinkList CreateListR(void) char ch; LinkList head; ListNode *s,*r; head=NULL;r=NULL; /鏈表初值

15、為空，尾指針初值為空 while(ch=getchar( )!=n) s=(ListNode *)malloc(sizeof(ListNode); s-data=ch; if(head=NULL) _； else _； r=s； if(r!=NULL) r-next=NULL； /對(duì)于非空表，將尾結(jié)點(diǎn)指針域置空 return head；4.5在鏈表中查找序號(hào)為i的結(jié)點(diǎn)ListNode * GetNode(LinkList head,int i)/在帶頭結(jié)點(diǎn)的單鏈表head中查找第i個(gè)結(jié)點(diǎn)，若找到（0in），則返回該結(jié)點(diǎn)的存儲(chǔ)位置，否則返回NULLint j；ListNode *p；p=head

16、；j=0； /從頭結(jié)點(diǎn)開(kāi)始掃描while(_) /順指針向后掃描，直到p-next為NULL或j=i為止 p=_； j+；if(i=j) return p； /找到了第i個(gè)結(jié)點(diǎn)else return NULL； /當(dāng)in時(shí)，找不到第i個(gè)結(jié)點(diǎn)4.6將值為x的結(jié)點(diǎn)插入到單鏈表的第i個(gè)位置上void InsertList(LinkList head,DataType x,int i)/將值為x的新結(jié)點(diǎn)插入到帶頭結(jié)點(diǎn)的單鏈表head的第i個(gè)結(jié)點(diǎn)的位置上ListNode *p；p=_；/尋找第i-1個(gè)結(jié)點(diǎn)if(p=NULL) Error(“position error”)； /in+1時(shí)插入位置i有錯(cuò)s

17、=(ListNode *)malloc(sizeof(ListNode);s-data=x;s-next=_；p-next=s;4.7刪除單鏈表中的第i個(gè)結(jié)點(diǎn)void DeleteList(LinkList head,int i)/刪去帶頭結(jié)點(diǎn)的單鏈表head上的第i個(gè)結(jié)點(diǎn)ListNode *p， *r；p=GetNode(head, i-1)； /找第i-1個(gè)結(jié)點(diǎn)if(p=NULL|p-next=NULL) /in時(shí)刪除位置有錯(cuò) Error (“position error”)； /退出程序運(yùn)行r=_；p-next=_；free(r)； /釋放結(jié)點(diǎn)所占用的空間第三章 棧和隊(duì)列一. 基本要求、

18、重點(diǎn)、難點(diǎn)本章的目的是介紹棧和隊(duì)列的邏輯結(jié)構(gòu)定義及在兩種存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)棧和隊(duì)列的基本運(yùn)算。要求在掌握棧和隊(duì)列的特點(diǎn)的基礎(chǔ)上，懂得在什么樣的情況下能夠使用?；蜿?duì)列。本章重點(diǎn)是掌握棧和隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算，難點(diǎn)是循環(huán)隊(duì)列中對(duì)邊界條件的處理。二. 考核目標(biāo)和考核要求要求達(dá)到識(shí)記層次的有：棧和隊(duì)列的特點(diǎn)，什么樣的情況下能夠使用棧或隊(duì)列要達(dá)到綜合應(yīng)用層次的有：棧的邏輯結(jié)構(gòu)特點(diǎn)，棧與線(xiàn)性表的異同；順序棧和鏈棧上實(shí)現(xiàn)的進(jìn)棧、退棧等基本算法；棧的“上溢”和“下溢”的概念及其判別條件；利用棧設(shè)計(jì)算法解決簡(jiǎn)單的應(yīng)用問(wèn)題；隊(duì)列的邏輯結(jié)構(gòu)特點(diǎn)，隊(duì)列與線(xiàn)性表的異同；順序隊(duì)列（主要是循環(huán)隊(duì)列）和鏈隊(duì)列上

19、實(shí)現(xiàn)的入隊(duì)、出隊(duì)等基本算法；隊(duì)列的“上溢”和“下溢”的概念及其判別條件；使用數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列取代普通的順序隊(duì)列的原因；循環(huán)隊(duì)列中對(duì)邊界條件的處理方法；利用隊(duì)列設(shè)計(jì)算法解決簡(jiǎn)單的應(yīng)用問(wèn)題。三. 練習(xí)題1. 單項(xiàng)選擇題1.1棧是一種受限的線(xiàn)性表，它的特點(diǎn)是（ ）A） 先進(jìn)先出B） 后進(jìn)先出C） 進(jìn)優(yōu)于出D） 隨機(jī)進(jìn)出1.2設(shè)一個(gè)棧的輸入序列為a，b，c,d，則所得出棧的輸出序列不可能是（ ）A） a,b,c,dB） d,a,b,cC） a,c,d,bD） d,c,b,a1.3由兩個(gè)棧共享受1個(gè)向量空間的好處是（ ）A） 減少存取時(shí)間，降低下溢發(fā)生的幾率B） 節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的幾率C）

20、減少存取時(shí)間，降低上溢發(fā)生的幾率D） 節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的幾率1.4設(shè)有一個(gè)空棧，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過(guò)pusu,push,pop,push,pop,pop,push,push,pop后輸出序列是（ ） A）2，3，4，5B）5，1，3，4C）2，3，1，5D）3，1，4，21.5判斷一個(gè)順序表st（最多元素為StackSize）為棧滿(mǎn)的條件是（ ）A） st.top！= StackSizeB） st.top！=0C） st.top=-1D） st.top= StackSize-11.6一個(gè)隊(duì)列的入隊(duì)序列是1，3，5，7，9，則出隊(duì)的輸出序列只能是（ ）A）9，7，5，

21、3，1B）1，3，5，7，9C）1，5，9，3，7D）9，5，1，7，31.7判斷一個(gè)順序隊(duì)列sq（最多元素為QueueSize）為空隊(duì)列的條件是（ ）A） sq.rear=cq.frontB） sq.rear=0C） sq.front= QueueSizeD） sq.rear= QueueSize+11.8判斷一個(gè)循環(huán)隊(duì)列cq（最多元素為QueueSize）為滿(mǎn)隊(duì)列的條件是（ ）A） cq.rear=cq.frontB） cq.rear= QueueSizeC） （cq.rear+1）% QueueSize=cq.frontD） cq.rear% QueueSize+1=cq.front1.

22、9隊(duì)列中的元素個(gè)數(shù)是（ ）A） 不變的B） 可變的C） 任意的D） 01.10同一隊(duì)列內(nèi)各元素的類(lèi)型（ ）A） 必須一致B） 可以不一致C） 不能一致D） 不限制1.11循環(huán)隊(duì)列占用的空間（ ）A） 必須連續(xù)B） 可以不連續(xù)C） 不能連續(xù)D） 不必連續(xù)1.12容量是10的循環(huán)隊(duì)的頭指針的位置Sq.front為2，則隊(duì)的頭元素的位置是（ ）A） 2B） 3C） 1D） 01.13初始化一個(gè)空間大小為5的順序棧Ss后，Ss-top的值（ ）A） 是-1B） 不定C） 不再改變D） 動(dòng)態(tài)變化1.14經(jīng)過(guò)下列棧的運(yùn)算后StackTop（s）的值是（ ） InitStack(s);Push(s,a);P

23、ush(s,b),Pop(s);A） aB） bC） 1D） 21.15經(jīng)過(guò)下列棧的運(yùn)算后*x的值是（ ）InitStack(s);Push(s,a);Push(s,b),StackTop(s);Pop(s,x);A） aB） bC） 1D） 21.16一個(gè)循環(huán)隊(duì)列一旦說(shuō)明，其占用空間的大?。?）A） 已固定B） 可以改變C） 不能固定D） 動(dòng)態(tài)變化1.17隊(duì)列結(jié)構(gòu)屬于下列結(jié)構(gòu)中的（ ）A） 集合B） 線(xiàn)性C） 樹(shù)型D） 網(wǎng)狀1.18設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front的值為（ ）A） front=front+

24、1B） front=（front+1）%（m-1）C） front=（front-1）%mD） front=（front+1）%m1.19存放循環(huán)隊(duì)列元素的數(shù)組data有10元素，則data數(shù)組的下標(biāo)范圍是（ ）A） 010B） 09C） 110D） 191.20存放循環(huán)隊(duì)列Sq元素的數(shù)組data有10個(gè)元素，Sq-front為9，隊(duì)列的頭元素的位置在（ ）A） 9B） 0C） 1D） 102. 填空題2.1棧又稱(chēng)后進(jìn)先出表，隊(duì)列又稱(chēng)為 表2.2設(shè)Smaxsize為一個(gè)順序存儲(chǔ)的棧，變量Top指向棧頂位置，棧為空的條件是 2.3設(shè)Smaxsize為一個(gè)順序存儲(chǔ)的棧，變量Top指向棧頂位置，棧為

25、滿(mǎn)的條件是 2.4對(duì)棧進(jìn)行入棧操作時(shí)，應(yīng)先判別棧是否為 2.5對(duì)棧進(jìn)行退棧操作時(shí)，應(yīng)先判別棧是否為 2.6已知一個(gè)棧的輸入序列為1，2，3，n，則其輸出序列的第2個(gè)元素為n的輸出序列的個(gè)數(shù)是 2.7設(shè)sqmaxsize為一個(gè)順序存儲(chǔ)的棧，變量top（為負(fù)數(shù)時(shí)棧為空）指示棧頂元素的位置，能做入棧操作的條件是 2.8設(shè)sqmaxsize為一個(gè)順序存儲(chǔ)的棧，變量top（為負(fù)數(shù)時(shí)棧為空）指示棧頂元素的位置，如要把棧頂元素彈出并送到x中，則需執(zhí)行下列語(yǔ)句： 2.9元素進(jìn)入隊(duì)列的那端是 2.10對(duì)鏈棧ls，指向棧頂元素的指針是 2.11鏈棧ls是空棧的條件是 2.12鏈棧ls的棧頂元素是鏈表的 元素2.1

26、3棧s經(jīng)過(guò)運(yùn)算InitStack(s);Push(s,a);Push(s,b)后StackTop（S）的值是 2.14已知循環(huán)隊(duì)列sq，在進(jìn)行出隊(duì)操作之前首先要判斷 2.15循環(huán)隊(duì)列sq存儲(chǔ)在數(shù)組sq.data0max中，sq.front為i，則存放隊(duì)列頭元素的數(shù)組元素是 2.16循環(huán)隊(duì)列sq存儲(chǔ)在數(shù)組sq.data0max中，sq.rear為0，則存放隊(duì)列尾元素的數(shù)組元素是 2.17循環(huán)隊(duì)列sq存儲(chǔ)在數(shù)組sq.data0max中，則sq中最多能存放 個(gè)隊(duì)列元素2.18在鏈隊(duì)列l(wèi)q中，鏈隊(duì)的尾元素是鏈表的 元素2.19循環(huán)隊(duì)列sq經(jīng)過(guò)運(yùn)算InitQueue(sq),sq.front= 2.20

27、循環(huán)隊(duì)列sq經(jīng)過(guò)運(yùn)算InitQueue(sq),sq.rear= 3. 簡(jiǎn)答題3.1在棧的順序存儲(chǔ)結(jié)構(gòu)下，進(jìn)棧（向棧中插入元素）的操作步驟是什么（用什么語(yǔ)言描述）？退棧（從棧中刪除元素）的操作步驟是哪些？3.2有循環(huán)隊(duì)列cq（最大長(zhǎng)度QueueSize，rear和front分別為隊(duì)尾和隊(duì)首指針）使用C語(yǔ)言表示的入隊(duì)、出隊(duì)操作時(shí)隊(duì)首、隊(duì)尾指針移動(dòng)語(yǔ)句。3.3如果編號(hào)為1，2，3的三輛列車(chē)進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，那么可能得到的三輛列車(chē)出站序列有哪些？不可能出現(xiàn)的序列是什么？3.4對(duì)于隊(duì)列來(lái)說(shuō)，出隊(duì)操作和取隊(duì)頭有什么區(qū)別？3.5簡(jiǎn)述下面給出的算法的功能是什么？（假設(shè)棧元素為整數(shù)類(lèi)型） void ex

28、31(SeqStack *s) int A80,i,n; n=0; while(!empty(S) An=pop(s); n+; for(i=0;in;i+) push(S,Ai);3.6簡(jiǎn)述下面給出的算法的功能是什么？（假設(shè)棧元素為整數(shù)類(lèi)型） void ex32(SeqStack *s,int c) SeqStack T; int d; while(!StackEmpty(S) d=pop(S); if(d!=c) push(T,d); while(!StackEmpty(T) d=pop(T); push(S,d);3.7設(shè)長(zhǎng)度為n的鏈隊(duì)列用循環(huán)鏈表表示，若只設(shè)頭指針則入隊(duì)操作的時(shí)間復(fù)雜度

29、是多少？若只設(shè)尾指針呢？3.8簡(jiǎn)述棧的特點(diǎn)及與一般線(xiàn)性表的區(qū)別？3.9簡(jiǎn)述隊(duì)列的特點(diǎn)及與一般線(xiàn)性表的區(qū)別？3.10比較棧和隊(duì)列的相同點(diǎn)與不同點(diǎn)3.11寫(xiě)出下列程序段的輸出結(jié)果main()Stack S; char x,y; InitStack(S); x=c;y=k; Push(S,x);Push(S,a); Push(S,y);Pop(S,x); Push(S,t);Push(S,x); Pop(S,x);Push(S,s); while(!StackEmpty(S) Pop(S,y); printf(y); ; printf(x); 3.12簡(jiǎn)述下列算法的功能algo(Stack S)in

30、t i,n,a255; n=0; while(!StackEmpty(s)n+;Pop(S,An); for(i=1;itop=-1;int StackEmpty(SeqStack *S) return S-top=1;int StackFull(SeqStack *S) return S-top=StackSize-1;void Push(SeqStack *S, DataType x)if(StackFull(S)Error(“Stack overflow”);/上溢，退出運(yùn)行 _;/棧頂指針加1后將x進(jìn)棧 DataType Pop(SeqStack *s)if(StackEmpty(S)

31、Error(“Stack underflow”);/下溢，退出運(yùn)行 return S-dataS-top-;/棧頂元素返回后將棧頂指針減1 DataType StackTop(SeqStack *s) if(StackEmpty(S) Error(“Stack is empty”); return _;4.2循環(huán)隊(duì)列基本算法 #define QueueSize 100 typedef char DataType /DataType的類(lèi)型依賴(lài)于具體應(yīng)用 typedef Sturet int front; /頭指針，隊(duì)非空時(shí)指向隊(duì)頭元素 int rear; /尾指針，隊(duì)非空時(shí)指向隊(duì)尾元素的下一位置

32、 int count; /計(jì)數(shù)器，記錄隊(duì)中元素總數(shù) DataType dataQueueSize CirQueue; void InitQueue(CirQueue *Q) Q-count=0; Q-count=0; /計(jì)數(shù)器置0int QueueEmpty(CirQueue *Q) return Q-count=0; /隊(duì)列無(wú)元素為空int QueueFull(CirQueue *Q) return Q-count=QueueSize; /隊(duì)中元素個(gè)數(shù)等于QueueSize時(shí)隊(duì)滿(mǎn)void EnQueue(CirQueue *Q, DataType x) if(QueueFull(Q) Err

33、or(“Queue overflow”);/隊(duì)滿(mǎn)上溢 Q-count+; /隊(duì)列元素個(gè)數(shù)加1 Q-dataQ-rear=x; /新元素插入隊(duì)尾 _; DataType DeQueue(CirQueue *Q)DataType temp; if(QueueEmpty(Q)Error(“Queue underflow”); /隊(duì)空下溢 temp=Q-dataQ-front; Q-count-; Q-front=(Q-front+1)%QueueSize;/循環(huán)意義下的頭指針加1 return temp;DataType QueueFront(CirQueue *Q)if(QueueEmpty(Q)

34、 Error(“Queue is empty.”); _;第四章 串一.基本要求、重點(diǎn)、難點(diǎn)本章的目的是介紹串的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其串上的基本運(yùn)算，本章重點(diǎn)是掌握串的兩種存儲(chǔ)表示、掌握串上實(shí)現(xiàn)的模式匹配算法。二.考核目標(biāo)和考核要求要求達(dá)到識(shí)記層次的是：串的有關(guān)概念及其運(yùn)算；串與線(xiàn)形性的關(guān)系要求達(dá)到簡(jiǎn)單應(yīng)用層次的是：串的兩種存儲(chǔ)表示；串上實(shí)現(xiàn)的模式匹配算法及其時(shí)間性能分析；使用C語(yǔ)言提供的串操作函數(shù)結(jié)構(gòu)與串相關(guān)的算法解決簡(jiǎn)單的應(yīng)用問(wèn)題三.練習(xí)題1.單項(xiàng)選擇題1.1如下陳述中正確的是（ ）A） 串是一種特殊的線(xiàn)性表B） 串的長(zhǎng)度必須大于0C） 串中元素只能是字母D） 空串就是空白串1.2設(shè)有兩個(gè)

35、串s和t，求t在s中首次出現(xiàn)的位置的運(yùn)算是（ ）A） 連接B） 模式匹配C） 求子串D） 求串長(zhǎng)1.3串的長(zhǎng)度是定義為（ ）A） 串中不同字母的個(gè)數(shù)B） 串中不同字符的個(gè)數(shù)C） 串中所含字符的個(gè)數(shù)，且大于0D） 串中所含字符的個(gè)數(shù)1.4設(shè)字符串s1=abcdefg，s2=pqrst，則運(yùn)算s=strcat（substr（s1，2，length（s2），substr（s1，length（s2），2）后串值為（ ）A） bcdefefB） bcpqrstC） bcdefgD） bcdef1.5下列哪些為空串（ ）A）S=“ ”B）S=“”C）S=“”D）S=“”1.6S1=“abcd”，S2=“

36、cd” ，則S2在S1中的位置是（ ）A） 1B） 2C） 3D） 41.7下列運(yùn)算，哪個(gè)是求串復(fù)制的函數(shù)（ ）A） Length(S)B） Copy(S1,S2)C） Concatenation(S1,S2)D） Compare(S1,S2)1.8列串的基本運(yùn)算，哪個(gè)是求串比較的函數(shù)（ ）A） Concatenation(S1,S2)B） Compare(S1,S2)C） Length(S)D） Index(S,C)2.填空題2.1在串S=“structure”中，以t為首字符的字串有 個(gè)2.2若S1=“abcdefg”，S2=“ def”，則strcat（S1，S2）= 3.簡(jiǎn)答題3.1空

37、串和空格串有什么區(qū)別？3.2串是一種特殊的線(xiàn)性表，特殊在哪里？3.3什么叫模式匹配？什么是模式串？3.4兩串相等的充分必要條件是什么？第五章 多維數(shù)組和廣義表一、基本要求、重點(diǎn)、難點(diǎn)本章目的是介紹多維數(shù)組的邏輯結(jié)構(gòu)特征及其存儲(chǔ)方式，特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法。本章重點(diǎn)是熟悉多維數(shù)組的存儲(chǔ)方式、矩陣的壓縮存儲(chǔ)方式，難點(diǎn)是稀疏矩陣的壓縮存儲(chǔ)方示下實(shí)現(xiàn)的算法。二、考核目標(biāo)、考核要求1.多維數(shù)組，要求達(dá)到“理解”層次1.1多維數(shù)組的邏輯特征。1.2多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及地址計(jì)算方式。1.3數(shù)組是一種隨機(jī)存取結(jié)構(gòu)的原因。2.矩陣的壓縮存儲(chǔ)，要求達(dá)到“理解”層次2.1特殊矩陣和稀疏矩陣的概念。2.

38、2特殊矩陣的壓縮存儲(chǔ)時(shí)的下標(biāo)變換方法。2.3稀疏矩陣的三元組表表示方法及有關(guān)算法。三、練習(xí)題1.單項(xiàng)選擇題1.1二維數(shù)組M的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍是從0到7，列下標(biāo)j的范圍從0到9，則存放M需要存儲(chǔ)單元數(shù)為（ ）A) 360B) 480C) 240D) 3201.2 N是一個(gè)58的二維數(shù)組，當(dāng)M按行優(yōu)先方式存儲(chǔ)時(shí)，表示該數(shù)組的第10個(gè)元素的是（ ）A) N22B)N21C) N11D) N121.3 二維數(shù)組Mij的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍是從0到4，列下標(biāo)j的范圍從0到5，M按行存儲(chǔ)時(shí)元素M35的起始地址與M按

39、列存儲(chǔ)時(shí)地址地址相同的元素是（ ）A) M24B)M34C) M35D) M441.4 稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（ ）A）二維數(shù)組和三維數(shù)組B）三元組和散列C）散列和十字鏈表D）三元組和十字鏈表1.5 常對(duì)數(shù)組進(jìn)行的兩種基本操作是（ ）A）建立和刪除B）索引和修改C）查找和修改D）查找和索引1.6 設(shè)矩陣A是一個(gè)對(duì)稱(chēng)矩陣，為了節(jié)省存儲(chǔ)空間，將其下三角部分（見(jiàn)圖5.1）按行序存放在一維數(shù)組SA0.n(n+1)/2中，對(duì)任一下三角部分元素aij（ij），在一維數(shù)組SA的下標(biāo)位置k的值是（ ）A）j*(j-1)/2+i-1B）i*(i+1)/2+jC）j*(j+1)/2+i-1D）i*(

40、i-1)/2+j圖5.12.填空2.1已知二維數(shù)組Amn采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC（A00），則Aij的地址是 。2.2 二維數(shù)組A1020采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素點(diǎn)一個(gè)存儲(chǔ)單元，且A00的存儲(chǔ)地址是200，則A612的地址是 。2.3 有一個(gè)10階對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式（以行序?yàn)橹鞔鎯?chǔ)，且A00=1），則A85的地址是 。第六章 樹(shù)一、基本要求、重點(diǎn)、難點(diǎn)本章目的是介紹二叉樹(shù)的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)、遍歷，樹(shù)的定義、存儲(chǔ)結(jié)構(gòu)、遍歷、樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換，哈夫曼樹(shù)等內(nèi)容。本章重點(diǎn)是掌握二叉樹(shù)的遍歷算法及有關(guān)應(yīng)用。難點(diǎn)是使用本章所學(xué)

41、到的有關(guān)知識(shí)設(shè)計(jì)出有效算法，解決與樹(shù)或二叉樹(shù)相關(guān)的應(yīng)用問(wèn)題。二、考核目標(biāo)、考核要求1.樹(shù)的概念，要求達(dá)到“理解”層次1.1樹(shù)的邏輯結(jié)構(gòu)特征。1.2樹(shù)的不同表示方法。1.3樹(shù)的常用術(shù)語(yǔ)及含義。2. 二叉樹(shù)，要求達(dá)到“簡(jiǎn)單應(yīng)用”層次2.1二叉樹(shù)的遞歸定義及樹(shù)與二叉樹(shù)的差別。2.2二叉樹(shù)的性質(zhì)、了解相應(yīng)的證明方法。2.3二叉樹(shù)的兩種存儲(chǔ)方法、特點(diǎn)及適應(yīng)范圍。3. 二叉樹(shù)的遍歷，要求達(dá)到“綜合應(yīng)用”層次3.1二叉樹(shù)的三種遍歷算法，理解其執(zhí)行過(guò)程。3.2確定三種遍歷所得到的相應(yīng)的結(jié)點(diǎn)訪(fǎng)問(wèn)序列。3.3以遍歷算法為基礎(chǔ)，設(shè)計(jì)有關(guān)算法解決簡(jiǎn)單的應(yīng)用問(wèn)題。4. 樹(shù)和森林，要求達(dá)到“理解”層次4.1樹(shù)和森林與二叉

42、樹(shù)的轉(zhuǎn)換方法。4.2樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)。4.3樹(shù)的兩種遍歷方法。5. 哈夫曼樹(shù)及其應(yīng)用，要求達(dá)到“簡(jiǎn)單應(yīng)用”層次5.1最優(yōu)二叉樹(shù)和最優(yōu)前綴碼的概念及特點(diǎn)。5.2哈夫曼算法的思想。5.3根據(jù)給定的葉結(jié)點(diǎn)及其權(quán)值構(gòu)造出相應(yīng)的最優(yōu)二叉樹(shù)。5.4根據(jù)最優(yōu)二叉樹(shù)構(gòu)造對(duì)應(yīng)的哈夫曼編碼。三、練習(xí)題1.單項(xiàng)選擇題1.1 設(shè)深度為K的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類(lèi)二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為（ ）A) k+1B) 2k+1C) 2k-1D) 2k1.2 按二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有（ ）種A) 5B) 4C) 3D) 61.3 深度為6的二叉樹(shù)至多有（ ）個(gè)結(jié)點(diǎn)A) 16B) 32C)

43、 64D) 631.4 二叉樹(shù)的第6層上最多有（ ）個(gè)結(jié)點(diǎn)A) 16B) 32C) 64D) 631.5 深度為6的完全二叉樹(shù)至少有（ ）個(gè)結(jié)點(diǎn)A) 31B) 32C) 63D) 641.6 某二叉樹(shù)共有4個(gè)葉結(jié)點(diǎn)，則其度為2的結(jié)點(diǎn)數(shù)共有（ ）個(gè)A) 5B) 4C) 3D) 無(wú)法計(jì)算1.7 某二叉樹(shù)只有度為0和度為2的結(jié)點(diǎn)，其中度為2結(jié)點(diǎn)數(shù)為8個(gè)，則該二叉樹(shù)共有（ ）個(gè)結(jié)點(diǎn)A) 15B) 17C) 16D) 無(wú)法計(jì)算1.8 從1開(kāi)始，對(duì)滿(mǎn)二叉樹(shù)從樹(shù)根起，自上層到下層，每層從左到右給每個(gè)結(jié)點(diǎn)順序編號(hào)，其第8層（假設(shè)第8層存在）第一個(gè)結(jié)點(diǎn)的編號(hào)是（ ）A) 256B)255C) 127D) 128

44、1.9 某完全二叉樹(shù)共有68個(gè)結(jié)點(diǎn)，從1開(kāi)始，對(duì)其從樹(shù)根起，自上層到下層，每層從左到右給每個(gè)結(jié)點(diǎn)順序編號(hào)，編號(hào)為32的結(jié)點(diǎn)的左孩子的編號(hào)是（ ）A) 16B) 64C) 65D) 無(wú)左孩子1.10 某完全二叉樹(shù)共有92個(gè)結(jié)點(diǎn)，從1開(kāi)始，對(duì)其從樹(shù)根起，自上層到下層，每層從左到右給每個(gè)結(jié)點(diǎn)順序編號(hào)，編號(hào)為46的結(jié)點(diǎn)的右孩子的編號(hào)是（ ）A) 23B) 24C) 92D) 無(wú)右孩子1.11 某完全二叉樹(shù)共有48個(gè)結(jié)點(diǎn)，從1開(kāi)始，對(duì)其從樹(shù)根起，自上層到下層，每層從左到右給每個(gè)結(jié)點(diǎn)順序編號(hào)，編號(hào)為15的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)是（ ）A) 7B) 8C) 30D) 311.12 如果T2是由有序樹(shù)T轉(zhuǎn)換而來(lái)

45、的二叉樹(shù)，那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的（ ）A) 前序B)中序 C) 后序D)層次序 1.13 如果T2是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的后序就是T2中結(jié)點(diǎn)的（ ）A) 前序B)中序C) 后序D)層次序1.14 樹(shù)的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹(shù)的基本遍歷策略可分為先序遍歷、中序遍歷、后序遍歷。這里，我們把由樹(shù)轉(zhuǎn)化得到的二叉樹(shù)叫做這棵樹(shù)的對(duì)應(yīng)二叉樹(shù)，結(jié)論（ ）是正確的A) 樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先序遍歷序列相同B) 樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后序遍歷序列相同C) 樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的中序遍歷序列相同D) 以上都不對(duì)1.15 任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（ ）A) 不發(fā)生改變B) 發(fā)生改變C) 不能確定D) 都不對(duì)1.16 一棵哈夫曼樹(shù)，共有13個(gè)葉結(jié)點(diǎn)，則該哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為（ ）A) 25B) 26C) 27D) 無(wú)法計(jì)算1.17 一棵非空的二叉樹(shù)的前序遍歷序列和后序遍歷序列正好相反，則該二叉樹(shù)一定滿(mǎn)足（ ）A) 其中任意一個(gè)結(jié)點(diǎn)均無(wú)左孩子B) 其中任意一個(gè)結(jié)點(diǎn)均無(wú)右孩子C) 其中只有一個(gè)葉子結(jié)點(diǎn)D) 是