电子科大19春《数据结构》在线作业2

国家开放大学电大《数据结构》网络课形考任务2作业及答案形考任务2一、单项选择题（每小题2分，共50分）题目1若让元素1，2，3依次进栈，则出栈顺序不可能为（）。

选择一项：A. 3，1，2题目2一个队列的入队序列是1，2，3，4。

则队列的输出序列是（）。

选择一项：D. 1，2，3，4题目3向顺序栈中压入新元素时，应当（）。

选择一项：D. 先移动栈顶指针，再存入元素题目4在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。

选择一项：C. p->next=top;top=p;题目5在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（）。

选择一项：A. x=top->data;top=top->next;题目6判断一个顺序队列（最多元素为m）为空的条件是（）。

选择一项：A. front==rear题目7判断一个循环队列为满的条件是（）。

选择一项：B. (rear+1)%MaxSize==front题目8判断栈满（元素个数最多n个）的条件是（）。

选择一项：A. top==n-1题目9设有一个20阶的对称矩阵A（第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵元素a6,2在一维数组B中的下标是（）。

选择一项：A. 17题目10在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。

选择一项：D. 队列题目11一个递归算法必须包括（）。

选择一项：D. 终止条件和递归部分题目12在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）。

选择一项：A. f=f->next;题目13在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（）。

电子科技大学19秋《数据结构》在线作业2
试卷总分:100 得分:100
【题目】若算法中语句的最大频度为T(n)=2006n+6n㏒n+29㏒2n,则其时间复杂度为（）。

[A.]O(㏒n)
[B.]O(n)
[C.]O(n㏒n)
[D.]O(㏒2n)
[分析以上题目，并完成作答]
正确答案:C
【题目】若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（）。

[A.]无头结点的双向链表
[B.]带尾指针的循环链表
[C.]无头结点的单链表
[D.]带头指针的循环链表
[分析以上题目，并完成作答]
正确答案:B
【题目】如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）。

[A.]栈
[B.]队列
[C.]树
[D.]图
[分析以上题目，并完成作答]
正确答案:C
【题目】判断两个串大小的基本准则是（）。

[A.]两个串长度的大小
[B.]两个串中首字符的大小
[C.]两个串中大写字母的多少
[D.]对应的第一个不等字符的大小
[分析以上题目，并完成作答]
正确答案:B
【题目】已知栈的最大容量为4。

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）。

[A.]5，4，3，2，1，6
[B.]2，3，5，6，1，4
[C.]3，2，5，4，1，6
[D.]1，4，6，5，2，3
[分析以上题目，并完成作答]。

(单选题)1: 对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分。

在第一趟划分过程中，元素移动次数最多的序列是()。

A: 82，75，70，16，10，90，68，23B: 23，10，16，70，82，75，68，90C: 70，75，68，23，10，16，90，82D: 70，75，82，90，23，16，10，68正确答案:(单选题)2: 算法分析的两个主要方面是（）。

A: 空间复杂度和时间复杂度B: 正确性和简明性C: 可读性和文档性D: 数据复杂性和程序复杂性正确答案:(单选题)3: 若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为( )。

A: 10，15，14，18，20，36，40，21B: 10，15，14，18，20，40，36，21C: 10，15，14，20，18，40，36，21D: 15，10，14，18，20，36，40，21正确答案:(单选题)4: 设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（）。

A: 3700B: 4376C: 3900D: 4620正确答案:(单选题)5: 若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。

A: 3，2，1B: 2，1，3C: 3，1，2D: 1，3，2正确答案:(单选题)6: 下列那种排序需要的附加存储开销最大（）。

A: 快速排序B: 堆排序C: 归并排序D: 插入排序正确答案:(单选题)7: 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。

A: O（nlog2e）B: O（n+e）C: O(n*e)D: O(n*n)正确答案:(单选题)8: 设无向图的顶点个数为n，则该图最多有（）条边。

