數據結構形考作業(yè)2

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