1下述哪一条是顺序存储结构的优点

【奥鹏】大工19秋《数据结构》在线作业1
试卷总分:100 得分:100
一、单选题 (共 10 道试题,共 50 分)
第1题，线性表采用顺序存储结构时,其地址 ( )。

[A.]部分地址必须是连续的
[B.]连续与否均可以
[C.]必须是连续的
[D.]一定是不连续的
正确的答案是:C
第2题，队列操作的原则是( )。

[A.]后进先出
[B.]只能插入
[C.]只能删除
[D.]先进先出
正确的答案是:D
第3题，下述哪一条是顺序存储结构的优点( )。

[A.]插入运算方便
[B.]存储密度大
[C.]可方便地用于各种逻辑结构的存储表示
[D.]删除运算方便
正确的答案是:B
第4题，若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( )存储方式最节省时间。

[A.]顺序表
[B.]带头结点的双循环链表
[C.]双链表
[D.]单循环链表
正确的答案是:A
第5题，链表不具有的特点是( )。

[A.]插入、删除不需要移动元素
[B.]所需空间与线性长度成正比
[C.]可随机访问任一元素
[D.]不必事先估计存储空间
正确的答案是:C
第6题，一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是( )。

[A.]不确定
[B.]n-i+1。

数据结构例题（及答案）项目一习题(答案)一选择题1. 算法的计算量的大小称为计算的(B )。

