哈尔滨工业大学数据结构与算法历年考题汇总

一、名词解释：算法、数据结构*3、存储结构、栈*3、队列、散列表、最小生成树*4、完全二叉树*5、连通图*3、强连通图、强连通分量、关键字二、解答题3.简述（1）算法的设计要求（2）顺序栈和链栈的优缺比较5.（1）单向循环链表应该用头指针比较好还是尾指针比较好？（2）给了个程序要求分析程序功能时间复杂度6.简述.（1）单向循环链表应该用头指针比较好还是尾指针比较好？（2）是给出一个代码，要你说出该代码实现了什么操作。

4.写一个程序，在一个顺序表删除“负数”元素，假设每个元素为负的概率为1/(n+1)，分析该程序的时间复杂度2、利用栈解释表达式6 用栈算出后缀表达式（5-2）*（3+8）7 循环队列的数据结构及入队程序3.写个Inverse函数把一个队列里的元素反序利用队列和栈的几个基本操作2、可变长顺序栈的数据结构和入栈操作1、设计循环队列的数据结构并实现入队操作4 二叉树写出二叉树的数据结构构造方法及把题中二叉树输入的程序4、树变二叉树4、将给出的树转换为对应的二叉树，并写出他的后根周游序列7.编程题给了二叉树的数据结构要求写出判断一棵二叉树是否是二叉排序树的6.二叉树的周游给了先序中序后序周游的部分结点顺序（就是完整的结点顺序上挖掉了几个空）要求画出这棵二叉树1.后根次序周游二叉树的时间和空间复杂度分析3、哈夫曼树和赫夫曼编码3 构造哈夫曼树写出赫夫曼编码给出8个代码及其出现概率1. 给出八个代码及他们出现的概率，按哈夫曼算法构造哈夫曼树，并进行赫夫曼编码。

5.哈夫曼树给了八个代码的权值，要求画出生成的哈夫曼树，写出哈弗曼代码4.哈夫曼树给了一堆代码的权值，要求画出生成的哈夫曼树，计算路径长度5、chemistry math Chinese English art geography geology geophysics physics 设计一个散列函数（c程序实现），对上述八个词进行处理，并用拉链法处理碰撞问题，画出存储结构的示意图。

数据结构与算法分析考试试题一、选择题（共 20 小题，每小题 3 分，共 60 分）1、在一个具有 n 个元素的顺序表中，查找一个元素的平均时间复杂度为（）A O(n)B O(logn)C O(nlogn)D O(n²)2、以下数据结构中，哪一个不是线性结构（）A 栈B 队列C 二叉树D 线性表3、一个栈的入栈序列是 1，2，3，4，5，则栈的不可能的出栈序列是（）A 5，4，3，2，1B 4，5，3，2，1C 4，3，5，1，2D 1，2，3，4，54、若一棵二叉树的先序遍历序列为 ABCDEFG，中序遍历序列为CBDAEGF，则其后序遍历序列为（）A CDBGFEAB CDBFGEAC CDBAGFED BCDAGFE5、具有 n 个顶点的无向完全图的边数为（）A n(n 1)B n(n 1) ／ 2C n(n ＋ 1) ／ 2D n²6、以下排序算法中，在最坏情况下时间复杂度不是O(n²)的是（）A 冒泡排序B 选择排序C 插入排序D 快速排序7、在一个长度为 n 的顺序表中，删除第 i 个元素（1≤i≤n）时，需要向前移动（）个元素。