A: n-1B: n(n-1)/2C: n(n+1)/2D: 0(单选题)9: 队列的删除操作是在（）进行。

数据结构试卷（一）一、单选题（每题 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)_____。

国家开放大学2019年春季学期期末统一考试数据结构(本)试题2019年7月一、单项选择题(每小题3分，共30分)1.以下说法正确的是( )。

A.在顺序表中可以随机访问任一结点B.一种逻辑结构在存储时只能采用一种存储结构C.对链表进行插入、删除元素的操作一定要移动结点D.在链表中可以随机访问任一结点参考答案：在顺序表中可以随机访问任一结点2.线性表在存储后，如果要求：仅通过已知的指向第i个结点的指针，进行相关操作，访问到该结点的前驱结点，则采用( )存储方式是不可行的。

A.单链表B.双链表C.单循环链表D.顺序表参考答案：单链表3.栈和队列的共同特点是( )。

A.都是先进后出B.元素都可以随机进出C.只容许在端点处插人和删除元素D.都是先进先出参考答案：只容许在端点处插人和删除元素4.元素4，6，8，10按顺序依次进栈，按该栈的可能输出序列依次人队列，该队列的可能输出序列是( )(进栈出栈可以交替进行)。

A.10，8，4，6 C.8，4，6，10B.10，6，4，8 D.10，8，6，4参考答案：10，8，6，45.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，从该队列中进行出队操作，并把结点的值保存在变量x中的操作为( )。

A.x=r->data；r=r->next；B.r一r一>next；x=r一>data；C.x=f~>data；f=f->next；D.f一f->next；x-f一>data；参考答案：x=f~>data；f=f->next；6.设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存到一维数组B中(数组下标从1开始)，则矩阵元素ag.2对应于数组B 中第( )号元素。

(矩阵中的第1个元素是a1.1)A.42B.39C.38D.40参考答案：387.一棵采用链式存储的二叉树中，共有n一1个指针域被有效使用(即指针域为非空)。

【奥鹏】19春华师《数据结构》在线作业
试卷满分:100 试卷得分:100
一、单选题（共30题，60分）
1、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为()。

An
Bn+1
Cn-l
Dn十e
[仔细阅读以上试题，并作出选择]
正确选择：A
2、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是()。

Aacbed
Bdecab
Cdeabc
Dcedba
[仔细阅读以上试题，并作出选择]
正确选择：D
3、稀疏矩阵一般的压缩存储方法有两种，即()。

A二维数组和三维数组
B三元组和散列
C三元组和十字链表
D散列和十字链表
[仔细阅读以上试题，并作出选择]
正确选择：C
4、一个栈的人栈序列是a，b，c，d，e，则栈的不可能的输出序列是()
Aedcba
Bdecba
Cdceab
Dabcde
[仔细阅读以上试题，并作出选择]
正确选择：C
5、广义表A=(()，(a)，(b，(c，d)))的深度为()
A2
B3
C4
D5
[仔细阅读以上试题，并作出选择]
正确选择：B。

(单选题)1: 关于网络体系结构，以下哪种描述是错误的？A: 物理层完成比特流的传输B: 数据链路层用于保证端到端数据的正确传输C: 网络层为分组通过通信子网选择适合的传输路径D: 应用层处于参考模型的最高层正确答案:(单选题)2: IEEE802.11使用的传输技术为( )。

A: 红外、跳频扩频与蓝牙B: 跳频扩频、直接序列扩频与蓝牙C: 红外、直接序列扩频与蓝牙D: 红外、跳频扩频与直接序列扩频正确答案:(单选题)3: 在网络操作系统的发展过程中，最早出现的是( )。

A: 对等结构操作系统B: 非对等结构操作系统C: 客户机/服务器操作系统D: 浏览器/服务器操作系统正确答案:(单选题)4: 在计算机网络中，联网计算机之间的通信必须使用共同的( )。

