数据结构期末考试题及标准答案

贵州大学理学院数学系信息与计算科学专业《数据结构》期末考试试题及答案(2003-2004学年第2学期)一、单项选择题1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。

(A)、正确性(B). 可行性(C). 健壮性(D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。

for(i=n-1；i>=0；i--)for(j=0；j<i；j++) S；(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（）。

（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（）。

（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。

（A）、k-1 （B）、k （C）、k-1和k （D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。

（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（）（（B）、p=Q.front->next; Q.front->next=p->next;（C）、p=Q.rear->next; p->next= Q.rear->next;（D）、p=Q->next; Q->next=p->next;9． Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（）域存储后继结点的地址。

2011-2012学年第一学期期末考查《数据结构》试卷（答案一律写在答题纸上，在本试卷上做答无效）一、选择（每题1分，共10分）1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D）A.O(0)B.O(1)C.O(n)D.O(n2)2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D）A.543612B.453126C.346512D.2341563.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ）A.8B.9C.10D.114.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ）A. m-nB.m-n-1C.n+1D.m+n5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B）A.9B.11C.15D.不确定6.下列哪一个方法可以判断出一个有向图是否有环。

（A）A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。

A.73B.234C.235D.2368.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B）A.（100,80,90,60,120,110,130）B.（100, 120, 110,130,80, 60,90）C.（100,60,80,90,120,110,130）D.（100,80, 60,90, 120, 130,110）9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 2584 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ）A.选择排序B.起泡排序C.快速排序D.插入排序10.对线性表进行折半查找时，要求线性表必须（D）A.以顺序方式存储B.以顺序方式存储，且数据元素有序C.以链接方式存储D.以链接方式存储，且数据元素有序二、填空（每空1分，共15分）1.数据结构中评价算法的两个重要指标是时间复杂度、空间复杂度。

《数据结构》试题（A卷）（考试时间： 90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。

A．数据 B.数据元素 C.数据对象 D.数据结构2.算法计算量的大小称为算法的（）。

A.效率B.复杂度C.数据元素之间的关系D.数据的存储方法3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（）方式最节省时间。

A.链式存储B. 索引存储C.顺序存储D.散列存储4.下述哪一条是顺序存储结构的优点？（）A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示5.在一个单链表中，若删除p所指结点的后续结点，则执行（）。

A.p->next=p->next->nextB.p->next=p->nextC.p=p->next;p->next=p->next->nextD.p=p->next->next6.带头结点的单链表head为空的判定条件是（）。

A.head==NULLB.head->next==NULLC.head->next==headD.head!==NULL7.非空的循环单链表head的尾结点(由p所指向)满足（）。

A.p->head==NULLB.p==NULLC.p->next==headD.p==head8.下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。

B.线性表采用顺序存储，便于进行插入和删除操作。

C.线性表采用链式存储，不必占用一片连续的存储单元。

D.线性表采用链式存储，便于插入和删除操作。

9.队列操作的原则是（）。

A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（）。

课程：数据结构专业：计算机科学与技术、网络工程、软件工程参考答案及评分标准一、单项选择题(10小题，每小题1分，共10分)1．算法指的是____D_____。

A．数据处理B．计算机程序C．解决问题的计算方法D．对特定问题求解步骤的一种描述，是指令的有限序列2．已知已个AOV网如图所示，下列____C_____不是该图的拓扑序列。

A．v0 v1 v5 v2 v3 v6 v4 B．v0 v1 v5 v2 v6 v3 v4C．v0 v1 v5 v3 v2 v6 v4 D．v0 v1 v5 v6 v2 v3 v43．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是___B______。

A．2 B．3 C．4 D．64．如果结点A有3个兄弟，B是A的双亲，则结点B的度是______D______。

A．1 B．2 C．3 D．45．二叉树的前序序列和后序序列正好相反，则该二叉树一定是___B______的二叉树。

A．完全二叉树B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子6．在一个无向图中，所有顶点的度数之和等于所有边数的____B______倍。

A．1 B．2 C．3 D．47．判定有向图是否存在回路除了可以利用拓扑排序方法外，还可以用_____A______。

A．深度优先遍历算法B．广度优先遍历算法C．求关键路径方法D．求最短路径方法8．下述排序方法中，比较次数与待排序记录的初始状态无关的是____C_______。

A．插入排序和快速排序B．归并排序和快速排序C．选择排序和归并排序D．插入排序和归并排序9．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值____A_____。

A．不一定都是同义词B．一定都是同义词C．一定都不是同义词D．都相同10．下列序列中，_______ 是执行第一趟快速排序的结果。

数据结构期末考试试题（含答案）2005年－2006学年第⼆学期“数据结构”考试试题（A）姓名学号(序号)_答案隐藏班号要求：所有的题⽬的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题⽬的序号。

每张答题纸都要写上姓名和序号。

⼀、单项选择题（每⼩题2分，共20分）1．数据的运算a 。

A.效率与采⽤何种存储结构有关B.是根据存储结构来定义的C.有算术运算和关系运算两⼤类D.必须⽤程序设计语⾔来描述答：A。

2.链表不具备的特点是 a 。

A.可随机访问任⼀结点B.插⼊删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正⽐答：参见本节要点3。

本题答案为：A。

3.在顺序表中删除⼀个元素的时间复杂度为 c 。

A.O(1)B.O(log2n)C.O(n)D.O(n2)答：C。

4．以下线性表的存储结构中具有随机存取功能的是d 。

A.不带头结点的单链表B.带头结点的单链表C.循环双链表D.顺序表解D。

5.⼀个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是c 。

A.edcba B.decbaC.dceabD.abcde答：C。

6.循环队列qu的队空条件是 d 。

A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB. (qu.rear+1)%MaxSize==qu.front+1C.(qu.rear+1)%MaxSize==qu.frontD.qu.rear==qu.front答：D。

7.两个串相等必有串长度相等且 b 。

A.串的各位置字符任意B.串中各位置字符均对应相等C.两个串含有相同的字符D.两个所含字符任意答：B。

8.⽤直接插⼊排序对下⾯四个序列进⾏递增排序，元素⽐较次数最少的是c 。

A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,40答：C。

“数据结构”期末考试试题一、单选题（每小题2分,共12分)1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点,则执行( )。

A． HL＝ps p一〉next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl;p＝HL；D． p一〉next＝HL一>next;HL一〉next＝p；2．n个顶点的强连通图中至少含有( ）。

A。

n—l条有向边 B.n条有向边C.n(n-1)／2条有向边 D。

n（n一1）条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( ）。

A。

O（1) B.O（n)C.O（1Ogzn)D.O（n2）4．由权值分别为3，8,6,2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( ）。

A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为（ )参数，以节省参数值的传输时间和存储参数的空间。