A n iB iC n i ＋ 1D n i 18、对于一个具有 n 个顶点和 e 条边的有向图，其邻接表表示中，所有顶点的边表中边的总数为（）A eB 2eC e/2D n(e 1)9、以下关于哈夫曼树的描述，错误的是（）A 哈夫曼树是带权路径长度最短的二叉树B 哈夫曼树中没有度为 1 的节点C 哈夫曼树中两个权值最小的节点一定是兄弟节点D 哈夫曼树中每个节点的权值等于其左右子树权值之和10、用邻接矩阵存储一个具有 n 个顶点的无向图时，矩阵的大小为（）A nB n²C （n 1)²D （n ＋ 1)²11、下列关于堆的描述，正确的是（）A 大根堆中，每个节点的值都大于其左右子节点的值B 小根堆中，每个节点的值都小于其左右子节点的值C 堆一定是完全二叉树D 以上都对12、在一个具有 n 个单元的顺序存储的循环队列中，假定 front 和rear 分别为队头指针和队尾指针，则判断队满的条件是（）A （rear ＋ 1) ％ n ＝＝ frontB （front ＋ 1) ％ n ＝＝ rearC rear ＝＝ frontD rear ＝＝ 013、已知一个图的邻接表如下所示，从顶点 1 出发，按深度优先搜索法进行遍历，则得到的一种可能的顶点序列为（）｜顶点|邻接顶点|｜｜｜｜1|2, 3|｜2|4, 5|｜3|5|｜4|6|｜5|6|｜6| ｜A 1, 2, 4, 6, 5, 3B 1, 2, 5, 3, 4, 6C 1, 2, 3, 5, 4, 6D 1, 3, 2, 4, 5, 614、对线性表进行二分查找时，要求线性表必须（）A 以顺序方式存储，且元素按值有序排列B 以顺序方式存储，且元素按值无序排列C 以链式方式存储，且元素按值有序排列D 以链式方式存储，且元素按值无序排列15、以下算法的时间复杂度为 O(nlogn)的是（）A 顺序查找B 折半查找C 冒泡排序D 归并排序16、若某链表最常用的操作是在最后一个节点之后插入一个节点和删除最后一个节点，则采用（）存储方式最节省时间。

1. 判断题(共20分)------------------------------------------------------------------------------------------------------------ (1). 顺序存储的线性表可以随机存取。

()答案：是(2). 对于n个记录的集合进行归并排序，所需要的附加空间数是0(n)。

()答案：是(3). 矩阵压缩存储的方法是用三元组表存储矩阵元素。

()答案：否(4). 进栈操作push(x，s)作用于链接栈时，无须判满。

()答案：是(5). 在堆中执行insert与deletemin运算都只需o(log2n)时间。

( )答案：是(6). 在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使用二分查找方法。

()答案：是(7). 因为算法和程序没有区别，所以在数据结构中二者是通用的。

( )答案：否(8). 按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。

( )答案：是(9). 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

()答案：否(10). 对于n个记录的集合进行冒泡排序，所需要的平均时间是O(n)。

()答案：否2. 选择题(共20分)------------------------------------------------------------------------------------------------------------ (1). 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为＿＿个。

A:4 B:5 C:6 D:7答案： C(2). 设关键字序列为：3，7，6，9，8，1，4，5，2。

进行排序的最小交换次数是＿＿。

A:6 B:7 C:8 D:20答案：A(3). 在一个单链表中，若删除p所指结点的后继结点，则执行( )。

1、在二叉搜索树（BST）中，以下哪个遍历顺序会按从小到大的顺序访问所有节点？A. 前序遍历B. 中序遍历C. 后序遍历D. 层次遍历（答案：B）2、对于一个给定的无向图，以下哪种算法最适合找到从起点到终点的最短路径（假设所有边的权重都相等）？A. Dijkstra算法B. Bellman-Ford算法C. Floyd-Warshall算法D. 广度优先搜索（BFS）（答案：D）3、在哈希表中处理冲突的一种方法是链地址法（也称为拉链法），以下关于链地址法的说法错误的是：A. 每个哈希表槽位连接一个链表B. 当发生冲突时，新元素添加到对应槽位的链表末尾C. 链地址法不需要处理哈希函数的设计，因为冲突总是通过链表解决D. 查找、插入和删除操作的时间复杂度与链表的长度有关（答案：C）4、以下哪种数据结构最适合实现优先队列，且支持高效的插入和删除最小（或最大）元素操作？A. 数组B. 链表C. 二叉堆D. 平衡二叉搜索树（如AVL树）（答案：C）5、在快速排序算法中，选择哪个元素作为基准（pivot）对算法的效率有重要影响，以下哪种策略通常不是一个好的选择？A. 数组的第一个元素B. 数组的最后一个元素C. 数组中间的元素D. 随机选择一个元素（答案：视具体情况而定，但通常A、B在特定情况下可能不是最佳，如当数组已近排序时；然而，此题要求选一个“通常不是好选择”的，若必须选一个，可以认为A或B在未知数据分布时风险较高，答案可倾向A或B，这里选A作为示例）6、以下哪个不是图的遍历算法？A. 深度优先搜索（DFS）B. 广度优先搜索（BFS）C. A*搜索算法D. 拓扑排序（答案：D）7、在平衡二叉搜索树（如红黑树）中，以下哪个操作的时间复杂度不是O(log n)？A. 查找B. 插入C. 删除D. 计算树中所有节点的和（答案：D，因为计算所有节点和需要遍历整个树，时间复杂度为O(n)）8、以下哪种情况最适合使用动态规划算法来解决？A. 查找无序数组中的最大值B. 对一组数进行排序C. 计算斐波那契数列的第n项D. 在已排序的数组中查找特定元素（答案：C）。

