数据结构网上作业

(一) 单选题1. 若已知一个栈的入栈序列是，其输出序列为，若,则为（）。

(A)(B)(C)(D) 不确定参考答案：(C)2. 程序段如下：其中n为正整数，则最后一行的语句频度在最坏情况下是（）。

(A)(B)(C)(D)参考答案：(D)3. 一个栈的入栈序列是，则栈的不可能的输出序列是（）。

(A) adcba(B) decba(C) dceab(D) abcde参考答案：(C)4. 从一个长度为n的顺序表中删除第i个元素时，需向前移动的元素的个数是（）。

(A)(B)(C)(D)参考答案：(A)5. 栈和队列的共同点是（）。

(A) 都是先进先出(B) 都是先进后出(C) 只允许在端点处插入和删除元素(D) 没有共同点参考答案：(C)6. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

(A) 存储结构(B) 逻辑结构(C) 算法(D) 操作参考答案：(B)7. 设广义表，则L的长度和深度分别为（）。

(A) 1和3 (B) 1和1 (C) 1和2 (D) 2和3参考答案：(C)8. 顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（）。

(A)(B)(C)(D)参考答案：(D)9. 在下面的程序段中，对x的赋值语句的频度为（）。

(A)(B)(C)(D)参考答案：(C)10. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（）。

(A) 较快(B) 较慢(C) 相同(D) 不定参考答案：(B)11. 求循环链表中当前结点的后继和前驱的时间复杂度分别是（）。

(A) 和(B) 和(C) 和(D) 和参考答案：(C)12. 数据的基本单位是（）。

