第二次作业
一、选择题
1、设有编号为1, 2, 3, 4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序为 D 。
A. 1234 B. 1243 C. 1324 D. 1423
2、4个元素按A, B, C, D顺序进入S栈，执行两次Pop(S, x)运算后，栈顶元素的值是 B 。
A. A B. B C. C D. D
3、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列
A 命令。
A. x=top; top=top->next; B. top=top->next; x=top->data;
C. x=top->data; D. x=top->data; top=top->next;
4、向顺序栈中输入元素时 A 。
A. 先存入元素，后移动栈顶指针 B. 先移动栈顶指针，后存入元素
C. 谁先谁后无关紧要 D. 同时进行
5、设有一个顺序栈，元素A, B, C, D, E, F依次进栈，如果6个元素出栈的顺序是B, D, C, F, E, A，则栈的容量至少为 A 。
A. 3 B. 4 C. 5 6. 6
6、设已将元素A, B, C依次入栈，元素D正等待进栈。那么下列4个序列中不可能出现的出栈顺序为 A 。
A. CADB B. CBDA C. CDBA D. DCBA
7、栈和队列的相同之处是 C 。
A.元素的进出满足先进后出 B.元素的进出满足后进先出
C.只允许在端点进行插入和删除操作 D.无共同点
8、设栈S 和队列Q 的初始状态为空,元素e1，e2，e3，e4，e5 和e6 依次通过栈，一个元素出栈后即进入队列Q,若6 个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S 的容量至少应该是 B 。
A. 6 B. 4 C. 3 D. 2
9、队列通常采用的两种存储结构是( A)。
A. 顺序存储结构和链式存储结构 B.散列方式和索引方式
C. 链表存储结构和线性存储结构 D.线性存储结构和非线性存储结构
10、循环队列SQ队满的条件是 B 。
A. SQ->rear==SQ->front B. (SQ->rear+1)%MAXLEN==SQ->front
B. SQ->rear==0 D. SQ->front==0
11、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为 B 。
A. 5和1 B. 4和2 C. 2和4 D. 1和5
12、链栈与顺序栈相比，有一个较为明显的优点是 A 。
A. 通常不会出现满栈的情况 B. 通常不会出现栈空的情况
C. 插入操作更加方便 D. 删除操作更加方便
13、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为 C 。
A. 42 B. 16 C. 17 D. 41
14、串是一种特殊的线性表，其特殊性体现在 B 。
A. 可以顺序存储 B. 数据元素是一个字符
C. 可以链式存储 D. 数据元素可以是多个字符
15、设主串的长度为n 模式串的长度为m 则串匹配的KMP算法的时间复杂度为 C 。
A. O(m) B. O(n) C. O(m+n) D. O(m×n)
16、已知串S=“abab”，其Next数组值为 A 。
A. 0123 B. 0121 C. 0112 D. 0122
17、若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存一个字符。假设每个字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为 C 。
A. 20% B. 40% C. 50% D. 33.3%
18、在双向链表中，在指针p所指的结点前插入一个指针q所指向的结点，操作是 C 。
A. p->Prior=q; q->Next=p; p->Prior->next=q; q->Prior=q;
B. p->Prior=q; p->Prior->next=q; q->next=p; q->Prior=p->Prior;
C. q->Next=p; q->Prior=p->Prior; p->Prior->Next=q; p->Prior=q;
D. q->Prior=p->Prior; q->Next=q;p->Prior=q; p->Next=q;
19、已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是 B 。
A. 0, 0 B. 0, n-1 C. n-1, 0 D. n-1, n-1
20、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作（称为输出受限的双端队列），若a, b, c, d, e元素依次进队，则不可能得到的顺序是 C 。
A. bacde(可以的) B. dbace C. dbcae D. ecbad
21、在双向链表中间插入一个结点时，需要修改 D 个指针域。
A. 1 B. 2 C. 3 D. 4
二、填空题
1、在栈中，可进行插入和删除操作的一端称 栈顶 。
2、在进栈运算时，应先判别栈是否 为满 。在出栈运算时应先判别栈是否 为空 。当栈中元素为n个时，进栈运算时发生上溢，则说明该栈的最大容量为 n 。
3、设有一空栈，现有输入序列为1, 2, 3, 4, 5，经过push, push, pop, push, pop, push, push, pop, pop之后，输出序列为 2354 。
4、对于循环向量的循环队列，求队列长度的公式为 （rear-front+n）%n 。
5、栈的逻辑特点是 先进后出 。队列的逻辑特点是 先进先出 。两者的共同特点是只允许在它们的端口出插入和删除数据元素，区别是栈只能在一端，队列可以在两端。
6、链队列LQ为空时，LQ->front->next= rear .
7、在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为 front+1=rear 。
8、设串S=“Ilikecomputer”，T=“com”，则Length(S)= 13 。Index(S, T)= 6 。
9、在KMP算法中，next[j]只与 子 串有关，而与 主串 无关。
10、字符串“ababaab“的Next数组值是 0112342 。
三、试编写一个整数进制转换的通用函数convert(int num, STACK S, int n)，要求将整数m转换为n进制数，n进制数的各位依次存放在栈S中。并在主函数中进行测试。
要求：1、定义栈以及栈的型。
2、定义栈的各种操作。
3、实现函数convert。
4、在main函数中，通过调用函数convert将num的n进制数存放到一个栈中，并通过出栈的方法输出该n进制数
#include<iostream>
using namespace std;
#define maxlength 100
typedef int Elementtype;
struct STACK {
int top;
Elementtype elements[maxlength];
};
void MakeNull( STACK &S )
{
S.top = 0 ;
}
bool Empty( STACK S )
{
if ( S.top < 1 ) return true;
else return false;
}
void error( string s )
{
cout << s << endl;
system("pause");
}
Elementtype Top( STACK S )
{
if( Empty( S ) ){
error ( "栈为空" ) ;
return -1;
}
else return ( S.elements[ S.top ] );
}
void Pop( STACK &S )
{
if ( Empty (S ) ) error ( "栈为空" ) ;
else S.top = S.top-1 ;
}
void Push( Elementtype x, STACK &S )
{
if ( S.top == maxlength - 1 ) error ( "栈已满" ) ;
else {
S.top = S.top + 1 ;
S.elements[ S.top ] = x ;
}
}
void convert( int m, STACK &S, int n )
{
while ( m != 0 )
{
Push(m % n, S);
m = m/n;
}
}
void print( STACK S )
{
for ( int i = S.top; i>0; i-- ) cout << S.elements[i];
cout << endl;
}
int main()
{
cout << "请输入整数m：";
字符串长度17模式串长度 int m; cin >> m;
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论