数据结构期中试卷及答案

《数据结构期中试卷及答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、选择题（每小题2分，共30分）1.数据结构是（D）。A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合2．以下与数据的存储结构无关的术语是（D）。A．链队列B.链表C.顺序表D.栈3．以下数据结构中，（A）是非线性数据结构A．树B．字符串C．队D．栈4．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。A．98B．100C．102D．1065．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D　　）。A．插入B．删

2、除C．排序D．查找6．线性表采用链式存储时，其地址(D)。A．必须是连续的B．一定是不连续的C．部分地址必须连续D．连续与否均可以7．线性表是(A)。A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空8．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（　B　）。A．3，2，6，1，4，5B．3，4，2，1，6，5C．1，2，5，3，4，6D．5，6，4，2，3，19.若一个栈的输人序列是1，2，3，…，n，输出序列的第一个元素是n，则第k个输出元素

3、是（C）。A．kB．n-k-1C．n-k+1D．不确定10.对于队列操作数据的原则是（A）。A.先进先出B.后进先出C.先进后出D.不分顺序11.栈和队列的共同点是（C）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（A）。A．front=front->nextB．rear=rear->nextC．rear->next=frontD．front->next＝rear13.空串与空格串（B）。A．相同B．不相同C．可能相同D

4、．无法确定14.串与普通的线性表相比较，它的特殊性体现在（C）。A．顺序的存储结构B．链接的存储结构C．数据元素是一个字符D．数据元素可以任意15.串的长度是指（B）。A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数二、填空题（每空2分，共20分）1．线性表、栈和队列，串都是__线性_____结构。2．数据的基本单位是__数据元素_______________。3．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序______存储结构

5、。4．已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为Loc(a1)，那么，第i个元素的存储地址Loc(ai)=Loc(a1)+(i-1)*k。5．栈（stack）是限定在表尾进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为__栈顶________，而另一端称为_栈底________。6．一个循环队列Q中，头指针和尾指针分别为Q.front和Q.rear，且最大队列长度为MaxQSize，则判断队空的条件为Q.rear==Q.front,判断队满的条件为(Q.rear+1)%MaxQSiz

6、e==Q.front。队列的长度为(.rear-Q.front+MaxQSize)%MaxQSize1．两个串相等的充分必要条件是两个串的长度相等，且各个对应位置的字符都相等。三、程序填空题（每空3分，共30分）1.在带头结点的单链表L中第i个数据元素之前插入数据元素e的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。typedefstructnode{intdata；structnode*next；}linknode,*link；intListInsert_L(link&L,inti,inte){Linkn

7、ode*p；intj；p=L；j=0；while(p&&jnext；++j；}//寻找第i-1个结点if(!p

8、

9、j>i-1)return0；s=(link)malloc(sizeof(linknode))；//生成新结点ss->data=e；s->next=p->next；p->next=s；//插入L中return1；}2.对顺序栈的C语言描述算法如下，其中top为栈顶指针，请填充算法中标出的空白处，插入元素e为新的栈顶元素。#defineSTACK_INIT_SIZE100#defineSTACKINCREMEN

10、T10typedefstruct{char*base;char*top;intstacksize;}SqStack;intPush(SqStack&S,chare)