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