數(shù)據(jù)結(jié)構(gòu)期中試卷

一、選擇題〔每題2分，共30分〕數(shù)據(jù)構(gòu)造是〔D〕。A．一種數(shù)據(jù)種類B．?dāng)?shù)據(jù)的存儲構(gòu)造C．一組性質(zhì)相同的數(shù)據(jù)元素的會合D．相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的會合2．以下與數(shù)據(jù)的存儲構(gòu)造無關(guān)的術(shù)語是〔D〕。A．鏈行列B.鏈表C.次序表D.棧3．以下數(shù)據(jù)構(gòu)造中，〔A〕是非線性數(shù)據(jù)構(gòu)造A．樹B．字符串C．隊D．棧4．一個次序存儲線性表的第一個元素的存儲地點是90，每個元素的長度是2，那么第6個元素的存儲地點是〔B〕。A．98B．100C．102D．1065．在線性表的以下運算中，不改變數(shù)據(jù)元素之間構(gòu)造關(guān)系的運算是〔D〕。A．插入B．刪除C．排序D．查找6．線性表采用鏈式存儲時，其地點(D)。A．必須是連續(xù)的B．一定是不連續(xù)的C．局部地點必須連續(xù)D．連續(xù)與否均能夠7．線性表是(A)。A．一個有限序列，能夠為空B．一個有限序列，不能夠為空C．一個無限序列，能夠為空D．一個無限序列，不能夠為空8．假定進棧序列為1，2，3，4，5，6，且進棧和出棧能夠穿插進行，那么可能出現(xiàn)的出棧序列為〔B〕。A．3，2，6，1，4，5B．3，4，2，1，6，5C．1，2，5，3，4，6D．5，6，4，2，3，19.假定一個棧的輸人序列是1，2，3，，n，輸出序列的第一個元素是n，那么第k個輸出元素是〔C〕。A．kB．n-k-1C．n-k+1D．不確定10.關(guān)于行列操作數(shù)據(jù)的原那么是〔A〕。A.先進先出B.后進先出C.先進后出D.不分次序11.棧和行列的共同點是〔C〕。A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點12．在一個鏈行列中，假定front和rear分別為頭指針和尾指針，刪除一個結(jié)點的操作是〔A〕。A．front=front->nextB．rear=rear->nextC．rear->next=frontD．front->next＝rear空串與空格串〔B〕。A．相同B．不相同C．可能相同D．無法確定14.串與普通的線性表相比較，它的特殊性表達在〔C〕。A．次序的存儲構(gòu)造B．鏈接的存儲構(gòu)造C．?dāng)?shù)據(jù)元素是一個字符D．?dāng)?shù)據(jù)元素能夠隨意串的長度是指〔B〕。A.串中所含不同字母的個數(shù)B.串中所含字符的個數(shù)C.串中所含不同字符的個數(shù)D.串中所含非空格字符的個數(shù)二、填空題〔每空2分，共20分〕1．線性表、棧和行列，串都是__線性_____構(gòu)造。2．?dāng)?shù)據(jù)的根本單位是__數(shù)據(jù)元素_______________。3．當(dāng)線性表的元素總數(shù)根本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用_次序______存儲構(gòu)造。4．擁有n個元素的一維數(shù)組采用次序存儲構(gòu)造，每個元素占k個存儲單元，第一個元素的地點為Loc(a1)，那么，第i個元素的存儲地點Loc(ai)=Loc(a1)+(i-1)*k。5．?！瞫tack〕是限定在表尾進行插人或刪除操作的線性表。在棧中，允許插人和刪除操作的一端稱為__棧頂________，而另一端稱為_棧底________。6．一個循環(huán)行列Q中，頭指針和尾指針分別為Q.front和Q.rear，且最大行列長度為MaxQSize，那么判斷隊空的條件為Q.rear==Q.front,判斷隊滿的條件為(Q.rear+1)%MaxQSize==Q.front。行列的長度為(.rear-Q.front+MaxQSize)%MaxQSize精選7．兩個串相等的充分必要條件是兩個串的長度相等，且各個對應(yīng)地點的字符都相等。三、程序填空題〔每空3分，共30分〕1.在帶頭結(jié)點的單鏈表L中第i個數(shù)據(jù)元素以前插入數(shù)據(jù)元素e的C語言描繪算法如下，其中L為鏈表頭結(jié)點指針。請?zhí)畛渌惴ㄖ袠顺龅目瞻滋帲_成其功能。typedefstructnode{intdata；structnode*next；}linknode,*link；intListInsert_L(link&L,inti,inte){Linknode*p；intj；p=L；j=0；while(p&&j<i-1){p=p->next；++j；}//尋找第i-1個結(jié)點if(!p||j>i-1)return0；s=(link)malloc(sizeof(linknode))；//生成新結(jié)點ss->data=e；s->next=p->next；p->next=s；//插入L中return1；}\2.對次序棧的C語言描繪算法如下，其中top為棧頂指針，請?zhí)畛渌惴ㄖ袠顺龅目瞻滋?，插入元素e為新的棧頂元素。#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{char*base;char*top;intstacksize;}SqStack;intPush(SqStack&S,chare){//if((s.top-s.base)>=s.stacksize)//棧滿，追加存儲空間{S.base=(SElemType*)realloc(S.base,S.stacksize+STACKINCREMENT)*sizeof(SElemType))；if(!S.base)return0；S.top=s.base+s.stacksize；//改正棧頂指針S.stacksize+=STACKINCREMENT；}*s.top++=e；//插入元素return1；}3.對鏈行列的C語言描繪算法如下，請?zhí)畛渌惴ㄖ袠顺龅目瞻滋?，刪除行列Q的隊頭元素并用e返回其值。typedefstructQNode{QElemTypedata；structQNode*next；}QNode,*QueuePtr；typedefstruct{QueuePtrfront；QueuePtrrear；}LinkQueue；intDeQueue(LinkQueue&Q,QElemType&e){Linknode*p；if(Q.front==Q.rear)retrun0；//行列空，返回p=Q.front->next；e=p->data；Q.front->next=p->next；//改正指針if(Q.rear==p)Q.rear=Q.front；//行列只有一個元素的情況free(p)；//釋放結(jié)點空間return1；}精選三、算法設(shè)計與剖析題〔每題10分，共20分〕1、簡述以下算法實現(xiàn)的功能：〔每題5分，共10分〕〔1〕typedefstructLNode{Chardata;structLNode*next;}LNode,*LinkList;LinkListDemo(LinkList&L){//L是無頭結(jié)點單鏈表LNode*Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}returnL;}//Demo答：將單鏈表的第一個結(jié)點刪除，放到鏈尾。———————————————————————————————————————————————————〔2〕#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{int*base;int*top;intstacksize;}Stack;voidDemo1(Stack&S,intm){StackT;inti;InitStack(T);//初始化棧while(!StackEmpty(S))//判斷棧是否為空if((i=Pop(S))!=m)Push(T,i);//入棧操作while(!StackEmpty(T)){i=Pop(T);//出棧操作Push(S,i);}}答：刪除棧S中所有值為m的數(shù)據(jù)元素有一個帶頭結(jié)點的單鏈表，頭指針為head，編寫一個算法計算所有數(shù)據(jù)域為X的結(jié)點的個數(shù)〔不包括頭結(jié)