📄 st07.htm
字号:
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><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'><spanstyle='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><spanstyle='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:宋体'>一、选择题<spanlang=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><spanstyle='mso-spacerun:yes'> </span></span>）。【北方交通大学<spanlang=EN-US> 2001 </span>一、<span lang=EN-US>24 </span>（<span lang=EN-US>2</span>分）】<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:17.9pt;mso-char-indent-count:1.71'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．由顶点和相邻顶点序偶构成的边所形成的序列<spanlang=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'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>C</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．由不同边所形成的序列<span lang=EN-US><spanstyle='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><spanstyle='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'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>n-1<spanstyle='mso-spacerun:yes'> </span>B</span>．<spanlang=EN-US>n(n-1)/2<spanstyle='mso-spacerun:yes'> </span>C</span>．<spanlang=EN-US> n(n+1)/2<spanstyle='mso-spacerun:yes'> </span>D</span>．<spanlang=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'><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>【清华大学<span lang=EN-US> 1998 </span>一、<spanlang=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>分）】<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><spanstyle='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>分）】<spanlang=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>个顶点的连通无向图，其边的个数至少为（<spanlang=EN-US><span style='mso-spacerun:yes'> </span></span>）。</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>【</span><spanstyle='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>分<spanlang=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'><spanlang=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<spanstyle='mso-spacerun:yes'> </span>B</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>．</span><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;mso-font-kerning:0pt'>n<spanstyle='mso-spacerun:yes'> </span>C</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>．</span><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;mso-font-kerning:0pt'>n+1<spanstyle='mso-spacerun:yes'> </span>D</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>．</span><spanlang=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><spanstyle='mso-spacerun:yes'> </span></span>）条边。【北京航空航天大学<spanlang=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'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>n-l<spanstyle='mso-spacerun:yes'> </span>B</span>．<span lang=EN-US>n<spanstyle='mso-spacerun:yes'> </span>C</span>．<span lang=EN-US>n+l<spanstyle='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span>D</span>．<spanlang=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]><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><spanstyle='mso-element:field-begin'></span><spanstyle='mso-spacerun:yes'> </span>= 2 \* CHINESENUM3 <spanstyle='mso-element:field-separator'></span></span><![endif]--><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体;mso-no-proof:yes'>二</span><!--[if supportFields]><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><spanstyle='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>分）】<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>n*n<spanstyle='mso-spacerun:yes'> </span></span>Ｂ．<spanlang=EN-US>n</span>（<span lang=EN-US>n</span>＋１）<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>C</span>．<spanlang=EN-US>n</span>／<span lang=EN-US>2<spanstyle='mso-spacerun:yes'> </span>D</span>．<span lang=EN-US>n*</span>（<span lang=EN-US>n</span>－<spanlang=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><spanstyle='mso-spacerun:yes'> </span></span>）个连通分量，最多有（<spanlang=EN-US><span style='mso-spacerun:yes'> </span></span>）个连通分量。<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:17.9pt;mso-char-indent-count:1.71'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>0<spanstyle='mso-spacerun:yes'> </span>B</span>．<span lang=EN-US>1<spanstyle='mso-spacerun:yes'> </span>C</span>．<span lang=EN-US>n-1<spanstyle='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'><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>【北京邮电大学<span lang=EN-US> 2000 </span>二、<spanlang=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><spanstyle='mso-spacerun:yes'> </span></span>）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（<spanlang=EN-US><span style='mso-spacerun:yes'> </span></span>）倍。【哈尔滨工业大学<spanlang=EN-US> 2001 </span>二、<span lang=EN-US>3 </span>（<span lang=EN-US>2</span>分）】<b><spanlang=EN-US><o:p></o:p></span></b></span></p><p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>1/2<spanstyle='mso-spacerun:yes'> </span>B</span>．<span lang=EN-US>2<spanstyle='mso-spacerun:yes'> </span>C</span>．<span lang=EN-US>1<spanstyle='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>）<spanlang=EN-US>/A</span>），至少需要顶点的数目为<span lang=EN-US>(<spanstyle='mso-spacerun:yes'> </span>)</span>。【中山大学<span lang=EN-US>1999</span></span><!--[if supportFields]><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><spanstyle='mso-element:field-begin'></span> = 1 \* CHINESENUM3 <spanstyle='mso-element:field-separator'></span></span><![endif]--><span⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -