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

一、單項(xiàng)選擇題（每小題2分，共50分）題目1若讓元素1，2,3依次進(jìn)棧，則出棧順序不可能為（）。選擇一項(xiàng)：3,2,12,1,31,3,23,1,2題目2一個(gè)隊(duì)列的入隊(duì)序列是1,2,3,4。則隊(duì)列的輸出序列是（）。選擇一項(xiàng)：4,3,2,11,2,3,41,4,3,23,2,4,1題目3向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（）。選擇一項(xiàng)：先移動(dòng)棧頂指針，再存入元素同時(shí)進(jìn)行先后次序無(wú)關(guān)緊要先存入元素，再移動(dòng)棧頂指針題目4在一個(gè)棧頂指針為top的鏈棧中，將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（）。選擇一項(xiàng)：top->next=p;p->next=top->next;top->next=p;p->next=top->next;top=top->next;p->next=top;top=p;題目5在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（）。選擇一項(xiàng)：top=top->next;x=top->data;x=top->data;x=top;top=top->next;x=top->data;top=top->next;題目6判斷一個(gè)順序隊(duì)列（最多元素為m）為空的條件是（）。選擇一項(xiàng)：rear==m-lfront==rearfront==rear+lrear=m題目7判斷一個(gè)循壞隊(duì)列Q（最多元素為m）為滿的條件是（）。選擇一項(xiàng)：Q->front==Q?>rearQ->front=Q->rear+1Q->rear!=（Q->front+l）%mQ->front==（Q->rear+l）%m題目8判斷棧滿（元素個(gè)數(shù)最多n個(gè)）的條件是（）。選擇一項(xiàng)：top==0top=-lC?top=D.top!=0題目9設(shè)有一個(gè)20階的對(duì)稱矩陣A（第一個(gè)元素為al,l）,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣元素a6,2在一維數(shù)組B中的下標(biāo)是（）。選擇一項(xiàng)：TOC\o"1-5"\h\z23172128題目10在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入緩沖區(qū)中，而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個(gè)（）結(jié)構(gòu)。選擇一項(xiàng)：隊(duì)列先性表數(shù)組堆棧題目11一個(gè)遞歸算法必須包扌舌（）。選擇一項(xiàng)：遞歸部分迭代部分終止條件和遞歸部分終止條件和迭代部分題目12在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（）。選擇一項(xiàng)：r=f->next;f=f->next;f=r->next;r=r->next;題目13在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（）。選擇一項(xiàng)：s->next=f;f=s;r->next=s;r=s;s->next=r;r=s;f->next=s;f=s;題目14數(shù)組a經(jīng)初始化chara[]=“English”；a[7]中存放的是（）。選擇一項(xiàng)：字符h"h"字符串的結(jié)束符變量h題目15設(shè)主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（）。選擇一項(xiàng)：ABCAbeBedTOC\o"1-5"\h\zBCd題目16字符串a(chǎn)l="AEIJING",a2=,,AEI",a3="AEFANG",a4="AEFI"中最大的是（）。選擇一項(xiàng)：a2ala3a4題目17兩個(gè)字符串相等的條件是（）o選擇一項(xiàng)：兩串的長(zhǎng)度相等，并且兩串包含的字符相同兩串的長(zhǎng)度相等兩串包含的字符相同兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同題目18一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的存儲(chǔ)地址為100,則該數(shù)組的首地址是（）。選擇一項(xiàng)：TOC\o"1-5"\h\z28649070題目19一個(gè)非空廣義表的表頭（）。選擇一項(xiàng)：可以是子表或原子不可能是原子只能是子表只能是原子題目20對(duì)桶疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)10行8列的棉疏矩陣A,其相應(yīng)的三元組表共有6個(gè)元素，矩陣A共有（）個(gè)零元素。選擇一項(xiàng)：TOC\o"1-5"\h\z7410728題目21對(duì)桶疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)10行8列的桶疏矩陣A共有73個(gè)零元素，A的右下角元素為6,其相應(yīng)的三元組表中的第7個(gè)元素是（）。選擇一項(xiàng)：A.(7,8,10)B.(7,10,8)C.(10,&7)D.(10,&6)題目22對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行入棧操作，通過(guò)指針變量p生成入棧結(jié)點(diǎn)，并給該結(jié)點(diǎn)賦值a,則執(zhí)行：p=（structnode*）malloc（sizeof（structnode）;p->data=a;和（）。選擇一項(xiàng)：top->next=p;p=top;p->next=top;p=top;top=top->next;pe=top;p->nex=top;top=p;題目23頭指針為head的帶頭結(jié)點(diǎn)的單向鏈表為空的判定條件是（）為真。選擇一項(xiàng)：head->next==NULLhead->next!=NULLhead==NULLhead->next!=NULL題目24設(shè)有一個(gè)對(duì)稱矩陣A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），B數(shù)組共有55個(gè)元素，則該矩陣是（）階的對(duì)稱矩陣。選擇一項(xiàng)：2015TOC\o"1-5"\h\z510題目25數(shù)組a經(jīng)初始化chara[]=“English”；a[1]中存放的是()。選擇一項(xiàng)："n"字符n字符E"E"二、填空題(每小題2分，共30分)題目26循環(huán)隊(duì)列隊(duì)頭指針在隊(duì)尾指針I(yè)、?一個(gè)位置，隊(duì)列是“滿”狀態(tài)。題目27循環(huán)隊(duì)列的引入，目的是為了克服假上溢。題目28判斷一個(gè)循壞隊(duì)列LU(最多元素為m)為空的條件是LU->front==LU->rearo題目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->nexto(結(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在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為f=f->nexto(結(jié)點(diǎn)的指針域?yàn)閚ext)題目33串是一種特殊的線性表，其特姝性表現(xiàn)在組成串的數(shù)據(jù)元素都是字符。題目34空串的長(zhǎng)度是0：空格串的長(zhǎng)度是空格字符的長(zhǎng)度。題目35設(shè)廣義表！_=((),()),則表頭是,表尾是,L的長(zhǎng)度是表頭是()，表尾是(O),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)i>j時(shí)，A的數(shù)組元素aij相應(yīng)于數(shù)組s的數(shù)組元素的下標(biāo)為i=(i-l)/2+jo(數(shù)組元素的下標(biāo)從1開(kāi)始)題目38對(duì)桶疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的、和三項(xiàng)信息。行下標(biāo)、列下標(biāo)和非零元素值題目39循環(huán)隊(duì)列用a[0],…，a[7]的一維數(shù)組存放隊(duì)列元素，（采用少用一個(gè)元素的模式），設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，且front和rear的值分別為2和7,當(dāng)前隊(duì)列中的元素個(gè)數(shù)是5。題目40循環(huán)隊(duì)列的引入，目的是為了克服假上溢。三、問(wèn)答題（每小題5分，共20分）題目41棧、隊(duì)列和線性表的區(qū)別是什么？答：棧是一種先進(jìn)后出的線性表，棧的插入和刪除操作都只能在棧頂進(jìn)行，而一般的線性表合一在線性表的任何位置進(jìn)行插入和刪除操作。隊(duì)列是一種先進(jìn)先出的線性表，隊(duì)列的插入只能在隊(duì)尾進(jìn)行，隊(duì)列的刪除只能在隊(duì)頭進(jìn)行,而一般的線性表可以在線性表的任何位置進(jìn)行插入和刪除操作題目42設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el,e2,e3,e4,e5和e6依次通過(guò)S,—個(gè)元素出棧后即進(jìn)隊(duì)列Q,若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,el,則棧S的容量至少應(yīng)該是多少？出隊(duì)序列是e2,e4,e3,e6,e5,el的過(guò)程:（1）el入棧（棧底到棧頂元素是el）（2）e2入棧（棧底到棧頂元素是el,e2）（3）e2出棧（棧底到棧頂元素是el）（4）e3入棧（棧底到棧頂元素是el,e3）（5）e4入棧（棧底到棧頂元素是el,e3,e4）（6）e4出棧（棧底到棧頂元素是el,e3）（7）e3出棧（棧底到棧頂元素是el）（8）e5入棧（棧底到棧頂元素是el,e5）（9）e6入棧（棧底到棧頂元素是el,e5,e6）（10）e6出棧（棧底到棧頂元素是el,e5）（IDe5出棧（棧底到棧頂元素是el）（12）el出棧（棧底到棧頂元素是空）棧中最多時(shí)有3個(gè)元素，所以棧S的容量至少是3題目43有5個(gè)元素，其入棧次序?yàn)椋篈、B、C、D、E,在各種可能的出棧次序中，以元素C、D最先的次序有哪幾個(gè)？從題中可知，要使C第一個(gè)且D第二個(gè)出棧，應(yīng)是A入棧，B入棧，C入棧，C出棧，D入棧，D出棧，之后可以有一下幾種情況：（1）B出棧，E入棧，E出棧，A出棧，CDBEA（2）E入棧，E出棧，B出棧