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

(1).下列选项中,不宜采用链式存储的是

A.无向图
B.单链表
C.最优二叉树
D.数组

(2).将10个数据元素保存在顺序栈S中,若栈顶元素的存储地址是100,中每个元素占4个存储单元,进栈按Stop=S.top+1修改栈顶,则栈底元素的存储地址是

A.60
B.64
C.136
D.140

(3).设指针变量head指向循环链表的头结点,next是结点的指针域,则判断此链表为空的条件是

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

(4).已知广义表LS=(((a,b,c)),((d,(e)),(f,(g))),(h,g),i),LS的深度是

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

(5).已知一棵完全二叉树T共有7个分支结点,则T中叶子结点个数最少是

A.7
B.8
C.9
D.10

(6).在一棵非空二叉树的后序遍历序列中,所有列在根结点前面的是

A.左子树中的部分结点
B.右子树中的全部结点
C.左右子树中的全部结点
D.左右子树中的部分结点

(7).用邻接表保存有n个顶点和e条边的无向图,邻接表中指针个数是

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

(8).有向图G中某个顶点的出度和入度均为2,则G中的顶点个数最少是

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

(9).在带权图的最短路径问题中,路径长度是指

A.路径上边的数目
B.路径上结点的数目
C.路径上边的权值之和
D.到达终点的最短路径数目

(10).对数据序列(15,10,8,12,15,8,10)按升序进行希尔排序,增量序列为5,3,两趟排序后,得到的排序结果为

A.8,8,10,10,15,15,12
B.8,8,10,10,12,15,15
C.8,10,8,10,15,15,12
D.8,10,8,10,12,15,15

(11).下列排序方法中,不稳定的排序方法是

A.直接选择排序
B.归并排序
C.直接插入排序
D.基数排序

(12).一组记录的关键字为(35,58,24,13,44,19,10),利用堆排序算法进行降序排序,要求空间复杂度为O(1),建立的初始堆为

A.10,13,19,58,44,35,24
B.10,13,35,58,44,19,24
C.58,44,24,13,35,19,10
D.58,35,24,13,44,19,10

(13).一棵二叉排序树中,关键字n所在结点的层数大于关键字m所在结点的层数,则

A.n一定大于m
B.n一定小于m
C.n一定等于m
D.n与m的大小关系不确定

(14).设散列表长m=10,散列函数H(key)=key%9.表中已保存3个关键字:H(13)=4,H(32)=5,H(15)=6,其余地址均为空。保存关键字23时存在冲突,采用线性探查法来处理。则查找关键字23时的探查次数是

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

(15).下面关于m阶(m≥3)B树的叙述中,正确的是

A.终端结点可位于不同层
B.非终端结点至多有m+1棵子树
C.若树非空,则根结点至少有2个关键字
D.每个非根结点包含n个关键字,[m/2]-1≤n≤m-1

(16).设电文字符集是{e1,e2,e3,e4,e5,e6},它们出现的次数分别为:38,12,17,26,14,20。现要为该字符集设计一种哈夫曼编码。请回答下列问题。(1)画出得到的哈夫曼树。(2)给出各符号的哈夫曼编码。

(17).

(1)ABDEFGC ABDEGFC
(2)ABCDEFG ABCDEGF ACBDEFG

(18).有以下关键字序列(15,20,24,32,15,7,14,23),使用快速排序方法将其按升序排列。请回答下列问题。(1)若取第一个关键字为基准,写出第一趟快速排序的结果。(2)若取最后一个关键字为基准,写出第一趟快速排序的结果

(1)14,7,15,32,15,24,20,23
(2)15,20,14,7,15,23,32,24

(19).

(20).

(1)3,5,9,10,2,30,
(2)用给定的整数建立顺序表,奇数从头插入,偶数从表尾插入。

(21).

(22).。

(1)R[mid].key==k
(2)mid-1
(3)mid+1

(23).

(1)Q[front]!=NULL
(2)rear%2(3)front++

(24).

(25).数据的四种基本存储方法是顺序存储、链接存储、____和散列存储。

索引存储

(26).指针p和指针q分别指向单链表L中的两个结点,next为指针域,则判断这两个结点是否相邻的条件是____

p->next==q||q->next==p

(27).递归求解过程中的最小子问题称为____

递归的终止条件(或递归出口)

(28).广义表(((a,b),(c,d,e)),(f,g),h)的表头是____

((a,b),(c,d,e))

(29).3个结点的不同形状的二叉树有____棵。

5

(30).若有向无环图G存在2个入度为0的结点,则G至少存在____个不同的拓扑序列。

2

(31).将一棵树T转换为一棵二叉树,则这棵二叉树的右子树____

为空(或不存在)

(32).对含n个元素的数据序列采用直接选择排序算法进行排序,最好情况下的时间复杂度是____

O(n²)

(33).散列存储中,拉链法(链地址法)是处理____的方法。

冲突

(34).假设顺序存储的有序表R含有14个关键字,进行二分查找时,查找失败时关键字的最大比较次数为____

4

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