A。

整形 B。

引用型C。

指针型 D。

常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为（）。

A．O(n） B．O(1)C．O（n2） D．O(10g2n）二、填空题（每空1分，共28分）1．数据的存储结构被分为——、——、——和-—四种.2．在广义表的存储结构中,单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。

3．—-中缀表达式 3十x*(2.4／5—6）所对应的后缀表达式为—-——。

4．在一棵高度为h的3叉树中,最多含有—-结点。

5．假定一棵二叉树的结点数为18,则它的最小深度为-—，最大深度为——·6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定-—该结点的值，右子树上所有结点的值一定-—该结点的值。

7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层—-调整,直到被调整到——位置为止。

《数据结构》试卷及答案1．算法分析的目的是( C )。

A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2．（ B ）是具有相同特性数据元素的集合，是数据的子集。

A.数据符号B.数据对象C.数据D.数据结构3．用链表表示线性表的优点是( C )。

A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同4．输入序列为（A,B,C,D）不可能的输出有（D ）。

A.(A,B,C,D)B. (D,C,B,A)C. (A,C,D,B) D . (C,A,B,D)5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( B )。

A. front=maxSizeB. (rear+1)%maxSize=frontC. rear=maxSizeD. rear=front6．设有串t='I am a good student '，那么Substr(t,6,6)=（ D ）。

A. studentB. a good sC. goodD. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（ B ）。

A.23B.33C.18D. 408．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子B的运算（C ）。

A. Gethead(Gethead(LS))B. Gettail(Gethead(LS))C. Gethead(Gethead(Gettail(LS)))D. Gethead(Gettail(LS))9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( A ) 。

A. CDBGFEAB. CDBFGEAC. CDBAGFED. BCDAGFE10．下列存储形式中，(C ) 不是树的存储形式。

数据结构期末考试试题及答案-、选择题1.评价一个算法时间性能的主要标准是（）。

A、算法易于调试B、算法易于理解C、算法的稳定性和正确性2.计算机算法具备有输入、输出、（）等五个特性。

A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D易读性、稳定性和安全性3.带头结点的单链表head为空的判定条件是（）。

A head==NULLC、head->next==headD head！=NULL4.以下关于线性表的说法不正确的是（）。

A、线性表中的数据元素可以是数字、字符、记录等不同类型。

B、线性表中包含的数据元素个数不是任意的。

C、线性表中的每个结点都有且只有一个直接前趋和直接后继。

D存在这样的线性表：表中各结点都没有直接前趋和直接后继。

5.在顺序表中，只要知道（），就可在相同时间内求出任一结点的存储地址。

A、基地址B、结点大小C、向量大小6.（）运算中，使用顺序表比链表好。

A、插入）个元素C 、 根据序号查找D 根据元素值查找7. 一个长度为n 的顺序表中，向第i 个元素之前插入一个新元素时，需要向后移动（A 、 n-iC 、n-i-1D i 8. ()适合作为经常在首尾两端操作线性表的存储结构。

A 、 顺序表B 、 单链表C 、 循环链表D 双向链表9. 栈和队列的共同点是()A 、 都是先进后出B 、 都是先进先出C 、 只允许在端点处插入和删除元素D 没有共同点10. 一个队列的入列序列是1 2 3 4，则队列的输出序列是()A 4 3 2 1C 、 1 4 3 2D 3 2 4 111. 队列与一般的线性表的区别在于()。

A 、 数据元素的类型不同B 、 运算是否受限制C 、 数据元素的个数不同12. “假上溢”现象会出现在()中。

A 、 循环队列C、链队列D顺序队列二、填空题1•数据的逻辑结构被分为集合、线性结构、树形结构和图结构。

2•数据的逻辑结构被分为集合、线性结构、树形结构和图状结构。

最新国家开放大学电大《数据结构(本)》期末题库及答案考试说明：本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并且每年都在更新。

该题库对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。

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

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

《数据结构》题库及答案一一、单项选择题（每小题3分，共30分）试题答案及评分标准（供参考）一、单项选择题（每小题3分，共30分）1．C 2．B 3．A 4．C 5．B6．C 7．A 8．D 9．A 10．D二、填空题（每小题2分，共24分）11.先出 12．树形 13．行下标列下标数组元素 14.3 15．存储位置 16. 1017. 20 18．二叉排序树 19.叶20.4 21. 2,4,3;5,6,8,7,9 22. a2《数据结构》题库及答案二一、单项选择题（每小题3分，共30分）二、填空题（每小题2分，共24分）三、综合题【每小题中每问5分，共30分）四、程序填空题（每空2分，共16分）试题答案及评分标准（供参考）一、单项选择题（每小题3分，共30分）1．A 2．D 3．C 4．B 5．B6．C 7．B 8．C 9．A 10.C二、填空题（每小题2分，共24分）11．图状 12. n-j 13．二叉排序树 14. 1,2,4,8,3,5,915. 4 16. 3 17. 5 18. 319. 9 20. 12 21. 32 22. 7《数据结构》题库及答案三一、单项选择题，在括号内填写所选择的标号1．输出一个二维数组b[m][n]中所有元素的时间复杂度为( )。

A．（）(n) B．（）(m十n)C．（）(n2) D．（）(m*n)2．在一个长度为n的顺序存储的有序表中搜索值为x元素时，其时间效率最高的算法的时间复杂度为( )。

3．当利用大小为n的数组顺序存储一个栈时，假定用top= =n表示栈空，则向这个栈插入一个元素时，首先应执行( )语句修改top指针。

数据结构考试题及答案一、选择题1. 下列哪种数据结构是一种线性结构？A. 树B. 栈C. 图D. 队列答案：B. 栈2. 以下哪种不是二叉树的遍历方式？A. 先序遍历B. 层序遍历C. 后序遍历D. 中序遍历答案：B. 层序遍历3. 在队列中，哪种操作不是O(1)时间复杂度的？A. 入队B. 出队C. 判空D. 获取队首元素答案：D. 获取队首元素二、填空题4. 二叉查找树的中序遍历结果为_______。

答案：升序排列的序列5. 栈的特点是_______进，_______出。

答案：后进，先出6. 图中两点间存在边则称它们为_______。

答案：邻接点三、简答题7. 请简要介绍一下栈和队列的应用场景及区别。

答：栈和队列都是常用的数据结构，栈适合用于实现括号匹配、表达式求值等场景，而队列常用于实现广度优先搜索、缓存队列等。

栈是一种后进先出的数据结构，而队列是一种先进先出的数据结构。

8. 什么是哈希表？它的优缺点分别是什么？答：哈希表是一种通过哈希函数将关键字映射到数组位置的数据结构。

其优点是能够快速查找、插入、删除元素，时间复杂度接近O(1)；缺点是可能发生哈希冲突，导致性能下降。

四、综合题9. 给定以下无向图的邻接矩阵表示，请写出图的深度优先搜索（DFS）遍历路径。

```0 1 2 30 0 1 0 11 1 0 1 12 0 1 0 13 1 1 1 0```答：起始节点为0，路径：0 - 1 - 3 - 210. 写出以下树的层序遍历结果。

```1/ \2 3/ \ / \4 5 6 7```答：1 - 2 - 3 - 4 - 5 - 6 - 7以上就是数据结构考试题及答案，希望对您有所帮助。

如果有不清楚的地方，欢迎随时向老师询问。

祝您考试顺利！。

《数据结构》习题汇编一、单项选择题1.在数据结构中,从逻辑上可以把数据结构分成（）。

Ａ．动态结构和静态结构ﻩﻩﻩＢ．紧凑结构和非紧凑结构Ｃ. 线性结构和非线性结构ﻩﻩD.内部结构和外部结构2.数据结构在计算机内存中的表示是指（）。

Ａ. 数据的存储结构ﻩﻩB.数据结构Ｃ. 数据的逻辑结构ﻩ D.数据元素之间的关系3.在数据结构中，与所使用的计算机无关的是数据的( )结构。

A. 逻辑ﻩﻩﻩB．存储ﻩﻩﻩC. 逻辑和存储ﻩD. 物理4.计算机算法指的是( ① ),它必须具备输入、输出和（②）等5个特性。

①A.计算方法ﻩﻩﻩB. 排序方法C. 解决问题的有限运算序列ﻩﻩD.调度方法②A.可行性、可移植性和可扩充性ﻩ B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性ﻩﻩD. 易读性、稳定性和安全性5.在一个长度为ｎ的顺序表中向第i个元素（１≤ｉ≤n+１）位置插入一个新元素时，需要从后向前依次后移（)个元素。

A. n－i ﻩB. n－i+1ﻩﻩC. n-i-1D. ｉ6.在一个长度为n的顺序表中删除第i个元素(1≤ｉ≤n）时，需要从前向后依次前移（)个元素。

A. n-iﻩﻩﻩＢ. n-i+１ﻩﻩC. ｎ-ｉ-1ﻩD．i7.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( )。

A. Ｏ（n)B.O（１)ﻩC. Ｏ(n２)D.O(log2n)8.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为(）。

A. O(n)B． O(ｎ/２) ﻩＣ.Ｏ(１) ﻩ D. Ｏ（ｎ2)9.不带头结点的单链表firsｔ为空的判定条件是:（ )Ａ.firｓt ＝= NＵLL;ﻩﻩﻩB． firｓｔ-＞next == NUＬL；C. firｓt->next ＝＝ｆｉrst;D.fiｒst != ＮＵＬL;10.带头结点的单链表firsｔ为空的判定条件是：（ )A. ｆirst＝=ＮULL; ﻩﻩﻩB． firsｔ->ｎｅxｔ＝＝ NULL;C. fｉｒsｔ-＞nｅxt ==fiｒｓｔ；ﻩﻩＤ. fｉｒｓｔ！= NULL；11.设单链表中结点的结构为(daｔa，neｘｔ）。

第一章1．在数据结构中，从逻辑上可以把数据结构分为（C ）A．动态结构和静态结构 B. 紧凑结构和非紧凑结构C．线性结构和非线性结构 D. 内部结构和外部结构2.在数据结构中,与所使用的计算机无关的是( A )A. 逻辑结构B. 存储结构C. 逻辑和存储结构D. 物理结构3.下面程序的时间复杂度为____O（mn）_______。

for (int i=1; i<=m; i++)for (int j=1; j<=n; j++ )S+=i第二章线性表链表不具备的特点是（A）A 可以随机访问任一结点（顺序）B 插入删除不需要移动元素C 不必事先估计空间D 所需空间与其长度成正比2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ）A head==nullB head->next==nullC head->next==headD head!=null3.在线性表的下列存储结构中，读取元素花费时间最少的是（D）A 单链表B 双链表C 循环链表D 顺序表4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C)A 顺序表B 用头指针表示的单循环链表C 用尾指针表示的单循环链表D 单链表5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作的时间复杂度为( D )A O(1)B O(log2n)C O(n2)D O(n)6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长度有关A 删除单链表中第一个元素B 删除单链表中最后一个元素C 在第一个元素之前插入一个新元素D 在最后一个元素之后插入一个新元素7.与单链表相比，双向链表的优点之一是(D)A 插入删除操作更简单B 可以进行随机访问C 可以省略表头指针或表尾指针D 顺序访问相邻结点更容易8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域(头结点的地址)中存放的是( B )A list的地址B list的内容C list指的链结点的值D 链表第一个链结点的地址9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B )A list2比list1占用更多的存储单元B list1与list2占用相同的存储单元C list1和list2应该是相同类型的指针变量D 双向链表比单链表占用更多的存储单元10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗 (不正确)11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。

