广东外语外贸大学计算机科学与技术系和软件工程系2005级
数据结构课程期中试卷
班级：__________学号：_________________姓名：____________成绩：____________
一、判断题 请在题后括号内打上√（正确）或○（错误）(共25分 每空2.5分) 1．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（ ）
2. 在对带头结点的链队列作出队操作时，头指针的值不会改变。（ ） 3．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1,2,3,4, 为了得到1,3,4,2出栈顺序相应的S和X操作序列为SXSSXSXX。（ ）
4. 在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（ ）
5. 顺序存储的线性表可以按序号随机存取。( )
6. 带头结点的单链表队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点（ ）
7．空串是由空白字符组成的串。（ ）
8．字符串比较‘ABCDEFG’>‘ABF’的结果为 （ ）
9．顺序栈插入、删除操作都是在同一端的进行，该端称为堆底。（ ） 10．给定循环链表中任一元素的地址均可得到其直接前驱的地址（ ）
二、单选题 (共24分 每空3分)
1. 数据结构是一门研究非数值计算的程序设计问题中计算机的（ ）以及它们之间的关系和运算等的学科。
A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象
2. 设单链表中指针p指向结点m ，若要删除m之后的结点（若存在），则需修改指针的操作为（ ）。
A. p->next=p->next->next; B. p=p->next; C. p=p->next->next; D. p->next=p;
3. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表 4．下面程序段的时间复杂度是( )。 for (i=1;i<=n;i++) for (j=i;j<=n;j++) s+=B[i][j]; A. n B. n
2
C. 1 D.
n
5．带头结点的单链表head为空的判定条件是 ( )。 A. head = = NULL; B. head->next = = NULL; C. head->next = = head; D. head! = NULL;
6. 在循环双链表的p所指结点之后插入s所指结点的操作是 ( )。 A. p->right=s; s->left=p; p->right->left=s; s=->right=p->right; B. p->right=s; p->right->left=s; s->left=p; s->right=p->right; C. s->left=p; s->right= p->right; p->right=s; p->right->left=s; D. s->left=p; s->right=p->right; p->right->left=s; p->right=s; 7．假设顺序栈的定义为：
typedef struct {
selemtype *base; /* 栈底指针*/
selemtype *top; /* 栈顶指针*/
int stacksize; /* 当前已分配的存储空间,以元素为单位*/ }sqstack;
变量st为sqstack型，则栈st为满的判断条件为（ ）。
A． st.base == NULL B． st.top == st.stacksize C． st.top-st.base>=st.stacksizeD． st.top == st.base
8．判断一个循环队列QU ( m为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 为空队列的条件是( )。 A．QU->front == QU->rear B．QU->front != QU-> rear
C．QU->front == (QU->rear+1) % mD．QU->front != (QU->rear+1) % m
三、算法设计题 (共51分)
1. (共20分 )已知Q是一个非空队列，S是一个空栈。仅用队列和栈的基本操作函数和少量工作变量，编写一个算法，将队列Q中的所有元素逆置。 栈的基本操作函数有： clearstack(&s); 置空栈 push(&s,e); 新元素e进栈
pop(s,&e):出栈，返回栈顶值给e stackEmpty(s): 判栈空否 队列的基本操作函数有
enqueue(&q,e); 元素e进队
dequeue(&q,&e):出队列，返回队头值给e queueempty(q): 判队列空否
2．(共31分 ) 设有一个带头结点，由正整数组成的无序单链表，头指针为L， Typedef struct Lnode{ int data;
struct Lnode *next; }Lnode,*Linklist; Linklist L;
给出完成下列功能的算法：
①找出最小值结点，且打印该数值；（15分）
②若该数值是奇数，则将其与直接后继结点（若存在）的数值交换；（8分） ③若该数值是偶数，则将其直接后继结点（若存在）删除；（8分）
参考答案： 一、
1F 2T 3T 4T 5T 6F 7F 8F 9F 10T 二、
1A 2A 3D 4B 5B 6D 7C 8A 三、
aaa(q,s) {
0
0
0
clearstack(s)
while(!queueempty(q)) {
dequeue(q,e); push(s,e); }
while(!stackempty(s)) {
pop(s,e);
enqueue(q,e); } } 四、
bbb(Linklist L) {
q=L->next;
if(!q) return ; p=q->next; while(p) {
if(p->data < q->data)q=p; p=p->next; }
printf(q->data); m=q->next;
if(!m) return; if(q->data%2==1) { temp=q->data; q->data=m->data; m->data=temp; } else
{ q->next=m->next; free(m);} }
