此文档为国家211工程院校,北京化工大学,计算机专业《数据结构》课程期末考试题及参考答案

北京化工大学2013——2014学年第一学期 《数据结构》期末考试A卷试题参考答案

课程代码

C

S

E

2

1

6

C

班级： 姓名： 题号 得分

一

二

三

学号：

四

五

分数： 六

七

八

总分

一、（14’）银行排队叫号系统有效缓解了客户排队等待的压力，已知该系统中有一个客户排队序列（List），序

列中每个元素记录了每个客户到达银行的时间（整型数）以及办理业务的类型（字符型）。假设针对该序列的基本操作有：创建序列、客户取号、窗口叫号、销毁序列； 1.请写出此序列的抽象数据类型；（4’） ADT List{ D：每个客户的到达信息 S：客户到达时间的先后关系（线性） P： void CreatList(List *L); // 创建序列 int GetNum(List *L, int time); // 客户取号 int CallNum(List *L); // 窗口叫号 void DestoryList(List *L); // 销毁队列 } ADT List

2.请针对题设序列，给出合适的存储结构的C语言（或C++）描述，并阐明依据；（5’）

typedef struct List{ typedef struct ListNode{

ListNode *front; // 队头 int Num; // 客户序号

ListNode *rear; // 队尾 int time; // 到达时间

int Length; // 队列长度，可以省略 char type; // 客户类型

}List; struct ListNode *next; //链式指针

}ListNode;

存储结构：链式线性表结构； 选择依据：

① 先来先办理，符合线性表中队列先进先出的逻辑结构；

② 客户数量不确定，且主要操作是序列的插入与删除操作，因此链式结构更适合。

3.针对你给出的存储结构，写出“窗口叫号”的代码实现（5’） int CallNum(List *L){ ListNode *p = L->front; int num = 0; if(p){ L->front = p->next; if(L->front == NULL) L->rear = NULL; num = p->Num; free(p); } // end if return num;

} // 函数返回结果：空序列 – 0，否则 – 当前序列第一个序号