1、A 10 B18B 19B 20 D有零個或多個輸出一、單項選擇題1C 2D 3B 4C 5D 6C 7B 8C 911C 12D 13C 14A 15B 16C 17C二、填空題1n-i+12n-i3集合 線性結構 樹形結構 圖狀結構4物理結構 存儲結構5線性結構 非線性結構6有窮性 確定性 可形性 有零個或多個輸入7圖狀結構8樹形結構9線性結構10 n-1 O(n)11 s-next=p-next;12 head13 q-next=p-next;14 p-next=head;15單鏈表16順序存儲 鏈式存儲17存儲結構 18兩個 直接后繼 直接前驅 尾結點 頭結點19頭結點的指針 指向第一

2、個結點的指針20鏈式 鏈表三、問答題1簡述數據的邏輯結構和存儲結構的區別與聯系，它們如何影響算法的設計與實現？ 答：若用結點表示某個數據元素， 則結點與結點之間的邏輯關系就稱為數據的邏輯結構。 數 據在計算機中的存儲表示稱為數據的存儲結構。 可見， 數據的邏輯結構是反映數據之間的固 有關系， 而數據的存儲結構是數據在計算機中的存儲表示。 盡管因采用的存儲結構不同， 邏 輯上相鄰的結點，其物理地址未必相同， 但可通過結點的內部信息，找到其相鄰的結點，從 而保留了邏輯結構的特點。 采用的存儲結構不同， 對數據的操作在靈活性， 算法復雜度等方 面差別較大。2解釋順序存儲結構和鏈式存儲結構的特點，并比

3、較順序存儲結構和鏈式存儲結構的優缺 點。答：順序結構存儲時，相鄰數據元素的存放地址也相鄰，即邏輯結構和存儲結構是統一的， ，要 求內存中存儲單元的地址必須是連續的。優點：一般情況下，存儲密度大，存儲空間利用率高。缺點：（ 1）在做插入和刪除操作時，需移動大量元素； （2）由于難以估計，必須預先分配較 大的空間，往往使存儲空間不能得到充分利用；（3）表的容量難以擴充。鏈式結構存儲時，相鄰數據元素可隨意存放， 所占空間分為兩部分，一部分存放結點值，另 一部分存放表示結點間關系的指針。優點：插入和刪除元素時很方便，使用靈活。缺點：存儲密度小，存儲空間利用率低。3什么情況下用順序表比鏈表好？ 答：順序

4、表適于做查找這樣的靜態操作， 鏈表適于做插入和刪除這樣的動態操作。 如果線性表的變化長度變化不大，且其主要操作是查找，則采用順序表； 如果線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。4解釋頭結點、第一個結點（或稱首元結點） 、頭指針這三個概念的區別？答：頭結點是在鏈表的開始結點之前附加的一個結點； 第一個結點 （或稱首元結點） 是鏈表中存 儲第一個數據元素的結點； 頭指針是指向鏈表中第一個結點 （或為頭結點或為首元結點） 的 指針。5解釋帶頭結點的單鏈表和不帶頭結點的單鏈表的區別。答：帶頭結點的單鏈表和不帶頭結點的單鏈表的區別主要體現在其結構上和算法操作上。在結構上， 帶頭

5、結點的單鏈表， 不管鏈表是否為空，均含有一個頭結點，不帶頭結點的單鏈 表不含頭結點。在操作上， 帶頭結點的單鏈表的初始化為申請一個頭結點。 無論插入或刪除的位置是地第一 個結點還是其他結點， 算法步驟都相同。 不帶頭結點的單鏈表， 其算法步驟要分別考慮插入 或刪除的位置是第一個結點還是其他結點。因為兩種情況的算法步驟不同。四、程序填空題1（1）p-data=i（2）p-next=NULL（3）q-next=p4）q=p2（1）head=p（2）q=p（3）p-next=NULL（4）p-next=q-next（5）q-next=p3（1） p=q-next（2） q-next=p-next五、

