《数据结构》吕云翔编著第三章答案

第六章图习题解答 一、选择题

1.某无向图的邻接矩阵A= ，可以看出该图共有（）个顶点

A.3 B.6 C.9 D.以上答案均不正确 【解答】A

2．无向图的邻接矩阵是一个（ ），有向图的邻接矩阵是一个（ ） A 上三角矩阵 B 下三角矩阵 C 对称矩阵 D 无规律 【解答】C，D

3．下列命题正确的是（ ）。

A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一 D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一 【解答】B

4. 在一个具有n 个顶点的有向完全图中包含有（ ）条边： A n(n-1)/2 B n(n-1) C n(n+1)/2 D n2 【解答】B

5．一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（ ）棵树。 A k B n C n - k D 1 【解答】C

6．用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（ ）。

A 逆拓扑有序 B 拓扑有序 C 无序 D 深度优先遍历序列 【解答】A

7. 关键路

数据结构第二章习题解答

一、单选题

1．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移 （B） 个元素。 A、n-i B、n-i+1 C、n-i-1 D、i

2．在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移 （A）个元素。

A、n-i B、n-i+1 C、n-i-1 D、i

3. 在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时 的平均查找长度（即需要比较的元素个数）为( C )。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2

4．在一个长度为 n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次 数为(C )。 A. (n+1)/2

B. n/2 C. n

D. n+1

5. 在一个顺序表的表尾插入一个元素的时间复杂度为(B )。 A. O(n) B. O(1) C. O(n*n) D. O(log2n)

6.若一个结

判断回文palindrome: #include #include using namespace std; bool huiwen(string s) {

int n=s.length(); int i,j; i= 0; j=n-1;

while(i=j) return true;else return false; }

int main() {

string s1; cin>>s1;

cout<

=============

（2）设从键盘输入一整数的序列：a1, a2, a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。 #include using namespace std; #define OVERFLOW -2 #define OK 1 #define ERROR 0

typedef int SElemType; typedef int Status; typedef struct { SElemType a[5]; int top; } SqStack

专业资料整理分享

第三章习题

1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴ 如进站的车厢序列为123，则可能得到的出站车厢序列是什么？

⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。

2. 设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下

列4步操作：

（1） 输出队首元素；

（2） 把队首元素值插入到队尾； （3） 删除队首元素； （4） 再次删除队首元素。

直到队列成为空队列为止，得到输出序列： （1）

A、C、E、C、C （2） A、C、E

（3） A、C、E、C、C、C （4） A、C、E、C

3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？ 4.

数据结构练习第三章 栈和队列

一、选择题

1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点

2．向顺序栈中压入新元素时，应当（ ）。

A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。

A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ).

A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（ ）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别

6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的

队尾指

习题三 栈和队列

一 单项选择题

1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2

2．若已知一个栈的进栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。

A 可能是2 B 一定是2 C 可能是1 D 一定是1

3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）

A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则

习题三 栈和队列

一 单项选择题

1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2

2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。

A 可能是2 B 一定是2 C 可能是1 D 一定是1

3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）

A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则

第三章作业

1、写出下列程序段的输出结果。 viod main ( ) { Stack S;

char x, y; InitStack (S); x=’c’; y=’k’;

Push(S, x); Push(S, ’a’); Push(S, y); Pop(S, x); Push(S, ’t’); Push(S, x); Pop(S, x); Push(S, ’s’); while ( ! StackEmpty(S) ) { Pop(S, y); printf (y); } printf(x);

}

stac k

2、简述下列算法的功能（栈的元素类型SElemType为int）。 （1）Ststus algo1(Stack S) { int I, n, A[255]; n=0;

while ( ! StackEmpty(S) ) { n++; Pop(S, A[n]); }

for ( i=1; i<=n; i++ ) Push(S, A[n]); }

将栈S中的元素以出栈的顺序排在数组中，且出栈的先后和数组的序号从小到大一致。栈S变成空栈。

， 《数据结构》第三章习题参考答案

一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）

1、栈和队列都是线性表，只是在插入和删除时受到了一些限制。( √ ) 2、循环队列也存在空间溢出问题。( √ )

3、任何一个递归过程都可以转换成非递归过程。( √ ) 4、消除递归不一定需要使用栈。( √ )

5、有n个数顺序（依次）进栈，出栈序列有Cn种，Cn=(1/（n+1）)*（2n）!/((n!)*(n!))。（ √ ）

6、循环队列方式能很好地解决队列的假溢出现象。（ √ ）

二、单项选择题

1、1．设有一个顺序栈S，元素P1，P2，P3，P4，P5，P6依次进栈，得到的出栈顺序P2，

P3，P4，P6，P5，P1，则顺序栈的容量至少为（ B ）。 A．2 B．3 C．4

D．无法确定

2．一个队列的输出序列是1，2，3，4，则队列的入队序列是（ A ）。

A．1，2，3，4 B．1，4，3，2 C．4，3，2，1 D．不确定

3、对于一个循环队列（最大元素个数为maxSize）进行入队操作时，对队列指针的修改

正确的语句是（ C

），且 top 是指向栈顶的指针。若想摘除链式栈的栈顶结点，并 x 中，则应执行操作（ ; top = top->link ; 11. 设循环队列的结构是

#define MaxSize 100 typedef int ElemType; typedef struct {

1. 2. 3. 4. 5. 6. 7. 8. 9. 第三章 栈和队列 试

题

、单项选择题

栈的插入和删除操作在（ ）进行。

A. 栈顶

B. 栈底 当利用大小为 n 的数组顺序存储一个栈时， 先应执行（ A. top++ ; ）语句修改 top 指针。 B.

top -- ; C. 任意位置 假定用 top ==n 表示栈空， C. top = 0 ; D. 指定位置 则向这个栈插入一个元素时， 首 D. top ; 若让元素 1,2,3 A. 3, 2, 1

依次进栈，则出栈次序不可能出现（ B. 2, 1, 3 C. 3, 1, 2 在一个顺序存储的循环队列中，队头指针指向队头元素的（ A. 前一个 B. 后一个 当利用大小为 n 的数组顺序存储一个队列时， A. n-2 B. n-1 从一个顺序存储的循环队列中删除一个元素时， A. 队头指针加一 C. 取出队头指