数据结构考研试题(第四章)串
第四章串
一、选择题
1．下面关于串的的叙述中，哪一个是不正确的？（）【北方交通大学2001 一、5（2分）】
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可
以采用链式存储
2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4
,index(S2,‘8’),length(S2)))
其结果为（）【北方交通大学 1999 一、5 （25/7分）】A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234
3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的
算法称为（）
A．求子串 B．联接 C．匹配 D．求串长
【北京邮电大学 2000 二、4（20/8分）】【西安电子科技大学 1996 一、
1 （2分）】
4．已知串S=‘aaab’,其Next数组值为（）。【西安电子科技大学 1996 一、7 （2分）】
A．0123 B．1123 C．1231 D．1211
5．串‘ababaaababaa’的next数组为（）。【中山大学 1999 一、7】A．012345678999 B．012121111212 C．011234223456 D．0123012322345
6．字符串‘ababaabab’的nextval 为（）
A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1)
C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )
【北京邮电大学 1999 一、1（2分）】
7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval数组的值为（）。
A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2
3 4 5 6 1 1 2
C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2
3 4 5 6 7 1 2
E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1
1 0
2 1 7 0 1
【北京邮电大学 1998 二、3 （2分）】
8．若串S=’software’,其子串的数目是（）。【西安电子科技大学 2001应用一、2（2分）】
A．8 B．37 C．36 D．9
9．设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。【中科院计算所1997 】
A．2n-1 B．n2 C．(n2/2)+(n/2) D．(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其他情况
10．串的长度是指（）【北京工商大学 2001 一、6 （3分）】A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
二、判断题
1．KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）【北京邮电大学 2002 一、4 （1分）】
2．设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）【长沙铁道学院 1998 一、1 (1分)】
3．串是一种数据对象和操作都特殊的线性表。（）【大连海事大学 2001 1、L (1分)】
二、填空题
1．空格串是指__(1)__，其长度等于___(2)__。【西安电子科技大学 2001软件一、4（2分）】
2．组成串的数据元素只能是________。【中山大学 1998 一、5 （1分）】3．一个字符串中________称为该串的子串。【华中理工大学 2000 一、3（1分）】
4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。【福州大学 1998 二、4 (2分)】
5．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。
【重庆大学 2000 一、4】
6．模式串P=‘abaabcac’的next函数值序列为________。【西安电子科技大学 2001软件一、6（2分）】
7．字符串’ababaaab’的nextval函数值为________。【北京邮电大学 2001 二、4 （2分）】
8．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为__(1)__，
又称P为__(2)__。
【西安电子科技大学 1998 二、5 （16/6分）】
9．串是一种特殊的线性表，其特殊性表现在__(1)__；串的两种最基本的存储方式是__(2)__、__(3)__；两个串相等的充分必要条件是__(4)__。【中国矿业大学 2000 一、3 （4分）】
10．两个字符串相等的充分必要条件是_______。【西安电子科技大学 1999软件一、1 （2分）】
11．知U=‘xyxyxyxxyxy’；t=‘xxy’；
ASSIGN（S，U）；
ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；
ASSIGN（m，‘ww’）
求REPLACE（S，V，m）= ________。【东北大学 1997 一、1 (5分)】12．实现字符串拷贝的函数 strcpy为：
void strcpy(char *s , char *t) /*copy t to s*/
{ while (________)
} 【浙江大学 1999 一、5 (3分)】
13．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如
f("abba")返回1，f("abab")返回0；
int f((1)________)
{int i=0,j=0;
while (s[j])(2)________;
for(j--; i return((3)_______) } 【浙江大学 1999 一、6 (3分)】 14．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。 程序（a） PROCEDURE maxcomstr(VAR s,t : orderstring; VAR index,length : integer); VAR i,j,k,length1:integer; con:boolean; BEGIN index :=0; length :=0; i :=1; WHILE(i<=s.len) DO [j:=1; WHILE (j<=t.len) DO [ IF (s[i]=t[j]) THEN [ k:=1; length1:=1; con:=true; WHILE con DO IF (1)__THEN [length1:=length1+1;k:=k+1;] ELSE(2) _; IF (length1>length) THEN [index:=i; length:=length1; ] (3)____; ] ELSE (4)____; ] (5) ___; ] END; 程序(b) void maxcomstr(orderstring *s,*t; int index, length) {int i,j,k,length1,con; index=0;length=0;i=1; while (i<=s.len) {j=1; while(j<=t.len) { if (s[i]= =t[j]) { k=1;length1=1;con=1; while(con) if (1) _ { length1=length1+1;k=k+1; } else (2) __; if (length1>length) { index=i; length=length1; } (3)____; } else (4) ___; } (5) __ } } 【上海大学 2000 一、2 （10分）】 15．完善算法：求KMP算法中next数组。 PROC get _next(t:string,VAR next:ARRAY[1..t.len] OF integer); BEGIN j:=1; k:=(1)__; next[1]:=0; WHILE j IF k=0 OR t.ch[j]=t.ch[k] THEN BEGIN j:=j+1; k:=k+1; next[j]:=k;END ELSE k:=(2)___; END; 【中山大学 1998 四、1 （4分）】 16．下面函数index用于求t是否为s的子串，若是返回t第一次出现在s中的序号(从1开始计)，否则返回0。 例如:s=‘abcdefcdek’，t=‘cde’,则indse(s,t)=3, index(s,’aaa’)=0 。已知t，s的串长分别是mt,ms FUNC index(s,t,ms,mt); i:=1;j:=1; WHILE (i IF s[i]=t[j] THEN [ (1)__; (2)__] ELSE [ (3)___; (4)_ ] IF j>mt THEN return (5)____; ELSE return (6)__ ENDF; 【南京理工大学 1999 三、2 （6分）】 17．阅读下列程序说明和pascal程序,把应填入其中的（）处的字 句写在答题纸上。 程序说明： 本程序用于判别输入的字符串是否为如下形式的字符串: W&M$ 其中,子字符串M是子字符串W的字符反向排列,在此假定W 不含有字符&和字符$,字符&用作W与M的分隔符,字符$用作字符串的 输入结束符。 例如,对输入字符串ab&ba$、11&12$、ab&dd$、&$,程序将分别输出Ok.(是),No.(不是)。 程序 PROGRAM accept(input,output); CONST midch=’&’; endch=’$’; VAR an:boolean; ch:char; PROCEDURE match(VAR answer: boolean); VAR ch1,ch2:char; f:boolean; BEGIN read(ch1); IF ch1<>endch THEN IF (1)__ THEN BEGIN match(f); IF f THEN BEGIN read(ch2); answer:=(2)_ END ELSE answer:=false END ELSE (3)___ ELSE (4)___ END; BEGIN writeln(‘Enter String:’); match(an); IF an THEN BEGIN (5)__ IF (6)_ THEN writeln(‘Ok.’) ELSE writeln(‘No.’) END ELSE writeln(‘No.’) END. 【上海海运学院 1998 七（15分）】 18．试利用下列栈和串的基本操作完成下述填空题。 initstack(s) 置s为空栈； push(s,x) 元素x入栈; pop(s) 出栈操作; gettop(s) 返回栈顶元素； sempty(s) 判栈空函数； setnull(st) 置串st为空串； length(st) 返回串st的长度； equal(s1,s2) 判串s1和s2是否相等的函数； concat(s1,s2) 返回联接s1和s2之后的串； sub(s,i,1) 返回s中第i个字符； empty(st) 判串空函数 FUNC invert(pre:string; VAR exp:string):boolean; {若给定的表达式的前缀式pre正确，本过程求得和它相应的表达式exp并返回“true”，否则exp为空串，并返回“false”。已知原表达式中不包含括弧，opset为运算符的集合。} VAR s:stack; i,n:integer; succ:boolean; ch: char; BEGIN i:=1; n:=length(pre); succ:=true; (1)__; (2)__; WHILE (i BEGIN ch:=sub（pre,i,l）; IF (3)_ THEN (4)__ ELSE IF (5)__THEN (6)_ ELSE BEGIN exp:=concat((7)___,(8)____); exp:=concat((9)___,(10)___); (11)__; END; i:=i+1 END; IF (12)___THEN BEGIN exp:=concat(exp,sub(pre,n,1)); invert:=true END ELSE BEGIN setnull(exp); invert:=false END END; 注意：每个空格只填一个语句。【清华大学 1996 八】 四、应用题 1．名词解释：串【大连海事 1996 一、10 (1分) 】【河海大学 1998 二、5（3分）】 2．描述以下概念的区别：空格串与空串。【大连海事大学 1996 三、2、（1）(2分)】 3．两个字符串S1和S2的长度分别为m和n。求这两个字符串最大共同子串算法的时间复杂度为T(m,n)。估算最优的T(m,n)，并简要说明理由。【北京工业大学 1996 一、5 (6分)】 4．设主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。请问：如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？【大连海事大学 2001 四 (8分)】 5．KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进?【大连海事大学1996三、1((2分)】 6．已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。 【北京邮电大学 1997 三（10分）】 7．给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。【北京邮电大学 2000 三、1（5分）】 8．令t=‘abcabaa’,求其next 函数值和nextval函数值。【北方交通大学 1994 一（6分）】 9．已知字符串‘cddcdececdea’，计算每个字符的next和nextval函数的值。【南京邮电大学 2000 一 2】 10．试利用KMP算法和改进算法分别求p1=‘abaabaa’和p2=‘aabbaab’ 的next函数和nextval函数。 【东南大学 1999 一、6（8分）】 11．已知KMP串匹配算法中子串为babababaa,写出next数组改进后的next 数组信息值（要求写出数组下标起点）。【西南交通大学 2000 二、2】12．求模式串T=‘abcaabbac' 的失败函数Next(j)值。【西安交通大学1996 四、4 (5分)】 13．字符串的模式匹配KMP算法中,失败函数(NEXT)是如何定义的?计算模式串p=‘aabaabaaabc’中各字符的失败函数值.【石油大学 1998 一、2 (10分)】 14．设字符串S=‘aabaabaabaac'，P=‘aabaac' （1）给出S和P的next值和nextval值； （2）若S作主串，P作模式串，试给出利用BF算法和KMP算法的匹配过程。 【北方交通大学1998二（15分）】 15．设目标为t=‘abcaabbabcabaacbacba’,模式为p=‘abcabaa’（1）计算模式p的naxtval函数值；（5分） （2）不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。（5分） 【清华大学 1998 八（10分）】 16．模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m，模式的长度为n，则在主串中寻找模式的KMP算法的时间复杂性是多少？如果，某一模式 P=’abcaacabaca’，请给出它的NEXT函数值及NEXT函数的修正值NEXTVAL之值。【上海交通大学 2000 一（5分）】17．设目标为S=‘abcaabbcaaabababaabca’，模式为P=‘babab’，（1）手工计算模式P的nextval数组的值；(5分) （2）写出利用求得的nextval数组，按KMP算法对目标S进行模式匹配的过程。 (5分) 【清华大学 1997 四（10分）】 18．用无回溯的模式匹配法（KMP法）及快速的无回溯的模式匹配法求模式串T的 【北京邮电大学 1992 三、1（25/4分）】 19．在改进了的（无回溯）字符串模式匹配中，要先求next数组的值。下面是求nextval值的算法。 TYPE SAR=ARRAY[1..m] OF INTEGER; PTY=ARRAY[1..m] OF CHAR; PROCEDURE next2(P:PTY;VAR NEXTVAL:SAR); {在模式P中求nextval数组的值} 11BEGIN 22J:=1;NEXTVAL[1]:=0;K:=0 33REPEAT 44 IF (K=0) OR (P[J]=P[K]) 55 THEN [ J:=J+1;K:=K+1; 66 IF P[J]=P[K] 77 THEN NEXTVAL[J]:=NEXTVAL[K] 88 ELSE NEXTVAL[J]:=K ] 99 ELSE K:=NEXTVAL[K] 1010 UNTIL J=m 1111END; 算法中第4行有P[J]=P[K],第六行中也有P[J]=P[K]。两处比较语句相同。请分析说明此两处比较语句的含义是什么？分析此算法在最坏情况下的时间复杂度是多少？【北京邮电大学 1993 二、2（6分）】 20．在字符串模式匹配的KMP算法中，求模式的next数组值的定义如下： next［j］=? ? ? ? ? = < < = - + - - 其它情况 ‘ 且 时 当 1 }' ... '' ... j k 1| k max{ 1 1 1 1 1j k j k p p p p j 请问： （1）当j=1时，为什么要取next[1]=0？ （2）为什么要取max{K},K最大是多少？ （3）其它情况是什么情况，为什么取next[j]=1? 【北京邮电大学 1994 二（8分）】 21．给出KMP算法中失败函数f的定义，并说明利用f进行串模式匹配的规则，该算法的技术特点是什么？ 【东南大学 1993 一、3 （9分） 1997 一、2 （8分） 2001 一、6 （6分）】 22．在模试匹配KMP算法中所用失败函数f的定义中，为何要求p1p2…… p f(j)为p1p2……p j两头匹配的真子串？且为最大真子串？【东南大学 1996 一、3（7分）】 23．如果两个串含有相等的字符，能否说它们相等？【西安电子科技大学2000软件一、3 （5分）】 24．设S1,S2为串，请给出使S1//S2=S2//S1成立的所有可能的条件（//为连接符）。 【长沙铁道学院 1997 三、5 (3分)】【国防科技大学 1999 一】25．已知：s ＝'（xyz）＋＊'，t ＝'（x＋z）＊y'。试利用联结、求子串和置换等基本运算，将 s 转化为 t 。 【北方交通大学 1996 一、3（5分）】【山东科技大学 2002 一、6 （5分）】 第五部分、算法设计 1．设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。（注：用程序实现）【南京航空航天大学 1997 九(10分)】 2．输入一个字符串，内有数字和非数字字符，如：ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组ａ中，例如123放入ａ［０］,456放入ａ［１］，……。编程统计其共有多少个整数，并输出这些数。【上海大学 1998 一（13分）】 3．以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。【东南大学 2000 五（15分）】类似本题的另外叙述有： （1）如果字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。试设计一算法，输入字符串S，以“！”作为结束标志。如果串S中不存在等值子串，则输出信息“无等值子串”，否则求出（输出）一个长度最大的等值子串。 例如：若S=“abc123abc123!”，则输出“无等值子串”；若S=“abceebccadddddaaadd!”，则输出“ddddd”。 【华中科技大学 2001】 4．假设串的存储结构如下所示，编写算法实现串的置换操作。【清华大学1995 五（15分）】 TYPE str t p =RECORD ch: ARRAY[1..maxlen] OF char; curlen:0..maxlen END; 5．函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s 中，插入位置为pos。请用c语言实现该函数。假设分配给字符串s的空 间足够让字符串t插入。（说明：不得使用任何库函数） 【北京航空航天大学 2001 六（10分）】 6．设计一个二分检索的算法,在一组字符串中找出给定的字符串,假设所有字符串的长度为4。 （1）简述算法的主要思想；(3分) （2）用PASCAL语言分别对算法中用到的类型和变量作出说明；(3分) （3）用类PASCAL语言或自然语言写算法的非递归过程； (8分) （4）分析该算法的最大检索长度；(3分) （5）必要处加上中文注释。(3分) 【山东工业大学 1995 八（20分）】 7．设计一PASCAL 或C语言的函数 atoi(x).其中X 为字符串，由0--9 十个数字符和表示正负数的‘-’组成，返回值为整型数值。【浙江大学 1994 二 (7分)】 8．已知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n),将其 按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3。【首 都经贸大学 1998 三、8（15分）】 9．串以静态存储结构存储，结构如下所述，试实现串操作equal算法. CONST maxlen=串被确认的最大长度 TYPE strtp=RECORD ch:ARRAY[1..maxlen] OF char; curlen:0..maxlen END; (以一维数组存放串值，并设指示器curlen指示当前串长)【北京轻工 业大学 1998 一（12分）】 10．编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存 入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。 【西北大学 2000 四 (10分)】 11．写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。【西 南交通大学 2000 三、2】 12．已知三个字符串分别为s=’ab…abcaabcbca…a’，s’=’caab’, s’’ =’bcb’。利用所学字符串基本运算的函数得到结果串为：s’’’=’caabcbca… aca…a’，要求写出得到上结果串S’’’所用的函数及执行算法。【东北大 学 1998 一、1 (10分)】 13．S=“S1S2…Sn”是一个长为N的字符串，存放在一个数组中，编程序 将S改造之后输出： （1）将S的所有第偶数个字符按照其原来的下标从大到小的次序放 在S的后半部分； （2）将S 的所有第奇数个字符按照其原来的下标从小到大的次序放 在S 的前半部分； 例如： S=‘ABCDEFGHIJKL ’ 则改造后的S 为‘ACEGIKLJHFDB ’。【中科院计算所 1995】 14．编一程序，对输入的一表达式（字符串），输出其TOKEN 表示。表达式 由变量A ，B ，C ，常数（数字）0，1，…，9，运算符+，*和括号“（”，“）” 组成。首先定义符号的类码： 其次定义符号的TOKEN 表示： 其中NAMEL 是变量名表（不允许有相同名）， CONST 是常量表（不允许 有相同数）。 例如，假设有表达式（A+A*2）+2*B*3#，则将生成如下TOKENL ： 【吉林大学 1995 一 (20分)】 变量：常量 + * （ ） 123456A +A *2789101112）+*132B *3 第四章串 注：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串 是任意串的子串，任意串是其自身的子串。若字符串长度为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{ 101111j k j k p p p p j 7．解法同上题6，其next 和nextval 值分别为0112123422和010*******。 8．解法同题6，t 串的next 和nextval 函数值分别为0111232和0110132。 9．解法同题6，其next 和nextval 值分别为011123121231和 011013020131。 10．p1的next 和nextval 值分别为：0112234和0102102；p2的next 和nextval 值分别为：0121123和0021002。 11．next 数组值为011234567 改进后的next 数组信息值为010101017。 12．011122312。 13．next 定义见题上面6和下面题20。串p 的next 函数值为：01212345634。 14．（1）S 的next 与nextval 值分别为012123456789和002002002009，p 的next 与nextval 值分别为012123和002003。 （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值分别为01112212321和01102201320。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 一.选择题篇 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1）它必须具备（2）这三个特性。【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）; A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）; A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（），它必须具备（）这三个特性; (1)A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2)A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性4．一个算法应该是（）; A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C 5. 下面关于算法说法错误的是（）; A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）; (1）算法原地工作的含义是指不需要任何额外的辅助空间;（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法;（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界;（4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类; A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）; A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）; A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关（）; A．栈 B. 哈希表 C. 线索树 D. 双向链表 北航2002年程序设计与数据结构试题 一、简答题（10’） 1. 数据结构课程是计算机专业的基础课还是专业课，或者专业基础课？（2’） 2. 学习数据结构课程需要哪些课程作为它的基础（举例两门课程）？若没有这些知识，对学习数据 结构课程可能会产生哪些影响？请举例说明（不超过100字）。（4’） 3. 数据结构课程将为那些课程学习奠定必要的基础？请举例说明哪些课程（举例两门课程）用到了 数据结构课程的哪些知识（不超过100字）。（4’） 二、（5’） 请推导出结论：具有0n 个叶结点的哈夫曼树（Huffman ）的分支总数为02(1)n -。 三、单项选择题（2’×15） 1. 线性链表中各链接点之间的地址________。 A. 必须连续 B. 部分地址必须连续 C. 不一定连续 D. 连续与否无所谓 2. 在非空线性链表中由p 所指的链接点后面插入一个由q 所致的链接点的过程是依次执行动作 ________。 A. link(q)←p; link(p)←q; B. link(q)←link(p); link(p)←q; C. link(q)←link(p); p ←q; D. link(p)←q; link(q)←p; 3. 在非空双向循环链表中由q 所指的那个链接点前插入一个p 指的链接点的动作对应的语句依次为 rlink(p)←q, llink(p)←llink(q), llink(q)←p, ________。（空白处为一条赋值语句） A. rlink(q)←p B. rlink(llink(q))←p C. rlink(llink(p))←p D. rlink(rlink(p))←p 4. 在初始为空的堆栈中依次插入元素f, e, d, c, b, a 以后，连续进行了三次删除操作，此时栈顶元素是 ________。 A. c B. d C. b D. e 5. 若某堆栈的输入序列为1, 2, 3, …, n ，输出序列的第1个元素为n ，则第i 个输出元素为________。 A. i B. n i - C. 1n i -+ D. 哪个元素无所谓 6. 求字符串T 在字符串S 中首次出现的位置的操作称为________。 A. 求串的长度 B. 求子串 C. 串的模式匹配 D. 串的连接 7. 若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为 4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树一共有________个叶结点。 A. 35 B. 28 C. 77 D. 78 8. 若一棵二叉树有1001个结点，且无度为1的结点，则叶结点的个数为________。 A. 498 B. 499 C. 500 D. 501 9. 已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为ABCDEFGH ，该完全二叉 树的后序遍历序列为________。 一、选择题 1. 算法的计算量的大小称为计算的（ B ）。【邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【理工大学 1999 一、1（2分）【交通科技大学 1996 一、1（ 4分）】 4．一个算法应该是（ B ）。【大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（ D ）【理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ C ）【理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D.栈 绪论 一、选择题 1.算法的计算量的大小称为计算的( 复杂性 A.效率 B. 2. 算法的时间复杂度取决于 A.问题的规模 3. 计算机算法指的是( (1) A .计算方法 法 (2) A .可执行性、 B. 1), B. 4. 5. )。【北京邮电大学 2000二、3 (20/8 C. 现实性 D. 难度 、1 (2 分)] ( )【中科院计算所1998 待处理数据的初态 它必须具备( 排序方法 C. A 和 B 这三个特性。 C. 解决问题的步骤序列 D. 分) 】 调度方 可移植性、可扩充性 B. 可执行性、确定性、有穷性 易读性、稳定性、安全性 、1 ( 4 C.确定性、有穷性、稳定性 【南京理工大学 1999 一、1 (2分) 一个 算法应该是( )。【中山大学 A .程序 B .问题求解步骤的描述 下面关于算法说法错误的是( A. 算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D.以上几个都是错误的 下面说法错误的是( )【南京理工大学 2000 一、2 (1.5分)] (1 ) (2) (3) (4) A . D. 【武汉交通科技大学 1996 1998 二、1 (2 分)】 C .要满足五个基本特性 D . A 和C. 分) 】 )【南京理工大学2000 一、1 (1.5分)】 )【南京理工大学 2000 算法原地工作的含义是指不需要任何额外的辅助空间 在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度 O(2n )的算法 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 同一个算法，实现语言的级别越高，执行效率就越低 (1) B.(1),(2) 7.从逻辑上可以把数据结构分为 A.动态结构、静态结构 C.线性结构、非线性结构 &以下与数据的存储结构无关的术语是 A.循环队列 B. 链表 9.以下数据结构中，哪一个是线性结构 A.广义表 B. 二叉树 10 .以下那一个术语与数据的存储结构无关？ A.栈 B. 11 .在下面的程序段中， 分)] 6. C.(1) ,(4) D.(3) ( )两大类。【武汉交通科技大学 1996 一、4 ( 2分)] B .顺序结构、链式结构 .初等结构、构造型结构 )。【北方交通大学 2000二、1 (2分)] 哈希表 D. 栈 )?【北方交通大学 2001 一、1 (2分)] 稀疏矩阵 ) 线索树 C. C. 哈希表 C. 对 x 的赋值语句的频度为( D.串 【北方交通大学2001 一、2 (2分)】 D. 双向链表 )【北京工商大学 2001 一、10 (3 FOR i:=1 FOR j:=1 x:=x+1; A. O(2 n) TO TO DO DO .0(n) 2 C . O(n) D .O(log 2n ) 12.程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO 青岛大学2017年硕士研究生入学考试试题科目代码：910科目名称：数据结构（共5页） 请考生写明题号，将答案全部答在答题纸上，答在试卷上无效 一、单项选择题（本大题共10道小题，每小题2分，共20分） 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．以上都不对 7．由带权为{8，2，5，7}的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。 A．23B．37C．46D43 8．若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。 A．非连通B．连通C．强连通D．有向 9．适用于折半查找的表的存储方式及元素排列要求为（）。 A．链接方式存储，元素无序B．链接方式存储，元素有序 C．顺序方式存储，元素无序D．顺序方式存储，元素有序 10．对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。 第1页，共5页 第9章集合 部分答案解释如下。 4．不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。 8．哈希表的结点中可以包括指针，指向其元素。 11．单链表不能使用折半查找方法。 20．按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于该结点的关键字，则会插入到该结点的左侧，成为其左孩子。这种插入就不是插入到叶子下面。 21．从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。 23．某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后继。 24．在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。26．只有被删除结点是叶子结点时命题才正确。 三．填空题 1．n n+1 2．4 3．6,9,11,12 4．5 5．26（第4层是叶子结点，每个结点两个关键字） 6．1,3,6,8,11,13,16,19 7．5,96 8．m-1,「m/2?-1 9．2,4,3 10．(1)哈希函数(2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀(6)简单 11．AVL树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。 12．小于等于表长的最大素数或不包含小于20的质因子的合数 13．16 14．?㏒n」+1 2 15．(1)45 (2)45 (3)46（块内顺序查找） 16．k(k+1)/2 17．30，31.5（块内顺序查找） 18．(1)顺序存储或链式存储 (2)顺序存储且有序 (3)块内顺序存储，块间有序 (4) 散列存储 第一章绪论 一、填空题（每空1分，共33分） 1. 一个计算机系统包括硬件系统和软件系统两大部分。 2. 一台计算机中全部程序的集合，称为这台计算机的软件资源/（系统）。 3. 计算机软件可以分为系统软件和应用软件两大类。科学计算程序包属于应用软 件，诊断程序属于系统软件（工具）。 4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是汇编语言。 5. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 6. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 7. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 8. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 9. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 10．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 11. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 12. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 13．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 14. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 15. 一个算法的效率可分为时间效率和空间效率。 16. 任何一个C程序都由一个主函数和若干个被调用的其它函数组成。 二、单项选择题（每小题1分，共15分） （ B ） 1. 通常所说的主机是指∶ A) CPU B) CPU和内存C) CPU、内存与外存D) CPU、内存与硬盘 （ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶ A) ACSII码B) BCD码C)二进制D)十六进制 （ D ）3. 软件与程序的区别是∶ A)程序价格便宜、软件价格昂贵； B)程序是用户自己编写的，而软件是由厂家提供的； C) 程序是用高级语言编写的，而软件是由机器语言编写的； D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。 （ C ）4. 所谓“裸机”是指∶ A) 单片机B)单板机C) 不装备任何软件的计算机D) 只装备操作系统的计算机 （ D ）5. 应用软件是指∶ A)所有能够使用的软件B) 能被各应用单位共同使用的某种软件 C)所有微机上都应使用的基本软件D) 专门为某一应用目的而编制的软件 一、选择题 1.算法的计算量的大小称为计算的（B）。【北京邮电大学2000二、3（20/8分）】 A．效率B.复杂性C.现实性D.难度 2.算法的时间复杂度取决于（C）【中科院计算所1998 二、1（2分）】 A．问题的规模B.待处理数据的初态和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法 (2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 【南京理工大学1999一、1（2分）【武汉交通科技大学1996一、1（4分）】 4．一个算法应该是（B）。【中山大学1998二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5.下面关于算法说法错误的是（D）【南京理工大学2000一、1（分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的 6.下面说法错误的是（C）【南京理工大学2000一、2（分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执 行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1)B.(1),(2)C.(1),(4)D.(3) 7．从逻辑上可以把数据结构分为（C）两大类。【武汉交通科技大学1996一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（D）。【北方交通大学2000二、1（2分）】 A．循环队列B.链表C.哈希表D.栈 9．以下数据结构中，哪一个是线性结构（D）【北方交通大学2001一、1（2分）】 A．广义表B.二叉树C.稀疏矩阵D.串 10．以下那一个术语与数据的存储结构无关（A）【北方交通大学2001一、2（2分）】 数据结构考研真题及其 答案 -CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN 一、选择题 1. 算法的计算量的大小称为计算的（ B ）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（C ）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分）【武汉交通科技大学1996 一、1（ 4分）】 4．一个算法应该是（ B ）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ C ）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 2 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【武汉交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D.栈 9．以下数据结构中，哪一个是线性结构（ D ） 【北方交通大学 2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关（ A ）【北方交通大学 2001 一、2（2分）】 3 数据结构精选考研试题 [注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释一、回答下列问题：[20分] 1、算法的定义和性质2、为什么说数组与广义表是线性表的推广？ 3、什么是结构化程序设计？ 4、哈希方法的基本思想 5、给出一不稳定排序方法名称与实例二、构造结果：[24分] 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。for i:=1 to n do for j:=1 to I do for k:=1 to j do x:=x+1 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．假设用于通讯的电文仅8个字母组成，字母在电文中出现的频率 分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为，H(x)=[i/2] ，其中i为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。构造有7个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。三、写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。[15分] 四、编写一非递归算法，对一棵二叉排序树实现中序遍历。[15分] 五、编写程序，完成下列功能：[15分] 1．读入整数序列，以整数0作为序列的结束标志，建立一个单链表。2．实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，可使用临时工作单元。例：输入序列为：1，8，4，3，0 六、 [ 注] ：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注 释一、回答下列问题： [20 分 ] 1、算法的定义和性质 2、为什么说数组与广义表是线性表的推广？ 3、什么是结构化程序设计？ 4、哈希方法的基本思想 5、给出一不稳定排序方法名称与实例 二、构造结果：[24分] （1）确定 x:=x+1 语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do for j:=1 to I do for k:=1 to j do x:=x+1 （2）画出对长度为 8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均 查找长度。 （3）已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列． （4）假设用于通讯的电文仅由8 个字母组成，字母在电文中出现的频率分别为{2 ， 3， 5，7， 11， 4， 13， 15} ，试为这 8 个字母设计哈夫曼编码． （ 5）在地址空间为0~15 的散列区中，对以下关键字序列构G 造哈希表，关键字序列为（ Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec ）， H(x)=[i/2]，其中i 为关键字中第一 字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找 成功的平均查找长度。 （6）构造有 7 个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。 三、写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。 [15 分 ] [15 分 ] 四、编写一非递归算法，对一棵二叉排序树实现中序遍历。 五、编写程序，完成下列功能：[15 分 ] 1．读入整数序列，以整数0 作为序列的结束标志（0 不作为序列元素），建立一个单链表。2．实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点， 可使用临时工作单元。 例：输入序列为：1， 8， 4，3， 0 第三章栈和队列答案 部分答案解释如下。 1、尾递归的消除就不需用栈 2、这个数是前序序列为1,2,3,…,n，所能得到的不相似的二叉树的数目。 三、填空题 1、操作受限（或限定仅在表尾进行插入和删除操作）后进先出 2、栈 3、3 1 2 4、23 100CH 5、0 n+1 top[1]+1=top[2] 6、两栈顶指针值相减的绝对值为1（或两栈顶指针相邻）。 7、(1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻（即值之差的绝对值为1） 8、链式存储结构 9、S×SS×S×× 10、data[++top]=x； 11、23.12.3*2-4/34.5*7/++108.9/+（注：表达式中的点(.)表示将数隔开，如23.12.3 是三个数） 12、假溢出时大量移动数据元素。 13、(M+1) MOD N (M+1)% N； 14、队列 15、先进先出 16、先进先出 17、s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s；r=s； 18、牺牲一个存储单元设标记 19、（TAIL+1）MOD M=FRONT (数组下标0到M-1，若一定使用1到M，则取模为0者，值改取M 20、sq.front=(sq.front+1)%(M+1)；return(sq.data(sq.front))； (sq.rear+1)%(M+1)==sq.front； 21、栈 22、（rear-front+m）% m； 23、（R-P+N）% N； 24、（1）a[i]或a[1] （2）a[i] （3）pop（s）或s[1]； 25、（1）PUSH（OPTR，w）（2）POP（OPTR）（3）PUSH（OPND，operate（a，theta，b）） 26、（1）T>0（2）i 《数据结构》考研真题及解答 目录 2009 年试题 (1) 填空题 (1) 解答题 (2) 2010 年试题 (2) 填空题 (2) 解答题 (4) 2011 年试题 (4) 填空题 (4) 解答题 (5) 2012 年试题 (6) 填空题 (6) 解答题 (7) 2013 年试题 (8) 填空题 (8) 解答题 (9) 2014 年试题 (10) 填空题 (10) 解答题 (11) 2015 年试题 (12) 填空题 (12) 解答题 (14) 2009 年试题 填空题 1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要 输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 A.栈 B.队列 C.树 D.图 2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。若每个元素出栈后立即 进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是 A．1 B.2 C.3 D.4 3.给定二叉树图所示。设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。 若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是 A．LRN B.NRL C.RLN D.RNL 4.下列二叉排序树中，满足平衡二叉树定义的是 5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数 最多是 A．39 B.52 C.111 D.119 6.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原 来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系 A.只有II B.I 和II C.I 和III D.I、II 和III 7.下列关于无向连通图特性的叙述中，正确的是 I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1 试卷代号：1252 中央广播电视大学2012-2013学年度第二学期“开放本科”期末考试 一、单项选择题（每小题2分，共30分） 1．在C语言中，顺序存储长度为3的字符串，需要占用( )个字节。 A．4 B．3 C．6 D．12 2。串函数StrCat(a，b)的功能是进行串( )。 A．比较 B．复制 C．赋值 D．连接 3．-棵有n个结点采用链式存储的二叉树中，共有( )个指针域为空。 A．n+l B．n C．n-l D．n-2 4．设一棵哈夫曼树共有n个非叶结点，则该树有( )个叶结点。A．n B．n+l C．n-l D．2n 5．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执 行( )。 A. x=top->data;top=top->next =top->data C. top= top->next; x=top->data =top->next;x=data 6．一棵完全二叉树共有5层，且第5层上有六个结点，该树共有( )个结点。 A．30 B．20 C．21 D．23 7．在一个无向图中，所有顶点的度数之和等于边数的( )倍。^A．O上；．B．3 C． D．2 8．已知如图1所示的一个图，若从顶点V，出发，按深度优先搜索法进行遍历，则可能得 到的一种顶点序列为( )。 9．已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到 的一种顶点序列为( )。A. abcedf B. abcefd C. aebcfd D. acfdeb 10.对二叉排序树进行( )遍历，可以使遍历所得到的序列是有序序列。 A．按层次 B．后序 C．中序 D．前序 11．在有序表(2，4，7，14，34，43，47，64，75，80，90，97，120)中，用折半查找法查找值80 时，经( )次比较后查找成功。 A．4 B．2 C．3 D．5 12．有一个长度为9的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的 平均比较次数为( )。 A．25/10 B．25/9 C．20/9 D．17/9 13.排序算法中，从未排序序列中依次取出元素与已排序序殂（初始为空）中的元素进行 比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是( )。 A．冒泡 B。直接插入 C．折半插入 D．选择排序 14．一组记录的关键字序列为(46，79，56，38，40，84)，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为( )。 A．40,38946,79956,84 B．40,38946,56,79,84 C．40，38,46,84,56,79 D．38，40,46956,79,84 15.排序方法中，从尚未排序序列中挑选元素，并将其依次放人已排序序列（初始为空）的 一端的方法，称为( )排序。 A．归并 B．插入 C．快速 D．选择 1．A 2．D3．A 4．B 6．C 7．D 8．A 9．B 11．B 2．B 13．C 14．B 二、填空题（每小题2分。共20分） 、选择题 注：子串的定义是：串中任意个连续的字符组成的子序列， 并规定空串是任意串的子串， 任意串是其自身的子串。若字符串长度为 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.0（m+n ） 6. 01122312 7 . 01010421 8 . （1）模式匹配 （2） 模式串 9. （1）其数据元素都是字符（2）顺序存储 ⑶ 和链式存储 ⑷ 串的长度相等且两串中对应位置 的字 符也相等 10. 两串的长度相等且两串中对应位置的字符也相等。 12 . *s++=*t++ 或(*s++=*t++ ) != ‘ \0 ' 13. (1) char s[] ⑵ 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 ，即程序中第二 个W HILE 循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的 WHILE 循环, 是当s 中某字符（s :i ］）与t 中某字符（t :j ］）相等时，求出局部公共子串。若该子串长 度大于已 求出的最长公共子串（初始为0） ，则最长公共子串的长度要修改。 程序(a ): (1) (i+k<=s.len ) AND(j+k<=t.len) AND(s[i+k]=t[j+k]) 的长度内，对应字符相等，则指针 k 后移（加1）。 和t 对 应字符不等时置标记退出 在t 串中，从第j+k 字符再与s ［i ］比较 串取下一字符 串指针i 后移（加1）。 程序(b )： (1) i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k] // (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） ch 仁ch2 //读入分隔符&后，判ch1是否等于ch2，得出真假结论。 (3) answer : =true (4) answer : =false (5) read (ch ) 第四章串 11.' xyxyxywwy // 如果在s 和t (2) con:= false //s (3) j:=j+k // (4) j:=j+1 //t 所有注释同上（a ） 2017年全国硕士研究生统一入学考试自命题试题（B卷） ******************************************************************************************** 学科、专业名称：计算机科学与技术、软件工程 研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203， 软件工程083500，计算机技术(专业学位) 085211，软件工程(专业学位) 085212 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一、单项选择题(每题2分，共30分) 1. 一个队列的入列序列是1,2,3,4, 则队列的输出序列是（）。 A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1 2. 循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear, 则当前队列中 的元素个数是( )。 A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 3. 平衡二叉树的平均查找长度是( )。 A. O(n2） B. O(nlog2n） C. O(n） D. O(log2n） 4. 设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点 数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。 A. N1-1 B. N2-1 C. N2+N3 D. N1+N3 5. 计算机内部数据处理的基本单元是（）。 A. 数据 B. 数据元素 C. 数据项 D. 数据库 6. 设按照从上到下、从左到右的顺序从1开始对完全二叉树的结点进行顺序编号，则编号为i 结点的左孩子结点的编号为（）。 A. 2i+1 B. 2i C. i/2 D. 2i-1 7. 设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。 A. 第i行非0元素的个数之和 B. 第i列非0元素的个数之和 C. 第i行0元素的个数之和 D. 第i列0元素的个数之和 8. 设一组初始记录关键字序列为(16, 25,12, 30,47,11, 23,36, 9,18,31)，则以增量d=5的一趟希尔 排序结束后的结果为（）。 A. 11, 23,12, 9, 18,16, 25,36,30, 47, 31 B. 11, 23,12, 9, 16, 18, 25,36, 47, 30, 31 C. 16, 23,12, 9, 11,18, 25,36,30, 47, 31 C. 9, 11,12, 16, 18, 23, 25,30, 36, 47, 31 9. 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。 A. n B. n-1 C. m D. m-1 10. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有 （）个空指针域。 A. 2m-1 B. 2m C. 2m+1 D. 4m 11. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H(K)=K %9作 为散列函数，则散列地址为1的元素有（）个。 A．1 B．2 C．3 D．4 考试科目：数据结构共5页，第1 页 数据结构考研真题及其答案 一、选择题 1. 算法的计算量的大小称为计算的（ B ）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（C ）【中科院计算所 1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】 4．一个算法应该是（ B ）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错 误的 6. 下面说法错误的是（ C ）【南京 理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需 要任何额外的辅助空间 （2）在相同的规模n下，复杂度 O(n)的算法在时间上总是优于 复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别 越高，执行效率就越低4 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为 （ C ）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构 B．顺计算机考研数据结构真题汇总
计算机数据结构考研真题及其答案
北航 1999-2002 程序设计与数据结构考研试题
大数据结构考研真题及其问题详解
数据结构考研试题精选及答案第1章绪论
2017年青岛大学考研试题910数据结构
数据结构考研试题精选及答案第9章 查找答案
考研资料数据结构试题汇总
数据结构考研真题及其答案
数据结构考研真题及其答案
数据结构精选考研试题
数据结构考研试题.doc
数据结构考研试题精选及答案第三章 栈和队列答案
历年《数据结构》考研真题及解答
数据结构历年试题及答案
算法与数据结构考研试题精析(第二版)第4章串答案
暨南大学考研真题数据结构
数据结构考研真题
- 数据结构考研真题
- 大数据结构考研真题及其问题详解
- 数据结构考研真题及其答案
- 计算机数据结构考研真题及其答案
- 数据结构考研真题及解答
- 数据结构考研真题和答案
- 数据结构考研真题及其答案
- 数据结构考研试题.doc
- 数据结构历年试题及答案
- 算法与数据结构考研试题精析(第二版)第4章串答案
- 计算机数据结构考研真题及其答案
- 数据结构考研真题及解答
- 数据结构考研试题精选及答案第三章 栈和队列答案
- 数据结构历年试题及答案
- 数据结构考研真题与其答案
- 2009-2010计算机考研真题及答案——数据结构部分
- 2008年江苏大学数据结构考研试题
- 数据结构考研真题及其答案
- 【考研题库】2020年中国海洋大学数据结构考研复试核心题库[应用题+算法设计题]
- 计算机考研数据结构真题汇总