数据结构复习题及标准答案————————————————————————————————作者：————————————————————————————————日期：一、选择题。

(每小题2分，共40分)(1) 计算机识别.存储和加工处理的对象被统称为____A____。

A.数据B.数据元素C.数据结构D.数据类型(2) 数据结构通常是研究数据的____ A _____及它们之间的联系。

A.存储和逻辑结构B.存储和抽象C.理想和抽象D.理想与逻辑(3) 不是数据的逻辑结构是____ A ______。

A.散列结构B.线性结构C.树结构D.图结构(4) 数据结构被形式地定义为<D,R>,其中D是____ B _____的有限集，R是____ C _____的有限集。

A.算法B.数据元素C.数据操作D.逻辑结构(5) 组成数据的基本单位是____ A ______。

A.数据项B.数据类型C.数据元素D.数据变量(6) 设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是____ A ______。

A.线性结构B.树型结构C.图型结构D.集合(7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___ C ____。

A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为___ A ____。

A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构(9) 对一个算法的评价，不包括如下____ B _____方面的内容。

A.健壮性和可读性B.并行性C.正确性D.时空复杂度(10) 算法分析的两个方面是__ A ____。

A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性(11) 线性表是具有n个___ C _____的有限序列（n≠0)。

一、是非题1.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

.......................( T )2.线性表的逻辑顺序与物理顺序总是一致的........( F )3.线性表中的每个结点最多只有一个前驱和一个后继。

