三、判断题
1、单链表不是一种随机存储结构。 ?
2、在具有头结点的单链表中，头指针指向链表的第一个数据结点。?
3、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。? 4、顺序存储方式只能用于存储线性结构。?
5、在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。? 6、链式存储的线性表可以随机存取。?
7、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结构。?
四、程序分析填空题
1、函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。 int GetElem(LinkList L,int i,Elemtype &e){ LinkList p；int j；
p=L->next;j=1;
while(p&&j } if(!p||j>i) return ERROR; e= (2) ; return OK; } 答案：(1)p=p->next (2)p->data 2、函数实现单链表的插入算法，请在空格处将算法补充完整。 int ListInsert(LinkList L,int i,ElemType e){ LNode *p,*s;int j; p=L;j=0; while((p!=NULL)&&(j if(p==NULL||j>i-1) return ERROR; s=(LNode *)malloc(sizeof(LNode)); s->data=e; (1) ; (2) ; return OK; }/*ListInsert*/ 答案：(1)s->next=p->next (2)p->next=s 3、函数实现单链表的删除算法，请在空格处将算法补充完整。 int ListDelete(LinkList L,int i,ElemType &e){ LNode *p,*q; int j; p=L;j=0; while(( （1） )&&(j if(p->next==NULL||j>i-1) return ERROR; q=p->next; （2） ; e=q->data; free(q); 5 return OK; }/*listDelete*/ 答案：(1)p->next!=NULL (2)p->next=q->next 4、写出算法的功能。 int func(LinkList L){ LinkList p=L; int n=0; while(p!=NULL) { p=p->next; n++; } return(n); } 答案：求单链表head的长度 第三章 栈和队列 一、选择题 1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（ ）。 A. a,b,c,d,e B. d,e,c,b,a C. d,c,e,a,b D. e,d,c,b,a 2、判断一个循环队列Q（最多n个元素）为满的条件是（ ）。 A. Q->rear==Q->front B. Q->rear==Q->front+1 C. Q->front==(Q->rear+1)%n D. Q->front==(Q->rear-1)%n 3、设计一个判别表达式中括号是否配对的算法，采用（ ）数据结构最佳。 A. 顺序表 B. 链表 C. 队列 D. 栈 5、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（ ）。 A. 1243 B. 2134 C. 1432 D. 4312 E. 3214 6、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。 A. 1和5 B. 2和4 C. 4和2 D. 5和1 7、队列的插入操作是在（ ）。 A. 队尾 B. 队头 C. 队列任意位置 D. 队头元素后 9、一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（ ）。 A. *S->top=e;S->top++; B. S->top++;*S->top=e; C. *S->top=e D. S->top=e; 10、表达式a*(b+c)-d的后缀表达式是（ ）。 A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 11、将递归算法转换成对应的非递归算法时，通常需要使用（ ）来保存中间结果。 A. 队列 B. 栈 C. 链表 D. 树 12、栈的插入和删除操作在（ ）。 A. 栈底 B. 栈顶 C. 任意位置 D. 指定位置 13、五节车厢以编号1，2，3，4，5顺序进入铁路调度站（栈），可以得到（ ）的编组。 A. 3，4，5，1，2 B. 2，4，1，3，5 C. 3，5，4，2，1 D. 1，3，5，2，4 14、判定一个顺序栈S（栈空间大小为n）为空的条件是（ ）。 A. S->top==0 B. S->top!=0 C. S->top==n D. S->top!=n 15、在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ ）。 6 A. front=front->next B. s->next=rear;rear=s C. rear->next=s;rear=s; D. s->next=front;front=s; 16、一个队列的入队序列是1，2，3，4，则队列的出队序列是（ ）。 A. 1，2，3，4 B. 4，3，2，1 C. 1，4，3，2 D. 3，4，1，2 17、依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（ ）。 A. a B. b C. c D. d 18、正常情况下，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是（ ）。 A. top不变 B. top=0 C. top=top+1 D. top=top-1 19、判断一个循环队列Q（空间大小为M）为空的条件是（ ）。 A. Q->front==Q->rear B. Q->rear-Q->front-1==M C. Q->front+1=Q->rear D. Q->rear+1=Q->front 21、当用大小为N的数组存储顺序循环队列时，该队列的最大长度为（ ）。 A. N B. N+1 C. N-1 D. N-2 22、队列的删除操作是在（ ）。 A. 队尾 B. 队头 C. 队列任意位置 D. 队头元素后 23、若让元素1，2，3依次进栈，则出栈次序不可能是（ ）。 A. 3，2，1 B. 2，1，3 C. 3，1，2 D. 1，3，2 24、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ ）。 A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 25、在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ ）结构。 A. 堆栈 B. 队列 C. 数组 D. 线性表 26、栈和队列都是（ ）。 A. 链式存储的线性结构 B. 链式存储的非线性结构 C. 限制插入删除位置的线性结构 D. 限制存取点的非线性结构 27、在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的操作是（ ）。 A. front=front->next B. rear= rear->next C. rear->next=front D. front->next=rear 28、队和栈的主要区别是（ ）。 A. 逻辑结构不同 B. 存储结构不同 C. 所包含的运算个数不同 D. 限定插入和删除的位置不同 二、填空题 1、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是 。 答案：3 2、一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为： 。 答案：(rear-front+M)%M 3、在具有n个元素的循环队列中，队满时具有 个元素。 答案：n-1 4、设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为 。 答案：61 5、已知循环队列的存储空间大小为20，且当前队列的头指针和尾指针的值分别为8和3，且该队列的 7 当前的长度为_______。 答案：15 三、判断题 1、栈和队列都是受限的线性结构。? 3、以链表作为栈的存储结构，出栈操作必须判别栈空的情况。? 四、程序分析填空题 1、已知栈的基本操作函数： int InitStack(SqStack *S); //构造空栈 int StackEmpty(SqStack *S);//判断栈空 int Push(SqStack *S,ElemType e);//入栈 int Pop(SqStack *S,ElemType *e);//出栈 函数conversion实现十进制数转换为八进制数，请将函数补充完整。 void conversion(){ InitStack(S); scanf(“%d”,&N); while(N){ （1） ; N=N/8; } while( （2） ){ Pop(S,&e); printf(“%d”,e); } }//conversion 答案：（1）Push(S,N%8) （2）!StackEmpty(S) 2、写出算法的功能。 int function(SqQueue *Q,ElemType *e){ if(Q->front==Q->rear) return ERROR; *e=Q->base[Q->front]; Q->front=(Q->front+1)%MAXSIZE; return OK; } 答案：出队。删除顺序队列Q的队头元素，并将被删元素保存至形参e 第四章 串 一、选择题 1、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（ C ）。 A. 连接 B. 求子串 C. 模式匹配 2、串与普通的线性表相比较，它的特殊性体现在（ C ）。 A. 顺序的存储结构 B. 链式存储结构 C. 数据元素是一个字符 D. 数据元素任意 3、空串和空格串（ B ）。 D. 判断子串 8