一、判断题
1、n个元素依次进栈，则出栈序列有n（n+1）/2 -1种。( ) 2、数据的存储结构是数据及其逻辑结构在计算机中的物理表示。( ) 3、单链表是随机存取的存储结构。( )
4、栈是特殊的线性表，它的插入和删除分别在线性表的两端进行。( ) 5、线性表的链接存储其逻辑顺序与物理顺序总是一致的。（ ） 6、稀疏距阵压缩存储后，必会失去随机存取功能。（ ） 7、栈可以作为实现过程调用的一种数据结构。( ) 8、循环队列中至少有一个数组空间是空闲的。（ ）
9、算法的时间复杂度都要通过算法中的基本语句的执行次数的数量级来确定。( ) 10、因为随时可以对数组进行存取访问，所以数组是随机存取结构。( )
二、填空题
1、在数据结构中，从逻辑关系上可以把数据结构分成 集 合、 、 、 。
2、设一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的退栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为______ 。
3、循环队列的引入是为了克服______ _，判断循环队列为满的条件是 。
4、设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个地址空间，则元素A[8][5]的存储地址为________________。
5、在一个长度为n的顺序表中，在第i个位置插入一个元素，则需要移动始关键字 个元素。 6、设单链表中指针p指向结点A，要删除A的后继结点(若存在)，则修改指针的操作为__ _____。 7、二维数组A［10］［20］, 采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［5］［6］的地址为 。
8、算法有五个特性，分别是 。 9、稀疏矩阵的压缩存储方法有两种，分别是 和 。
10、一个具有n个结点的单链表，在p所指结点后插入一个新结点的时间复杂度为 ，在给定值为x的结点后插入一个新结点的时间复杂度为 。
三、选择题
1．线性表的顺序存储结构是一种( )的存储结构。
A．随机存取 B.顺序存取 C.索引存取 D.散列存取 2. 假设有两个串A和B，求B在A中首次出现的位置的操作，我们称为（ ）。
A.连接 B.模式匹配 C.求子串 D.求串长 3．循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( ) 。
A. rear=rear+1 B. rear=(rear+1)％(m-1) C. rear=(rear+1)％m D. rear=(rear+1)％(m+1) 4. 元素的进栈次序为a，b，c，d，e，则出栈中不可能的序列是（ ）。
A. a，b，c，d，e B. b，c，d，e，a C. e，a，b，c，d D. e，d，c，b，a 5. 从逻辑上可以把数据结构分为（ ）。
A. 动态结构、静态结构 B. 顺序结构、链式结构 C. 线性结构、非线性结构 D. 初等结构、构造型结构
第 1 页 共 4 页
6. 若线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一元素，则采用（ ）存储方法最节省时间。
A. 单链表 B. 带头指针的单循环链表 C. 双链表 D. 带尾指针的单循环链表
7. 若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（ ）。
A. 1和5 B. 2和4 C. 4和2 D. 5和1
8．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（ ）。
A. q→next=s；p→next=s； B. q→next=s；s→next=p； C. q→next=s；q→next=p； D. q→next=s；s→next=q 9．数据结构是（ ）
A．数据的存储结构 B．一组性质相同的数据元素的集合
C．一种数据类型 D．相互之间存在一种或多种特定关系的数据元素的集合 10. 在一个单链表中，若p结点不是最后结点，在p之后插入s结点，则实行( )。 A. s->next=p；p->next=s; B. s->next=p->next; p->next=s； C. s->next=p->next; p=s; D. p->next=s; s->next=p; 11．下面程序段的时间复杂度为( )。
k=1;
for（i=0；i A. O（n） B. O（n） C. O（2n） D. O（1） 12. 设循环队列的元素存放在一维数组Q[0‥30]中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（ ）。 A.Q[4] B.Q[5] C.Q[14] D.Q[15] 13．以下关于链式存储结构的叙述中，不正确的的（ ）。 A．结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B．逻辑上相邻的结点物理上不必邻接 C．可以通过计算直接确定第i个结点的存储地址 D．插入、删除操作方便，不必移动结点 14．下面说法不正确的是（）。 A． 数组是一种线性结构 B．数组是一种定长的线性结构 C． 除了插入和删除操作外，数组的基本操作还有存取、修改检索和排序 D．数组的基本操作还有存取、修改检索和排序等，没有插入和删除操作 15.设线性表有n个元素，以下操作中，（ ）在顺序表上实现比在链表上实现的效率更高。 A输出第i个元素值 B交换第一个和第二个元素的值 C顺序输出所有n个元素 D查找与给定值x相等的元素在线性表中的序号 2 四、综合应用题（本题共5小题，共计30分）。 1. 简述下面算法的功能，答案写在算法的右侧：（4分） void algo1(Stack &S, int e) { Stack T; int d;initstack(T); while (!StackEmpty(S)) { Pop(s,d); if(d!=e) Push(T,d);} 第 2 页 共 4 页 while (!stackEmpty(T)) { Pop(T,d); Push(S,d);}} 2. 写出下列程序段的输出结果（队列中的元素类型Qelemtype 为char）（4分）： void algo2( ) { Queue Q;initQueue（Q）; Char x=’e’,y=’c’; EnQueue(Q,’h’); EnQueue(Q,’r’);EnQueue(Q, y ); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, ‘a’); While (!QueueEmpty(Q)) {DeQueue(Q,y);printf(y);} Printf(x)} 3、设s=“I AM A STUDENT”,t=“GOOD”，q=“WORKER”求strlength（s）；substring（s，8,7）；index（s，’A’）；index（s，t）；replace（s，“STUDENT”，q）； concat（substring（s，6,2），concat（t，substring（s，7,8）））.（6分） 4． 编写算法：设单链表L以升序排列，设计算法实现在单链表中删除值相同的多余结点。 （8分） L /// 5 12 12 5 以不带附加表头的循环单链表来表示队，仅设尾指针rear（指向尾元素），写出入队或出队算 法。（8分） 第 3 页 共 4 页 90 ∧