电子科大20春《数据结构》在线作业1

大连理工大学网络教育学院2020年春《数据结构》期末考试复习题☆注意事项：本复习题满分共：200分。

一、单项选择题1、在队列中存取数据的原则是（）。

A．先进先出B．后进先出C．先进后出D．随意进出2、在下列链表中，不能从当前结点出发访问到其余各结点的是（）。

A．单链表B．单循环链表C．双向链表D．双向循环链表3、在一棵二叉树上第5层的结点数最多为（）设树根为第1层。

A．16 B．15 C．8 D．324、一棵有124叶子结点的完全二叉树，最多有（）个结点。

A．247 B．249 C．248 D．1255、具有10个叶子结点的二叉树中有（）个度为2的结点。

A．8 B．9 C．10 D．116、若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（）。

A．gdbehfca B．bdgaechfC．gdbecfha D．gcefhabd7、对线性表进行顺序查找时，要求线性表的存储结构是（）。

A．倒排表B．索引表C．顺序表或链表D．散列表8、对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用折半查找，则查找元素26的查找长度为（）。

A．2 B．3 C．4 D．59、在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的是（）。

A．希尔排序B．起泡排序C．插入排序D．选择排序10、堆的形状是一棵（）。

A．二叉排序树B．满二叉树C．完全二叉树D．平衡二叉树11、线性表采用顺序存储结构时，其地址（）。

A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以12、在栈中存取数据的原则是（）。

A．先进先出B．后进先出C．后进后出D．随意进出13、插入和删除只能在一端进行的线性表，称为（）。

A．队列B．循环队列C．栈D．数组14、一个基本线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）。

1.算符文法是指（）的文法。

①没有形如U：：=...VW...的规则(U，V，W ∈VN)②终结符号集VT中任意两个符号对之间至多有一种优先关系成立③没有相同的规则右部④没有形如U：：= ε的规则。

A.①B.①②C.①②③D.①②③④【参考答案】: A2.高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。

A.自左至右B.自顶向下C.自底向上D.自右向左【参考答案】: B3.在编译程序中，语法分析分为自顶向下分析和自底向上分析两类：采用自顶向下分析方法时，要求文法中不含有（）。

A.右递归B.左递归C.直接右递归D.直接左递归【参考答案】: B4.素短语是指（）的短语。

①至少包含一个符号②至少包含一个终结符号③至少包含一个非终结符号④除自身外不再包含其他终结符号⑤除自身外不再包含其他非终结符号⑥除自身外不再包含其他短语⑦除自身外不再包含其他素短语。

A.②⑦B.①④C.①⑤D.①⑥【参考答案】: A5.LR(1)分析法的名字中，“1”的含义是（）。

A.自右向左进行分析B.采用最右推导的逆过程——最左归约C.向貌似句柄的符号串后查看1个输入符号D.自左向右进行分析【参考答案】: C6.己知文法G[S]:S->eT|RT，T->DR|ε，R->dR|ε，D->a|bd。

FIRST(S)=（）。

