发布时间 : 星期四 文章数据结构习题1更新完毕开始阅读0c9897303968011ca30091a9
1、对于双向链表，在两个结点之间插入一个新结点时需修改的指针共有_____个，单链表为_____个。
2、对一个循环单链表中，表尾结点的指针域与表头指针值_____。
3、在线性表的顺序存储中，元素之间的逻辑关系是通过_____决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_____决定的。
4、单链表表示法的基本思想是用_____表示结点间的逻辑关系。 5、头结点的next 域值是指示单链表的_____。
6、线性表的两种存储结构分别为_____和_____。 7、在线性表的单链表存储中，若一个元素所在结点地址为p，则其后继结点的地址为_____。 8、线性表的逻辑结构是_____结构，其所含结点的个数称为线性表的_____。 9、表长为０的线性表称为_____。
10、通常将链接方式存储的线性表称为_____，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。 参考答案：
一、 选择题：
1、C 2、C 3、D 4、A 5、D 6、C 7、C 8、D
9、A 10、D 11、C 二、 填空题
1、4 2 2、相同 3、物理存储位置 链指针 4、指针 5、第一个数据结点存储地址 6、顺序 链接 7、p->next 8、线性 长度 9、空表 10 链表 三、算法设计
1、假设有两个按元素递增有序排列的线性表Ａ和Ｂ，均以单链表作存储结构。请编写算法，将表Ａ和表Ｂ归并成一个按元素值非递减有序（允许值相同）排列的线性表Ｃ，并要求利用原表（即表Ａ和表Ｂ）的结点空间存放表Ｃ。 Lklist connect(lklist *a,lklist *b) {lklist *p,*q,*r,*u,*c; p=a->next; q=b->next; C=a; r=a;
while(p!=NULL)&&(q!=NULL) switch
{case p->data>q->data: {u=q->next;
r=q; q->next=p; q=u;
}
case p->data<=q->data; {r=p; p=p->next; }}
if(q!=NULL) r>next=q;
r->next=q; return(c);}
2、设有头结点的单链表Ｌ，编程对表中任一值只保留一个结点，删除其余值相同的结点。 DelElem(lklist *L); {pointer *p, *t,*pre; p=L->link; t=p;
while(p!=NULL) {pre=t; t=t->link; do
24
{while(t!=NULL)&&(t->data!=p->data) {pre=t; t=t->link; }
if(t!=NULL) {pre->next=t->next; free(t); t=pre->link; }
}while(t!=NULL); p=p->link; t=p;
}}
3、有一带头结点的单链表，编程将链表颠倒过来，要求不用另外的数组或结点完成。 Void reverse(lklist *h); {lklist *p, *q;
p=h->next;
h->next=NULL;
while(p->next!=NULL) {q=p; p=p->next;
q->next=h->next; h->next=q; } }
4、设计将一个双向循环链表逆置的算法。 Invert(dlklist *head) {dlklist *p, *q; p=head; do
{q=p->next;
p->next=-p->pre; p->pre=q; p=q;
}while(p!=head); }
习
一、选择题：
题三
1、若用一个大小为６的数组来实现循环队列，且当rear和front的值分别为０和３。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？
A、1和5 B、2和4 C、4和2 D、5和1 2、设栈的输入序列是（1、2、3、4），则 不可能是其出栈序列。
A、1243 B、2134 C、1432 D、4312 E、3214
25
3、设栈S和队列Q的初始状态为空，元素e1、e2、e3 、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2 、e4 、e3 、e6、e5、e1，则栈S的容量至少应该是_____。
A、6 B、4 C、3 D、2
4、假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是_____。
A、front+1==rear B、front==rear+1 C、front==0 D、front==rear 5、假定一个顺序循环队列存储于数组A[n]中，其队首和队尾指针分别用front和rear表示，则判断队满的条件是_____。
A、（rear-1）%n==front B、(rear+1)%n==front C、 rear==(front-1)%n D、rear==(front+1)%n 6、栈的插入和删除操作在_____进行。
A、栈顶 B、栈底 C、任意位置 D、指定位置
7、当利用大小为N的数组存储顺序循环队列时，该队列的最大长度为_____。 A、 N-2 B、 N-1 C、 N D、 N+1 8、如果以链表作为栈的存储结构，则退栈操作时_____。 A、必须判别栈是否满 B、判别栈元素的类型 C、必须判别栈是否空 D、对栈不作任何判别 9、链栈与顺序栈相比有一个明显的优点，即_____。
A、插入操作更加方便 B、通常不会出现栈满的情况 C、不会出现栈空的情况 D、 删除操作更加方便
二、填空题：
1、表达式求值是_____应用的一个典型例子。 2、队列是特殊的线性表，其特殊性在于_____。
3、向一个循环队列存入新元素时，需要首先移动_____，然后再向它所指位置_____新元素。 4、设输入元素的顺序为1、2、3、4、5，要在栈S的输出端得到43521，则应进行栈的基本运算表示应为：push(S,1),push(S,2),push(S,3),push(S,4),pop(S), _____,pop(S),pop(S),pop(S)。 5、__ ___又称作先进先出表。
6、栈是特殊的线性表，其特殊性在于__ ___。 7、栈又称为___ __表，队列又称为__ ___表。 参考答案： 一、 选择题：
1、B 2、D 3、C 4、D 5、B 6、A 7、B 8、C 9、B
二、填空题：
1、栈 2、只允许在表的一端进行元素插入而在另一端进行元素的删除
3、队尾指针 存入 4、pop(s),push(s,5) 5、队列 6、只允许在栈顶加入或删除元素 7、后进先出 先进先出 三、算法设计
1、请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH（ST，X）：元素X入ST栈；POP（ST，X）：ST栈顶元素出栈，赋给变量X；Sempty(ST)：判ST栈空否。那么如何用栈的运算来实现该队列的三个运算：enqueue：插入一个元素入队列；dequeue：删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释）
26
一个栈s1用来插入元素，另一个栈用来删除元素，删除元素时应将前一栈s1中的所有元素读出，然后进入到第二个栈s2中。算法描述如下： void enqueue(stack s1,int x) { if(s1->top= =n)
printf(“队列上溢”)；
else
push(s1,x)
}
void dequeue(stack s1,stack s2,int x) { s2->top= =0; while (!empty(s1))
push(s2,pop(s1));
pop(s2,x);
while(!empty(s2)); push(s1,pop(s2)); }
int queue_empty(stack s1) {if empty(s1) return (1); else
return (0);}
2、编写循环队列入队和出队的算法。 （1） 循环队列入队算法：
int encycqueue(cycqueuetp *sq,datatype x) {if(sq->rear+1)%maxsize= =sq->front} { printf(“队满”);
return (0);
} else
{ sq->rear=(sq->rear+1)%maxsize; sq->data[sq->rear]=x; return(0); }}
(2)环队列出队算法
int outcycqueue(cycqueuetp *sq,datatype *x) {if(sq->front= =sq->rear) { printf(“队空”) return (0); } else
{ sq->front=(sq->front+1)%maxsize; *x=sq->data[sq->front]; return (1);}}
27