A. 链式存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构
27、在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的操作是（ ）。
A. front=front->next B. rear= rear->next C. rear->next=front D. front->next=rear 28、队和栈的主要区别是（ ）。
A. 逻辑结构不同 B. 存储结构不同 C. 所包含的运算个数不同 D. 限定插入和删除的位置不同
二、填空题
1、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是 。 答案：3
2、一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为： 。 答案：(rear-front+M)%M
3、在具有n个元素的循环队列中，队满时具有 个元素。 答案：n-1
4、设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为 。 答案：61
5、已知循环队列的存储空间大小为20，且当前队列的头指针和尾指针的值分别为8和3，且该队列的当前的长度为_______。 三、判断题
1、栈和队列都是受限的线性结构。?
2、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结构。?
3、以链表作为栈的存储结构，出栈操作必须判别栈空的情况。?
四、程序分析填空题
1、已知栈的基本操作函数： int InitStack(SqStack *S); //构造空栈 int StackEmpty(SqStack *S);//判断栈空 int Push(SqStack *S,ElemType e);//入栈 int Pop(SqStack *S,ElemType *e);//出栈
函数conversion实现十进制数转换为八进制数，请将函数补充完整。
void conversion(){ InitStack(S); scanf(“%d”,&N); while(N){ （1） ; N=N/8;
}
while( （2） ){ Pop(S,&e); printf(“%d”,e); }
}//conversion 答案：（1）Push(S,N%8) （2）!StackEmpty(S) 2、写出算法的功能。
int function(SqQueue *Q,ElemType *e){ if(Q->front==Q->rear) return ERROR; *e=Q->base[Q->front];
11
Q->front=(Q->front+1)%MAXSIZE; return OK; }
3、阅读算法f2,并回答下列问题：
（1）设队列Q=（1，3，5，2，4，6）。写出执行算法f2后的队列Q; （2）简述算法f2的功能。
void f2(Queue *Q){ DataType e;
if (!QueueEmpty(Q)){ e=DeQueue(Q); f2(Q);
EnQueue(Q,e); } }
答案：（1）6,4,2,5,3,1 （2）将队列倒置
五、综合题
1、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列算法（用函数实现）。
答案：void EnQueue(Lnode *rear, ElemType e)
{ Lnode *new;
New=(Lnode *)malloc(sizeof(Lnode));
If(!new) return ERROR;
new->data=e; new->next=rear->next; rear->next=new; rear =new; }
2、已知Q是一个非空队列，S是一个空栈。编写算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q的所有元素逆置。 栈的ADT函数有：
void makeEmpty(SqStack s); 置空栈
void push(SqStack s,ElemType e); 元素e入栈 ElemType pop(SqStack s); 出栈，返回栈顶元素 int isEmpty(SqStack s); 判断栈空 队列的ADT函数有：
void enQueue(Queue q,ElemType e); 元素e入队 ElemType deQueue(Queue q); 出队，返回队头元素 int isEmpty(Queue q); 判断队空 答案：void QueueInvent(Queue q)
{ ElemType x;
makeEmpty(SqStack s);
while(!isEmpty(Queue q))
{x=deQueue(Queue q);
push(SqStack s, ElemTypex);} while(!isEmpty(SqStack s))
{x=pop(SqStack s);
enQueue(Queue q, ElemType x);}
}
3、对于一个栈，给出输入项A,B,C,D，如果输入项序列为A,B,C,D，试给出全部可能的输出序列。
答案：出栈的可能序列：
ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA CBDA CBAD CDBA DCBA
12
rear
第四章 串
一、选择题
1、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（ C ）。
A. 连接 B. 求子串 C. 模式匹配 D. 判断子串
2、已知串S=?aaab?，则next数组值为（ A ）。
A. 0123 B. 1123 C. 1231 D. 1211 3、串与普通的线性表相比较，它的特殊性体现在（ C ）。
A. 顺序的存储结构 B. 链式存储结构 C. 数据元素是一个字符 D. 数据元素任意 4、设串长为n，模式串长为m，则KMP算法所需的附加空间为（ A ）。 A. O(m) B. O(n) C. O(m*n) D. O(nlog2m) 5、空串和空格串（ B ）。
A. 相同 B. 不相同 C. 可能相同 D. 无法确定 6、与线性表相比，串的插入和删除操作的特点是（ ）。 A. 通常以串整体作为操作对象 B. 需要更多的辅助空间 C. 算法的时间复杂度较高 D. 涉及移动的元素更多 7、设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=’Beijing&Nanjing’，SUBSTR(S,4,5)=（ B ）。
A. ?ijing? B. ?jing&? C. ?ingNa? D. ?ing&N? 二、判断题
（ ）1、造成简单模式匹配算法BF算法执行效率低的原因是有回溯存在。 （√ ）2、KMP算法的最大特点是指示主串的指针不需要回溯。 （√ ）3、完全二叉树某结点有右子树，则必然有左子树。 三、填空题
1、求子串在主串中首次出现的位置的运算称为 模式匹配 。 2、设s=?I︺AM︺A︺TEACHER?,其长度是____。
3、两个串相等的充分必要条件是两个串的长度相等且 对应位置字符相同 。 四、程序填空题
1、函数kmp实现串的模式匹配，请在空格处将算法补充完整。
int kmp(sqstring *s,sqstring *t,int start,int next[]){ int i=start-1,j=0; while(i
2、函数实现串的模式匹配算法，请在空格处将算法补充完整。 int index_bf(sqstring*s,sqstring *t,int start){ int i=start-1,j=0;
while(i
if(s->data[i]==t->data[j]){ i++;j++; }else{
i= i-j+1 ;j=0; }
if(j>=t->len)
return i-t->len+1 ;
13
else
return -1; }}/*listDelete*/ 3、写出下面算法的功能。
int function(SqString *s1,SqString *s2){ int i; for(i=0;i
答案：.串比较算法 4、写出算法的功能。
int fun(sqstring *s,sqstring *t,int start){ int i=start-1,j=0;
while(i
if(s->data[i]==t->data[j]){ i++;j++; }else{
i=i-j+1;j=0; }
if(j>=t->len)
return i-t->len+1; else
return -1; }
答案：串的模式匹配算法
第五章 数组和广义表
一、选择题
1、设广义表L=((a，b，c))，则L的长度和深度分别为（ C ）。
A. 1和1 B. 1和3 C. 1和2 D. 2和3
2、广义表((a),a)的表尾是（ B ）。
A. a B. (a) C. () D. ((a)) 3、稀疏矩阵的常见压缩存储方法有（ C ）两种。
A. 二维数组和三维数组 B. 三元组和散列表 C. 三元组和十字链表 D. 散列表和十字链表 4、一个非空广义表的表头（ D ）。
A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是子表或原子
5、数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是（ A ）。
A. 1175 B. 1180 C. 1205 D. 1210
6、广义表G=(a,b(c,d,(e,f)),g)的长度是（ A ）。
A. 3 B. 4 C. 7 D. 8
7、采用稀疏矩阵的三元组表形式进行压缩存储，若要完成对三元组表进行转置，只要将行和列对换，这种说法（ B ）。
A. 正确 B. 错误 C. 无法确定 D. 以上均不对
8、广义表(a,b,c)的表尾是（ B ）。
A. b,c B. (b,c) C. c D. (c) 9、常对数组进行两种基本操作是（ C ）。
A. 建立和删除 B. 索引和修改 C. 查找和修改
14
D. 查找与索引
10、对一些特殊矩阵采用压缩存储的目的主要是为了（ D ）。
A. 表达变得简单 B. 对矩阵元素的存取变得简单 C. 去掉矩阵中的多余元素 D. 减少不必要的存储空间的开销
11、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ ）。
A. 13 B. 33 C. 18 D. 40
12、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i>=j)，在一维数组B的下标位置k的值是（ B ）。
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 13、广义表A=((a),a)的表头是（ B ）。
A. a B. (a) C. b D. ((a)) 14、稀疏矩阵一般的压缩存储方法有两种，即（ C ）。
A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表
15、假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ B ）。
?0?8060??0?8060?????7000070003????A. ? B. ? ?00000?50400???????50400??00000??????0?8060??0?8060?????0003?0000??0?7C. ? D. ??50403? 70000???????50400??0?0000????16、以下有关广义表的表述中，正确的是（ A ）。
A. 由0个或多个原子或子表构成的有限序列 B. 至少有一个元素是子表
C. 不能递归定义 D. 不能为空表
17、对广义表L=((a,b),((c,d),(e,f)))执行head(tail(head(tail(L))))操作的结果是（ ）。
A. 的 B. e C. (e) D. （e,f） 二、判断题
（ ）1、广义表中原子个数即为广义表的长度。
（ ）2、一个稀疏矩阵采用三元组表示，若把三元组中有关行下标与列下标的值互换，并把mu和nu的值进行互换，则完成了矩阵转置。
（√ ）3、稀疏矩阵压缩存储后，必会失去随机存取功能。 （ ）4、广义表的长度是指广义表中括号嵌套的层数。
（√ ）5、广义表是一种多层次的数据结构，其元素可以是单原子也可以是子表。 三、填空题
1、已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是___ Loc(A[0][0])+(i*N+j)*k ____。
2、广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是： (x,y,z) 。 3、二维数组，可以按照 两种不同的存储方式。 4、稀疏矩阵的压缩存储方式有： 和 。 四、综合题
1、现有一个稀疏矩阵，请给出它的三元组表。
15
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构试题库集及答案(3)在线全文阅读。
相关推荐：