......( T )4.线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

.......................( F )5.栈和队列逻辑上都是线性表。

..........................( T )6.单链表从任何一个结点出发，都能访问到所有结点........( F )7.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。

.................................................( T )8.在用单链表表示的链式队列中，队头在链表的链尾位置。

....( F )9.多维数组是向量的推广。

..............................( T )10.栈是一种先进先出的线性表。

....( F )11.凡是递归定义的数据结构都可以用递归算法来实现它的操作。

......( T )12.设串S的长度为n,则S的子串个数为n(n+1)/2。

...........( F )13.一般树和二叉树的结点数目都可以为0。

................( F )14.按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结点。

....( T )15.后序序列和中序序列能唯一确定一棵二叉树。

....( T )16.对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂度为O(n) .............( T )17.网络的最小代价生成树是唯一的。

...( T )18.图的拓扑有序序列不是唯一的。

第一章1．在数据结构中，从逻辑上可以把数据结构分为（C ）A．动态结构和静态结构 B. 紧凑结构和非紧凑结构C．线性结构和非线性结构 D. 内部结构和外部结构● 2.在数据结构中,与所使用的计算机无关的是( A )A. 逻辑结构B. 存储结构C. 逻辑和存储结构D. 物理结构3.下面程序的时间复杂度为____O（mn）_______。

