2024年4月12日发(作者：2019大庆二模数学试卷)

得分

评卷人

一. 单项选择（每小题3分，总共15分）

( A ) 1、在如下的有向图中，从V

1

到V

4

长度为3 的道路有（ A ）条。

A． 1； B．2； C．3； D．4 。

( B ) 2、假设S、T是两个有限集合。那么下面正确的是：

A. |S∪T| = |S| + |T| B. |S∪T| = |S| + |T| - |S∩T|

C. |S×T|= |S| × |T| - |S∩T| D. |S-T|= |S| - |T|

( B )3、假定递归算法把一个规模为n的问题分解为a个子问题，每个

子问题规模为n/b. 再假定把子问题的解组合成原来问题的解的算法处理

中，需要总量为g(n)的运算数. 用f(n)表示求解规模为n的问题所需的运

算数，则得出运算数f(n)的递推关系为：

A．f(n) = b f(n/a) + g(n)； B．f(n) = af(n/b) + g(n)；

C．f(n) = f(n/b) +ag(n)； D．f(n) = ag(n/b) + f(n)；

( D ) 4、如果两个图H与G同构，且结点数大于1，则下面不正确的是：

A．如果H有一个子图是非平面图，则G是非平面图

B．如果H是连通图，则G没有孤立点。

C．H是偶图则G也是偶图，反之也成立

D．f是H的结点集到G的结点集的双射，则H的任一结点h的度数

等于G中结点f(h)的度数。

1

( D ) 5、下面说法不正确的是：

A：不同算法求出的两个不同结点的最短通路的长度是一样的。

B: 不同算法求得的两个不同结点的最短通路可能不一样。

C: 连通有权图的任两个不同结点的最短通路一定是存在的。

D：最短通路未必就是简单路。

得分

评卷人

二. 填空（每小题3分，总共15分）

1、连通无向图有欧拉开路（非回路）的充要条件是

恰好有两个度为奇数的结点

2、 8位座机号码，如果不能以0开头，而且不容许数字全部相同，有多

少个可以选择的号码 9*10^7 - 9 ;

3、从n种不同的元素中，取r（r

n+r-1个取r个的组合数 减去 n个取r个的组合数 ;

4、将5个相同的球放到3个不同的盒子中, 方案数为 21 （7个里面取

5个的组合数） .

.

5、 n（n>1）个结点的简单连通无向图，如果不是树，结点总度数至少是

多少 2n .

得分 评卷人

2


更多推荐

结点,问题,算法,通路,规模,大庆