数据结构期中试卷_答案

《数据结构》期中考试题答案一、填空题（20分，每题2分）1.逻辑结构、存储结构2.便于插入和删除操作3.方便运算的实现4.算法执行过程中所需要的基本运算次数5.存储结构6.q.next=p.next ； p.next=q7．递归算法8.抽象类或接口二、选择题（30分，每题2分）AACBB BDDCB AACAC三、问答题（50分，每题10分）1.什么是栈和队列？两者有何异同？答：栈和队列都属于线性表结构，它们是两种特殊的线性表，栈的插入和删除操作都在线性表的一端进行，所以栈的特点是“后进先出”；而队列的插入和删除操作分别在线性表的两端进行，所以队列的特点是“先进先出”。

2.采用顺序存储结构的栈和队列，在进行插入、删除操作时需要移动数据元素吗？为什么？答：采用顺序存储结构的栈和队列，在进行插入、删除操作时不需要移动数据元素，因为栈和队列均不能进行中间插入、删除操作。

3.什么是队列的假溢出？为什么顺序存储结构队列会出现假溢出？怎样解决队列的假溢出问题？链式存储结构队列会出现假溢出吗？答：顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列尾下标越界，数据溢出。

此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出并不是因存储空间不够而产生的，称之为假溢出。

顺序队列之所以会产生假溢出现象，是因为顺序队列的存储单元没有重复使用机制。

解决的办法是将顺序队列设计成循环结构。

链式存储结构队列不会出现假溢出。

因为每次元素入队，都要申请新结点，数据不会溢出。

4.答案：(1) (a2, a4, …, ) (2)将单链表中偶数结点位置的元素值写入顺序表list5.数据的存储结构有哪两种，各有什么特点？答：数据存储结构的基本形式有两种：顺序存储结构和链式存储结构。

顺序存储结构使用一组连续的内存单元依次存放数据元素，元素在内存中的物理存储次序与它们的逻辑次序相同。

链式存储结构使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，数据元素间的关系需要采用附加信息特别指定。

1、每一行执行的频度void MatrixMultiply( int A[n][n], int B[n][n], int C[n][n] ){for (i = 0; i < n; i++ )for (j = 0; j < n; j++ ) {C[i][j] = 0;for ( k = 0; k < n; k++ )C[i][j] = C[i][j] + A[i][k] * B[k][j];}}2、求@语句频度3、顺序表的结构体定义#define LIST_INIT_SIZE 100 //初始分配量#define LISTINCREMENT 10 //分配增量type struct{ElemType *elem; //存储空间基址int length; //当前长度int listsize; //当前分配的存储容量}SqList4、单链表的插入/删除操作在结点*P后插入一个结点删除结点*P本身5、单链表的插入/删除操作在结点*P前插入一个结点删除结点*P的后继6、改用尾指针rear来表示带头结点的单循环链表，请问头结点a0、开始结点a1和终端结点an如何表示？它们的存储位置分别是rear–>next 、(rear–>next) —>next和rear，7、栈后进先出(LIFO)8、若进站的车厢序列为123456，如何得出出站序列135426。

请用S表示入栈，X表示出栈。

9、若进站的车厢序列为123456，如何得出出站序列435621。

请用S表示入栈，X表示出栈。

10、例 3.2 设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是D 。

(A) A,B,C,D (B) D,C,B,A(C) A,C,D,B (D) D,A,B,C11、例3.3 已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=n,则pi的值 C 。

一、单项选择题(本题总分 20分，每题 2分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母。

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) 。

A.顺序表 B.链表 C.索引表 D.散列表采用排除法，顺序表存储位置表示数据元素的顺序关系，跟关键字无法；链表的地址是动态分配的；索引表是 按数据元素的关键字排序所得，它的数据元素是没有规律的2.在长度为 n 的顺序表的第 i(1≤i ≤n+1)个位置上插入一个元素，元素的移动次数为( A ) 。

A.n -i+1B.n -iC.iD.i -1代入计算法，我们知道在 i=n+1 时不需要移动元素3.若一棵二叉树的先序遍历序列为 a,b,c ，则由 abc 三个结点构成的二叉树个数为( B ) 。

A.4B.5C.6D.74.三维数组 A[4][5][6]按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元素的存 储地址为 130，则元素 A[3][4][5]的存储地址为(B A.370B .368C .366) 。

D.372Loc(3,4,5)=loc(0,0,0)+(3*5*6+4*6+5)*2=130+119*2=368;5.高度为 h 的二叉树（仅含根结点的二叉树高度为 1）的结点最少是多少( D) 。

