国家开放大学数据结构真题精选.docx

国家开放大学数据结构真题精选.docx

《国家开放大学数据结构真题精选.docx》由会员分享，可在线阅读，更多相关《国家开放大学数据结构真题精选.docx（15页珍藏版）》请在冰点文库上搜索。

国家开放大学数据结构真题精选

国家开放大学（数据结构）真题精选

[单项选择题]

1、邻接表是图的一种（）。

A.索引存储结构

B.顺序存储结构

C.散列存储结构

D.链式存储结构

参考答案：

D

[填空题]

2结构中的元素之间存在多对多的关系称为（）结构。

参考答案：

图状

[单项选择题]

3、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。

A.一棵树

B.有回路

C.完全图

D.连通图

参考答案：

D

[填空题]

4在队列的顺序存储结构中，当插入一个新的队列元素时，（）指针的值增1，当删除一个元素队列时，（）指针的值增1。

参考答案：

尾；头

[填空题]

5结点的度是指结点所拥有的（）。

参考答案：

子树树木或后继结点数

[填空题]

6树的度是指（）。

参考答案：

树中所有结点的度的最大值

[填空题]

7如图所示的二叉树，其后序遍历序列为（）。

参考答案：

gdbeihfca

[填空题]

8度等于0的结点称作（）或（）。

参考答案：

叶子结点；终端结点

[填空题]

9在一棵树中，每个结点的（）或者说每个结点的（）称为该结点的（），简称为孩子。

参考答案：

子树的根；后继结点；孩子结点

[填空题]

10按照二叉树的递归定义，对二叉树遍历的常用算法有（）、（）、（）三种。

参考答案：

先序；中序；后序

[填空题]

11树的深度或高度是指（）。

参考答案：

树中结点的最大层数

[填空题]

12稀疏矩阵存储时，采用一个由（）、（）、（）3部分信息组成的三元组唯一确定矩阵中的一个非零元素。

参考答案：

行号；列号；非零元

[填空题]

13序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的（）；先序遍历二叉树的（），先序遍历二叉树的（）。

参考答案：

根结点；左子树；右子树

[单项选择题]

14、把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。

A.逻辑结构

B.给相关变量分配存储单元

C.算法的具体实现

D.物理结构

参考答案：

D

[填空题]

15先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的（）；先序遍历二叉树的（），先序遍历二叉树的（）。

参考答案：

根结点；左子树；右子树

[填空题]

16在一个不带头结点的非空链队中，f和r分别为队头和队尾指针，队结点的数据域为data，指针域为next，若要进行出队操作，并用变量x存放出队元素的数据值，则相关操作为x=f->data；（）。

参考答案：

f=f->next；

[填空题]

17后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的（）；后序遍历二叉树的（），访问而叉树的（）。

参考答案：

左子树；右子树；根结点

[单项选择题]

18、下列说法中，不正确的是（）。

A.数据可有若干个数据元素构成

B.数据元素是数据的基本的单位

C.数据项是数据中不可分割的最小可标识单位

D.数据项可由若干个数据元素构成

参考答案：

D

[填空题]

19将树中结点赋上一个有着某种意义的实数，称此实数为该结点的（）。

参考答案：

权

[填空题]

20设有一个单向循环链表，头指针为head，链表中结点的指针域为next，p指向尾结点的直接前驱结点，若要删除尾结点，得到一个新的单向循环链表，可执行操作（）。

参考答案：

p->next=head；

[填空题]

21哈夫曼树又称为（），它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL（）。

参考答案：

最优二叉树；最小的二叉树

更多内容请访问《睦霖题库》微信公众号

[单项选择题]

22、数据结构中，与所使用的计算机无关的是数据的（）。

A.物理结构

B.逻辑结构

C.物理和存储结构

D.存储结构

参考答案：

B

[填空题]

23若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（）。

参考答案：

69

[填空题]

24通常可以把一本含有不同章节的书的目录结构抽象成（）结构。

参考答案：

树形

[填空题]

25图的深度优先搜索遍历类似于树的（）遍历。

参考答案：

先序

[单项选择题]

26、下列的叙述中，不属于算法特性的是（）。

A.有穷性

B.可行性

C.可读性

D.输入性

参考答案：

C

[填空题]

27图的广度优先搜索类似于树的（）遍历。

参考答案：

按层次

[单项选择题]

28、排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（）排序。

A.归并

B.插人

C.快速

D.选择

参考答案：

D

[填空题]

29已知某二叉树的先序遍历结果是：

A，B，D，G，C，E，H，L，I，K，M，F和J，它的中序遍历结果是：

G，D，B，A，L，H，E，K，I，M，C，F和J，请画出这棵二叉树，并写出该二叉树后续遍历的结果。

参考答案：

（1）二叉树图形表示如下：

（2）该二叉树后序遍历的结果是：

G、D、B、L、H、K、M、I、E、J、F、C和A。

[单项选择题]

30、算法的时间复杂度与（）有关。

A.所使用的计算机

B.数据结构

C.算法本身

D.计算机的操作系统

参考答案：

C

[单项选择题]

31、链表所具备的特点是（）。

A.可以随机访问任一结点

B.占用连续的存储空间

C.插人删除元素的操作不需要移动元素结点

D.可以通过下标对链表进行直接访问

参考答案：

C

[填空题]

32假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I组成，它们出现的频率分别是：

10、20、5、15、8、2、3、7和30。

请请用这9个字母出现的频率作为权值求：

设计一棵哈夫曼树。

参考答案：

[单项选择题]

33、设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。

A.n-i+1

B.n-i-1

C.n-i

D.i

参考答案：

A

[单项选择题]

