西安交通大学17年9月课程考试《数据结构》作业考核试题 .pdfVIP

西安交通大学17年9月课程考试《数据结构》作业考核试题

一、单选题

1、B2、A3、D4、A5、D

一、单选题

一、单选题（共30道试题，共60分。）V1.（）二叉排序树可以得到一个从小到大的

有序序列。

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历

正确答案：B

2.下列程序段的时间复杂度为（）。i=0，s=0；while(sn){s=s+i；i++；}

A.O(n)

B.O(n)

C.O(n)

D.O(n)

正确答案：A

3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，

则执行出队操作后其头指针front值为（）

A.front=front+1

B.front=(front+1)%(m-1)

C.front=(front-1)%m

D.front=(front+1)%m

正确答案：D

4.程序段s=i=0；do{i=i+1；s=s+i；}while(i=n)；的时间复杂度为（）。

A.O(n)

B.O(nlog2n)

C.O(n)

D.O(n/2)

正确答案：A

5.设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵

哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。

A.129

B.219

C.189

D.229

正确答案：D

6.设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。

A.2n

B.n

C.n/2

D.n(n-1)

正确答案：B

7.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。

A.head==0

B.head-next==0

C.head-next==head

D.head!=0

正确答案：A

8.栈和队列的共同特点是（）。

A.只允许在端点处插入和删除元素

B.都是先进后出

C.都是先进先出

D.没有共同点

正确答案：A

9.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为

A.O（1）

B.O（n）

C.O（1og2n）

D.O（n2)

正确答案：C

10.设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储

到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]

的地址之差为（）。

A.10

B.19

C.28

D.55

正确答案：B

11.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得

到序列为（）

A.BADC

B.BCDA

C.CDAB

D.CBDA

正确答案：A

12.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度

数为1的结点数有2个，那么度数为0的结点数有（）个。

A.4

B.5

C.6

D.7

正确答案：C

13.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。

A.top=top+1;

B.top=top-1;

C.top-next=top;

D.top=top-next;

正确答案：D

14.二叉排序树中左子树上所有结点的值均（）根结点的值。

A.

B.

C.=

D.!=

正确答案：A

15.若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下

的时间复杂度是（）

A.O（1）

B.O（n）

C.O（n^2)

D.O（n^3）

正确答案：C

16.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。

A.n-i

B.n+l-i

C.n-1-i

D.i

正确答案：A

17.设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，

则该三叉链权中有（）个度数为0的结点。

A.5

B.6

C.7

D.8

正确答案：C

18.设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),

则利用二分法查找关键字90需要比较的关键字个数为（）。

A.1

B.2