一、选择题单选
1．从物理结构上可以把数据结构分为（B ）两大类。
A．动态结构、静态结构 B．顺序存储结构、链式存储结构
C．线性结构、非线性结构 D．基本结构、构造结构
2．下述哪一条是顺序存储结构的优点？（ A ）
A．物理上相邻的元素在逻辑上也相邻 B．插入运算方便
C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
3．下面关于线性表的叙述中，错误的是哪一个？（ B）
A．线性表采用顺序存储，必须占用一段连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链式存储，不必占用一片连续的存储单元。
D．线性表采用链式存储，便于进行插入和删除操作。
4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
5．6个元素按照6，5，4，3，2，1的顺序进栈下列,哪一个不是合法的出栈序列？（C)
A. 5，4，3，6，1，2 B. 4，5，3，1，2，6
C. 3，4，6，5，2，1 D. 2，3，4，1，5，6
6. 一个递归算法必须包括（ D ）。
A. 递归部分 B. 终止条件和递归部分
C. 循环部分 D. 终止条件和循环部分
7. 执行完下列语句段后，i值为：（ B ）
int f(int x) {
return ((x>0) ? x* f(x-1):2);
}
int i ;
i =f(f(1));
A．2 B. 4 C. 8 D. 无限递归
8． 若用front和rear分别表示循环队列的队头元素和队尾元素在数组中的下标，则队列为空时有（C ）。
A. rear=front-1 B. rear=front+1
C. rear=front D. 不能确定
9. 栈和队都是（ C ）
A．顺序存储的线性结构 B. 链式存储的非线性结构
C. 限制存取点的线性结构 D. 限制存取点的非线性结构
二选择题单选
1．数据结构是一门研究非数值计算的程序设计问题中计算机的A以及它们之间的B和运算等的学科。
①A．操作对象 B．计算方法 C．逻辑存储 D．数据映象
②A．结构 B．关系 C．运算 D．算法
2．数据结构被形式地定义为（K，R），其中K是B的有限集合，R是K上的D的有限集合。
①A．算法 B．数据元素 C．数据操作 D．逻辑结构
②A．操作 B．映象 C．存储 D．关系
3．在数据结构中，从逻辑上可以把数据结构分成C。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构
C．线性结构和非线性结构 D．内部结构和外部结构
4．线性表的顺序存储结构是一
种B的存储结构，线性表的链式存储结构是一种C的存储结构。
A．随机存取 B．顺序存取 C．索引存取 D．散列存取
5．算法分析的目的是A，算法分析的两个主要方面是A。
①A．找出数据结构的合理性
B．研究算法中的输入和输出的关系
C．分析算法的效率以求改进
D．分析算法的易懂性和文档性
②A．空间复杂性和时间复杂性
B．正确性和简明性
C．可读性和文档性
D．数据复杂性和程序复杂性
6． 在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为B
A．逻辑结构 B．顺序存储结构
C．链表存储结构 D．以上都不对
三、填空题
1．数据逻辑结构包括集合、线性和非线性三种类型，树形结构和图形结构合称为非线性。
2．线性结构中元素之间存在一个对一个关系，树形结构中元素之间存在一个对多个关系，图形结构中元素之间存在多个对多个关系。。
3．下面程序段的时间复杂度是O（n3）。
（4）For (I=1; I
For (j=1; j
For (k=1; k
三、简答
1.怎样理解数据结构在计算机课中的核心地位。
为什么要用数据类型来描述数据结构。
2.描述数据结构、逻辑结构、存储结构和运算的有关概念及其相互之间的关系，它们如何影响算法的设计与实现。
3.描述算法所具备的基本特征，并指出算法与程序之间的差异。
第二章 线性表
一、 选择题
1．下述哪一条是顺序存储结构的优点？（ A ）
A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
2．下面关于线性表的叙述中，错误的是哪一个？（B ）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．线性表是具有n个（ C ）的有限序列（n>0）。
A．表元素 B．字符 C．数据元素 D．数据项 E．信息项
4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
5．下面的叙述不正确的是（ BC ）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个
元素的时间同i 的值成正比
D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( C )最节省时间。
A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表
7．链表不具有的特点是（ B ）
A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
8．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ B ）。
A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;
9．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ）
A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL
10．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。
A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
11．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（C ）
A．O（i） B．O（1） C．O（n） D．O（i-1）
12．循环链表h的尾结点p的特点是（ A ）
A．p→next=h B．p→next=h->next C．p=h D．p=h->next
13．完成在双循环链表结点p之后插入s的操作是（ D ）
A． p->next=s ; s->priou=p; p->next->priou:=s ; s->next=p->next;
B． p->next->priou=s; p->next=s; s->priou=p; s->next:=p->next;
C．s->priou=p; s->next:=p->next; p->next=s; p->next->priou=s ;
D．s->priou=p; s->next:=p->next; p->next->priou=s ; p->next=s;
14．双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（D ）（链中结点数大于2，p不是第一个结点）
A．p->llink->rlink=p->llink; p->llink->rlink=p->rlink; dispose(p);
B．dispose(p); p->llink->rlink=p->llink; p->llink->rlink=p->rlink;
C．p->llink->rlink=p->llink; dispose(p); p->llink->rlink=p->rlink;
D．以上A，B，C都不对。
二、填空
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序______存储结构。
2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_n-1／2_。
4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动__n-i+1______个元素。
5．在单链表中设置头结点的作用是__便于写算法
6．对于一个具有n个结点的单链表，在已知的结点*p
后插入一个新结点的时间复杂度为__O（1)______,
在给定值为x的结点后插入一个新结点的时间复杂度为__O(n)______。
7．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成__单链表______和_双链表______；而又根据指针的连接方式，链表又可分成_单项链表______和__双向链表______。
8. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：
s->next=p； s->prior=__p->prior______；p->prior=s；_p->prior->next_______=s；
9.顺序存储结构是通过_元素在存储器中的相对位置__表示元素之间的关系的;链式存储结构是通过_元素存储地址的指针_______表示元素之间的关系的。
10. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _4_____个，单链表为____2___个。
11. 循环单链表的最大优点是：_从表中任意一点出发均可找到表中其他结点_______。
12. 带头结点的双循环链表L中只有一个元素结点的条件是：__L- >next->next==null______
13. 在单链表L中，指针p所指结点有后继结点的条件是：p->next!=null
14. 带头结点的双循环链表L为空表的条件是：L->NEXT==NULL
三. 算法设计题
1． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
3. 已知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。
4. 顺序存储结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类C语言给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。
5. 设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。编一类C过程，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。程序中不得使用 NEW过程申请空间。
6. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。
7. 已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。
8. 已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链
表A插入到单链表B的第j个元素之前。
第三章 栈和队列
一 选择题
1. 对于栈操作数据的原则是（ B ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
2. 在作进栈运算时,应先判别栈是否( ①B ),在作退栈运算时应先判别栈是否( ②A )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③B )。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④D )分别设在这片内存空间的两端,这样,当( ⑤C)时，才产生上溢。
①, ②: A. 空 B. 满 C. 上溢 D. 下溢
③: A. n-1 B. n C. n+1 D. n/2
④: A. 长度 B. 深度 C. 栈顶 D. 栈底
⑤: A. 两个栈的栈顶同时到达栈空间的中心点.
B. 其中一个栈的栈顶到达栈空间的中心点.
C. 两个栈的栈顶在栈空间的某一位置相遇.
D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.
3. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ C ）。
A. i-j-1 B. i-j C. j-i+1 D. 不确定的
4. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ D ）。
A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b
5. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ B ）
A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop
6. 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( C )。
A．top=top+1; V [top]=x B. V [top]=x; top=top+1
C. top=top-1; V [top]=x D. V [top]=x; top=top-1
7. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ D ）。
A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2]
8. 栈在（ D ）中应用。
A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ
9. 一个递归算法必须包括（ D ）。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分
10. 执行完下列语句段后，i值为：（ B ）
int f(int x)
{ return ((x>0) ? x* f(x-1):2);}
int i ;
i =f(f(1));
A．2 B. 4 C. 8 D. 无限递归
11. 表达式a*(b+c)-d的后缀表达式是( B )。
A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd
12. 设计一个判别表达式中左，右括
号是否配对出现的算法，采用（ D ）数据结构最佳。
A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈
13. 用链接方式存储的队列，在进行删除运算时（ D ）。
A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
14. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( A )。
A．仅修改队头指针 B. 仅修改队尾指针
C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改
15. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。
A．队列 B．多维数组 C．栈 D. 线性表
16. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。
A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m
17. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
18. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（ E ）。
A. dacb B. cadb C. dbca D. bdac E. 以上答案都不对
19. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ A ）。
A. (rear+1) MOD n=front B. rear=front
C．rear+1=front D. (rear-l) MOD n=front
20. 栈和队列的共同点是（C ）。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
21. 栈和队都是（ C ）
A．顺序存储的线性结构 B. 链式存储的非线性结构
C. 限制存取点的线性结构 D. 限制存取点的非线性结构
22. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。
A． 6 B. 4 C. 3 D. 2
三 填空题
1．栈是_运算受限______的线性表，其运算遵循__后进先出_____的原则。
2．__栈_____是限定仅在表尾进行插入或删除操作的线性表。
3. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是__2,3_____，而栈顶指针值是__1012_____H。设栈为顺序栈，每
个元素占4个字节。
4. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为__1_____，栈2空时 ，top[2]为__n_____，栈满时为_top[1]=top[2]______。
5．两个栈共享空间时栈满的条件_______。
6．在作进栈运算时应先判别栈是否_为满_;在作退栈运算时应先判别栈是否_为空_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_n_。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_栈底_分别设在内存空间的两端，这样只有当_(5)_时才产生溢出。
7. 多个栈共存时，最好用__顺序存储结构_____作为存储结构。
8．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_23 12 3*2-4/34 5 7/*++108 9/+____。
9. 循环队列的引入，目的是为了克服_假设______。
10. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_s->next=null；_f->next=x__r=s___。
11．区分循环队列的满与空，只有两种方法，它们是_另设一标志位_____和__少用一个元素空间____。
12. 设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为_sq.front-1______，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_(sq.rear+1)_%M_____。
13．表达式求值是___栈____应用的一个典型例子。
四 应用与算法设计题
应用题:
1.（1） 什么是递归程序？
（2） 递归程序的优、缺点是什么？
（3） 递归程序在执行时，应借助于什么来完成？
（4） 递归程序的入口语句、出口语句一般用什么语句实现？
2. 举例说明顺序队的“假溢出”现象，并给出解决方案。
算法设计题:
1. 设从键盘输入一整数的序列：a1, a2, a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。
2. 如果允许在循环队列的两端都可以进行插入和删除操作。要求：
（1）写出循环队列的类型定义；
（2）写出“从队尾删除”和“从队头插入”的算法。