学习-----好资料
第一章 复习题
1.简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。
答：在顺序结构中，逻辑关系上相邻的两个元素在物理位置上也相邻。而链式存储结构中，数据元素之间关系是由结点中指针指示的。 2.数据结构是一门……的学科。
3.在数据结构中，从逻辑上可以把数据结构分成（ C ）。 A、动态结构与静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构
4.编写一个函数，用不多于3n/2的平均比较次数，在一个数组中找出最大和最小值元素。 void maxmin(int a[],int n) {
max=min=a[0]; for(i=1;i if(a[i]>max) max=a[i]; else if(a[i] printf(“max=%d, min=%d”,max, min); } 第二章 复习题 1．下述哪一条是顺序存储结构的优点？（ A ） A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>=0） 。 A．表元素 B．字符 C．数据元素 D．数据项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表 B．单循环链表 C．带头结点的双循环链表 D．双链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采更多精品文档 学习-----好资料 用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 6．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A．单链表 B．双向链表 C．单循环链表 D．带头结点的双向循环链表 7. 链表不具有的特点是（ B ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 8. 下面的叙述不正确的是（ BC ） A. 线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 9. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 10. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 11．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ） A．O（i） B．O（1） C．O（n） D．O（i-1） 12．非空的循环单链表head的尾结点p满足（ A ）。 A．p->next==head B．p->next==NULL C．p==NULL D．p== head 13．循环链表H的尾结点P的特点是（ A ）。 A．P->NEXT==H B．P->NEXT== H->NEXT C．P==H D．P==H->NEXT 14．完成在双循环链表结点p之后插入s的操作是（ D ）； A． p->next=s ; s->prior=p; p->next->prior=s ; s->next=p->next; B． p->next->prior=s; p->next=s; s->prior=p; s->next=p->next; C． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s ; D． s->prior=p; s->next=p->next; p->next->prior=s ; p->next=s; 15．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( D )。 A. p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior; 更多精品文档 学习-----好资料 B. q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next; C. q->next=p; p->next=q; p->prior->next=q; q->next=p; D. p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q; 16．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ Ｂ ）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 17．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ Ｂ ） A．head==NULL B．Head->next==NULL C．Head->next==head D．head!=NULL 18 在双向链表中，删除p所指的结点时须修改指针（ A ）。 A． p->prior->next=p->next; p->next->prior=p->prior; B． p->prior=p->prior->prior; p->prior->next=p; C． p->next->prior=p; p->next=p->next->next D． p->next=p->prior->prior . p->prior=p->next->next; 19．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。 20．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1)/2 21．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:py->next=px->next; px->next=py 22．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动n-i+1个元素。 23．对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为O(1),在给定值为x的结点后插入一个新结点的时间复杂度为O(n) 24．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表，和多重链表；而又根据指针的连接方式，链表又可分成（动态）链表和静态链表 25.循环单链表的最大优点是：从任一结点出发都可访问到链表中每一个元素 26. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是q=p->next;p->next=q->next; free (q); 27. 带头结点的双循环链表L中只有一个元素结点的条件是：L->next->next==L 28. 在单链表L中，指针p所指结点有后继结点的条件是：p->next!=null 29.带头结点的双循环链表L为空表的条件是：L->next==L && L->prior==L 30. 在单链表p结点之后插入s结点的操作是： s->next=p->next;p->next=s; 第三章 复习题 1. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元更多精品文档 学习-----好资料 素是（ B ）。 A. 不确定 B. n-i+1 C. i D. n-I 2. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 3. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ B ） A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 4. 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( C )。 A．top=top+1; V [top]=x B. V [top]:=x; top:=top+1 C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1 5. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 6. 用链接方式存储的队列，在进行删除运算时（ D ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 7. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m 8. 循环队列存储在数组A[0..m]中，则入队时的操作为（ D ）。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 9. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 10. 栈和队列的共同点是（ C ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 11. 栈和队都是（ ） A．顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构 更多精品文档