34、在对一组元素（64，48，106，33，25，82，70，55，93）进行直接插入排序时，当进行到要把第7个元素70插入到已经排好序的子表时，为找到插入位置，需进行（）次元素间的比较（指由小到大排序）。

A.6

B.2

C.3

D.4

参考答案：

C

[填空题]

35假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I组成，它们出现的频率分别是：

10、20、5、15、8、2、3、7和30。

请请用这9个字母出现的频率作为权值求：

写出每个字符的哈夫曼编码。

参考答案：

每个字符的哈夫曼编码为：

A：

100，B：

11，C:

//1010，D:

//000，E:

//0010，F:

//10110，G:

//10111，H：

0011，I：

01。

[单项选择题]

36、在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。

A.p->next=q->next

B.p=q->next

C.q->next=NULL

D.p->next=q

参考答案：

A

[填空题]

37已知无向图G描述如下：

G=（V，E）V={V1，V2，V3，V4，V5}E={（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）}画出G的图示。

参考答案：

[单项选择题]

38、已知一个图的所有顶点的度数之和为m，且m是以下4中情况之一，则m只可能是（）。

A.9

B.7

C.15

D.8

参考答案：

D

[填空题]

39已知无向图G描述如下：

G=（V，E）V={V1，V2，V3，V4，V5}E={（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）}写出每个顶点的度。

参考答案：

V1、V2、V3、V4、V5的度分别为：

2，3，2，3，2。

[单项选择题]

40、在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。

A.p=s->next

B.p->next=s；s->next=p->next

C.p->next=s->next；

D.s->next=p->next；p->next=s；

参考答案：

D

[单项选择题]

41、设有一个10阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。

（矩阵A的第一个元素为a1，1，数组b的下标从1开始），则矩阵元素a5，3对应一维数组b的数组元素是（）。

A.b[18]

B.b[8]

C.b[13]

D.b[10]

参考答案：

C

[填空题]

42以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。

参考答案：

（1）Inorder（BT->left）

（2）printf（"%c"，BT->data）

[单项选择题]

43、链表不具有的特点是（）。

A.可随机访问任一元素

B.插入删除不需要移动元素

C.不必事先估计存储空间

D.所需空间与线性表长度成正比

参考答案：

A

[单项选择题]

44、对线性表进行二分查找时，要求线性表必须（）。

A.以顺序存储方式

B.以顺序存储方式，且数据元素有序

C.以链接存储方式，且数据元素有序

D.以链接存储方式

参考答案：

B

[单项选择题]

45、一个栈的进栈序列是a，b，c，d，则栈的不可能的出栈序列是（）。

A.dcba

B.bcad

C.cbad

D.adbc

参考答案：

D

[单项选择题]

46、带头结点的链表为空的判断条件是（）（设头指针为head）。

A.head->next==NULL

B.head->next==head

C.head==NULL

D.head!

=NULL

参考答案：

A

[单项选择题]

47、有关线性表的正确说法是（）。

A.表中的元素必须按由小到大或由大到下排序

B.除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继

C.线性表至少要求一个元素

D.每个元素都有一个直接前驱和一个直接后继

参考答案：

B

[单项选择题]

48、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

A.（n-1）/2

B.（n+1）/2

C.n

D.n/2

参考答案：

B

[单项选择题]

49、从n个数中选取最大元素（）。

A.基本操作是数据元素间的交换

B.算法的时间复杂度是O（n）

C.算法的时间复杂度是O（n2）

D.需要进行（n+1）次数据元素间的比较

参考答案：

B

[单项选择题]

50、向一个有127个元素的顺序表中插入一个新元素，并保持原来的顺序不变，平均要移动（）个元素。

A.8

B.7

C.63

D.63.5

参考答案：

D

[单项选择题]

51、已知一个有序表为{11，22，33，44，55，66，77，88，99}，则顺序查找元素55需要比较（）次。

A.5

B.6

C.4

D.3

参考答案：

A

[单项选择题]

52、在双向循环链表中，在p所指的结点之后插入指针f所指的新结点，其操作步骤是（）。

A.f->prior=p；f->next=p->next；p->next=f；p->next->prior=f；

B.p->next=f；f->prior=p；p->next->prior=f；f->next=p->next；

C.f->prior=p；f->next=p->next；p->next->prior=f；p->next=f；

D.p->next=f；p->next->prior=f；f->prior=p；f->next=p->next；

参考答案：

C

[填空题]

53在一个长度为n的顺序存储结构的线性表中，向第i（1£i£n+1）个元素之前插入新元素时，需向后移动（）个数据元素。

参考答案：

n-i+1

[单项选择题]

54、在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是（）。

A.冒泡

B.选择

C.折半插入

D.直接插入

参考答案：

C

[单项选择题]

55、设有一个20阶的对称矩阵A，采用压缩存储方式，将其下三角部分以行序为主序存储到一维数组中（矩阵A的第一个元素为a11，数组b的下标从1开始），则矩阵元素a8，5在一维数组b中的下标是（）。

A.30

B.28

C.40

D.33

参考答案：

D

[单项选择题]

56、设顺序存储的线性长度为n，要在第i个元素之前插入一个新元素，按课本的算法当i=（）时，移动元素次数为2。

A.n/2

B.n

C.n-1

D.1

参考答案：

C

[填空题]

57除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为（），每个结点可有任意多个前驱和后继结点数的结构为（）。

参考答案：

线性结构；非线性结构

[单项选择题]

58、有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）。

A.12，24，30，37，45，53，96

B.30，24，12，37，45，96，53

C.37，24，12，30，53，45，96

D.45，24，53，12，37，96，30

参考答案：

C

[填空题]

59数据结构中的数据元素存在多对多的关系称为（）。

参考答案：

图状结构

[填空题]

60数据结构中的数据元素存在一对多的关系称为（）。

参考答案：

树形结构