数据结构试题试卷三含答案 .pdfVIP

数据结构试题试卷三含答案

模拟试题三

模拟试题三

一、选择题（30分）

1.下面程序的时间复杂度为()。

for(i=O;im;i++)p=

for(j=0;jt;j++)p=

c[i][j]=O;

for(i=O;im;i++)p=

for(j=O;jt;j++)p=

for(k=O;kSPAN

c[i][j]=c[i][j]+a[i][k]b[k][j];

A)O(mnt)B)0(m+n+t)C)O(m+nt)D)O(mt+n)

2.从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移

动()个元素。

A)n-iB)n-i+lC)n-i-lD)i

3.串的逻辑结构与()的逻辑结构不同。

A)线性表B)栈C)队列D)树

4.二叉树第i(i≥1)层最多有()个结点。

A)2iB)2iC)2i-lD)2i-1

5.设单链表中指针p指向结点A，若要删除A之后的结点（若存

在），则修改指针的操作为()。

A)p-next=p-next-nextB)p=p-next

C)p=p-next-nextD)p-next=p

6.设一数列的输入顺序为l，2，3，4，5，6，通过栈操作不可能

排成的输出序列为()。

A)3,2,5,6,4,lB)l,5,4,6,2,3

C)2,4,3,5,l,6D)4,5,3,6,2,l

7。设字符串Sl=‘ABCDEFG’，S2=‘PQRST’，则运算

S=Concat(Sub(S1，2，Length(S

2))Sub(S1，Length(S2)，2))后结果为()。

A)‘BCQRB)‘BCDEF

C)‘BCDEFGD)‘BCDEFEF

8.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主

存储，all为第1个元素，其存储地址为1，每个元素占用1个地址空

间，则a85的地址为()

A)13B)33C)18D)40

9.如果结点A有3个兄弟，且B为A的双亲，则B的度为()。

A)3B)4C)5D)1

10.线索化二叉树中某结点D，没有左孩子的主要条件是()。

A)D-Lchild=NULLB)D-ltag=l

C)D-Rchild=NULLD)D-ltag=0

11.采用顺序查找法查找长度为n的线性表，则查找每个元素的平

均比较次数为()。

A)nB)n/2C)(n+l)/2D)(n-l)/2

12.已知一个有序表为(13，18，24，35，47，50，62，83，90，

115，134)，当二分查找值为90的元素时，需()次比较可查找成功。

A)lB)2C)3D)4

13.在顺序存储的线性表R[029]上进行顺序查找的平均查找长度为

(①);进行二分查找的平均查找长度为(②)，进行分块查找（设分为5块）

的平均查始长度为(⑨)。

①A)15B)15.5C)16D)20

②A)4B)62/15C)64/15D)25/6

⑧A)6B)11C)5D)6.5

14.在所有排序方法中，关键字的比较次数与记录的初始排列无关

的是()。

A)Shell排序B）冒泡排序

C)直接插入排序D）直接选择排序

15.已知8个元素(34，76，45，18，26，54，92，65)，按照依

次插入结点的方法生成一棵二叉排序树，该树的深度为()。

A)lB)2C)3D)4

二、填空题（15分）

1.二维数组A[10][5]采用以行序为主方式存储，每个元素占4个存

储单元。并且A[5][3]的存储地址是1000，则A[8][2]的地址是

__________。