哈工大2009年春季试卷-数据结构与算法-带答案

西华大学课程考试参考答案（A卷）课程代码： 8401801 试卷总分： 100 分一、单项选择题参考答案及评分标准：（本大题共20个小题，每小题2分，共40分）评分标准：选对一题得2分，不选或选错得0分。

1-5：CBACC 6-10：CCBDB 11-15：ABCCD 16-20：CADDC二、算法理解题参考答案及评分标准：（本大题共3个小题，第1、2小题各7分，第3小题6分，共20分）评分标准：请根据各解答步骤酌情给分。

1. 解：构造过程各图（略），最后结果为：2. 解：设权w=(5,29,7,8,14,23,3,11)，可构造一棵赫夫曼树如下图所示。

所得赫夫曼编码为：A: 0110B: 10C: 1110D: 1111E: 110F: 00G: 0111H: 0103. 解：（1）希尔排序第一趟（增量d=5）排序后 7、12、36、23、12、51、60、55、72、49第二趟（增量d=3）排序后 7、12、36、23、12、51、49、55、72、60第三趟（增量d=1）排序后 7、12、12、23、36、49、51、55、60、72（2）归并排序第一趟排序后 12、51、23、55、7、49、36、60、12、72第一趟排序后 12、23、51、55、7、36、49、60、12、72第三趟排序后 7、12、23、36、49、51、55、60、12、72第四趟排序后 7、12、12、23、36、49、51、55、60、72三、算法设计题参考答案及评分标准：（本大题共4个小题，每小题10分，共40分）评分标准：请根据编程情况酌情给分。