A: 体系结构B: 网络协议C: 操作系统D: 硬件结构正确答案:(单选题)5: 网络协议精确地规定了交换数据的( )。

A: 格式和结果B: 格式和时序C: 结果和时序D: 格式、结果和时序正确答案:(单选题)6: 如果一个用户通过电话网将自己的主机接入因特网，以访问因特网上的Web站点，那么用户不需要在这台主机上安装和配置( )。

A: 调制解调器B: 网卡C: TCP/IP协议D: WWW浏览器正确答案:(单选题)7: 我们将文件从FTP服务器传输到客户机的过程称为( )。

B: 上传C: 浏览D: 邮寄正确答案:(单选题)8: 因特网用户利用电话网接入ISP时需要使用调制解调器，其主要作用是( )。

A: 进行数字信号与模拟信号之间的变换B: 同时传输数字信号和语音信号C: 放大数字信号，中继模拟信号D: 放大模拟信号，中继数字信号正确答案:(单选题)9: 关于WWW服务系统，以下哪种说法是错误的？A: WWW服务采用服务器/客户机工作模式B: 页面采用HTTP书写而成C: 客户端应用程序通常称为浏览器D: 页面到页面的链接信息由URL维持正确答案:(单选题)10: 在Windows?2000家族中，运行于客户端的通常是( )。

【奥鹏】-[四川大学]《数据结构2264》19秋在线作业2试卷总分:100 得分:100第1题,若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。

则该二叉树结点的前序遍历的序列为（）。

A、E、G、F、A、C、D、BB、E、A、G、C、F、B、DC、E、A、C、B、D、G、FD、E、G、A、C、D、F、B正确答案:C第2题,AOV网是一种（）。

A、有向图B、无向图C、无向无环图D、有向无环图正确答案:D第3题,队列的特点是（）。

A、先进后出B、先进先出C、任意位置进出D、前面都不正确正确答案:B第4题,设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（）。

A、m-n-1B、n+1C、m-n+1D、m-n正确答案:D第5题,从L=（）,（）)中，取出banana元素的表达式为（）。

A、head(tail(L))B、head(head(tail(L)))C、tail(head(tail(L)))D、head(tail(head(tail(L))))正确答案:D第6题,带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（）。

A、head= =NULB、head-next= =NULLC、head!=NULLD、head-next= =head正确答案:D第7题,以下数据结构中哪一个是非线性结构？（）A、队列B、栈C、线性表D、二叉树正确答案:D第8题,在数据结构中，数据元素可由（）。

A、实体B、域C、数据项D、字段正确答案:C第9题,在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（）。

A、iB、i+1C、n-iD、n-i+1正确答案:C第10题,已知一个图的顶点集V={1,2,3,4,5,6,7}；边集E={（）3, （）5, （）8, （）10, （）6, （）15, （）12, （）9, （）4, （）20, （）18, （）25}，用克鲁斯卡尔算法得到最小生成树，则在最小生成树中依次得到的各条边为（）。

（精华版）国家开放大学电大《数据结构》网络课形考网考作业及答案100%通过考试说明：2020年秋期电大把该网络课纳入到“国开平台”进行考核，该课程共有4个形考任务，针对该门课程，本人汇总了该科所有的题，形成一个完整的标准题库，并且以后会不断更新，对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。

做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。

本文库还有其他网核及教学考一体化答案，敬请查看。

课程总成绩=形成性考核X50% +终结性考试X 50%形考任务1一、单项选择题（每小题3分，共60分）题目1把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）o选择一项：D.物理结构题目2下列说法中，不正确的是（）o选择一项：C.数据项可由若干个数据元素构成题目3一个存储结点存储一个（）。

选择一项：C.数据元素题目4数据结构中，与所使用的计算机无关的是数据的（）。

选择一项：C.逻辑结构题目5在线性表的顺序结构中，以下说法正确的是（）o选择一项：D.逻辑上相邻的元素在物理位置上也相邻题目6对链表，以下叙述中正确的是（）o选择一项：C.不能随机访问任一结点题目7下列的叙述中，不属于算法特性的是（)o选择一项：C.可读性题目8算法的时间复杂度与（）有关。

