下载文档原格式
1．顺序存储结构中数据元素之间的逻辑关系是由（存储位置）表示的。
2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（顺序表）存储方式最节省时间。
3. 执行下面程序段时，语句S的执行次数为(n+1)(n+2)/24 对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（顺序表）存储方式最节省时间。
5．在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为：n – i + 16．非空的单循环链表由头指针head指示，p 指针指向链尾结点的条件是（p->next==head）。
7．下列选项中，（可以随机访问表中的任意元素）是链表不具有的特点。
8.假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。
则表示该遗产继承关系的最合适的数据结构应该是（图）。
9．栈和队列的共同点是（只允许在端点处插入和删除元素）10．一个队列的入队序列是a,b,c,d，则该队列的出队序列是（a,b,c,d）。
11.带头结点的单链表h为空的判断条件是（h->next== NULL）。
12. 下面关于串的叙述中，哪一个是不正确的？（空串是由空格构成的串）13．判断一个最大容量为m的循环队列Q为空的条件是（Q->front==Q->rear）。
14．在一棵树中，每个节点最多有（1）前驱节点？15．已知完全二叉树的第7层有10个叶子结点，则整个二叉树中结点数为（73）。
16. 下面的说法中，不正确的是（稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储）17．在一棵深度为k的满二叉树中，结点总数为（2k-1）18．数组A中，每个元素的长度为3个字节，行下标从1到5，列下标从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（90）。
19. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有的顶点，则该图一定是（连通图）。
第七章图一、选择题1．图中有关路径的定义是（）。
A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n23．一个n个顶点的连通无向图，其边的个数至少为（）。
A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。
A．n-l B．n C．n+l D．2n5．一个有n个结点的图，最少有（B ）个连通分量，最多有（D ）个连通分量。
A．0 B．1 C．n-1 D．n6. 下列说法不正确的是（）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程7．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b8. 在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( )。
A. O(n)B. O(n+e)C. O(n2)D. O(n3)9. 求解最短路径的Floyd算法的时间复杂度为( )。
A．O（n） B. O（n+c） C. O（n*n）D. O（n*n*n）10．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。
一、填空题1．数据结构根据数据元素之间关系的不同特性，有四种基本结构：集合、线性结构、和。
2．数据结构的形式定义可用二元组表示，其成分分为数据元素的有限集，和。
3．一个好的算法设计应满足正确性、、健壮性和效率与低存储量需求。
4．数组是一种存取的存储结构。
5．串中组成的子序列称该串的子串。
6．稀疏矩阵存储时，常采用三元组表和的表示方法。
7．设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子结点的个数是。
8．指针pred 指向刚刚访问过的结点，p 指向当前访问的结点，结点的结构含有左指针lchild，右指针rchild，左标志ltag，右标志rtag，当结点的左指针为空时，线索化操作为：p->ltag=1；和。
9．用图的顶点表示活动，用弧表示活动间的优先关系的有向图称为网。
10．排序方法稳定的，是指排序后的序列中的元素前后次序仍不变。
11．文件在存储介质（磁盘或磁带）上的组织方式称为文件的。
12．索引文件是包括和索引表两大部分的文件。
13．在算法是正确的前提下，评价算法的两个标准是、。
14．链表是一种存取的存储结构。
15．设链栈的栈顶指针为LS，链栈的结点结构为，栈空的条件是。
16．在非空双链表（结点结构为）中，指针p指向该链表中的某个结点。
若要指针p往前移动两个结点，即使p指向当前结点的前驱的前驱（假定存在这样的结点），则需要执行一个语句。
17．设无向图G用邻接表表示，图中顶点V i的度等于。
18．中序遍历二叉排序树可得到一个关键字的。
19．后序遍历如图所示的一棵二叉树，所得到结点序列为。
20．在有n 个叶子结点的哈夫曼树中，其结点总数为 。
21．含有n 个顶点的无向图是一个环，则它有 棵生成树。
22．设单链表的结点结构为，且r 始终指向单链表的最后一个结点，要在最后一个结点之后插入由s 所指向的结点，需要执行的三条语句是 ；r=s ；s->next=NULL ；23．串中任意个连续的字符组成的子序列称为 。
二、填空题1. 线性表是一种典型的___线性______结构。
2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移__n-i+1__个元素。
3. 顺序表中逻辑上相邻的元素的物理位置__相邻______。
4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需向__前___移一个位置，移动过程是从_前____向_后____依次移动每一个元素。
5. 在线性表的顺序存储中，元素之间的逻辑关系是通过__物理存储位置_____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过__链域的指针值_____决定的。
6. 在双向链表中，每个结点含有两个指针域，一个指向___前趋____结点，另一个指向____后继___结点。
7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用___顺序__存储结构为宜。
相反，当经常进行的是插入和删除操作时，则采用__链接___存储结构为宜。
8. 顺序表中逻辑上相邻的元素，物理位置__一定_____相邻，单链表中逻辑上相邻的元素，物理位置___不一定____相邻。
9. 线性表、栈和队列都是__线性_____结构，可以在线性表的___任何___位置插入和删除元素；对于栈只能在___栈顶____位置插入和删除元素；对于队列只能在___队尾____位置插入元素和在___队头____位置删除元素。
10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为__单链表_______和__双链表_____；而根据指针的联接方式，链表又可分为__循环链表______和__非循环链表______。
11. 在单链表中设置头结点的作用是__使空表和非空表统一______。
12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为_o(1)_____，在给定值为x的结点后插入一个新结点的时间复杂度为__o(n)_____。
13. 对于一个栈作进栈运算时，应先判别栈是否为__栈满_____，作退栈运算时，应先判别栈是否为_栈空______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为___m____。
《数据结构（C语言版第2版）》（严蔚敏著）第三章练习题答案第3章栈和队列1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。
A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。
（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。
A．i B．n-i C．n-i+1 D．不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。
（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。
A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。
（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。
A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；答案：A解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。
《数据结构》练习题一、选择题1．一个数组元素a[i]与（ A ）的表示等价。
A ．*（a+i ） B ．a+i C ．*a+i D ．&a+ia 是存储的是数组首地址，*a 指向的就是数组第一个元素a[0],所以*（a+i ）的地址和a[i]的地址一样。
数组和指针在一定程度上本质是一样的。
2．当利用大小为N 的数组顺序存储一个栈时，假定用top==N 表示栈空，则退栈时，修改top 指针的语句是（ A ）。
A ．top++;B ．top=0;C ．top--;D ．top=N; 3．队列的删除操作是在（ A ）进行。
A ．队首B ．队尾C ．队前D ．队后队列删除元素是在队首进行，队列是进先先出，相对来说，队首元素是最先进入队列的，因此出队应该是在队首进行。
队列其实就和我们平时排队一样的4．二叉树上叶子结点数等于（ C ）。
A ．分支结点数加1B ．单分支结点数加1C ．双分支结点数加1D ．双分支结点数减15．哈希冲突是指（ D ）。
A ．两个元素具有相同的序号B ．两个元素的键值不同，而其他属性相同C ．数据元素太多D ．不同键值的元素对应于相同的存储地址6．由权值分别为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ A ）。
A ．51B ．23C ．53D ．742310 135 56 72 3(2+3)*3+5*2+(6+7)*2=517．某程序的时间复杂度为)log log 1003(22n n n n +⨯+，其数量级表示为（ B ）。
A ．O(n)B ．)log (2n n OC ．O(100)D ．)(log 2n O8．从二叉搜索树中查找一个元素时，其时间复杂度大致为（ C ）。
A ．O(n)B ．O(1)C ．)(log 2n OD ．)(2n O9．在线性表的散列存储中，若用m 表示散列表的长度，n 表示待散列存储的元素的个数，则装填因子α等于（ A ）。
数据结构基本概念练习题1、选择练习题1）执行下面程序段时，执行S语句的次数为-------for(int I=1;I<=n;I++)for(int j=1;j<=I;j++)S;(A) n^2 (B) n^2/2 (C) n(n+1) (D) n(n+1)/2答案：D2）算法是指令的有限序列，其中每一条指令表示一个或多个操作。
下列______不属于算法的五个特性之一。
(A) 有一或多个输出(B) 有零或多个输入(C) 有穷性(D) 通俗易懂性答案：D3）若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
(A) 顺序表(B) 双链表(C) 带头结点的双循环链表(D) 单循环链表答案：A4）下面的叙述正确的是（）(A) 线性表在链式存储时，查找第i个元素的时间同i的值成正比;(B) 线性表在链式存储时，查找第i个元素的时间同i的值无关;(C) 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比;(D) 以上说法都不对.答案：A5) 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。
(A) 单链表(B) 顺序表(C) 单向循环链表(D) 双链表答案：B6) 在双向链表指针p指向的结点前插入一个指针q指向的结点操作是( )。
(A) p->prior=q;q->next=p;p->prior->next=q;q->prior=q;(B) p->prior=q;p->prior->next=q;q->next=p;q->Prior=p->prior;(C) q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;(D) q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;答案：C7) 设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。
数据结构练习题1一、单项选择题，在括号内填写所选择的标号（每小题1分，共12分）2. 以下说法错误的是（）。
A. 抽象数据类型具有封装性。
B. 抽象数据类型具有信息隐蔽性。
C. 使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。
D. 抽象数据类型的一个特点是使用与实现分离。
3. 设有一个n n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（）处。
A. (i+3)*i/2B. (i+1)*i/2C. (2n-i+1)*i/2D. (2n-i-1)*i/24. 已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（）。
A. O(1)B. O(m)C. O(n)D. O(m+n)5. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。
A. front == rearB. front != NULLC. rear != NULLD. front == NULL7. 在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于( )。
A. 2h-1B. 2h+1C. 2h-1D. 2h8. 一棵树的广义表表示为a(b,c(e,f(g)),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为( )。
A 1B 2C 3D 49. 向具有n个结点的、结构均衡的二叉搜索树中插入一个元素的时间复杂度大致为( )。
A. O(1)B. O(log2n )C. O(n)D. O(nlog2n)10. 具有n个顶点的有向无环图最多可包含( )条有向边。
A．n-1 B．n C．n(n-1)/2 D．n(n-1)11. 图的广度优先搜索类似于树的（）次序遍历。
A. 先根B. 中根C. 后根D. 层次12. 如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中( )算法最快。
1 第1章 选择题： 1.1 数据结构在计算机内存中的表示是指： A．数据的存储结构 B.数据结构 C．数据的逻辑结构 D.数据元素之间的关系 1.2 数据的逻辑结构是指： A. 数据所占的存储空间量 B．各数据元素之间的逻辑关系 C. 数据在计算机中顺序或链接的存储方式 D. 存储在内存或外存中的数据 1.3 在下列的叙述中，正确的是： A．数据的逻辑结构是指数据的各数据项之间的逻辑关系。 B．数据的物理结构是指数据在计算机内的实际存储形式。 C．在顺序存储结构中，数据元素之间的关系是显示体现的。 D．链接存储结构是通过结点的存储位置相邻来体现数据元素之间的关系。 填空题： 1.4 数据结构主要研究 数据的逻辑结构 ， 数据的存储结构 ， 数据的运算 三个方面的内容。 1.5 链接存储的特点是通过附加 指针域 来表示数据元素之间的逻辑关系。 1.6 数据结构中讨论的三种经典结构包括： 线性表 ， 树 ， 图 。 1.7 数据结构中常用的存储方法有： 顺序 ， 链接 ， 索引 ， 散列 。 1.8 顺序存储结构可以通过位置 隐含 表示关系，链接存储结构通过附加指针来 显示 表示关系。 1.9 算法的特性包括 有穷性 ， 确定性 ， 可行性 ，输入和输出。 1.10 算法性能分析的两个主要定量评价指标是 时间复杂度 和 空间复杂度 。 简答题： 1.11 数据结构研究的三方面内容之间有什么联系和区别？ 数据结构研究的三方面内容包括: 数据的逻辑结构、存储结构和运算。数据的逻辑结构是数学模型，存储结构是指逻辑结构到存储区域的映射，运算是定义在逻辑结构上，实现在存储结构上。 1.12 简述数据结构中讨论的三种经典结构的逻辑特征是什么？ 三种经典结构：线性表、树和图。逻辑特征分别为： （1）线性表：一对一。有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点。 （2）树：一对多。有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点。 （3）图：多对多。可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点。 1.13 简述各种常用存储方法的基本思想。 各种方法的基本思想： 顺序存储：逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。 链接存储：通过附加指针域表示数据元素之间的关系。 索引存储：除了存储数据元素，还要建立附加的索引表来标识数据元素的地址。 散列存储：根据关键字直接计算出该结点的存储地址，通常称为关键字－地址转换法。 2
第2章 选择题： 2.1 线性表L=（a1，a2，…，an），下列说法正确的是： A. 每个元素都有一个直接前驱和一个直接后继。 B. 线性表中至少有一个元素。 C. 表中元素的排列顺序必须是由小到大或由大到小。 D. 除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继。 2.2 下面关于线性表的叙述中，错误的是： A．线性表若采用顺序存储，必须占用一片连续的存储单元 B．线性表若采用顺序存储，便于进行插入和删除操作 C．线性表若采用链接存储，不必占用一片连续的存储单元 D．线性表若采用链接存储，便于插入和删除操作 2.3 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为： A .n-i+1 B .n-i C .i D .i-1 2.4 删除长度为n的顺序表中的第i(1≤i≤n)个位置上的元素，元素的移动次数为： A. n-i+1 B. n-i C. i D. i-1 2.5 已知一个带头结点单链表L，在表头元素前插入新结点 *s的语句为： A. L=s; s->next=L; B. s->next=L->next; L->next=s; C. s=L; s->next=L; D. s->next=L; s=L; 2.6 已知一个不带头结点单链表的头指针为L，则在表头元素之前插入一个新结点*s的语句为： A. L=s; s->next=L; B. s->next=L; L=s; C. s=L; s->next=L; D. s->next=L; s=L; 2.7 已知单链表上一结点的指针为p，则在该结点之后插入新结点*s的正确操作语句为： A． p->next=s; s->next=p->next; B． s->next=p->next; p->next=s; C． p->next=s; p->next=s->next; D． p->next=s->next; p->next=s; 2.8 已知单链表上一结点的指针为p，则删除该结点后继的正确操作语句是： A． s= p->next; p=p->next; free(s); B． p=p->next; free(p); C． s= p->next; p->next=s->next; free(s); D． p=p->next; free(p->next); 2.9 设一个链表最常用的操作是在表尾插入结点和在表头删除结点，则选用下列哪种存储结构效率最高？ A. 单链表 B. 双链表 C. 单循环链表 D. 带尾指针的单循环链表 2.10 线性表的链接存储结构是一种（ ）存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 2.11 链表不具备的特点是： A. 插入删除不需要移动元素 B. 不必事先估计存储空间 C. 可随机访问任一结点 D. 所需空间与其长度成正比 填空题： 2.1 在单链表L中，指针p所指结点有后继结点的条件是 p->next!=NULL 。 2.2 判断带头结点的单链表L为空的条件 L->next==NULL。 2.12 顺序表和链表中能实现随机存取的是 顺序表 ，插入、删除操作效率高的是 链表 。 2.13 对于一个具有n个结点的单链表，已知一个结点的指针p，在其后插入一个新结点的时间复杂度为 O（1） ；若已知一个结点的值为x，在其后插入一个新结点的时间复杂度为 O（n） 。
2.14 顺序表的存储密度 大 ，链表的存储密度 小 。 3
简答题： 2.15 比较顺序表和链表这两种线性表不同存储结构的特点。
2.16 简述头结点的作用。 头结点的作用是使得单链表在表头位置的插、删操作同中间位置的插、删操作完全相同。即使“空表”与“非空表”的操作统一，也使“表头结点”与其他位置结点的操作完全一致，无须特殊处理。 2.17 写出单链表存储结构的C语言描述。 typedef int DataType; typedef struct Node { DataType data; struct Node *next; }LinkList;
完善程序题： 2.18 设计一个算法，其功能为：向一个带头结点的有序单链表（从小到大有序）中插入一个元素x，使插入后链表仍然有序。请将代码补充完整。 typedef int DataType; typedef struct Node { DataType data; ; /*定义指向该结构类型的指针变量next*/ }Linklist; void insert(Linklist *L,DataType x) { Linklist *s,*p=L; while(p->next && p->next->data; /*p指针后移一步*/ ; /*申请一个新结点空间，将其地址赋给变量s*/ s->data=x; ; ; /*将*s结点插入到*p结点的后面*/ } struct Node * next; p=p->next; s=(LinkList *)malloc(sizeof(LinkList)); s->next=p->next; p->next=s;
2.19 设计一个函数功能为：在带头结点的单链表中删除值最小的元素。请将代码补充完整。 typedef int DataType; typedef Node /*定义结构体类型*/ { DataType data; struct Node * next; }LinkList;
顺序表 存储密度大 存储空间连续 静态分配 随机存取 插、删效率低
链表 存储密度大 存储空间可不连续 动态分配 顺序存取 插、删效率高 4 void deleteMin(LinkList *L) { LinkList *p=L->next,*q; /*首先查找值最小的元素，指针q指向最小元素结点*/ q=p; while(p) { if( p->data < q->data) q=p; ; /* p指针后移一步，比较单链表中的每一个结点*/ } if(!q) return; /*不存在最小结点（空表）时，直接退出*/ p=L; /*若存在最小结点，则先找到最小结点的前驱，即*q的前驱*/ while( ) p=p->next; ; /*从单链表中删除最小元素结点（指针q所指结点）*/ ; /* 释放指针q所指结点的空间*/ }
struct p=p->next; p->next!=q p->next=q->next; free(q); 算法设计题： 2.20 已知长度为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。分两种情况编写函数：（1）线性表采用顺序存储；（2）线性表采用单链表存储。 （1）线性表采用顺序存储 #define MAX 1024 typedef int DataType; typedef struct { DataType data[MAX]; int last; } SeqList; int LocateElem (SeqList *L, DataType item) { int i,j=0; for(i=0;i<=L->last ;i++) if( L->data[i] >item ) j++; return j; } （2）线性表采用单链表存储 typedef int DataType; typedef struct Node { DataType data; struct Node *next; }LinkList; int locateElem(LinkList *L, DataType item )
