【成人自考】【数据结构】【02331】2015年04月考试真题

(1).1．以下各阶时间复杂度中，性能最优的是

A.O(log2n)
B.O(n)
C.O(n3)
D.O(2n)

正确答案A

(2).2．头指针head指向带头结点的单循环链表。链表为空时下列选项为真的是

A.head!=Null
B.head==Null
C.head->next—Null
D.head->next==head

正确答案D

(3).3．设栈的进栈序列为a，b，c，d，e，经过合理的出入栈操作后，不能得到的出栈序列是

A.d，c，e，a，b
B.d，e，c，b，a
C.b，c，d，e
D.e，d，c，b，a

正确答案A

(4).4．使用大小为6的数组实现循环队列，若当前rear=0，front=3。当从队列中出队一 个元素，再入队两个元素后，rear和front的值分别是

A.1和5
B.4和2
C.2和4
D.5和1

正确答案C

(5).5．二维数组a[101120]按行优先顺序存放在连续的存储空间中，元素a[0] [O]的存储地址为200，若每个元素占1个存储空间，则元素a[6][2]的存储地址是

A.226
B.322
C.341
D.342

正确答案B

(6).6．广义表A=(a(b，c，(e，f, g，h)))的深度是

A.2
B.3
C.4
D.7

正确答案B

(7).7．以二叉链表作为二叉树的存储结构，在有n(n>O)个结点的二叉链表中，空指针 域的个数是

A.n一1
B.n+1
C.2n—l
D.2n+l

正确答案B

(8).8．构造一棵含n个叶结点的哈夫曼树，树中结点总数是

A.n—l
B.n+l
C.2n一1
D.2n+l

正确答案C

(9).9．若图G的邻接表中有奇数个表结点，下列选项中，正确的是

A.G中必有奇数个顶点
B.G中必有偶数个顶点
C.G为无向图
D.G为有向图

正确答案D

(10).10. 下列关于有向无环图G的拓扑排序序列的叙述中，正确的是

A.存在且唯一
B.存在且不唯一
C.存在但可能不唯一
D.无法确定是否存在

正确答案C

(11).

11．对下图进行广度优先搜索遍历，不能得到的遍历序列是 

A.A
B.B
C.C
D.D

正确答案B

(12).12.下列排序方法中，效率较高且使用辅助空间最少的方法是

A.冒泡排序
B.快速排序
C.堆排序
D.归并排序

正确答案C

(13).13.下列排序方法中，平均比较次数最少的方法是

A.插入排序
B.快速排序
C.简单选择排序
D.归并排序

正确答案B

(14).14．对含有l6个元素的有序表进行二分查找，关键字比较次数最多是

A.3
B.4
C.5
D.6

正确答案C

(15).15．下列叙述中，不符合m阶B树定义的是

A.根结点可以只有一个关键字
B.所有叶结点都必须在同一层上
C.每个结点内最多有m棵子树
D.每个结点内最多有m个关键字

正确答案D

(16).16．算法必须满足可行性等五个准则，其中_________的含义是：算法中每条指令的含义都必须明确，无二义性。

确定性

(17).17.采用大0表示法时，常数阶算法的时间复杂度记为_________。

O(1)

(18).18.一个线性表如果需要频繁地增删元素，则存储结构应该选择_________。

链式存储结构

(19).19.队列Q中已有元素l，3，5，数据序列2，4，6，8，10依次入队，再连续执行6次出队操作，得到的出队序列是_________。

1，3，5，2，4，6

(20).20.广义表A=(a，(b，C，(e，￡9，h)))，head(tail(A))= _________。

（b,c(c,f,g,h))

(21).21.一棵右子树为空的二叉树在后序线索化后，其空指针域的个数为_________。

2

(22).22.用矩阵作为图的存储结构，该矩阵称为图的_________。

邻接矩阵

(23).23．普里姆(Prim)算法得到的是带权连通图的_________。

最小生成树

(24).24．希尔排序方法使用的增量序列中，最后一个增量必须是_________。

1

(25).25. 若待排序序列中的关键字基本有序，采用快速排序或直接插入排序时，效率较高的是_________。

直接插入排序

(26).26．顺序栈的类型定义如下：规定栈底位置在MaxSize—l，请回答下列问题。(1)若要求栈空时条件为真，则判断栈空的条件表达式是什么?(2)若要求栈满时条件为真，则判断栈满的条件表达式是什么?(3)用语句表示将X入栈的操作。

（1）判断栈空的条件：S.top=MaxSize-1 (2分）（2）判断栈满的条件：S.top==-1 (2分）（3）S.data[S.top--]=x; (2分）注：本题答案不唯一，只要正确，同样给分。

(27).27．已知广义表及结点类型结构如下：请回答下列问题。(1)若广义表A为空表，应如何表示?(2)若广义表A=(a，(b，c))，画出A的存储结构。

（1）空表为：A=NULL （1分）（2）存储结构如下：注：每正确画出一个节点给一分，共四分。

(28).28．已知散列函数为H(key)=key％11，现将关键字序列{23，27，34，56，58，10，18，120)散列到散列表HT（0…10）中，利用线性探查法解决冲突。回答下列问题。(1)画出最后的散列表；(2)求在等概率情况下查找成功时的平均查找长度。

（1）散列表如下：（4分）下标 （2） （1分）

(29).31．下列函数的功能是在带头结点的单链表head中删除所有数据域值为X的结点，请在空白处填上适当的语句，使其完成指定功能。

（1）p->next=q (3分）（2）q=q->next （2分）

(30).32．下列函数的功能是：在带头结点的单链表上进行选择排序。请在空白处填上适当内容将函数补充完整，并说明该算法是否是稳定的。

（1）q->next（1分）（2）p-next=q-next （1分）（3）r0->next=q （1分）该算法是稳定额排序方法。 （2分）

(31).二维数组a[10][20]按行优先顺序存放在连续的存储空间中，元素a[0] [0]的存储地址为200，若每个元素占1个存储空间，则元素a[6][2]的存储地址是

A.226
B.322
C.341
D.342

正确答案B

此题目数据由翰林刷题小程序免费提供