选择一项：D.算法本身题目9的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动设有一个长度为n元素个数为（）0选择一项：C. n-i+1题目10设有一个长度为的顺序表，要删除第i个元素移动元素的个数为（）on选择一项：C. n-i题目11在一个单链表中，P、q分别指向表中两个相邻的结点，且q所指结点是P所指结点的直接后继，现要删除q所指结点, 可用语句（）。

选择一项：A.p->next=q->next题目12在一个单链表中P所指结点之后插入一个s所指的结点时，可执行（）。

杭州电子科技大学数据结构数据结构试题及答案一、选择题1. 下面哪一个不是线性结构的特点？（）A. 有且只有一个根结点B. 每个结点最多有一个前驱，最多有一个后继C. 至少有一个结点D. 结构中任意两个结点都可以相邻答案：D解析：线性结构的特点包括有且只有一个根结点，每个结点最多有一个前驱，最多有一个后继，至少有一个结点。

而结构中任意两个结点都可以相邻并不是线性结构的特征。

2. 下面关于栈的叙述中，正确的是（）A. 栈是一种先进先出的线性表B. 栈是一种后进先出的线性表C. 栈是一种随机存取的线性表D. 栈是一种非线性结构答案：B解析：栈是一种后进先出的线性表，即最后进入的元素最先被删除。

二、填空题3. 一个栈的初始状态为空。

首先将元素5、3、2依次进栈，然后退栈一次，再进栈一个元素6，然后再退栈三次，此时栈顶元素的值为______。

答案：2解析：元素进栈的顺序是5、3、2，退栈一次后栈顶元素是3，再进栈一个元素6，栈顶元素变为6，退栈三次后，栈顶元素是2。

4. 设栈S和队列Q的初始状态都为空。

元素a、b、c、d、e依次进栈S，然后再依次出栈，并将出栈的元素放入队列Q 中，则队列Q的元素顺序是______。

答案：e d c b a解析：元素a、b、c、d、e依次进栈后，出栈顺序是e、d、c、b、a，因此队列Q的元素顺序也是e、d、c、b、a。

三、判断题5. 在链表中，存储结点包含数据域和指针域两部分。

（）答案：正确解析：链表中的每个存储结点确实包含数据域和指针域两部分，其中数据域存储元素值，指针域存储下一个结点的地址。

6. 二分查找法适用于顺序存储的有序表。

（）答案：正确解析：二分查找法只适用于顺序存储的有序表，因为它是通过比较中间元素与目标值的大小来逐步缩小查找范围的。

四、应用题7. 设有一个长度为12的线性表，元素依次为（a1, a2, a3, ..., a12），采用二分查找法查找元素a7，请写出查找过程。

《数据结构》在线作业二
试卷总分:100 得分:100
一、单选题 (共 40 道试题,共 100 分)
1.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（）。

A.P，A，C，S，Q，D，F，X，R，H，M，Y
B.H，C，Q，P，A，M，S，R，D，F，X，Y
C.F，H，C，D，P，A，M，Q，R，S，Y，X
D.A，D，C，R，F，Q，M，S，Y，P，H，X
答案:B
2.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。

A.5，3，4，6，1，2
B.3，2，5，6，4，1
C.3，1，2，5，4，6
D.1，5，4，6，2，3
答案:B
3.数组的逻辑结构不同于下列（??）的逻辑结构。

A.队列
B.线性表
C.树
D.栈
答案:C
4.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。

A.top=top->next;
B.top=top-1;
C.top=top+1;
D.top->next=top;
答案:A
5.一个有n个顶点的无向图最多有（）条边。

A.n(n-1)/2
B.n(n-1)
C.n
D.2n
答案:A
6.设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。

