32.如题32图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F。能否在栈的输出端得到序列DCFEBA及EDBFCA？若能，给出栈操作的过程，若不能，简述其理由。
35.某带头结点的单链表的结点结构说明如下： typedef struct node1 { int data;
struct node1 *next }node；
试设计一个算法int copy(node *head1, node *head2)，将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。
3.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( ) A.5 B.6 C.7 D.9
4.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p指针所指向结点的表达式是( )
A.p→llink B.p→rlink C.p→llink→llink D.p→llink→rlink
5.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是( ) A. 110 B. 108 C. 100 D. 120
6.设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( ) A.DCBA B.CDAB C.DBAC D.DCAB
7.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为( )
A.top++ B.top-- C.top不变 D.top=0
17.设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为―p→next=head；‖和―________‖。 18.单链表中逻辑上相邻的两个元素在物理位置上______相邻。
19.在一个长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动的元素的个数是________。
31.如题31图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。
34.下面程序段为删除循环链表中第一个info域值等于x的结点，请填上程序中缺少的部分。循环链表的结构如题34图所示：
6
struct node{ int info; struct node *link; }
int Delete (struct node *head, int x)
{ struct node *p, *q; /*p:当前处理的结点；q：p的前驱结点*/
if (! head ) return (0); if (head→link ==head) { if (head→info==x)
{ free (head); head=NULL； return (x) } return (0); }
p=head; q=head;
while (q→link!=head) q=(1) ; while (p→link!=head) { if (p→info==x)
{ (2) ;
if (p==head) head=(3) ; free (p);return (x); }
else { q=p ;（4） ;} } return (0);
}
1．关于栈和队列的说法中正确的是（ ）
A．栈和队列都是线性结构 B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构 2．关于存储相同数据元素的说法中正确的是（ ）
A顺序存储比链式存储少占空间 B.顺序存储比链式存储多占空间
C.顺序存储和链式存储都要求占用整块存储空间 D.链式存储比顺序存储难于扩充空间 3．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ ） A．线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构
4．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（ ）
A．q→next=s；p→next=s； B.q→next=s；s→next=p； C.q→next=s；q→next=p； D.q→next=s；s→next=q； 5．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（ ） A．O(n) B.O(1) C.O(log2n) D.O(n2)
6．设一个栈的输入序列是a,b,c,d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（ ） A．a，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b 7．关于串的叙述中，正确的是（ ）
7
A．空串是只含有零个字符的串 B.空串是只含有空格字符的串
C.空串是含有零个字符或含有空格字符的串 D.串是含有一个或多个字符的有穷序列
8．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（ ） A．front==rear B.(front+1)%m==rear C.rear+1==front D.(rear+1)%m==front
9．设有二维数组A［n］［n］表示如下： ， 则A［i］［i］（0≤i≤n-1）的值为（ ）
A．i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 D.i2/2 18．在顺序表上读表元算法的时间复杂度为_______。
19．双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：S→next=P;S→prior=P→prior;P→prior=S;_______; 20．设数组A［0..8］［0..8］的起始元素位置为a，每个元素占2 L个存储单元，按行序为主序存储。若元素A［i］［j］的存储位置为a+66 L，则元素A［j］［i］的存储位置为_______。
29．有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。 34．设单链表的结点结构如下： struct node{datatype data; struct node*next; }
试编写一个函数int count(struct node *head,datatype x)统计单链表中数据域为x的结点个数。
3.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ）
A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表
4.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（ ） A.n-i B.n-i+1 C.n-i-1 D.i
5.顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（ ） A.s.elem［top］=e；s.top=s.top+1；
B.s.elem［top+1］=e；s.top=s.top+1；
C.s.top=s.top+1；s.elem［top+1］=e； D.s.top=s.top+1； s.elem［top］=e； 6.循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（ ） A.8 B.16 C.17 D.18
7.设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（ ） A.13 B.35 C.17 D.36
18.顺序表的存储密度为________，而链表的存储密度为______。 19.对于栈只能在________插入和删除元素。
20.在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为________。
3.对于长度为n的顺序表执行删除操作，则其结点的移动次数（ ）
A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n-1 D.最少为1，最多为n-1 4.在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是 （ A. p->next=q B. p->next=q->next C. p=q->next D. p->next=q->next->next 5.有关栈的描述，正确的是（ ） A.栈是一种先进先出的特殊的线性表
8
B.只能从栈顶执行插入、删除操作 C.只能从栈顶执行插入、栈底执行删除 D.栈顶和栈底均可执行插入、删除操作 6.二维数组A［10］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为（ ）
A.700 B.1120 C.1180 D.1140
18.对长度为n的顺序表执行删除操作，其删除算法在最坏情况下的时间复杂性为________________。 19.串是一种特殊的线性表，串常见的存储结构有顺序存储和________________两种方式。 20.我们通常把队列中允许插入的一端称为________________。
21.二维数组在机器级的具体实现，通常均采用________________存储结构。 34.试编写一个函数，以读取单链表的第i个元素。
3.若在长度为n的顺序表中插入一个结点，则其结点的移动次数( )
A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n+1 D.最少为1，最多为n+1
4.在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是( ) A.s->next=q；p->next=s->next B.p->next=q；p->next=s C.s->next=q->next；p->next=s D.s->next=q->next；p->next=s->next 5.若有一串数字5、6、7、8入栈，则其不可能的输出序列为( ) A.5、6、7、8 B.8、7、6、5 C.8、7、5、6 D.5、6、8、7 6.FORTRAN语言对数组元素的存放方式通常采用( ) A.按行为主的存储结构 B.按列为主的存储结构 C.按行或列为主的存储结构 D.按行和列为主的存储结构
18.对顺序表执行删除操作，其删除算法的平均时间复杂性为__________。
19.若head表示循环链表的头指针，t表示尾结点，则头指针head与尾结点t之间的关系可表示为_____。 20.我们通常把队列中允许删除的一端称为_______。
21.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是__________。
34.若循环单链表长度大于1，p为指向链表中某结点的指针，试编写一算法删除p结点的前驱结点。 3.下列关于线性表的叙述中，不正确的是( )
A.线性表是n个结点的有穷序列 B.线性表可以为空表
C.线性表的每一个结点有且仅有一个前趋和一个后继 D.线性表结点间的逻辑关系是1:1的联系 4.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是( ) A.p=p->next B.p->next=p->next C.p->next=p->next->next D.p->next=p 5.栈和队列( )
A.共同之处在于二者都是先进先出的特殊的线性表 B.共同之处在于二者都是先进后出的特殊的线性表
C.共同之处在于二者都只允许在顶端执行删除操作 D.没有共同之处
6.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是( )A.127 B.142 C.150 D.157 18.判断带头结点head的单链表为空的条件是___________。
19.若顺序表每个元素长度均为5，其中第一个元素的存储地址为30，则第6个元素的存储地址为____。
20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则判断循环队列为满的条件是_______。
21.对于顺序存储结构的二维数组，通常采用___________两种存放方式存储数据元素。 34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。
9
3.下列关于线性表的基本操作中，属于加工型的操作是（ ） A.初始化、求表长度、插入操作 B.初始化、插入、删除操作 C.求表长度、读元素、定位操作 D.定位、插入、删除操作
4.在一个单链表中，若p所指结点不是最后结点，s指向已生成的新结点，则在p之后插入s所指结点的正确操作是（ ）
A.s–>next=p–>next; p–>next=s; B.p–>next=s–>next; s–>next=p; C.s–>next=p; p–>next=s; D.s–>next=p–>next; p=s;
5.若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有（ ） A.3种 B.4种 C.5种 D.6种
6.C语言对数组元素的存放方式通常采用（ ） A.按行为主的存储结构 B.按列为主的存储结构 C.按行或列为主的存储结构 D.具体存储结构无法确定
18.对顺序表执行插入操作，其插入算法的平均时间复杂性为___________。
19.在具有n个单元、且采用顺序存储的循环队列中，队满时共有___________个元素。
20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则循环队列为空的条件是___________。
21.二维数组A[10][20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[0][0]的存储地址为300，则[A][10][10]的地址为___________。
34.设某单链表中，存在多个结点其数据值均为D，试编写一算法统计该类结点的个数。 2．设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（ A．O（log2n） B．O(n) C．O(nlog2n) D．O(n2)
3．在线性表的下列存储结构中，读取元素花费时间最少的是（ ） A．单链表 B．双链表 C．循环链表 D．顺序表
4．将一个头指针为p的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为（） q=NULL;
while (p!=NULL) { （ ） } p=q;
A．r=q; q=p; p=p -> next; q -> next=r; B．q=p; r=q; p=p -> next; q -> next=r; C．r=q; p=p -> next; q=p; q -> next=r; D．q=p; p=p -> next; r=q; q -> next=r; 5．数组通常具有两种基本运算，即（ ）
A．创建和删除 B．索引和修改 C．读和写 D．排序和查找
17．在顺序存储的线性表（a1,a2…，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动___个元素。 18．在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现： ______； sq -> data[sq -> top]=x；
19．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的______。
列。（5分）
29．如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序 34．设某头指针为head的单链表的结点结构说明如下：（6分） typedef struct node1 { int data;
struct node1*next
10