国家开放大学数据结构试题.docx
《国家开放大学数据结构试题.docx》由会员分享，可在线阅读，更多相关《国家开放大学数据结构试题.docx（14页珍藏版）》请在冰点文库上搜索。
国家开放大学数据结构试题
国家开放大学（数据结构）
[单项选择题]
1、把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。
A.逻辑结构
B.给相关变量分配存储单元
C.算法的具体实现
D.物理结构
参考答案：
D
[单项选择题]
2、下列说法中，不正确的是（）。
A.数据可有若干个数据元素构成
B.数据元素是数据的基本的单位
C.数据项是数据中不可分割的最小可标识单位
D.数据项可由若干个数据元素构成
参考答案：
D
[单项选择题]
3、数据结构中，与所使用的计算机无关的是数据的（）。
A.物理结构
B.逻辑结构
C.物理和存储结构
D.存储结构
参考答案：
B
[单项选择题]
4、下列的叙述中，不属于算法特性的是（）。
A.有穷性
B.可行性
C.可读性
D.输入性
参考答案：
C
[单项选择题]
5、算法的时间复杂度与（）有关。
A.所使用的计算机
B.数据结构
C.算法本身
D.计算机的操作系统
参考答案：
C
[单项选择题]
6、设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。
A.n-i+1
B.n-i-1
C.n-i
D.i
参考答案：
A
[单项选择题]
7、在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。
A.p->next=q->next
B.p=q->next
C.q->next=NULL
D.p->next=q
参考答案：
A
[单项选择题]
8、在一个单链表中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
[单项选择题]
9、链表不具有的特点是（）。
A.可随机访问任一元素
B.插入删除不需要移动元素
C.不必事先估计存储空间
D.所需空间与线性表长度成正比
参考答案：
A
[单项选择题]
10、带头结点的链表为空的判断条件是（）（设头指针为head）。
A.head->next==NULL
B.head->next==head
C.head==NULL
D.head!
=NULL
参考答案：
A
[单项选择题]
11、有关线性表的正确说法是（）。
A.表中的元素必须按由小到大或由大到下排序
B.除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继
C.线性表至少要求一个元素
D.每个元素都有一个直接前驱和一个直接后继
参考答案：
B
[单项选择题]
12、向一个有127个元素的顺序表中插入一个新元素，并保持原来的顺序不变，平均要移动（）个元素。
A.8
B.7
C.63
D.63.5
参考答案：
D
[单项选择题]
13、在双向循环链表中，在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
[填空题]
14在一个长度为n的顺序存储结构的线性表中，向第i（1£i£n+1）个元素之前插入新元素时，需向后移动（）个数据元素。
参考答案：
n-i+1
[填空题]
15除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为（），每个结点可有任意多个前驱和后继结点数的结构为（）。
参考答案：
线性结构；非线性结构
[填空题]
16数据结构中的数据元素存在多对多的关系称为（）。
参考答案：
图状结构
[填空题]
17数据结构中的数据元素存在一对多的关系称为（）。
参考答案：
树形结构
[填空题]
18在一个单链表中p所指结点之后插入一个s所指结点时，应执行（）和p->next=s；的操作。
参考答案：
s->next=p->next；
[填空题]
19设有一个头指针为head的单向循环链表，p指向链表中的结点，若p->next=（），则p所指结点为尾结点。
参考答案：
head
[填空题]
20设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next= =NULL，通过操作（），就可使该单向链表构形成单向循环链表。
参考答案：
p->next=head；
[填空题]
21线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。
其逻辑顺序和物理存储顺序不再一致，而是一种（）存储结构，又称为（）。
参考答案：
链式；链表
更多内容请访问《睦霖题库》微信公众号
[填空题]
22解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。
参考答案：
顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。
优点：
一般情况下，存储密度大，存储空间利用率高。
缺点：
（1）在做插入和删除操作时，需移动大量元素；
（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；
（3）表的容量难以扩充。
链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。
优点：
插入和删除元素时很方便，使用灵活。
缺点：
存储密度小，存储空间利用率低。
[填空题]
23下列是用尾插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。
参考答案：
p->data=i；p->next=NULL；q->next=p；q=p
[填空题]
24下列是在具有头结点单向链表中删除第i个结点的算法，请在空格内填上适当的语句。
参考答案：
q=q->next；p=q->next；q->next=p->next
[填空题]
25下列是在具有头结点单向列表中在第i个结点之前插入新结点的算法，请在空格内填上适当的语句。
参考答案：
（NODE *）malloc（sizeof（NODE））；p->next=q->next；q->next=p
[单项选择题]
26、一个队列的入队序列是1，2，3，4。
则队列的输出序列是（）。
A. 3，2，4，1
B. 1，2，3，4
C. 4，3，2，1
D. 1，4，3，2
参考答案：
B
[单项选择题]
27、向顺序栈中压入新元素时，应当（）。
A. 先存入元素，再移动栈顶指针
B. 先移动栈顶指针，再存入元素
C. 先后次序无关紧要
D. 同时进行
参考答案：
B
[单项选择题]
28、判断一个顺序队列（最多元素为m）为空的条件是（）。
A.rear==m-1
B.front==rear+1
C.front==rear
参考答案：
C
[单项选择题]
29、判断栈满（元素个数最多n个）的条件是（）。
A.top==0
B.top!
=0
C.top=-1
D.top==n-1
参考答案：
D
[单项选择题]
30、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。
A.队列
B.先性表
C.数组
D.堆栈
参考答案：
A
[单项选择题]
31、一个递归算法必须包括（）。
A.递归部分
B.迭代部分
C.终止条件和迭代部分
D.终止条件和递归部分
参考答案：
D
[单项选择题]
32、在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（）。
A.s->next=r；r=s；
B.r->next=s；r=s；
C.s->next=f；f=s；
D.f->next=s；f=s；
参考答案：
B
[单项选择题]
33、数组a经初始化chara[]=“English”；a[7]中存放的是（）。
A."h"
B.字符串的结束符
C.变量h
D.字符h
参考答案：
B
[单项选择题]
34、设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（）。
A.BCd
B.Bcd
C.Abc
D.ABC
参考答案：
B
[单项选择题]
35、两个字符串相等的条件是（）。
A.两串的长度相等，并且对应位置上的字符相同
B.两串的长度相等
C.两串的长度相等，并且两串包含的字符相同
D.两串包含的字符相同
参考答案：
A
[单项选择题]
36、一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（）。
A.64
B.90
C.28
D.70
参考答案：
D
[单项选择题]
37、对稀疏矩阵进行压缩存储，可采用三元组表，一个10行8列的稀疏矩阵A共有73个零元素，A的右下角元素为6，其相应的三元组表中的第7个元素是（）。
A.（10，8，7）
B.（10，8，6）
C.（7，10，8）
D.（7，8，10）
参考答案：
B
[单项选择题]
38、对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，并给该结点赋值a，则执行：
p=（structnode*）malloc（sizeof（structnode））；p->data=a；和（）。
A.p->next=top；p=top；
B.top->next=p；p=top；
C.p->nex=top；top=p；
D.top=top->next；pe=top；
参考答案：
C
[单项选择题]
39、数组a经初始化chara[]=“English”；a[1]中存放的是（）。
A."n"
B.字符n
C."E"
D.字符E
参考答案：
B
[填空题]
40循环队列队头指针在队尾指针（）位置，队列是“满”状态。
参考答案：
下一个
[填空题]
41判断一个循环队列LU（最多元素为m）为空的条件是（）。
参考答案：
LU->front==LU->rear
[填空题]
42向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行（）和（）操作。
（结点的指针域为next）
参考答案：
s->next=h；h=s；
[填空题]
43串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是（）。
参考答案：
字符
[填空题]
44空串的长度是（）。
参考答案：
0
[填空题]
45设有n阶对称矩阵A，用数组s进行压缩存储，当i≥j时，A的数组元素aij相应于数组s的数组元素的下标为（）。
（数组元素的下标从1开始）
参考答案：
i（i-1）/2+j
[填空题]
46对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的（）、（）和（）三项信息。
参考答案：
行下标；列下标；非零元素值
[填空题]
47环队列的引入，目的是为了克服（）。
参考答案：
假上溢
[填空题]
48栈、队列和线性表的区别是什么？
参考答案：
栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。
队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。
[填空题]
49设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是多少？
参考答案：
出队序列是e2，e4，e3，e6，e5，e1的过程：
（1）e1入栈（栈底到栈顶元素是e1）
（2）e2入栈（栈底到栈顶元素是e1，e2）
（3）e2出栈（栈底到栈顶元素是e1）
（4）e3入栈（栈底到栈顶元素是e1，e3）
（5）e4入栈（栈底到栈顶元素是e1，e3，e4）
（6）e4出栈（栈底到栈顶元素是e1，e3）
（7）e3出栈（栈底到栈顶元素是e1）
（8）e5入栈（栈底到栈顶元素是e1，e5）
（9）e6入栈（栈底到栈顶元素是e1，e5，e6）
（10）e6出栈（栈底到栈顶元素是e1，e5）
（11）e5出栈（栈底到栈顶元素是e1）
（12）e1出栈（栈底到栈顶元素是空）
栈中最多时有3个元素，所以栈S的容量至少是3。
[填空题]
50简述广义表和线性表的区别和联系。
参考答案：
广义表是线性表的的推广，它也是n（n>0）个元素a1，a2，…，ai，…，an的有限序列，其中ai或者是原子或者是一个广义表。
所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。
[单项选择题]
51、假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。
A.17
B.16
C.15
D.47
参考答案：
B
[单项选择题]
52、将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。
A.35
B.33
C.34
D.36
参考答案：
C
[单项选择题]
53、如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。
A.平衡二叉树
B.完全二叉树
C.二叉树
D.哈夫曼树
参考答案：
D
[单项选择题]
54、在一棵度具有5层的满二叉树中结点总数为（）。
A.31
B.32
C.16
D.33
参考答案：
A
[单项选择题]
55、利用n个值作为叶结点的权生成的哈夫曼树中共包含有（）个结点。
A.n+1
B.2*n
C.n
D.2*n-1
参考答案：
D
[单项选择题]
56、在一棵树中，（）没有前驱结点。
A.叶结点
B.空结点
C.树根结点
D.分支结点
参考答案：
C
[单项选择题]
57、设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（）个结点。
A.2n-1
B.2n+2
C.2n+1
D.2n
参考答案：
A
[单项选择题]
58、邻接表是图的一种（）。
A.索引存储结构
B.顺序存储结构
C.散列存储结构
D.链式存储结构
参考答案：
D
[单项选择题]
59、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。
A.一棵树
B.有回路
C.完全图
D.连通图
参考答案：
D
[填空题]
60结点的度是指结点所拥有的（）。
参考答案：
子树树木或后继结点数
升级会员 