期中试卷
一、单项选择题（共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;i<=n;i++)
for(j=1;j<=i;j++) s++; A、O(n) B、O(lgn) C、O(n2) D、O(n3)
5、顺序表是线性表的( B )。 A.、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构
6、一个顺序表第一个元素的存储地址是100，每个元素的存储长度为4，则第5个元素的地址是( B )。 A、110 B、116 C、100 D、120
7、一个长度为n的顺序表中，在第i（1≤i≤n+1）个元素的位置上插入一个新元素时，需要向后移动( B )个元素。 A、n-i B、n-i+1 C、n-i-1 D、i
8、对于顺序表的优缺点，以下说法错误的是( D )。 A、无需为表示结点间的逻辑关系而增加额外的存储空间 B、可以方便地随机存取表中的任一结点 C、插入和删除运算较方便
D、容易造成一部分空间长期闲置而得不到充分利用
9、当对线性表的操作是以插入操作和删除操作为主时或当线性表的长度不能确定或表长变化很大时，应选择( D )作为线性表的存储结构。 A、顺序表 B、链表
第 1 页 共 7 页
期中试卷
C、栈 D、队列
10、顺序表A和B，其元素均按由小到大的升序排列。下列算法将它们合并成一个元素也是由小到大的升序排列的顺序表C。下列选项中能完成此功能的语句序列为( C )。
void Merge(SeqList A, SeqList B,SeqList *C) {
int i,j,k; i=0;j=0;k=0;
while(i
C-> data[k++]=A.data[i++]; while(j C-> data[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==NULL B、head->next==NULL C、head->next==head D、head!=NULL 13、在双向链表指针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-1 B、i-j C、j-i+1 D、不确定 17、有六个元素按6，5，4，3，2，1 的顺序进栈，下列哪一个不是合法的出栈序列( C )。 A、5 4 3 6 1 2 B、4 5 3 1 2 6 C、3 4 6 5 2 1 D、2 3 4 1 5 6 18、用链接方式存储的队列，在进行删除运算时( D )。 A、仅修改头指针 B、仅修改尾指针 C、头、尾指针都要修改 D、头、尾指针可能都要修改 19、设有循环队列Q，其容量为QueueSize，队尾指针为rear，则队尾指针rear在循环意义下的加1操作为( D )。 A、rear++ B、Q->rear++ C、Q->rear= Q->rear %QueueSize D、Q->rear= (Q->rear+1) %QueueSize 20、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。 A、1和 5 B、2和4 C、4和2 D、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、已知顺序表描述如下： #define ListSize 100 //假定表容量为100 typedef int DataType;//假定DataType代表的类型为int型 typedef struct{ DataType data[ListSize];//数组data用于存放表结点 int length; //当前表的长度（结点数） } SeqList; 请将如下在顺序表（a1,a2,…,an）中删除第i个结点的算法填写完整。void DeleteList(SeqList *L,int i) { int j; if (i<1||i>L->length) { puts(\删除位置错\ } if (L->length==0) { puts(\空表不能删除\ } else 第 4 页 共 7 页 ( 1 ) ( 1 ) 期中试卷 {//请在答题纸中将代码填写完整 } } 2、已知链表的描述如下： typedef char DataType; //定义结点的数据域类型 typedef struct node { //结点类型定义 DataType data; //结点的数据域 struct node *next; //结点的指针域 }ListNode; //结构体类型标识符 typedef ListNode *LinkList; 请将如下尾插法建带头结点单链表的算法补充完整。 LinkList CreatListRH(void) {//用尾插法建立带头结点的单链表 DataType ch; LinkList head; ListNode *s,*r;//工作指针 head=(ListNode *)malloc(sizeof(ListNode)); r=head;//尾指针初值也指向头结点 printf(\请输入链表各结点的数据(字符型):\\n\ //请在答题纸中将以下代码补充完整 } 3、已知链栈的描述如下: typedef char DataType;//假定栈元素的类型为字符类型 typedef struct stacknode {//结点的描述 DataType data; struct stacknode *next; }StackNode; 第 5 页 共 7 页