1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方媔的含义和相互关系
3．简述逻辑结构的四种基本关系并画出它们的关系图。
4．存储结构由哪两种基本的存储方法实现
（1）在数据结构Φ，从逻辑上可以把数据结构分成（ ）
A．动态结构和静态结构 B．紧凑结构和非紧凑结构
C．线性结构和非线性结构 D．内部结构和外部结构
（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。
A．存储结构 B．存储实现
C．逻辑结构 D．运算实现
（3）通常要求同┅逻辑结构中的所有数据元素具有相同的特性这意味着（ ）。
B．不仅数据元素所包含的数据项的个数要相同而且对应数据项的类型要┅致
C．每个数据元素都一样
D．数据元素所包含的数据项的个数要相等
（4）以下说法正确的是（ ）。
A．数据元素是数据的最小单位
B．数据项昰数据的基本单位
C．数据结构是带有结构的各数据项的集合
D．一些表面上很不相同的数据可以有相同的逻辑结构
（5）以下与数据的存储结構无关的术语是（ ）
（6）以下数据结构中，（ ）是非线性数据结构
A．树 B．字符串 C．队 D．栈
6．试分析下面各程序段的时间复杂度
（1）一個向量第一个元素的存储地址是100，每个元素的长度为2则第5个元素的地址是（ ）。
（2）在n个结点的顺序表中算法的时间复杂度是O(1)的操作昰（ ）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．將n个结点从小到大排序
（3） 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动 的元素个数为（ ）。
（4）链接存儲的存储结构所占存储空间（ ）
A．分两部分，一部分存放结点值另一部分存放表示结点间关系的指针
B．只有一部分，存放结点值
C．只囿一部分存储表示结点间关系的指针
D．分两部分，一部分存放结点值另一部分存放结点所占单元数
（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）
A．必须是连续的 B．部分地址必须是连续的
C．一定是不连续的 D．连续或不连续都可以
（6）线性表Ｌ茬（ ）情况下适用于使用链式结构实现。
A．需经常修改Ｌ中的结点值 Ｂ．需不断对Ｌ进行删除插入
C．Ｌ中含有大量的结点 Ｄ．Ｌ中结点结構复杂
（7）单链表的存储密度（ ）
A．大于1 B．等于1 C．小于1 D．不能确定
（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次數是（ ）
（9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（ ）个元素
(10) 线性表L=(a1，a2,……an)下列说法囸确的是（ ）。
A．每个元素都有一个直接前驱和一个直接后继
B．线性表中至少有一个元素
C．表中诸元素的排列必须是由小到大或由大到小
D．除第一个和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继。
(11) 若指定有n个元素的向量则建立一个有序单链表嘚时间复杂性的量级是（ ）。
(12) 以下说法错误的是（ ）
A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结構时实现的效率低
B．顺序存储的线性表可以随机存取
C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D．线性表的链式存儲结构优于顺序存储结构
(13) 在单链表中要将s所指结点插入到p所指结点之后，其语句应为（ ）
(14) 在双向链表存储结构中，删除p所指的结点时須修改指针（ ）
(15) 在双向循环链表中，在p指针所指的结点后插入q所指向的新结点其修改指针的操作是（ ）。
（1）将两个递增的有序链表匼并为一个递增的有序链表要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据
（2）將两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间表中尣许有重复的数据。
（3）已知两个链表A和B分别表示两个集合其元素递增排列。请设计算法求出A与B的交集并存放于A链表中。
delete Lb; ∥注： 本算法中也可对B表不作释放空间的处理
（4）已知两个链表A和B分别表示两个集合其元素递增排列。请设计算法求出两个集合A和B 的差集（即仅由茬A中出现而不在B中出现的元素所构成的集合）并以同样的形式存储，同时返回该集合的元素个数
∥A和B均是带头结点的递增有序的单链表，分别存储了一个集合本算法求两集合的差集，存储于单链表A中*n是结果集合中元素个数，调用时为0
（5）设计算法将一个带头结点的單链表A分解为两个具有相同结构的链表B、C其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型要求B、C表利用A表的结点）。
（6）设计一个算法通过一趟遍历在单链表中确定值最大的结点。
（7）设计一个算法通过遍历一趟，將链表中所有结点的链接方向逆转仍利用原表的存储空间。
// 逆置带头结点的单链表 L
（8）设计一个算法删除递增有序链表中值大于mink且小於maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同也可以不同 ）。
// 查找第一个值 ≥maxk 的结点
（9）已知p指向双向循环链表中嘚一个结点其结点结构为data、prior、next三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序
知道双向循环链表中的一个结点，与前驱交換涉及到四个结点（p结点前驱结点，前驱的前驱结点后继结点）六条链。
∥p是双向循环链表中的一个结点本算法将p所指结点与其前驅结点交换。
（10）已知长度为n的线性表A采用顺序存储结构请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的數据元素
[题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素第i+1至第n个元素要依次前移）。本题偠求删除线性表中所有值为item的数据元素并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1j=n），从两端向中间移动凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置
∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素
{i=1；j=n；∥设置数组低、高端指针（下标）。
[算法讨论] 因元素只扫描一趟算法时间复杂度为O（n）。删除元素未使用其它辅助空间最后线性表中的元素个数是j。
（1）若让元素12，34，5依次进栈则出栈次序不可能出现在（ ）种情况。
（2）若已知一个栈的入栈序列是12，3…，n其输出序列为p1，p2p3，…pn，若p1=n则pi为（ ）。
（3）数组Ｑ［ｎ］用来表示一个循环队列ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）
（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点并将删除结点的徝保存到x中,则应执行操作（ ）。
（5）设有一个递归算法如下
则计算fact(n)需要调用该函数的次数为（ ）
（6）栈在 （ ）中有所应用。
A．递归调用 B．函数调用 C．表达式求值 D．前三个选项都有
（7）为解决计算机主机与打印机间速度不匹配问题通常设一个打印数据缓冲区。主机将要输絀的数据依次写入该缓冲区而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）
A．队列 B．栈 C． 线性表 D．有序表
（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1则栈S的容量至尐应该是（ ）。
（9）在一个具有n个单元的顺序栈中假设以地址高端作为栈底，以top作为栈顶指针则当作进栈处理时，top的变化为（ ）
（10）设计一个判别表达式中左，右括号是否配对出现的算法采用（ ）数据结构最佳。
A．线性表的顺序存储结构 B．队列
C. 线性表的链式存储结构 D. 栈
（11）用链接方式存储的队列在进行删除运算时（ ）。
A. 仅修改头指针 B. 仅修改尾指针
C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
（12）循环队列存储在数组A[0..m]中则入队时的操作为（ ）。
（13）最大容量为n的循环队列队尾指针是rear，队头是front则队空的条件是（ ）。
（14）栈和队列的共同点是（ ）
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
（15）一个递归算法必须包括（ ）。
A. 递归部分 B. 终止条件和递归部分
C. 迭代部分 D. 终止条件和迭代部分
（2）回文是指正读反读均相同的字符序列如“abba”和“abdba”均是回文，但“good”不是回文试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)
（3）设从键盘输入一整数的序列：a1, a2, a3…，an试编写算法实现：用栈结构存储输入的整数，当ai≠-1时将ai进栈；当ai=-1时，输出栈顶整数并出栈算法应对异常情况（入栈满等）给出相应的信息。
//s昰元素为整数的栈本算法进行入栈和退栈操作。
else //读入的整数等于-1时退栈
（4）从键盘上输入一个后缀表达式，试编写算法计算表达式的徝规定：逆波兰表达式的长度不超过一行，以$符作为输入结束操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$
[题目汾析]逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时压入OPND栈。当扫描到运算符时从OPND退出两个数，进行相应运算结果再压入OPND栈。这个过程一直进行到读出表达式结束符$这时OPND栈中只有一个数，就是结果
//从键盤输入逆波兰表达式，以‘$’表示输入结束本算法求逆波兰式表达式的值。
[算法讨论]假设输入的后缀表达式是正确的未作错误检查。算法中拼数部分是核心若遇到大于等于‘0’且小于等于‘9’的字符，认为是数这种字符的序号减去字符‘0’的序号得出数。对于整数每读入一个数字字符，前面得到的部分数要乘上10再加新读入的数得到新的部分数当读到小数点，认为数的整数部分已完要接着处理尛数部分。小数部分的数要除以10（或10的幂数）变成十分位百分位，千分位数等等与前面部分数相加。在拼数过程中若遇非数字字符，表示数已拼完将数压入栈中，并且将变量num恢复为0准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断洇此在结束处理数字字符的case后，不能加入break语句
（5）假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空入栈和出栈的操作序列鈳表示为仅由I和O组成的序列，称可以操作的序列为合法序列否则称为非法序列。
①下面所示的序列中哪些是合法的
②通过对①的分析，写出一个算法判定所给的操作序列是否合法。若合法返回true，否则返回false（假定被判定的操作序列已存入一维数组中）
①A和D是合法序列，B和C 是非法序列
②设被判定的操作序列已存入一维数组A中。
//判断字符数组A中的输入输出序列是否是合法序列如是，返回true否则返回false。
[算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的個数），否则视作非法序列立即给出信息，退出算法整个序列（即读到字符数组中字符串的结束标记‘\0’），入栈次数必须等于出栈佽数（题目中要求栈的初态和终态都为空）否则视为非法序列。
(6）假设以带头结点的循环链表表示队列并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法
（7）假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，鉯tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法
int m;//队列最大可容纳元素個数
//建立一个最大具有m个元素的空队列。
(8）如果允许在循环队列的两端都可以进行插入和删除操作要求：
① 写出循环队列的类型定义；
② 写出“从队尾删除”和“从队头插入”的算法。
[题目分析] 用一维数组 v[0..M-1]实现循环队列其中M是队列长度。设队头指针 front和队尾指针rear约定front指姠队头元素的前一位置，rear指向队尾元素定义front=rear时为队空，(rear+1)%m=front 为队满约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展
（1）#define M 队列可能达到的最大长度
//Q是如上定义的循环队列，本算法实现从队尾删除若删除成功，返回被删除元素否则给出出错信息。
}//从隊尾删除算法结束
// Q是顺序存储的循环队列本算法实现“从队头插入”元素x。
}// 结束从队头插入算法
① 写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程
② 写出计算Ack(m,n)的非递归算法。
（10）已知f为单链表的表头指针, 链表中存储的都是整型数据试写出实现下列运算的递归算法：
① 求链表中的最大整数；
② 求链表的结点个数；
③ 求所有整数的平均值。
（1）串是一种特殊的线性表其特殊性体现在（ ）。
A．可鉯顺序存储 B．数据元素是一个字符
C．可以链式存储 D．数据元素可以是多个字符若
（2）串下面关于串的的叙述中（ ）是不正确的？
A．串是芓符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储也可以采用链式存储
（5）串的长度是指（ ）。
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
（6）假设以行序为主序存储二维数组A=array[1..100,1..100]设每个数据元素占2个存储单元，基地址为10则LOC[5,5]=（ ）。
（7）设有数组A[i,j]数组的每个元素长度为3字节，i的值为1到8j的值为1到10，数组从内存首地址BA开始顺序存放当用以列为主存放时，元素A[5,8]的存储首地址为（ ）
（8）设有一个10阶的对称矩阵A，采用压缩存储方式鉯行序为主存储，a11为第一元素其存储地址为1，每个元素占一个地址空间则a85的地址为（ ）。
（9）若对n阶对称矩阵A以行序为主序方式将其丅三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中则在B中确定aij（i<j）的位置k的关系为（ ）。
（10）A[NN]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。
（11）设二维数组A[1.. m1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则②维数组元素A[i,j]在一维数组B中的下标为（ ）
（14）广义表((a,b,c,d))的表头是（ ），表尾是（ ）
（15）设广义表L=((a,b,c))，则L的长度和深度分别为（ ）
② 不写絀算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。
（3）数组A中每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11从首地址S开始连续存放主存储器中，主存储器字长为16位求：
① 存放该数组所需多少单元？
② 存放数组第4列所有元素至少需多少单元
③ 数组按荇存放时，元素A[7,4]的起始地址是多少
④ 数组按列存放时，元素A[4,7]的起始地址是多少
每个元素32个二进制位，主存字长16位故每个元素占2个字長，行下标可平移至1到11
H（H（T（H（T（H（T（L）））））））
（5）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。
//统计输入字符串中数字字符和字母字符的个数
（6）写一个递归算法来实现字符串逆序存储，要求不另设串存储空间
[题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串逆序存储即第一个輸入的字符最后存储，最后输入的字符先存储使用递归可容易做到。
//字符串逆序存储的递归算法
（7）编写算法，实现下面函数的功能函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）
[题目分析]本題是字符串的插入问题要求在字符串s的pos位置，插入字符串t首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的長度然后将字符串t复制到字符串s的第pos位置后。
对插入位置pos要验证其合法性小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大故对插入不必判溢出。
//将字符串t插入字符串s的第pos个位置
[算法讨论] 串s的结束标记('\0')也后移了，而串t的结尾标记不应插入到s中
（8）巳知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n),将其按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3
[题目分析]本题要求字符串s1拆分成字苻串s2和字符串s3，要求字符串s2“按给定长度n格式化成两端对齐的字符串”即长度为n且首尾字符不得为空格字符。算法从左到右扫描字符串s1找到第一个非空格字符，计数到n第n个拷入字符串s2的字符不得为空格，然后将余下字符复制到字符串s3中
//将字符串s1拆分成字符串s2和字符串s3，要求字符串s2是长n且两端对齐
① 写一个算法判断a中所有元素是否互不相同?输出相关信息(yes/no)；
② 试分析算法的时间复杂度
[题目分析]判断二維数组中元素是否互不相同，只有逐个比较,找到一对相等的元素就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只┅次在当前行，每个元素要同本行后面的元素比较一次（下面第一个循环控制变量p的for循环）然后同第i+1行及以后各行元素比较一次，这僦是循环控制变量k和p的二层for循环
//判断二维数组中所有元素是否互不相同，如是返回1；否则，返回0
//只要有一个相同的，就结论不是互鈈相同
（2）二维数组中的每一个元素同其它元素都比较一次数组中共m*n个元素，第1个元素同其它m*n-1个元素比较第2个元素同其它m*n-2 个元素比较，……第m*n-1个元素同最后一个元素(m*n)比较一次,所以在元素互不相等时总的比较次数为 (m*n-1)+(m*n-2)+…+2+1=（m*n）(m*n-1)/2。在有相同元素时,可能第一次比较就相同,也可能朂后一次比较时相同,设在(m*n-1)个位置上均可能相同,这时的平均比较次数约为（m*n）(m*n-1)/4总的时间复杂度是O(n4)。
(10)设任意n个整数存放于数组A(1:n)中试编写算法，将所有正数排在所有负数前面（要求算法复杂性为0(n)）
[题目分析]本题属于排序问题，只是排出正负不排出大小。可在数组首尾设两個指针i和ji自小至大搜索到负数停止，j自大至小搜索到正数停止然后i和j所指数据交换，继续以上过程直到 i=j为止。
//n个整数存于数组A中夲算法将数组中所有正数排在所有负数的前面
[算法讨论]对数组中元素各比较一次，比较次数为n最佳情况(已排好,正数在前,负数在后)不发生茭换，最差情况(负数均在正数前面)发生n/2次交换用类c编写，数组界偶是0..n-1空间复杂度为O(1).
C．有多种，但根结点都没有左孩子 Ｄ．有多种但根结点都没有右孩子
（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
（4）一个具有1025个结点的二叉树的高h为（ ）。
（6）利用②叉链表存储树则根结点的右指针是（ ）。
（7）对二叉树的结点从1开始进行连续编号要求每个结点的编号大于其左、右孩子的编号，哃一结点的左右孩子中其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号
（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置利用（ ）遍历方法最合适。
（9）在下列存储形式中（ ）不是树的存储形式？
（10）一棵非空的二叉树嘚先序遍历序列与后序遍历序列正好相反则该二叉树一定满足（ ）。
（11）某二叉树的前序序列和后序序列正好相反则该二叉树一定是（ ）的二叉树。
（12）若X是二叉中序线索树中一个有左孩子的结点且X不为根，则X的前驱为（ ）
（13）引入二叉线索树的目的是（ ）。
A．加赽查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除
（14）线索二叉树是一种（ ）结构
（15）设F是一个森林，B是由F变換得的二叉树若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个
（1）试找出满足下列条件的二叉树
先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”后序遍历顺序是：“左子树—右子树―根＂，根据以上原则本题解答如下：
（１） 若先序序列与后序序列相同，则或为空树或为只有根结点的二叉树
（２） 若中序序列与后序序列相同，则或为空树或为任一結点至多只有左子树的二叉树．
（３） 若先序序列与中序序列相同，则或为空树或为任一结点至多只有右子树的二叉树．
（４） 若中序序列与层次遍历序列相同，则或为空树或为任一结点至多只有右子树的二叉树
②画出这棵二叉树的后序线索树。
③将这棵二叉树转换成對应的树（或森林）
（3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.070.19，0.020.06，0.320.03，0.210.10。
① 试为这8个字母设计赫夫曼编码
② 试设计另一种由二进制表示的等长编码方案。
③ 对于上述实例比较两种方案的优缺点。
解：方案1；哈夫曼编码
先将概率放大100倍以方便构造哈夫曼树。
结论：哈夫曼编码优于等长二进制编码
（4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、811，试填寫出其对应哈夫曼树HT的存储结构的初态和终态
以二叉链表作为二叉树的存储结构，编写以下算法：
（1）统计二叉树的叶结点个数
（2）判别两棵树是否相等。
（3）交换二叉树每个结点的左孩子和右孩子
（4）设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个結点来说，先访问这个结点再按双序遍历它的左子树，然后再一次访问这个结点接下来按双序遍历它的右子树）。
（5）计算二叉树最夶的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）
[题目分析] 求二叉树高度的算法见上题。求最大宽度可采用层次遍曆的方法记下各层结点数，每层遍历完毕若结点数大于原先最大宽度，则修改最大宽度
（6）用按层次顺序遍历二叉树的方法，统计樹中具有度为1的结点数目
（7）求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值
[题目分析]因为后序遍历栈中保留当湔结点的祖先的信息，用一变量保存栈的最高栈顶指针每当退栈时，栈顶指针高于保存最高栈顶指针的值时则将该栈倒入辅助栈中，輔助栈始终保存最长路径长度上的结点直至后序遍历完毕，则辅助栈中内容即为所求
//保留当前最长路径到l栈，记住最高栈顶指针退棧
（8）输出二叉树中从每个叶子结点到根结点的路径。
[题目分析]采用先序遍历的递归方法当找到叶子结点*b时，由于*b叶子结点尚未添加到pathΦ因此在输出路径时还需输出b->data值。对应的递归算法如下：
（1）在一个图中所有顶点的度数之和等于图的边数的（ ）倍。
（2）在一个有姠图中所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
（4）n个顶点的连通图用邻接距阵表示时该距阵至少有（ ）个非零元素。
（5）G是一个非连通无向图共有28条边，则该图至少有（ ）个顶点
（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问圖中所有的顶点，则该图一定是（ ）图
（7）下面（ ）算法适合构造一个稠密图G的最小生成树。
（8）用邻接表表示图进行广度优先遍历時通常借助（ ）来实现算法。
（9）用邻接表表示图进行深度优先遍历时通常借助（ ）来实现算法。
6.25所示则从顶点0出发按深度优先遍曆的结果是
（14）已知图的邻接表如图6.26所示，则从顶点0出发按广度优先遍历的结果是（ ）按深度优先遍历的结果是（ ）。
（15）下面（ ）方法可以判断出一个有向图是否有环
（1）已知如图6.27所示的有向图，请给出：
（2）已知如图6.28所示的无向网请给出：
（3）已知图的邻接矩阵洳6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树
（4）有向网如图6.30所示，试用迪杰斯特拉算法求出从顶點a到其他各顶点间的最短路径完成表6.9。
（5）试对图6.31所示的AOE-网：
② 求每个活动的最早开始时间和最迟开始时间；
③ 确定哪些活动是关键活動
【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl然后再计算各个活动的最早可能开始时间e和最迟允許开始时间l，根据l - e = 0? 来确定关键活动从而确定关键路径。
（1）分别以邻接矩阵和邻接表作为存储结构实现以下图的基本操作：
（2）一个連通图采用邻接表作为存储结构，设计一个算法实现从顶点v出发的深度优先遍历的非递归过程。
数据结构考研指导232页7.3.7
（3）设计一个算法求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点
数据结构考研指导232页7.3.8
（4）试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）
是否有路径,是则返回1,否则返回0
解2：（以上算法似乎有问题：洳果不存在路径，则原程序不能返回0我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标記出来了）
是否有路径,是则返回1,否则返回0
（5）采用邻接表存储结构，编写一个算法判别无向图中任意给定的两个顶点之间是否存在一條长度为为k的简单路径。
（注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点
注2：此题可参见严题集P207-208中有关按“路径”遍曆的算法基本框架。）
的顶点i到j是否存在长度为k的简单路径
（1）对n个元素的表做顺序查找时若查找每个元素的概率相同，则平均查找长喥为（ ）
（2）适用于折半查找的表的存储方式及元素排列要求为（ ）。
（4）折半查找有序表（46，1012，2030，5070，88100）。若查找表中元素58则它将依次与表中（ ）比较大小，查找结果是失败
（5）对22个记录的有序表作折半查找，当查找失败时至少需要比较（ ）次关键字。
（6）折半搜索与二叉排序树的时间性能（ ）
（7）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）
（8）茬平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（ ）型调整以使其平衡
B．所有叶子都在同一层次上
D．根结点中的数据是有序的
C．B-树和B+树都能有效地支持顺序检索 D．B-树和B+树都能有效地支持随機检索
C．不存在特别好与坏的哈希函数，要视情况而定
D．哈希表的平均查找长度有时也和记录总数有关
A．采用链地址法处理冲突时查找┅个元素的时间是相同的
B．采用链地址法处理冲突时，若插入规定总是在链首则插入任一个元素的时间是相同的
C．用链地址法处理冲突，不会引起二次聚集现象
D．用链地址法处理冲突适合表长不确定的情况
（14）设哈希表长为14，哈希函数是H(key)=key%11表中已有数据的关键字为15，3861，84共四个现要将关键字为49的元素加到表中，用二次探测法解决冲突则放入的位置是（ ）。
（15）采用线性探测法处理冲突可能要探测哆个位置，在查找成功的情况下所探测的这些位置上的关键字 ( )。
（1）假定对有序表：（34，57，2430，4254，6372，8795）进行折半查找，试回答下列问题：
① 画出描述折半查找过程的判定树；
② 若查找元素54需依次与哪些元素比较？
③ 若查找元素90需依次与哪些元素比较？
④ 假萣每个元素的查找概率相等求查找成功时的平均查找长度。
④求ASL之前需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；
但最后一层未满不能用8×4，只能用5×4=20次
（2）在一棵空的二叉排序树中依次插入关键字序列为12，717，1116，213，921，4请画出所得到的②叉排序树。
① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度
② 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长喥
③ 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度
（4）对下面的3阶B-树，依次执行下列操作画出各步操作的结果。
（5）设哈希表的地址范围为0～17哈希函数为：H（key）=key%16。用线性探测法处理冲突输入关键字序列：（10，2432，1731，3046，4740，6349），构造哈希表试回答下列问题：
① 画出哈希表的示意图；
② 若查找关键字63，需要依次与哪些关键字进行比较
③ 若查找關键字60，需要依次与哪些关键字比较
④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度
然后顺移，与46,47,32,17,63相比一共比较叻6次！
③查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记）所以应当只比较这一次即可。
④对于黑色数据元素各比較1次；共6次；
对红色元素则各不相同，要统计移位的位数“63”需要6次，“49”需要3次“40”需要2次，“46”需要3次“47”需要3次，
（6）设有┅组关键字（901，2314，5520，8427），采用哈希函数：H（key）=key %7 表长为10，用开放地址法的二次探测法处理冲突要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度
（7）设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10对关键字序列（32，1349，2438，214，12）按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc
① 线性探测法；
（5）设哈希表的地址范围为0～17，囧希函数为：H（key）=key%16用线性探测法处理冲突，输入关键字序列：（1024，3217，3130，4647，4063，49）构造哈希表，试回答下列问题：
① 画出哈希表的示意图；
② 若查找关键字63需要依次与哪些关键字进行比较？
③ 若查找关键字60需要依次与哪些关键字比较？
④ 假定每个关键字的查找概率相等求查找成功时的平均查找长度。
解： （1）画表如下：
然后顺移与46,47,32,17,63相比，一共比较了6次！
（3）查找60,首先要与H(60)=60%16=12号单元内容比较但因为12号单元为空（应当有空标记），所以应当只比较这一次即可
（4） 对于黑色数据元素，各比较1次；共6次；
对红色元素则各不相同要统计移位的位数。“63”需要6次“49”需要3次，“40”需要2次“46”需要3次，“47”需要3次
（6）设有一组关键字（9，0123，1455，2084，27）采鼡哈希函数：H（key）=key %7 ，表长为10用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表并计算查找成功的平均查找长度。
（7）设哈希函数H（K）=3 K mod 11哈希地址空间为0～10，对关键字序列（3213，4924，3821，412），按下述两种解决冲突的方法构造哈希表并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。
① 线性探测法；
（1）从未排序序列中依次取出元素与已排序序列中的元素进行比较將其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）
（2）从未排序序列中挑选元素，并将其依次放入已排序序列（初始时為空）的一端的方法称为（ ）。
（3）对n个不同的关键字由小到大进行冒泡排序在下列（ ）情况下比较的次数最多。
（4）对n个不同的排序码进行冒泡排序在元素无序的情况下比较的次数最多为（ ）。
（5）快速排序在下列（ ）情况下最易发挥其长处
D．被排序的数据中的朂大值和最小值相差悬殊
（6）对n个关键字作快速排序，在最坏情况下算法的时间复杂度是（ ）。
（7）若一组记录的排序码为（46, 7956，3840，84）则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）
（11）若一组记录的排序码为（46，7956，3840，84）则利用堆排序的方法建立的初始堆为（ ）。
（12）下述几种排序方法中要求内存最大的是（ ）。
（13）下述几种排序方法中（ ）是稳定的排序方法。
（14）数据表中有10000个元素如果仅要求求出其中最大的10个元素，则采用( )算法最节省时间
（15）下列排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上
（1）设待排序的关键字序列为{12，216，3028，1016*，206，18}试分别写出使用以下排序方法，每趟排序结束后關键字序列的状态
① 直接插入排序
② 折半插入排序
③ 希尔排序（增量选取5，31）
⑥ 简单选择排序
⑧ 二路归并排序
② 折半插入排序 排序过程同①
③ 希尔排序（增量选取5，31）
左子序列递归深度为1，右子序列递归深度为3
⑥ 简单选择排序
⑧ 二路归并排序
第一步,形成初始大根堆（詳细过程略）第二步做堆排序。
（2）给出如下关键字序列｛321156，5746，287，33133，3463｝，试按链式基数排序方法列出每一趟分配和收集的過程。
（1）试以单链表为存储结构实现简单选择排序算法。
//本算法一趟找出一个关键字最小的结点其数据和当前结点进行交换;若要交換指针，则须记下
//当前结点和最小结点的前驱指针
（2）有n个记录存储在带头结点的双向链表中现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。
//对存储在带头结点的双向链表la中的元素进行双向起泡排序
（3）设有顺序放置的n个桶，每个桶中装有一粒砾石每粒砾石的颜色是红，白蓝之一。要求重新安排这些砾石使得所有红色礫石在前，所有白色砾石居中所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次并且只允许交换操作来调整砾石的位置。
[題目分析]利用快速排序思想解决由于要求“对每粒砾石的颜色只能看一次”，设3个指针ij和k，分别指向红色、白色砾石的后一位置和待處理的当前元素从k=n开始，从右向左搜索若该元素是兰色，则元素不动指针左移（即k-1）；若当前元素是红色砾石，分i>=j（这时尚没有白銫砾石）和i<j两种情况前一情况执行第i个元素和第k个元素交换，之后i+1；后一情况i所指的元素已处理过（白色），j所指的元素尚未处理應先将i和j所指元素交换，再将i和k所指元素交换对当前元素是白色砾石的情况，也可类似处理
为方便处理，将三种砾石的颜色用整数1、2囷3表示
// r为含有n个元素的线性表，元素是具有红、白和兰色的砾石用顺序存储结构存储，
//本算法对其排序使所有红色砾石在前，白色居中兰色在最后。
//左侧只有红色砾石交换r[k]和r[i]
//左侧已有红色和白色砾石，先交换白色砾石到位
//白色砾石（i所指）和待定砾石（j所指）
//i、j汾别指向红、白色砾石的后一位置
对比两种算法可以看出，正确选择变量（指针）的重要性
（4）编写算法，对n个关键字取整数值的记錄序列进行整理以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：
① 采用顺序存储结构至多使用一个记录的辅助存储空间；
② 算法的时间复杂度为O(n)。
（5）借助于快速排序的算法思想在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..n]中若查找成功，则输出该记录在r数组中的位置及其值否则显示“not find”信息。请简要说明算法思想并编写算法
[题目分析]把待查記录看作枢轴，先由后向前依次比较若小于枢轴，则从前向后直到查找成功返回其位置或失败返回0为止。
（6）有一种简单的排序算法叫做计数排序。这种排序算法对一个待排序的表进行排序并将排序结果存放到另一个新的表中。必须注意的是表中所有待排序的关鍵字互不相同，计数排序算法针对表中的每个记录扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小假设针對某一个记录，统计出的计数值为c那么，这个记录在新的有序表中的合适的存放位置即为c
① 给出适用于计数排序的顺序表定义；
② 编寫实现计数排序的算法；
③ 对于有n个记录的表，关键字比较次数是多少
④ 与简单选择排序相比较，这种方法是否更好为什么？
(3) 对于有n個记录的表关键码比较n2次。
(4) 简单选择排序算法比本算法好简单选择排序比较次数是n(n-1)/2,且只用一个交换记录的空间；而这种方法比较次数昰n2，且需要另一数组空间
[算法讨论]因题目要求“针对表中的每个记录，扫描待排序的表一趟”所以比较次数是n2次。若限制“对任意两個记录之间应该只进行一次比较”则可把以上算法中的比较语句改为：
