数据结构期中试卷

一、选择题〔每题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＝rear空串与空格串〔B〕。A．相同B．不相同C．可能相同D．无法确定14.串与普通的线性表相比较，它的特殊性表达在〔C〕。A．次序的存储构造B．链接的存储构造C．数据元素是一个字符D．数据元素能够随意串的长度是指〔B〕。A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数二、填空题〔每空2分，共20分〕1．线性表、栈和行列，串都是__线性_____构造。2．数据的根本单位是__数据元素_______________。3．当线性表的元素总数根本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_次序______存储构造。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)%MaxQSize==Q.front。行列的长度为(.rear-Q.front+MaxQSize)%MaxQSize精选7．两个串相等的充分必要条件是两个串的长度相等，且各个对应地点的字符都相等。三、程序填空题〔每空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；}//寻找第i-1个结点if(!p||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#defineSTACKINCREMENT10typedefstruct{char*base;char*top;intstacksize;}SqStack;intPush(SqStack&S,chare){//if((s.top-s.base)>=s.stacksize)//栈满，追加存储空间{S.base=(SElemType*)realloc(S.base,S.stacksize+STACKINCREMENT)*sizeof(SElemType))；if(!S.base)return0；S.top=s.base+s.stacksize；//改正栈顶指针S.stacksize+=STACKINCREMENT；}*s.top++=e；//插入元素return1；}3.对链行列的C语言描绘算法如下，请填充算法中标出的空白处，删除行列Q的队头元素并用e返回其值。typedefstructQNode{QElemTypedata；structQNode*next；}QNode,*QueuePtr；typedefstruct{QueuePtrfront；QueuePtrrear；}LinkQueue；intDeQueue(LinkQueue&Q,QElemType&e){Linknode*p；if(Q.front==Q.rear)retrun0；//行列空，返回p=Q.front->next；e=p->data；Q.front->next=p->next；//改正指针if(Q.rear==p)Q.rear=Q.front；//行列只有一个元素的情况free(p)；//释放结点空间return1；}精选三、算法设计与剖析题〔每题10分，共20分〕1、简述以下算法实现的功能：〔每题5分，共10分〕〔1〕typedefstructLNode{Chardata;structLNode*next;}LNode,*LinkList;LinkListDemo(LinkList&L){//L是无头结点单链表LNode*Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}returnL;}//Demo答：将单链表的第一个结点删除，放到链尾。———————————————————————————————————————————————————〔2〕#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{int*base;int*top;intstacksize;}Stack;voidDemo1(Stack&S,intm){StackT;inti;InitStack(T);//初始化栈while(!StackEmpty(S))//判断栈是否为空if((i=Pop(S))!=m)Push(T,i);//入栈操作while(!StackEmpty(T)){i=Pop(T);//出栈操作Push(S,i);}}答：删除栈S中所有值为m的数据元素有一个带头结点的单链表，头指针为head，编写一个算法计算所有数据域为X的结点的个数〔不包括头结