A.{d，ε}B.{a, b, d, e，ε}C.{a，b}D.{a，b，#}E.{a,b，ε}F.{#}【参考答案】: B7.编译程序中的语法分析器接受以（）为单位的输入，并产生有关信息供以后各阶段使用。

A.表达式B.产生式C.单词D.语句【参考答案】: C8.编译方法中自顶向下的语法分析算法有（）①简单优先分析方法②算符优先分析方法③递归子程序法④LL(K)分析方法⑤SLR方法⑥LR(K)方法⑦LALR(K)方法⑧预测分析方法。

A.①②③⑧B.④⑤⑥⑦C.①②⑤⑥⑦D.③④⑧E.③④⑦⑧F.③④【参考答案】: D9.词法分析器的输出结果是（）。

数据结构试卷（一）一、单选题（每题 2 分，共20分）1.栈和队列的共同特点是( A )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( D ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( D )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

CA．688 B．678 C．692D．6965.树最适合用来表示( C )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( D ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( D )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为CA. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（D）个A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：正确性易读性强壮性和_高效率。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为___0(n)_____。

20春《数据结构》在线作业1
试卷总分:100 得分:100
一、单选题 (共 16 道试题,共 48 分)
1.通常将链串的结点大小设置为大于1是为了（）。

A.提高存储密度
B.提高串匹配效率
C.便于插入操作
D.便于删除操作
答案:B
2.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需（）。

A.视情况而定
B.后移一个位置
C.前移一个位置
D.不动
答案:C
3.在计算机内实现递归算法时所需的辅助数据结构是（）。

A.队列
B.树
C.栈
D.图
答案:C
4.下面程序段的时间复杂度是（）。

for(i=0;i<n;i++) for(j=1;j<m;j++) A[i][j]=0；
A.O(n)
B.O(m+n+1)
C.O(m+n)
D.O(m*n)
答案:D
5.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）。

A.5，6，4，2，3，1
B.3，4，2，1，6，5
C.3，2，6，1，4，5
D.1，2，5，3，4，6
答案:B
6.已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（）。

A.9
B.8
C.7。

科目名称：大工20春《数据结构》在线作业1学校名称：奥鹏-大连理工大学一、单选题 (共 10 道试题,共 50 分)1.以下选项属于非线性结构的是( )。

A.广义表B.队列C.优先队列D.栈提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：A2.在存储数据时,通常不仅需要存储数据元素的值,还要存储( )。

A.数据元素的类型B.数据的基本运算C.数据元素之间的关系D.数据的存取方式提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：C3.以下选项属于逻辑结构的是( )。

A.顺序表B.散列表C.有序表D.单链表提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：C4.一个递归算法必须包括( )。

A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：B5.算法的时间复杂度与( )有关。

A.问题规模B.计算机硬件的运行速度C.源程序的长度D.编译后执行程序的质量提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：A6.静态链表与动态链表相比较,其缺点是( )。

A.插入和删除需移动较多数据B.有可能浪费较多存储空间C.不能随机存取D.以上都不是提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：B7.链式栈和顺序栈相比,有一个比较明显的优点,即( )。

A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：B8.链式栈的栈顶在链表的( )位置。

A.链头B.链尾C.链中D.任意提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：A9.栈和队列具有相同的( )。

A.逻辑结构B.存储结构C.存取点D.运算提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：A10.计算机操作系统为了实现进程管理,采用了多种进程调度策略,先来先服务的策略使用了( )作为算法实现的基础。

1.下列操作中不是数据操作的是()。

A.删除B.排序C.构造D.查找【参考答案】: C2.在计算机系统中，操作系统是()。

A.处于裸机之上的第一层软件B.处于硬件之下的低层软件C.处于应用软件之上的系统软件D.处于系统软件之上的用户软件【参考答案】: A3.栈中输入A，B，C，D，E，F六个字符，出栈顺序是()。

A.ABCDEFB.FEDCBAC.AFECBD.FABCDE【参考答案】: B4.C语言的基本数据类型不包括A.doubleB.intC.floatD.char【参考答案】: A5.下列哪个不是线性结构()。

A.链表B.队列C.串D.树【参考答案】: D6.图的遍历有()。

A.广度优先搜索遍历B.深度优先搜索遍历C.前序遍历D.后序遍历【参考答案】: AB7.内存分配常采用的策略有()。

A.首次适用算法B.最佳适用算法C.最坏适用算法D.中等适用算法【参考答案】: ABC8.C语言的基本数据类型包括()。

A.doubleB.intC.floatD.char【参考答案】: BCD9.进程管理应具有以下功能()。

A.进程控制B.进程同步C.进程通信D.进程调度【参考答案】: ABCD10.对作业调度算法的选择要考虑三个目标是()。

A.尽量提高系统的作业吞吐量，即每天处理尽可能多的作业B.尽量使CPU 和外部设备保持忙碌状态，以提高资源利用率C.对各种作业公平合理，使用有用户都满意D.减少作业运行次数【参考答案】: ABC11.数据结构的三层次是()。

A.数据的逻辑结构B.数据的存储结构C.数据的操作集合D.非线性结构【参考答案】: ABC12.进程控制原语包括()。

A.创建原语B.撤销原语C.阻塞原语D.唤醒原语【参考答案】: ABCD13.作业的状态分为()。

A.进入状态B.后备状态C.运行状态D.完成状态【参考答案】: ABCD14.数据的逻辑结构包括()。

A.线性结构B.非线性结构C.算数结构D.几何结构【参考答案】: AB15.分时系统中作业的控制有哪些()。