2022年哈尔滨工程大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（）。

A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.333、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

数据结构与算法测试题+参考答案一、单选题（共80题，每题1分，共80分）1、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？A、仅有头指针的单循环链表B、双链表C、仅有尾指针的单循环链表D、单链表正确答案：C2、数据结构研究的内容是（）。

A、数据的逻辑结构B、数据的存储结构C、建立在相应逻辑结构和存储结构上的算法D、包括以上三个方面正确答案：D3、下列关于无向连通图特征的叙述中，正确的是：所有顶点的度之和为偶数边数大于顶点个数减1至少有一个顶点的度为1A、只有1B、1和2C、1和3D、只有2正确答案：A4、下面的程序段违反了算法的（）原则。

void sam(){ int n=2;while (n%2==0) n+=2;printf(“%d”,n);}A、确定性B、可行性C、有穷性D、健壮性正确答案：C5、对任意给定的含 n (n>2) 个字符的有限集 S，用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树 T1 和 T2。

下列叙述中，正确的是：A、出现频次不同的字符在 T2 中处于相同的层B、出现频次不同的字符在 T1 中处于不同的层C、T1 的高度大于 T2 的高度D、T1 与 T2 的结点数相同正确答案：A6、数据序列{ 3，2，4，9，8，11，6，20 }只能是下列哪种排序算法的两趟排序结果？A、快速排序B、选择排序C、插入排序D、冒泡排序正确答案：A7、设散列表的地址区间为[0,16]，散列函数为H(Key)=Key%17。

采用线性探测法处理冲突，并将关键字序列{ 26，25，72，38，8，18，59 }依次存储到散列表中。

元素59存放在散列表中的地址是：A、11B、9C、10D、8正确答案：A8、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：A、每次划分后，先处理较短的分区可以减少递归次数B、递归次数与每次划分后得到的分区处理顺序无关C、递归次数与初始数据的排列次序无关D、每次划分后，先处理较长的分区可以减少递归次数正确答案：B9、以下数据结构中，（）是非线性数据结构。

2022年哈尔滨工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。

A.5B.6C.8D.92、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定8、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。

A.二叉排序树B.哈夫曼树C.AVL树D.堆9、设X是树T中的一个非根结点，B是T所对应的二叉树。

在B中，X是其双亲的右孩子，下列结论正确的是（）。

A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟10、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）。

数据结构与算法题库（含参考答案）一、单选题（共100题，每题1分，共100分）1、在一次校园活动中拍摄了很多数码照片，现需将这些照片整理到一个PowerPoint 演示文稿中，快速制作的最优操作方法是：A、创建一个 PowerPoint 相册文件。

B、创建一个 PowerPoint 演示文稿，然后批量插入图片。

C、创建一个 PowerPoint 演示文稿，然后在每页幻灯片中插入图片。

D、在文件夹中选中所有照片，然后单击鼠标右键直接发送到PowerPoint 演示文稿中。

