折半查找法的查找速度一定比顺序查找法快。

哈尔滨工业大学二〇〇八年硕士研究生考试模拟试题（一）考试科目：计算机专业基础适用专业：计算机科学与技术I 数据结构（含高级语言）部分（共75分）一、填空题（每空1分，共9分）+−++的后缀表达式1.表达式23((12*32)/434*5/7)108/9是。

2.设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85的地址为。

3.设有广义表A=（（（a，b），x），（（a），（b）），（c，（d，（y）））），得到y的对广义表A的操作序列为。

4.如果二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总节点数为。

5.G是一个非连通无向图，共有28条边，则该图至少有个顶点。

6.构造n个结点的强联通图，至少有条弧。

7.设表长为1023的有序线性表，查找每个元素的概率相等，采用折半查找方法，查找成功的ASL是。

8.分别采用堆排序、快速排序、冒泡排序和归并排序，对初太为有序的表，则最省时间的是算法，最费时间的是算法。

二、单项选择题（每题1分，共11分）1.静态链表中指针表示的是（）A 下一元素的地址B 内存储器的地址C 下一元素在数组中的位置D 左链或右链指向的元素的地址2.计算算法的时间复杂度是属于一种（）A 事前统计的方法B 事前分析估算的方法C 事后统计的方法D 时候分析估算的方法3.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）A 1和5B 2和4C 4和2D 5和14.若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是（）A 1040B 1042C 1026D 都不正确5.一棵124个叶节点的完全二叉树，最多有（）个节点。

A 247B 248C 249D 250E 251 6.有n （n>0）个分支结点的满二叉树的深度为（ ） A n 2-1 B log 2(n+1)+1 C log 2(n+1) D log 2(n-1) 7.某二叉树结点的中序序列为BDAECF ，后续序列为DBEFCA ，则该二叉树对应的森林包括（ ）棵树。

一、单选题1. 从物理上可以把数据结构分为（B）两大类。

A. 动态结构、静态结构B. 顺序结构、链式结构C. 线性结构、非线性结构D. 初等结构、构造型结构2. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C ）(1≤i≤n+1)。

A. O(0)B. O(1)C. O(n)D. O(n2)3. 链表不具有的特点是（B）。

A. 插入、删除不需要移动元素B. 可随机访问任一元素C. 不必事先估计存储空间D. 所需空间与线性长度成正比4. 下列排序算法中(C)排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择B. 起泡C. 归并D. 堆5. 在下列排序算法中，哪一个算法的时间复杂度与初始排序无关（D ）。

A. 插入排序B. 起泡排序C. 快速排序D. 选择排序6. 一个栈的输入序列为1,2,3,…,n，若输出序列的第一个元素是i，则第j个输出元素是（D）。

A. i-j-1B. i-jC. j-i+1D. 不确定7. 输入序列为ABC，可以变为BCA时，经过的栈操作为（D ）。

A. push,pop,push,pop,push,popB. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,push,pop,push,pop,pop8. 有六个元素6 5 4 3 2 1 的顺序进栈，下列（C ）不是合法的出栈序列。

A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 69. 串的长度是指（B ）。

