一、选择题(20分)
1．下面关于线性表的叙述错误的是（D ）。
(A) 线性表采用顺序存储必须占用一片连续的存储空间
(B) 线性表采用链式存储不必占用一片连续的存储空间
(C) 线性表采用链式存储便于插入和删除操作的实现
(D) 线性表采用顺序存储便于插入和删除操作的实现
2．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A ）。
(A) BADC (B)BCDA (C) CDAB (D) CBDA
3．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C ）。
(A) 9 (B) 10 (C) 11 (D) 12
4．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ B ）。
(A) O(1) (B) O(log2n) (C) (D) O(n2)
5．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ B ）方法可以达到此目的。
(A)快速排序(B)堆排序(C)归并排序(D)插入排序
第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。
6.下列四种排序中（ D ）的空间复杂度最大。
(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序
7．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。
(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)
8．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。
(A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1
9．在二叉排序树中插入一个结点的时间复杂度为（B ）。
(A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)
10．设用链表作为栈的存储结构则退栈操作（ B ）。
(A) 必须判别栈是否为满(B) 必须判别栈是否为空
(C) 判别栈元素的类型(D) 对栈不作任何判别
11．下列四种排序中（A ）的空间复杂度最大。
(A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆
12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（ C ）。
(A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1 (D) N0=2N1+l
13.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不
超过（A ）。
(A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)
14．数据的最小单位是（ A ）。
(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量
15．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ D ）。
(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)
16．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为N l，……，度数为m的结点数为Nm，则N0=（B ）。
(A) N l+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm
(C) N2+2N3+3N4+……+(m-1)Nm (D) 2N l+3N2+……+(m+1)Nm
17．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（C ）。
(A) n-i (B) n-1-i (C) n+1-i (D) 不能确定
18．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ A ）。
(A) 堆排序(B) 冒泡排序(C) 希尔排序(D) 快速排序
19．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（D ）。
(A) 空或只有一个结点(B) 高度等于其结点数
(C) 任一结点无左孩子(D) 任一结点无右孩子
20．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（A ）。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
21．二路归并排序的时间复杂度为（ C ）。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
22. 深度为k的完全二叉树中最少有（B ）个结点。
(A) 2k-1-1 (B) 2k-1(C) 2k-1+1 (D) 2k-1
23.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（D ）。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
24．（ B ）二叉排序树可以得到一个从小到大的有序序列。
(A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历
25．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i 结点的左孩子结点的编号为（B ）。
(A) 2i+1 (B) 2i (C) i/2 (D) 2i-1
26．程序段s=i=0；do {i=i+1；s=s+i；}while(i<=n)；的时间复杂度为（A ）。
(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)
27.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ D ）。
(A)top=top+1; (B)top=top-1;
(C)top->next=top; (D)top=top->next;
28.建立一个长度为n的有序单链表的时间复杂度为（ C ）
(A) O(n) (B)O(1) (C)O(n2) (D)O(log2n)
29.在二叉排序树中插入一个关键字值的平均时间复杂度为（ B ）。
(A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2)
30.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ B ）。
(A) 8 (B) 7 (C) 6 (D) 5
31.队列是一种（A ）的线性表。
(A) 先进先出(B) 先进后出(C) 只能插入(D) 只能删除
32.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（ C ）。
(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)
33．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（D ）。
(A) p->right=s；s->left=p；p->right->left=s；s->right=p->right；
(B)s->left=p；s->right=p->right；p->right=s；p->right->left=s；
(C) p->right=s；p->right->left=s；s->left=p；s->right=p->right；
(D) s->left=p；s->right=p->right；p->right->left=s；p->right=s；
34.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是C 。
A．edcba B．decba C．dceab D．Abcde
A：a,b,c,d,e进，之后依次出栈
B：a,b,c,d,进，d出，e进，e,c,b,a出
D：a进a出，b进b出……e进e出
C：的话dce都好办，之后的ab做不到
这道题就是没告诉你进栈的同时可以随时出栈==
二、填空题
1.数据的物理结构主要包括顺序存储结构和链式存储结构两种情况。
2.数据结构从逻辑上划分为三种基本类型：线性结构、树型结构和图型结构。
3.
4.公式：二维数组A中任一元素a ij的存储位置：（LOC（0，0）是a00的存储位置）
LOC(i，j)=LOC（0，0）+（b2*i+j）L
5.快速排序的时间性能分析
最好情况：
每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为O(nlog2n)。
最坏情况：
每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为 O(n2)。
平均情况：为O(nlog2n)。
6.在快速排序、堆排序、归并排序中，___归并______排序是稳定的。
7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_O(log2n)_____，整个堆
排序过程的时间复杂度为___O(nlog2n)_____。
8.快速排序的最坏时间复杂度为O(n2)，平均时间复杂度为O(nlog2n)。
9.散列表中解决冲突的两种方法是开放定址法和链地址法。
10.在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择___
快速_____排序，如果从节省存储空间的角度来考虑则最好选择__堆______排序。
三、判断题
全对或全错得5分
1．调用一次深度优先遍历可以访问到图中的所有顶点。（×）
2．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（√）3．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（√）
4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（√）
5．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（×）6．层次遍历初始堆可以得到一个有序的序列。（×）
7．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（√）
8．线性表的顺序存储结构比链式存储结构更好。（×）
9．中序遍历二叉排序树可以得到一个有序的序列。（√）
10.快速排序是排序算法中平均性能最好的一种排序。（√）
11．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（√）12．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（√）
13．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（√）14．完全二叉树中的叶子结点只可能在最后两层中出现。（√）
15．哈夫曼树中没有度数为1的结点。（√）
16．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（√）
17．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（√）
18．由树转化成二叉树，该二叉树的右子树不一定为空。（×）
19．线性表中的所有元素都有一个前驱元素和后继元素。（×）
20.带权无向图的最小生成树是唯一的。（×）
21.如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（√）
22.设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（×）
23.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（√）
24.二维数组和多维数组均不是特殊的线性结构。（×）
25.向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（×）
26.如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（√）
27.非空的双向循环链表中任何结点的前驱指针均不为空。（√）
28.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（√）
29.图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（√）
30.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（√）
31.有向图的邻接表和逆邻接表中表结点的个数不一定相等。(× )
32.对链表进行插入和删除操作时不必移动链表中结点。(√ )
33.子串“ABC”在主串“AABCABCD”中的位置为2。(√ )
34.若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。(√ )
35.希尔排序算法的时间复杂度为O(n2)。(× )
36.用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。(× )
37.中序遍历一棵二叉排序树可以得到一个有序的序列。(√)
38.入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。(√ )
39.顺序表查找指的是在顺序存储结构上进行查找。（×）
40.堆是完全二叉树，完全二叉树不一定是堆。（√）
四、简答题
1、四类数据结构
答；Ⅰ、集合；结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。
Ⅱ、线性结构：结构中数据元素之间存在一个对一个的关系。
Ⅲ、树形结构：结构中的数据元素之间存在一个对多个的关系。
Ⅳ、图形结构或网状结构：结构中的数据元素之间存在多个对多个的关系。
2、什么叫稳定的排序？列出基本稳定排序的算法。
答：假定在K i=K j（1≤i≤n，1≤j≤n，i≠j）,且在排序前的序列中R i领先于R j（即i 基本稳定的排序方法：直接插入排序、冒泡排序、归并排序、基数排序。 不稳定的排序方法：直接选择排序、希尔排序、快速排序和堆排序。 3、散列函数的基本概念、设计原则。 答：基本概念： 在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应，我们称这种对应关系为f的散列函数。 设计原则： 根据散列函数的思想建立一个散列表，在建立一个散列表之前需要解决两个主要问题。（1）构造一个合适的散列表。常用方法有：直接定址法、数字分析法、平方取和法、折叠法、保留余数法、随机数法。 （2）处理冲突的方法：开放定址法、链地址法、建立一个公共溢出区。 4、（给出一个时间复杂度或一种表示方法，分析每一个字母的含义） 略 5、在一个双向循环链表中，我们要实现数据元素的插入所对应基本的操作。 略 五、综合题 1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。 解： 2、在链式存储结构上设计直接插入排序算法 解： void straightinsertsort(lklist *&head) { lklist *s,*p,*q; int t; if (head==0 || head->next==0) return; else for(q=head,p=head->next;p!=0;p=q->next) { for(s=head;s!=q->next;s=s->next) if (s->data>p->data) break; if(s==q->next)q=p; else{q->next=p->next; p->next=s->next; s->next=p; t=p->data;p->data=s->data;s->data=t;} } } 3.试编写算法,删除双向循环链表中第k个结点。（老师中说要删除节点的前驱和后序）void del(DUNODE **head,int i) { DUNODE *p; if(i==0) { *head=*head->next; *head->prior=NULL; return(0); } Else {for(j=0;j p=p->next; if(p==NULL||j>i) return(1); p->prior->next=p->next; p->next->prior=p->proir; free(p); return(0); } 4、给出二叉树结构图实现变历算法，先中序后序、考察先序变点，对先中后序访问，输出结点的次序。 略 填空题 1.文件可按其记录的类型不同而分成两类，即( 操作系统文件 )和( 数据库 )文件。 2.数据库文件按记录中关键字的多少可分成( 单关键字文件 )和( 多关键字文件 )两种文件。 3.文件由( 记录 )组成，记录由( 数据项 )组成。 4.从用户观点看，文件的逻辑结构通常可以区分为两类：一类是如dBASE中数据库文件那样的文件组织结构，称为( 数据库 )文件；另一种是诸如用各种文字处理软件编辑成的文本文件，称为( 文本 )文件。 从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即( 顺序组织 )、 ( 随机组织 )、( 链组织 )。 B+树适用于组织( 随机组织 )的索引结构， m阶B+树每个结点至多有( m ) 除根结点外每个结点至少有( (m/2)向上取整 )个儿子，根结点至少有( 2 )个儿子，有k个儿子的结点必有( k )个关键码。 5.物理记录之间的次序由指针相链表示的顺序文件称为( 串联文件) 6.顺序文件中，要存取第I个记录，必须先存取( 第I-1 )个记录。 7.索引顺序文件既可以顺序存取，也可以( 随机 )存取。 8.建立索引文件的目的的( 提高查找速度 )。 9.索引顺序文件是最常用的文件组织之一，通常用( 树 )结构来组织索引。 10.倒排文件的主在优点在于( 检索记录块 )。 11.检索是为了在文件中满足一定条件的记录而设置的操作。检索可以按( 关 键字 )检索，也可以按( 记录号 ) 检索； 按( 记录号 ) 检索又可以有( 顺序 ) 检索和( 直接 ) 检索。 12.哈希检索的技术的关键是( 构造哈希函数 )和( 解决冲突的方法 )。结构来组织索引。 13.VSAM系统是由( 索引集 )、( 顺序集 ) 、( 数据集 )构成的。 14.VSAM( 虚拟存储存取方法 )文件的优点是：动态地( 分配和释放存储空间 ) ，不需要文件进行( 重组 ) ，并能较快地( 对插入的记录 ) 进行查找。 一～五章选择题 一 1.学习数据结构的主要目的是( C )。 A．处理数据计算问题 B．研究程序设计技巧 C．选取合适数据结构，写出更有效的算法 D．是计算机硬件课程的基础2.数据结构是一门研究非数值计算的程序设计问题中计算机的逻辑存储以及 它们之间的( B )和运算的科学。 A．结构 B．关系 C．运算 D．算法 3.在计算机中存储一个数据元素的位串称为 ( A ) 。 A. 结点 B. 数据项 C. 数据字段 D. 字符串 4.算法指的是( C ) A.计算机程序 B.排序算法 C.解决问题的有限运算序列 D.解决问题的计算方法 5.( D )是数据不可分割的最小单位。 A．数据结构 B．数据对象 C．数据元素 D．数据项 6.数据结构有 ( D ) 种基本逻辑结构。 A. 1 B. 2 C. 3 D. 4 7.在数据结构中，从逻辑上可以把数据结构分成( C )。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 8.通常所说的时间复杂度是指( B )。 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 《数据结构》期末考试题型及分值 （1）简答题6题*5分=30分简要回答要点 （2）分析题6题*5分=30分给出结果 （3）设计题1题*10分=10分设计思想及结果 （4）编程题1题*10分=10分完整代码 （5）综合题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析{定义=功能（ADT）表示=存储结构体实现=算法（基本操作）算法分析=时间、空间复杂度} 考试概念有：1.数据结构{一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构） 二、非线性表（集合-树-图）} 2.抽象数据类型数据对象-数据关系-基本操作 3.算法性质-要求（设计）-效率（度量） 4.实例查找：高效查找算法 排序：高效的排序算法 分析题考试题目参考 （1）1-2-3-4-5-6顺序建BBST （2）6-5-4-3-2-1顺序建BBST 简答题实例 设计题： （1） （2） 数据结构试卷（一） 三、计算题（每题6分，共24分） 1. 在如下数组A 中链接存储了一个线性表，表头指针为A[0].next ，试写出该线性表。 A01234567 dat a 60 50 78 90 34 40 nex t 3 5 7 2 0 4 1 线性表为：（78，50，40，60，34，90）??????? ?????????01110 10 1 11101 11010101110 2. 请画出下图的邻接矩阵和邻接表。 3. 已知一个图的顶点集V 和边集E 分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20 4.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。见图12 图12 图11 四、阅读算法（每题7分，共14分） 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 A. 6 B. 4 C. 3 D. 2 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2) 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（） 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 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（） 一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 数据结构复习要点带答案 算法的五大特性：（有零个或多个输入）、（有一个或多个输出）、（有穷性）、（确定性）、（可行性）。 算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列；算法分析的目的是（分析算法的效率以求改 进），算法分析的两个主要方面是（空间性能和时间性能）。 1.算法质量的标准：时间复杂度是测量一个算法优劣的重要标准。 时间复杂度的计算：设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（Ο(1)），若为n*log25n，则表示成数量级的形式为（Ο(nlog2n)）。 【分析】：用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2.数据、数据元素、数据项的关系：（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体 进行考虑和处理；（数据项）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。 【分析】数据结构指的是数据元素以及数据元素之间的关系。 3.设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。 试画出其逻辑结构图并指出属于何种结构。 【解答】其逻辑结构图如图1-3所示，它是一种图结构。 4.栈的特性：栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一段叫做栈顶，另一 端叫做栈底，不含任何数据元素的栈叫做空栈。（栈）可作为实现递归函数调用的一种数据结构。 【分析】递归函数的调用和返回正好符合后进先出性。 栈的特点是先进后出，即：进去的早，出来的晚！ 54321进栈，5在栈底，1在栈顶！ 出一次栈，则栈顶的1先出来，2成为新的栈顶。 ABCD入栈，D成为新的栈顶。 全部出栈：D C B A 2 3 4 5 综上，所有元素退栈顺序为：1 D C B A 2 3 4 5 5.入栈：template 第1章绪论 一、判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（×） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√） 7.数据的存储结构是数据的逻辑结构的存储映象。（√） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和步骤的描述。（√） 二、填空题 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算法和事后统计法。 16.一个算法的时间复杂度是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。 18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（nlog2n）。 19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）。 20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学 科。 三、选择题 1.数据结构通常是研究数据的（A）及它们之间的相互关系。 A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑 2.在逻辑上可以把数据结构分成（C）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．部结构和外部结构。 3.数据在计算机存储表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。 A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构 4.非线性结构中的每个结点（D）。 A．无直接前驱结点．B．无直接后继结点． 第一章概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K）以及这些数据之间的一组二元关系（关系集合R）来表示：(K, R) 结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R是定义在集合K上的一组关系，其中每个关系r（r∈R）都是K×K上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char）、指针类型（pointer）b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a．大Ο分析法：上限，表明最坏情况 b．Ω分析法：下限，表明最好情况 c．Θ分析法：当上限和下限相同时，表明平均情况 第二章线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L（设每个元素需占用L个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e.插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head和tail指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n）】 e.不足：next仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head和tail指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相比其比例较大时，应该慎重选择 第三章栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项><项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ?<常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp为中缀表达式，PostfixExp为后缀表 达式 初始化操作数栈OP，运算符栈OPND； OPND.push('#'); 读取InfixExp表达式的一项 操作数：直接输出到PostfixExp中； 操作符： 当‘（’：入OPND; 当‘）’：OPND此时若空，则出错；OPND若 非空，栈中元素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若为‘（’，弹出即 可 当‘四则运算符’：循环（当栈非空且栈顶不是 ‘（’&& 当前运算符优先级>栈顶运算符优先 级），反复弹出栈顶运算符并输入到 PostfixExp中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是 递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作 在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear；队满： (rear+1)%n==front 第五章二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶 结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶 结点的层数 d.如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作满二 叉树 e.如果一颗二叉树最多只有最下面的两层结点 度数可以小于2；最下面一层的结点都集中在 该层最左边的位置上，则称此二叉树为完全二 叉树 f.当二叉树里出现空的子树时，就增加新的、特 殊的结点——空树叶组成扩充二叉树，扩充二 叉树是满二叉树 外部路径长度E：从扩充的二叉树的根到每个 外部结点（新增的空树叶）的路径长度之和 内部路径长度I：扩充的二叉树中从根到每个内 部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i层（根为第0层，i≥0）最多有 2^i个结点 b. 深度为k的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的 结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其 分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子 树(指针)数目等于其结点数加1 f. 有n个结点（n>0）的完全二叉树的高度为 ?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n个结点的完全二叉树，结点按层 次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点 编号是(i-1)/2 2) 当2i+1数据结构复习题总结
数据结构试题库答案
(完整版)非常实用的数据结构知识点总结
数据结构期末考试复习总结,DOC
数据结构复习题(附答案)
《数据结构》题库及答案
数据结构复习要点(整理版).docx
《数据结构》期末考试题带答案(99%能过)
数据结构复习题附答案
数据结构试题及答案(10套最新)
数据结构复习提纲(整理)
2015年数据结构期末考试题及答案
算法与数据结构题库与答案
2021年自考02331数据结构重点总结最终修订
数据结构期末复习总结超详细1
数据结构练习试题和答案解析
大学数据结构期末知识点重点总结
相关主题
文本预览