计算机专业基础综合（数据结构）模拟试卷31

计算机专业基础综合（数据结构）模拟试卷31

单选题

1.数据结构是具有( )的数据元素的集合。(B)

A. 性质相同

B. 特定关系

C. 相同运算

D. 数据项

解析：数据结构由数据元素集合和数据元素关系两部分组成。

2.求解Hanoi问题时，若初始有5个圆盘，则移动圆盘的次数是( )。(C)

A. 7

B. 15

C. 31

D. 5

解析：求解Hanoi问题时，对于n个圆盘，有T(n)=2ⁿ-1。

3.线性表的静态链表存储结构与顺序存储结构相比优点是( )。(C)

A. 所有的操作算法实现简单

B. 便于随机存取

C. 便于插入与删除

D. 便于利用零散的存储器空间

解析：基础题。静态链表具有链表的插入和删除方便的优点，也不需要移动较多的元素。

4.在一个单链表HL中，若要向表头插入一个由指针P指向的结点，则执行( )。(B)

A. HL=P：P-＞next=HL；

B. P-＞next=HL；HL=P；

C. P-＞next=HL；P=HL；

D. P-＞next=HL-＞next；HL-＞next=P；

解析：根据插入运算的定义，需要修改头指针HL，令其指向结点P，同时结点P的指针域应指向原来的头结点。修改了头指针HL会影响后面操作，所以必须先将P的指针域指向头结点(P-＞next=HL)，再修改HL(即HL=P)。

5.循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为( )。(A)

A. (rear-front+m)MOD m

B. real-front+1

C. real-front-1

D. rear-front

解析：循环队列中rear和front分别指向队尾和队头，当rear＞front时，元素的个数为rear-front，根据循环队列的性质，当插入点已经插入到数组A的最后位置且有新的元素插入时，会继续从数组的开始位置执行插入操作，此时rear＜front，数组元素的个数为。rear—front+m。综合两种情况，循环队列中当前元素的个数计算方法为：(rear—front+m)MOD m。

6.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a_1，1为第一元素，其存储地址为1，每个元素占一个地址空间，则a_8，5的地址是( )。(B)

A. 13

B. 33

C. 18

D. 40

解析：数组下标从1开始，只存储其下三角形元素，在a_8，5的前面有7行，第1行有1个元素，第2行有2个元素，…，第7行有7个元素，这7行共有(1+7)×7／2=28个元素，在第8行中，a_8，5的前面有4个元素，所以a_8，5前有28+4=32个元素，其地址为33。

7.设高度为H的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为( )。(B)

A. 2×H

B. 2×H-1

C. 2×H+1

D. H+1

解析：结点最少的情况如下图所示：

8.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )(C)

A. 所有的结点均无左孩子

B. 所有的结点均无右孩子

C. 只有一个叶子结点

D. 是任意一棵二叉树

解析：先序遍历的次序为根一左一右，而后序遍历的次序为左一右一根，，先序遍历与后序遍历相对次序可以相反的部分为根-左(对后序的左一根)，或者是根一右(对后序的右一根)，所以满足条件的二叉树只有一个叶子结点。

9.若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有( )棵树。(C)

A. k

B. n

C. n-k

D. n+k

解析：一个具有n个结点的树有n-1条边，结点数比边数多1，则若一个森林中有m棵树，其结点数比边数多 m。反过来，森林中树的个数等于结点数减去边数。

10.以下关于二叉排序树的说法正确的是( )

I、在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小

Ⅱ、每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树

Ⅲ、在二叉排序树中，新插入的关键字总是处于最底层

Ⅳ、在二叉排序树中，新结点总是作为叶子结点来插入的

V、二叉排序树的查找效率和二叉排序树的高度有关(D)

A. I、Ⅱ、Ⅳ、V

B. Ⅱ、Ⅲ、Ⅳ

C. I、Ⅲ、V

D. I、Ⅳ、V

解析：在二叉排序树中，新插入的关键字总是作为叶子结点来插入的，但是叶子结点不一定总是处于最底层。对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字；右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子的关键字进行比较。

11.在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( )倍。(C)

A. 1／2

B. 2

C. 1

D. 4

解析：在有向图中每个顶点的入度就是另外一个顶点的出度，因此所有顶点的入度之和等于所有顶点出度之和，等于有向图中所有的边数。

12.已知有向图G=(V，E)，其中V={V₁，V₂，V₃，V₄，V₅，V₆，V本文档预览：3000字符，共7556字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载