数据结构试题集(包含答案 - 完整版) 下载本文

return ERROR;

*e=Q->base[Q->front];

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、假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针,请写出相应的入队列算法(用函数实现)。

rear

答案: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,试给出全部可能的输出序列。 4,1,4,1,2,1,1 答案:出栈的可能序列:

ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA BDCA CBDA CBAD CDBA DCBA

第四章 串

一、选择题

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、与线性表相比,串的插入和删除操作的特点是( B )。

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’,其长度是__14__。

3、两个串相等的充分必要条件是两个串的长度相等且 对应位置字符相同 。 四、程序填空题

1、函数kmp实现串的模式匹配,请在空格处将算法补充完整。

int kmp(sqstring *s,sqstring *t,int start,int next[]){ int i=start-1,j=0;

while(ilen&&jlen)

if(j==-1||s->data[i]==t->data[j]){ i++;j++; }

else j= next[j] ; if(j>=t->len)

return( i=t->len+1 ); else

return(-1); }

2、函数实现串的模式匹配算法,请在空格处将算法补充完整。 int index_bf(sqstring*s,sqstring *t,int start){ int i=start-1,j=0;

while(ilen&&jlen)

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; }}/*listDelete*/

3、写出下面算法的功能。

int function(SqString *s1,SqString *s2){ int i;

for(i=0;ilength&&ilength;i++) if(s->data[i]!=s2->data[i])

return s1->data[i]-s2->data[i]; return s1->length-s2->length; }

答案:.串比较算法 4、写出算法的功能。

int fun(sqstring *s,sqstring *t,int start){ int i=start-1,j=0;

while(ilen&&jlen)

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. 查找和修改 D. 查找与索引

10、对一些特殊矩阵采用压缩存储的目的主要是为了( D )。

A. 表达变得简单 B. 对矩阵元素的存取变得简单 C. 去掉矩阵中的多余元素 D. 减少不必要的存储空间的开销

11、设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一个元素,其存储地址为1,每元素占1个地址空间,则a85的地址为( B )。

A. 13 B. 33 C. 18 D. 40

12、设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i>=j),在一维数组B的下标位置