6、完成：實驗 1線性表根據實驗要求（見教材 P201-202）認真完成本實驗，并提交實驗報告。作業 2 答案本部分作業覆蓋教材第 3-5 章的內容）一、單項選擇題1C 2B 3A 4C 5B 6A 7B 8C 9A 10C11B 12C 13B 14B 15A 16C 17B 18A 19C 20D 21B 22D 23C 24B 25D 26A 27C 28D 29D 30C 31A 32D、填空題 1后進先出2下一個3增 1 增 14假上溢5棧是否滿 s-top=MAXSIZE-1 棧頂指針 棧頂對應的數組元素 棧是否空 s-top=-1 棧頂元素 修改棧頂指針6bceda7終止條件 遞歸部

7、分8LU-front=LU-rear9運算符 操作數 ab+c/fde/-10 s-next=h;11 h=h-next;12 r-next=s;13 f=f-next;14字符15順序存儲方式 鏈式存儲方式16 0 空格字符的個數17特殊 稀疏18（） （） 219（d,e,f） 20串長度相等且對應位置的字符相等21 i(i-1)/2+j 22行下標、列下標、非零元素值三、問答題1簡述棧和一般線性表的區別。答：棧是一種先進后出的線性表， 棧的插入和刪除操作都只能在棧頂進行， 而一般的線性表 可以在線性表的任何位置進行插入和刪除操作。2簡述隊列和一般線性表的區別。隊列是一種先進先出的線性表，

8、隊列的插入只能在隊尾進行，隊列的刪除只能在隊頭進行， 而一般的線性表可以在線性表的任何位置進行插入和刪除操作。3鏈棧中為何不設頭結點？答：因為鏈棧只在鏈頭插入和刪除結點， 不可能在鏈表中間插入和刪除結點， 算法實現很簡 單，所以一般不設置頭結點。4利用一個棧，則：（1）如果輸入序列由 A，B，C 組成，試給出全部可能的輸出序列和不可能的輸出序列。（2）如果輸入序列由 A，B，C，D 組成，試給出全部可能的輸出序列和不可能的輸出序列。答：（1）棧的操作特點是后進先出，因此輸出序列有：A 入， A 出， B 入， B 出， C 入 C出，輸出序列為 ABC。A入， A出， B入， C入， C出，B

9、 出，輸出序列為 ACB。A 入，B入，B 出，A 出，C入，C出，輸出序列為BAC。A 入，B入，B 出，C 入，C出，A 出，輸出序列為BCA。A 入，B入，C 入，C出，B 出，A 出，輸出序列為CBA。由 A，B， C組成的數據項，除上述五個不同的組合外，還有一個C，A，B 組合。但不可能先把 C出棧，再把 A 出棧，（A 不在棧頂位置） ，最后把 B出棧，所以序列 CAB不可能由輸 入序列 A，B， C 通過棧得到。（2）按照上述方法，可能的輸出序列有：ABCD，ABDC，ACBD，ACDB，ADCB，BACD， BADC，BCAD，BCDA，BDCA，CBAD，CBDA， CDBA

10、，DCBA。不可能的輸出序列有：DABC，ADBC，DACB， DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD5用 S表示入棧操作， X 表示出棧操作， 若元素入棧順序為 1234，為了得到 1342 出棧順序， 相應的 S和 X 操作串是什么？答：應是 SXSSXSX。X各操作結果如下：S 1 入棧X 1 出棧 輸出序列： 1S 2 入棧S 3 入棧X 3 出棧 輸出序列： 13S 4 入棧X 4 出棧 輸出序列： 134X 2 出棧 輸出序列： 13426有 5 個元素，其入棧次序為： A、B、C、 D、 E，在各種可能的出棧次序中，以元素C、D最先的次序有哪幾個？答

