数据结构精品课程习题

main ( ) {

InitQueue (Q); x=’e’; y=’c’;

EnQueue (Q, ‘h’) ; EnQueue (Q, ‘r’) ; EnQueue (Q, ‘y’) ; OutQueue (Q, x ) ; EnQueue (Q, x ) ; OutQueue (Q, x ) ; EnQueue (Q, ‘a’) ; while (! EmptyStack ( Q ) ) {

OutQueue (Q, y) ; printf (y) ; } printf (x) ; }

13、简述下列算法的功能。ex13 (Q) InitQueue (S) ;

while (!EmptyStack (Q) ) {

OutQueue (Q, d) ; Push (S, d) ; }

while (! EmptyStack (S) ) {

Pop (S, d) ;

37

EnQueue (Q,d) ; }

14、已知下列数组a的起始地址是2000，求a[2][2][1]的起始地址。 int a[3][4][2]； loc[2，2，1]=?

15、设有一循环队列sq. data[maxsize]，一般情况下队列中至多可存放多少个元素？为什么？ 四、设计题

1、借助栈将输入任意一个非负的十进制整数，打印输出与其等值的八进制。 2、已知带表头结点循环链表存储链队的元素（如下所示），指针rear指向队列的尾元素，写出将元素X进队的算法。

EnQueue ( rear, X)

3、设字符串仅由圆括号“（”和“）”，方括号“[”和“]”，花括号“{”和“}”组成，利用链栈的操作编写一个检查括号是否正确配对的算法：int Matcher ( LstackTP * ls)。例如，[{{（）}[]}（）{[]}]是正确的，而{（{（）[]}）}]}是不正确的。设链栈定义如下： typedef struck node {char data; struct node * next; } LStackTp ;

4、Ss是结构体变量，其内包括指示栈顶位置的域Ss.top和数组Ss.data，用类C语言写出顺序栈基本运算的算法。 （1）获得一个空的顺序栈。 InitStack (Ss)

（2）将值X进顺序栈的算法。 Push (Ss, x)

（3）对顺序栈Ss进行出栈的算法，将出栈的值赋给变量X。 Pop (Ss, x)

（4）判断顺序栈Ss是否是空栈算法。 Emptys (Ss)

38

（5）将顺序栈Ss栈顶元素的值拷贝给变量X的算法。 GetTop (Ss,X)

（6）写出判断顺序栈Ss中元素个数的算法。 Length (Ss)

5、Sq 是结构体变量，其内包括循环队列头（Sq.front）、尾（Sq.rear）位置的信息，用类C语言写出循环队列基本运算的算法。 （1）获得一个空的循环队列Sq。 InitQueue (Sq)

（2）将值X放进循环队列的算法。 EnQueue (Sq, x)

（3）对循环队列Sq进行出队的算法，将出队的值赋给变量X。 OutQueue (Sq,x )

（4）判断循环队列Sq是否是空队的算法。 EmptyQueue (Sq)

（5）将循环队列Sq头元素的值拷贝给变量X的算法。 GetHead (Sq, X)

（6）写出判断循环队列Sq中元素个数的算法。 Length (Sq)

6、使用类C语言编写一个算法，使用栈对输入的符号序列中的中括号“[”与“]”是否配对进行判断，如果不配对，判断哪个括号多，输入“#”表示序列输入结束。

7、使用类C语言编写一个算法，判断用向前链表表示的链栈Ls中包括栈元素个数的算法。 StackLength(Ls)

8、使用类C语言编写一个算法，判断用向前链表表示的链队Lq中包括栈元素个数的算法。

QueueLength(Lq)

9、已知整型一维数组a，使用类C语言编写一个算法，每输入一个数组元素的下标，便输出相应数组元素的值，输入-1时结束。

39

10、已知整型一维数组a，使用类C语言编写一个算法，每输入一个数组元素的下标和数值，则将值赋给相应的数组元素，输入-1时结束。

一、单项选择题

1、在如下所示的各无向图中：

（1）找到所有简单环（ ）。（2）连通图有（ ）。

第七章40

图