数据结构第一教学单元单元测验
一、选择
1.下列叙述中关于好的编程风格，正确的描述是：
A.程序中的注释是可有可无的
B.对递归定义的数据结构不要使用递归过程
C.递归应是封闭的，尽量少使用全局变量 D.多采用一些技巧以提高程序运行效率
2.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。以下解释错误的是( )
A.正确性 算法应能正确地实现预定的功能(即处理要求)
B.易读性 算法应易于阅读和理解 以便于调试 修改和扩充
C.健壮性 当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果
D.高效性 即达到所需要的时间性能
3.以下说法正确的是 ( )
A.数据元素是数据的最小单位 B.数据项是数据的基本单位
C.数据结构是带有结构的各数据项的集合 D.数据结构是带有结构的数据元素的集合
4.下面关于线性表的叙述中，错误的是哪一个？（ ）
A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链接存储，不必占用一片连续的存储单元。
D.线性表采用链接存储，便于插入和删除操作。
5.链表不具有的特点是：
A.可随机访问任一个元素 B.插入删除不需要移动元素
C.不必事先估计存储空间 D.所需空间与线性表长度成正比
6.线性表是具有n个（ ）的有限序列
A．表元素 B．字符 C．数据元素 D．数据项 7.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( ．信息项
)最节省时间。
E
A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表
8.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）
A．O（i） B．O（1） C．O（n） D．O（i-1）
9.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。
A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;
10.在一个单链表中，若删除p所指结点的后续结点，则执行（ ）
A、p->next=p->next->next; B、p=p->next; p->next=p->next->next;
C、p->next=p->next; D、p=p->next->next;
11.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL
12.循环链表H的尾结点P的特点是（ ）。
A．P->NEXT==H B．P->NEXT==H->NEXT C．P==H D．P==H->NEXT
13.完成在双循环链表结点p之后插入s的操作是（ ）；
A． p->next=s ; s->prior=p; p->next->prior=s ; s->next=p->next;
B． p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;
C． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s ;
D． s->prior=p; s->next=p->next; p->next->prior=s ; p->next=s;
14.栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
15.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
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
16.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是（ ）
A.2 B.3 C.5 D.6
17.表达式a*(b+c)-d的后缀表达式是( )。
A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd
18.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（ ）
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
19.循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A.rear=rear+1 B. rear=(rear+1)% (m-1)
C.rear=(rear+1)% m D. rear=(rear+1)%(m+1)
20.循环队列的队满条件为（ ）
A.(sq.rear+1) % mazsize ==(sq.front+1) % maxsize; B.(sq.rear+1)% ==sq.front+1
C.(sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front
21.循环队列的队空条件为（ ）
A.(sq.rear+1) % maxsize ==(sq.front+1) % maxsize B.(sq.rear+) % ==sq.front+1
C.(sp.rear+1) % maxsize ==sq.front D.sq.rear == sq.front
maxsize maxsize 22.以下哪一个不是队列的基本运算？（ ）
A.在队列第i个元素之后插入一个元素。
B.从队头删除一个元素。
C.判断一个队列是否为空。
D.读取队头元素的值。
23.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（个不同的字符串。
A.14 B.5 C.6 D.8
24.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（ ）个元素。
A. n B.n-1 C. n+1 D.不确定
25. 栈在（ ）中应用。
A.递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ
二、填空题
1.算法的五个重要特性是:___ __
）
2.下面程序段的时间复杂度是__ _
i=1;
while(i<=n)
i=i*3;
3.一个好的算法应当具有下列好的特性：正确性、 、 和效率和低存储需求。
4.采用顺序存储结构的线性表，其每个元素占用Ｌ个单元。第一个元素的地址为Ｎ，则第i个元素的存储位置为 。
5.已知栈的输入序列为1、2、3……n 输出序列为a1,a2,…,an 符合a2=n的输出序列共有 种。
6.在一个单链表中p所指结点之前插入一个由指针s所指结点，可依次执行以下操作：
s->next=_ _; p->next=s; t=p->data; p->data=_ _; s->data= _; 三、判断题
1.在顺序表中取出第i个元素所花费的时间与i成正比
2.线性表的长度是线性表所占用的存储空间的大小
3.在对链队列作出队列操作，不会改变front指针的值
4.双循环链表中，任一个结点的后继指针均指向其逻辑后继
5.已知指针P指向链表L中某结点，执行语句P=P->next不会删除该链表中结点
6.在链队列中，即便不设置尾指针也能进行入队列操作
7.栈和队列都是运算受限的线性表
8.在带头结点的单循环链表中，任一结点的后继指针均不空
9.线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是O(N)，因而两种存储方式的插入、删除运算所花费的时间相同
10.对任何数据结构链式存储结构一定优于顺序存储结构
四、算法设计
1.带头结点的单链表，其长度存放在头结点的数据域中，设计一算法求倒数第k个结点的值，并且删除该结点。要求：
（1）用类C语言描述该单链表
（2）写出解决该问题的类C语言算法过程
2.给出利用栈和队列判断任意输入但以’@’结束的字符串是否回文的算法思想。并写出算法
因篇幅问题不能全部显示，请点此查看更多更全内容