正确答案：A2、下面对“对象”概念描述错误的是A、对象不具有封装性B、对象是属性和方法的封装体C、对象间的通信是靠消息传递D、一个对象是其对应类的实例正确答案：A3、设栈与队列初始状态为空。

首先A,B,C,D,E依次入栈，再F,G,H,I,J 依次入队；然后依次出队至队空，再依次出栈至栈空。

则输出序列为A、F,G,H,I,J,E,D,C,B,AB、E,D,C,B,A,J,I,H,G,FC、F,G,H,I,J,A,B,C,D,E,D、E,D,C,B,A,F,G,H,I,J正确答案：A4、设表的长度为 20。

则在最坏情况下，冒泡排序的比较次数为A、20B、19C、90D、190正确答案：D5、设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。

则后序序列为A、DGHEBIJFCAB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ正确答案：A6、Excel工作表B列保存了11位手机号码信息，为了保护个人隐私，需将手机号码的后 4 位均用“*”表示，以 B2 单元格为例，最优的操作方法是：A、=REPLACE(B2,7,4,"****")B、=REPLACE(B2,8,4,"****")C、=MID(B2,7,4,"****")D、=MID(B2,8,4,"****")第 10 组正确答案：B7、小金从网站上查到了最近一次全国人口普查的数据表格，他准备将这份表格中的数据引用到 Excel 中以便进一步分析，最优的操作方法是：A、通过 Excel 中的“自网站获取外部数据”功能，直接将网页上的表格导入到 Excel 工作表中。

哈尔滨工业大学2008年考研试题Ⅰ数据结构部分一填空题1.已知一个线性表有n个元素，其中每个元素的数据占8个字节，假设一个指针的大小为4个字节，如果采用有30个元素的数组存储，那么当数组中有效元素个数满足⑴条件时，数组的存储效率比不带头结点的单链表更高。

2. 给定14个字母，假设它们的权值都相等．采用huffman编码，则每个字母的平均代码长度是⑵。

3. 按C语言的运算符优先级，中缀表达式“A&&B||!(E>F)”的等价后缀形式为⑶。

4. 设按顺时针方向移动的循环队列Q[N]的头尾指针分别为F、R，头指针F总是指在队列中的第一个元素的前一位置，尾指针R在最后一个元素的位置，则队列中的元素个数为⑷。