11、：從題中可知，要使 C第一個且 D第二個出棧，應是 A入棧，B入棧，C入棧， C出棧， D 入棧。之后可以有以下幾種情況：1)B 出棧，A出棧，E 入棧，E出棧，輸出序列為：CDBAE。2)B 出棧，E入棧，E出棧，A 出棧，輸出序列為CDBEA。3)E入棧，E 出棧，B出棧，A 出棧，輸出序列為CDEBA所以可能的次序有： CDBAE，CDBEA，CDEBA7寫出以下運算式的后綴算術運算式 3x2+x-1/x+5 (A+B)*C-D/(E+F)+G答；對應的后綴算術運算式 3x2*x+1x/-5+ AB+C*DEF+/-G+8 簡述廣義表和線性表的區別和聯系。答：廣義表是線性表的的推廣，它也

12、是n(n0)個元素 a1 ,a2 ai a的n 有限序列，其中 ai 或者是原子或者是一個廣義表。所以，廣義表是一種遞歸數據結構，而線性表沒有這種特性， 線性表可以看成廣義表的特殊情況，當 ai 都是原子時，廣義表退化成線性表。四、程序填空題11) q-front-next=p-next;2) free(p);3) q-rear=q-front五、綜合題1答：出隊序列是 e2,e4,e3,e6,e5,e1 的過程： e1 入棧（棧底到棧頂元素是 e1 ） e2 入棧（棧底到棧頂元素是 e1,e2 ） e2 出棧（棧底到棧頂元素是 e1 ） e3 入棧（棧底到棧頂元素是 e1,e3 ） e4 入

13、棧（棧底到棧頂元素是 e1,e3,e4 ） e4 出棧（棧底到棧頂元素是 e1,e3 ） e3 出棧（棧底到棧頂元素是 e1 ） e5 入棧（棧底到棧頂元素是 e1,e5 ） e6 入棧（棧底到棧頂元素是 e1,e5,e6 ） e6 出棧（棧底到棧頂元素是 e1,e5 ） e5 出棧（棧底到棧頂元素是 e1 ） e1 出棧（棧底到棧頂元素是空）棧中最多時有 3 個元素，所以棧 S的容量至少是 3。2算法設計如下：/* 只有一個指針 rear 的鏈式隊的基本操作 */#include typedef char elemtype;struct node /* 定義鏈隊列結點 */elemtype

14、data;struct node *next;typedef struct queue /* 定義鏈隊列數據類型 */struct node *rear; LinkQueue;void initqueue(LinkQueue *Q)/* 初始化隊列 */Q=(struct queue *)malloc(sizeof(struct queue);Q-rear=NULL;void enqueue(LinkQueue *Q,elemtype x) /* 入隊算法 */struct node *s,*p;s=(struct node *)malloc(sizeof(struct node);s-dat

15、a=x;if (Q-rear=NULL) /* 原為空隊時 */Q-rear=s;s-next=s;else /* 原隊不為空時 */p=Q-rear-next; /*p 指向第一個結點 */Q-rear-next=s; /* 將 s 鏈接到隊尾 */Q-rear=s; /*Q-rear 指向隊尾 */s-next=p;void delqueue(LinkQueue *Q) /* 出隊算法 */struct node *t;if (Q-rear=NULL)printf( 隊列為空 !n);return(0);else if (Q-rear-next=Q-rear) /* 只有一個結點時 */t=Q-rear;Q-rear=NULL;else /* 有多個結點時 */t=Q-rear-next; /*t 指向第一個結點 */Q-rear-next=t-next; /* 引成循環鏈 */free(t);elemtype gethead(LinkQueue *Q) /* 取隊首元素算法 */if (Q-rear=NULL)printf( 隊列為空 !n);elsereturn(Q-rear-next-data);int emptyqueue(LinkQueue *Q) /* 判斷隊列是否為空算法 */ if (Q-rear=NULL) return(1); /* 為空 ,