A.A[7]，A[5] ，A[3]，A[4]
B.A[7]，A[3]，A[5]，A[4]
C.A[1]，A[2]，A[3]，A[4]。

一、单项选择题1．C 2．D 3．B 4．C 5．D 6．C 7．B 8．C 9．A 10．B11．C 12．D 13．C 14．A 15．B 16．C 17．C 18．B 19．B 20．D 二、填空题1．n-i+12．n-i3．集合线性结构树形结构图状结构4．物理结构存储结构5．线性结构非线性结构6．有穷性确定性可形性有零个或多个输入有零个或多个输出7．图状结构8．树形结构9．线性结构10．n-1 O(n)11．s->next=p->next;12．head13．q->next=p->next;14．p->next=head;15．单链表16．顺序存储链式存储17．存储结构18．两个直接后继直接前驱尾结点头结点19．头结点的指针指向第一个结点的指针20．链式链表三、问答题1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。

数据在计算机中的存储表示称为数据的存储结构。

可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。

尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。

采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。

2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。

答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。

优点：一般情况下，存储密度大，存储空间利用率高。

缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。

链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。

大工19春《数据结构》在线作业2【标准答案】(总3页)本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March大工19春《数据结构》在线作业2试卷总分:100 得分:0一、单选题 (共 10 道试题,共 50 分)1.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2.假定一棵度为3的树中结点总数为50,则其最小高度为( )。

3.一棵二叉树中有35个结点,其中所有结点的度之和是( )。

4.一棵高度为8的完全二叉树至少有( )叶子结点。

5.某二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树一定是( )。

A.空B.完全二叉树C.二叉排序树D.高度等于其结点数6.如果二叉树T2是由一棵树T1转换而来的二叉树,那么T1中结点的先根序列对应T2的( )序列。

A.先序遍历B.中序遍历C.后序遍历D.层次遍历7.若一棵二叉树的先序遍历序列为efhigjk,中序遍历序列为hfiejkg,则该二叉树根结点的右孩子为( )。

8.若一棵二叉树的先序遍历序列为abcdef,中序遍历的序列为cbaedf,则后序遍历的结果为( )。

D.不确定9.一棵线索二叉树中含有的线索数比分支数多( )个。

D.不确定10.一棵满二叉树共有64个叶子结点,则其深度为( )。

二、判断题 (共 10 道试题,共 50 分)1.度为2的有序树就是二叉树。

A.对B.错2.二叉树的顺序存储只能从下标1的位置开始存放。

A.对B.错3.在任意一棵二叉树中,非叶结点的数目一定小于叶结点的数目。

A.对B.错4.使用先序遍历算法可以求得二叉树的深度。

A.对B.错5.二叉树的遍历是对一个非线性结构的元素做线性化排列的过程。

A.对B.错6.在二叉树的先序遍历序列中,任一结点均处在其子树结点前面。

A.对B.错7.从二叉树的先序遍历序列和中序遍历序列可以导出二叉树的后序遍历序列。

国家开放大学电大《数据结构》网络课形考任务2作业及答案档任务2一、单项选择题（每小题2分，共50分）题目1 若让元素1,2,3依次进栈，则出栈顺序不可能为（）。

选择一项： A、3,1,2 B、3,2,1 C、2,1,3 D、1,3,2 题目2 一个队列的入队序列是1,2,3,4。

则队列的输出序列是（）» 选择一项： A、1,4,3,2 B、4,3,2,1 C、3,2,4,1 D、1,2,3,4 题目3 向顺序栈中压入新元素时，应当（）。

选择一项： A、先后次序无关紧要 B、先存入元素，再移动栈顶指针 C、同时进行 D、先移动栈顶指针，再存入元素题目4 在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）、选择一项： A、 p->next=top->next;top->next=p: B、 p->next=top->next;top=top->next; C、 p->next=top:top=p: D、 top->next=p; 题目5 在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。

