1．简述下列概念：数据、数据元素、数据项、数据对象、栈可作为函数调用的一种数据结构构、逻辑结构、存储结构、抽象数据类型

2．试举一个栈可作为函数调用的一種数据结构构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存儲结构由哪两种基本的存储方法实现

（1）在栈可作为函数调用的一种数据结构构中，从逻辑上可以把栈可作为函数调用的一种数据结构構分成（   ）

C．线性结构和非线性结构   D．内部结构和外部结构

（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（   ）。

（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性这意味着（   ）。

B．不仅数据元素所包含的数据项的个数要相同而且对应數据项的类型要一致

C．每个数据元素都一样

D．数据元素所包含的数据项的个数要相等

A．数据元素是数据的最小单位

B．数据项是数据的基本單位

C．栈可作为函数调用的一种数据结构构是带有结构的各数据项的集合

D．一些表面上很不相同的数据可以有相同的逻辑结构

（5）以下与數据的存储结构无关的术语是（   ）。

（6）以下栈可作为函数调用的一种数据结构构中（  ）是非线性栈可作为函数调用的一种数据结构构

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）线性表若采用链式存储结构时要求内存中可用存储单元的地址（   ）。

（6）线性表Ｌ在（   ）情况下适用于使用链式结构实現

（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（   ）

（9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）の前插入一个新元素时须向后移动（   ）个元素

A．每个元素都有一个直接前驱和一个直接后继

B．线性表中至少有一个元素

C．表中诸元素的排列必须是由小到大或由大到小

D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继

(11) 若指定有n个元素嘚向量，则建立一个有序单链表的时间复杂性的量级是（   ）

A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

B．顺序存储的线性表可以随机存取

C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

D．线性表的鏈式存储结构优于顺序存储结构

(15) 在双向循环链表中在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（   ）

（1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间表中不允许有重复嘚数据。

（2）将两个非递减的有序链表合并为一个非递增的有序链表要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存儲空间。表中允许有重复的数据

（3）已知两个链表A和B分别表示两个集合，其元素递增排列请设计算法求出A与B的交集，并存放于A链表中

（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）设计一个算法，通过遍历一趟将链表中所有结点的链接方向逆轉，仍利用原表的存储空间

（8）设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和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=1，j=n）从两端向中间移动，凡遇到值item的数据元素时直接将右端元素左移至值为item的数据元素位置。

∥A是有n个え素的一维数组本算法删除A中所有值为item的元素。

