2018年4月自考02331数据结构试题及答案含解析

数据结构年月真题

0233120184

1、【单选题】数据结构不包含的内容是

数据的元素来源

数据的逻辑结构

A:

数据的存储结构

B:

对数据施加的操作

C:

答D:案：A

解析：数据结构包含的内容包括三方面内容：数据之间的逻辑关系，数据元素的存储方

式，数据的运算即对数据元素施加的操作。

2、【单选题】下列选项中，属于逻辑结构的是

循环队列

二叉树

A:

散列表

B:

邻接表

C:

答D:案：B

解析：逻辑结构是反映数据元素之间逻辑关系的数据结构。逻辑结构反应数据之间的关

系，常见的逻辑结构有：集合、线性结构、树形结构、图状结构，其中树形结构常见的有

二叉树；物理结构是存储结构，如队列、散列表、邻接表等。

3、【单选题】下列选项中，属于顺序存储结构优点的是

插入运算方便

删除运算方便

A:

存储密度大

B:

方便存储各种逻辑结构

C:

答D:案：C

解析：顺序存储时,相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存

储单元的地址必须是连续的。优点：存储密度大，存储空间利用率高。缺点：插入或删除

元素时不方便。

4、【单选题】某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元

素，则下列存储结构中，最节省运算时间的是

单链表

仅有头指针的单循环链表

A:

双向链表

B:

仅有尾指针的单循环链表

C:

答D:案：D

解析：有尾指针的单链表，删除最后一个元素与链表的长度无关，单循环链表有尾指针，

所以时间复杂度为O(1),其他的都要O(n)。

5、【单选题】用不带头结点的单链表存储队列，在进行删除运算时

仅修改头指针

仅修改尾指针

A:

头、尾指针一定都要修改

B:

头、尾指针可能都要修改

C:

答D:案：D

解析：因为当队列中只有一个元素时，删除此元素后要将队列置空，此时要修改队尾指

针，使尾指针与头指针相等（即Q.rear=Q.front）。假设head是指向队列的头结点指

针，p为与head同类型的指针，那么head->next指向的是队列的首结点，那么出队的操

作为p=head->next;//指向欲出队的结点；head->next=p->next;free(p);//销毁队首

节点

6、【单选题】二维数组M，行下标取值范围为0～8，列下标取值范围为1～10，若按行优先

存储时，元素M[8][5]的存储地址为ar，则按列优先存储时，地址ar存储的数组元素应是

M[8][5]

M[5][8]

A:

M[3][10]

B:

M[0][9]

C:

答D:案：C

解析：按行优先存储时，元素M[8][5]的存储地址ar为第85个存储空间，则按列优先存

储时，第85个存储空间的元素是M[3][10]。

7、【单选题】根据二叉树的定义，3个结点构成的二叉树的树型有

2种

3种

A:

4种

B:

C:

5种

答D:案：D

解析：

3个结点能构成的二叉树如图：

8、【单选题】—棵有序树可转换为一棵二叉树，树的后序遍历对应二叉树的

前序遍历

中序遍历

A:

后序遍历

B:

以上都不对

C:

答D:案：B

解析：树转换成二叉树：首先在所有兄弟结点之间加一道连线，然后再对每个结点保留长

子的连线，去掉该结点与其他孩子的连线。树的后序遍历是指先依次后序遍历根的每棵子

树，然后访问根结点。二叉树的中序遍历1、中序遍历左子树2、访问根节点3、中序遍

历右子树。

9、【单选题】若图G的邻接表中有奇数个表结点，则G是

含奇数个顶点的图

无向图

A:

含偶数个顶点的图

B:

有向图

C:

答D:案：D

解析：无向图的邻接表的表结点的个数一定是偶数，为边数的2倍。若图G的邻接表中有

奇数个表结点，则图G一定是有向图。

10、【单选题】若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图

拓扑排序序列的结论是

存在，且唯一

存在，且不唯—

A:

存在，可能不唯一

B:

无法确定是否存在

C:

答D:案：C

解析：一个有向图有拓扑序列的充要条件是该图是有向无环图。对角线以下元素均为零，

表明只有顶点i到顶点j（i<j）可能有边，而顶点j到顶点i一定没有边，即有向图是一

个无环图，因此有向无环图一定存在拓扑排序，但拓扑排序不一定唯一。

11、【单选题】如果无向图G的最小生成树中含有边（a，b）和（a，c）,则下列选项

中，—定不在T中的边是

(b，c)

(b，d)

A:

(c，d)

B:

(c，e)

C:

答D:案：A

解析：最小生成树是：一个有n个结点的连通图的生成树是原图的极小连通子图，且包

含原图中的所有n个结点，并且有保持图连通的最少的边。只有答案A（b，c）这条边是

多余的。

12、【单选题】下列排序算法中，在每一趟都能选出一个元素放到其最终位罝上的是

插入排序

希尔排序

A:

归并排序

B:

堆排序

C:

答D:案：D

解析：堆排序的思想：在排序过程中，将记录数组看成一棵完全二叉树的顺序存储结构，

利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大

或最小记录。

13、【单选题】若数据元素序列11，13,15,7,8,9,23,2,5是采用下列排序方法之一得到的

第二趟排序后的结果，则该排序算法是

冒泡排序

插入排序

A:

选择排序

B:

归并排序

C:

