第Ⅰ部分 选择题
一、单项选择题(在每小题列出的四个备选项中只有一个是符合题目要求的)10. 设栈S和队列Q的初始状态为空，元素e
1，e
2，e
3，e
4，e
5和e
6依次通过栈S，元素退栈后即进入队列Q，若6个元素的出队序列是e
2，e
4，e
3，e
6，e
5，e
1，则栈S的容量至少为______
A B C D
D
[考点] 栈和队列的特点
[解析] 栈后进先出，队列先进先出。
第Ⅱ部分 非选择题
二、填空题1. 从宏观上看，数据组织应分成三个不同的层次，即数据、______和数据项。
数据元素
[考点] 数据组织的三个不同层次
[解析] 数据组织应分为三个不同的层次，即数据、数据元素、数据项。
2. 在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向______和______。
直接前驱 直接后继
[考点] 双链表的存储结构
[解析] 在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向直接前驱和直接后继。
3. 根据数据元素之间关系的不同特性，通常有______、______、______、______四类基本逻辑结构，它们反映了四类基本的数据组织形式。
集合 线形 树形 图形
[考点] 逻辑结构的类别
[解析] 根据数据元素之间关系的不同特性，通常有集合、线形、树形、图形四类基本逻辑结构，它们反映了四类基本的数据组织形式。
4. 在表长为n的顺序表上做删除运算，平均要移动的结点个数为______。
(n-1)/2
[考点] 队列的概念
[解析] 在表长为n的顺序表上做删除运算，平均要移动的结点个数为(n-1)/2。
5. 队列又称为______的线性表。
先进先出
[考点] 线性表的删除
[解析] 队列又称为先进先出的线性表。
6. 线性表常见的链式存储结构有单链表、______和______，其中最简单的是单链表。
循环链表 双向循环链表
[考点] 线性表的链式存储结构
[解析] 线性表常见的链式存储结构有单链表、循环链表和双向循环链表，其中最简单的是单链表。
7. 顺序表定位运算又称作______，其基本操作是______。
按值查找 比较
[考点] 线性表的定位
[解析] 顺序表定位运算又称作按值查找，其基本操作是比较。
8. 单链表中，增加头结点的目的是为了______。
方便算法的实现
[考点] 单链表中头结点的作用
[解析] 单链表中增加头结点的目的是为了方便算法的实现。
9. 栈中的数据元素已经填满了，如果再进行栈操作，会发生______。为了防止数据丢失，在进栈操作之前应该判断是否栈满。
上溢
[考点] 进栈操作易出现的现象
[解析] 栈中的数据元素已经填满了，如果再进行栈操作，会发生上溢。为了防止数据丢失，在进栈操作之前应该判断是否桟满。
10. 在栈中，可进行插入和删除操作的一端称为______，另一端称为______。
栈顶 栈底
[考点] 栈的基本概念
[解析] 在栈中，可进行插入和删除操作的一端称为栈顶，另一端称为栈底。
11. 在队列中，新插入的结点只能添加到______，被删除的只能是排在______的结点。
队列尾 队列首
[考点] 队列的插入和删除操作
[解析] 在队列中，新插入的结点只能添加到队列尾，被删除的只能是排在队列首的结点。
12. 如果值相同的元素或者零元素在矩阵中的分布有一定规律，称此类矩阵为______。
特殊矩阵
[考点] 特殊矩阵的定义
[解析] 如果值相同的元素或者零元素在矩阵中的分布有一定规律，称此类矩阵为特殊矩阵。
13. 对称矩阵中有近半的元素可以通过其对称元素获得，若为每一对元素只分配一个存储空间，则可将n
2个元素压缩存储到______个元素的存储空间中。
n(n+1)/2
[考点] 对称矩阵的压缩存储
[解析] 对称矩阵中有近半的元素可以通过其对称元素获得，若为每一对元素只分配一个存储空间，则可将n2个元素压缩存储到n(n+1)/2个元素的存储空间中。
三、应用题1. 有一个整数序列，其输入顺序为20，30，90，-10，45，78，试用栈将其输出序列变为30，-10，45，90，78，20。请给出该整数序列进栈和出栈的操作步骤(可用push(x)表示x进栈，pop(x)表示x出栈)。
push(20)，push(30)，pop(30)，push(90)，push(-10)，pop(-10)，push(45)，pop(45)，pop(90)，push(78)，pop(78)，pop(20)。
[考点] 栈的存取原则是后进先出
2. 顺序存储结构与链式存储结构是什么关系?
顺序存储结构是指存储结点存放在一个连续的存储区里，利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。
链式存储结构是指每个存储结点除了含有一个数据元素之外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。
[考点] 数据元素之间的主要关联结构，即顺序存储结构和链式存储结构之间的关系
3. 简述双向循环链表插入运算的关键步骤(即在p所指结点的后面插入一个新结点*t，写出需要修改的四个指针)。
(1)t-＞prior=p;
(2)t-＞next=p-＞next;
(3)p-＞next-＞prior=t;
(4)p-＞next=t;
[考点] 双向循环链表插入运算的关键步骤(指针的修改)
4. 试编写在带头结点的单链表上实现线性表基本运算定位和删除的算法。
(1)定位
在带头结点的单链表上实现的算法为：
int LocateLiklis(LinkListhead, Data Type x)
//求表head中第一个值等于x的结点的序号，若不存在这种结点，返回结果为0
{
Node * p=head; //p是工作指针
p=p-＞next; //初始时p指向首结点
int i=0; //i代表结点的序号，这里置初值为0
while(p!=NULL&&p-＞data!=x) //访问链表
{i++;
p=p-＞next;
}
if(p!=NULL) return i+1;
else return 0;
}
(2)删除
在带头结点的单链表上实现的算法为：
void DeleteLinklist(LinkList head,int i) //删除表head的第i个结点
{Node * q;
if(i==o)q=head;
else q=GetLinklist(head,i-1) //先找待删结点的直接前驱
if(q!==NULL&&q-＞next!=NULL) //若直接前驱存在且待删结点存在
{
p=q-＞next; //p指向待删结点
q-＞next=p-＞next; //移出待删结点
free(p); //释放已移出结点p的空间
}
else exit("找不到要删除的结点"); //结点不存在
}
[考点] 带头结点单链表定位和删除运算的关键步骤(指针的修改)
5. 设循环队列的容量为40(序号从0～39)，现经过一系列的入队和出队运算后，有(1)front=11，rear=19；(2)front=19，rear=11；问这两种情况下循环队列中的元素各有几个?
(1)(rear-front+max)% max=(19-11+40)%40=8
(2)(rear-front+max)% max=(11-19+40)%40=32
[考点] 循环队列的存取规则
四、算法设计题1. 在一单链表中，存在多个结点，其数据值均为50，试写一个算法统计该类结点的个数。
int count(head)
{
Node * head;
int n=0; //初始化值为50的结点个数
p=head;
while(p!=NULL)
{
if(p-＞data==50)n++;
p=p-＞next;
}
return(n);
{
2. 假设一个算术表达式中可包含两种括号：“(”，“)”；“[”，“]”，且这两种括号可按任意的次序嵌套使用。试用栈的运算编写判断给定表达式中所含括号是否正确配对出现的算法(可设表达式已存入字符型数组中)。
设表达式已存入字符数组A[n]中：
void prool(A[n])
{IntStack(s);
i=0;flag=true;
while((i＜n)&&flag)
{if((A[i]=='(')||(A[i]=='['])
Push(s,A[i]);
else if((A[i]==')')||(A[i]==']')
if(EmptyStack(s)) flag=false;
else
{x=GetTop(s);
Switch(A[i])
case')':if(x=='(') Pop(s);
else flag=false;
break;
case']':if(x=='[') Pop(s);
else flag=false;
}
}
i++;
}
}
[考点] 栈的存取原则的应用
深色：已答题 浅色：未答题