5. 从空二叉树开始,严格按照BST（二又查找树）的插入算法，逐个插入关键字{18,73,10，5，68，99，27，41,32，25）构造出一颗BST ，对该BST按照先根遍历得到的序列为⑸。

6. 将两个长度为m的有序序列归并为一个有序序列，最少需要做⑹次关键字比较，最多需要做⑺次关键字比较。

7. 散列查找中，⑻现象称为冲突，⑼现象称为聚集。

8. 设可用的内存单元可处理4个记录，采用4 路归并的选择树法生成由小到大的初始归并段，对有12个记录在案的文件，产生的第一个初的归并段长度为⑽个。

9. 在两种求图的最小生成树的算法中，⑾算法适合于边稀疏的图的最小生成树。

10. 已知一个序列为{21，39，35，12，17，43}，则利用堆排序方法建立的初始堆为：⑿。

二、判断（每题1分．共9分）1. 倒排文件只能按关键字的顺序存储。

（①）2. 堆的存储表示可能是链接式的，也可以是顺序的。

（②）3. 在AOE网中，任何一个关键活动的延迟，都会使整个工程延迟。

（③）4. 有环路的有向图不能进行拓扑排序。

（④）5. 对无向图进行一次深度优先搜索可以访问到图中的所有顶点。

（⑤）6. 大根堆的最大元素应该在堆顶，即根结点。

13哈尔滨工业大学数据结构试题及答案数据结构试卷（一）；一、单选题（每题2分，共20分）；1.栈和队列的共同特点是()；A.只允许在端点处插入和删除元素；B.都是先进后出；C.都是先进先出；D.没有共同点；2.用链接方式存储的队列，在进行插入运算时().；A.仅修改头指针B.头、尾指针都要修改；C.仅修改尾指针D.头、尾指针可能都要修改；3.以下数据结构中哪一个是非线性结构？()；A.队列B.数据结构试卷（一）一、单选题（每题 2 分，共20分）1. 栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2. 用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3. 以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965. 树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6. 二叉树的第k层的结点数最多为( ).kk-1 A．2-1 B.2K+1 C.2K-1 D. 27. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

哈工大数据结构作业14./*升序创建两个含有整形数据的链表，其中Create函数中调用Insert函数实现升序排列。

再通过Combine函数将两个链表合并，用Print函数输出。

代码如下。

*/#include "stdafx.h"#include <iostream>struct node {int data ;struct node *next ;} ;using namespace std;node* Insert(node *head,node *n)/*数据插入,升序排列*/{node *p1,*p2;p1=p2=head;if(head==NULL){head=n;n->next=NULL;return head;}if(head->data>=n->data) //新结点插入首结点之前{n->next=head;head=n;return head;}//在首结点之后寻找位置插入新结点while(p2->next&&p2->data<n->data){p1=p2;p2=p2->next;}if(p2->data<n->data){p2->next=n;n->next=NULL;}else{n->next=p2;p1->next=n;}return head;}/*创建有序链表*/node * Create(void){node *head,*n;int a ;head=NULL;cout<<"升序插入法产生链表，请输入数据（-1结束）：\n";for(cin>>a;a!=-1;cin>>a){n=new node;n->data=a;head=Insert(head,n);}return head;}void Print( node *head){cout<<"链表的结点数据（升序）为：\n";while(head){cout<<head->data<<'\t';head=head->next;}}node * Combine(node *p,node *q){ node *hc,*pc;node *pa,*pb;pa=p->next;pb=q->next;hc=pc=p;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pa=pa->next;pc=pc->next;}else {pc->next=pb;pb=pb->next;pc=pc->next;}}pc->next=pa?pa:pb;return hc;}int main(){node *ha,*hb,*hc;cout<<"链表a添加数据\n";ha=Create();cout<<"链表b添加数据\n";hb=Create();Print(ha);Print(hb);hc=Combine(ha,hb);Print(hc);return 0;}8.XSXXXSSSXXSXXSXXSSSS15.//设置链表结点：struct celltype{Elementtype element;celltype *next;int a; //在结点中设置一个int型a来表示链表元素总数};/*顺时针方向查找：即为普通单向链表的查找。

哈工大2004年硕士研究生入学考试试题《数据结构》答案及解析一、 填空题解答：1、()1%m n + 或 ()1mod m n +【备注】本题主要考查考生对循环队列的数组实现过程中 关于空对与满队的区分 ，同时还考查，如何利用数组来实现循环队列，即依赖于数学意义上的求模运算来实现。

2、 第一【备注】本题主要考查考生对二叉树中 关于前序、中序、后序遍历定义的理解，由教材中的理论可知，无论在上述三种遍历中的哪种方式中，在某子树中，同一层级上的左孩子一定在右孩子的前面首先被遍历。

因此，可以将该题抽象为或者简化为如下形式（这也是 二叉树的一般形式）：由题意，显然答案如上。

3、 9、4、6、7、8【备注】本题主要考查考生对二分查找（即折半查找）算法的理解。

在二分算法中，需要注意的是，每次对low 、mid 、up 的选取（通过关键字进行比较即可得到）。

由教材中关于对二分查找算法的描述可知：()/2mid low up = + （注意这是两个整型数相加后与整数2作除法，其结果仍为整数，即对数学意义上的结果进行取整。

），下一次可能需要继续查找的区间为两种情况：[],1low mid − 或者 []1,mid up + 。

因此，可以得到本题的查找区间分别为：()117/29mid =+=、()18/24mid =+=、()58/26mid =+=、()78/27mid =+=、()88/28mid =+=4、N 和 2log N⎡⎤⎢⎥【备注】本题主要考查考生对快速排序算法的理解，同时还考察了考生对二分查找、二元查找树、二叉树、算法的最坏情况、算法的最好情况等知识点的理解。

该题有一定的难度。

由所学知识可知：快速排序算法的关键还是类似于二分的思想，那就是每次都将区间分割为三个集合（其中基准元本身单独构成了一个集合），然后依次递归下去。

显然，我们可以将这种剖分方式与二分查找对应起来，由二分查找可知，整个二分查找过程其实就是对应于一个二元查找树，其查找效率与相应的二元查找树的深度相关。

[期末] 2005数据结构与算法试卷试卷类型: 期末试卷年份: 05授课教师: 廖明宏有无答案: 无答案哈工大2005年春季学期数据结构与算法试卷)一．填空题（每空1分，共10分）1．假定对线性表(38,25,74,52,48)进行散列存储，采用H(K)=K %7作为散列函数，若分别采用线性探查法和链接法处理冲突，则对各自散列表进行查找的平均查找长度分别为_______和________。

