西安交通大学24秋“计算机科学与技术”《数据结构》考试历年常考点试题选编附答案_1.docxVIP

西安交通大学24秋“计算机科学与技术”《数据结构》考试历年常考点试题选编附答案

第1卷

一.综合考核(共15题)

1.数组A[0..4，-1..-3，5..7]中含有元素的个数()。

A.55

B.45

C.36

D.16

2.二维数组和多维数组均不是特殊的线性结构。()

A.错误

B.正确

3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为()。

A.O(1)

B.O(n)

C.O(m)

D.O(m+n)

4.入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。()

A.错误

B.正确

5.下列程序段的时间复杂度为()。I=0，s=0;while(s＜n){s=s+i;i++;}

A.O(n1/2)

B.O(n1/3)

C.O(n)

D.O(n2)

6.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为()。

A.O(n)

B.O(nlog2n)

C.O(1)

D.O(n2)

7.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是()。

A.直接选择排序

B.直接插入排序

C.快速排序

D.起泡排序

8.对于线性表(7，34，55，25，64，46，20，10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有()个。

A.1

B.2

C.3

D.4

9.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。

A.24

B.71

C.48

D.53

10.如果要求频繁的对线性表进行插入和删除操作，则线性表应该采用()存储结构。

A.散列

B.顺序

C.链式

D.任意

11.栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。()

A.错误

B.正确

12.程序段如下：s=i=0;do{i=i+1;s=s+i;}while(i=n);其时间复杂度为()。

A.O(n)

B.O(nlog2n)

C.O(n2)

D.O(n3/2)

13.设某无向图有n个顶点，则该无向图的邻接表中有()个表头结点。

A.2n

B.n

C.n/2

D.n(n-1)

14.每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里，这种存储结构称为()结构。

A.顺序结构

B.链式结构

C.索引结构

D.散列结构

15.设串S的长度为n，则S的子串个数为n(n+1)/2。()

A.错误

B.正确

第1卷参考答案

一.综合考核

1.参考答案：B

2.参考答案：A

3.参考答案：C

4.参考答案：B

5.参考答案：A

6.参考答案：C

7.参考答案：C

8.参考答案：D

9.参考答案：B

10.参考答案：C

11.参考答案：B

12.参考答案：A

13.参考答案：B

14.参考答案：A

15.参考答案：A