1. 参考答案示例：void DelInsert(LinkList &L）{∥本算法将带头结点的非空单链表L中数据域值最小的那个结点移到链表的最前面。

p=L->next；∥p是链表的工作指针pre=L；∥pre指向链表中数据域最小值结点的前驱。

q=p；∥q指向数据域最小值结点，初始假定是首元结点while （p->next!=NULL）{ if（p->next->data<q->data）{ pre=p；q=p->next；} ∥找到新的最小值结点 p=p->next；}if (q!=L->next){ pre->next=q->next；∥将最小值结点从链表上摘下q->next= L->next；∥将q结点插到链表最前面L->next=q；}}//DelInsert2. 参考答案示例：void Count(BiTree T,int &n0,int &n){//统计二叉树T上叶结点数n0和非叶结点数n。

数据结构与算法复习题库含答案1. 问题描述：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

答案：可以使用哈希表来解决此问题。

首先初始化一个空的哈希表，然后遍历数组中的每个元素。

对于每个元素，首先计算目标值与当前元素的差值，然后在哈希表中查找该差值。

如果找到了该差值，则说明存在两个数的和等于目标值，返回这两个数的下标；否则，将当前元素插入到哈希表中。

时间复杂度为O(n)，其中n为数组的长度。

2. 问题描述：给定一个字符串，找出其中不含重复字符的最长子串的长度。

答案：可以使用滑动窗口来解决此问题。

维护一个窗口，其中包含没有重复字符的子串。

遍历字符串中的每个字符，如果该字符不在窗口中，将其加入窗口；如果该字符在窗口中，移动窗口的左边界直到窗口中不包含重复字符。

记录窗口的最大长度。

时间复杂度为O(n)，其中n为字符串的长度。

3. 问题描述：给定一个字符串和一个单词列表，找出字符串中可以由单词列表中的单词组成的所有子串的起始位置。

答案：可以使用滑动窗口和哈希表来解决此问题。

首先统计单词列表中每个单词的出现次数。

然后遍历字符串中的每个位置作为子串的起始位置，维护一个滑动窗口。

在窗口中依次取出长度和单词列表中单词总长度相等的子串，在哈希表中统计子串中每个单词出现的次数。

如果窗口中的子串与单词列表中的单词出现次数一致，则记录该子串的起始位置。

时间复杂度为O(n*m)，其中n为字符串的长度，m为单词列表中的单词个数。

4. 问题描述：给定一个无序的整数数组，找出其中缺失的第一个正整数。

答案：可以使用原地哈希表来解决此问题。

遍历数组中的每个元素，将每个正整数放到数组中对应的位置上。

遍历数组中的每个元素，如果该位置上的数不等于数组索引加一，则该索引加一即为缺失的第一个正整数。

时间复杂度为O(n)，其中n为数组的长度。

5. 问题描述：给定一个字符串s，找到s中最长的回文子串。

答案：可以使用动态规划来解决此问题。

一、单项选择题（每空1分，共15分）1、B2、C3、A4、B5、D6、C7、D8、B9、A10、B11、C12、B13、B14、C15、B二、判断题（每空1分，共10分）1、×2、×3、√4、√5、×6、√7、×8、×9、×10、×三、填空题（每空1分，共10分）1、数据项2、稳定3、环4、递增5、双亲的右子树中最左下的叶子结点6、后进先出7、树内各结点度的最大值8、三元组9、广义表10、n+1四、应用题（每题7分，共35分）1、答：依题意，采用快速排序法排序的各趟的结果如下：初始：503,87,512,61,908,170,897,275,653,4621趟：[462,87,275,61,170] 503 [897,908,653,512]2趟：[170,87,275,61] 462,503 [897,908,653,512]3趟：[61,87] 170 [275] 462,503 [897,908,653,512]4趟：61 [87] 170 [275] 462,503 [897,908,653,512]5趟：61,87,170 [275] 462,503 [897,908,653,512]6趟：61,87,170,275,462,503 [897,908,653,512]7趟：61,87,170,275,462,503 [512,653] 897 [908]8趟：61,87,170,275,462,503,512 [653] 897 [908]9趟：61,87,170,275,462,503,512,653,897 [908]10趟：61,87,170,275,462,503,512,653,897,9082、答：该二叉树后序遍历的结果是：GDBLHKMIEJFCA。

3、答：带权路径长度WPL值为280。

4、答：用Kruskal算法构造的最小生成树为选边次序为(2,3)，(3,4)，(1,6)，(1,5)，(2,6)。

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

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

4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．部结构和外部结构（2）与数据元素本身的形式、容、相对位置、个数无关的是数据的（）。

A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说确的是（）。

A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）。

A．顺序队列 B. 链表 C.有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

《数据结构与算法》习题与答案（解答仅供参考）一、名词解释：1. 数据结构：数据结构是计算机存储、组织数据的方式，它不仅包括数据的逻辑结构（如线性结构、树形结构、图状结构等），还包括物理结构（如顺序存储、链式存储等）。

它是算法设计与分析的基础，对程序的效率和功能实现有直接影响。

2. 栈：栈是一种特殊的线性表，其操作遵循“后进先出”（Last In First Out, LIFO）原则。

在栈中，允许进行的操作主要有两种：压栈（Push），将元素添加到栈顶；弹栈（Pop），将栈顶元素移除。

3. 队列：队列是一种先进先出（First In First Out, FIFO）的数据结构，允许在其一端插入元素（称为入队），而在另一端删除元素（称为出队）。

常见的实现方式有顺序队列和循环队列。

4. 二叉排序树（又称二叉查找树）：二叉排序树是一种二叉树，其每个节点的左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。

这种特性使得能在O(log n)的时间复杂度内完成搜索、插入和删除操作。

5. 图：图是一种非线性数据结构，由顶点（Vertex）和边（Edge）组成，用于表示对象之间的多种关系。

根据边是否有方向，可分为有向图和无向图；根据是否存在环路，又可分为有环图和无环图。

二、填空题：1. 在一个长度为n的顺序表中，插入一个新元素平均需要移动______个元素。

答案：(n/2)2. 哈希表利用______函数来确定元素的存储位置，通过解决哈希冲突以达到快速查找的目的。

答案：哈希（Hash）3. ______是最小生成树的一种算法，采用贪心策略，每次都选择当前未加入生成树且连接两个未连通集合的最小权重边。

答案：Prim算法4. 在深度优先搜索（DFS）过程中，使用______数据结构来记录已经被访问过的顶点，防止重复访问。

答案：栈或标记数组5. 快速排序算法在最坏情况下的时间复杂度为______。

2009春季数字通信试题及答案Question One: Determine a set of orthonormal functions for the four signals shown below: (20%)1(s t2(t (t t 22-Here give the details of the derivation1.Answer:2-22-2Question Two: (20%)Determine the probability error for the signals shown below, then give the bit error probability and symbol error probability of QPSK.122. Answer:Let us assume that the two signals are equally likely and that signal 1()s t wastransmitted.Then, the received signal from the (matched filter or correlation) demodulator is1r s nn =+=where n represents the additive Gaussian noise component, which has zero mean and variance 2012n N σ=. If 0r >, the decision is made in favor of 1()s t , and if 0r <, the decision is made that 2()s t was transmitted. Clearly, the two conditional PDFs of r are20(/1(/2(|)(|)r N r N p r s p r s --==2211/2/2(|)(|)exp[xxP e s p r s drdrdxdxQ-∞-∞--∞∞-=====⎰22/221/2(x NxP n n dxdxQ∞-∞-->===Question Three: (15%)Considering 4M=biorthogonal signals shown in below for transmitting information over anAWGN channel. The noise is assumed to have zero-mean and power spectral density12N. Determine the basis functions for this signal set, the impulse responses of the matched-filter demodulators, and the output waveforms of the matched-filter demodulators when the transmittedsignal is4()s t.AA-3. Answer:The impulse responses of the two matched filters are11221()()()20 ()1)()()20 ()T t Th t f T totherwiset Th t f T totherwise≤≤=-=⎪⎩≤≤=-=⎪⎩()()(),1,2Tkn ky T n t f t dt k==⎰2200002000[()][()()]()()1()()()211()22TTn kn k k T T k k T k E y T E n t n f t f dtd N t f t f dtd N f t dt N στττδτττ===-==⎰⎰⎰⎰⎰Observe that the 0SNRfor the first matched filter is0002SNR 2N N ε==12121212(,),),(),(,)r r n n n n n n =and 12(,)n n .Question Four: (15%)Complex-valued cross-correlation coefficient of any pair of signal waveforms ()m s t and()k s t is defined as()()km lm lk s t s t dt ρ+∞*-∞=Where ε is the energy of ()s t , and ()l s t is the bandpass representation of the ()s t (1) Do you know where the coefficient 1/2 in km ρcome from? (2) （2）Can it be defined as ()()km lm lk s t s t dt ρ+∞*-∞=?4. Answer:(1)22Re()Re()c c j f t j f t m k lm lk S S dt S e S e dt ππ∞∞-∞-∞=⋅⋅⎰⎰441()4c c j f t j f t lm lk lm lk lm lk lm lk S S e S S S S S S e dt ππ∞-****-∞=+++⎰ 1Re()2lm lk S S dt ∞*-∞=⎰ (3) YesQuestion Five: (20%)Let X be Gaussian distributed with zero mean and variance σ2, consider the random variable Y defined as2Y X =Determine (the details of the derivation are needed): (1) PDF of Y (2) CDF of Y(3) The characteristic function of Y5. Answer:2=Y Xso the probability distribution function of Y is2()()()(||)()()Y X X F y P Y y P X y P X y F y F y =≤=≤=≤=--and the probability density function of Y is[][]()22X X Y p y p y p y a ya y-=+Question Six: (20%)Your own explanation for the figure below, which is the comparison of several modulation methods at 10-5 symbol error probability6. Answer:There are no standard answers. Students should give answers according to their knowledge and experience.。

1045: 百鸡问题时间限制: 1 Sec 内存限制: 32 MB提交: 362 解决: 139题目描述用小于等于n元去买100只鸡，大鸡5元/只，小鸡3元/只,还有1/3元每只的一种小鸡，分别记为x只,y只,z只。

编程求解x,y,z所有可能解。

输入测试数据有多组，输入n。

输出对于每组输入,请输出x,y,z所有可行解，按照x，y，z依次增大的顺序输出。

样例输入40样例输出x=0,y=0,z=100x=0,y=1,z=99x=0,y=2,z=98x=1,y=0,z=992009年哈尔滨工业大学计算机研究生机试真题1046: 求最大值时间限制: 1 Sec 内存限制: 32 MB提交: 400 解决: 168题目描述输入10个数，要求输出其中的最大值。

输入测试数据有多组，每组10个数。

输出对于每组输入,请输出其最大值（有回车）。

样例输入10 22 23 152 65 79 85 96 32 1样例输出max=1522009年哈尔滨工业大学计算机研究生机试真题1047: 素数判定时间限制: 1 Sec 内存限制: 32 MB提交: 301 解决: 154题目描述给定一个数n，要求判断其是否为素数（0,1，负数都是非素数）。

输入测试数据有多组，每组输入一个数n。

输出对于每组输入,若是素数则输出yes，否则输入no。

样例输入13样例输出1048: 判断三角形类型时间限制: 1 Sec 内存限制: 32 MB提交: 248 解决: 130题目描述给定三角形的三条边，a,b,c。

判断该三角形类型。

输入测试数据有多组，每组输入三角形的三条边。

输出对于每组输入,输出直角三角形、锐角三角形、或是钝角三角形。

样例输入3 4 5样例输出直角三角形2009年哈尔滨工业大学计算机研究生机试真题1049: 字符串去特定字符时间限制: 1 Sec 内存限制: 32 MB提交: 250 解决: 121题目描述输入字符串s和字符c，要求去掉s中所有的c字符，并输出结果。

第2页 共 2页8、一棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有( )个结点。

A ．2hB ．2h-1C ．2h+1D ．h+19、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。

A ．先序B ．中序C ．后序D ．按层次遍历10、一棵二叉树的先序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ ）。

A ．CABDEFGB ．ABCDEFGC ．DACEFBGD ．ADBCFEG11、一棵有n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i 个结点（i 从1开始用上述方法编号）的右孩子在数组A 中的位置是（ ）A ．A[2i](2i<=n)B ．A[2i+1](2i+1<=n)C ．A[i-2]D ．条件不充分，无法确定12、一个n 个顶点的连通无向图，其边的个数至少为（ ）。

A ．n-1B ．nC ．n+1D ．nlogn13、下列关于AOE 网的叙述中，不正确的是（ ）。

A ．关键活动不按期完成就会影响整个工程的完成时间B ．任何一个关键活动提前完成，那么整个工程将会提前完成C ．所有的关键活动提前完成，那么整个工程将会提前完成D ．某些关键活动提前完成，那么整个工程将会提前完成 14、下面关于折半查找的叙述正确的是( )。

A ．表必须有序，表可以顺序方式存储，也可以链表方式存储C ．表必须有序，而且只能从小到大排列B ．表必须有序且表中数据必须是整型，实型或字符型D ．表必须有序，且表只能以顺序方式存储A．直接插入排序B．起泡排序C．快速排序D．直接选择排序二、判断题（每空1分，共10分）1、数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的储存结构。

( )2、对任何数据结构，链式存储结构一定优于顺序存储结构。

2009级《数据结构》课程试题（A卷）参考答案一、单选题：（每题 2 分，共30 分）DCDCC CABDB CCAAD二、按要求解答下列问题：（每空 5 分，共30 分）1. 算法效率和算法使用的策略、问题规模、书写语言、算法运行的软硬件环境等有关系，简要说明使用算法时间复杂度度量算法效率的思想。

不考虑计算机硬件、软件有关的因素，认为一个特定算法运行工作量的大小只依赖于问题的规模，即从算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复的次数作为算法的时间度量。

2. 证明：对任何一棵二叉树T，如果终端结点数为n0，度为2的结点数为n2，则n0=n2+1设二叉树中度为1的结点数为n1，度为2的结点数为n2，二叉树中总结点数为n，因二叉树中所有结点的度均小于或等于2，有n＝n0＋n1＋n2由于这些分支都是由度为1和2的结点射出的，所以有：B＝n1+2n2n＝n1＋2n2＋1n0+n1+n2=n1+2n2+1n0＝n2＋13. 假设有5项活动，每项活动要求的前驱活动如下：C1：无；C2：C1，C3；C3：C1；C4：C3，C5 C5：C2，C3；试根据上述关系，（1）画出相应的有向图：（2）写出拓扑排序序列；C1 ,C3, C2, C5, C44. 含12个结点的平衡二叉树的最大深度是多少（设根结点的深度为1）？画出一颗这样的树。

最大深度是55. 判别下面的每个结点序列是否表示一个堆，如果不是，请把它调整为一个堆。

（1）100 ， 90， 80，60，85，75，20，25 （2）100 ， 70， 50，20，90，75，60，25 (1) 是（2）不是 100，90，75，25，70，50，60，206. 关键字序列：22、41、53、46、30、13、01、67，h (key) = key mod 11,表长为11，用线性探测再散列处理冲突，试填写下表并计算每个关键字的冲突次数、比较次数和平均查找长度。

一、选择题（每空1分，共15分）1.D2.D3.C4.D5.B6.A7.B8.B9.C 10.B11.D 12.A 13.B 14.D 15.D二、判断题（每空1分，共10分）1.×2.×3.√4.×5.×6.√7.×8.×9.×10.×三、填空题（每空1分，共10分）1.q=p->next; p->next=q->next; free(q);2.（rear-front+m）% m3.两串的长度相等且两串中对应位置的字符也相等。

4.22685.186.2K+1-17.98.6、3、4、59.6310.初始有序四、应用题（每题7分，共35分）1.字符A，B，C，D出现的次数为9,1,5,3。

其哈夫曼编码如下A:1，B:000，C:01，D:0012.先序：A B C D E F G H I J K L中序：C B E D F G A J I H K L后序：C E G FD B J I L K H A3.构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）4.ASL =（1+1+1+2+1+2+1+2）/8=11/85.不变调整40之后：调整85之后：调整22五、算法设计题（每题15分，共30分）1.LinkedList Union(LinkedList la,lb)∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次序排列的单链表。

{ pa=la->next; pb=lb->next;∥pa，pb分别是链表la和lb的工作指针la->next=null; ∥la作结果链表的头指针，先将结果链表初始化为空。

while(pa!=null && pb!=null) ∥当两链表均不为空时作if(pa->data<=pb->data){ r=pa->next; ∥将pa 的后继结点暂存于r。

《数据结构与算法》试卷A适用专业： 考试日期： 闭卷 所需时间：120分钟 总分：100分一、 选择题(每题1分, 共20题，总共20分)。

1.算法分析的目的是（ ） A ．辨别数据结构的合理性 B ．评价算法的效率C ．研究算法中输入与输出的关系D ．鉴别算法的可读性2.在一个单链表HL 中，若要在当前由指针p 指向的结点后面插入一个由q 指向的结点，则执行如下( )语句序列。

A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（ ）A. 在队列第i 个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D.读取队头元素的值4.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。

A ． 11 B.35 C. 19 D. 535.如下图所示的4棵二叉树中，（ ）不是完全二叉树。

6．下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。

B ．线性表采用顺序存储，便于进行插入和删除操作。

C ．线性表采用链接存储，不必占用一片连续的存储单元。

D ．线性表采用链接存储，便于插入和删除操作。

7．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A ．单链表B ．仅有头指针的单循环链表C ．双链表D ．仅有尾指针的单循环链表8. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。

A. O(0)B. O(1)C. O(n)D. O(n 2)9. 若已知一个栈的入栈序列是1,2,3,…,n ，其输出序列为p 1,p 2,p 3，…，p N ,若p N 是n ，则p i 是( )。

[期末] 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个元素的存储地址时。

哈工大2009年春季学期数据结构与算法 试卷一、填空题（每空2分，共20分）1. 在 情况下，等长编码是最优前缀码。

2．设有两个算法在同一机器上运行，其执行时间分别为100n 2和2n ，要使前者快于后者，n 至少为 。

3．采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的是_ 。

4． 设二叉树结点的先根序列为ABDECFGH ，中根序列为DEBAFCHG,则二叉树中叶结点是_________.5. 用下标从0开始的N 个元素的数组实现循环队列时,为实现下标变量m 加1后在数组有效下标范围内循环,可采用的表达式是m= 。

6. 由带权为3，9，4，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为 。

7. 对n 个记录的表进行选择排序，在最坏情况下所需要进行的关键字的比较次数为 。

8. 任意一个有n 个结点的二叉树，已知它有m 个叶结点，则度数为2的结点有 。

9. n 个顶点的连通图用邻接矩阵表示时，该矩阵至少有 个非零元素10. 举出两种磁带文件的分类方法： 。

二、选择题（每题1分，共10分）注意行为规范遵守考场纪律1．设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（ ）。

(A) 40，42，45，55，80，83(B) 42，40，45，80，85，88(C) 42，40，55，80，45，85(D) 42，40，45，85，55，802．数据的最小单位是（ ）。

(A) 数据项(B) 数据类型(C) 数据元素 (D) 数据变量3．关键路径是AOE网中( ) 。

A.从始点到终点的最短路径B.从始点到终点的最长路径C.从始点到终点的边数最多的路径D.从始点到终点的边数最少的路径4．下列说法正确的是（）。

A．最小生成树也是哈夫曼树B．最小生成树是唯一的Ｃ．对于n 个顶点的连通无向图，Prim算法的时间复杂性为O(n2)D．Kruskal 算法比Prim算法更适合边稠密的图5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。

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个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

2009年计算机统考数据结构部分真题解析一、单项选择题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是______。

A.栈B.队列C.树D.图【解析】B。

考察栈和队列的特点。

C和D直接排除，缓冲区的特点需要先进先出，若用栈，则先进入缓冲区的数据则要排队到最后才能打印，不符题意，所以只有队列符合题意。

2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。

若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是______。

A.1B.2C.3D.4【解析】C。

考察栈的最大深度。

时刻注意栈的特点是先进后出。

下面是出入栈的详细栈内的最大深度为3，故栈S的容量至少是3。

3.给定二叉树图所示。

设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列是3, 1, 7, 5, 6, 2, 4，则其遍历方式是______。

1234567A.LRNB.NRLC.RLND.RNL【解析】D。

考察二叉树的遍历。

L表示左分支，R表示右分支，N表示根。

分析遍历后的结点序列，可以看出根结点是在中间被访问的，而且右子树结点在左子树之前，则遍历的方法是RNL。

本题考查的遍历方法并不是二叉树遍历的三种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。

4.下列二叉排序树中，满足平衡二叉树定义的是______。

A. B. C. D.【解析】B。

考察平衡二叉树的定义。

根据平衡二叉树的定义有，任意结点的左右子树高度差的绝对值不超过1。

而其余三个答案均可以找到不符合的结点。

5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是_____。

A.39B.52C.111D.119【解析】C。

考察完全二叉树的特点。

完全二叉树比起满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层上有叶结点。