北京邮电大学
2019年硕士研究生招生考试试题
考试科目：软件工程专业综合
请考生注意：
（1）所有答案（包括选择题和填空题）一律写在答题纸上，否则不计成绩。 （2）允许使用计算器。
（3）本考题包括数据结构，操作系统，数据库三个科目。其中数据结构为必选部分。操作系统，数据库为二选一，考生只需选择其中一个科目答题即可。考生需在答题纸上标明选答科目的名称。 必选科目数据结构部分（90分） 一、选择题（每小题2分，共20分）
1.考虑下面程序段：
void power（int m，int n） { //前提：n>=0
int result=1； while（n>1）
if（n为偶数）{m=m*m；n=n/2；}
else{result=result*m；n=n-1；}
return result；
}
则调用power（m，n）的时间复杂度是：
A.O（n） B.O（n logn） C.o（logn） D.O（n2）
2.下面是对有序数组进行二分查找程序的教学版。
bool search（T a[ ]，int n，T key）
{ //n：数组a的长度。前提：n>=0， T是某种数据类型
if（n<=0）return false； int mid=n/2；
if（a[mid]==key） return true；
if（almid] 考虑函数调用search（a，n，key）；下面三个命题中哪些是正确的？ return search（a+mid+1，n-mid-1，key）； （1）成功查找的键值比较次数的时间复杂度是O（logn）。 （2）不成功查找的键值比较次数的时间复杂度是O（logn）。 （3）若键值x，y均不在数组中，则查找他们所执行的键值比较次数相 A.（1），（2），（3）全部正确 B.仅（1），（2）正确 C.仅（1），（3）正确 D.仅（2），（3）正确 3.n个结点的简单有向图最多有多少条弧边？ 4.以下哪个函数是O（n3）？ A.n3log（n）+n3 B.n3+log（n） C.3n D.n3log（n3） 5.将键值个数分别为m，n的两个有序表归并为一个大的有序表最多需要多少次键值比较？ A.min（m，n） B.m+n-1 C.max（m，n） D.m+n 6.假设队列是用循环单链表存储，队列的长度是n，头指针是front，尾指针rear 指向队列的最后一个元素所在的结点，指针x指向的结点包含的元素需要入队，需要下面的那个选项的入队操作序列？ A.front=x；front=front->next； B.x->next=front->next；front=x； C.rear->next=x；rear=x； D.rear->next=x；x->next=null；rear=x； 7.具有n（n>0）个结点的完全二叉树的高度为（假设只有一个结点的二叉树的高度为0）。 8.使用哈希函数 h（key）=key mod 5将键值为18，13，19，15，8，依次添加到编号为0，1，2，3，4的桶中。使用封闭式线性再探测处理冲突，即如果发生冲突，则依次探测： （H（key）+1）mod 5，（H（key）+2）mod 5，（H（key）+3）mod 5.. 等位置。则哈希表中2号桶中的值为： A.18 B.19 C.8 D.空 9.设有向图G的邻接矩阵为A。即A[j，k]=1表示图中含有从j到k的弧边否则A[j，k]为零。令B是矩阵A的平方，即B=A*A。并且B[j，k]=3。则下面的说法哪个最准确？ A.从j到k是连通的。 B.从j到k有3条路径。 C.从j到k的长度为2的路径有3条。 D.从j到k的长度为3的路径有2条。 10.考察下面的C++语言打印二又树结点的函数。 struct Node { char data； Node*lc；/指向左子 Node*rc；//指向右子 }; void print_tree（Node*root） if（root==0）return； std::cout <
北京邮电大学2019年软件工程专业综合考试真题807
