《数据结构》学习中心：专业：学号：姓名：作业练习一(第二章)一、选择题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的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移( )个元素。

A)n-i B)n-i+1 C)n-i-1 D)i7、( )运算中，使用顺序表比链表好。

A)插入B)删除C)根据序号查找 D)根据元素值查找8、个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。

A) O(1) B) O(n) C) O(n2) D) O(log2n)9、在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移( )个元素。

A)n-i B)n-i+1 C)n-i-1 D)i10、在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x 同元素的平均比较次数，假定查找每个元素的概率都相等）为( )。

A)n B)n/2 C)(n+1)/2 D)(n-1)/211、在一个带头结点单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。

A)HL = p; p->next = HL;B)p->next = HL; HL = p;C)p->next = HL; p = HL; D)p->next = HL->next; HL->next = p;12、在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行( )。

A)q->next = p->next ; p->next = q; B)p->next = q->next; q = p;C)q->next = p->next; p->next = q; D)p->next = q->next ; q->next = p;13、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行( )。

A)p = q->next ; p->next = q->next; B)p = q->next ; q->next = p;C)p = q->next ; q->next = p->next; D)q->next = q->next->next; q->next = q;14、在双向链表指针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;二、填空题1、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为（）,在给定值为x的结点后插入一个新结点的时间复杂度为（）。

2、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成（）和（）。

3、顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示元素之间的关系的。

4、对于双向链表,在两个结点之间插入一个新结点需修改( )个指针，单链表为( )个。

5、循环单链表的最大优点是( ) 。

6、在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在( )结点的next域中。

7、带头结点的双循环链表L为空表的条件是（）。

8、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用( )存储结构。

三、问答题与算法题1、试描述头指针、头结点、首结点的区别、并说明头指针和头结点的作用。

2、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?3、为什么在单循环链表中设置尾指针比设置头指针更好?4、写出下图双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。

结点结构为：(prior,data,next)5、下述算法的功能是什么?LinkList ABC(LinkList L){ // L 是无头结点单链表if( L&&L->next ){ Q=L;L=L->next;P=L;P->next=Q; Q->next=NULL;}return L;}6、V oid AA(SqList &L, int i, int x){ if(i>=1&&i<=Length(L)){ FOR(j= Length (L);j>=i;j - -)A[j+1]=A[j];A[i]=x;}else exit(ERROR);}假定调用该算法时线性表L的内容为（15，26，37，48，55），i为3,x为51，则调用返回后该单链表的内容变为什么?7、设顺序表L是一个递减有序表，试写一算法，插入元素x，插入后仍保持L的有序性。

V oid sinsert(Sqlist &S, int x)8、写出从一个带头结点．．．．的单链表中删除其值等于给定值x的结点的算法函数。

Int delete(LinkList &L, int x){9、已知递增有序的两个带头结点．．．．的单链表La，Lb分别存储了一个非空集合A,B。

设计算法实现求两个集合的并集的运算A=A∪Bvoid mergelist(linklist &La, linklist Lb)10、设计算法将不设表头结．．．的单向链表就地逆转。

．．．．．点．的不循环（第三章）一、选择题1、对于栈操作数据的原则是（）。

A)先进先出 B)后进先出 C)后进后出 D)不分顺序2、一般情况下，将递归算法转换成非递归应通过设置（）实现。

A)数组；B)线性表；C)队列；D)栈。

3、栈和队列的共同点是（）A)都是先进后出B)都是先进先出C)只允许在端点处插入和删除元素D)没有共同点4、个栈的入栈序列是abcde，则栈的不可能的输出序列是()。

A)edcba B) decba C)dceab D)abcde5、在对栈的操作中，能改变栈的结构的是()。

A)StackLength(S) B)StackEmpty(S) C)GetTop(S) D)ClearStack(S)6、在一个栈顶指针为HS的(不带头结点)链栈中将一个S指针所指的结点入栈,执行()。

A)HS->next=s; B)S->next=HS->next;HS->next=s;C)S->next=HS; HS=s; D)S->next=HS;HS=HS->next;7、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列是p1,p2,p3，…，pn，若p1=n，则pi=( )。

A)I B)n-i C)n-i+1D)不确定8、若用一个大小为６的数组来实现循环队列，且当前尾指针rear和头指针front的值分别为０和３，当从队列中删除一个元素，再加入两个元素后，尾指针rear和头指针front的值分别是（）。

A)１和５；B)２和４；C)４和２；D)５和１。

9、输入序列为ABC，可以变为BAC时，经过的栈操作为（）A)push,pop,push,pop,push,pop B)push,push,push,pop,pop,popC)push,push,pop,pop,push,pop D)push,pop,push,push,pop,pop10、设用一个大小m=60的顺序表A［m］表示一个循环队列，如果当前的尾指针rear=32，头指针front＝15, 则当前循环队列的元素个数是( )。

A)42 ；B)16 ；C)17 ；D)41 。

11、设用顺序表a[n]表示循环队列，头、尾指针分别为front和rear，则判断队列为空的条件是（），判断队列满的条件是（）。

（1）A)a.front +1= =a.rear ；B)a.front = = a.rear +1；C)a.front = = 0 ；D)a.front = = a.rear。

（2）A)(a.rear -1) % n = a.front ；B)(a.rear +1) % n = a.front；C) a.rear =( a.front-1) % n；D)a.rear = (a.front +1) % n 。

12、循环队列存储在数组A[0..m]中，则入队时的操作为（）。

A)rear=rear+1 B)rear=(rear+1) mod (m-1)C)rear=(rear+1) mod m D)rear=(rear+1)mod(m+1)13、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，该缓冲区应该是一个（）结构。

A)栈；B)队列；C)数组；D)线性表。

二、填空题1、在栈中，可进行插入和删除操作的一端称( )。

2、在作进栈运算时,应先判别栈是否( ),在作退栈运算时应先判别栈是否( )。

当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( )。