(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量参考答案：(A)13. 从逻辑上可以把数据结构分为（）两大类。

(A) 动态结构、静态结构(B) 顺序结构、链式结构(C) 线性结构、非线性结构(D) 初等结构、构造型结构参考答案：(C)14. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（）。

国家开放大学电大《数据结构》网络课形考任务3作业及答案形考任务3一、单项选择题（每小题2分，共38分）题目1假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。

选择一项：B. 16题目2二叉树第k层上最多有（）个结点。

选择一项：A. 2k-1题目3将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。

选择一项：C. 34题目4如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。

选择一项：B. 哈夫曼树题目5在一棵度具有5层的满二叉树中结点总数为（）。

选择一项：C. 31题目6一棵完全二叉树共有6层，且第6层上有6个结点，该树共有（）个结点。

选择一项：B. 37题目7利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（）。

选择一项：A. 18在一棵树中，（）没有前驱结点。

选择一项：A. 树根结点题目9设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有20个指针域为空,则该树有（）个叶结点。

选择一项：B. 10题目10在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。

选择一项：A. 2题目11邻接表是图的一种（）。

选择一项：A. 链式存储结构题目12图的深度优先遍历算法类似于二叉树的（）遍历。

选择一项：A. 先序题目13已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。

选择一项：D. V1V2V4V8V5V3V6V7题目14已知如下图所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。

选择一项：D. aecbdf题目15图状结构中数据元素的位置之间存在（）的关系。

选择一项：B. 多对多在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（）。

国家开放大学电大《数据结构》网络课形考任务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所指结点的运算为（）。

数据结构（本科）武汉理工大学在线作业一、判断(共计40分,每题2.5分)1、快速排序是排序算法中平均性能最好的一种排序。

（）A. 正确B. 错误答案:【A】2、调用一次深度优先遍历可以访问到图中的所有顶点。

（）A. 正确B. 错误答案:【B】3、对连通图进行深度优先遍历可以访问到该图中的所有顶点。

（）A. 正确B. 错误答案:【A】4、线性表中的所有元素都有一个前驱元素和后继元素。

（）A. 正确B. 错误答案:【B】5、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。

（）A. 正确B. 错误答案:【B】6、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。

（）A. 正确B. 错误答案:【A】7、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。

（）A. 正确B. 错误答案:【A】8、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

（）B. 错误答案:【A】9、子串“ABC”在主串“AABCABCD”中的位置为2。

( )A. 正确B. 错误答案:【A】10、非空的双向循环链表中任何结点的前驱指针均不为空。

（）A. 正确B. 错误答案:【A】11、分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

（）A. 正确B. 错误答案:【A】12、线性表的顺序存储结构比链式存储结构更好。

（）A. 正确B. 错误答案:【B】13、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。

（）A. 正确B. 错误答案:【B】14、层次遍历初始堆可以得到一个有序的序列。

（）A. 正确B. 错误答案:【B】15、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。

（）A. 正确B. 错误答案:【A】16、设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。

（）A. 正确B. 错误二、单选(共计60分,每题2.5分)17、在二叉排序树中插入一个关键字值的平均时间复杂度为（）。

电子科技《数据结构》在线作业1
单选题多选题判断题
一、单选题（共 16 道试题，共 48 分。

）
1. 在计算机内实现递归算法时所需的辅助数据结构是（）。

A. 栈
B. 队列
C. 树
D. 图
-----------------选择：A
2. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。

A. 顺序表
B. 用头指针表示的单循环链表
C. 用尾指针表示的单循环链表
D. 单链表
-----------------选择：C
3. 判断两个串大小的基本准则是（）。

A. 两个串长度的大小
B. 两个串中首字符的大小
C. 两个串中大写字母的多少
D. 对应的第一个不等字符的大小
-----------------选择：B
4. 在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是（）。

A. 0
B. 2
C. 3
D. 5
-----------------选择：C
5. 栈和队列都是（）。

A. 限制存取位置的线性结构
B. 顺序存储的线性结构
C. 链式存储的线性结构
D. 限制存取位置的非线性结构
-----------------选择：D
6. 设有两个串T和P，求P在T中首次出现的位置的串运算称作（）。

A. 联接
B. 求子串
C. 字符定位
D. 子串定位
-----------------选择：D
7. 算法分析的目的是（）。

大工15秋《数据结构》在线作业1满分答案大工15秋《数据结构》在线作业1一单选题1.广义表((e))的表头是（）。

A. eB. (e)C. ()D. (())正确答案：B2.在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值。

A. 1B. 2C. 3D. 4正确答案：B3.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。

A. (n+1)/2B. n/2C. nD. n+1正确答案：C4.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。

A. head==NULLB. head→next==NULLC. head→next==headD. head!=NULL正确答案：B5.一个顺序栈S，元素a，b，c，d，e依次进栈，如果5个元素的出栈顺序为b，e，d，c，a，则顺序栈的容量至少应为（）。

A. 2B. 3C. 4D. 5正确答案：C6.在表长为n的顺序表中,若在每个位置插入数据元素的概率相等，插入一个数据元素平均需要移动（）个数据元素。

A. (n-1)/2B. n/2C. n-1D. n正确答案：B7.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（）。

A. cB. b，cC.（b，c）D.（（b，c））正确答案：D8.表达式a*(b+c)-d的后缀表达式是（）。

A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd精确谜底：B9.在一个单链表中，删除*p结点之后的一个结点的操作是（）。

A. p->next=p;B. p->next->next=p->next;C. p->next->next=p;D. p->next=p->next->next;精确谜底：D10.最大容量为n的轮回行列，队尾指针是rear，队头是front，则队空的条件是（）。

西北工业大学21春《数据结构》在线作业一满分答案1. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素。

A.8B.63.5C.63D.7参考答案：B2. 线性链表不具有的特点是( )A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比参考答案：A3. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。

A.2B.3C.8D.9参考答案：C4. 以下关于线性表的说法不正确的是( )。

A.线性表中的数据元素可以是数字、字符、记录等不同类型B.线性表中包含的数据元素个数不是任意的C.线性表中的每个结点都有且只有一个直接前趋和直接后继D.存在这样的线性表：表中各结点都没有直接前趋和直接后继参考答案：C5. 对线性表进行二分查找时，要求线性表必须( )。

A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列参考答案：C6. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

( )A、错误B、正确参考答案：B7. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边。

A.n(n-1)/2B.n(n-1)C.n2D.n2-1参考答案：A8. 任何一个无向连通图的最小生成树( )。

A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在参考答案：B9. 空格串的长度是空格的个数。

( )A、错误B、正确参考答案：B10. 设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[]A[0][0]存入B[0]中，则A[8][5]在B[]中( )A.32B.33C.41D.65参考答案：C11. 在队列中，允许进行删除操作的一端称为队尾。

一、单选:1.数据结构通常是研究数据的( )及它们之间的相互关系.A.存储和逻辑结构B.存储和抽象C.理想与抽象D.理想与逻辑2.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称为( )A.存储结构B.逻辑结构5C.顺序存储结构D.链式存储结构3.非线性结构是数据元素之间是存在的一种( )A.一对多关系B.多对多关系C.多对一关系D.一对一关系4.非线性结构中,每个结点( )A.无直接前趋.B.只有一个直接前驱和后继C.只有一个直接前驱和个数不受限制的直接后继D.有个数不受限制的直接前驱和后继.5.除了考虑存储数据结构本身所占用的空间外,实现算法所用辅助空间的多少称为算法的:A.时间效率B.空间效率C.硬件效率D.软件效率二、填空1、数据结构包括数据的_逻辑结构_,数据的_存储结构_,数据的__运算__,这三个方面的内容 .2、数据结构按逻辑结构可分为两大类,分别是__线性结构和非线性结构 _.3、数据的存储结构可用四种基本的存储方法表示,分别是__顺序、链式、索引、散列_.4、线性结构反映结点间的逻辑关系是_一对一关系_.非线性结构反映结点间的逻辑关系是多对多关系.5、一个算法的效率可分为时间效率和_空间效率_.三、简答：分别写出下列两个算法的时间复杂度.1、x=0;for(i=1;i<n;i++)for(j=i+1;j<=n;j++)x++;答：2、x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;答：欧一、填空1、在栈中存取数据的原则是：_先进后出_2、在栈中，出栈操作的时间复杂度为：_ 0(1)3、栈与一般线性表的区别主要在于__栈只允许在表尾进行插入和删除操作_4、顺序栈是空栈的条件是：_ s.top=0_5、插入和删除只能在一端进行的线性表，称为：__受限线性表_6、设循环向量有m个元素，循环向量中有一个循环队列，在循环队列中设队头指针front指向队头元素，队尾无名指是针指向队尾元素后的一个空闲元素。

华东理工大学2020年春季数据结构（本）网上作业2一、单选题1.(5分)设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是：• A.BCDEF• B.BCDEFG• C.BCPQRST• D.BCDEFEF纠错得分：5收起解析D2.(5分)设有两个串p和q，求q在p中首次出现的位置的运算称作：（）。

• A.连接• B.模式匹配• C.求子串• D.求串长纠错得分：5收起解析B3.(5分)线性表L在（）情况下适用于使用链式结构实现。

• A.需经常修改Ｌ中的结点值• B.需不断对Ｌ进行删除插入• C.Ｌ中含有大量的结点• D.Ｌ中结点结构复杂纠错得分：5收起解析B4.(5分)数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（）。

• A.存储结构• B.逻辑结构• C.顺序存储结构• D.链式存储结构纠错得分：5收起解析C5.(5分)在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。

• A.s->next=p+1、p->next=s• B.(*p).next=s、(*s).next=(*p).next• C.s->next=p->next、p->next=s->next• D.s->next=p->next、p->next=s纠错得分：5收起解析D6.(5分)在一个带头结点的循环双向链表中，若要在指针p所指向的结点之前插入一个q 指针所指向的结点，则需要对p->prior->next赋值为（）。

• A.q• B.p• C.p->next• D.p->prior纠错得分：5收起解析A7.(5分)若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

×第一次在线作业单选题 (共40道题)展开收起1.（2.5分）程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]> A[j+1] THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）•A、O（n）•B、O(nlogn)•C、O(n3)•D、O(n2)我的答案：D此题得分：2.5分2.（2.5分）若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1< =i< =n+1)。

