数据结构期中试卷b

《数据结构期中试卷b》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构期中试卷B一、判断题：（10分，每题1分）1、线性表的顺序存储表示优于链式存储表示。()2、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（）3、单链表从任何一个结点出发，都能访问到所有结点。（）4、用一组地址连续的存储单元存放的元素一定构成线性表。（）5、非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（）6、符号p->next出现在表达式中表示p所指的那个结点的内容。（）7、线性链表中各个链结点之间的地址不一定要连续。（）8、程序越短，程序运行的时间就越少。（）9、采用循环链表作为

2、存储结构的队列就是循环队列。（）10、堆栈是一种插入和删除操作在表的一端进行的线性表。（）二、填空题：（10分，每空1分）1、一个串的任意个连续的字符组成的子序列称为该串的______，包含该子串的串称为____。2、若频繁地对线性表进行插入与删除操作，该线性表应采用______________存储结构。3、已知广义表A=((a,b,c),(d,e,f)),则运算head(head(tail（A）)))=________。4、链式存储结构中的结点包含________________域，_______________域。5、栈结构

3、允许进行删除操作的一端为_____________。6、已知循环队列的存储空间为数组data[21]，且头指针和尾指针分别为8和3，则该队列的当前长度___________。7、若一个n阶矩阵A中的元素满足：Aij=Aji(0<=I,j<=n-1)则称A为________矩阵；若主对角线上方(或下方)的所有元素均为零时，称该矩阵为__________。三、选择题：（30分，每题2分）（1）数据结构通常是研究数据的及它们之间的联系。A、存储和逻辑结构B、存储和抽象C、理想和抽象D、理想与逻辑（2）已知广义表的表头为A，表尾为(B,

4、C)，则此广义表为________A、（A,(B,C)）B、（A,B,C）C、(A,B,C)D、((A,B,C))（3）二维数组A按行顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为_______A、470B、471C、472D、473（4）在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。Ａ、行号Ｂ、列号Ｃ、元素值Ｄ、地址（5）在以下的叙述中，正确的是__________Ａ、二维数组是它的每个数据元素为一个线性表的线性

5、表Ｂ、栈的操作方式是先进先出Ｃ、线性表的线性存储结构优于链表存储结构Ｄ、队列的操作方式是先进后出（6）如下陈述中正确的是________A、串是一种特殊的线性表B、串的长度必须大于零C、串中元素只能是字母D、空串就是空白串（7）一个非空广义表的表头________A、不可能是子表B、只能是子表C、只能是原子D、可以是子表或原子（8）在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行_____。A、p=q->next;p->next=q->next;C、p=q->next;q->next=p->next;B、p=q-

6、>next;q->next=p;D、q->next=q->next->next;q->next=q;（9）在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的________。A、行号B、列号C、元素值D、地址（10）在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移_____个元素。A、n-iB、n-i+1C、n-i-1D、i（11）当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行_____语句修改top指针。A

7、、top++B、top--C、top=0D、top（12）若让元素1，2，3依次进栈，则出栈次序不可能出现_____种情况。A、3，2，1B、2，1，3C、3，1，2D、1，3，2（13）假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是_____。A、f+1==rB、r+1==fC、f==0D、f==r（14）计算机识别、存储和加工处理的对象被统称为_________A、数据B、数据元素C、数据结构D、数据类型（15）在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是________A、

8、O（1）B、O（n）C、O(nlogn)D、O(n2)四、应用题：(16分)1．已知稀疏矩阵如下：请写出该稀疏矩阵三元组表示。（3分）2．请写出下面链表表示的广义表。（4分）3．将两个栈存入数组V[1..m]中应如何安排最好?这时栈空栈满的条件是什么?（5分）4