答D:案：B

解析：插入排序(InsertionSort)的基本思想是：每次将一个待排序的记录，按其关键字

大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

14、【单选题】线性表采用顺序存储或链式存储，对其进行查找的方法应是

顺序查找

二分查找

A:

散列查找

B:

索引查找

C:

答D:案：A

解析：顺序查找无论是顺序存储或链式存储都同样适用，缺点就是效率低。二分查找对象

是顺序存储结构的有序表。

15、【单选题】设有序表为{1,3,9,12,32,41,45,62,75,77,82},采用二分查找法查找关键字

75,查找过程中关键字之间的比较次数是

1

2

A:

3

B:

4

C:

答D:案：B

解析：第一次比较时mid=6,第二次mid=9,正好是关键字75.

16、【问答题】两个栈共享数组空间data[m]（定义如下），它们的栈底分别设在数组的

两端（初始化后top1=-1，top2=m）。

答案：（1）判断栈满Intstackfull(SeqStack*s){returns->top1+1==s->top2;}

（2）进栈Voidpush(SeqStack*S,intsi,DataTypeX){if(stackfull(s))

printf(“satckoverflow”);else{if(si==0)s->data[++s->top1]=x;elses->data[--

s->top2]=x;}}

17、【问答题】已知二叉树T中含有元素A，B，C，D，E，F，G，H，T的前序遍历序

列、中序遍历序列和后序遍历序列如下，其中符号____表示未知元素.试写出①到⑩所代

表的正确元素值.

答案：①C②H③D④E⑤H⑥D⑦B⑧E⑨G⑩A

解析：

根据题意可以画出二叉树：

18、【问答题】设图G如题28图所

示.回答下列问题。（1）图

G是否是有向无环图？（2）给出图G所有的拓扑排序序列。

答案：（1）是有向无环图（2）该图的拓扑排序序列有：（1，2，5，4，3，6）和（1，

2，5，4，3，7，6）

解析：有向无环图指的是一个无回路的有向图，图G没有回路。拓扑序列的拓扑排序算法

主要是循环执行以下两步，直到不存在入度为0的顶点为止。(1)选择一个入度为0的顶

点并输出之；(2)从网中删除此顶点及所有出边。循环结束后，若输出的顶点数小于网中

的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

19、【问答题】设关键字序列为：53,15,72,52,48,67,63,23。己知散列表地址空间为0〜11,

散列函数为H（k）=kmod11，采用线性探查再散列法解决冲突。（1）将所给关键字数

据依次填入该散列表中；（2）计算等概率下查找成功的平均查找长度。

答案：

解析：53/11余9，15/11余4，72/11余6，53/11余8，48/11余4，冲突后重新分配，

（4+1）/11余5，67/11余1，63/11余8，冲突后重新分配，（8+1）/11余9，还是冲

突，（9+1）/11余10，23/11余1，处理冲突（1+1）/11余2。按余的值放到散列表的相

应位置。一共查找了12次，共8个数，所以12除8=1.5是查找长度。

20、【问答题】己知队列的基本操作定义如下，请在空白处填写适当的语句，完成指定的

功能。

答案：(1)Q->rear==Q->front(2)(Q->rear+1)%QueueSize(3)(Q->front+1)%QueueSize

21、【问答题】程序G1是将输入的m行n列的二维数组a变换为三元组表形式存储在数

组b中.请在空白处填上适当内容将算法补充完整，

答案：(1)*a；(2)k++；(3)k

22、【问答题】已知二叉树7.如题32图所示.阅读程序f32,写出执行f32（T）的输出

结果。

答案：7,3,9,6,1,5,2,8,4

解析：先输出右子树的值，再输出根结点的值，再输出左子树的值，左右子树分别递归。

23、【问答题】阅读下列程序，写出执行结果。

答案：62,32,21,23,25,5,10,1,20,9

解析：堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值

就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个

元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有

序序列了.

24、【问答题】己知带有头结点的单链表定义如下：

答案：intf34(LinkListh,charstring[]){LinkListp,q;Char

*pcintcount=0;Pc=string;While(*pc!=’\0’){P=h;While(p->next!=null){if(p-

>next->ch!=*pc)P=p->next;Elsebreak;}if(p-

>next==null){q=(LinkList)malloc(sizeof(ListNode));q->ch=*pc;q->next=p->next;p-

>next=q;count++;}Pc++;}Returncount;}

解析：就是新建一个ListNode，然后链到新链表上，如果遇到重复的字符就跳过去。

25、【填空题】在数据结构中，从逻辑上可以把数据结构分为线性结构和。

答案：非线性结构

26、【填空题】为便于实现单链表的插入及删除运算，需要在单链表中增加一个结点，该结

点称为。

答案：头结点

27、【填空题】在二维数组A[10][8]中，每个数组元素占用4个存储单元，则数组A需要的

存储单元个数是。

答案：320

28、【填空题】对长度为1的广义表A，若有Head（A）=Tail（A），则A=。

答案：（（））

29、【填空题】设高为h的二叉树T中只有度为0和2的结点，则T包含的结点数最多为

（）。

答案：2h-1

解析：

考虑按如下规则构造一棵高度为H的二叉树，可使得其节点数最少：1)构造一个根结点2)

为根结点构造2个儿子结点3)如果树的高度已经达到H，则结束；否则以上