A. h+1B. 2hC. 2h －1D. h二叉树性质 26. 将两个各有 n 个元素的有序表归并成一个有序表，其最多的比较次数是( A. nB.n+1 C. 2n-1D. n-17. 已知一算术表达式的中缀形式为 A ＋B *C -D/E ，后缀形式为 ABC *+DE/-，其前缀形式为( C) 。

A )。

A. -+A*BC/DE C. -+*ABC/DEB. –A+B*CD/E D. –A+B*C/DE根据中缀和后缀表达式可画出表达树如下：- + /A* D EBC故前缀表达式为：-+A*BC/DE数据结构期中考试8．下面图示的顺序存储结构表示的二叉树是（ A ）。

《数据结构》期中测试班级：姓名：学号：一、填空题：1、在数据结构中，从逻辑上可以把数据结构分为集合、线性结构、树形结构和图状结构，其中树形结构和图状结构合称为非线性结构。

数据结构被形式地定义为二元组（D，S），其中D是数据元素的有限集合，S是D上关系的有限集合。

2、算法的五个重要特性是有穷性、确定性、可行性、输入和输出。

3、一个顺序表第一个元素的存储地址是100，每个元素的长度为3，则第6个元素的地址是115。

在顺序表中插入或删除一个元素，需要平均移动（n+1）/2个元素，具体移动的元素个数与插入或删除元素的位置有关。

顺序表中逻辑上相邻的元素的物理位置相邻。

单链表中逻辑上相邻的元素的物理位置不一定相邻。

单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的指针域指示。

在单链表中设置头结点的作用是使第一个结点与其他结点的操作统一。

4、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（n+1）/2个结点。

在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O（n）。

给定有n个元素的线性表，建立一个有序单链表的时间复杂度是O（n2）。

5、已知L是无表头结点的非空单链表，且指针p所指结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

在p所指结点后插入s所指结点：4、1。

在p所指结点前插入s所指结点：7、11、8、4、1。

在表首插入s所指结点：5、12。

在表尾插入s所指结点：11、9、1、6。

1)p->next=s;2)p->next=p->next->next;3)p->next=s->next;4)s->next=p->next;5)s->next=L;6)s->next=NULL;7)q=p;8)while(p->next!=q) p=p->next;9)while(p->next!=NULL) p=p->next;10)p=q;11)p=L;12)L=s;13)L=p;6、已知指针p所指结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

《数据结构》一．选择题（从下列答案选项中选出一个正确答案，每小题2分)1.在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。

A．逻辑结构B．顺序存储结构C．链式存储结构 D. 以上都对2.线性表就是顺序表，这种说法（）。

A．正确B．错误3.若已知一个栈的入栈序列是1, 2, 3, 4, 5，不可能得到的输出序列是（）。

A．2,3,4,1,5 B．5,4,1,3,2C．2,3,1,4,5 D．1,5,4,3,24.串的逻辑结构与（）的逻辑结构不同。

A.栈B.队列C.树D.线性表5.如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。

（）A.正确B.错误6.设有两个串P和Q，求Q在P中首次出现的位置的操作称为（）。

A.连接B.模式匹配C.求子串D.求串长7.已知模式串t=“abcaabbcabcaabdab”，该模式串的next数组值为（）。

A.-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1B.0，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1C.-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1，D.-1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，18.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。

A.13B.33C.18D.409.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法（）。

A.正确B.错误10.树形结构的特点是：一个结点可以有（）。

A、多个直接前趋B、多个直接后继C、多个前趋D、一个后继11.在一棵高度为h的满三叉树中，结点总数为（）A、3h-1B、(3h-1)/2C、(3h-1)/3D、3h12.设森林T中有4棵树，结点个数依次为n1, n2, n3, n4，当把森林T转换成一棵二叉树后，二叉树根结点的右子树上有（）个结点。

数据结构期中试卷及答案解析考试说明考试说明：考察前五章小题，难度接近真题。

满分100分，共20道选择题，每题5分。

请在60分钟内完成。

C T(n)=n3+5000nD T(n)=2nlogn-1000n参考答案：C本题考察时间复杂度，多个项相加时，只保留最高阶项由于巴啦啦能量——“常<对<幂<指<阶”，因此T(n)=logn+5000n=O(n)T(n)=n2-8000n=O(n2)T(n)=n3+5000n=O(n3)T(n)=2nlogn-1000n=O(nlogn)所以O(n3)复杂度最大，选C。

3.下列叙述中正确的是（）①线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比②线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关③线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比A. 仅①B. 仅②C. 仅③D. ①②③参考答案：A线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比。

线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关4.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。

