3986.net
小网站 大容量 大智慧
当前位置:首页 >> 数学 >>

数据结构模拟试卷二及答案1

模拟试卷二

一、

单选题(每题 2 分,共 20 分)

1. 在一个带有附加表头结点的单链表 HL 中,若要向表头插入一个由指针 p 指向的结

点,则执行(B )。

A. HL=p; p->next=HL;

B. p->next=HL->next; HL->next=p;

C. p->next=HL; p=HL;

D. p->next=HL; HL=p;

2. 若顺序存储的循环队列的 QueueMaxSize=n,则该队列最多可存储(A B )个元素.

A. n

B.n-1

C. n+1

D.不确定

3. 下述哪一条是顺序存储方式的优点?(C A )

A.存储密度大

B.插入和删除运算方便

C. 获取符合某种条件的元素方便

D.查找运算速度快

4. 设有一个二维数组 A[m][n],假设 A[0][0]存放位置在 600(10),A[3][3]存放位置在 678(10),每个元素占一个空间,问 A[2][3](10)存放在什么位置?(脚注(10)表示用 10 进 制表示,m>3) BD

A.658

B.648

C.633

D.653 3m+3=78 m=25

5. 下列关于二叉树遍历的叙述中,正确的是( DA ) 。

A. 若一个树叶是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序遍历

最后一个结点

B.若一个点是某二叉树的前序遍历最后一个结点,则它必是该二叉树的中序遍历的最

后一个结点

C.若一个结点是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序最后

一个结点

D.若一个树叶是某二叉树的前序最后一个结点,则它必是该二叉树的中序遍历最后一

个结点

6. k 层二叉树的结点总数最多为( A ).

A.2k-1

B.2K+1

C.2K-1

D. 2k-1

7. 对线性表进行二分法查找,其前提条件是( ).

A.线性表以链接方式存储,并且按关键码值排好序

B.线性表以顺序方式存储,并且按关键码值的检索频率排好序

C. 线性表以顺序方式存储,并且按关键码值排好序

D. 线性表以链接方式存储,并且按关键码值的检索频率排好序

8. 对 n 个记录进行堆排序,所需要的辅助存储空间为

A. O(1og2n)

B. O(n)

C. O(1)

D. O(n2)

9. 对于线性表(7,34,77,25,64,49,20,14)进行散列存储时,若选用 H(K)

=K %7 作为散列函数,则散列地址为 0 的元素有( )个,

A.1

B.2

C.3

D.4

10.下列关于数据结构的叙述中,正确的是( D ).

A. 数组是不同类型值的集合

B. 递归算法的程序结构比迭代算法的程序结构更为精炼

C. 树是一种线性结构

D. 用一维数组存储一棵完全二叉树是有效的存储方法

二、

填空题(每空 1 分,共 26 分)

1. 数据的逻辑结构被分为_________、________、__________和___________四种。

2. 一个算法的时间复杂度为(3n3+2000nlog2n+90)/n2,其数量级表示为________。 3. 对于一个长度为 n 的单链存储的队列,在表头插入元素的时间复杂度为_________,在

表尾插入元素的时间复杂度为____________。

4. 假定一棵树的广义表表示为 A(D(E,G),H(I,J)),则树中所含的结点数为__________

个,树的深度为___________,树的度为_________。

5. 后缀算式 79 2 30 + - 4 2 / *的值为__________。中缀算式(3+X*Y)-2Y/3 对

应的后缀算式为_______________________________。

6. 在一棵高度为 5 的理想平衡树中,最少含有_______个结点,最多含有_______个结点。

7. 在树中,一个结点的直接后继结点称为该结点的________。一个结点的直接前趋结点称

为该结点的________。

8. 在一个具有 10 个顶点的无向完全图中,包含有________条边,在一个具有 n 个顶点的

有向完全图中,包含有________条边。

9. 假定一个线性表为(12,17,74,5,63,49,82,36),若按 Key % 4 条件进行划分,使得同一余数

的 元 素 成 为 一 个 子 表 , 则 得 到 的 四 个 子 表 分 别 为 ____________________________ 、

___________________、_______________________和__________________________。

10. 对一棵 B_树进行删除元素的过程中,若最终引起树根结点的合并时,会使新树的高度

比原树的高度___________。

11. 在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为________,整个堆排序

过程的时间复杂度为________。

