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

(1).数据结构不包含的内容是

A.数据的元素来源
B.数据的逻辑结构
C.数据的存储结构
D.对数据施加的操作

(2).下列选项中，属于逻辑结构的是

A.循环队列
B.二叉树
C.散列表
D.邻接表

(3).下列选项中，属于顺序存储结构优点的是

A.插入运算方便
B.删除运算方便
C.存储密度大
D.方便存储各种逻辑结构

(4).某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则下列存储结构中，最节省运算时间的是

A.单链表
B.仅有头指针的单循环链表
C.双向链表
D.仅有尾指针的单循环链表

(5).用不带头结点的单链表存储队列，在进行删除运算时

A.仅修改头指针
B.仅修改尾指针
C.头、尾指针一定都要修改
D.头、尾指针可能都要修改

(6).二维数组M，行下标取值范围为0～8，列下标取值范围为1～10，若按行优先存储时，元素M[8][5]的存储地址为ar，则按列优先存储时，地址ar存储的数组元素应是

A.M[8][5]
B.M[5][8]
C.M[3][l0]
D.M[0][9]

(7).根据二叉树的定义，3个结点构成的二叉树的树型有

A.2种
B.3种
C.4种
D.5种

(8).—棵有序树可转换为一棵二叉树，树的后序遍历对应二叉树的

A.前序遍历
B.中序遍历
C.后序遍历
D.以上都不对

(9).若图G的邻接表中有奇数个表结点，则G是

A.含奇数个顶点的图
B.无向图
C.含偶数个顶点的图
D.有向图

(10).若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑排序序列的结论是

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

(11).

如果无向图G的最小生成树中含有边（a，b）和（a，c）,则下列选项中，—定不在T中的边是

A.(b，c)
B.(b，d)
C.(c，d)
D.(c，e)

(12).下列排序算法中，在每一趟都能选出一个元素放到其最终位罝上的是

A.插入排序
B.希尔排序
C.归并排序
D.堆排序

(13).若数据元素序列11，13,15,7,8,9,23,2,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法是

A.冒泡排序
B.插入排序
C.选择排序
D.归并排序

(14).线性表采用顺序存储或链式存储，对其进行查找的方法应是

A.顺序查找
B.二分查找
C.散列查找
D.索引查找

(15).设有序表为{1,3,9,12,32,41,45,62,75,77,82},采用二分查找法查找关键字75,查找过程中关键字之间的比较次数是

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

(16).在数据结构中，从逻辑上可以把数据结构分为线性结构和 。

非线性结构

(17).为便于实现单链表的插入及删除运算，需要在单链表中增加一个结点，该结点称为 。

头结点

(18).在二维数组A[10][8]中，每个数组元素占用4个存储单元，则数组A需要的存储单元个数是 。

320

(19).对长度为1的广义表A，若有Head（A）=Tail（A），则A= 。

（（））

(20).设高为h的二叉树T中只有度为0和2的结点，则T包含的结点数最多为 。

2<>h-1

(21).—个连通图的 是包含图中所有顶点的极小连通子图。

生成树

(22).无向图G中含7个顶点，顶点间的边是随机设罝的，为保证图G在任何情况下都是连通的，则需要的边数最少是 。

16

(23).求单源最短路径的迪杰斯特拉（Dijkstra）算法是按照路径 不减的次序求出各条路径的。

长度

(24).—组记录的关键字为（45,53,18,49,36,76,13,97,36,32）,利用快速排序方法对其进行排序，选择45为基准，一次划分后的结果为 。

32，36，18，13，36，45，76，97，49，53

(25).对箱排序的改进和推广的排序算法是 。

基数排序

(26).

两个栈共享数组空间data[m]（定义如下），它们的栈底分别设在数组的两端（初始化后 top1=-1，top2=m）。

（1）判断栈满Int stackfull(SeqStack *s){ return s->top1+1==s->top2;}（2）进栈Void push(SeqStack *S,int si,DataType X){if (stackfull(s)) printf(“satck overflow”);else{ if (si==0)s->data[++s->top1]=x;else s->data[--s->top2]=x;}}

(27).

已知二叉树T中含有元素 A，B，C，D，E，F，G，H，T的前序遍历序列、中序遍历序列和后序遍历序列如下，其中符号__ __表示未知元素. 试写出①到⑩所代表的正确元素值.

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

(28).

设图G如题28图所示. 回答下列问题。 （1）图G是否是有向无环图？ （2）给出图G所有的拓扑排序序列。

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

(29).设关键字序列为：53,15,72,52,48,67,63,23。己知散列表地址空间为0〜11,散列函数为H （ k ） = k mod11，采用线性探查再散列法解决冲突。 （1）将所给关键字数据依次填入该散列表中； （2）计算等概率下查找成功的平均查找长度。

（1）散列表是（2）ASL_查找成功=12/8=1.5

(30).

己知队列的基本操作定义如下，请在空白处填写适当的语句，完成指定的功能。

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

(31).

程序G1是将输入的m行n列的二维数组a变换为三元组表形式存储在数组b中. 请在空白处填上适当内容将算法补充完整，

(1)*a；(2)k++；(3)k

(32).

已知二叉树7. 如题32图所示. 阅读程序f32,写出执行f32（T）的输出结果。

7,3,9,6,1,5,2,8,4

(33).

阅读下列程序，写出执行结果。

62,32,21,23,25,5,10,1,20,9

(34).

己知带有头结点的单链表定义如下：

int f34(LinkList h,char string[]){ LinkList p,q;Char *pcint count=0;Pc=string;While(*pc!=’\0’){P=h;While(p->next!=null){if(p->next->ch!=*pc)P=p->next;Else break;}if(p->next==null){q=(LinkList)malloc(sizeof(ListNode));q->ch=*pc;q->next=p->next;p->next=q;count++;}Pc++;}Return count;}

(35).求单源最短路径的迪杰斯特拉（Dijkstra）算法是按照路径______不减的次序求出各条路径的。

长度

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