2．假定一组记录的排序码为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为________________。

3．在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。

4．有向图的邻接矩阵表示法中某一行非0元素的个数代表该顶点的，某一列非0元素的个数是该顶点的。

]5．对于下面的带权图G3，若从顶点v0出发，则按照普里姆（Prim）算法生成的最小生成树中，依次得到的各条边为______________。

6．由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为7．由三个结点构成的二叉树，共有种不同结构。

二．选择题（每题1分，共10分）1．快速分类在的情况下不利于发挥其长处.`A. 待分类的数据量太大B. 待分类的数据相同值过多C. 待分类的数据已基本有序D. 待分类的数据值差过大.2．两路归并排序中，归并的趟数是。

A. O(n)B. O(log2n)C. O(nlog2n)D. O(n2)注意行为规范(遵守考场纪律第1页，共6页3．对外部分类的K路平衡归并，采用败者树时，归并的效率与K 。

A. 有关B.无关C.不能确定D. 都不对4．对于一个索引顺序文件，索引表中的每个索引项对应主文件中的。

}A. 一条记录B.多条记录C. 所有记录D.三条以上记录5．.若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址时。

硕士研究生入学考试初试专业课资料
计算机专业基础
计算机考研历年真题(1991年-2008年) 友情分享！余人玫瑰手留余香！
第 3 页共 3 页
第共
第 3 页共 3 页
七、依次读入数据元素序列{a，b，c，d，e，f，g}j进栈每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行则栈空时弹出的元素构成的序列是以下那些序列？（
{d ，e，c，f，b，g，a}， {f，e，g，d，a，c，b}
（低电平有效）作访作读
作读写命令信号（高电平为读，低电平为写）。

有一系统程序编译后为
根数据线，允许输出，允许写，片选
允许写，
允许输出，片选
允许输出，片选，允许写。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性4．一个算法应该是（）。

【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表13．以下哪个数据结构不是多型数据类型（）【中山大学 1999 一、3（1分）】A．栈 B．广义表 C．有向图 D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学 1999 一、4】A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构。

1. 判断题判断题 (共20分) ------------------------------------------------------------------------------------------------------------ (1). 哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。

哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。

() 答案：是答案：是(2). 线性表的链式存储结构优于顺序行储结构。

线性表的链式存储结构优于顺序行储结构。

() 答案： 否答案：(3). 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

() 答案： 否答案：(4). 对于n个记录的集合进行归并排序，存最坏的情况下所需要的时间是0(n^2)。

() 答案： 否答案：(5). 由于磁带的价格比磁盘便宜，用磁带实现直接访问文件较为合理。

() 答案： 否答案：(6). 表中的每一个元素都有一个前驱和后继元素。

() 答案： 否答案：(7). 只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。

只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。

() 答案： 否答案：(8). 在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使用二分查找方法。

() 查找方法。

答案：是答案：是(9). 数据元素是数据的最小单位。

数据元素是数据的最小单位。

( ) 答案： 否答案：(10). 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

() 答案： 否答案：2. 选择题选择题 (共20分) ------------------------------------------------------------------------------------------------------------ (1). 设一个数列的顺序为1，2，3，4，5，6，通过栈结构可以排成的顺序数列为＿＿。