​数据结构自考2015年4月真题

数据结构自考2015年4月真题及答案解析

本试卷为单选题型，填空题，算法阅读，算法设计等题型。

一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

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

A.O(log2n)
B.O(n)

C.

D.

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

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

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

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

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

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

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

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

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

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

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

A.n-1
B.n+1
C.2n-1
D.2n+1

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

A.n-1
B.n+1
C.2n-1
D.2n+1

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

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

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

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

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

A.

B.

C.

D.

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

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

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

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

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

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

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

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

二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。

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

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

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

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

15.广义表A=(a，(b，C，(e，f，g，h)))，head(tail(A))= _________。

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

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

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

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

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

三、解答题(本大题共4小题，每小题5分，共20分)

21.顺序栈的类型定义如下：typedef struct{      DataType data[MaxSize];         int top;}SeqStack;SeqStack S;规定栈底位置在MaxSize-1，请回答下列问题。(1)若要求栈空时条件为真，则判断栈空的条件表达式是什么?(2)若要求栈满时条件为真，则判断栈满的条件表达式是什么?(3)用语句表示将X入栈的操作。

22.已知广义表及结点类型结构如下：typedef enum{ATOM, LIST}NodeTag;       //ATOM=0,表示原子;LIST=1,表示子表typedef struct GLNode{ NodeTag tag;     //区分原子结点和表结点     union{     DataType data;      //存放原子结点的值     GLNode *slink;       //指向子表的指针};GLNode *next;    //指向下一个表结点}*Glist; //广义表类型请回答下列问题。(1)若广义表A为空表，应如何表示?(2)若广义表A=(a，(b，c))，画出A的存储结构。

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

24.给定带权图G如题29图所示，使用迪杰斯特拉(Dijkstra)算法，求顶点vl到其他 各顶点的最短路径，列出每条路径上的各顶点及路径长度。

四、算法阅读题(本大题共4小题，每小题5分，共20分)

31.设下列程序段中的数据皆为int型，请指出该程序段的功能是什么。

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

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

34.阅读程序，并回答下列问题。 假设顺序表R的元素存放在下标为l～8的数组元素中，K=7，low=1，high=8。(1)R的关键字依次为{1，2，3，4，5，6，7，8)，函数f33的返回值是多少?(2)R的关键字依次为{7，7，7，7，7，7，7，7)，函数f33的返回值是多少?(3)简述函数的功能。

五、算法设计题(本大题共1小题，共10分)

41.存储二叉树的二叉链表定义如下：ypedef struct node {       char data;       struct node *lchild, *rchild;} BinTNode;typedef BinTNode *BinTree;请编写一个后序遍历二叉树的递归程序void PostOrder(BinTree root)，并输出遍历序列。其中root指向二叉树根结点。