算法与数据结构考研试题精析(第二版)第4章串答案
第四章串
任意串是其自身的子串。若字符串长度为n（n>0），长为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，……，长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8*（8+1）/2+1=37。故选B。但某些教科书上认为“空串是任意串的子串”无意义，所以认为选C。为避免考试中的二意性，编者认为第9题出得好。
二、判断题
三．填空题
1．(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数 2．字符
3．任意个连续的字符组成的子序列 4．5 5.O(m+n) 6．01122312 7．01010421 8．(1)模式匹配 (2)模式串
9．(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等
10．两串的长度相等且两串中对应位置的字符也相等。
11．’xyxyxywwy’ 12．*s++=*t++ 或（*s++=*t++）!=‘\0’
13．（1）char s[ ] (2) j++ (3) i >= j
14．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。串s用i指针（1<=i<=s.len）。t串用j指针（1<=j<=t.len）。算法思想是对每个i（1<=i<=s.len，即程序中第一个WHILE循环），来求从i开始的连续字符串与从j（1<=j<=t.len，即程序中第二个ＷHILE循环）开始的连续字符串的最大匹配。程序中第三个（即最层）的WHILE循环，是当s中某字符（s［i］）与t中某字符（t［j］）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。
程序（a）：（1）（i+k<=s.len）AND(j+k<=t.len) AND(s[i+k]=t[j+k])
//如果在s和t的长度，对应字符相等，则指针k 后移（加1）。
（2）con:=false //s和t对应字符不等时置标记退出
（3）j:=j+k //在t串中，从第j+k字符再与s[i]比较
（4）j:=j+1 //t串取下一字符
（5）i：=i+1 //s串指针i后移（加1）。
程序（b）：(1) i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k] //所有注释同上（a） (2) con=0 (3) j+=k (4) j++ (5) i++
15．（1）0 （2）next[k]
16．（1）i：=i+1 （2）j:=j+1 (3)i:=i-j+2 (4)j:=1; (5)i-mt（或i:=i-j+1） (6)0 17.程序中递归调用
（1）ch1<>midch //当读入不是分隔符&和输入结束符$时，继续读入字符
（2）ch1=ch2 //读入分隔符&后，判ch1是否等于ch2，得出真假结论。
（3）answer：=true
（4）answer：=false
（5）read（ch）
（6）ch=endch
18．（1）initstack（s） /／栈s初始化为空栈。
(2) setnull (exp) //串exp初始化为空串。
(3) ch in opset //判取出字符是否是操作符。
(4) push (s,ch) //如ch是运算符，则入运算符栈s。
(5) sempty (s) //判栈s是否为空。
(6) succ := false //若读出ch是操作数且栈为空，则按出错处理。
(7) exp (8)ch //若ch是操作数且栈非空，则形成部分中缀表达式。
(9) exp (10) gettop(s) //取栈顶操作符。
(11) pop(s) //操作符取出后，退栈。
(12) sempty(s) //将pre的最后一个字符（操作数）加入到中缀式exp的最
后。
四．应用题
１．串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。
２．空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。
３．最优的T(m,n)是O（n）。串S2是串S1的子串，且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度，一般情况下，T(m,n) =O(m*n)。
４．朴素的模式匹配（Brute－Force）时间复杂度是Ｏ（m＊n），KMP算法有一定改进，时间复杂度达到Ｏ（m＋n）。本题也可采用从后面匹配的方法，即从右向左扫描，比较６次成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二个字符开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种方法，本题比较18次成功。
５．KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入存且经常发生部分匹配时，KMP算法的优点更为突出．
６．模式串的next函数定义如下：
next［j］=?
?
?
?
?
=
<
<
=
-
+
-
-
其它情况
当此集合不空时
‘
且
时
当
1
}'
...
''
...
j
k
1|
k
max{
1
1
1
1
1j
k
j
k
p
p
p
p
j
根据此定义，可求解模式串t的next和nextval值如下：
7．解法同上题6，其next和nextval值分别为0112123422和010*******。
8．解法同题6，t串的next和nextval函数值分别为0111232和0110132。
9．解法同题6，其next和nextval 值分别为1和1。
10．p1的next和nextval值分别为：0112234和0102102；p2的next和nextval值分别为：
0121123和0021002。
11．next数组值为011234567 改进后的next数组信息值为010101017。12．011122312。
13．next定义见题上面6和下面题20。串p的next函数值为：。
（1）S的next与nextval值分别为9和9，p的next与nextval值分别为012123和002003。14．
（2）利用BF算法的匹配过程：利用KMP算法的匹配过程：
第一趟匹配： aabaabaabaac 第一趟匹配：aabaabaabaac
aabaac(i=6,j=6) aabaac(i=6,j=6)
第二趟匹配： aabaabaabaac 第二趟匹配：aabaabaabaac
aa(i=3,j=2) (aa)baac
第三趟匹配： aabaabaabaac 第三趟匹配：aabaabaabaac
a(i=3,j=1) (成功) (aa)baac 第四趟匹配： aabaabaabaac
aabaac(i=9,j=6)
第五趟匹配： aabaabaabaac
aa(i=6,j=2)
第六趟匹配： aabaabaabaac
a(i=6,j=1)
第七趟匹配： aabaabaabaac
(成功) aabaac(i=13,j=7)
15．（1）p的nextval函数值为0110132。（p的next函数值为0111232）。
（2）利用KMP(改进的nextval)算法，每趟匹配过程如下：
第一趟匹配： abcaabbabcabaacbacba
abcab(i=5,j=5)
第二趟匹配： abcaabbabcabaacbacba
abc(i=7,j=3)
第三趟匹配： abcaabbabcabaacbacba
a(i=7,j=1)
第四趟匹配： abcaabbabcabaac bacba
(成功) abcabaa(i=15,j=8)
16．KMP算法的时间复杂性是O（m+n）。
p的next和nextval值分别为和。
17．（1）p的nextval函数值为01010。（next函数值为01123）
（2）利用所得nextval数值，手工模拟对s的匹配过程，与上面16题类似，为节省篇幅，故略去。
18．模式串T的next和nextval值分别为0121123和0021002。
19．第4行的p[J]=p[K]语句是测试模式串的第J个字符是否等于第K个字符，如是，则指针J和K均增加1，继续比较。第6行的p[J]=p[K]语句的意义是，当第J个字符在模式匹配中失配时，若第K个字符和第J个字符不等，则下个与主串匹配的字符是第K个字符；否则，若第K个字符和第J个字符相等，则下个与主串匹配的字符是第K个字符失配时的下一个（即NEXTVAL[K]）。
该算法在最坏情况下的时间复杂度O（m2）。
20．（1）当模式串中第一个字符与主串中某字符比较不等（失配）时，next[1]=0表示模式串中已没有字符可与主串中当前字符s[i]比较，主串当前指针应后移至下一字符，再和模
式串中第一字符进行比较。
（2）当主串第i个字符与模式串中第j个字符失配时，若主串i不回溯，则假定模式串第k个字符与主串第i个字符比较，k值应满足条件1 （3）在上面两种情况外，发生失配时，主串指针i不回溯，在最坏情况下，模式串从第1个字符开始与主串第i个字符比较，以便不致丢失可能的匹配。 21．这里失败函数f，即是通常讲的模式串的next函数，其定义见本章应用题的第6题。 进行模式匹配时，若主串第i个字符与模式串第j个字符发生失配，主串指针i不回溯，和主串第i个字符进行比较的是模式串的第next[j]个字符。模式串的next函数值，只依赖于模式串，和主串无关，可以预先求出。 该算法的技术特点是主串指针i不回溯。在经常发生“部分匹配”和主串很大不能一次调入存时，优点特别突出。 22．失败函数（即next）的值只取决于模式串自身，若第j个字符与主串第i个字符失配时，假定主串不回溯，模式串用第k（即next[j]）个字符与第i个相比，有‘ p1…p k-1’=‘p j-k+1…p j-1’，为了不因模式串右移与主串第i个字符比较而丢失可能的匹配，对于上式中存在的多个k值，应取其中最大的一个。这样，因j-k最小，即模式串向右滑动的位数最小，避免因右移造成的可能匹配的丢失。 23．仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。 24．（1）s1和s2均为空串；（2）两串之一为空串；（3）两串串值相等（即两串长度相等且对应位置上的字符相同）。（4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。 25、题中所给操作的含义如下： //：连接函数，将两个串连接成一个串 substr（s,i,j）：取子串函数，从串s的第i个字符开始，取连续j个字符形成子串replace（s1,i,j,s2）：置换函数，用s2串替换s1串中从第i个字符开始的连续j个字符 本题有多种解法，下面是其中的一种： （1） s1=substr（s,3,1） //取出字符：‘y’ （2） s2=substr（s,6,1） //取出字符：‘+’ （3） s3=substr（s,1,5） //取出子串：‘(xyz)’ （4） s4=substr（s,7,1） //取出字符：‘*’ （5） s5=replace（s3,3,1,s2）//形成部分串：‘（x+z）’ （6） s=s5//s4//s1 //形成串t即‘（x+z）*y’ 五、算法设计 1、[题目分析]判断字符串t是否是字符串s的子串，称为串的模式匹配，其基本思想是对串s和t各设一个指针i和j，i的值域是0..m-n，j的值域是0..n-1。初始值i和j 均为0。模式匹配从s0和t0开始，若s0=t0，则i和j指针增加1，若在某个位置s i!=t j，则主串指针i回溯到i=i-j+1，j仍从0开始，进行下一轮的比较，直到匹配成功（j>n-1），返回子串在主串的位置（i-j）。否则，当i>m-n则为匹配失败。 int index(char s[],t[],int m,n) //字符串s和t用一维数组存储，其长度分别为m和n。本算法求字符串t在字符串s 中的第一次出现，如是，输出子串在s中的位置，否则输出0。 {int i=0,j=0; while (i<=m-n && j<=n-1) if (s[i]==t[j]){i++;j++;} //对应字符相等，指针后移。 else {i=i-j+1;j=0;} //对应字符不相等，I回溯，j仍为0。 if(i<=m-n && j==n) {printf(“t在s串中位置是%d”,i-n+1);return(i-n+1);}//匹配成功 else return(0); //匹配失败 }//算法index结束 main ()//主函数 {char s[],t[]; int m,n,i; scanf(“%d%d”,&m,&n); //输入两字符串的长度 scanf(“%s”,s); //输入主串 scanf(“%s”,t); //输入子串 i=index(s,t,m,n); }//程序结束 [程序讨论]因用C语言实现，一维数组的下标从0开始，m-1是主串最后一个字符的下标，n-1是t串的最后一个字符的下标。若匹配成功，最佳情况是s串的第0到第n-1个字符与t匹配，时间复杂度为o（n）；匹配成功的最差情况是，每次均在t的最后一个字符才失败，直到s串的第m-n个字符成功，其时间复杂度为o（（m-n）*n），即o（m*n）。失败的情况是s串的第m-n个字符比t串某字符比较失败，时间复杂度为o（m*n）。之所以串s的指针i最大到m-n，是因为在m-n之后,所剩子串长度已经小于子串长度n，故不必再去比较。算法中未讨论输入错误（如s串长小于t串长）。 另外，根据子串的定义，返回值i-n+1是子串在主串中的位置，子串在主串中的下标是i-n。 2.［问题分析］在一个字符串，统计含多少整数的问题，核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符串扫描到结束。 int CountInt（） // 从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。 ｛int i=0，a[]； // 整数存储到数组a，i记整数个数 scanf（“％c”，&ch）；// 从左到右读入字符串 while（ch!=‘#’） //‘#’是字符串结束标记 if（isdigit（ch））// 是数字字符 ｛num=０； // 数初始化 while（isdigit（ch）&& ch!=‘#’）// 拼数 ｛num=num＊10+‘ch’-‘０’； scanf（“％c”，&ch）； ｝ a[i]=num；i++； if（ch!=‘#’）scanf（“%c”，&ch）； // 若拼数中输入了‘#’，则不再输入 ｝// 结束while（ch！＝‘#’） printf（“共有%d个整数，它们是：”i）； for（j=０；j ｛printf（“%6d”，a[j]）； if（（j+1）％10==0）printf（“\n”）；} // 每10个数输出在一行上｝// 算法结束 ［算法讨论］假定字符串中的数均不超过32767，否则，需用长整型数组及变量。 3、[题目分析]设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。 int LongestString(char s[],int n) //串用一维数组s存储，长度为n，本算法求最长重复子串，返回其长度。 {int index=0,max=0; //index记最长的串在s串中的开始位置，max记其长度 int length=1,i=0,start=0; //length记局部重复子串长度，i为字符数组下标 while(i if(s[i]==s[i+1]) {i++; length++;} else //上一个重复子串结束 {if(max i++;start=i;length=1; //初始化下一重复子串的起始位置和长度 } printf(“最长重复子串的长度为%d，在串中的位置%d\n”，max,index); return(max); }//算法结束 [算法讨论]算法中用i 算法的时间复杂度为O(n），每个字符与其后继比较一次。 4、[题目分析]教材中介绍的串置换有两种形式：第一种形式是replace（s,i,j,t），含义是将s串中从第i个字符开始的j个字符用t串替换,第二种形式是replace(s,t,v)，含义是将s串中所有非重叠的t串用v代替。我们先讨论第一种形式的替换。因为已经给定顺序存储结构，我们可将s串从第（i+j-1）到串尾（即s.curlen）移动t.curlen-j绝对值个位置（以便将t串插入）：若j>t.curlen，则向左移；若j int replace(strtp s,t,int i,j) //s和t是用一维数组存储的串，本算法将s串从第i个字符开始的连续j个字符用t 串置换，操作成功返回1，否则返回0表示失败。 {if(i<1 || j<0 || t.curlen+s.curlen-j>maxlen) {printf(“参数错误\n”);exit(0);} //检查参数及置换后的长度的合法性。 if(j else if (j>t.curlen) //s串中被替换子串的长度小于t串的长度。 for(k=i-1+j;k<=s.curlen-1;k++) s.ch[k-(j-t.curlen)]=s.ch[k]; for(k=0;k 数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满 《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 一、实验目的 第一题利用单向环表实现约瑟夫环。 第二题归并顺序表。 二、实验内容 第一题采用单向环表实现约瑟夫环。 请按以下要求编程实现： ①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，……，m。 ②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。 例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。 第二题选作：归并顺序表。 请按以下要求编程实现： ①从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。 ②将链表linka和linkb归并为linkc，linkc仍然为升序排列。归并完成后，linka 和linkb为空表。输出linkc。 ③对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。 例如：linka输入为：10 20 30 40 50 0 linkb输入为：15 20 25 30 35 40 45 50 0 归并后的linkc为：10 15 20 20 25 30 30 35 40 40 45 50 50 删除重复后的linkc为：10 15 20 25 30 35 40 45 50 三、程序设计 1、概要设计 第一题为了实现程序功能，应当建立单向环表来寄存信息及结点，通过查找结 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构B．存储实现 C．逻辑结构D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列B.链表C.有序表D.链栈 （6）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i 算法与数据结构复习资料 一、单选题 在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B)。 A. HL=p;p->next=HL; B.p->next=HL->next;HL->next=p; C.p->next=HL;p=HL; D.p->next=HL;HL=p; 若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（B）个元素. A. n B.n-1 C.n+1 D.不确定 下述哪一条是顺序存储方式的优点？（A） A．存储密度大B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快 设有一个二维数组A[m][n]，假设A[0][0]存放位置在600 (10)，A[3][3]存放位置在678 (10) ， 每个元素占一个空间，问A[2][3] (10)存放在什么位置？(脚注 (10) 表示用10进制表示,m>3)C A．658 B．648 C．633 D．653 下列关于二叉树遍历的叙述中，正确的是( D) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 k层二叉树的结点总数最多为(A). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 对线性表进行二分法查找，其前提条件是( C). A.线性表以链接方式存储，并且按关键码值排好序 B.线性表以顺序方式存储，并且按关键码值的检索频率排好序 C. 线性表以顺序方式存储，并且按关键码值排好序 D. 线性表以链接方式存储，并且按关键码值的检索频率排好序 对n个记录进行堆排序，所需要的辅助存储空间为（C） A. O（1og2n） B. O（n） C. O（1） D.O（n2） 对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（D）个， A．1 B．2 C．3 D．4 下列关于数据结构的叙述中，正确的是( D). A. 数组是不同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为精炼 C. 树是一种线性结构 D. 用一维数组存储一棵完全二叉树是有效的存储方法 在决定选取何种存储结构时，一般不考虑（ A ）。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（B）。A．单链表B．静态链表C．线性链表D．顺序存储结构 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A）。 A．q=p->next；p->data=q->data；p->next=q->next；free(q)； B．q=p->next；q->data=p->data；p->next=q->next；free(q)； C．q=p->next；p->next=q->next；free(q)； 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点内容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基本 单位，在计算机程序中通常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数 据项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 数据结构试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 复习题集─参考答案 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续存空间时，为提高存利用率，减少溢出机会，应把两个栈的栈底分别设在这片存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据] （×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] （√）28.树形结构中每个结点至多有一个前驱。 （×）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。 （×）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。 （×）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。 （×）32.顺序查找方法只能在顺序存储结构上进行。 （×）33.折半查找可以在有序的双向链表上进行。 烟台大学计算机学院课程设计（算法与数据结构） 设计题目： 班级 姓名 学号 指导教师 成绩 二○一三年四月十日 内容包括： 一、课程设计题目： 二、课程设计内容： 三、算法设计： 四、程序正确性验证（指边界测试数据，即程序对于精心选择的典型、苛刻 而带有刁难性的几组输入数据能够得出满足要求的结果）： 五、课程设计过程中出现的主要问题、原因及解决方法： 六、课程设计的主要收获： 七、对今后课程设计的建议： 算法与数据结构课程设计题目 一、单项分值：25分 1、约瑟夫环游戏 2、八皇后问题(图形表示加20分) 3、表达式的求值问题 4、迷宫问题(图形表示加10分) 二、单项分值：80分 5、HTML文档标记匹配算法 要求：输入一段HTML代码，判断该代码是否符合HTML的语法 提示：HTML文档由不同的标记划分为不同的部分与层次。与括号类似，这些标记需要成对出现，对于名为 数据结构复习题 第一章概论 一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。 数据结构与方法 1、算法的基本特征:可行性、确定性、有穷性、拥有足够的情报 2、算法的基本运算与操作:算术运算、逻辑运算、关系运算、数据传输 3、算法的基本控制结构:顺序结构、选择结构、循环(重复)结构 4、算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法 5、算法的复杂度主要包括:时间复杂度、空间复杂度 6、算法的时间复杂度:指执行算法所需要的计算工作量 7、算法的空间复杂度:指执行这个算法所需要的内存空间 8、数据结构主要研究:数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算 9、数据结构研究的目的:提高数据处理的效率 10、数据处理的效率:数据处理的速度、减少处理过程中占用计算机的存储空间 11、数据处理:指对数据集合中的各元素以各种方式进行运算 12、数据元素:指在数据处理中,每一个需要处理的对象都可以抽象成数据元素 13、数据结构:指反映数据元素之间关系的数据元素集合的表示 14、数据的逻辑结构:指反映数据元素之间逻辑关系的数据结构,两要素:数据元素的集合、数据元素在集合上的关系 15、数据的存储结构:指数据的逻辑结构在计算机存储空间的存放形式,常用的存储结构有:顺序、链接、索引等 16、数据结构的图形表示中每个元素加上方框成为结点 17、数据结构一般分为:线性结构、非线性结构 18、线性结构满足:有且仅有一个根结点、每个结点最多有一个前件与后件、在一个线性结构中插入与删除任何一个结点后还就是线性结构 19、线性表定义:线性表就是由n个数据元素a1、a2、a3、a4……an组成的一个有限序列,表中每一个数据元素,除了第一个外,有且仅有一个前件,除了最后一个外,有且仅有一个后件20、非线性表的特征:有且只有一个根节点a1,它无前件、有且只有一个终结点an,它无后件、除了第一个与最后一个外,其她所有结点只有一个前件与一个后件 21、线性表的长度:线性表中的结点的个数n成为线性表的长度,当n=0时,成为空表 22、线性表的顺序存储的特点:所有元素所占的存储空间就是连续的、各数据元素在存储空间中就是按逻辑顺序一次存放的 23、线性表的随机存取地址计算公式:ADD(ai)=ADD(a1)+(i-1)*k 24、线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转 25、栈的定义:栈就是限定在一端进行插入与删除的线性表,它按照“先进后出,后进先出”的原则组织数据 26、栈的顺序存储:在程序设计语言中,一般一维数组S(1:m)作为栈的顺序存储空间,其中m 为栈的最大容量 27、栈的基本运算:入栈、退栈、读栈顶元素 28、入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,称为“上溢”错误 29、退栈运算:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1。当栈顶指针为0时,说明栈空,成为“下溢”错误 30、队列的定义:队列就是指允许在一端进行插入,而在另一端进行删除的线性表,它按照“先进先出”的原则组织数据 31、循环队列:在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列, 《算法与数据结构》习题1 第一部分 一、单项选择题 1.（）二叉排序树可以得到一个从小到大的有序序列。 A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 2.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i 结点的左孩子结点的编号为（）。 A、2i+1 B、2i C、i/2 D、2i-1 3.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序 列为（）。 A、q=p->next；p->data=q->data；p->next=q->next；free(q)； B、q=p->next；q->data=p->data；p->next=q->next；free(q)； C、q=p->next；p->next=q->next；free(q)； D、q=p->next；p->data=q->data；free(q)； 4.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得 到序列为（）。 A、BADC B、BCDA C、CDAB D、CBDA 5.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。 A、n B、n-1 C、m D、m-1 6.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。 A、O(1) B、O(log2n) C、O(nlog2n) D、O(n2) 7.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A、25 B、10 C、7 D、1 二、填空题 1.设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A 的后面插入结点X的操作序列为______=p；s->right=p->right；______=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为______。 3.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为 3的结点数有______个。 4.后缀算式9 2 3 + - 10 2 / -的值为______。中缀算式（3+4X）-2Y/3对应的后缀算式 为______。 5.设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第______个元 素开始进行筛选。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 算法设计题 1. 设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的个数。 【答案】 int count=0; void algo2(BTNode *bt){ if (bt){ if(bt->lchild || bt->rchild){ printf(bt->data); count++; } algo2(bt->lchild); algo2(bt->rchild); } } 2. 阅读下列函数arrange() int arrange(int a[],int 1,int h,int x) {//1和h分别为数据区的下界和上界 int i,j,t； i=1；j=h； while(i 数据结构模拟试题... 一、简答题（15分，每小题3分） 1.简要说明算法与程序的区别。 2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？ 3.说明在图的遍历中，设置访问标志数组的作用。 4.说明以下三个概念的关系：头指针，头结点，首元素结点。 5.在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？ 二、判断题（10分，每小题1分） 正确在括号内打√，错误打× ( )（1）广义表((( a ), b), c ) 的表头是(( a ), b)，表尾是( c )。 ( )（2）在哈夫曼树中，权值最小的结点离根结点最近。 ( )（3）基数排序是高位优先排序法。 ( )（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。 ( )（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p->next = s; s->next = p->next; ( )（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。 ( )（7）数组元素的下标值越大，存取时间越长。 ( )（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。 ( )（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。 ( )（10）长度为1的串等价于一个字符型常量。 三、单项选择题（10分, 每小题1分） 1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？ A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序 2．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该： A）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元素全部置为0 C）将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素全部置为0 3．有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是： A.head->priro==NULL B. head->next==NULL C. head->next==head D. head->next-> priro==NULL 4. 在顺序表( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比 内江师范学院 数据结构与算法设计课程设计实验报告册 编制算法设计课题组审定曾意 数学与信息科学学院 2014年9月 1. 学生在做实验之前必须要准备实验，主要包括预习与本次实验相关的理论知识，熟练与本次实验相关的软件操作，收集整理相关的实验参考资料，要求学生在做实验时能带上充足的参考资料；若准备不充分，则学生不得参加本次实验，不得书写实验报告； 2. 要求学生要认真做实验，主要是指不得迟到、早退和旷课，在做实验过程中要严格遵守实验室规章制度，认真完成实验内容，极积主动地向实验教师提问等；若学生无故旷课，则本次实验等级计为D； 3. 学生要认真工整地书写实验报告，实验报告的内容要紧扣实验的要求和目的，不得抄袭他人的实验报告； 4. 实验成绩评定分为A+、A、A-、B+、B、C、D 各等级。根据实验准备、 实验态度、实验报告的书写、实验报告的内容进行综合评定，具体对应等级如下：完全符合、非常符合、很符合、比较符合、基本符合、不符合、完全不符 合 实验名称：算法设计基础实验(实验一) 指导教师：牟廉明，刘芳实验时数： 4 实验设备：安装了VC++计算机 实验日期：年_月_日实验地点：第五教学楼北802 实验目的： 掌握算法设计的基本原理，熟悉算法设计的基本步骤及其软件实现。 实验准备： 1. 在开始本实验之前，请复习相关实验内容； 2. 需要一台准备安装Windows XP Professional操作系统和装有VC++6.0的计算机。 实验内容： 求n至少为多大时，n个1组成的整数能被2013整除。 实验过程： 1.1算法思想 2013=61*33,6个1能够整除33,寻找满足n个1能够整除61的n即可。 1.2算法步骤 1?定义变量y储存余数，i储存1的个数，m为被除数，初始化为111111； 2?如果被除数能够除尽61,输出i; 如果被除数不能够除尽61，while继续循环，m=y*1000000+111111,i++; 3?重复2，直到找到满足条件的m为止，输出i; 1.3算法实现(C++程序代码) #in clude 数据结构与算法基础 一．判断题： 1．数据元素是数据的最小单位。 2．数据结构是带有结构的数据元素的集合。 3．数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点、数据域。 4．数据项是数据的基本单位。 5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。 6．数据的物理结构是指数据在计算机内实际的存储形式。 7．算法和程序没有区别，所以在数据结构中二者是通用的。 答案： 1．错误 2．正确 3．正确 4．错误 5．正确 6．正确 7．错误 二． 数据结构是研究数据的 A 和 B 以及它们之间的相互关系，并对这种结构定义相应的 C ，设计出相应的 D ，而确保经过这些运算后所得到的新结构是 E 结构类型。 供选择答案： A、Ｂ：ａ理想结构ｂ抽象结构ｃ物理结构ｄ逻辑结构 Ｃ、Ｄ、Ｅ：ａ运算ｂ算法ｃ结构ｄ规则ｅ现在的ｆ原来的 答案： Ａ：ｃＢ；ｄＣ：ａＤ：ｂＥ：ｆ 三．从供选择的答案中选取正确的答案填在下面叙述中的横线上： 1． A 是描述客观事物的数字、字符以及所能输入到计算机中并被计算机程序加工处理的符号的集合。 2. B 是数据的基本单位,即数据集合中的个体。有时一个 B 由若干个___C____组成，在这种情况下，称 B 为记录。 C 是数据的最小单位。而由记录所组成的线性表为 D 。 3. E 是具有相同特性的数据元素的集合，是数据的子集。 4. Ｆ是带有结构特性数据元素的集合。 5. 被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系。通常将数据元素的这种关系称为Ｇ。 6. 算法的计算量的大小称为计算的Ｈ。 供选择的答案： Ａ－Ｆ：ａ数据元素ｂ符号ｃ记录ｄ文件ｅ数据ｆ数据项ｇ数据对象ｈ关键字ｉ数据结构 《算法与数据结构》习题1 一、单项选择题 1. 数据结构从逻辑上分为（）。 A．动态结构和静态结构 B．内部结构和外部结构 C．紧凑结构和非紧凑结构 D．线性结构和非线性结构 2. 栈和队列的共同点是（）。 A．都是先进后出 B．都是后进先出 C．只允许在端点处插入和删除元素 D．没有共同点 3．若按从左到右的顺序读入已知序列a、b、c、d、e、f、g中的元素，然后结合栈的操作，能得到下列序列中的哪些序列？（） A．decfbga B．fegdacb C．efdgbca D．dcbefag 4. 在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点 s，则执行（）。 A．s→link=p→link；p→link =s； B．p→link =s；s→link=q； C．p→link=s→link；s→link =p； D．q→link =s；s→link=p； 5．算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 6. 一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C 7. 从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8. 以下数据结构中，哪一个是线性结构？（） A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 二、多项选择题 1. 以下说法正确的是（）。 A. 二叉树的特点是每个结点至多只有两棵子树 B. 二叉树的子树无左右之分 C. 二叉树只能进行链式存储 D. 树的结点包含一个数据元素及若干指向其子树的分支2．在数组上能做的操作有（）。 A.插入 B.删除 C.取值操作 D.赋值操作 3. 图的应用算法有（）。 A. 克鲁斯卡尔算法 B. 哈弗曼算法 C. 迪杰斯特拉算法 D. 拓扑排序算法 4. 计算机算法必须具备（）等特性。 A. 可行性、确定性 B. 可行性、可移植性 C. 输入、输出 《数据结构》 Part1 一．选择 1. 组成数据的基本单位是（） A）数据项B）数据类型C）数据元素D）数据变量 2．算法分析的目的是（） A）找出数据结构的合理性B）研究算法的输入/输出关系 C）分析算法的效率以求改进D）分析算法的易读性 3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A）O(1) B）0(n) C）O(n^2) D）O(nlog2n) 4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（） A）112 B）144 C）148 D）412 5．下面关于线性表的叙述中，错误的是（） A）顺序表使用一维数组实现的线性表B）顺序表必须占用一片连续的存储单元. C）顺序表的空间利用率高于链表D）在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（）比较合适 A）单链表B）双链表C）顺序表D）循环链表 7．队列通常采用的两种存储结构是（） A）顺序存储结构和链式存储结构B）散列方式和索引方式 C）链表存储结构和线性存储结构D）线性存储结构和非线性存储结构 8．在一个单链表中，若删除p所指结点的后继结点，则执行（） A）p->next=p->next->next；B）p=p->next；p->nex=p->next->next； C）p->next=p->next；D）p=p->next->next； 9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间 A）单链表B）仅有头指针的单循环链表C）双链表D）仅有尾指针的单循环链表 10．按二叉树的定义，具有三个结点的二元树共有（）种形态。 A）3 B）4 C）5 D）6 11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）发生改变B）不发生改变C）不能确定D）以上都不对12．深度为5的二叉树至多有（）个结点 A）16 B）32 C）31 D）10 13．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。 A）4 B）5 C）6 D）7 14．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（） A）n B）n+1 C）n-1 D）n/2 15．静态查找表和动态查找表二者的根本差别在于（）数据结构与算法基础知识总结
数据结构与算法设计实验一
数据结构与算法习题及答案
算法与数据结构复习资料
数据结构与算法设计知识点
算法与数据结构试题及答案
数据结构与算法复习题及参考答案
《算法与数据结构》课程设计报告书
:节的头部 ●数据结构与算法复习题库含答案
数据结构与算法知识点必备
算法与数据结构习题
数据结构算法设计题复习题
算法与数据结构试题及答案
数据结构与算法设计课程设计
数据结构与算法基础
算法与数据结构练习题
数据结构和C++程序设计_题库