•A、O(0)•B、O(1)•C、O(n)•D、O(n2)我的答案：C此题得分：2.5分3.（2.5分）算法的计算量的大小称为计算的•A、效率•B、复杂性•C、现实性•D、难度我的答案：B此题得分：2.5分4.（2.5分）算法的时间复杂度取决于•A、问题的规模•B、待处理数据的初态•C、A和B我的答案：C此题得分：2.5分5.（2.5分）下面关于算法说法错误的是•A、算法最终必须由计算机程序实现•B、为解决某问题的算法同为该问题编写的程序含义是相同的•C、算法的可行性是指指令不能有二义性•D、以上几个都是错误的我的答案：D此题得分：2.5分6.（2.5分）下面说法错误的是•A、算法原地工作的含义是指不需要任何额外的辅助空间•B、在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法•C、所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界•D、同一个算法，实现语言的级别越高，执行效率就不定我的答案：A此题得分：2.5分7.（2.5分）从逻辑上可以把数据结构分为（）两大类•A、动态结构、静态结构•B、顺序结构、链式结构•C、线性结构、非线性结构•D、初等结构、构造型结构我的答案：C此题得分：2.5分8.（2.5分）以下数据结构中，哪一个是线性结构（）•A、广义表•B、二叉树•C、稀疏矩阵•D、串我的答案：D此题得分：2.5分9.（2.5分）以下那一个术语与数据的存储结构无关？•A、栈•B、哈希表•C、线索树•D、双向链表我的答案：A此题得分：2.5分10.（2.5分）在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;•A、O(2n)•B、O(n)•C、O(n2)•D、O(log2n)我的答案：C此题得分：2.5分11.（2.5分）以下数据结构中，（）是非线性数据结构•A、树•B、字符串•C、队•D、栈我的答案：A此题得分：2.5分12.（2.5分）下列数据中，（）是非线性数据结构•A、栈•B、队列•C、完全二叉树•D、堆我的答案：C此题得分：2.5分13.（2.5分）下面关于线性表的叙述中，错误的是哪一个？（）•A、线性表采用顺序存储，必须占用一片连续的存储单元。