for (int i=1; i<=m; i++)for (int j=1; j<=n; j++ )S+=i第二章线性表●链表不具备的特点是（A）A 可以随机访问任一结点（顺序）B 插入删除不需要移动元素C 不必事先估计空间D 所需空间与其长度成正比2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ）A head==nullB head->next==nullC head->next==headD head!=null●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D）A 单链表B 双链表C 循环链表D 顺序表● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C)A 顺序表B 用头指针表示的单循环链表C 用尾指针表示的单循环链表D 单链表● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作的时间复杂度为( D )A O(1)B O(log2n)C O(n2)D O(n)● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长度有关A 删除单链表中第一个元素B 删除单链表中最后一个元素C 在第一个元素之前插入一个新元素D 在最后一个元素之后插入一个新元素●7.与单链表相比，双向链表的优点之一是(D)A 插入删除操作更简单B 可以进行随机访问C 可以省略表头指针或表尾指针D 顺序访问相邻结点更容易●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域(头结点的地址)中存放的是( B )A list的地址B list的内容C list指的链结点的值D 链表第一个链结点的地址●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B )A list2比list1占用更多的存储单元B list1与list2占用相同的存储单元C list1和list2应该是相同类型的指针变量D 双向链表比单链表占用更多的存储单元10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确)11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。

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

