數(shù)據(jù)結構期中試卷及答案

1、一、選擇題每題 2分，共30分1. 數(shù)據(jù)結構是D 。A. 種數(shù)據(jù)類型B 數(shù)據(jù)的存儲結構C. 一組性質相同的數(shù)據(jù)元素的集合D. 相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合2 以下與數(shù)據(jù)的存儲結構無關的術語是D 。A.鏈隊列 B. 鏈表 C. 順序表 D.棧3以下數(shù)據(jù)結構中，A 是非線性數(shù)據(jù)結構A.樹 B.字符串C .隊 D4. 一個順序存儲線性表的第一個元素的存儲地址是90,A . 98 B . 100 C . 102.棧每個元素的長度是 2,那么第6個元素的存儲地址是B。D . 1065在線性表的以下運算中，不改變數(shù)據(jù)元素之間結構關系的運算是D 。A.插入 B .刪除 C .排序 D .查

2、找6.線性表采用鏈式存儲時，其地址A .必須是連續(xù)的BC .局部地址必須連續(xù)DD 。.一定是不連續(xù)的.連續(xù)與否均可以7 .線性表是A 。A. 個有限序列，可以為空C. 一個無限序列，可以為空B.一個有限序列，不可以為空D.一個無限序列，不可以為空&假設進棧序列為1, 2, 3, 4, 5,6,且進棧和出棧可以穿插進行，那么可能出現(xiàn)的出棧序列為B 。A. 3, 2, 6, 1, 4, 5 B3, 4, 2, 1, 6, 5C. 1 , 2, 5, 3, 4, 6D . 5, 6, 4, 2, 3, 19.假設一個棧的輸人序列是1, 2, 3,A. k B . n-k-1 C,n,輸出序列

3、的第一個元素是n ,那么第k個輸出元素是C 。n-k+1 D.不確定10. 對于隊列操作數(shù)據(jù)的原那么是 A 。A.先進先出B.后進先出C.先進后出D.不分順序11. 棧和隊列的共同點是C 。A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點12 .在一個鏈隊列中，假定front和rear分別為頭指針和尾指針，刪除一個結點的操作是 A 。A. front=front->nextB. rear=rear->nextC . rear->next=frontD. front->next = rear13.空串與空格串B 。A .相同 B.不相同C .

4、可能相同D.無法確定14.串與普通的線性表相比擬，它的特殊性表達在 C 。A.順序的存儲結構C .數(shù)據(jù)元素是一個字符BD.鏈接的存儲結構.數(shù)據(jù)兀素可以任意15.串的長度是指B 。A.串中所含不同字母的個數(shù)B.串中所含字符的個數(shù)C.串中所含不同字符的個數(shù)D.串中所含非空格字符的個數(shù)二、填空題每空 2分，共20 分1 .線性表、棧和隊列，串都是線性結構。2 .數(shù)據(jù)的根本單位是_數(shù)據(jù)元素 。3. 當線性表的元素總數(shù)根本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用順序_一存儲結構。4. 具有n個元素的一維數(shù)組采用順序存儲結構，每個元素占k個存儲單元，第一個元素的地址為

5、Loca"，那么，第i個元素的存儲地址Loca i = Loca 1+i-1*k。5. 棧stack 是限定在表尾進行插人或刪除操作的線性表。在棧中，允許插人和刪除操作的一端稱為棧頂，而另一端稱為棧底6. 一個循環(huán)隊列 Q中，頭指針和尾指針分別為Q.front和Q.rear ,且最大隊列長度為MaxQSize,那么判斷隊空的條件為 Q.rear=Q.front, 判斷隊滿的條件為Q.rear+1%MaxQSize=Q.front。隊列的長度為.rear-Q.front+MaxQSize %MaxQSize三、程序填空題(每空3分，共30分)1在帶頭結點的單鏈表L中第i個數(shù)據(jù)元素之前插

6、入數(shù)據(jù)元素e的C語言描述算法如下，其中完成其功能。typedef struct nodeint data ；struct node *n ext ；li nkn ode,*l ink；int List In sert_L(li nk & L, i nt i, i nt e) Linknode *p ； int j ；P = L ； j = 0；while (p && j < i-1) p= ； +j ； II 尋找第i-1 個結點if 仲 | j > i-1) return 0；s=(link)malloc(sizeof(linknode)； II 生成新結

7、點 ss->data = e ；s->next=p->next； p->next = s ； II 插入 L 中return 1； 2.對順序棧的C語言描述算法如下，其中top為棧頂指針，請?zhí)畛渌惴ㄖ袠顺龅目瞻滋?，插入元?define STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10typedef structchar *base;char *top;int stacksize;SqStack;L為鏈表頭結點指針。請?zhí)畛渌惴ㄖ袠顺龅目瞻滋?e為新的棧頂元素。int Push( SqStack &S, char e) I

8、Iif ( (s II 棧滿，追加存儲空間S.base=(SElemType *)realloc(S.base,S.stacksize+STACKINCREMENT) *sizeof(SElemType) if (! S.base) return 0；S.top = s.base+s.stacksize； II修改棧頂指針S.stacksize += STACKINCREMENT ；*s.top+=e； II 插入元素return 1；3.對鏈隊列的C語言描述算法如下，請?zhí)畛渌惴ㄖ袠顺龅目瞻滋?，刪除隊列Q的隊頭元素并用typedef struct QNodeQElemType data ；st

9、ruct QNode *n ext；QNode, *QueuePtr ；e返回其值。typedef struct QueuePtr frontQueuePtr rearLin kQueue ；int DeQueue(L in kQueue &Q, QElemType &e) Linknode *p ；if( Q.front=Q.rear ) retrun 0； II 隊列空，返回p = Q.front -> n ext；e = p->data ；Q.front -> next=p->next； II 修改指針if(Q.rear=p) Q.rear= Q.

10、front； II 隊列只有一個元素的情況free(p)； II釋放結點空間return 1；三、算法設計與分析題(每題 10 分，共 20 分)1、簡述以下算法實現(xiàn)的功能： (每題 5 分，共 10 分)( 1) typedef struct LNodeChar data;struct LNode *next;LNode,*LinkList;LinkList Demo(LinkList &L) / L 是無頭結點單鏈表LNode *Q,*P;if(L&&L->next)Q=L; L=L->next; P=L;while (P->next) P=P-&

11、gt;next;P->next=Q; Q->next=NULL;return L;/ Demo答：將單鏈表的第一個結點刪除，放到鏈尾。(2)#define STACK_INIT_SIZE100#define STACKINCREMENT10typedef struct int *base;int *top;int stacksize; Stack;void Demo1( Stack &S, int m) Stack T; int i;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ù)元素2. 有一個帶頭結點的單鏈表，頭指針為head，編寫一個算法計算所有數(shù)據(jù)域為X的結點的個數(shù)(不包括頭結點)