数据结构：期中练习题

一、选择题

1．把长度为m的单链表LB接在长度为n的单链表LA之后的算法的时间复杂度为( )

A．O(m) B．O(n) C．O(m+n) D．O(1) 2．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）

A．插入 B．删除 C．定位 D．排序

3．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ ）

A．3，2，6，1，4，5 B．5，6，4，2，3，1 C．1，2，5，3，4，6 D．3，4，2，1，6，5

4．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2,1)的值为（ ）

A．15 B．16 C．17 D．18

5．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（ ） A. 108 B. 112 C. 116 D. 120

6．有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是( ) A. 访问第i个节点（1≤i≤n）

B. 在第i个节点后插入一个新节点（1≤i≤n） C. 删除第i个节点（1≤i≤n） D. 将n个节点从小到大排序

7. 将递归过程转化为非递归过程需用到( )

第 1 页 共 6 页

A．栈 B．队 C．线性表 D．链表

8．在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指结点，则执行（ ）

A. s->next=p; p->next=s B. p-next=s; s->next=p

C. p=s; s->next=p->next D. s->next=p->next; p->next=s

9. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。

A. |top[2]-top[1]|=1 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2]

10.为解决计算机主机与打印机之间速度不匹配的问题通常设置一个打印数据缓冲区。打印机将要打印输出的数据一次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ） A．栈 B.队列 C.树 D.图

11.在链表中最常用的操作是删除表中最后一个结点和在最后一个结点之后插入元素， 则采用( ) 最节省时间。 A．头指针的单向循环链表 B．双向链表

C．带尾指针的单向循环链表 D．带头指针双向循环链表 12.链表不具有的特点是（）。

A.可随机访问任一元素 B.插入、删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与线性表长度成正比 13.一个栈的入栈序列为a,b,c,d,e，那么不可能出现输出序列为( )

第 2 页 共 6 页

A. edcba B decba C dceab D abcde

14. 若串S=’software’,其子串的数目是（ ）。

A．8 B．37 C．36 D．9

二、填空题

1. 在顺序栈中，当栈顶指针top＝-1时，表示_____；当top=MaxSize-l时，表示_____。

2. 假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为___。

3. 在一个长度为n的单链表L中，删除链表中p所指第i个结点的前驱的时间复杂度为__。

4. 在具有n个单元的循环队列中，队满时共有 个元素。 5. 对于栈只能在_______插入和删除元素。

6. 设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为 。

7. 在单循环链表L中，指针p所指结点为尾结点的条件是 。 8. 在单链表中，删除指针p所指结点的后继结点的语句是 。 9. 若某串的长度小于一个常数，则采用 存储方式最节省空间。

10. 在一个带头结点的单向循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为 。

11.在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s

第 3 页 共 6 页

所指的结点，则需执行下列语句：

s-> next=p； s->prior= ________；p->prior=s；________=s； 三、判断题

1. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

2. 栈和队列都是限制存取点的线性结构。

3. 设栈的输入序列是1、2、?、n，若输出序列的第一个元素是n，则第i个输出元素是n-i+1。

4. 链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。

5. 在用单链表表示的链式队列中，队头在链表的链尾位置。 6. 在栈满情况下不能作进栈操作，否则产生“上溢”。 7. 线性表的长度是线性表所占用的存储空间的大小。

8. 双循环链表中，任意一结点的后继指针均指向其逻辑后继。 9. 在对链队列做出队操作时，不会改变front指针的值。 10. 如果两个串含有相同的字符，则说它们相等。 11. 线性表就是顺序表。

12. 设指针p指向单链表中的一个结点，则语句序列u=p->next; u=u->next将删除一个结点。 13. 链表的每个节点都恰好有一个指针。

14. 链式存储结构中一个结点的空间可以不连续。

15. 长度为m的单链表连接在长度为n的单链表之后的算法的时间复杂度为O(n)。

第 4 页 共 6 页

四、算法填空或显示输出结果。 1. void AE(Stack& S){

InitStack(&S);

int x,y, i,a[5]={1,5,8,12,15}; Push(&S,3);Push(&S,4); Pop(&S,&x); Pop(&S,&y);

x =x+2*y;

Push(&S,x);

for(i=0;i<5;i++) Push(&S,2*a[i]); while(!StackEmpty(S))

{ Pop(&S,&x);printf(“%d ”,x);}

}

该算法被调用后得到的输出结果为：

2．PROC ins__linklist(linkisttp la, integer i, elemtp b)

{//la为指向带头结点的单链表的头指针，本算法在表中第i个元素之前插入元素b}

p=(1) ; j=(2) ;{指针初始化，j为计数器}

WHILE (p<>NULL) AND ((3) ) DO [p=(4) ; j=j+1；]

{寻找第 i-1 个结点}

IF (p=NULL) OR ((5) ) THEN error (‘No this position’)

ELSE {new(s) ; s->data=b; s->next=p->next; p->next=s;} 3. 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

第 5 页 共 6 页

void reverse(linklist * h) /* h为附加头结点指针； */ { linklist *p,*q;

p=h->next; h->next=NULL;

while((1)________)

{q=p; p=p->next; q->next=h->next; h->next=(2)________; }

第 6 页 共 6 页

}

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新高中教育数据结构：期中练习题 全文阅读和word下载服务。