数据结构期中考试试题

本文格式为Word版，下载可任意编辑——数据结构期中考试试题期中试卷

一、单项选择题（共20题，每题2分，共40分）

1、数据的运算定义在数据的规律结构上，只有确定了(C)，才能具体实现这些运算。

A、数据对象B、规律结构C、存储结构D、数据操作

2、基本的规律结构包括(D)。

A、树型结构、图状结构、线性结构和非线性结构B、集合结构、线性结构、树型结构和非线性结构C、集合结构、树型结构、图状结构和非线性结构D、集合结构、线性结构、树型结构和图状结构

3、假使将与计算机软硬件相关的因素确定下来，那么一个特定算法的运行工作量就只依靠于(B)。A、计算机硬件B、实现算法的语言C、问题的规模D、编译生成的目标代码的质量

4、下面程序段执行的时间繁杂度为(C)。for(i=1;idata[k++]=A.data[i++];while(jdata[k++]=B.data[j++];____③____}

A、①C->data[k++]=A.data[i++];②C->data[k++]=B.data[j++];③C->length=k;B、①C->data[k++]=A->data[i++];②C->data[k++]=B->data[j++];③C->length=k;C、①C->data[j++]=A.data[i++];②C->data[j++]=B.data[k++];③C->length=j;D、①C->data[j++]=A->data[i++];②C->data[j++]=B->data[k++];③C->length=j;11、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(C)最节省时间。A、单链表B、单循环链表C、带尾指针的单循环链表D、带头结点的双循环链表

12、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是(B)。

A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL13、在双向链表指针p指向的结点前插入一个指针q指向的结点操作是()。A、p->prior=q;q->next=p;p->prior->next=q;q->prior=q;

B、p->prior=q;p->prior->next=q;q->next=p;q->Prior=p->prior;C、q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;D、q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;

14、链表不具有的特点是(B)。A、插入、删除不需要移动元素B、可随机访问任一元素

第2页共7页

期中试卷

C、不必事先估计存储空间

D、所需空间与线性表长度成正比15、当实际问题具有后进先出的特性且线性表有确定的最大长度，表长变化不大时应选择(B)作为线性表的存储结构。A、顺序栈B、链栈C、顺序队列D、链队列

16、若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是(C)。A、i-j-1B、i-jC、j-i+1D、不确定

17、有六个元素按6，5，4，3，2，1的顺序进栈，以下哪一个不是合法的出栈序列(C)。A、543612B、453126C、346521D、234156

18、用链接方式存储的队列，在进行删除运算时(D)。A、仅修改头指针B、仅修改尾指针

C、头、尾指针都要修改

D、头、尾指针可能都要修改

19、设有循环队列Q，其容量为QueueSize，队尾指针为rear，则队尾指针rear在循环意义下的加1操作为(D)。A、rear++B、Q->rear++

C、Q->rear=Q->rear%QueueSizeD、Q->rear=(Q->rear+1)%QueueSize

20、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再参与两个元素后，rear和front的值分别为()。A、1和5B、2和4C、4和2D、5和1二、是非判断题（共10题，每题2分，共20分），对打√，错打×。1、算法的5大特性为：有穷性，正确性，可行性，输入和输出。(2)2、数据结构研究的主要是数据的规律结构、存储结构和数据运算三方面内容。

(1)

3、取线性表的第i个元素的时间与i的大小有关。(2)4、顺序存储方式的特点是存储密度大，且插入和删除运算效率高。(1)

第3页共7页

期中试卷

5、单链表从任何一个结点出发，都能访问到所有结点。(2)6、对链表执行插入和删除操作时，不必移动结点。(2)7、在单链表L中，指针p所指结点有后继结点的条件是p->next!=NULL。

(1)

8、假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为b,c,a,e,d。(2)9、栈和队列都是线性表，只是在插入和删除时受到了一些限制。10、在链队中，即使不设置尾指针也能进行入队操作。

三、算法设计完善题（共4题，每题10分，共40分）1、已知顺序表描述如下：

#defineListSize100//假定表容量为100

typedefintDataType;//假定DataType代表的类型为int型typedefstruct{

DataTypedata[ListSize];//数组data用于存放表结点intlength;//当前表的长度（结点数）

}SeqList;

请将如下在顺序表（a1,a2,…,an）中删除第i个结点的算法填写完整。voidDeleteList(SeqList*L,inti){

intj;

if(iL->length){

puts(\删除位置错\

}

if(L->length==0){

puts(\空表不能删除\

}else

第4页共7页

(1)(1)期中试卷

{//请在答题纸中将代码填写完整

}}

2、已知链表的描述如下：

typedefcharDataType;//定义结点的数据域类型typedefstructnode{//结点类型定义

DataTypedata;//结点的数据域structnode*next;//结点的指针域}ListNode;//结构体类型标识符typedefListNode*LinkList;

请将如下尾插法建带头结点单链表的算法补充完整。LinkListCreatListRH(void){//用尾插法建立带头结点的单链表DataTypech;LinkListhead;

ListNode*s,*r;//工作指针

head=(ListNode*)malloc(sizeof(ListNode));r=head;//尾指针初值也指向头结点

printf(\请输入链表各结点的数据(字符型):\\n\//请在答题纸中将以下代码补充完整}

3、已