12. 在线性表的散列存储中,装填因子?又称为装填系数,若用 m 表示散列表的长度,n 表

示待散列存储的元素的个数,则?等于________。

三、

运算题(每题 6 分,共 24 分)

1. 在如下数组 A 中链接存储了一个线性表,表头指针存放在 A [ 0].next,试写出该线性表。

A0 12 34 56 7

data

60 50 78 90 34

40

next 4 0 5 2 7 1

3

2. 已知一棵二叉树的前序遍历的结果是 ABKCDFGHIJ, 中序遍历的结果是 KBCDAFHIGJ, 试画出这棵二叉树。
3. 已知一个图的顶点集 V 为: V={1,2,3,4,5,6,7}; 其共有 10 条边。该图用如下边集数组存储:

起点 1 2 2 5 5 2 2 6 1 3

终点 6 4 5 4 7 6 7 7 7 5

权 1122233457

试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。

4. 画出向小根堆中加入数据 4, 2, 5, 8, 3, 6, 10, 1 时,每加入一个数据后堆的变化。

四、

阅读算法(每题 7 分,共 14 分)

1. 在下面的每个程序段中,假定线性表 La 的类型为 List,元素类型 ElemType 为 int,

并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表 La。

(1)InitList(La);

Int a[]={100,26,57,34,79};

For (i=0;i<5;i++)

Insert(La,a[i]);

TraverseList(La);

(2)DeleteFront(La);

InsertRear(La, DeleteFront(La));

TraverseList(La);

(3)ClearList(La);

For (i=0;i<5;i++)

InsertFront(La,a[i]);

TraverseList(La);

2. 现面算法的功能是什么?

void ABC(BTNode * BT)

{

if BT {

cout<<BT->data<<' ';

ABC(BT->left);

ABC(BT->right);

}

}

五、

算法填空(共 8 分)

二分查找的递归算法。

Int Binsch(ElemType A[],int low,int high,KeyType K)

{

if ___________________{

int mid=(low+high)/2;

if (_____________________) return mid; //查找成功,返回元素的下标

else if (K<A[mid].key)

return Binsch(A,low,mid-1,K);

//在左子表上继续查找

else return_____________________________; //在右子表上继续查找

}

else ________________;

//查找失败,返回-1

}

六、

编写算法(共 8 分)

HL 为单链表的表头指针,试写出在该单链表中查找具有给定的元素 item 的算法。

bool Find(LNode* HL, ElemType &item)

模拟试卷二参考答案

一、

单选题(每题 2 分,共 20 分)

1.B 2.B 3.A 4.D 5.A 6.A 7.C 8.C 9.D 10.D

二、

填空题(每空 1 分,共 26 分)

1. 集合结构 线性结构 树结构 图结构

2. O(n)

3. O(1) O(1)

4. 7 3 2

5. 94

3 XY*+2Y*3/-

6. 16 31

7. 孩子(或子)结点 双亲(或父)结点

8. 45 n(n-1)

9. (12,36) (17,5,49) (74,82) (63)

10. 减少 1(或减少)

11. O(log2n) O(nlog2n)

12. n/m

三、

运算题(每题 6 分,共 24 分)

1. 线性表为:(90,40,78,50,34,60)

2. 当前序序列为 ABKCDFGHIJ,中序序列为 KBCDAFHIGJ 时,逐步形成二叉树的过程

如下图 4 所示:

KBCD A

A

A

FHIGJ

B

F

B

F

K CD HIGJ K C

G

