计130121第二次作业.doc

第二次作业 一、选择题 1、栈和队列的相同之处是 C 。 A.元素的进出满足先进后出 B.元素的进出满足后进先出 C.只允许在端点进行插入和删除操作 D.无共同点 2、设栈S 和队列Q 的初始状态为空,元素e1，e2，e3，e4，e5 和e6 依次通过栈，一个元素出栈后即进入队列Q,若6 个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S 的容量至少应该是 C 。 A. 6 B. 4 C. 3 D. 2 3、队列通常采用的两种存储结构是( A)。 A. 顺序存储结构和链式存储结构 B.散列方式和索引方式 C. 链表存储结构和线性存储结构 D.线性存储结构和非线性存储结构 4、循环队列SQ队满的条件是 A 。 A. SQ-rear==SQ-front B. (SQ-rear+1)%MAXLEN==SQ-front B. SQ-rear==0 D. SQ-front==0 5、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为 B 。 A. 5和1 B. 4和2 C. 2和4 D. 1和5 6、链栈与顺序栈相比，有一个较为明显的优点是 A 。 A. 通常不会出现满栈的情况 B. 通常不会出现栈空的情况 C. 插入操作更加方便 D. 删除操作更加方便 7、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为 B 。 A. 42 B. 16 C. 17 D. 41 8、串是一种特殊的线性表，其特殊性体现在 B 。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链式存储 D. 数据元素可以是多个字符 9、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为 C 。 A. O(m) B. O(n) C. O(m+n) D. O(m×n) 10、已知串S=“abab”，其Next数组值为 0012 。 A. 0123 B. 0121 C. 0112 D. 0122 11、若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存一个字符。假设每个字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为 D 。 A. 20% B. 40% C. 50% D. 33.3% 12、在双向链表中，在指针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; 13、已知循环队列存储在一维数组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 14、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作（称为输出受限的双端队列），若a, b, c, d, e元素依次进队，则不可能得到的顺序是 C 。 A. bacde B. dbace C. dbcae D. ecbad 15、在双向链表中间插入一个结点时，需要修改修改 D 个指针域。 A. 1 B. 2 C. 3 D. 4 16、在按行优先顺序存储的三元组表中，下述陈述错误的是 D 。 A. 同一行的非零元素，是按列号递增次序存储的 B. 同一列的非零元素，是按行号递增次序存储的 C. 三元组表中三元组行号是非递减的 D. 三元组表中三元组列号是非递减的 17、在稀疏矩阵的三元组表示法中，每个三元组表示 D 。 A. 矩阵中非零元素的值 B. 矩阵中数据元素的行号和列号 C. 矩阵中数据元素的行号、列号和值 D. 矩阵中非零数据元素的行号、列号和值 18