A. 单链表B. 双向链表C. 单循环链表D. 顺序表参考答案：D注意到，题目要求存取第i个元素及其前驱和后继，ABC三个选项找到第i个元素的时间复杂度均为O(n)，而D选项对于这3个位置的存取的时间复杂度均为O(1)，故选D。

5.静态链表中next域表示的是（）A 下一个元素的地址B 下一个元素的值C 当前元素的值D 下一个元素在数组中的位置参考答案：D静态链表一般保存在数组中，它和链表最大的区别是静态链表占用一段固定的区间，所以next域只需要表示下一个元素在数组中的下标即可而不是表示下一个元素的地址，选D。

6.对于不带头结点的链栈L（next域表示该结点下一个元素），top指针指向栈顶元素（栈顶在链头方向），则x结点进栈操作为A top->next=x;top=x;B top=x;top-next=x;C top=x;x->next=top;D x->next=top;top=x;参考答案：D本题考察链栈的操作x入栈之后x下一个元素为原来的top，所以先把x->next=top，然后更新top，栈顶元素指向x。

一、选择题（每小题 1分，共10分）1、队列是插入和删除受限的线性表，其删除操作是在线性表的（1）进行。

A．表头 B．表尾 C．任意位置 D．指定位置2、下述哪一条是顺序存储结构的优点（2）。

A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示3、设有一个栈，元素的进栈次序为A, B, C, D, E，下列哪个是不可能的出栈序列（3）。

A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A4、若二叉树的根结点所在的层次为第1层，则该二叉树的第k层上至多有（4）个结点。

2k B．2k C．2k-1 D．2k+1A. 15、设单链表中指针p指向结点m，若要删除m的后继结点（假设该后继结点存在），则需修改指针的操作为（5）。

A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;6、下面程序段的时间复杂度为（6）。

for(int i=0; i<m; i++)for(int j=0; j<n; j++) a[i][j] = i*j;A．O(m2) B．O(n2) C．O(m+n) D． O(m*n)7、非空的循环单链表head的尾结点指针p满足（7）。

A．p==NULL B．p== head C．p->next==head D．p->next==NULL8、已知二维数组A[0..9,0..9]中，元素a[2][0]的地址为560，每个元素占4个字节，则元素a[1][0]的地址为（8）。

A. 518B. 520C. 522D. 5249、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（9）。

A．rear％n= = front B．（front+l）％n= = rearC．rear％n -1= = front D．(rear+l)％n= = front10、假设在一棵二叉树中，度为2的结点数为15，度为1的结点数为10个，则该二叉树的分支总数为（10）个。

厦门大学《＿数据结构＿》课程期中试卷信息科学与技术学院计算机科学系＿＿年级＿＿＿专业主考教师：＿＿＿＿试卷类型：（A卷/B卷）任选5题（（1，2），（3，4），（5，6），（7，8）中必须至少做一题），每题20分。

一、试设计一个双栈结构，它有两个端点end1和end2，满足从end1端插入的表目只能从end1端被删除，从end2端插入的表目只能从end2端被删除，并给出指定端i（i=1，2）的进栈push(S,e,i)和出栈pop(S,e,i)操作的算法描述。

再设计一个算法，它能够将一个有限长度的数据序列a1，a2，…，an，按照下标奇偶序号交替的方式将ai (1≤i≤n)分别从两端入栈，然后将数据出栈以实现整个数据序列的倒排。

该双栈宜采用顺序存储、栈顶迎面增长的存储方式，其形式定义如下：#define STACK_SIZE 1000typedef struct {SElemType base[STACK_SIZE];SElemType *top[3]; //top[1]表示end1端的栈顶指针，top[2]表示end2端的栈顶指针//初始值分别为base和base+STACK_SIZE-1}DSqStack;指定端i（i=1，2）的进栈push(S,e,i)和出栈pop(S,e,i)操作的算法描述如下：Status push(DSqStack &S, SElemType e, int i) {if ( S.top[1]-S.top[2]==1 ) //栈满exit(OVERFLOW);else if (i==1)*S.top[1]++ = e;else if (i==2)*S.top[2]-- = e;elsereturn ERROR;return OK;}Status pop(DSqStack &S, SElemType &e, int i) {if (i==1) {if ( S.top[1] == S.base ) return ERROR;e = *--S.top[1] = e;return OK;}else if (i==2) {if (S.top[2] == S.base+STACK_SIZE-1) return ERROR;e = *++S.top[2];return OK;} elsereturn ERROR;}基于上述结构的数据序列的倒排算法描述如下：Status resevers(DSqStack &S, SElemType a[], int n) {for (j=1;j<=n;j++)if (j%2==0) push(S, a[j-1],2);else push(S, a[j-1],1);for (j--;j>=1;j--)if (j%2==0) pop(S, a[n-j],2);else pop(S, a[n-j],1);return OK;}二、利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算。

