发布时间 : 星期一 文章数据结构习题(1,2,3章)讲课稿更新完毕开始阅读abb3f4915222aaea998fcc22bcd126fff7055d01
精品文档
7．设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ ）
A．p->next=p->next->next; C．p=p->next->next;
B．p=p->next; D．p->next=p;
8．在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ ）
A．s->next=p->next; p->next=s B．q->next=s; s->next=p C．p->next=s->next; s->next=p D．p->next=s; s->next=q
9．线性表的顺序存储结构是一种（ ）的存储结构。
A．随机存取 存取
二．算法设计
1．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法（要求用最少的时间和最小的空间）
①确定在序列中比正整数x大的数有几个（相同的数只计算一次） ②将单链表中比正整数x小的偶数从单链表中删除
2．设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。
收集于网络，如有侵权请联系管理员删除
B．顺序存取 C．索引存取 D．散列
精品文档
p h Λ Λ h Λ 3．设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。
4. 假设链表A、B分别表示一个集合，试设计算法以判断集合A是否是集合B的子集，若是，则返回1，否则返回0，并分析算法的时间复杂度。
5．设有一单循环链表la，其结点有三个域：prior、data与next，其中data为数据域,，next域指向直接后继，prior域应指向直接前驱，但目前空着。试写一算法将此单循环链表改造为双向循环链表。
6．设顺序表用数组 A[]表示，表中元素存储在数组下标 1~m+n 的范围内，前 m 个元素递增有序，后 n 个元素递增有序，设计一个算法，使得整个顺序表有序。
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度。
收集于网络，如有侵权请联系管理员删除
精品文档
收集于网络，如有侵权请联系管理员删除
精品文档
第三章 栈和队列
一．选择题
1．已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ ）
A.5，4，3，2，1，6 B.2，3，5，6，1，4 C.3，2，5，4，1，6 D.1，4，6，5，2，3
2．在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ ）
A．top不变
B．top=0
C．top--
D．top++
3．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（ ）
A．rear％n= = front B．（front+l）％n= = rear C．rear％n -1= = front D．(rear+l)％n= = front
4．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（ ）
A．rear％n= = front B．front+l= rear C．rear= = front D．(rear+l)％n= front
5．在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ ）
A．front=front->next B．rear=rear->next C．rear=front->next D．front=rear->next
收集于网络，如有侵权请联系管理员删除