A( 效率 B. 复杂性 C. 现实性 D. 难度2.算法的时间复杂度取决于(C )A(问题的规模 B. 待处理数据的初态 C. A和B3(从逻辑上可以把数据结构分为(C )两大类。

A(动态结构、静态结构 B(顺序结构、链式结构C(线性结构、非线性结构 D(初等结构、构造型结构4(连续存储设计时，存储单元的地址(A )。

A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续5. 以下属于逻辑结构的是(C )。

A(顺序表 B. 哈希表 C.有序表 D. 单链表二、判断题1. 数据元素是数据的最小单位。

(×)2. 记录是数据处理的最小单位。

(×)3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×)4(程序一定是算法。

(×)5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。

(×)6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

(×)7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。

(?)8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×)三、填空1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。

2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形结构，图状结构或网状结构四种。

3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。

而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。

4(一个数据结构在计算机中表示(又称映像) 称为存储结构。

5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。

6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。

一、选择题1. 算法的计算量的大小称为计算的（）。

A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性4．一个算法应该是（）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.5. 下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 】13．以下哪个数据结构不是多型数据类型（）】A．栈 B．广义表 C．有向图 D．字符串14．以下数据结构中，（）是非线性数据结构】A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构。

习题一一、单选题1.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B )。

A. HL=p; p->next=HL;B. p->next=HL->next; HL->next=p;C. p->next=HL; p=HL;D. p->next=HL; HL=p;2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（ B ）个元素.A. nB.n-1C. n+1D.不确定3.下述哪一条是顺序存储方式的优点？（A ）A．存储密度大 B.插入和删除运算方便C. 获取符合某种条件的元素方便D.查找运算速度快4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3)DA．658 B．648 C．633 D．6535.下列关于二叉树遍历的叙述中，正确的是( AD ) 。

A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6.k层二叉树的结点总数最多为( A ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.对线性表进行二分法查找，其前提条件是( B ).A.线性表以链接方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以顺序方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序8.对n个记录进行堆排序，所需要的辅助存储空为Cn） B. O（n） C. O（1） D. O（n2）A. O（1og29.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素有（ D ）个，A．1 B．2 C．3 D．410.下列关于数据结构的叙述中，正确的是( D ).A.数组是不同类型值的集合B.递归算法的程序结构比迭代算法的程序结构更为精炼C.树是一种线性结构D.用一维数组存储一棵完全二叉树是有效的存储方法二、填空题1.数据的逻辑结构被分为_集合结构、__线性结构、_树结构和_图结构四种。

第1章1在数据结构中,从逻辑上可以把数据结构分成 CA 、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构答：常用的数据结构分为线性结构、树形结构和图状结构。

其中树形结构和图状结构合起来称为非线性结构。

2以下说法正确的是 DA 、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构答：数据元素是数据的基本单位，数据项是数据的最小单位。

C明显不对，所以选D3以下与数据的存储结构无关的术语是 CA 、顺序队列B、链表C、有序表D、链栈答：顺序队列、链表、链栈都与存储结构有关！4以下数据结构中哪个是非线性数据结构AA 、树B、字符串C、队列D、栈答：字符串、队列、栈都是线性结构。

5研究数据结构就是研究DA 、数据的逻辑结构B、数据的存储结构C、数据的逻辑结构和存储结构D、数据的逻辑结构、存储结构及其基本操作答：由数据结构的定义可知。

6算法分析的两个主要方面是 AA 、空间复杂度和时间复杂度B、正确性和简单性C、可读性和文档性D、数据复杂性和程序复杂性7下面程序段的时间复杂度是 Cfor(i=0;i<m;i++)for(j=0;j<n;j++)[i][j]=i*j;A 、O(m2) B、O(n2) C、O(m*n) D、O(m+n)答： A [i][j]=i*j执行的次数为m*n，所以时间复杂度为O(m*n)。

8计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( )等5个特性。

BA 、可行性、可移植性和可扩充性B、可行性、有穷性和确定性C、确定性、有穷性和稳定性D、易读性、稳定性和确定性9算法是DA 、计算机程序B、解决问题的计算方法C、排序算法D、问题求解步骤的描述10某算法的语句执行频度为(3n+nlog2n+n2+8) , 其时间复杂度表示CA 、O(n) B、O(nlog2n) C、O(n2) D、O(log2n)11下面程序段的时间复杂度为i=1; Cwhile(i<=n) i=i*3;A 、O(n) B、O(3n) C、O(log3n) D、O(n3) 设执行K次，则则k<=log3n12数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( )和运算等的学科。

第一章绪论考点1 数据结构基础知识1.数据的逻辑结构是指（），数据的存储结构是指（）分析：数据结构包括三方面的内容：数据的逻辑结构、存储结构和数据的运算。

其中，逻辑结构是指各数据元素之间的逻辑关系，存储结构是指逻辑结构用计算机语言的实现。

解答：数据元素之间的逻辑关系；数据的逻辑结构用计算机语言的实现。

2.在数据结构中，从逻辑上可以把数据结构分为：（A）A 线性和非线性结构B 紧凑和非紧凑结构C 动态和静态结构D 内部和外部结构分析：数据结构中，逻辑上可以把数据结构分成线性结构和非线性结构。

线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存储结构。

线性表若采用链式存储表示时，所有结点之间的存储单元地址可连续可不连续。

逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数无关。

关键考点点评：线性结构的特征，有且仅有一个开始结点和终端结点，所有结点最多只有一个直接前驱和后继。

栈和队列。

非线性结构的结点有多个前驱或后继，树和图。

3.数据结构在物理上可以分为（）存储结构和链式存储结构。

分析：物理存储解答：顺序4.下列术语中，（）与数据的存储结构无关A 循环队列B 堆栈C 散列表D 单链表解答： A5.（）不是算法所必须具备的特性A 有穷性B 确定性C 高效性D 可行性分析：算法的五个重要特征：有穷性、确定性、可行性、输入和输出。

解答：C考点2 时间复杂度计算1.设n是描述问题规模的非负整数，下面程序段的时间复杂度是（）2.第二章线性表考点1 线性表的基本概念1.线性表是n个（）的有限序列。

A 字符B数据元素 C 由数据项 D 信息项解析：解答 B2.线性表是一个（）。

A 有限序列，可以为空B 有限序列，不能为空C 无限序列，可以为空D 无限序列，不能为空解答 A关键考点点评：对于非空线性表1.有且仅有一个开始结点，没有直接前驱，有且仅有一个直接后继；2.有且仅有一个终结结点，没有直接后继，有且仅有一个直接前驱；3.其余的内部结点都有且仅有一个直接前驱和后继3.单链表不能随机存取元素原因是：要得到元素的存储地址，必须（）解答：从起始结点开始扫描以得到其地址注：顺序表可以，但是链表不行考点2 线性表的顺序存储结构1.下述（）是顺序存储结构的优点A 插入运算方便B 可方便地用于各种逻辑结构的存储表示C 存储密度大D 删除运算方便解答： C2.线性表的（）存储结构是随机存储结构。

一、选择题（每小题 1分，共10分）1、队列是插入和删除受限的线性表，其删除操作是在线性表的（1）进行。

A．表头 B．表尾 C．任意位置 D．指定位置2、下述哪一条是顺序存储结构的优点（2）。

A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示3、设有一个栈，元素的进栈次序为A, B, C, D, E，下列哪个是不可能的出栈序列（3）。

A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A4、若二叉树的根结点所在的层次为第1层，则该二叉树的第k层上至多有（4）个结点。

2k B．2k C．2k-1 D．2k+1A. 15、设单链表中指针p指向结点m，若要删除m的后继结点（假设该后继结点存在），则需修改指针的操作为（5）。

A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;6、下面程序段的时间复杂度为（6）。

for(int i=0; i<m; i++)for(int j=0; j<n; j++) a[i][j] = i*j;A．O(m2) B．O(n2) C．O(m+n) D． O(m*n)7、非空的循环单链表head的尾结点指针p满足（7）。

A．p==NULL B．p== head C．p->next==head D．p->next==NULL8、已知二维数组A[0..9,0..9]中，元素a[2][0]的地址为560，每个元素占4个字节，则元素a[1][0]的地址为（8）。

A. 518B. 520C. 522D. 5249、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（9）。

A．rear％n= = front B．（front+l）％n= = rearC．rear％n -1= = front D．(rear+l)％n= = front10、假设在一棵二叉树中，度为2的结点数为15，度为1的结点数为10个，则该二叉树的分支总数为（10）个。

线性表1.下列有关线性表的叙述中，正确的是（A）。

A）线性表中元素之间的关系是线性关系B）线性表中至少有一个元素C）线性表中的任一元素有且仅有一个直接前趋D）线性表中的任一元素有且仅有一个直接后继2.下述哪一条是顺序存储结构的优点？（A）A）存储密度大B）插入方便C）删除方便D）可方便地用于各种逻辑结构的存储表示3.在一个长度为n的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时需向后移动（D）个元素。

A）1 B）n-i C）n-i-1 D）n-i+14.如果某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，那么采用（A）存储方式最节省时间。

A）顺序表B）单链表C）双链表D）循环链表5.对顺序存储的线性表，设其长度为n，且在任何位置上插入或删除操作都是等概率的。

则插入一个元素时平均要移动表中的（A）个元素。

A）n/2 B）(n+1)/2 C）(n-1)/2 D）n6.下述哪一条是顺序存储结构的缺点？（C）A）存储密度太大B）随机存取C）一般要估计最大的需要空间D）只能应用于少数几种逻辑结构的存储表示7.在单链表中，增加头结点的目的是（C）。

A）使单链表至少有一个结点B）标志表中首结点的位置C）方便运算的实现D）说明单链表是线性表的链式存储表示8.单链表不具有的特点是（A）。

A)可随机访问任一元素B)插入和删除不需要移动元素C)不必事先估计存储空间D)所需空间和线性表长度成正比9.循环链表的主要优点是（D）。

A）不再需要头指针了B）已知某个结点的位置后，能够容易找到他的直接前趋C）在进行插入、删除运算时，能更好的保证链表不断开D）从表中的任意结点出发都能扫描到整个链表10.链表对于数据元素的插入与删除是（B）。

A）不需移动结点，不需改变结点指针B）不需移动结点，只需改变结点指针C）只需移动结点，不需改变结点指针D）既需移动结点，又需改变结点指针11.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若要在q 和p 所指结点之间插入s所指的结点,则执行（B）。