【北京邮电大学2000二、3（20/8分）】A．效率 B.复杂性 C.现实性 D.难度2. 算法的时间复杂度取决于（）【中科院计算所1998二、1（2分）】A．问题的规模 B.待处理数据的初态 C. A 和 B3.计算机算法指的是（ 1），它必须具备（ 2）这三个特性。

(1) A．计算方法 B.排序方法 C.解决问题的步骤序列 D.调度方法(2) A ．可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D.易读性、稳定性、安全性【南京理工大学1999一、1（2分）【武汉交通科技大学1996一、1（ 4 分）】4．一个算法应该是（）。

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

【武汉交通科技大学1996 一、4（ 2 分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学2000二、 1（2分）】A．循环队列 B.链表 C.哈希表 D.栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001一、 1（2分）】A．广义表 B.二叉树 C.稀疏矩阵 D.串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001一、 2（2 分）】A ．栈 B.哈希表 C.线索树 D.双向链表11．在下面的程序段中，对 x 的赋值语句的频度为（）【北京工商大学2001一、10（ 3 分）】FOR i:=1TOn DOFOR j:=1TOn DOx:=x+1;A． O(2n)B． O(n)C． O(n2)D． O(logn 2 )12．程序段FOR i:=n-1DOWNTO1DOFOR 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(n 3)D. O(n 2)【南京理工大学 1998 一、 1(2 分 ) 】13．以下哪个数据结构不是多型数据类型（）【中山大学1999一、 3（ 1 分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999一、 4】A．树B．字符串C．队D．栈15.下列数据中，（）是非线性数据结构。

单元测验1一．判断题（ㄨ）（1）数据的逻辑结构和数据的存储结构是相同的。

（ㄨ）（2）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。

（√）（3）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（√）（4）数据的存储结构是数据的逻辑结构的存储映像。

（ㄨ）（5）数据的逻辑结构是依赖于计算机的。

