C.数据的逻辑结构和存储结构
D.数据的逻辑结构、存储结构及其数据在运算上的实现
A.为解决某问题的算法与为该问题编写的程序含义是相同的
B.算法最终必须由计算机程序实现
C.算法的可行性是指指令不能有二义性
D.以上几个都是错误的
3.计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出( C )等5个特性
A.可执行性、有穷性和可扩充性
B.可执行性、有穷性和确定性
C.确定性、有穷性和稳定性
D.易读性、稳定性和确定性
6.数据的存储结构包括顺序、链接、散列和( D )4种基本类型
7.通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量。以下解释错误的是(D )
A.正确性算法应能正确地实现预定的功能(即处理要求)
B.易读性算法应易于阅读和理解，以便于调试、修改和扩充
C.健壮性当环境发生变化时，算法能适当地做反应或进行处理，不会产生不需要的运行结果
D.高效性即达到所需要的时间性能
8.关于逻辑结构，以下说法错误的是( B )
A.逻辑结构与数据元素本身的形式、内容无关
B.逻辑结构与数据元素的相对位置有关
C.逻辑结构与所含结点个数无关
D.一些表面上很不相同的数据可以有相同的逻辑结构
9.根据数据元素之间关系的不同特性，以下4类基本逻辑结构反映了4类基本数据组织形式。下列解释错误的是( B )
A.集合中任何两个结点间都有逻辑关系，但组织形式松散
B.线性结构中结点按逻辑关系依次排列成一条“锁链”
C.树型结构具有分支、层次特性，其形态有点像自然界中的树
D.图状结构中各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
1.顺序存储方式只能用于存储线性结构
2.数据元素是数据的最小单位
3.算法可用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了
4.数据结构是带有结构的数据元素的集合
5.数据的逻辑结构是指各数据元素间的逻辑关系，是用户根据需要而建立的
6.数据结构、数据元素、数据项在计算机中的映象（或表示）分别称为存储结构、结点、数据域、
7.数据的物理结构是指数据在计算机内实际的存储形式
1.一个数据结构在计算机中的( 存储形式 )称为存储结构
2.对于给定的n个元素，可以构造出的逻辑结构有( 集合)、(线性结构 )、( 树型结构)、( 图状结构)4种
3.数据是描述客观事物的数、字符以及所有( 输入)计算机中并被计算机程序所( 识别 )的符号
4.从一维数组a[n]中顺序查找出一个最大值元素的平均时间复杂度为( O(n)),读取一个二维数组b[m,n]中任一元素的时间复杂性为(O(1) )
5.线性结构中元素间存在( 一对一 )的关系，树形结构中元素间存在(一对多)的关系，图形结构中元素存在(多对多)的关系，而集合结构中元素间不存在( 逻辑 )关系
1.线性表是具有n个( C )的有限序列
2.线性表的静态存储结构与顺序存储结构相比优点是( B)
C.便于插入和删除 D.便于利用零散的存储器空间
3.若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素算法的时间复杂度为(C )
4.(1)静态链表既有顺序存储的优点,又有动态链表的优点.所以,它存取表中第i个元素的时间与i无关.
(2)静态链表中能容纳元素个数的最大数在定义时就确定了,以后不能增加.
(3)静态链表与动态链表在元素的插入,删除上类似,不需做元素的移动.
以上说法错误的是( B )
5.将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是(A)
7.若给定有n个元素的向量,则建立一个有序单向链表的时间复杂度为( C)
A.每个元素都有一个直接前驱和一个直接后继
B.线性表中至少要有一个元素
C.表中诸元素的排列顺序必须是由小到大或由大到小
D.除第一个和最后一个元素外,表中每个元素都有一个且仅有一个直接前驱和直接后继
9.对单链表表示法,以下说法错误的是( C )
A.数据域用于存储线性表的一个数据元素
B.指针域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针
C.所有数据通过指针的链接而组织成单链表
D.NULL称为空指针,它不指向任何结点只起标志作用
A.顺序存储方式的优点是存储密度大且插入,删除运算效率高
B.链表的每个结点中都恰好包含一个指针
C.线性表的顺序存储结构优于链式存储结构
D.顺序存储结属于静态结构而链式结构属于动态结构
11.以下说法错误的是(A )
A.对循环链表来说,从表中任一结点出发都能通过前后移操作扫描整个循环链表
B.对单链表来说,只有从头结点开始才能扫描表中全部结点
C.双链表的特点是找结点的前趋和后继都很容易
D.对双链表中来说,结点*P的存储位置既存放在其前趋结点的后继指针域中,也存放在它的后继结点的前趋指针中
12. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个数据元素,则采用(D)存储方式最节省运算时间
13.非空的循环单链表head的尾结点*P满足(A )
1.便于插入和删除操作的是(ABDE )
2.表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素原概率相等时,插入一个元素所需移动的元素平均个数为( e),删除一个元素所需移动的平均个数为 ( a ).
3.从表中任一结点出发都能扫描整个表的是( DE ).
1.线性表采用链表存储时,结点和结点内部的存储空间都可以是不连续的
2.在具有头结点的链式存储结构中,头指针指向链表中的第一个数据结点
3.顺序存储的线性表可以随机存取
4.顺序存储结构属于静态结构,链式结构属于动态结构
1.线性表有两种存储结构:一是顺序表,二是链表,试问:
(1)如果有n个线性表同时共存,并且在处理过程中各表的长度会动态地发生变化,线性表的总数也会自动地改变.在此情况下,应选用哪种存储结构?为什么?
(2)若线性表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素,那么应采用哪种存储结构?为什么? 顺序
2.链表所表示的元素是否是有序的?如果有序,则有序性体现在何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解? 链表用指针来表示其逻辑顺序，它所表示的元素不一定在物理是相邻。有序表不仅元素间具有前后顺序，并且元素从小到大排列。
3.用线性表的顺序存储结构来描述一个城市的设计和规划是否合适?为什么? 不合理，因为城市规划不断变化
1.若用单链表来表示队列,则应选用(B)
C.带头指针的非循环链表 D.带头指针的循环链表
2.若用一个大小为6的数组来实现循环队列,且当rear和front和值分别为0和3.当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为多少?( B )
4设栈的输入序列是(1,2,3,4),则( D )不可能是其出栈序列
5.设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的序列是:e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是(C)
6.一般情况下,将递归算法转换成等价的非递增归算法应该设置( A)
8.设栈的输入序列是1,2,…,n;若输出序列的第一个元素是n,则第i个输出元素是( B )
9.循环队列中,tail=32指向队尾元素,head=15指向队头元素的前一个空位置,则元素数目是( C)
10.链栈与顺序栈相比有一个明显的优点,即(B)
A.插入操作更方便B.通常不会出现栈满的情况
C.不会出现栈空的情况D.删除操作更方便
2.一个输入序列abcd经过一个栈到达输出序列,并且一旦离开输入序列后就不能再返回到输入序列,则下面 (ABDE)为正确的输出序列.
1.栈和队列都是限制存取点的线性结构
2.有n个数顺序(依次)进栈,出栈序列有Cn种,即:Cn=
3.即使对不含相同元素的同一输入序列进行两组不同的,合法的入栈和出栈组合操作,所得的输出序列也一定相同
不存在这样的输出序列:…,Pi,…,Pj,…,Pk,…
简单地说,对于输入序列123,不存在输出序列312
再证必要条件:如果初始输入序列为1,2,…,n并入栈,且同时又存在这样的I,j,k,使用权得i<j<k时有Pj<Pk<Pi成立,即对输入序列:
从中可以看出,Pi先进后出满足栈的特点,因为Pi最大也就是在Pj和Pk 之后进入,但却出现了在Pk之前进入的Pj在Pk之前出来;也即说明其不满足先进后出的特点,即与前面假设的栈不符.
2.设串长为n,模式串长为m,则KMP算法所需的附加空间为(A )
3.设S为一个长度为n的字符串,其中的字符各不相同,则S中互异的非平凡子串(非空且不同于S本身)的个数为( D )
5.设字符串中每个字符都不相同,则在字符串匹配中,当模式串位j与主串位i的比较失败时,新一趟匹配开始,主串的位移公式是(D)
7.设两个串p和q,求q在p中首次出现的位置的运算称作( C)
9.串是一种特殊的线性表,其特殊性体现在(B)
1.串是由有限个字符构成的连续序列,串长度为串中字符的个数,子串是主串中字符构成的有限序列. 错
2.子串定位函数的时间复杂度在最坏情况下为O(n*m),因此子串定位函数没有实际使用的价值.
3.设有两个串P和Q,其Q是P的子串,把Q在P中首次出现的位置作为子串Q在P中的位置算法称为模式匹配.
4.KMP算法最大特点是指示主串的指针不需回溯.
1.若某串的长度小于一个常数,则采用何种存储方式最节省空间?
2.已知3个字符串分别为
利用所学字符串基本运算的函数得到结果串为:
要求写出得到上述结果串S所用的函数及执行算法.
第五章数组部分思考题：
1． 试叙述一维数组与有序表的异同。
一维数组是一种特殊的线性表结构，它与有序表的差异在于该结构中不存在元素值之间的递增或递减关系。
2． 简述数组与字符串属于线性表的理由。
3． 有三种稀疏矩阵的存储方法：（1）十字链表法；（2）二维数组法；（3）三元组表示法。
现有一n*n的稀疏矩阵，其非零元素的个数为P，假设在上述三种表示法中，每个域（值和指针）都占4个字节的空间，而且头结点和非头结点有相同的结构。请给出三种表示法表示该矩阵各自所需的空间数（以字节为单位）。
数组可以看成是线性表的扩展，也即此时线性表中的数据元素本身也是一个数据结构。对n维数组来说，可以看作具有n个数据元素的线性表，而每一个数据元素本身又是一个数据结构，即由n-1维的数组构成；依此类推，也即：对于n维数组中的每一个元素来说都受到n个关系（n维）的约束，在每个关系（每一维）中，数据元素都有有一个直接后继（除去最后一个元素）和一个直接前驱（除去最前一个元素）。因此，这n个（n维）关系中的任一关系，就其单个关系而言，仍是线性关系。
串是取值范围受到限制的线性表，即只能取字符集合的字符。因此，串仍然是线性表。
4． 设m*n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[1: (t+1),1:3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义？
解：稀疏矩阵A有t个非零元素，占数组LTMA的存储单元数为3*(t+1)，而用二维数组存储时将占用m*n个存储单元。因此，当t的三元组表示所占存储单元小于用二维数组存储所占存储单元时，采用LTMA才有意义；即：应有3*（t+1）<m*n，也就是：
5． 设按低下标优先存储整数数组A[-3：8，3：5，-4：0，0：7]时，第一个元素的字节存储地址是100，每个整数占4字节，问：A[0，4， -2，5]的存储地址是什么？
利用n维数组数据元素的存储位置公式：
由于本题使用了负下标，因此只需作适当的下标平移，就可以转化为在数组A(0:11,0:2,0:4,0:7)中求A（3，1，2，5）的存储位置。所以有：
6． 设有5对角矩阵A=（aij）20*20，按特殊矩阵压缩存储的方式将其5条对角线上的元素存于数组B[-10:m]中，计算元素A[15,15]的存储位置。（分别考虑按行存放时其存储位置、按对角线顺序存放时的存储位置）
解：由图可知，5对角矩阵A=（aij）n*n的第1行和第n行上有3个非零元素，第2行和n-1行上有4个非零元素，其余行上有5个非零元素。
本题中n=20，由此可计算础按行序存放时，A[15，15]是第几个非零元素。
此外，还可以按对角线顺序进行存放。由于A[15，15]在主对角线上，而第一条对角线元素个数为18，第二条对角线元素数为19，而主对角线元素数虽然为20，但A[15，15]在主对角线上长度为15个元素；故按对角线顺序，A[15，15]为：18+19+15=52个，其存储位置为：52-10-1=41。因此，元素A[15，15]存储于B[41]中。
1. 算法的时间复杂度取决于（ B ）
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
4．从逻辑上可以把数据结构分为（ C ）两大类。
其中 n为正整数，则最后一行的语句频度在最坏情况下是（ D ）
6．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。
7. 静态链表中指针表示的是（ B ）.
8. 在作进栈运算时,应先判别栈是否( ① B ),在作退栈运算时应先判别栈是否( ② A )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ B )。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ D )分别设在这片内存空间的两端,这样,当( ⑤ C )时，才产生上溢。
B. 其中一个栈的栈顶到达栈空间的中心点.
9. 设栈的输入序列是1，2，3，4,则（D ）不可能是其出栈序列。
13．下面关于串的的叙述中，哪一个是不正确的？（ B ）
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
16. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是（ ① H ）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（ ② C ）和（ ③ E
19．稀疏矩阵一般的压缩存储方法有（ C ）两种。
21.设堆栈的输入序列是1、2、…、n，若输出序列的第一个元素是n,则第i个输出元素是（ B ）。
二、判断题(10题,1’/题)
1. 记录是数据处理的最小单位。 (×)
2．算法的优劣与算法描述语言无关，但与所用计算机有关。( ×)
3. 数据结构的抽象操作的定义与具体实现有关。(×)
4. 数据结构的基本操作的设置的最重要的准则是，实现
应用程序与存储结构的独立。( √ )
5. 链表中的头结点仅起到标识的作用。( × )
6. 所谓静态链表就是一直不发生变化的链表。( × )
7. 栈与队列是一种特殊操作的线性表。（ √ ）
8. 通常使用队列来处理函数或过程的调用。（ × ）
9．串是一种数据对象和操作都特殊的线性表。（ × ）
10. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ √ ）
1．数据的物理结构包括 数据 的表示和 关系 的表示。
2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
3.顺序存储结构是通过__位置__表示元素之间的关系的;链式存储结构是通过__指针_表示元素之间的关系的。
4. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：
6. 循环队列的引入，目的是为了克服 假溢出情况 。
7．区分循环队列的满与空，只有两种方法，它们是_另设一个标志位_和少用一个元素空间 。
8．串是一种特殊的线性表，其特殊性表现在 数据元素的取值范围 ；串的两种最基本的存储方式是 堆分配存储、 串块链存储；两个串相等的充分必要条件是长度相等和个对应位置相等 。
11．设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85的地址为_33_。
1. 名词解释：队列(4’)
2．描述以下概念的区别：空格串与空串。6’
3.（1） 什么是递归程序？(4’)
（2） 递归程序在执行时，应借助于什么来完成？(3’
（3） 递归程序的入口语句、出口语句一般用什么语句实现？(3’)
5.双向链表的结点形式为：(4’)
删除此链表中由指针p所指的结点的主要两步操作是：
// 将 a 中整数序列重新排列成自小至大有序的整数序列。
// 将a 中整数序列重新排列成自小至大有序的整数序列。
每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。
C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同
3.数组的存储结构采用顺序存储方式。
4.数组是同类型值的集合。（错 有限 ）
5. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ 错 ）
2. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ Ｂ ）。
5. 稀疏矩阵压缩存储后，必会失去随机存取功能。（ 错）
6. 一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（ 错 ）
5. 二维以上的数组其实是一种特殊的广义表。（ 对 ）
6. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ 错 ）
7. 若一个广义表的表头为空表，则此广义表亦为空表。（ 错 ）
1. 树是结点的有限集合，它（ (1）A)根结点，记为T。其余结点分成为m（m>0）个(（2）A)的集合T1，T2， …，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数称为该结点的( （3）B )。供选择的***：
3．树形结构中元素之间存在一个对多个的关系。 对
3．请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。
1.二叉树与树是两个不同的概念，二叉树也是结点的有限集合，它(（4）A)根结点。可以把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。令T是一棵二叉树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式│λKi-λKj│≤1一定成立时，则称T为一棵（(5)D）。供选择的***：
①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
3．具有10个叶结点的二叉树中有（ B ）个度为2的结点.
8．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为 69 。
1．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。
3．二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是：C
（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；
（2）按二叉树定义，具有三个结点的二叉树共有6种。
5.已知一个二分树的中序序列和后序序列如下：
试画出此二分树的结构。
1．设无向图的顶点个数为n，则该图最多有（ B ）条边。
2．一个n个顶点的连通无向图，其边的个数至少为（ A ）。
3．要连通具有n个顶点的有向图，至少需要（ B ）条边。
5．在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。
1.树中的结点和图中的顶点就是指数据结构中的数据元素。对
2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。 错
3．强连通图的各顶点间均可达。对
4．强连通分量是无向图的极大强连通子图。错
4．G是一个非连通无向图，共有28条边，则该图至少有( 9 )个顶点。
6．如果含n个顶点的图形形成一个环，则它有( n )棵生成树。
7．下图中的强连通分量的个数为（ 3 ）个。
1．下列哪一种图的邻接矩阵是对称矩阵?（ B）
2．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。错
3. 十字链表是无向图的一种存储结构。错
4．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。 错
5. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。 错
6. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。 对
7．N个顶点的连通图用邻接矩阵表示时,
该矩阵至少有(2(n-1) )个非零元素。
8．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的__度数___；对于有向图来说等于该顶点的___出度___。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次
B．遍历的基本算法有两种：深度遍历和广度遍历
C．图的深度遍历不适用于有向图
D．图的深度遍历是一个递归过程
3. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需___队列___存放被访问的结点以实现遍历。
3、从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需____________一个位置。
6、假设三维数组A[10][9][8]按行优先顺序存储(A[0][0][0]为数组第一个元素)，若每个元素占3个存储单元，且首地址为100H，则元素A[9][8][7]的存储起始地址是____________H。
11、设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
1、假设通信电文使用的字符集为{a,b,c,d,e,f}，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。
2、已知一个图如下所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中，请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd，进行广度优先遍历时得到的顶点序列为acbdfe。
某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答问题：
(1)写出执行函数调用f(p)的输出结果；
(2)简述函数f的功能。