数据结构习题集(含答案)(6)

{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

3、已知Fibonacci数列的递归定义如下： 0??fib(n)??1?fib(n?1)?fib(n?2)?试写出求解fib(n)的递归算法。

n?0n?1n?1Int fibonacci(int n) { if(n= =0||n= =1)

fib=n;

else

fib=fibonacci(n-1)+fibonacci(n-2); return(fib); }

习

一、选择题：

题四

1、串是一种特殊的线性表，其特殊性体现在_____。 A、可以顺序存储 B、数据元素是一个字符

C、可以链接存储 D、数据元素可以是多个字符

2、设有两个串p 和q，求p 在q中首次出现的位置的运算称作 。 A、连接 B、求子串 C、模式匹配 D、求串长

3、串是任意有限个

A、符号构成的集合 B、符号构成的序列 C、字符构成的集合 D、字符构成的序列

4、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如图所示）按行序存放在一维数组B[1..n(n-1)/2]中，对下三角部分中任一个元素aij(ij)在一维数组B的下标位置k值是_____。

A、I(I-1)/2+j-1 B、I(I-1)/2+j C、I(I+1)/2+j-1 D、I(I+1)/2+j ?a11?a21a22?A???????an1an2?二、填空题：

?????ann?1、两个字符串相等的充分必要条件是_____。

2、字符在串中的位置，即是字符在该序列中的_____。

3、设有串S1=’I an a student’,S2=’st’,其index(S1,S2)= _____。 4、串是指_____。

5、含零个字符的串称为_____串，用_____表示；其他串称为_____串。任何串中所含_____的_____个数称为该串的长度。

6、一个串中任意个连续字符组成的子序列称为该串的_____串，该串称为它的所有子串的_____串。

7、广义表（a,(a,b),d,e,((I,j),k)）的长度是_____，深度是_____。 8、设数组a[50][80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45][68]的存储地址为_____；若以列序为主序存储，则元素a[45][68]的存储地址为

28

_____。

9、三维数组a[4][5][6]（下标从0开始计，a有4×5×6个元素），每个元素的长度是2，则a[2][3][4]的地址是_____。（设a[0][0][0]的地址是1000，数据以行为主序方式存储） 参考答案：

一、 选择题

1、B 2、C 3、D 4、B 二、 填空题：

1、长度相同且对应位置上的字符相同 2、序号 3 、8 4、含n个字符的有限序列且n≥0 5、空 ф 非空 字符 6、子 主 7、5 3 8、9174 8788 9、1164 三、

算法设计： Void reverse(char a[]) { char ch; int I; I=1;

do

{ scanf(“%c”,ch);

reverse(a);

a[I]=ch; I++;

}while(ch!=’#’&&I

2、试设计一算法测试一个串T的值是否为回文（即从左向右读出的内容与从右向左读出的内容一样）。 Int invert(char t[ ]) {int I,j;

j=length(t)/2; for(I=0;I

if(substr(t,I,1)!=substr(t,leng(t)-I+1,1) return (0); else return(1); }

1、 一个递归算法来实现字符串逆序存储，要求不另设串存储空间。

习

一、选择题

题五

1、一棵有n个结点的二叉树，按层次从上到下，同一层从左到右的顺序存储在一维数组A[n]中，则二叉树中第I个结点（I从1开始用上述方法编号）的右孩子在数组A中的位置是_____。 A、A[2I] (2I≤n) B、A[2I+1] (2I+1≤n) C、A[i/2] D、条件不充分，无法确定

2、将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是_____。 A、4 B、5 C、6 D、7 3、下列有关二叉树的说法正确的是_____。

29

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题集(含答案)(6)在线全文阅读。