📄 st07.htm
字号:
mso-level-tab-stop:36.5pt;
mso-level-number-position:left;
margin-left:36.5pt;
text-indent:-21.0pt;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
-->
</style>
<!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:普通表格;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
</style>
<![endif]--><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="6146"/>
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1,2,3,4"/>
<o:regrouptable v:ext="edit">
<o:entry new="1" old="0"/>
<o:entry new="2" old="0"/>
<o:entry new="3" old="0"/>
<o:entry new="4" old="0"/>
</o:regrouptable>
</o:shapelayout></xml><![endif]-->
</head>
<body lang=ZH-CN style='tab-interval:21.0pt;text-justify-trim:punctuation'>
<div class=Section1 style='layout-grid:15.35pt 0pt;mso-layout-grid-char-alt:
-98'>
<p class=MsoNormal align=center style='text-align:center'><b><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'> </span></span></b><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-bidi-font-weight:bold'>第七章<span lang=EN-US><span
style='mso-spacerun:yes'> </span></span>图<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal><b><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>一、选择题<span
lang=EN-US><o:p></o:p></span></span></b></p>
<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>1</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．图中有关路径的定义是（<span lang=EN-US><span
style='mso-spacerun:yes'> </span></span>）。【北方交通大学<span
lang=EN-US> 2001 </span>一、<span lang=EN-US>24 </span>（<span lang=EN-US>2</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:17.9pt;mso-char-indent-count:1.71'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．由顶点和相邻顶点序偶构成的边所形成的序列<span
lang=EN-US><span style='mso-spacerun:yes'>
</span>B</span>．由不同顶点所形成的序列<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:17.9pt;mso-char-indent-count:1.71'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>C</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．由不同边所形成的序列<span lang=EN-US><span
style='mso-spacerun:yes'>
</span>D</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:宋体'>2</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．设无向图的顶点个数为<span lang=EN-US>n</span>，则该图最多有（<span lang=EN-US><span
style='mso-spacerun:yes'> </span></span>）条边。<b><span lang=EN-US><o:p></o:p></span></b></span></p>
<p class=MsoNormal style='text-indent:17.9pt;mso-char-indent-count:1.71'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>n-1<span
style='mso-spacerun:yes'> </span>B</span>．<span
lang=EN-US>n(n-1)/2<span
style='mso-spacerun:yes'> </span>C</span>．<span
lang=EN-US> n(n+1)/2<span
style='mso-spacerun:yes'> </span>D</span>．<span
lang=EN-US>0<span style='mso-spacerun:yes'>
</span>E</span>．<span lang=EN-US>n<sup>2</sup><b><o:p></o:p></b></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>【清华大学<span lang=EN-US> 1998 </span>一、<span
lang=EN-US>5 </span>（<span lang=EN-US>2</span>分）】【西安电子科技大<span lang=EN-US> 1998
</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 style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>【北京航空航天大学<span lang=EN-US>
1999 </span>一、<span lang=EN-US>7 </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:宋体'>3</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'>一个<span lang=EN-US>n</span>个顶点的连通无向图，其边的个数至少为（<span
lang=EN-US><span style='mso-spacerun:yes'> </span></span>）。</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>【</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;mso-font-kerning:
0pt'>浙江大学<span lang=EN-US> 1999 </span>四、<span lang=EN-US>4 (4</span>分<span
lang=EN-US>)</span>】<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'>A</span><span 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'>n-1<span
style='mso-spacerun:yes'>
</span>B</span><span 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'>n<span
style='mso-spacerun:yes'>
</span>C</span><span 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'>n+1<span
style='mso-spacerun:yes'>
</span>D</span><span 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'>nlogn</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>；<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:宋体'>4</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．要连通具有<span lang=EN-US>n</span>个顶点的有向图，至少需要（<span lang=EN-US><span
style='mso-spacerun:yes'> </span></span>）条边。【北京航空航天大学<span
lang=EN-US> 2000 </span>一、<span lang=EN-US>6(2</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>n-l<span
style='mso-spacerun:yes'>
</span>B</span>．<span lang=EN-US>n<span
style='mso-spacerun:yes'>
</span>C</span>．<span lang=EN-US>n+l<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>D</span>．<span
lang=EN-US>2n<o:p></o:p></span></span></p>
<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>5</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．<span lang=EN-US>n</span>个结点的完全有向图含有边的数目（ ）。【中山大学<span lang=EN-US> 1998 </span></span><!--[if supportFields]><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-element:field-begin'></span><span
style='mso-spacerun:yes'> </span>= 2 \* CHINESENUM3 <span
style='mso-element:field-separator'></span></span><![endif]--><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-no-proof:yes'>二</span><!--[if supportFields]><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-element:field-end'></span></span><![endif]--><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>、<span lang=EN-US>9 </span>（<span lang=EN-US>2</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>n*n<span
style='mso-spacerun:yes'> </span></span>Ｂ．<span
lang=EN-US>n</span>（<span lang=EN-US>n</span>＋１）<span lang=EN-US><span
style='mso-spacerun:yes'> </span>C</span>．<span
lang=EN-US>n</span>／<span lang=EN-US>2<span
style='mso-spacerun:yes'>
</span>D</span>．<span lang=EN-US>n*</span>（<span lang=EN-US>n</span>－<span
lang=EN-US>l</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:宋体'>6</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．一个有<span lang=EN-US>n</span>个结点的图，最少有（<span lang=EN-US><span
style='mso-spacerun:yes'> </span></span>）个连通分量，最多有（<span
lang=EN-US><span style='mso-spacerun:yes'> </span></span>）个连通分量。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:17.9pt;mso-char-indent-count:1.71'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>0<span
style='mso-spacerun:yes'>
</span>B</span>．<span lang=EN-US>1<span
style='mso-spacerun:yes'>
</span>C</span>．<span lang=EN-US>n-1<span
style='mso-spacerun:yes'>
</span>D</span>．<span lang=EN-US>n<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>【北京邮电大学<span lang=EN-US> 2000 </span>二、<span
lang=EN-US>5 </span>（<span lang=EN-US>20/8</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:宋体'>7</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．在一个无向图中，所有顶点的度数之和等于所有边数（<span lang=EN-US><span
style='mso-spacerun:yes'> </span></span>）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（<span
lang=EN-US><span style='mso-spacerun:yes'> </span></span>）倍。【哈尔滨工业大学<span
lang=EN-US> 2001 </span>二、<span lang=EN-US>3 </span>（<span lang=EN-US>2</span>分）】<b><span
lang=EN-US><o:p></o:p></span></b></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>1/2<span
style='mso-spacerun:yes'>
</span>B</span>．<span lang=EN-US>2<span
style='mso-spacerun:yes'>
</span>C</span>．<span lang=EN-US>1<span
style='mso-spacerun:yes'>
</span>D</span>．<span lang=EN-US>4<o:p></o:p></span></span></p>
<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>8</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．用有向无环图描述表达式<span lang=EN-US>(A+B)*</span>（（<span lang=EN-US>A+B</span>）<span
lang=EN-US>/A</span>），至少需要顶点的数目为<span lang=EN-US>(<span
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -