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

1、一、單項(xiàng)選擇題（每小題2分，共50分）題目1若讓元素1，2，3依次進(jìn)棧，則出棧順序不可能為（）。選擇一項(xiàng)：A. 3，2，1B. 2，1，3C. 1，3，2D. 3，1，2題目2一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4。則隊(duì)列的輸出序列是（）。選擇一項(xiàng)：A. 4，3，2，1B. 1，2，3，4C. 1，4，3，2D. 3，2，4，1題目3向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（）。選擇一項(xiàng)：A. 先移動(dòng)棧頂指針，再存入元素B. 同時(shí)進(jìn)行C. 先后次序無(wú)關(guān)緊要D. 先存入元素，再移動(dòng)棧頂指針題目4在一個(gè)棧頂指針為top的鏈棧中，將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（）。選擇一項(xiàng)：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在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（）。選擇一項(xiàng)：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判斷一個(gè)順序隊(duì)列（最多元素為m）為空的條件是（）。

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

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

5、（）。選擇一項(xiàng)：A. r=f->next;B. f=f->next;C. f=r->next;D. r=r->next;題目13在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（選擇一項(xiàng)：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中存放的是（）。選擇一項(xiàng)：A. 字符hB. "h"C. 字符串的結(jié)束符D. 變量h題目15設(shè)主串為"

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

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

8、（7，10，8）C. （10，8，7）D. （10，8，6）題目22對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行入棧操作，通過指針變量p生成入棧結(jié)點(diǎn)，并給該結(jié)點(diǎn)賦值a,貝U執(zhí)行：p=（structnode*）malloc（sizeof（structnode）;p->data=a;和（）。選擇一項(xiàng)：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é)點(diǎn)的單向鏈表為空的判定條件是（）為真。選擇一項(xiàng)：A. head->next

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

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

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

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

13、性表可以在線性表的任何位置進(jìn)行插入和刪除操作題目42設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el,e2,e3,e4,e5和e6依次通過S,一個(gè)元素出棧后即進(jìn)隊(duì)列Q,若6個(gè)元素出隊(duì)白序列是e2,e4,e3,e6,e5,el,則棧S的容量至少應(yīng)該是多少？出隊(duì)序列是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出棧（棧底到棧頂元素是空）棧中最多時(shí)有3個(gè)元素，所以棧S的容量至少是3題目43有5個(gè)元素，其入棧次序?yàn)椋篈、B、CD、E,在各種可能的出棧次序中，以元素CD最先的次序有哪幾個(gè)？從題中可知，要使C第一個(gè)且D第二個(gè)出棧，應(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