图 4 D HI J 3. 用克鲁斯卡尔算法得到的最小生成树为:
(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7 4. 见图 5。

A

B

F

KC

G

D H IJ

4

4

2

2

2

2

2

4

4

5

4

5

4

5

8

83

2

2

2

1

3

5

3

5

3

5

6

2

5

图5

四、

阅读算法(每题 7 分,共 14 分)

1. (1) La=(26,34,57,79,100)

(2)La=(57,79,100,34)

(3)La=(79,34,57,26,100)

2. 前序遍历链式存储的二叉树。

五、

算法填空(每空 2 分,共 8 分)

(low<=high) K==A[mid].key

Binsch(A,mid+1,hight,K)

六、

编写算法(8 分)

bool Find(LNode* HL, ElemType &item)

{

LNode* p=HL;

while p

if (p->data==item){

return true;

}

else p=p->next;

return false;

}

模拟试卷二

return -1

七、

单选题(每题 2 分,共 20 分)

11. 在一个带有附加表头结点的单链表 HL 中,若要向表头插入一个由指针 p 指向的结

点,则执行( )。

A. HL=p; p->next=HL;

B. p->next=HL->next; HL->next=p;

C. p->next=HL; p=HL;

D. p->next=HL; HL=p;

12.若顺序存储的循环队列的 QueueMaxSize=n,则该队列最多可存储( )个元素.

A. n

B.n-1

C. n+1

D.不确定

13.下述哪一条是顺序存储方式的优点?( )

A.存储密度大

B.插入和删除运算方便

C. 获取符合某种条件的元素方便

D.查找运算速度快

14. 设有一个二维数组 A[m][n],假设 A[0][0]存放位置在 600(10),A[3][3]存放位置在 678(10),每个元素占一个空间,问 A[2][3](10)存放在什么位置?(脚注(10)表示用 10 进 制表示,m>3)

A.658

B.648

C.633

D.653

15.下列关于二叉树遍历的叙述中,正确的是( ) 。

A. 若一个树叶是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序遍历

最后一个结点

B.若一个点是某二叉树的前序遍历最后一个结点,则它必是该二叉树的中序遍历的最

后一个结点

C.若一个结点是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序最后

一个结点

D.若一个树叶是某二叉树的前序最后一个结点,则它必是该二叉树的中序遍历最后一

个结点

16.k 层二叉树的结点总数最多为( ).

A.2k-1

B.2K+1

C.2K-1

D. 2k-1

17.对线性表进行二分法查找,其前提条件是( ).

E.线性表以链接方式存储,并且按关键码值排好序

F.线性表以顺序方式存储,并且按关键码值的检索频率排好序

G. 线性表以顺序方式存储,并且按关键码值排好序

H. 线性表以链接方式存储,并且按关键码值的检索频率排好序

18.对 n 个记录进行堆排序,所需要的辅助存储空间为

A. O(1og2n)

B. O(n)

C. O(1)

D. O(n2)

19.对于线性表(7,34,77,25,64,49,20,14)进行散列存储时,若选用 H(K)

=K %7 作为散列函数,则散列地址为 0 的元素有( )个,

A.1

B.2

C.3

D.4

20.下列关于数据结构的叙述中,正确的是( ).

E. 数组是不同类型值的集合

F. 递归算法的程序结构比迭代算法的程序结构更为精炼

G. 树是一种线性结构

H. 用一维数组存储一棵完全二叉树是有效的存储方法

八、

填空题(每空 1 分,共 26 分)

13. 数据的逻辑结构被分为_________、________、__________和___________四种。

14. 一个算法的时间复杂度为(3n3+2000nlog2n+90)/n2,其数量级表示为________。 15. 对于一个长度为 n 的单链存储的队列,在表头插入元素的时间复杂度为_________,在

表尾插入元素的时间复杂度为____________。

16. 假定一棵树的广义表表示为 A(D(E,G),H(I,J)),则树中所含的结点数为__________

个,树的深度为___________,树的度为_________。

17. 后缀算式 79 2 30 + - 4 2 / *的值为__________。中缀算式(3+X*Y)-2Y/3 对

应的后缀算式为_______________________________。

18. 在一棵高度为 5 的理想平衡树中,最少含有_______个结点,最多含有_______个结点。

19. 在树中,一个结点的直接后继结点称为该结点的________。一个结点的直接前趋结点称

为该结点的________。

20. 在一个具有 10 个顶点的无向完全图中,包含有________条边,在一个具有 n 个顶点的

有向完全图中,包含有________条边。

21. 假定一个线性表为(12,17,74,5,63,49,82,36),若按 Key % 4 条件进行划分,使得同一余数

的 元 素 成 为 一 个 子 表 , 则 得 到 的 四 个 子 表 分 别 为 ____________________________ 、

___________________、_______________________和__________________________。

22. 对一棵 B_树进行删除元素的过程中,若最终引起树根结点的合并时,会使新树的高度

比原树的高度___________。

23. 在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为________,整个堆排序

过程的时间复杂度为________。

24. 在线性表的散列存储中,装填因子?又称为装填系数,若用 m 表示散列表的长度,n 表

示待散列存储的元素的个数,则?等于________。

九、

运算题(每题 6 分,共 24 分)

5. 在如下数组 A 中链接存储了一个线性表,表头指针存放在 A [ 0].next,试写出该线性表。

A0 12 34 56 7

data

60 50 78 90 34

40

next 4 0 5 2 7 1

3

6. 已知一棵二叉树的前序遍历的结果是 ABKCDFGHIJ, 中序遍历的结果是 KBCDAFHIGJ, 试画出这棵二叉树。
7. 已知一个图的顶点集 V 为: V={1,2,3,4,5,6,7}; 其共有 10 条边。该图用如下边集数组存储:

起点 1 2 2 5 5 2 2 6 1 3

终点 6 4 5 4 7 6 7 7 7 5

权 1122233457

试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。

8. 画出向小根堆中加入数据 4, 2, 5, 8, 3, 6, 10, 1 时,每加入一个数据后堆的变化。

十、

阅读算法(每题 7 分,共 14 分)

3. 在下面的每个程序段中,假定线性表 La 的类型为 List,元素类型 ElemType 为 int,

并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表 La。

(4)InitList(La);

Int a[]={100,26,57,34,79};

For (i=0;i<5;i++)

Insert(La,a[i]);

TraverseList(La);

(5)DeleteFront(La);

InsertRear(La, DeleteFront(La));

TraverseList(La);

(6)ClearList(La);

For (i=0;i<5;i++)

InsertFront(La,a[i]);

TraverseList(La);

4. 现面算法的功能是什么?

void ABC(BTNode * BT)

{

if BT {

cout<<BT->data<<' ';

ABC(BT->left);

ABC(BT->right);

}

}

十一、 算法填空(共 8 分)

二分查找的递归算法。

Int Binsch(ElemType A[],int low,int high,KeyType K)

{

if ___________________{

int mid=(low+high)/2;

if (_____________________) return mid; //查找成功,返回元素的下标

else if (K<A[mid].key)

return Binsch(A,low,mid-1,K);

//在左子表上继续查找

else return_____________________________; //在右子表上继续查找

}

else ________________;

//查找失败,返回-1

}

十二、 编写算法(共 8 分)

HL 为单链表的表头指针,试写出在该单链表中查找具有给定的元素 item 的算法。

bool Find(LNode* HL, ElemType &item)

模拟试卷二参考答案

七、

单选题(每题 2 分,共 20 分)

1.B 2.B 3.A 4.D 5.A 6.A 7.C 8.C 9.D

八、

填空题(每空 1 分,共 26 分)

13. 集合结构 线性结构 树结构 图结构

14. O(n)

15. O(1) O(1)

16. 7 3 2

17. 94

3 XY*+2Y*3/-

18. 16 31

10.D

19. 孩子(或子)结点 双亲(或父)结点

20. 45 n(n-1)

21. (12,36) (17,5,49) (74,82) (63)

22. 减少 1(或减少)

23. O(log2n) O(nlog2n)

24. n/m

九、

运算题(每题 6 分,共 24 分)

5. 线性表为:(90,40,78,50,34,60)

6. 当前序序列为 ABKCDFGHIJ,中序序列为 KBCDAFHIGJ 时,逐步形成二叉树的过程

如下图 4 所示:

KBCD A

A

A

FHIGJ

B

F

B

F

K CD HIGJ K C

G

图 4 D HI J 7. 用克鲁斯卡尔算法得到的最小生成树为:
(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7 8. 见图 5。

A

B

F

KC

G

D H IJ

4

4

2

2

2

2

2

4

4

5

4

5

4

5

8

83

2

2

2

1

3

5

3

5

3

5

2

5

84

8 46

8 图4 5 6 10

34

十、

阅读算法(每题 7 分,共 14 分)

8

3. (1) La=(26,34,57,79,100)

(2)La=(57,79,100,34)

(3)La=(79,34,57,26,100)

4. 前序遍历链式存储的二叉树。

十一、 算法填空(每空 2 分,共 8 分)

(low<=high) K==A[mid].key

Binsch(A,mid+1,hight,K)

十二、 编写算法(8 分)

bool Find(LNode* HL, ElemType &item)

{

LNode* p=HL;

while p

if (p->data==item){

return true;

}

else p=p->next;

return false;

}

6 10
return -1


xaairways.com tuchengsm.com gaizaoahe.com
网站首页 | 网站地图 | 学霸百科 | 新词新语 | xaairways.com | tuchengsm.com | gaizaoahe.com
3986 3986.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com