A. 串中所含不同字母的个数B. 串中所含字符的个数C. 串中所含不同字符的个数D. 串中所含非空格字符的个数10. 设二维数组A[1.. m,1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为( A)。

一判断题1．顺序查找法适用于存储结构为顺序或链接存储的线行表。

2．一个广义表可以为其他广义表所共享。

3．快速排序是选择排序的算法。

4．完全二叉树的某结点若无左子树，则它必是叶子结点。

5．最小代价生成树是唯一的。

6．哈希表的结点中只包含数据元素自身的信息，不包含任何指针。

7．存放在磁盘，磁带上的文件，即可意识顺序文件，也可以是索引文件。

8．折半查找法的查找速度一定比顺序查找法快。

二选择题1．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A. nB. 2n-1C. 2nD. n-12.在文件"局部有序"或文件长度较小的情况下，最佳内部排序的方法是（）。

A. 直接插入排序B.气泡排序C. 简单选择排序D. 快速排序3.高度为K的二叉树最的结点数为（）。

A. 24.一个栈的输入序列是12345，则占的不可能的输出序列是（）A.54321B. 45321C.43512D.123455.ISAM文件和V ASM文件属于（）A索引非顺序文件 B. 索引顺序文件 C. 顺序文件 D. 散列文件6. 任何一棵二叉树的叶子结点在先序，中序和后序遍历序列中的相对次序（）A. 不发生变化B. 发生变化C. 不能确定D. 以上都不对7.已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（）。

A. acbedB. decabC. deabcD.cedba三．填空题1．将下图二叉树按中序线索化，结点的右指针指向（），Y的左指针指向（）E2．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四各度为4的结点和若干叶子结点，则T的叶结点数为（）3．抽象数据类型的定义仅取决与它的一组（），而与（）无关，即不论其内部结构如何变化，只要它的（）不变，都不影响其外部使用。

4.VSAM(虚拟存储存取方法)文件的优点是：动态地（），不需要文件进行（），并能较快的（）进行查找。

3. 简答题（1）简述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求。

对长度为n 的表来说，三种查找法在查找成功时的平均查找长度各是多少？答：三种方法对查找的要求分别如下。

① 顺序查找法：表中元素可以任意次序存放。

② 折半查找法：表中元素必须按关键字递增或递减排列，且最好采用顺序存储结构。

③ 分块查找法：表中元素每块内的元素可以任意次序存放，但块与块之间必须以关键字的大小递增（或递减）排列，即前一块内所有元素的关键字都不能大（或小）于后一块内任何元素的关键字。

三种方法的平均查找长度分别如下。

① 顺序查找法：查找成功的平均查找长度为(n +1)/2。

② 折半查找法：查找成功的平均查找长度为log 2(n +1)-1。

③ 分块查找法：若用顺序查找确定所在的块，平均查找长度为：21(sn+s )+1；若用二分查找确定所在块，平均查找长度为log 2(s n +1)+2s。

其中，s 为每块含有的元素个数。

（2）折半查找适不适合链表结构的序列，为什么？用折半查找的查找速度必然比线性查找的速度快，这种说法对吗？答：不适合。

虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。

折半查找的速度在一般情况下是快些，但在特殊情况下未必快。

例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。

（3）给定关键字序列为{3,5,7,9,11,13,15,17}，回答以下问题：① 按表中元素的顺序依次插入一棵初始值为空的二叉排序树。

画出插入完成后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度。

答：① 按输入顺序构造的二叉排序树如图8.1所示。

在等概率情况下查找成功的平均查找长度为：ASL succ =887654321+++++++=4.5由此可见在同样序列的查找中，平衡二叉树比二叉排序树的平均查找长度要小，查找效率要高。

顺序查找直接查找折半查找算法一、顺序查找算法顺序查找也被称为线性查找，是一种简单直观的算法。

其基本原理是逐个遍历数据集中的元素，直到找到目标值为止。

算法步骤如下：1.从数据集的第一个元素开始顺序遍历。

2.如果当前元素与目标值相同，返回元素的索引。

3.如果遍历到数据集的最后一个元素仍未找到目标值，返回失败。

顺序查找算法的时间复杂度为O(n)，其中n为数据集的大小。

由于需要遍历整个数据集，这种算法适用于小型数据集。

二、直接查找算法直接查找算法也被称为线性查找优化算法，其思想是在遍历数据集时，通过跳跃一定步长快速确定目标值所在的范围，然后在该范围内进行顺序查找。

算法步骤如下：1.设定步长为k。

2.从数据集的第一个元素开始，每次跳跃k个元素。

3.如果当前元素大于目标值，将步长减半并继续跳跃，直到找到目标值或步长变为1为止。

4.在跳跃范围内进行顺序查找，找到目标值则返回索引，否则返回失败。

直接查找算法的时间复杂度为O(n/k)，其中n为数据集的大小，k为步长。

通过调整步长，可以在时间和空间之间取得平衡。

折半查找算法是一种效率较高的算法，也被称为二分查找。

其基本原理是将数据集分为两半，通过比较目标值与中间元素的大小关系来确定目标值所在的范围，然后在该范围内进行递归查找。

算法步骤如下：1.将数据集按升序或降序排列。

2.初始化左右指针，分别指向数据集的第一个和最后一个元素。

3.计算中间元素的索引。

4.如果中间元素等于目标值，则返回索引。

5.如果中间元素大于目标值，则更新右指针为中间元素的前一个元素，重复步骤36.如果中间元素小于目标值，则更新左指针为中间元素的后一个元素，重复步骤37.当左指针大于右指针时，返回失败。

折半查找算法的时间复杂度为O(logn)，其中n为数据集的大小。

由于每次都将数据集分为两半，因此效率较高。

但是该算法要求数据集必须有序。

综上所述，顺序查找、直接查找和折半查找算法都是常用的算法，适用于不同规模和有序性的数据集。

福师《数据结构概论》在线作业二-0002试卷总分：100得分：100一、单选题（共25道试题,共50分）1.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为 n,森林F中第一棵树的结点个数是（）A.m-nB.m-n-1C.n+1D.条件不足，无法确定答案:A2.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。

A.前序B.中序C.后序D.按层次答案:C3.一个算法应该是（）。

A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A 和 C.答案:B4.栈和队列的共同点是（）。

A.都是先进先出8.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点E.限制存取点的线性结构F.限制存取点的非线性结构答案:C5.下面的程序段中，对x的赋值语句的频度为（）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1;A.O（2n）B.O（n）C.O（n"2）D.O（log2n）答案:C6.算法的计算量的大小称为计算的（）A.效率B.复杂性C.现实性D.难度答案:B7.对于栈操作数据的原则是（）A.先进先出8.后进先出C.后进后出D.不分顺序答案:B8.下列表达式中结果不是日期型的是？A.CT0D（"2000/10/01"）B.「99/10/01}+365C.VAL（"2000/10/01"）D.DATE（）答案:C9.关键路径是事件结点网络中（）A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长回路D.最短回路答案:A10.就平均性能而言，目前最好的内排序方法是（）排序法。

A.冒泡B.希尔插入C.交换D.快速答案:D11.栈和队都是（）A.顺序存储的B.线性结构C.链式存储的D.非线性结构答案:B12.关系数据库中，实现实体之间的联系是通过表与表之间的?A.公共索引B.公共存储C.公共元组D.公共属性答案:D13.下列关于候选键的说法中错误的是？A.键是惟一标识实体的属性集B.候选键能惟一决定一个元组C.能惟一决定一个元组的属性集是候选键D.候选键中的属性均为主属性答案:C14.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）A.808B.818C.1010D.1020答案:B15.链表不具有的特点是（）儿插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比答案:B16.若要求尽可能快地对序列进行稳定的排序，则应选（A.快速排序B.归并排序C.冒泡排序D.堆答案:B17.下面关于关系数据模型的说法，正确的是哪一项？A.只能表示实体间的1：1联系B.只能表示实体间的l：n联系C.只能表示实体间的m：n联系D.可以表示实体间的上述三种联系答案:D18.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）（1<=i<=n+1）。

20 06—20 07学年第2 学期《数据结构与算法》考试试卷（A卷）（时间120分钟）院/系专业姓名学号一、选择题（每小题2分，共20分）1、数据结构中，与所使用的计算机无关的是数据的结构。

A. 存储结构B. 物理结构C. 逻辑结构D. 物理和存储结构2、循环链表的主要优点是。

A. 不再需要头指针了B. 已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D. 从表中任一结点出发都能遍历整个链表3、栈和队列都是。

A. 顺序存储的线性结构B.链式存储的非线性结构C. 限制存取点的线性结构D.限制存取点的非线性结构4、串的长度是指。

A. 串中所含不同字母的个数B. 串中所含不同字符的个数C. 串中所含字符的个数D. 串中所含非空格字符的个数5、若某二叉树的先序和中序遍历序列分别为ABCD、ACDB，则该二叉树的后序遍历序列为。

A. DBCAB. ADCBC. DCBAD. CDBA6、有n个叶子结点的哈夫曼树，其结点总数为。

A．2n-1 B．2n C．2n+1 D．不确定。

7、无向图的邻接矩阵一定是。

A. 对角矩阵B. 稀疏矩阵C. 三角矩阵D. 对称矩阵8、以下序列中符合堆的定义。

A. (2,40,20,25,30)B. (2,20,40,25,30)C. (40,25,2,30,20)D. (40,25,2,20,30)9、下列排序方法中属于不稳定排序方法的是。

A.直接插入排序B.冒泡排序C.快速排序D.归并排序10、设有一个用线性探测法解决冲突得到的散列表(或哈希表)如下图所示，散列函数为H(k)=k % 11，若要查找元素14，探查的次数为。

(第一题，第10小题图)A.5B.9C.3D.6二、填空题（每小题2分，共20分）1、一个“好”的算法要考虑以下标准：正确性 、可读性 、 和高效率与低存储量需求。

2、对于二维数组a[0..4,0..5]，设每个元素占1个存储单元，且以行为主序存储，则元素a[2,3]相对于数组空间起始地址的偏移量是 。

大工18春《数据结构》在线作业3
试卷总分:100 得分:100
一、判断题 (共 10 道试题,共 50 分)
1.散列文件中存放一组记录的存储单位称为桶。

A.对
B.错
正确答案:A
2.散列方法的查找性能用平均查找长度ASL来衡量。

A.对
B.错
正确答案:A
3.二分查找对线性表的存储结构无任何要求。

A.对
B.错
正确答案:B
4.折半查找只能在有序的顺序表上进行而不能在有序链表上进行。

A.对
B.错
正确答案:A
5.快速排序算法是一种不稳定的算法。

A.对
B.错
正确答案:A
6.直接选择排序属于选择类排序,是一种稳定的排序方法。

A.对
B.错
正确答案:B
7.对于一个堆,按二叉树层次进行遍历可以得到一个有序序列。

A.对
B.错
正确答案:B。