一、判断题：1、线性表的逻辑顺序与物理顺序总是一致的。

( )2、线性表的顺序存储表示优于链式存储表示。

( )3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

( )4、二维数组是其数组元素为线性表的线性表。

( )5、每种数据结构都应具备三种基本运算：插入、删除和搜索。

( )6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

( )7、线性表中的每个结点最多只有一个前驱和一个后继。

（）8、线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

（）9、栈和队列逻辑上都是线性表。

（）10、单链表从任何一个结点出发，都能访问到所有结点（）11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。

（）12、快速排序是排序算法中最快的一种。

（）13、多维数组是向量的推广。

（）14、一般树和二叉树的结点数目都可以为0。

（）15、直接选择排序是一种不稳定的排序方法。

（）16、98、对一个堆按层次遍历，不一定能得到一个有序序列。

（）17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

（）18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。

（）19、堆栈在数据中的存储原则是先进先出。

（）20、队列在数据中的存储原则是后进先出。

（）21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。

（）22、哈夫曼树一定是满二叉树。

（）23、程序是用计算机语言表述的算法。

（）24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。

（）25、用一组地址连续的存储单元存放的元素一定构成线性表。

（）26、堆栈、队列和数组的逻辑结构都是线性表结构。

（）27、给定一组权值，可以唯一构造出一棵哈夫曼树。

（）28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。

一、选择题（每小题 1分，共10分）1、队列是插入和删除受限的线性表，其删除操作是在线性表的（1）进行。

A．表头B．表尾C．任意位置D．指定位置2、下述哪一条是顺序存储结构的优点？（2）。

A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示3、设有一个栈，元素的进栈次序为A, B, C, D, E，下列哪个是不可能的出栈序列（3）。

A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A4、若二叉树的根结点所在的层次为第1层，则该二叉树的第k层上至多有（4）个结点。

2k B．2k C．2k-1 D．2k+1A. 15、设单链表中指针p指向结点m，若要删除m的后继结点（假设该后继结点存在），则需修改指针的操作为（5）。

A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;6、下面程序段的时间复杂度为（6）。

for(int i=0; i<m; i++)for(int j=0; j<n; j++) a[i][j] = i*j;A．O(m2) B．O(n2) C．O(m+n) D．O(m*n)7、非空的循环单链表head的尾结点指针p满足（7）。

A．p==NULL B．p== head C．p->next==head D．p->next==NULL8、已知二维数组A[0..9,0..9]中，元素a[2][0]的地址为560，每个元素占4个字节，则元素a[1][0]的地址为（8）。

A. 518B. 520C. 522D. 5249、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（9）。

A．rear％n= = front B．（front+l）％n= = rearC．rear％n -1= = front D．(rear+l)％n= = front10、假设在一棵二叉树中，度为2的结点数为15，度为1的结点数为10个，则该二叉树的分支总数为（10）个。

1．评价算法优劣的基本标准有哪些？请就每一项给出简短说明。

答：（1）正确性：对输入的合法数据（包括边界情况），都能有正确的输出结果。

（2）健壮性：对输入的非法数据，算法能适当地做出反应或进行处理，而不是产生莫名其妙的输出结果。

（3）可读性：有助于人对算法的理解，易于发现错误，便于调试和修改。

（4）效率与低存储量需求：效率和存储量需求分别指算法执行所需要的时间和最大存储空间。

2．已知一棵二叉树的中序和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA，（1）画出这棵二叉树，对这棵二叉树的构造过程给出一个简短说明；（2）将这棵二叉树理解为“孩子-兄弟法”表示的森林，画出这个森林。

答：（1）构造出的二叉树如图1所示：图1构造过程说明：①后序序列的最后一个元素为A, 得知二叉树的根为A；②在中序序列中找到树根A, A左侧的部分GLDHBEI为左子树的中序序列，A右侧的部分CJFK为右子树的中序序列。

并得知左子树7个节点，右子树4个节点；③后序序列的前7个节点LGHDIEB是左子树的后序序列，后续序列的后4个节点JKFC是右子树的后序序列；④根据中序GLDHBEI后序LGHDIEB求左子树，根据中序CJFK后序JKFC 求右子树。

依此类推，便可唯一构造出此二叉树。

