数据结构期中试卷及答案

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

2、找6.线性表采用链式存储时，其地址A .必须是连续的BC .局部地址必须连续DD 。.一定是不连续的.连续与否均可以7 .线性表是A 。A. 个有限序列，可以为空C. 一个无限序列，可以为空B.一个有限序列，不可以为空D.一个无限序列，不可以为空&假设进栈序列为1, 2, 3, 4, 5,6,且进栈和出栈可以穿插进行，那么可能出现的出栈序列为B 。A. 3, 2, 6, 1, 4, 5 B3, 4, 2, 1, 6, 5C. 1 , 2, 5, 3, 4, 6D . 5, 6, 4, 2, 3, 19.假设一个栈的输人序列是1, 2, 3,A. k B . n-k-1 C,n,输出序列

3、的第一个元素是n ,那么第k个输出元素是C 。n-k+1 D.不确定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 .

4、可能相同D.无法确定14.串与普通的线性表相比拟，它的特殊性表达在 C 。A.顺序的存储结构C .数据元素是一个字符BD.链接的存储结构.数据兀素可以任意15.串的长度是指B 。A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数二、填空题每空 2分，共20 分1 .线性表、栈和队列，串都是线性结构。2 .数据的根本单位是_数据元素 。3. 当线性表的元素总数根本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序_一存储结构。4. 具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为

5、Loca"，那么，第i个元素的存储地址Loca i = Loca 1+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三、程序填空题(每空3分，共30分)1在带头结点的单链表L中第i个数据元素之前插

6、入数据元素e的C语言描述算法如下，其中完成其功能。typedef struct nodeint data ；struct node *n ext ；li nkn ode,*l ink；int List In sert_L(li nk & L, i nt i, i nt e) Linknode *p ； int j ；P = L ； j = 0；while (p && j < i-1) p= ； +j ； II 寻找第i-1 个结点if 仲 | j > i-1) return 0；s=(link)malloc(sizeof(linknode)； II 生成新结

7、点 ss->data = e ；s->next=p->next； p->next = s ； II 插入 L 中return 1； 2.对顺序栈的C语言描述算法如下，其中top为栈顶指针，请填充算法中标出的空白处，插入元素#define STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10typedef structchar *base;char *top;int stacksize;SqStack;L为链表头结点指针。请填充算法中标出的空白处,e为新的栈顶元素。int Push( SqStack &S, char e) I

8、Iif ( (s II 栈满，追加存储空间S.base=(SElemType *)realloc(S.base,S.stacksize+STACKINCREMENT) *sizeof(SElemType) if (! S.base) return 0；S.top = s.base+s.stacksize； II修改栈顶指针S.stacksize += STACKINCREMENT ；*s.top+=e； II 插入元素return 1；3.对链队列的C语言描述算法如下，请填充算法中标出的空白处，删除队列Q的队头元素并用typedef struct QNodeQElemType data ；st

9、ruct QNode *n ext；QNode, *QueuePtr ；e返回其值。typedef struct QueuePtr frontQueuePtr rearLin kQueue ；int DeQueue(L in kQueue &Q, QElemType &e) Linknode *p ；if( Q.front=Q.rear ) retrun 0； II 队列空，返回p = Q.front -> n ext；e = p->data ；Q.front -> next=p->next； II 修改指针if(Q.rear=p) Q.rear= Q.

10、front； II 队列只有一个元素的情况free(p)； II释放结点空间return 1；三、算法设计与分析题(每题 10 分，共 20 分)1、简述以下算法实现的功能： (每题 5 分，共 10 分)( 1) typedef struct LNodeChar data;struct LNode *next;LNode,*LinkList;LinkList Demo(LinkList &L) / L 是无头结点单链表LNode *Q,*P;if(L&&L->next)Q=L; L=L->next; P=L;while (P->next) P=P-&

11、gt;next;P->next=Q; Q->next=NULL;return L;/ Demo答：将单链表的第一个结点删除，放到链尾。(2)#define STACK_INIT_SIZE100#define STACKINCREMENT10typedef struct int *base;int *top;int stacksize; Stack;void Demo1( Stack &S, int m) Stack T; int i;InitStack (T);/ 初始化栈while (! StackEmpty(S)/ 判断栈是否为空if( i=Pop(S) !=m)Push( T,i);/ 入栈操作while (! StackEmpty(T)i=Pop(T); / 出栈操作Push(S,i);答：删除栈S中所有值为m的数据元素2. 有一个带头结点的单链表，头指针为head，编写一个算法计算所有数据域为X的结点的个数(不包括头结点)