《数据结构》练习一答案

数据结构概论练习1
一、单选:
1.数据结构通常是研究数据的( A )及它们之间的相互关系.
A.存储和逻辑结构
B.存储和抽象
C.理想与抽象
D.理想与逻辑
2.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称为( C )
A.存储结构
B.逻辑结构
C.顺序存储结构
D.链式存储结构
3.非线性结构是数据元素之间是存在的一种( B )
A.一对多关系
B.多对多关系
C.多对一关系
D.一对一关系
4.非线性结构中,每个结点( D )
A.无直接前趋.
B.只有一个直接前驱和后继
C.只有一个直接前驱和个数不受限制的直接后继
D.有个数不受限制的直接前驱和后继.
5.除了考虑存储数据结构本身所占用的空间外,实现算法所用辅助空间的多少称为算法的:（B）
A.时间效率
B.空间效率
C.硬件效率
D.软件效率
二、填空
1、数据结构包括数据的逻辑结构,数据的存储结构,数据的运算,这三个方面的内容 .
2、数据结构按逻辑结构可分为两大类,分别是线性结构和非线性结构.
3、数据的存储结构可用四种基本的存储方法表示,分别是顺序、链式、索引和散列.
4、线性结构反映结点间的逻辑关系是一对一关系.非线性结构反映结点间的逻辑关系是多对多关系.
5、一个算法的效率可分为时间效率和空间效率.
分别写出下列两个算法的时间复杂度.
1、
x=0;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
x++;
答：O（n2）
2、
x=0;
for(i=1;i<n;i++)
for(j=1;j<=n-i;j++)
x++;
答：O（n2）
一、填空
1、在栈中存取数据的原则是：先进后出
2、在栈中，出栈操作的时间复杂度为：O(1)
3、栈与一般线性表的区别主要在于栈只允许在表尾进行插入和删除操作
4、顺序栈是空栈的条件是：s.top==0
5、插入和删除只能在一端进行的线性表，称为：受限线性表
6、设循环向量有m个元素，循环向量中有一个循环队列，在循环队列中设队头指针front指向队头元素，队尾无名指是针指向队尾元素后的一个空闲元素。

.在循环队列中，队空标志为front==rear队满标志为front==(rear+1)%m
.当rear>=front时，队列长度为rear-front；当rear<FRONT时，队列长度是rear+m-front。

7、在队列中存取数据应遵从的原则是：先进先出
8、在队列结构中，允许插入的一端称为队尾，允许删除的一端称为：队头
9、s1="abcd",s2="cd"，则s2在s1中的位置是3
10、不含任何字符的串称为空串，仅含有空格字符的串称为空白串。

1、设长度为n的链队列用单循环链表表示，若只设头指针，则入队，出队操作的时间是什么？如果只设尾指针呢？
答：若只设头指针，则出队时间为1，入队时间需要n。

因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。

若只设尾指针，则出入队时间均为1。

因为是循环链表，尾指针所指的下一个元素就是头指针所指的元素，所以出队时不需要遍历整个队列。

2、设T[0..n-1]="abaabaabcaabaa" P[0..m-1]="aab",当用模式串P匹配目标串T时，请给出所有的有效位移。

朴素匹配返回的位移是哪一个？
答：所有的有效位移i的值为：2，5，9。

朴素匹配的返回值是第一个有效位移，因此是2。

3、如果目标串一共有10个字符，模式串共有2个字符，问，当匹配不成功的时候，最多比较了多少个字符？举例说明。

答：串匹配算法最坏情况下需比较字符的总次数为（n-m+1）m。

n为主串长，m为子串长。

即（10-2+1）*2=18
4、如果目标串一共有10个字符，模式串共有2个字符，问，当匹配成功的时候，最多比较了多少个字符？举例说明。

答：串匹配算法最坏情况下需比较字符的总次数为（n-m+1）m。

n为主串长，m为子串长。

即（10-2+1）*2=18。