數(shù)據(jù)結(jié)構(gòu)形考作業(yè)2

1、一、單項選擇題（每小題2分，共50分）題目1若讓元素1，2，3依次進棧，則出棧順序不可能為（）。選擇一項：A. 3，2，1B. 2，1，3C. 1，3，2D. 3，1，2題目2一個隊列的入隊序列是1，2，3，4。則隊列的輸出序列是（）。選擇一項：A. 4，3，2，1B. 1，2，3，4C. 1，4，3，2D. 3，2，4，1題目3向順序棧中壓入新元素時，應(yīng)當(dāng)（）。選擇一項：A. 先移動棧頂指針，再存入元素B. 同時進行C. 先后次序無關(guān)緊要D. 先存入元素，再移動棧頂指針題目4在一個棧頂指針為top的鏈棧中，將一個p指針所指的結(jié)點入棧，應(yīng)執(zhí)行（）。選擇一項：A. top->next=p;

2、B. p->next=top->next;top->next=p;C. p->next=top->next;top=top->next;D. p->next=top;top=p;題目5在一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，則執(zhí)行（）。選擇一項：A. top=top->next;x=top->data;B. x=top->data;C. x=top;top=top->next;D. x=top->data;top=top->next;題目6判斷一個順序隊列（最多元素為m）為空的條件是（）。

3、選擇一項：A. rear=m-1B. front=rearC. front=rear+1D. rear=m題目7判斷一個循環(huán)隊列Q（最多元素為m）為滿的條件是（）。選擇一項：A. Q->front=Q->rearB. Q->front=Q->rear+1C. Q->rear!=（Q->front+1）%mD. Q->front=（Q->rear+1）%m題目8判斷棧滿（元素個數(shù)最多n個）的條件是（）。選擇一項：A. top=0B. top=-1C. top=n-1D. top!=0題目9設(shè)有一個20階的對稱矩陣A（第一個元素為a1,1）,采用壓縮

4、存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），則矩陣元素a6,2在一維數(shù)組B中的下標是（）。選擇一項：A. 23B. 17C. 21D. 28題目10在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個（）結(jié)構(gòu)。選擇一項：A. 隊列B. 先性表C. 數(shù)組D. 堆棧題目11一個遞歸算法必須包括（）。選擇一項：A. 遞歸部分B. 迭代部分C. 終止條件和遞歸部分D. 終止條件和迭代部分題目12在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運算為

5、（）。選擇一項：A. r=f->next;B. f=f->next;C. f=r->next;D. r=r->next;題目13在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的運算為（選擇一項：A. s->next=f;f=s;B. r->next=s;r=s;C. s->next=r;r=s;D. f->next=s;f=s;題目14數(shù)組a經(jīng)初始化chara="English"a7中存放的是（）。選擇一項：A. 字符hB. "h"C. 字符串的結(jié)束符D. 變量h題目15設(shè)主串為"

6、ABcCDABcdEFaBc,以下模式串能與主串成功匹配的是（）。選擇一項：A. ABCB. AbcC. BcdD. BCd題目16字符串a(chǎn)1="AEIJING",a2="AEI",a3="AEFANG",a4="AEFI"中最大的是（）。選擇一項：A. a2B. a1C. a3D. a4題目17兩個字符串相等的條件是（）。選擇一項：A. 兩串的長度相等，并且兩串包含的字符相同B. 兩串的長度相等C. 兩串包含的字符相同D. 兩串的長度相等，并且對應(yīng)位置上的字符相同題目18一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用6

7、個字節(jié)，第6個元素的存儲地址為該數(shù)組的首地址是（）。選擇一項：A. 28B. 64C. 90）。100，則D. 70題目19一個非空廣義表的表頭（）。選擇一項：A. 可以是子表或原子B. 不可能是原子C. 只能是子表D. 只能是原子題目20對稀疏矩陣進行壓縮存儲,可采用三元組表，一個10行8列的稀疏矩陣A，其相應(yīng)的三元組表共有6個元素，矩陣A共有（）個零元素。選擇一項：A. 74B. 10C. 72D. 8題目21對稀疏矩陣進彳T壓縮存儲，可采用三元組表，一個10行8列的稀疏矩陣A共有73個零元素，A的右下角元素為6，其相應(yīng)的三元組表中的第7個元素是（）。選擇一項：A. （7，8，10）B.

8、（7，10，8）C. （10，8，7）D. （10，8，6）題目22對一個棧頂指針為top的鏈棧進行入棧操作，通過指針變量p生成入棧結(jié)點，并給該結(jié)點賦值a,貝U執(zhí)行：p=（structnode*）malloc（sizeof（structnode）;p->data=a;和（）。選擇一項：A. top->next=p;p=top;B. p->next=top;p=top;C. top=top->next;pe=top;D. p->nex=top;top=p;題目23頭指針為head的帶頭結(jié)點的單向鏈表為空的判定條件是（）為真。選擇一項：A. head->next

