数据结构期中试卷

一、选择题（每题2分，共30分）数据结构是（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．删除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个输出元素是（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．无法确定14.串与一般的线性表对照较，它的特别性表现在（C）。A．序次的储藏结构B．链接的储藏结构C．数据元素是一个字符D．数据元素可以任意15.串的长度是指（B）。A.串中所含不相同字母的个数B.串中所含字符的个数C.串中所含不相同字符的个数D.串中所含非空格字符的个数二、填空题（每空2分，共20分）1．线性表、栈和队列，串都是__线性_____结构。2．数据的基本单位是__数据元素_______________。3．当线性表的元素总数基本牢固，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_序次______储藏结构。4．已知拥有n个元素的一维数组采用序次储藏结构，每个元素占k个储藏单元，第一个元素的地址为1Loc(a)，那么，第i个元素的储藏地址i)=Loc(a1。Loc(a)+(i-1)*k5．栈（stack）是限制在表尾进行插人或删除操作的线性表。在栈中，赞同插人和删除操作的一端称为__栈顶________，而另一端称为_栈底________。6．一个循环队列Q中，头指针和尾指针分别为和，且最大队列长度为MaxQSize，则判断队空的条件为==,判断队满的条件为+1)%MaxQSize==。队列的长度为(.+MaxQSize)%MaxQSize7．两个串相等的充分必要条件是两个串的长度相等，且各个对应地址的字符都相等。三、程序填空题（每空3分，共30分）1.在带头结点的单链表L中第i个数据元素从前插入数据元素e的C语言描述算法以下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。typedefstructnode{intdata；structnode*next；}linknode,*link；intListInsert_L(link&L,inti,inte){Linknode*p；intj；p=L；j=0；while(p&&j<i-1){p=p->next；++j；}对序次栈的C语言描述算法以下，其中top为栈顶指针，请填充算法中标出的空白处，插入元素为新的栈顶元素。#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{char*base;char*top;intstacksize;}SqStack;intPush(SqStack&S,chare){

对链队列的C语言描述算法以下，请填充算法中标出的空白处，删除队列typedefstructQNode{

Q的队头元素并用

e返回其值。QElemTypedata

；structQNode*next

；}QNode,*QueuePtr

；typedefstruct{QueuePtrfront

；QueuePtrrear

；}LinkQueue；intDeQueue(LinkQueue&Q,QElemType&e){Linknode*p

；if(==)retrun0

；一个带头结点的单链表，头指针为

head，编写一个算法计算所有数据域为

X的结点的个数（不包括头结点）

。typedefstructnode{intdata;structnode*next;}linknode,*