计算机专业(基础综合)-试卷15.pdfVIP

计算机专业（基础综合）-试卷15

(总分：98.00，做题时间：90分钟)

一、单项选择题(总题数：41，分数：82.00)

1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

__________________________________________________________________________________________

2.在具有n个结点的顺序表，算法的时间复杂度是O(1)的操作是()。

A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)√

B.在第i个结点后插入一个新结点(1≤i≤n)

C.删除第i个结点(1≤i≤n)

D.将n个结点从大到小排序

顺序表是随机存取结构，选项A中实质是查找第i个结点和第i一1个结点，因此时间复杂度为O(1)；选

项B和C插入和删除都需要移动元素，时间复杂度为O(n)；选项D是排序问题，时间复杂度是O(n)～O(n2)。

3.使用双链表存储线性表，其优点是()。I提高查找速度Ⅱ更方便数据的插入和删除Ⅲ节约存储空间Ⅳ

很快回收存储空间

A.I、Ⅱ

B.I、Ⅳ

C.仅Ⅱ√

D.Ⅱ、Ⅲ、Ⅳ

在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然

不能节省存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以其

插入和删除操作更加方便。

4.若进栈序列为a，b，c，则通过出栈操作可能得到a，b，c的不同排列个数为()。

A.4

B.5√

C.6

D.7

若进栈序列为a，b，c，可以考虑所有进栈出栈情况，则可能得到a，b，c的出栈序列是abc，acb，bac，

bca，cba。[归纳总结]对于n个不同元素进栈，出栈序列的个数为：。[解题技巧]当n一3时，

出栈序列的个数为，即可快速得出正确答案。

5.若对n阶对称矩阵A[1．．n，1．．n]以行序为主序方式下将其下三角的元素(包括主对角线上的所有元

素)依次存放于一维数组B[1．．n(n＋1)／2]中，则在B中确定a(i

ij

A.i(i－1)／2＋j

B.j(j－1)／2＋i√

C.i(i＋1)／2＋j

D.j(j＋1)／2＋i

将对称矩阵A中的下三角的元素存放于B数组中，若求a(ij)的位置k的关系，答案为A，即i(i－1)

ij

／2＋j。但是，本题求a(iij(iij(iij，这就需要将备选答案A中i(i一1)／2＋j的i与j互换，

ij

因此正确答案为B，即j(j一1)／2＋i。

6.在线索化二叉树中，t所指结点没有左子树的充要条件是()。

A.t－left＝NULL

B.t－ltag＝1√

C.t－ltag＝1且t－left＝NULL

D.以上都不对

线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为1。

7.若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵()。

A.第i行中值为1的元素个数

B.所有值为1的元素个数

C.第i行及第