选择一项： A、 x=top->data;top=top->next: B、top=top->next;x=top->data; C、 x=top->data： D、 x=top：top=top->next; 题目6 判断一个顺序队列（最多元素为m）为空的条件是（）» 选择一项： A、 front=rear B、 front=rear+l C、 rear=m-l D、 rear=m 题目7 判断一个循环队列为满的条件是（）next; B、 r=r->next; C、 r=f->next; D、 f=r->next; 题目13 在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（）» 选择一项： A、 r->next=s;r=s; B、 s->next=f;f=s; C、 s->next=r;r=s; D、 f->next=s;f=s：题目14 数组a经初始化char a[ ]= “English” ：a[7]中存放的是（）。

东大19秋学期《数据结构Ⅱ》在线平时作业2
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.数据的四种基本存储结构是指
A.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
B.顺序存储结构、链式存储结构、树型存储结构、图型存储结构
C.顺序存储结构、索引存储结构、链式存储结构、散列存储结构
D.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
【运用所学知识，完成上述题目】
参考选择:C
2.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是
A.4，3，2，1，5，6
B.3，2，4，1，6，5
C.2，4，3，1，5，6
D.2，3，5，1，6，4
【运用所学知识，完成上述题目】
参考选择:D
3.有关二叉树下列说法正确的是
A.二叉树的度为2
B.二叉树中至少有一个结点的度为2
C.二叉树中任何一个结点的度都为2
D.一棵二叉树的度可以小于2
【运用所学知识，完成上述题目】
参考选择:D
4.算法分析的目的是
A.鉴别算法的可读性
B.辨别数据结构的合理性
C.评价算法的效率
D.研究算法中输入与输出的关系
【运用所学知识，完成上述题目】
参考选择:C
5.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为
A.X的左子树中最右结点
B.X的左子树中最右叶结点
C.X的右子树中最左的结点
D.X的双亲
【运用所学知识，完成上述题目】
参考选择:A。

1电子科技大学网络教育考卷（A2卷）(20 年至20 学年度第 学期)考试时间 年 月 日(120分钟) 课程 数据结构(本) 教师签名_____一、名词解释(每题2分，共10分) 1. 线性表2. 静态链表3. 哈夫曼树4. 串5. 图二、判断正误(正确打√，错误划×，每题1分，共10分) 1. 算法是可以直接在计算机上运行的程序。

()2. 链表能够动态分配结点空间。

( )3. 栈只能使用顺序存储结构。

( )4. 二维数组能够实现随机存取。

( )5. 在二叉树的第i 层上至多有2i-1个结点(i ≥1)。

()6. 在无向图中，顶点的度为与该顶点相连的边的个数。

( )7. 邻接表只能用于有向图的存储。

（ ） 8. 有向图不能进行广度优先遍历()9. 平均查找长度 ASL 可作为衡量一个查找算法效率高低的标准。

( ) 10. 所有的内部排序算法都是稳定的。

( )三、填空(每空2分，共10分) 1. 线性表、栈和队列都是()结构。

2. 假设三维数组Rpmn 每个数据元素占L 个存储地址，并以Loc(i,j,k) 表示下标为(i,j,k) 的数据元素的存储地址，各维元素个数为 p, m, n 。

则下标为 i,j,k 的数组元素的存储地址为( )。

3. 队列的出队操作总是在()进行。

4. 按存储结构不同，串可分为( )。

5. 深度为k 的完全二叉树至少有()个结点。

四、选择题(单选或多选)(每题2分，共30分)1. 关于线性结构的说法错误的是( )。

A. 元素间是一对一B. 元素存在唯一直接前趋C. 元素存在唯一直接后继D. 可随机存取2. 设一棵二叉树中，度为2的结点数为9，则该二叉树的叶结点的数目为( )。

A ．10B. 11C. 12D. 不确定3. 在线索二叉树中，ｔ所指结点没有左子树的充要条件是（ ）。

