数据结构期中试卷及答案_数据结构试卷期中答案
数据结构期中试卷及答案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构试卷期中答案”。
一、选择题（每小题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．98 B．100 C．102 D．106
5．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（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，5 B．3，4，2，1，6，5 C．1，2，5，3，4，6 D．5，6，4，2，3，1
9.若一个栈的输人序列是1，2，3，…，n，输出序列的第一个元素是n，则第k个输出元素是（C）。
A．k B．n-k-1 C．n-k+1 D．不确定
10.对于队列操作数据的原则是（A）。
A.先进先出 B.后进先出 C.先进后出 D.不分顺序 11.栈和队列的共同点是（C）。
A.都是先进先出 B.都是先进后出 C.只允许在端点处插入和删除元素 D.没有共同点
12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（A）。
A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear
13.空串与空格串（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个存储单元，第一个元素的地址为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为链表头结点指针。请填充算法中标出的空白处，完成其功能。
typedef struct node {int data；
struct node *next；
}linknode,*link；
int ListInsert_L(link &L, int i, int e){ Linknode *p；int j； p = L； j = 0；
while(p && j next ； ++j； } // 寻找第i-1个结点 if(!p || j > i-1)return 0；
s=(link)malloc(sizeof(linknode))；// 生成新结点s s->data = e；
s->next=p->next ； p->next = s； // 插入L中 return 1； }
2.对顺序栈的C语言描述算法如下，其中top为栈顶指针，请填充算法中标出的空白处，插入元素e为新的栈顶元素。
#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ char *base;char *top;int stacksize;}SqStack;
int Push(SqStack &S, char e){ //
if((s.top-s.base)>=s.stacksize)//栈满，追加存储空间 { S.base=(SElemType *)realloc(S.base,S.stacksize+STACKINCREMENT)*sizeof(SElemType))； if(!S.base)return 0；
S.top = s.base+s.stacksize ； //修改栈顶指针 S.stacksize += STACKINCREMENT； } *s.top++=e ；//插入元素 return 1； }
3.对链队列的C语言描述算法如下，请填充算法中标出的空白处，删除队列Q 的队头元素并用e返回其值。typedef struct QNode{ QElemType data； struct QNode *next； }QNode, *QueuePtr；
typedef struct { QueuePtr front； QueuePtr rear； }LinkQueue；
int DeQueue(LinkQueue &Q, QElemType &e){ Linknode *p；
if(Q.front==Q.rear)retrun 0；//队列空，返回 p = Q.front-> next； e = p->data；
Q.front-> next=p->next；//修改指针
if(Q.rear==p)Q.rear= Q.front ； //队列只有一个元素的情况 free(p)；//释放结点空间 return 1； }
三、算法设计与分析题（每题10分，共20分）
1、简述下列算法实现的功能：（每题5分，共10分）（1）typedef struct LNode{
Char 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->next;
P->next=Q;Q->next=NULL;
} return L;}// Demo 答：将单链表的第一个结点删除，放到链尾。
———————————————————————————————————————————————————
（2）#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef 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的结点的个数（不包括头结点）。typedef struct node {int data;struct node *next;}linknode,*link;int sample(link head, int X){ int count=0;link p=head->next;while(p){if(p->data==X)count++;p=p->next;} return count;}
数据结构试卷（一）一、选择题（20分）1．组成数据的基本单位是（ ）。(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={，，，}，则数据结构A是（ ）。(A)......
数据结构试卷（八）一、选择题(30分) 1.字符串的长度是指（）。(A) 串中不同字符的个数 (B) 串中不同字母的个数(C) 串中所含字符的个数 (D) 串中不同数字的个数 2.建立一个长度为n......
广东海洋大学2013 ——2014 学年第 1 学期《数据结构与算法》课程试题一、选择题（6小题，每题3分）1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用(A)存储......
2014－2015学年度第一学期《数据结构》期中考试试卷一、选择题（每题2分，共20分）1.计算机内部数据处理的基本单位是（ B ）。A.数据 B.数据元素C.数据项D.数据库 2.设语句x++的时间是......
数据结构试卷（六）一、选择题(30分) 1． 设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。(A) 20 (B) 30 (C) 40 (D) 45 2．执行一趟快速排序能够得到......