9、=NULLB. head->next!=NULLC. head=NULLD. head->next!=NULL題目24設(shè)有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），B數(shù)組共有55個元素,則該矩陣是（）階的對稱矩陣。選擇一項：A.20B. 15C. 5D. 10題目25數(shù)組a經(jīng)初始化chara="English"a1中存放的是（）。選擇一項：A. "n"B. 字符nC. 字符ED. "E"二、填空題（每小題2分，共30分）題目26循環(huán)隊列隊頭指針在隊尾指針下一個位置

10、，隊列是“滿”狀態(tài)。題目27循環(huán)隊列的引入，目的是為了克服假上溢。題目28判斷一個循環(huán)隊列LU（最多元素為m）為空的條件是LU->front=LU->rear。題目29向一個棧頂指針為h的鏈棧中插入一個s所指結(jié)點時，可執(zhí)行s->next=h和h=s操作。（結(jié)點的指針域為next）題目30從一個棧頂指針為h的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，可執(zhí)行x=h->data;和h=h->next。（結(jié)點的指針域為next）題目31在一個鏈隊中，設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的操作為r->next=s和r=s;（結(jié)點的指針域為next）題目32

11、在一個鏈隊中，設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的操作為f=f->next。（結(jié)點的指針域為next）題目33串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是字符。題目34空串的長度是0；空格串的長度是空格字符的長度。題目35設(shè)廣義表L=（）,（），則表頭是，表尾是，L的長度是表頭是（），表尾是（），L的長度是2題目36廣義表A（a，b，c），（d，e，f）的表尾為d,e,f。題目37設(shè)有n階對稱矩陣A,用數(shù)組s進行壓縮存儲，當(dāng)iRj時，A的數(shù)組元素aij相應(yīng)于數(shù)組s的數(shù)組元素的下標為i=（i-1）/2+j。（數(shù)組元素的下標從1開始）題目38對稀疏矩陣進行壓縮存儲，矩陣

12、中每個非零元素對應(yīng)的三元組包括該元素的、和三項信息。行下標、列下標和非零元素值題目39循環(huán)隊列用a0,，a7的一維數(shù)組存放隊列元素，（采用少用一個元素的模式），設(shè)front和rear分別為隊頭和隊尾指針，且front和rear的值分別為2和7，當(dāng)前隊列中的元素個數(shù)是5。題目40循環(huán)隊列的引入，目的是為了克服假上溢。三、問答題（每小題5分，共20分）題目41棧、隊列和線性表的區(qū)別是什么？答：棧是一種先進后出的線性表，棧的插入和刪除操作都只能在棧頂進行，而一般的線性表合一在線性表的任何位置進行插入和刪除操作。隊列是一種先進先出的線性表，隊列的插入只能在隊尾進行，隊列的刪除只能在隊頭進行，而一般的線

13、性表可以在線性表的任何位置進行插入和刪除操作題目42設(shè)棧S和隊列Q的初始狀態(tài)為空，元素el,e2,e3,e4,e5和e6依次通過S,一個元素出棧后即進隊列Q,若6個元素出隊白序列是e2,e4,e3,e6,e5,el,則棧S的容量至少應(yīng)該是多少？出隊序列是e2,e4,e3,e6,e5,e1的過程：（1）e1入棧（棧底到棧頂元素是e1）（2） e2入棧（棧底到棧頂元素是e1,e2）（3） e2出棧（棧底到棧頂元素是e1）（4） e3入棧（棧底到棧頂元素是e1,e3）（5） e4入棧（棧底到棧頂元素是e1,e3,e4）（6） e4出棧（棧底到棧頂元素是e1,e3）（7） e3出棧（棧底到棧頂元素是e

14、1）（8） e5入棧（棧底到棧頂元素是e1,e5）（9） e6入棧（棧底到棧頂元素是e1,e5,e6）（ 10） e6出棧（棧底到棧頂元素是e1,e5）（11）e5出棧（棧底到棧頂元素是e1）（12）e1出棧（棧底到棧頂元素是空）棧中最多時有3個元素，所以棧S的容量至少是3題目43有5個元素，其入棧次序為：A、B、CD、E,在各種可能的出棧次序中，以元素CD最先的次序有哪幾個？從題中可知，要使C第一個且D第二個出棧，應(yīng)是A入棧，B入棧，C入棧，C出棧，D入棧，D出棧，之后可以有一下幾種情況：（1） B出棧，E入棧，E出棧，A出棧，CDBEA（2） E入棧，E出棧，B出棧，A出棧，CDEBA（3） B出棧，A出棧，E入棧，E出棧，CDB