数据结构全部习题整理 答案 1800Word文档下载推荐.docx
《数据结构全部习题整理 答案 1800Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构全部习题整理 答案 1800Word文档下载推荐.docx（62页珍藏版）》请在冰点文库上搜索。
n0.5<
n3/2<
nlgn<
（3/2）n<
2n<
n!
<
nn
8、 常用的存储表示方法有哪几种?
常用的存储表示方法：
顺序存储方法、链接存储方法、索引存储方法、散列存储方法。
9、 设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要（ 15 ）。
收藏分享评分
自考，其实我一直在努力！
河南自考论坛：
请大家使用论坛上方的搜索功能，方便查找自己想要的论坛资料。
二、线性表
1、 以下关于线性表的说法不正确的是（ C）。
A、线性表中的数据元素可以是数字、字符、记录等不同类型。
B、线性表中包含的数据元素个数不是任意的。
C、线性表中的每个结点都有且只有一个直接前趋和直接后继。
D、存在这样的线性表：
表中各结点都没有直接前趋和直接后继。
2、 线性表是一种典型的（ 线性 ）结构。
3、 线性表的逻辑结构特征是什么?
对于非空的线性表:
①有且仅有一个开始结点A1，没有直接前趋，有且仅有一个直接后继A2；
②有且仅有一个终结结点AN，没有直接后继，有且仅有一个直接前趋AN-1；
③其余的内部结点AI（2≤I≤N-1）都有且仅有一个直接前趋AI-1和一个AI+1。
4、 线性表的顺序存储结构是一种（ 随机存取 ）的存储结构。
5、 在顺序表中，只要知道（ 基地址和结点大小 ），就可在相同时间内求出任一结点的存储地址。
6、 在等概率情况下，顺序表的插入操作要移动（ 一半 ）结点。
7、 在一个长度为n的顺序表中删除第i个元素，要移动（ n-i ）个元素
8、 如果要在第i个元素前插入一个元素，要后移（ n-i+1）个元素。
9、 采用（ 顺序 ）存储结构的线性表叫顺序表。
10、顺序表中逻辑上相邻的元素的物理位置（ 相邻）。
11、 在（ C）运算中，使用顺序表比链表好。
A、插入 B、删除 C、根据序号查找 D、根据元素值查找
12、 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ O（n））。
13、 在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在（ 前趋）结点的next域中。
14、 在（ 循环 ）链表中，从任何一结点出发都能访问到表中的所有结点。
15、 （ 双向）链表适合从指点结点开始，寻找直接前趋的运算。
16、 顺序表相对于链表的优点有节省存储和随机存取。
17、 在链表的开始结点前设置头结点的优点是什么？
头结点是在链表的开始结点之前附加一个结点。
它具有两个优点:
（1）、由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;
（2）、无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。
18、 （ 双向链表）适合作为经常在首尾两端操作线性表的存储结构。
19、 如果线性表的存储空间变化较大，则适合用（ 链 ）表。
20、 当线性表的数据变化不大，主要用于查询时，用（ 顺序 ）表比较好。
21、 在链表中，每个结点中含8个字符，1个指针域。
其中每个字符占1个字节，每个指针占4个字节。
则该结点的存储密度是（ 2/3 ）。
（1+1+4）/（8+1）=2/3 存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）
22、 链表相对于顺序表的优点有插入和删除操作方便。
23、 在n个结点的顺序表中插入一个结点需平均移动n/2个结点，具体任务的移动次数取决于表长n和插入位置i。
24、 在n个结点的顺序表中删除一个结点需平均移动（n－1）/2个结点，具体任务的移动次数取决于表长n和删除位置i。
25、 尾指针是指向终端结点的指针查找时间都是O
（1），用头指针来表示该链表，则查找终端结点的时间为O（n）。
补充：
1、顺序表上实现的基本运算：
表的初始化、求表长、取表中第i个结点三种运算的时间复杂度都为O
（1）。
2、 顺序表插入操作算法分析
①问题的规模
表的长度L-＞length（设值为n）是问题的规模。
②移动结点的次数由表长n和插入位置i决定
算法的时间主要花费在for循环中的结点后移语句上。
该语句的执行次数是n-i+1。
当i=n+1：
移动结点次数为0，即算法在最好时间复杂度是0
（1）
当i=1：
移动结点次数为n，即算法在最坏情况下时间复杂度是0（n）
③移动结点的平均次数Eis（n）
其中：
在表中第i个位置插入一个结点的移动次数为n-i+1
pi表示在表中第i个位置上插入一个结点的概率。
不失一般性，假设在表中任何合法位置（1≤i≤n+1）上的插入结点的机会是均等的，则p1=p2=…=pn+1=1/（n+1） 因此，在等概率插入的情况下，
即在顺序表上进行插入运算，平均要移动一半结点。
3、 顺序表删除操作算法分析
①结点的移动次数由表长n和位置i决定：
i=n时，结点的移动次数为0，即为0
（1）
i=1时，结点的移动次数为n-1，算法时间复杂度分别是0（n）
②移动结点的平均次数EDE（n）
其中：
删除表中第i个位置结点的移动次数为n-i
pi表示删除表中第i个位置上结点的概率。
不失一般性，假设在表中任何合法位置（1≤i≤n）上的删除结点的机会是均等的，则p1=p2=…=pn=1/n 因此，在等概率插入的情况下，
顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0（n）。
4、 单链表的运算：
头插法建表、尾插法建表、尾插法建带头结点的单链表三个算法的时间复杂度均为0（n）。
5、 单链表的查找运算：
按序号查找、按值查找其平均时间复杂度为O（n）。
6、 单链表的插入运算：
算法的时间主要耗费在查找操作GetNode上，故时间复杂度亦为O（n）。
7、 单链表的删除运算：
算法的时间复杂度也是O（n）。
8、 循环链表：
若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是O（n）。
若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O
（1）。
9、 双向链表的前插和删除本结点操作：
两个算法的时间复杂度均为O
（1）。
10、 结点ai的存储地址
不失一般性，设线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。
假设表中每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a1的存储地址（简称为基地址）是LOC（a1），那么结点ai的存储地址LOC（ai）可通过下式计算：
LOC（ai）=LOC（a1）+（i-1）*c1≤i≤n
顺序表
链表
基于空间考虑分配方式
静态分配。
程序执行之前必须明确规定存储规模。
若线性表长度n变化较大，则存储规模难于预先确定估计过大将造成空间浪费，估计太小又将使空间溢出机会增多。
动态分配只要内存空间尚有空闲，就不会产生溢出。
因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。
存储密 度
为1。
当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。
<
1
基于时间考虑存取方法
随机存取结构，对表中任一结点都可在O
（1）时间内直接取得线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜。
顺序存取结构，链表中的结点，需从头指针起顺着链扫描才能取得。
插入删除
在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。
在链表中的任何位置上进行插入和删除，都只需要修改指针。
对于频删除，都只需要修改指针。
对于频删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜
三、栈和队列
1、 栈与一般的线性表的区别在于（ 运算是否受限制 ）。
2、 一个栈的入栈序列是abcde，则栈的不可能的输出序列是（ C ）。
A、Edcba B、decba C、dceab D、abcde
3、 在对栈的操作中，能改变栈的结构的是（ InitStack（S） ）。
4、 顺序栈的类型定义如下：
typedefmaxsize64;
typedefstruct{
intdata[maxsize];
inttop;
}seqstack;
seqstack*s;
顺序栈s栈满条件是（ s->
top==maxsize-1 ）。
5、 向一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈，执行（ S->
next=HS->
next;
HS=s;
）。
6、 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列是p1,p2,p3，…，pn，若p1=n，则pi=（ n-i+1）。
7、 在栈中，可进行插入和删除操作的一端称（ 栈顶）。
8、 在栈的出栈操作中，要先判断栈是否空，否则会产生（ 下溢）现象。
9、 当程序中同时使用（ 2 ）个栈时，让它们共享同一向量空间可减少上溢的发生。
10、 栈的特点是（ 后进先出）。
当问题满足（ 先进后出 ）原则时可使用队列作数据结构。
当问题满足（ 后进先出 ）原则时可使用栈作数据结构。
11、 由于链栈的操作只在链表头部进行，所以没有必要设置（ 头）结点。
12、 若内存空间充足，（ 链）栈可不定义栈满运算。
13、 一个队列的入列序列是1234，则队列的输出序列是（ 1234 ）。
14、 队列与一般的线性表的区别在于（ 运算是否受限制 ）。
15、 “假上溢”现象会出现在（ 顺序队列）中。
16、 在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是（ F=F->
）。
17、 假设以数组sequ[m]存放循环队列，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含的元素个数，则判别队满的条件是（ quelen==m ）。
18、 为了克服“假上溢”，一般可用（ 循环）向量存储队列中的元素。
19、 在顺序队列中，若队列非空，（ 队头）指针指向队头元素,队尾指针指向队尾元素的下一位置。
20、 循环队列采用的是（ 顺序 ）存储结构。
21、 设F和R是循环队列的队头指针和队尾指针，则判断队空的条件是（ F==R ）。
22、 在（ 队列中只有一个元素）情况下，链队列的出队操作需要修改尾指针。
23、 说出解决循环队列中，判断队空和队满情况的三种方法。
①另设一布尔变量以区别队列的空和满；
②少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：
REAR所指的单元始终为空）；
③使用一个计数器记录队列中元素的总数（实际上是队列长度）。
24、 设计一个判别表达式中左、右括号是否配对出现的算法，采用（ 线性表的顺序存储结构 ）数据结构最佳。
25、 在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（ 栈）数据结构。
26、 计算机在运行递归程序时，要用到（ 系统 ）提供的栈。
27、 什么是递归算法?
设计递归算法要分哪两个步骤？
所谓递归是指：
若在一个函数、过程或者数据结构定义的内部又直接（或间接）出现有定义本身的应用，则称它们是递归的，或者是递归定义的。
递归算法的设计步骤第一步骤（递归步骤）：
将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题，即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题；
第二步骤：
确定一个或多个无须分解、可直接求解的最小子问题（称为递归的终止条件）。
28、 在栈结构中，允许插入、删除的这一端为栈顶（ Top ），另一端称为栈底（ Bottom ）。
29、 在有n个元素的栈中，进栈和退栈操作的时间复杂度为O
（1）和O
（1）。
30、 在队列结构中，允许插入的一端称为队尾，允许删除的一端称为队头。
31、 设长度为n的链队列用单循环链表，若只设头指针，则入队和出队操作的时间复杂度分别为O（n）和O
（1）；
若只设尾指针，则入队和出队操作的时间复杂度分别为O
（1）和O
（1）。
32、 设循环向量有m个元素，循环向量中有一个循环队列。
在循环队列中，设头指针front指向队头元素，队尾指针指向队尾元素后的一个空闲元素。
（1）在循环队列中，队空标志为front==rear；
队满标志为front==（rear+1）%QueueSize。
（2）当rear>
=front时，队列长度为rear-front；
当rear<
front；
队列长度是rear+Queue-front；
33、 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：
（1）若入、出栈次序为Push
（1）,Pop（）,Push
（2）,Push（3）,Pop（）,Pop（）,Push（4）,Pop（）,则出栈的数字序列为何（这里Push（i）表示i进栈，Pop（）表示出栈）?
（2）能否得到出栈序列1423和1432?
并说明为什么不能得到或者如何得到。
（3）请分析1，2，3，4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。
（1）出栈序列为：
1324
（2）不能得到1423序列。
因为要得到14的出栈序列，则应做Push
（1）,Pop（）,Push
（2）,Push（3）,Push（4）,Pop（）。
这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。
能得到1432的出栈序列。
具体操作为：
Push
（1）,Pop（）,Push
（2）,Push（3）,Push（4）,Pop（）,Pop（）,Pop（）。
（3）在1，2，3，4的24种排列中，可通过相应入出栈操作得到的序列是：
1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321
不能得到的序列是：
1423,2413,3124,3142,3412,4123,4132,4213,4231,4312
34、 指出下述程序段的功能是什么?
（1）voidDemo1（SeqStack*S）{
inti;
arr[64];
n=0;
while（StackEmpty（S））arr[n++]=Pop（S）;
for（i=0,i<
n;
i++）Push（S,arr）;
}//Demo1
程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。
此栈中元素个数限制在64个以内。
（2）SeqStackS1,S2,tmp;
DataTypex;
...//假设栈tmp和S2已做过初始化
while（!
StackEmpty（&
S1））
{
x=Pop（&
S1）;
Push（&
tmp,x）;
}
tmp））
x=Pop（&
tmp）;
Push（&
S1,x）;
S2,x）;
答：
程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。
（3）voidDemo2（SeqStack*S,intm）
{//设DataType为int型
SeqStackT;
inti;
InitStack（&
T）;
while（!
StackEmpty（S））
if（（i=Pop（S））!
=m）Push（&
T,i）;
StackEmpty（&
T））
{
i=Pop（&
Push（S,i）;
}
程序段的功能是利用栈T，将一个非空栈S中值等于m的元素全部删去。
（4）voidDemo3（CirQueue*Q）
intx;
SeqStackS;
InitStack（&
S）;
QueueEmpty（Q））
{x=DeQueue（Q）;
Push（&
S,x）;
}
s））
{x=Pop（&
EnQueue（Q,x）;
}//Demo3
程序段的功能是将一个循环队列Q经过S栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。
（5）CirQueueQ1,Q2;
//设DataType为int型
intx,i,n=0;
...//设Q1已有内容，Q2已初始化过
QueueEmpty（&
Q1））
{x=DeQueue（&
Q1）;
EnQueue（&
Q2,x）;
n++;
for（i=0;
i<
i++）
{x=DeQueue（&
Q2）;
EnQueue（&
Q1,x）;
EnQueue（&
}
这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。
1、顺序栈的基本操作
前提条件：
设S是SeqStack类型的指针变量。
若栈底位置在向量的低端，即S-＞data[0]是栈底元素。
（1）进栈操作
进栈时，需要将S-＞top加1
注意：
①S-＞top==StackSize-1表示栈满
②"
上溢"
现象--当栈满时，再做进栈运算产生空间溢出的现象。
上溢是一种出错状态，应设法避免。
（2）退栈操作
退栈时，需将S-＞top减1
①S-＞top<
0表示空栈
②"
下溢"
现象——当栈空时，做退栈运算产生的溢出现象。
下溢是正常现象，常用作程序控制转移的条件。
2、 顺序队列中的溢出现象
①"
现象当队列为空时，做出队运算产生的溢出现象。
“下溢”是正常现象，常用作程序控制转移的条件。
②"
真上溢"
现象当队列满时，做进栈运算产生空间溢出的现象。
“真上溢”是一种出错状态，应设法避免。
③"
假上溢"
现象 由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。
当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。
该现象称为"
现象。
为充分利用向量空间，克服"
现象的方法是：
将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。
存储在其中的队列称为循环队列（CircularQueue）。
四、串
1、 串是一种特殊的线性表，其特殊性体现在（ 数据元素是一个字符）。
2、 有两个串P和Q，求P和Q中首此出现的位置的运算称（ 求子串）。
3、 设串s1='
ABCDEFG'
s2='
PQRST'
函数con（x,y）返回x和y串的连接串，subs（s,I,j）返回串s的从序号i的字符开始的j个字符组成的子串，len（s）返回串s的长度，则con（subs（s1,2,len（s2））,subs（s1,len（s2）,2）））的结果串是（ D ）。
A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF
4、 在空串和空格串中，长度不为0的是（ 空格串）。
5、 在串的模式匹配中，一般（ 有效位移的个数小于合法位移的个数）。
6、 在顺序串中，根据空间分配方式的不同，可分为（ 静态分配和动态分配）。
7、 按存储结构不同，串可分为（ 顺序串和链串）。
通常在程序中使用的串可分为：
串变量和串常量。
8、 在C语言中，以字符（ #CONTENT# ）表示串值的终结。
9、 在链串中，为了提高存储密度，应该增大（ 结点的大小）.
10、 假设每个字符占1个字节，若结点大小为4的链串的存储密度为50%，则其每个指针占（ 4 ）个字节。
11、 顺序串上的子串定位运算算法分析：
该算法最坏情况下的时间复杂度为O（（n-m+1）m）。
分析：
当目标串和模式串分别是"
an-1b"
和"
am-1b"
时，对所有n-m+1个合法的位移，均要比较m个字符才能确定该位移是否为有效位移，因此所需比较字符的总次数为（n-m+1）m。
12、 串（String）是零个或多个字符组成的有限序列。
一般记为S="
a1a2……an"
。
13、 长度为零的串称为空串（EmptyString），它不包含任何字符。
仅由一个或多个空格组成的串称为空白串（BlankString）。
14、 子串定位运算又称串的模式匹配或串匹配。
在串匹配中，一般将被匹配的主串称为目标（串），子串称为模式（串）。
15、 朴素的串匹配算法最坏情况下需比较字符的总次数为（n-m+1）m。
n为主串长，m为子串长。
16、 串匹配就是对于合法的位置（又称合法的位移）0≤i≤n-m，依次将目标串中
升级会员 