（√）（6）算法是对解题方法和步骤的描述。

二．填空题1．数据有逻辑结构和存储结构两种结构。

2.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。

3．树形结构和图形结构合称为非线性结构。

4．数据的存储结构又叫物理结构。

5．数据的存储结构形式包括：顺序存储和链式存储6．线性结构中的元素之间存在一对一的关系。

7．树形结构中的元素之间存在一对多的关系。

8．图形结构的元素之间存在多对多的关系。

9．数据结构主要研究数据的逻辑结构、存储结构和二者之间的相互运算三个方面的内容。

11．若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O（nlog2n）。

12．若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为O（n2）。

三．选择题1．数据结构通常是研究数据的（D ）及它们之间的相互联系。

A.联系与逻辑B.存储和抽象C.联系和抽象D.存储结构和逻辑结构2．数据在计算机内存储时，数据元素在存储器内相对位置可以表示元素之间的逻辑关系，称为（D）。

A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3．链接存储的存储结构所占存储空间（A）。

A．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数4．在数据结构中，与所使用的计算机无关的是（B）A.物理结构B.逻辑结构(不用进行计算)C.存储结构D.逻辑和存储结构5．算法能正确的实现预定功能的特性称为（A）A.正确性B.易读性C.健壮性D.高效性6．算法在发生非法操作时可以作出处理的特性称为（B）A.正确性B.健壮性C.易读性D.高效性7．下列时间复杂度中最坏的是（A）A.O（n2）B.O（log2n）C.O（n）D.O（1）8.算法分析的两个主要方面是（C）。

数据结构试卷一. (共 75 题,共 150 分)1. 数据的基本单位是() 。

(2 分)A.数据元素B.记录C.数据对象D.数据项★检查答案标准答案： A2. ()是数据的不可分割的最小单位。

(2 分)A.数据对象B.数据元素C.数据类型D.数据项★检查答案标准答案： D3. 算法的空间复杂度是对算法()的度量。

(2 分)A. 时间效率B.空间效率C.可读性D.健壮性★检查答案标准答案： B4. ()是限制了数据元素的内部结构仅为一个字符的线性表。

(2 分)A.栈B. 队列C.串D.数组★检查答案标准答案： B5. 串的长度是指串中所含()的个数。

(2 分)A.不同字符B.不同字母C.相同字符D.所有字符★检查答案标准答案： D6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针()次。

(2 分)A.1B.2C.3D.4★检查答案标准答案： B7. 线性表的顺序存储结构是一种()的存储结构。

(2 分)A.顺序存取B. 随机存取C.索引存取D.Hash 存取★检查答案标准答案： B8. 数组 a[1..m] 采用顺序存储， a[1]和 a[m] 地址分别为 1024 和 1150，每个元素占 2 字节，则 m 是() 。

(2 分)A.64B.32C. 16D.8★检查答案标准答案： A9. 深度为 h 的二叉树，第 h 层最多有()个结点。

(2 分)A.hB.2h-1C.2h-1D.2h★检查答案标准答案： C10. m 个结点的二叉树，其对应的二叉链表共有()个非空链域。

(2 分)A.mB.m+1C.2mD.m- 1★检查答案标准答案： B11. 下面叙述错误的是() 。

(2 分)A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系B.对于空队列进行出队操作过程中发生下溢现象C.有向图的邻接矩阵一定是对称的D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的★检查答案标准答案： C12. 以下与数据的存储结构无关的术语是() 。

数据结构练习题第一部分绪论一、单选题1. 一个数组元素a[i]与________的表示等价。

A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。

A、参数类型B、参数个数C、函数类型3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数A、指针B、引用C、值4. 下面程序段的时间复杂度为____________。

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)5. 执行下面程序段时，执行S语句的次数为____________。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/26. 下面算法的时间复杂度为____________。

int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1);}A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1. 数据的逻辑结构被分为__________、_________、__________和__________四种。

2. 数据的存储结构被分为__________、_________、__________和__________四种。

3. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。

4. 一种抽象数据类型包括__________和__________两个部分。

5. 当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。