st04.htm

1800道数据结构题和答案

</span>B</span>．<span lang=EN-US>37<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>C</span>．<span lang=EN-US>36<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>D</span>．<span lang=EN-US>9<o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>9</span><span
style='font-family:宋体'>．设<span lang=EN-US>S</span>为一个长度为<span lang=EN-US>n</span>的字符串，其中的字符各不相同，则<span
lang=EN-US>S</span>中的互异的非平凡子串（非空且不同于<span lang=EN-US>S</span>本身）的个数为（<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span>）。【中科院计算所<span
lang=EN-US> 1997 </span>】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US style='font-family:宋体'>A</span><span style='font-family:宋体'>．<span
lang=EN-US>2n-1<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>B</span>．<span
lang=EN-US>n2<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>C</span>．<span lang=EN-US>(n2/2)+(n/2)<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>D</span>．<span lang=EN-US>(n2/2)+(n/2)-1<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>E. (n2/2)-(n/2)-1<span
style='mso-spacerun:yes'>&nbsp; </span>F.</span>其他情况<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>10</span><span
style='font-family:宋体'>．串的长度是指（<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span>）【北京工商大学<span
lang=EN-US> 2001<span style='mso-spacerun:yes'>&nbsp; </span></span></span><!--[if supportFields]><span
lang=EN-US style='font-family:宋体'><span style='mso-element:field-begin'></span><span
style='mso-spacerun:yes'>&nbsp;</span>= 1 \* CHINESENUM3 <span
style='mso-element:field-separator'></span></span><![endif]--><span
style='font-family:宋体;mso-no-proof:yes'>一</span><!--[if supportFields]><span
lang=EN-US style='font-family:宋体'><span style='mso-element:field-end'></span></span><![endif]--><span
style='font-family:宋体'>、<span lang=EN-US>6 </span>（<span lang=EN-US>3</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US style='font-family:宋体'>A</span><span style='font-family:宋体'>．串中所含不同字母的个数<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>B</span>．串中所含字符的个数<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US style='font-family:宋体'>C</span><span style='font-family:宋体'>．串中所含不同字符的个数<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>D</span>．串中所含非空格字符的个数<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><b><span style='font-family:宋体'>二、判断题<span lang=EN-US><o:p></o:p></span></span></b></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>1</span><span
style='font-family:宋体'>．<span lang=EN-US>KMP</span>算法的特点是在模式匹配时指示主串的指针不会变小。（<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span>）【北京邮电大学<span
lang=EN-US> 2002 </span>一、<span lang=EN-US>4 </span>（<span lang=EN-US>1</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>2</span><span
style='font-family:宋体'>．设模式串的长度为<span lang=EN-US>m,</span>目标串的长度为<span
lang=EN-US>n</span>，当<span lang=EN-US>n</span>≈<span lang=EN-US>m</span>且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span>）【长沙铁道学院<span
lang=EN-US> 1998 </span>一、<span lang=EN-US>1 (1</span>分<span lang=EN-US>)</span>】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>3</span><span
style='font-family:宋体'>．串是一种数据对象和操作都特殊的线性表。（<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span>）【大连海事大学<span
lang=EN-US> 2001 1</span>、<span lang=EN-US>L<span
style='mso-spacerun:yes'>&nbsp; </span>(1</span>分<span lang=EN-US>)</span>】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
lang=EN-US style='font-family:宋体'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><b><span style='font-family:宋体'>二、填空题<span lang=EN-US><o:p></o:p></span></span></b></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>1</span><span
style='font-family:宋体'>．空格串是指<u><span lang=EN-US>__(1)__</span></u>，其长度等于<u><span
lang=EN-US>___(2)__</span></u>。 【西安电子科技大学<span lang=EN-US> 2001</span>软件 一、<span
lang=EN-US>4</span>（<span lang=EN-US>2</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>2</span><span
style='font-family:宋体'>．组成串的数据元素只能是</span><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>________</span><span style='font-family:宋体'>。 【中山大学<span
lang=EN-US> 1998<span style='mso-spacerun:yes'>&nbsp; </span></span></span><!--[if supportFields]><span
lang=EN-US style='font-family:宋体'><span style='mso-element:field-begin'></span><span
style='mso-spacerun:yes'>&nbsp;</span>= 1 \* CHINESENUM3 <span
style='mso-element:field-separator'></span></span><![endif]--><span
style='font-family:宋体;mso-no-proof:yes'>一</span><!--[if supportFields]><span
lang=EN-US style='font-family:宋体'><span style='mso-element:field-end'></span></span><![endif]--><span
style='font-family:宋体'>、<span lang=EN-US>5 </span>（<span lang=EN-US>1</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>3</span><span
style='font-family:宋体'>．一个字符串中</span><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>________</span><span style='font-family:宋体'>称为该串的子串 。 【华中理工大学<span
lang=EN-US> 2000 </span>一、<span lang=EN-US>3</span>（<span lang=EN-US>1</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>4</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;mso-font-kerning:
0pt'>．</span><span lang=EN-US style='font-family:宋体'>INDEX</span><span
style='font-family:宋体'>（‘<span lang=EN-US>DATASTRUCTURE</span>’， ‘<span
lang=EN-US>STR</span>’）<span lang=EN-US>=</span></span><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>________</span><span
style='font-family:宋体'>。【福州大学<span lang=EN-US> 1998 </span>二、<span lang=EN-US>4
(2</span>分<span lang=EN-US>)</span>】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>5</span><span
style='font-family:宋体'>．设正文串长度为<span lang=EN-US>n</span>，模式串长度为<span
lang=EN-US>m</span>，则串匹配的<span lang=EN-US>KMP</span>算法的时间复杂度为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>________</span><span
style='font-family:宋体'>。<span lang=EN-US> <o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
style='font-family:宋体'>【重庆大学<span lang=EN-US> 2000 </span></span><!--[if supportFields]><span
lang=EN-US style='font-family:宋体'><span style='mso-element:field-begin'></span><span
style='mso-spacerun:yes'>&nbsp;</span>= 1 \* CHINESENUM3 <span
style='mso-element:field-separator'></span></span><![endif]--><span
style='font-family:宋体;mso-no-proof:yes'>一</span><!--[if supportFields]><span
lang=EN-US style='font-family:宋体'><span style='mso-element:field-end'></span></span><![endif]--><span
style='font-family:宋体'>、<span lang=EN-US>4</span>】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>6</span><span
style='font-family:宋体'>．模式串<span lang=EN-US>P=</span>‘<span lang=EN-US>abaabcac</span>’的<span
lang=EN-US>next</span>函数值序列为</span><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>________</span><span style='font-family:宋体'>。【西安电子科技大学<span
lang=EN-US> 2001</span>软件 一、<span lang=EN-US>6</span>（<span lang=EN-US>2</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>7</span><span
style='font-family:宋体'>．字符串’<span lang=EN-US>ababaaab</span>’的<span lang=EN-US>nextval</span>函数值为<span
lang=EN-US>________</span>。 【北京邮电大学<span lang=EN-US> 2001 </span>二、<span
lang=EN-US>4 </span>（<span lang=EN-US>2</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>8</span><span
style='font-family:宋体'>．设<span lang=EN-US>T</span>和<span lang=EN-US>P</span>是两个给定的串，在<span
lang=EN-US>T</span>中寻找等于<span lang=EN-US>P</span>的子串的过程称为<u><span lang=EN-US>__(1)_</span></u><span
lang=EN-US>_</span>，又称<span lang=EN-US>P</span>为<u><span lang=EN-US>__(2)__</span></u>。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
style='font-family:宋体'>【西安电子科技大学<span lang=EN-US> 1998 </span>二、<span
lang=EN-US>5 </span>（<span lang=EN-US>16/6</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>9</span><span
style='font-family:宋体'>．串是一种特殊的线性表，其特殊性表现在</span><u><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>__(1)__</span></u><span
style='font-family:宋体'>；串的两种最基本的存储方式是</span><u><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>__(2)_</span></u><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>_</span><span
style='font-family:宋体'>、</span><u><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>__(3)_</span></u><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>_</span><span style='font-family:宋体'>；两个串相等的充分必要条件是</span><u><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>__(4)__</span></u><span
style='font-family:宋体'>。 【中国矿业大学<span lang=EN-US> 2000 </span>一、<span
lang=EN-US>3 </span>（<span lang=EN-US>4</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>10</span><span
style='font-family:宋体'>．</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>两个字符串相等的充分必要条件是<span
lang=EN-US>_______</span>。 </span><span style='font-family:宋体'>【西安电子科技大学<span
lang=EN-US> 1999</span>软件 一、<span lang=EN-US>1 </span>（<span lang=EN-US>2</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>11</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;mso-font-kerning:
0pt'>．</span><span style='font-family:宋体'>知<span lang=EN-US>U=</span>‘<span
lang=EN-US>xyxyxyxxyxy</span>’；<span lang=EN-US>t=</span>‘<span lang=EN-US>xxy</span>’；<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US style='font-family:宋体'>ASSIGN</span><span style='font-family:宋体'>（<span
lang=EN-US>S</span>，<span lang=EN-US>U</span>）；<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US style='font-family:宋体'>ASSIGN</span><span style='font-family:宋体'>（<span
lang=EN-US>V</span>，<span lang=EN-US>SUBSTR</span>（<span lang=EN-US>S</span>，<span
lang=EN-US>INDEX</span>（<span lang=EN-US>s</span>，<span lang=EN-US>t</span>），<span
lang=EN-US>LEN</span>（<span lang=EN-US>t</span>）<span lang=EN-US>+1</span>））；<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US style='font-family:宋体'>ASSIGN</span><span style='font-family:宋体'>（<span
lang=EN-US>m</span>，‘<span lang=EN-US>ww</span>’）<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
style='font-family:宋体'>求<span lang=EN-US>REPLACE</span>（<span lang=EN-US>S</span>，<span
lang=EN-US>V</span>，<span lang=EN-US>m</span>）<span lang=EN-US>= </span></span><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>________</span><span
style='font-family:宋体'>。 【东北大学<span lang=EN-US> 1997 </span>一、<span lang=EN-US>1<span
style='mso-spacerun:yes'>&nbsp; </span>(5</span>分<span lang=EN-US>)</span>】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left;mso-layout-grid-align:
none;text-autospace:none'><span lang=EN-US style='font-family:宋体'>12</span><span
style='font-family:宋体'>．</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>实现字符串拷贝的函数<span lang=EN-US>
strcpy</span>为：<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:19.5pt;
mso-char-indent-count:1.71;mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'><span style='mso-spacerun:yes'>&nbsp;</span>void
strcpy(char *s , char *t) /*copy t to s*/<o:p></o:p></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:19.5pt;
mso-char-indent-count:1.71;mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'>{ while<span style='mso-spacerun:yes'>&nbsp; </span>(</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>________</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'>)<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'>}<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span><span
style='font-family:宋体'>【</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>浙江大学</span><span
style='font-family:宋体'> </span><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>1999</span><span lang=EN-US
style='font-family:宋体'> </span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>一、<span lang=EN-US>5</span></span><span
lang=EN-US style='font-family:宋体'> </span><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体;color:black;mso-font-kerning:0pt'>(3</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;mso-font-kerning:
0pt'>分<span lang=EN-US>)</span>】</span><span lang=EN-US style='font-family:
宋体'><o:p></o:p></span></p>