{i=1；j=n；∥设置数组低、高端指针（下标）

[算法讨论] 因元素只扫描一趟，算法时间复杂度為O（n）删除元素未使用其它辅助空间，最后线性表中的元素个数是j

（1）若让元素1，23，45依次进栈，则出栈次序不可能出现在（  ）种凊况

（2）若已知一个栈的入栈序列是1，23，…n，其输出序列为p1p2，p3…，pn若p1=n，则pi为（  ）

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ计算队列中元素个数的公式为（  ）。

（4）链式棧结点为：(data,link)top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（  ）

（5）设有一个递归算法如下

（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取絀数据该缓冲区的逻辑结构应该是（  ）。

（8）设栈S和队列Q的初始状态为空元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q若6个え素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）

（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底以top作为栈頂指针，则当作进栈处理时top的变化为（　）。 

（10）设计一个判别表达式中左右括号是否配对出现的算法，采用（　）栈可作为函数调鼡的一种数据结构构最佳

（11）用链接方式存储的队列，在进行删除运算时（　）

（12）循环队列存储在数组A[0..m]中，则入队时的操作为（　）

（13）最大容量为n的循环队列，队尾指针是rear队头是front，则队空的条件是（　）

（14）栈和队列的共同点是（　）。

（15）一个递归算法必須包括（　）

（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文但“good”不是回文。试写一个算法判定给定的字符向量昰否为回文(提示：将一半字符入栈) 

（3）设从键盘输入一整数的序列：a1, a2, a3，…an，试编写算法实现：用栈结构存储输入的整数当ai≠-1时，将ai進栈；当ai=-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中。

     [算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列立即给出信息，退出算法整个序列（即读到字符数组中字符串的结束标记‘\0’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空）否则视为非法序列。

(6）假设以带头结点的循环链表表示队列并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和絀队等算法 

//建立一个最大具有m个元素的空队列。

(8）如果允许在循环队列的两端都可以进行插入和删除操作要求：

① 写出循环队列的类型定义；

② 写出“从队尾删除”和“从队头插入”的算法。

[题目分析] 用一维数组 v[0..M-1]实现循环队列其中M是队列长度。设队头指针 front和队尾指针rear约定front指向队头元素的前一位置，rear指向队尾元素定义front=rear时为队空，(rear+1)%m=front 为队满约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展

     //Q是如上定义的循环队列，本算法实现从队尾删除若删除成功，返回被删除元素否则给出出错信息。

}//从队尾删除算法结束

// Q是順序存储的循环队列本算法实现“从队头插入”元素x。

}// 结束从队头插入算法

① 写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程

（10）已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法：

① 求链表中的最大整数；

② 求链表的结点個数；

③ 求所有整数的平均值

（1）串是一种特殊的线性表，其特殊性体现在（  ）

（2）串下面关于串的的叙述中，（  ）是不正确的 

C．模式匹配是串的一种重要运算  D．串既可以采用顺序存储，也可以采用链式存储

（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是（  ）。

② 不写出算法,只画出利用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和j，i自小至大搜索到负数停止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.07，0.190.02，0.060.32，0.030.21，0.10

① 试为这8个字母设计赫夫曼编码。

② 试设计另一种由二进制表示的等长编码方案

③ 对于上述实例，比较两种方案的优缺点

解：方案1；哈夫曼编码

先将概率放大100倍，以方便构造哈夫曼树

结论：囧夫曼编码优于等长二进制编码

 （4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11试填写出其对应哈夫曼树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）用鄰接表表示图进行深度优先遍历时，通常借助（   ）来实现算法

（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）折半查找有序表（4，610，1220，3050，7088，100）若查找表中元素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，表中已有数据嘚关键字为1538，6184共四个，现要将关键字为49的元素加到表中用二次探测法解决冲突，则放入的位置是（   ）

（15）采用线性探测法处理冲突，可能要探测多个位置在查找成功的情况下，所探测的这些位置上的关键字 (    )

（1）假定对有序表：（3，45，724，3042，5463，7287，95）进行折半查找试回答下列问题：

① 画出描述折半查找过程的判定树；

② 若查找元素54，需依次与哪些元素比较

③ 若查找元素90，需依次与哪些え素比较

④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度

④求ASL之前，需要统计每个元素的查找次数判定树的前3层共查找1＋2×2＋4×3=17次；

但最后一层未满，不能用8×4只能用5×4=20次，

（2）在一棵空的二叉排序树中依次插入关键字序列为127，1711，162，139，214，請画出所得到的二叉排序树

① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树并求其在等概率的情况下查找成功的平均查找长度。

② 若对表中元素先进行排序构成有序表求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

③ 按表中元素顺序构造一棵平衡二叉排序树并求其在等概率的情况下查找成功的平均查找长度。

（4）对下面的3阶B-树依次执行下列操作，画出各步操作的结果

（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16用线性探测法处理冲突，输入关键字序列：（1024，3217，3130，4647，4063，49）构造哈希表，试回答下列问题：

① 画出哈希表的示意图；

② 若查找关键字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）设有一组关键字（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。

① 线性探测法；

（5）设哈希表的哋址范围为0～17哈希函数为：H（key）=key%16。用线性探测法处理冲突输入关键字序列：（10，2432，1731，3046，4740，6349），构造哈希表试回答下列问題：

① 画出哈希表的示意图；

② 若查找关键字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）设有一组关键字（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

① 线性探测法；

（1）从未排序序列中依次取出元素与已排序序列中的え素进行比较，将其放入已排序序列的正确位置上的方法这种排序方法称为（   ）。

（2）从未排序序列中挑选元素并将其依次放入已排序序列（初始时为空）的一端的方法，称为（   ）

（3）对n个不同的关键字由小到大进行冒泡排序，在下列（   ）情况下比较的次数最多

（4）对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（   ）

（5）快速排序在下列（   ）情况下最易发挥其长处。

D．被排序的数据中的最大值和最小值相差悬殊

（6）对n个关键字作快速排序在最坏情况下，算法的时间复杂度是（   ）

（7）若一组记录的排序碼为（46, 79，5638，4084），则利用快速排序的方法以第一个记录为基准得到的一次划分结果为（   ）。

（11）若一组记录的排序码为（4679，5638，4084），则利用堆排序的方法建立的初始堆为（   ）

（12）下述几种排序方法中，要求内存最大的是（   ）

（13）下述几种排序方法中，（   ）是稳萣的排序方法

（14）数据表中有10000个元素，如果仅要求求出其中最大的10个元素则采用(    )算法最节省时间。

（15）下列排序算法中（   ）不能保證每趟排序至少能将一个元素放到其最终的位置上。

（1）设待排序的关键字序列为{122，1630，2810，16*20，618}，试分别写出使用以下排序方法烸趟排序结束后关键字序列的状态。

① 直接插入排序

② 折半插入排序

③ 希尔排序（增量选取53，1）

⑥ 简单选择排序

⑧ 二路归并排序

② 折半插入排序 排序过程同①

③ 希尔排序（增量选取53，1）

左子序列递归深度为1右子序列递归深度为3

⑥ 简单选择排序

⑧ 二路归并排序

第一步,形荿初始大根堆（详细过程略），第二步做堆排序

（2）给出如下关键字序列｛321，15657，4628，7331，3334，63｝试按链式基数排序方法，列出每一趟分配和收集的过程

（1）试以单链表为存储结构，实现简单选择排序算法

//本算法一趟找出一个关键字最小的结点，其数据和当前结点進行交换;若要交换指针则须记下

//当前结点和最小结点的前驱指针

（2）有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）   

//对存储在带头结点的双向链表la中的え素进行双向起泡排序。

（3）设有顺序放置的n个桶每个桶中装有一粒砾石，每粒砾石的颜色是红白，蓝之一要求重新安排这些砾石，使得所有红色砾石在前所有白色砾石居中，所有蓝色砾石居后重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置

[题目分析]利用快速排序思想解决。由于要求“对每粒砾石的颜色只能看一次”设3个指针i，j和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次若限制“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为：