数据结构期中试卷_答案
《数据结构》期中试卷
学号：姓名：分数：
一、填空题（每空1.5分，共15分）
1、根据数据元素之间关系的不同特性，数据结构包含4类基本结构：集合
、线性结构、树形结构、图状(网状)结构。
2、具有“逻辑上相邻的数据元素在计算计中的存储位置也相邻”这样一种存储结构的线性表称为顺序表。
3、线性表链式存储结构中的结点包含两个部分。其中，存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。
4、在线性表的链式存储结构中，将表中最后一个结点的指针域指向头结点，使整个链表形成一个环，则该链表被称为循环链表。
5、栈存取元素的特点是后进先出(先进后出)；队列存取元素的特点是：先进先出(后进后出)。
二、写出下列程序段的输出结果（每题10分，共10分）
void main(){
Stack S; Queue Q; char x , y; InitStack(S);
InitQueue(Q); x = ‘u’; y = ‘r’;
EnQueue(Q, x); Push(S, ‘C’); EnQueue(Q,‘t’);
DeQueue(Q, x); Push(S, x); EnQueue(Q, x);
GetHead(Q,x); Push(S, x); Pop(S, x); EnQueue(Q, y);
Push(S, y); Push(S, x); EnQueue(Q, ‘e’); Push(S, ‘s’);
while(!StackEmpty(S)) {Pop(S, y); Printf(y);}
while(!QueueEmpty(Q)) {DeQueue(Q, y); Printf(y);}
}
输出结果: Structure
三、分析题（每题15分，共15分）
若进栈序列为ABCD，写出所有具有合理出栈顺序的出栈序列。
ABCD ABDC ACBD ACDB ADBC ADCB
BACD BADC BCAD BCDA BDAC BDCA
CABD CADB CBAD CBDA CDAB CDBA
DABC DACB DBAC DBCA DCAB DCBA
四、程序填空题（每空4分，共20分）
1、在顺序线性表L中删除第i个元素并用e返回。
Status ListDelete_Sq(SqList &L, int i, ElemType &e){ if(i <1 || i > L.length) return ERROR;
p = &L.elem[i-1]; e = *p; q= &L.elem[L.length-1] ;
for(++p ; p<=q ; p++) *(p-1) = *p;
--L.length; return OK; }
2、在带头结点的单链线性表L中第i个位置之前插入元素e
Status ListInsert_L(LinkList &L, int i, ElemType e){
j = 0; p = L;
while( p && j < i - 1) { p=p->next; j++; }
if( !p || j > i-1) return ERROR;
s = ( LinkList ) malloc ( sizeof ( LNode ));
s -> data = e ;
s->next = p->next; p->next =s ;
return OK; }
五、编程题（每题10分，共40分）
1、写一算法在带头结点的单链表结构上实现线性操作ListLength(L);
Status ListLength_L(LinkList L){
j = 1;
p = L->next;
while( p ) { p = p -> next; j++; }
return j-1;
}
2、编程实现十进制数转换成二进制数。
Void conversion(){
InitStack(S); scanf(“%d”,N);
while(N) { Push(S, N %2); N = N /2; }
while(!StackEmpty(S)) { Pop(S,e); Printf(“%d”,e); }
}
3、编程实现删除队列S中元素值为e的元素（借助辅助队列）。
Status QueueDelete(Queue S, QElemType e){ Queue T; InitQueue(&T);
while(!QueueEmpty(S))
{ DeQueue(S,x); if(x != e) EnQueue(T,x);}
whiel(!QueueEmpty(T))
{ DeQueue(T,x); EnQueue(S,x);}
4、编程实现队列中元素的逆置（借助辅助栈）
Status QueueInverse(Queue Q){
Stack S; InitStack(&S);
while(!QueueEmpty(Q))
{ DeQueue(Q,x); Push(S,x);}
whiel(!StackEmpty(S))
{ Pop(S,x); EnQueue(Q,x);}