（2）“孩子-兄弟表示法”，又称二叉链表表示法，链表中结点的两个链域分别指向该结点的第一个孩子和下一个兄弟结点，一棵二叉树与森林一一对应，该森林如图2所示：图23．字符A，B，C，D，E，F，G的使用频度分别是15，8，10，21，6，19，3，写出A，B，C，D，E，F，G的Huffman编码，列出编码过程，解释Huffman 有什么优点。

解：编码过程如下：各字符编码为字符 A B C D E F G编码011 110 010 00 1111 10 1110优点：Huffman编码为前缀码，它根据结点出现的频度由低到高编码，则可以使频度较高的结点有尽可能短的编码，从而使整个发送文件的总编码长度尽可能短。

数据结构2010年下学期 考试时间：100分钟 考试形式：闭卷（所有答案写在答题纸上，请在答题纸上注明班级、学号） 一、概念题（每题 2 分，共 24分） 1、从逻辑角度看，数据可归结为四类基本结构：集合、线性结构、 树状结构 和 图状结构 。

2、算法效率度量分析的两个基本指标是 时间复杂度 和 空间复杂度 。

前者是基于算法执行时间的度量，后者是基于算法所需存储空间的度量。

3、线性表顺序存储的特点是：表中相邻的元素a i 和a i+1所对应的存储地址 LOC （a i ）和LOC(a i+1)也是____相邻_____的。

设线性表a 的起始地址为LOC(a 1)，每个数组元素所占用的存储单元数为b ，则表中第i(1≤i ≤n)个元素a i 的存储起始地址LOC(a i )可用如下公式得到__ LOC(a i )_ = LOC(a 1)+(i-1)*b ______。

4、在线性表的存储结构中，顺序表是一个可 随机存取 存取的存储结构，单链表则是一个 顺序存取 存取的存储结构。

5、设单链表的结点数据类型定义和指针变量说明如下 #define DATATYPE2 char typedef struct node { DATATYPE2 data; struct node *next; } LINKLIST; LINKLIST *p,*q,*s; 在一个单链表中，已知q 所指向结点是p 所指向结点的直接前趋结点。

若欲在q 结点和p 结点之间插入一个s 所指向的结点，则可写 q->next=s;s->next=p 6、关于选用顺序表结构或链表结构，在考虑线性表的操作的时间性能时，若线性表上的操作主要是查找、读取而很少做插入和删除操作时，以采用 顺序 表结构为宜。

但是，若线性表需频繁地进行插入和删除操作时，则采用 链表 表结构为宜。

7、如果在待排序的序列中，存在有多个关键字相同的记录，经过排序后，这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是 稳定 的；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是 不稳定 的。

数据结构期中试卷答案（信计11）嘉兴学院试卷2012 —2013学年第2学期期中考试试卷课程名称：数据结构使⽤班级：信计11级考试形式：闭卷在题⼲的括号内。

每个选择1分，共10分)1．抽象数据类型可⽤三元组（D，R，P）表⽰，其中R是 D 的有限集。

A．算法B．数据元素C．数据操作D．数据关系2．数据结构的研究包含三个⽅⾯的内容，它们分别是数据的 B 、数据的存储结构和数据运算。

A．数据元素B．逻辑结构C．存储结构D．计算⽅法3．线性结构的顺序存储结构是⼀种随机存取的存储结构，⽽链式存储结构是⼀种 A 的存储结构。

A．顺序存取 B．随机存取 C．索引存取 D．散列存取4．线性表L在 B 情况下，最适合使⽤链接结构实现算法。

A．不需经常对L进⾏修改 B．需经常对L进⾏删除和插⼊C．需经常修改L中结点值 D．L中结点结构复杂5．⼀个队列的⼊列序列是a，b，c，d，则队列的输出序列是 A 。

A．a，b，c，d B．a，d，c，b C．c，b，d，a D．d，c，b，a6．循环队列Q中的数据元素值存放在长度为m的数组中，且此数组最多只能存放m-1个数据元素。

已知头尾指针分别是Q．front和Q．rear, 则判断Q为满队列的条件是 B 。

A．Q．front= =Q．rear B．Q．front= =(Q．rear+1) %mC．Q．front!=Q．rear D．Q．front!= (Q．rear+1) %m7．⼀个栈的⼊栈序列是a, b, c, d, e, 则栈的不可能的输出序列是D 。

A．abcde B．decba C．edcba D．dceab8．判定⼀个顺序栈S（最多存放元素个数是m）为空栈的条件是 C 。

(顺序栈类型定义为：typedef struct {Selemtype *base;Selemtype *top;Int stacksize; } Sqstack；) A．S．top= =0 B．S．top= =m C．S．top= = S．base D．S．base= =0 9．从数据结构来看，串是⼀种特殊的线性表，其特殊性体现中 B 。