【渝粤题库】广东开放大学 数据结构期末考试押题试卷标准答案

广东开放大学 形成性考核 平时作业 参考答案 标准答案

关注【广开搜题】微信公众号 发送题目获取标准答案

1、在一棵度具有5层的满二叉树中结点总数为（ ）。（难度系数：易 ）（2 分）

A、31

B、32

C、33

D、16

2、下列关于串的叙述中，不正确的是（ ）。（难度系数：易 ）（2 分）

A、串是字符的有限序列

B、空串是由空格构成的串

C、模式匹配是串的一种重要运算

D、串既可以采用顺序存储，也可以采用链式存储

3、广义表(a, b, (c, (d)))的表尾是（ ）。（难度系数：易 ）（2 分）

A、(d)

B、(c,(d))

C、b,(c,(d))

D、(b,(c,(d)))

4、广义表((a,b,c,d))的表头是（ ）。（难度系数：易 ）（2 分）

A、a

B、()

C、(a,b,c,d)

D、(b,c,d)

5、下面的说法中，不正确的是（　　　）。（难度系数：易 ）（2 分）

A、广义表是一种多层次的结构

B、广义表是一种共享结构

C、广义表是一种非线性结构

D、广义表是一种递归

6、下面（　　　）不属于特殊矩阵。（难度系数：易 ）（2 分）

A、对角矩阵

B、三角矩阵

C、稀疏矩阵

D、对称矩阵

7、设广义表L=((a,b,c)),则L的深度是（ ）。（难度系数：易 ）（2 分）

A、0

B、1

C、2

D、3

8、设有数组A[i,j]，数组的每个元素长度为3个字节，i的值为1~8，j的值为1~10，数组从内存首地址BA开始顺序存放，当用以列为主序存放时，元素A[5,8]的存储首地址为（ ）。（难度系数：易 ）（2 分）

A、BA+141

B、BA+180

C、BA+222

D、BA+225

9、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（ ）结构。（难度系数：易 ）（2 分）

A、线性表

B、栈

C、队列

D、数组

10、用链接方式存储的队列，在进行删除运算时（　）。（难度系数：易 ）（2 分）

A、仅修改头指针

B、仅修改尾指针

C、头、尾指针都要修改

D、头、尾指针可能都要修改

11、两个字符串相等的条件是（ ）（难度系数：易 ）（2 分）

A、两串的长度相等

B、两串包含的字符相同

C、两串的长度相等，并且两串包含的字符相同

D、两串的长度相等，并且对应位置上的字符相同

12、将含有86个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为42的左孩子编号为（ ）（难度系数：易 ）（2 分）

A、80

B、40

C、90

D、84

13、设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ ）。（难度系数：易 ）（2 分）

A、(i-1)*n+j

B、(i-1)*n+j-1

C、i*(j-1)

D、j*m+i-1

14、设广义表L=((a,b,c)),则L的长度是（ ）。（难度系数：易 ）（2 分）

A、1

B、2

C、3

D、4

15、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。（难度系数：易 ）（2 分）

A、先序

B、中序

C、后序

D、从根开始按层次遍历

16、在一棵树中，（ ）没有前驱结点。（难度系数：易 ）（2 分）

A、分支结点

B、叶结点

C、树根结点

D、空结点

17、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i（2 分）

A、i*(i-1)/2+j

B、j*(j-1)/2+i

C、i*(i+1)/2+j

D、j*(j+1)/2+i

18、把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。（难度系数：易 ）（2 分）

A、1

B、2

C、3

D、4

19、设计一个判别表达式中左，右括号是否配对出现的算法，采用（　）数据结构最佳。（难度系数：易 ）（2 分）

A、线性表的顺序存储结构

B、队列

C、线性表的链式存储结构

D、栈

20、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ ）。（难度系数：易 ）（2 分）

A、4

B、5

C、6

D、7

21、设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。（难度系数：易 ）（2 分）

A、n-1

B、n

C、n+1

D、n+2

22、数组A[0...4,-1...-3,5...7]中含有元素的个数为（ ）。（难度系数：易 ）（2 分）

A、45

B、55

C、36

D、16

23、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。（难度系数：易 ）（2 分）

A、250

B、254

