數(shù)據(jù)結(jié)構(gòu)期中試卷及答案(共3頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一、選擇題（每小題2分，共30分）1. 數(shù)據(jù)結(jié)構(gòu)是（ D ）。A一種數(shù)據(jù)類型 B數(shù)據(jù)的存儲結(jié)構(gòu)C一組性質(zhì)相同的數(shù)據(jù)元素的集合D相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合 2以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關的術語是（ D ）。A鏈隊列 B. 鏈表 C. 順序表 D. 棧3以下數(shù)據(jù)結(jié)構(gòu)中，（ A ）是非線性數(shù)據(jù)結(jié)構(gòu)A樹 B字符串 C隊 D棧4一個順序存儲線性表的第一個元素的存儲地址是90，每個元素的長度是2，則第6個元素的存儲地址是（B）。 A98 B100 C102 D1065在線性表的下列運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關系的運算是（D）。A插入 B刪除 C排序 D查找6線

2、性表采用鏈式存儲時，其地址(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）。 A3，2，6，1，4，5 B3，4，2，1，6，5 C1，2，5，3，4，6 D5，6，4，2，3，1 9. 若一個棧的輸人序列是1，2，3，n，輸出序列的第一個元素是n，則第k個輸出元素是（C ）。Ak Bn-k-1 Cn-k+1 D不確定10.對于隊列操作數(shù)據(jù)的原則是

3、（ A ）。A. 先進先出 B. 后進先出 C. 先進后出 D. 不分順序11. 棧和隊列的共同點是（ C ）。A. 都是先進先出 B. 都是先進后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點12在一個鏈隊列中，假定front和rear分別為頭指針和尾指針，刪除一個結(jié)點的操作是（ A ）。 Afront=front->next Brear=rear->next Crear->next=front Dfront->nextrear13. 空串與空格串（ B ）。 A相同 B不相同 C可能相同 D無法確定14. 串與普通的線性表相比較，它的特殊性體現(xiàn)在（C ）。

4、 A順序的存儲結(jié)構(gòu) B鏈接的存儲結(jié)構(gòu) C數(shù)據(jù)元素是一個字符 D數(shù)據(jù)元素可以任意15. 串的長度是指（ B ）。A.串中所含不同字母的個數(shù) B.串中所含字符的個數(shù)C.串中所含不同字符的個數(shù) D.串中所含非空格字符的個數(shù)二、填空題（每空2分，共20分）1 線性表、棧和隊列，串都是_線性_結(jié)構(gòu)。2 數(shù)據(jù)的基本單位是_數(shù)據(jù)元素_。3 當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用_順序_存儲結(jié)構(gòu)。4 已知具有n個元素的一維數(shù)組采用順序存儲結(jié)構(gòu)，每個元素占k個存儲單元，第一個元素的地址為Loc(a1)，那么，第i個元素的存儲地址Loc(ai)= Lo

5、c(a1)+(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 )%MaxQSize7 兩個串相等的充分必要條件是 兩個串的長度相等，且各個對應位置的字符都相等 。三、程序填空題（每空3分，共30分）1. 在帶頭結(jié)點

6、的單鏈表L中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e的C語言描述算法如下，其中L為鏈表頭結(jié)點指針。請?zhí)畛渌惴ㄖ袠顺龅目瞻滋?，完成其功能。typedef struct node int data； struct node *next； linknode,*link；int ListInsert_L(link &L, int i, int e) Linknode *p；int j；p = L； j = 0；while (p && j < i-1) p=p->next ； +j； / 尋找第i-1個結(jié)點if (!p | j > i-1) return 0； s=(l

7、ink)malloc(sizeof(linknode) ；/ 生成新結(jié)點ss->data = e； s->next=p->next ； p->next = s； / 插入L中return 1； 2. 對順序棧的C語言描述算法如下，其中top為棧頂指針，請?zhí)畛渌惴ㄖ袠顺龅目瞻滋帲迦朐豦為新的棧頂元素。#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct char *base; char *top; int stacksize; SqStack;int Push( SqStack &

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

9、元素并用e返回其值。typedef struct QNode QElemType data； struct QNode *next； QNode, *QueuePtr； typedef struct QueuePtr front； QueuePtr rear； LinkQueue；int DeQueue(LinkQueue &Q, QElemType &e) Linknode *p； if( Q.front=Q.rear ) retrun 0；/隊列空，返回 p = Q.front -> next； e = p->data； Q.front -> next=p

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

11、;if(L&&L->next)   Q=L; L=L->next; P=L; while (P->next) P=P->next;   P->next=Q; Q->next=NULL;   return L;/ Demo答：將單鏈表的第一個結(jié)點刪除，放到鏈尾。（2）#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef 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.有一個帶頭結(jié)點的單鏈表，頭指針為head，編寫一個算法計算所有數(shù)據(jù)域為X的結(jié)點的個數(shù)（不包括頭結(jié)點）。typedef