A ．t->Lchild==NullB ．t->Ltag==1 C. t->Ltag==1&&t->Lchild==Null D. 以上都不对4. 关于队列的说法正确的是（ ）A. 先进先出B. 属于非线性结构C. 只能采用顺序存储D.属于散列结构 5. 用单链表表示的链式队列的队尾是在链表的()位置A. 表尾B. 表头C. 表中D. 任意 6. 树的非叶子结点是（ ）。

19春学期《数据结构Ⅰ》在线作业1一棵完全二叉树上有1001个结点，其中叶子结点的个数是A.250B.500C.254D.以上答案都不对正确答案:D顺序存储设计时，存储单元的地址A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续正确答案:A若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为A.f,c,bB.f,d,bC.g,c,bD.g,d,b正确答案:A在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为A.iB.i+1C.n-iD.n-i+1正确答案:C在长度为n的顺序表中删除第i个元素(1in)时，元素移动的次数为A.n-i+1B.iC.i+1D.n-i正确答案:D在线性表的下列运算中，不改变数据元素之间结构关系的运算是A.插入B.删除C.排序D.查找正确答案:D队列和栈的主要区别是A.逻辑结构不同B.存储结构不同C.所包含的运算个数不同D.限定插入和删除的位置不同正确答案:D数组A[1..5，1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为A.1140B.1145C.1120D.1125正确答案:A通常将链串的结点大小设置为大于1是为了A.提高串匹配效率B.提高存储密度C.便于插入操作D.便于删除操作正确答案:B高度为5的完全二叉树中含有的结点数至少为A.16B.17C.31D.32正确答案:A在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为A.4，4，3B.4，3，3C.3，4，4D.3，3，4正确答案:B倒排文件的主要优点是A.便于进行插入和删除运算B.便于进行文件的恢复C.便于进行多关键字查询D.节省存储空间正确答案:C某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则该二叉树对应的森林包括的树的棵树是A.1B.2C.3D.概念上是错误的正确答案:B如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法正确答案:B已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为A.ABCDEFB.ABCEFDC.ABFCDED.ABCDFE正确答案:D数据元素及其关系在计算机存储器内的表示，称为数据的A.逻辑结构B.存储结构C.线性结构D.非线性结构正确答案:B判断两个串大小的基本准则是A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小正确答案:D若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是A.1234B.4132C.4231D.4213正确答案:C一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是A.不确定B.0C.1D.2正确答案:D无向图中一个顶点的度是指图中A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数C.通过该顶点的回路数D.与该顶点连通的顶点数正确答案:D19春学期《数据结构Ⅰ》在线作业2设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是A.A，B，C，DB.D，C，B，AC.A，C，D，BD.D，A，B，C正确答案:D算法的时间复杂度主要取决于A.问题的规模B.待处理数据的初态C.难度D.A和B正确答案:A文件中，主关键字能唯一标识A.一个记录B.一组记录C.一个类型D.一个文件正确答案:A下列程序段for(i=1;i=n;i++)A[i,j]=0;的时间复杂度是A.O(1)B.O(0)C.O(1+n)D.O(n)正确答案:D二叉树中第5层上的结点个数最多为A.8B.15C.16D.32正确答案:C有关二叉树下列说法正确的是A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2正确答案:B抽象数据类型的三个组成部分分别为A.数据对象、数据关系和基本操作B.数据元素、逻辑结构和存储结构C.数据项、数据元素和数据类型D.数据元素、数据结构和数据类型正确答案:A对n个关键字的序列进行快速排序，平均情况下的空间复杂度为A.O(1)B.O(logn)C.O(n)D.O(nlogn)正确答案:D用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为A.5B.6C.8正确答案:A十字链表的三元组表是稀疏矩阵的一种A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构正确答案:B在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是A.G中有弧Vi，VjB.G中有一条从Vi到Vj的路径C.G中没有弧Vi,VjD.G中有一条从Vj到Vi的路径正确答案:D如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为A.插入排序B.归并排序C.冒泡排序D.堆排序正确答案:A在待排关键字序列基本有序的前提下，效率最高的排序方法是A.直接插入排序B.快速排序C.直接选择排序D.归并排序正确答案:A下面关于线性表的叙述中，错误的是A.线性表采用顺序存储，必须占用一片连续的存储单元。

(单选题)1: 门禁系统属于（）系统中的一种安防系统。

A: 智能强电B: 智能弱电C: 非智能强电D: 非智能弱电正确答案:(单选题)2: 不能防止计算机感染病毒的措施是（）A: 定时备份重要文件B: 经常更新操作系统C: 除非确切知道附件内容，否则不要打开电子邮件附件D: 重要部门的计算机尽量专机专用与外界隔绝正确答案:(单选题)3: 我国信息论专家钟义信教授将信息定义为（）。

A: 信息是用来减少随机不定性的东西B: 信息是人们在适应外部世界，且该适应反作用于外部世界的过程中，同外部世界进行互相交换的内容的名称。

C: 信息是反映事物的形式、关系和差别的东西，它包含在事物的差异之中，而不在事物本身。

D: 信息是事物运动的状态和状态变化的方式。

正确答案:(单选题)4: 对于联网型门禁系统，（）也接受来自管理计算机发送的人员信息和相对应的授权信息，同时向计算机传送进出门的刷卡记录A: 读卡器B: 门禁控制器C: 电控锁D: 连接线正确答案:(单选题)5: 关于NAT说法错误的是（）A: NAT允许一个机构专用Intramt中的主机透明地连接到公共域中的主机，元需内部主机拥有注册的(已经越来越缺乏的)全局互联网地址B: 静态NAT是设置起来最简单和最容易实现的一种地址转换方式，内部网络中的每个主机都被永久映射成外部网络中的某个合法的地址C: 动态NAT主要应用于拨号和频繁的远程连接、当远程用户连接上之后，动态NAT就会分配给用户一个IP地址，当用户断开时，这个IP地址就会被释放而留待以后使用D: 动态NAT又叫做网络地址端口转换NAPT正确答案:(单选题)6: RSA算法是一种基于（）的公钥体系。

A: 素数不能分解；B: 大数没有质因数的假设；C: 大数不可能对质因数进行分解假设；D: 公钥可以公开的假设。

正确答案:(单选题)7: A自己的文件乘上随机因子后，再将文件交给B，下面不属于完全盲签名的特点的是（）。

1.下面程序段的时间复杂度为（）。

for (i=0; i<m; i++) for (j=0; j<n; j++) A[i][j]=i*j;A.O (m2)B.O (n2)C.O (m*n)D.O (mn)【参考答案】: C2.已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（）。

A.7B.8C.9D.10【参考答案】: A3.数据结构是（）。

A.一种数据类型B.数据的存储结构C.一组性质相同的数据元素的集合 D.相互之间存在一种或多种特定关系的数据元素的集合【参考答案】: D4.若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（）。

A.无头结点的双向链表B.带尾指针的循环链表C.无头结点的单链表 D.带头指针的循环链表【参考答案】: B5.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需（）。

A.前移一个位置B.后移一个位置C.不动D.视情况而定【参考答案】: A6.对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（）。

A.求一个顶点的邻接点B.求一个顶点的度C.深度优先遍历D.广度优先遍历【参考答案】: B7.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（）。

A.O(1)B.O(n)C.O(n㏒n)D.O(n2)【参考答案】: B8.一棵含18个结点的二叉树的高度至少为（）。

A.3B.4C.5D.6【参考答案】: C9.算法分析的目的是（）。

A.辨别数据结构的合理性B.评价算法的效率C.研究算法中输入与输出的关系D.鉴别算法的可读性【参考答案】: B10.高度为5的完全二叉树中含有的结点数至少为（）。

A.16B.17C.31D.32【参考答案】: A11.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j 的子串，函数Scopy(s,t)的功能为复制串t到s。

若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到（）。