C、500

D、501

24、引入二叉线索树的目的是（ ）。（难度系数：易 ）（2 分）

A、加快查找结点的前驱或后继的速度

B、为了能在二叉树中方便的进行插入与删除

C、为了能方便的找到双亲

D、使二叉树的遍历结果唯一

25、在一棵二叉树中，若编号为i的结点存在右孩子，则（ ）孩子的顺序编号为 2i+1（难度系数：易 ）（2 分）

A、权

B、左

C、右

D、无

26、向顺序栈中压入新元素时，应当（ ）。（难度系数：易 ）（2 分）

A、先移动栈顶指针，再存入元素

B、先存入元素，再移动栈顶指针

C、先后次序无关紧要

D、同时进行

27、串是一种特殊的线性表，其特殊性体现在（ ）。（难度系数：易 ）（2 分）

A、可以顺序存储

B、可以链式存储

C、数据元素是单个字符

D、数据元素可以是多个字符

28、利用二叉链表存储树，则根结点的右指针是（ ）。（难度系数：易 ）（2 分）

A、指向最左孩子

B、指向最右孩子

C、空

D、非空

29、广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。（难度系数：易 ）（2 分）

A、(g)

B、(d)

C、c

D、d

30、设二维数组A[5][6]按行优先顺序存储在内存中，已知A[0][0] 起始地址为1000，每个数组元素占用5个存储单元，则元素A[4][4]的地址为（ ）。（难度系数：易 ）（2 分）

A、1140

B、1145

C、1120

D、1125

多项选择题

31、一个队列的入队序列是1，2，3，4。则队列的输出序列错误是（ ）。（难度系数：易 ）（2 分）

A、4，3，2，1

B、1，2，3，4

C、1，4，3，2

D、3，2，4，1

32、下列有关二叉树的说法不正确的是（ ）。（难度系数：易 ）（2 分）

A、二叉树中度为0的结点的个数等于度为2的结点的个数加1

B、二叉树中结点个数必大于0

C、完全二叉树中，任何一个结点的度，或者为0或者为2

D、二叉树的度是2

33、下列关于m阶B-树的说法正确的是（）。（难度系数：易 ）（2 分）

A、根结点至多有m棵子树

B、所有叶子都在同一层次上

C、非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树

D、根结点中的数据是有序的

34、n（n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，正确的是（）。（难度系数：易 ）（2 分）

A、该树一定是一棵完全二叉树

B、树中一定没有度为1的结点

C、树中两个权值最小的结点一定是兄弟结点

D、树中任一非叶结点的权值一定不小于下一层任一结点的权值

35、下面关于哈希查找的说法，正确的是（）。（难度系数：易 ）（2 分）

A、采用链地址法处理冲突时，查找一个元素的时间是相同的

B、采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的

C、用链地址法处理冲突，不会引起二次聚集现象

D、用链地址法处理冲突，适合表长不确定的情况

36、不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。（2 分）

正确

错误

37、程序是用计算机语言表述的算法。（2 分）

正确

错误

38、算法一定要有输入和输出。（2 分）

正确

错误

39、线性表的顺序存储结构优于链接存储结构。（难度系数：易 ）（2 分）

正确

错误

40、逻辑结构与数据元素本身的内容和类型无关。（难度系数：易 ）（2 分）

正确

错误

41、数据项是数据处理的最小单位。（2 分）

正确

错误

42、顺序存储的线性表可以随机访问,链式存储的线性表只能顺序访问。（2 分）

正确

错误

43、算法分析的目的旨在分析算法的效率以求改进算法。（2 分）

正确

错误

44、顺序文件是指文件中的物理记录按其在文件中的逻辑记录顺序依次存入存储介质而建立的（2 分）

正确

错误

45、非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（2 分）

正确

错误

46、在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上不一定相邻。（2 分）

正确

错误

47、每种数据结构都应具备三种基本运算：插入、删除和搜索。（2 分）

正确

错误

48、线性表的逻辑顺序和存储顺序总是一致的。（难度系数：易 ）（2 分）

正确

错误

49、快速排序法是一种稳定性排序法。（2 分）

正确

错误

50、线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。（难度系数：易 ）（2 分）

正确

错误