哈尔滨工业大学数据结构与算法历年考题汇总.docx
- 文档编号:17072549
- 上传时间:2023-07-21
- 格式:DOCX
- 页数:25
- 大小:106KB
哈尔滨工业大学数据结构与算法历年考题汇总.docx
《哈尔滨工业大学数据结构与算法历年考题汇总.docx》由会员分享,可在线阅读,更多相关《哈尔滨工业大学数据结构与算法历年考题汇总.docx(25页珍藏版)》请在冰点文库上搜索。
哈尔滨工业大学数据结构与算法历年考题汇总
[期末]2005数据结构与算法试卷
试卷类型:
期末
试卷年份:
03
授课教师:
廖明宏
有无答案:
无答案
哈工大2005年春季学期
数据结构与算法试卷
一・填空题(每空1分,共10分)
1.假定对线性表(3&25,74,52,48)进行散列存储,采用H(K)二K%7作为散列函
数,若分别采用线性探查法和链接法处理冲突,则对各自散列表进行查找的平均
查找长度分别为和O
2.假定一组记录的排序码为(46,79,56,38,40,80),对其进行归并排序的过程中,第二趟归并后的结果为,
3.在堆排序的过程中,对任一分支结点进行调整运算的时间复杂度为
整个堆排序过程的时间复杂度为.
4.有向图的邻接矩阵表示法中某一行非0元素的个数代表该顶点的,某一列非0元素的个数是该顶点的。
5.对于下面的带权图G3,若从顶点vO出发,则按照普里姆(Prim)算法生成
的最小生成树中,依次得到的各条边为=
6.由带权为3,9,6,2,5的5个叶子结点构成一棵哈夫曼树,则带权路径长度为
7.由三个结点构成的二义树,共有种不同结构。
2.选择题(每题1分,共10分)
1.快速分类在的情况下不利于发挥其长处.
A.待分类的数据量太大B.待分类的数据相同值过多
C.待分类的数据已基本有序D.待分类的数据值差过大.
2.两路归并排序中,归并的趟数是。
A.0(n)B.0(log2n)C.0(nlog2n)D.0(n2)
注意行为规范
遵守考场纪律
第1页,共6页
3.对外部分类的K路平衡归并,采用败者树时,归并的效率与K。
A.有关B.无关C.不能确定D.都不对
4.对于一个索引顺序文件,索引表中的每个索引项对应主文件中的。
)
A.一条记录B.多条记录
C.所有记录D.三条以上记录
5..若线性表采用顺序存储结构,每个元素占用4个存储单元,笫一个元素的存储地址为100,则第12个元素的存储地址时。
6.若频繁地对线性表进行插入和删除操作,该线性表应该采用存储结构。
A.散列B.顺序C.链式D.索引
7.若长度为n的非空线性表釆用顺序储存结构,删除表中第i个数据元素,需要移动表中个数据元素。
+i+1
8.栈和队列的相同之处是。
(
A.元素的进出满足先进后出B.元素的进出满足后进先出
C.只允许在端点进行插入和删除操作D.无共同点
9.在一棵高度为k的二义树中,最多含有()个结点。
A.2k-1B.2k-lC.2k-1D.k
10.任何一棵二义树的叶结点在先序、中序和后序遍历序列中的相对次序()。
A.发生改变B.不发生改变C.不能确定D.以上都不对
3.判断题,正确的在括号内画V,错误的在括号内画X。
(每小题1分,共10分)
1.树的父链表示就是用数组表示树的存储结构。
()・
2.任何二元树都唯一对应一个森林,反之亦然。
.()
3.有向图的邻接矩阵一定不是对称的。
()
4.A0E网中,只有一个入度为0的顶点(起始点),只有一个出度为0的顶点(结束点)。
()
5.关键路径可能不只一条,但缩短某一关键路径一定能够缩短工期。
()
6.顺序存储方式只能用于存储线性结构。
()
7.用循环链表作为存储结构的队列就是循环队列。
()
8.倒排文件的主要优点为便于节省空间()。
9.一组记录的关键字为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准元素得到的一次划分结果为40,38,46,56,79,84()。
10.算法分析的口的是分析算法的易读性()。
4.简答题
1.简述如何用两个栈模拟一个队列的入队和出队操作.(6分)
<
2.对于图G5所示的树:
(7分)
(1)写出先根遍历得到的结点序列;
(2)写岀按层遍历得到的结点序列;
(3)画出转换后得到的二元树
1
图G5
5.算法设计
1.设二元树采用左右链存储,写出后序遍历该二元树的非递归算法。
(12分)
2.设图中各边上的权值均相等,试以邻接表为存储结构,写出求源点Vi到Vj的最短路径算法。
(15分)..
注意行为规范
遵守考场纪律
管导核字
主领审签
—-
二
Its
八
1
八
儿
1
0'刀・
分数
1.填牢题(每题2分,共28分)
1.假设•个15阶的上二角矩阵A按行优先顺用压缩存储在维数组B中,则非零元
素A[9][9]在B中的心储位毀K=,(注,矩阵元素下标从1开始)
2.设有广义衣/=(((M),.r),@),(力)),(c,仏(P)))),则得到y的对广义农A的
操作序列为.
3.对于•个只有n个结点的单向链2乙在已如P所指结点后插入•个新结点的吋的毀
杂度为;在值域为给定值的结点后插入个新结点的时间复杂度
为O
4.表达式2屯{(1*2)-32+”43的后缀表达式
是a
5.设栈S和队列Q的初始状态均为空,元素。
,b.c.d,c,F依次通过栈S,•个
元索出栈后即进入队列Q,若这6个元索出队列的顺序是b,ctc,f,e.a,则栈的容杲至少应该是o
6.在完全二叉树中,编号为i和j的两个结亢处于同•层的条件是-
7・设F足rhTl,T2,T3二棵树组成的森林,与F对应的二叉树为B,己如Tl,T2,
T3的结点数分别为nl,n2,n3,则•.叉树B的左/*・树屮有个结点,
右了树中冇个结点。
8・有数据WG=(7.19,2,6,32,3,21,10),则所建Huffman树的树高为,
帶权路径长度WPL为。
9.在有n个定点的有向图中,若任意两点间对以h相到达,則至少需要条弧.
10.已知有序记录(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47),
用折半査找算法査找关键字为7.41的记录时,比较次数分别为—次和次。
设有100个结点,用折半含找算法时,绘大比较次数为次。
11.对俎记录(50,40,95,20,15,70,60,45,80)进行直接插入揩序吋,当把
第7个记录60插入到有序表中时.为寻找插入位岂需比较次.
12.若图足可拓扑排序的,则该图中处存任入读和L11皮分别为的不同顶点。
若
某图不能•次完成拓扑排序,则该何向图必定或•
13.假定K个斤健字互为同义词,若用线性探测再散列法把这K个关谍字“入散列农
中,至少婆进行次探测.
14•在棵树中,度为1的结点的个数为度为2的结点的个数为乞,……,度为
m的结点的个数为心,则该树冇个叶子結点。
二、简答题(共30分)
I.请分别御述在I)彷线索二叉树中求菜结点P在曲序遍丿万顺序下的戌接前驱($尸)和氏接后继(PS)的幕本世想°(5分)
试题:
2008年春数据结构・A卷班号:
姓名:
2.诸简述利H]Kruskal算注、Prim聲法和破圈法求图的最小土成树的基本思担。
(5为
试题:
2008年祚数据结构・A卷班小
].R泡排仔过程中,冇的关傩7在某醞阳Y:
中可能朝带与掖终排庁相反的方向務动,试举例悦
明Z。
亦尔辦湘快速博序过程中分别有这种现像吗?
如有,谗举例说明。
(8分)
4.•棵一叉树的前序、中丿沢后序序列如下,Jt中有部分未标出,试填充完虧(6分)【精析
P103】
前序序列为:
・
CDE_
G_
_H_I_K
中序序列为:
C
7RFA_
_J
¥LJG
后序序列为:
■
_EFDB_J
ill
_A
第4页(共7页)
试题:
200R年春数据结构・A卷班号:
姓名:
5H知•纽关铢字狛(26,36,41,38,44,15,
68,12,06,51,25),用饼地址法解决冲
试题:
2008年春数据结构・A卷班号:
姓名:
~已知组关键字为(26,36,41,38,44,15,68,12,06,51,25),用链地址法解决冲
突,假设装填因了为a=0.75,Hash函数的形式为H(K)=KMODF,试回答下列问题:
(6分)
【订构造Hash函数;
【ii]计算等概率情况下查找成功的平均査找长度;
[iii]计算等概率借况下住找失敢的平均杳找长度。
五、算法设计(共20分)
1.(10分)请设计•种队列,要求*
[i]队列的大小不受限制,可根据实际需要进行分配;
队列的入队操作的时何效率足0
(1),出队操作的吋间救率足0
(1);
[iii]无需额外的辅助空间来完成队列的入队和出队操作:
咸于上述要求,根拯你设计的队列,实现下列操作:
Ca]队列的初始化操作:
lb]队列的队空和队满判启操作;
rd队列的入队和出队操作:
试题:
2008年春数拥结构・A卷班号:
姓名:
2.~(10分)请写出在中序线索一叉树里找指总结点在后序下的前驱結点的算法,苴中要求:
【订二叉树采用左右孩了表示法,线索二叉树是对基本结构的相应扩展:
【门给出存储结构描述,并以伪代码或CI代码方式给出算法的棊本描述;
哈工大数据结构与算法2009年试题
题号
—
二
三
四
总分
分值
20
10
10
30
70
得分
一、填空题(每空2分f共20分)
1.在情况下,等长编码是最优前缀码。
意为范守场律注行规遵考纱
2・设有两个算法在同一机器上运行.其执行时间分别为100*和2“f要使前者快于后者"至少为—o
3•采用堆排序、快速排序、冒泡排序,对初态有序的表,锻省时间的
S
4.设二叉树结点的先根序列为ABDECFGH,中根序列为
DEBAFCHG,则二叉树中叶结点是・
5.用下标从0幵始的N个元素的数组实现循环队列时,为实现下标变
呈m加1后在数组有效下标范围内循环,可采用的表达式是m二
O
6.由带权为3,9,4,2.5的5个叶子结点构成一棵哈夫曼树.则带
权路径长度为O
7•对n个记录的表进行选择排序,在最坏情况下所需要进行的关铤字的比较次数为—O
8.任意一个有n个结点的二叉树.已知它有m个叶结点.则度数为2的结点有—O
9」个顶点的连通图用邻接矩阵表示时,该矩阵至少
有个非零元素
10.举出两种磁带文件的分类方法二
二、选择题(每题1分,共10分)
1・设一组初始记录关键字序列为(45r80,55.40.42,85)f则以第一个记录关键字45为基准而得到一趟快速排序的结果是()。
(A)40r42,45f55r80,83(B)42,40,45,80,85.88
(C)42,40,55.80,45,85(D)42f40,45,85r55,80
2•数据的最小单位是()。
(A)数据项(B)数据类型(C)数据元素(D)数据变虽
3•关犍路径是AOE网中()。
A.从始点到终点的最迈路径
B.从始点到终点的最长路径
C.从始点到终点的边数晟多的路径
D.从始点到终点的边数最少的路径
4•下列说法正确的是()。
A・最小生成树也是哈夫曼树
B・最小生成树是唯一的
C•对于n个顶点的连通无向图,Prim算法的时间复杂性为Ofn2)
D•Kruskal算法比Prim算法更适合边稠密的图
5•设栈S和队列Q的初始状态为空.元素ElsE2、E3SE4SE5和E6依次通过栈Sr一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、Em.E6、E5和El•则桟S的容呈至少应该是()。
(A)6(B)4(C)3(D)2
6.将10阶对称矩阵压缩存储到一维数组A中.则数组A的长度最少为()。
(A)100(B)40(C)55(D)80
7.若数据元素序列11,12r13f7;8,9f23,4f5是采用下列排序方法之一得到的第二趟排序结果,则该排序算法只能是()o
8•设哈希表长m=14.哈希函数H(key)=key%llo表中已有4个结点:
addr(15)=4,addr(38)二5faddr(61)二6faddr(84)=7其余地址为空。
如果用二次探测再散列处理冲突,关犍字为49的结点的地址是()
A.8B.3C.5D.9
9・有组记录的输入顺序为(46.79,56.38,40,84).则利用堆排序方法建立的初始堆为()
A.79,46;56#38,40,80B.38,40r56;79,46#84
C.84,79f56#46r40r38D.84,56,79,40,46.38
10.下列叙述中.不符合m阶B树定义要求的是()
A.根结点最多有m棵子树B.所有叶结点都在同一层上C・各结点内的关键字有序D.叶结点之间通过指针链接
三、简答题(10分)
・带权图(权值非负,表示边连接的两个顶点的距韶)的最短路径问题是找出初始顶点到目标顶点之间的一条最短路径。
假设从初始顶点到目标顶点之间的存在路径r现有一种解决该问题的方法:
1)设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;
2)选择离u最近的且尚未在最短路径中的一个顶点v,
加入到最短路径中,修改当前顶点U=v;
3)重复步骤2)r直到是目标顶点为止。
请问上述方法能否求得最短路径?
若可行请证明之;否则,请举例说明。
四、算法设计:
栈、队列的存储结构、基本操作可以直接引用(共30分)
1.设二叉树采用左右链方式存储,设计一个判断二叉树是否是二叉排序树的算法。
(10分)
2.设有一个双链表,每个结点中除有prior、data和next三个域外,还有一个访问频度域freqf在琏表被起用之前r其值均初始化为零。
每当在链表进行一次LocateNode(L,x)is算时f令元素值为x的结点中friq域的值加1,并调整表中结点的次序,使其按访问频度的递减序排列,以便使频驚访问的结点总是靠近表头。
试写出符合上述要求的LocateNode运算的算法。
(10分)
3.给定一个无向连通图,写一个算法找出半径最小的生成树(搜索起点作为生成树的根■树的半径定义为从根到叶子的最大距离)。
(10分)
参考答案:
一、填空题
1.等概率2.153.冒泡4.EFHf5.(m+l)%N6.51
7.n(n+l)/2,n(n-l)/28.m-l9.2(n-1)10.平衡归并、
多阶段归并
二、选择题
1C2A3B4C5C6C7A8D9B10D
三、简答题
不可以。
设初始顶点为1,目标顶点为3,不能求出最短路径。
四、算法题
1・根据二叉排序树中序遍历所得结点值为增序的性质,在遍历中将当前遍历结点与其前驱结点值比较,即可得出结论。
为此设全局指针变Spre(初值为null)和全局变量flagz初值为trueo若非二叉排序树,则置flag为false。
voidJudgeBSTfBSlreet,int*flag)
|判断二叉树是否是二叉排序树,本算法结束后,在谓用程序中由flag得出结论
=null&&*flag)
{Judgebst(t->lchild,&flag);||中序遍历左子树
if(pre==null)pre=t;||中序遍历的第一个结点不必判断
elseif(pre->data
Judgebst(t->rchildF&flag);||中序遍历右子树
}|ifHJudgeBST算法结束
本题的另一算法是按定义,二叉排序树的左、右子树都是二叉
排序树,根结点的值大于左子树中所有结点的值而小于右子树中
所有结点的值,即根结点大于左子树的最大值而小于右子树的最
小值。
算法如下:
intJudgeBST(BSlreet)
II判断二叉树t是否是二叉排序树,若是,返回true,否则,返回false{if(t==null)returntrue;
if(Judgebst(t->lchild)&&judgebst(t->rchild))||左右子树均为二叉排序树
{m=max(t->lchild);n=min(t->rchild);||左子树中最大值和右子树中
最小值
return(t->data>m&&t->data }||ifI• elsereturnfalse;||不是二叉排序树11广*[ 痛婀&•IXJL1.X•J/JL Intmax(BSTreep)||求二叉树左子树的最大值 {if(p==null)returnmaxint;||返回机器最小整数 else{while(p->rchild)p=p->rchild;returnp->data; }|while}||end intmin(BSTreep)||求二叉树右子树的最小值{if(p==null)returnmaxint;||返回机器最大整数else{whlle(p->IchiId)p=p->lchild;returnp->data; }|while}||end DListlocate(DListLrElemlypex) IIL是带头结点的按访问频度递减的双向链表 ||本算法先査找数据x,査找成功时结点的访问频度域增1r煨后将该结点按频度递城插入链表中 {DUstp=L->next,q;||p为L表的工作指针.q为p的前驱.用于查找插入位§ while(p&&p->data! =x)p=p->next;||査找值为x的结点 lf(! p){prints不存在所查结点\n");exit(O): } else{p->freq++;||令元素值为x的结点的freq1 p->next->pred=p->p佗d;||将p结点从链表上摘下p->pred->next=p・Anext; q=p->pred;||以下查找p结点的插入位直 while(q! =L&&q->freq } return(p);0返回值为x的结点的捋针 }II算法结束 3.采用广度优先遍历,其邻接点均已遍历的结点是叶子结点,记下结点的半径(以分枝个数记) intMiiiiRadius(AdjListg,intv) IlSg以邻接表形式存储,求半径最小的生成树。 设顶点信息就是编号•从顶点Y开始遍历 {typed"struct {bitv,level;Juode;||队列元索 liltMAX二10设最大层次数 imvisi[ed[MAXl=O: ||访问数组 nodeR.QH;||Q为队列,容量足够大 R.v=v;R.level=l; Makeiiullt(Q);EiiQueue(Q,R); while(! Emptv(Q) (R=DeQueuG(Q);||出队 v=R.v;l=R.lcvel;p=g[v].firstcage;flag=0;||flag是顶点是否是叶子的标记while(p) {u~p->adjvex; if(visited[w]==O){flag=1;R.level=l+1;EnQueue((^R);} p=p->next; } if(flag==O)||其邻接点均已遗历的顶点是叶子结点 {if(l } renimMAX; 2010年春A卷 一、填空题(每空1分,共15分) 1.在顺序存储的二叉树中,编号为i和j的两个结点处在同一层的条件 是。 2.某二叉树的前序遍历序列是ABCDEFG,中序遍历序列是CBDAFGE, 则其后序遍历序列是。 3.在有n个叶子的哈夫曼树中,分支结点总数为个。 4.对于含有n个顶点 e条边的连通图,利用Prim算法求最小生成树的 时间复杂度为° 5.表达式a*(b+c)-d的后缀表达式是 6.假左一棵二叉树的结点数为18,则它的最小深度为,最大深 度为O 7.设有一个n阶的下三角矩阵A,如果按照行的顺序将下三角矩阵中的 元素(包括对角线上元素)存放在n(n+l)个连续的存储单元中,则A[i][j]与A[0][0]之间有个数据元素。 8.设一组初始记录关键字序列为(20,18,22,16,30,19),则根据这些初始关键字序列 建成的初始堆为。 9.磁盘文件的归并技术有 、、o10.设有向图G中有向边的集合E二{<1,2>,<2,3>,<1,4>,<4,2>, <4,3>},则该图的一种拓扑序列为」 11•设一组初始记录关键字序列为(345,253,674,924,627),则用基 数排序需要进行趟的分配和回收才能使得初始关键字序列变成有序序列。 12.利用Dijkstra算法求从有向图顶点vl到其他各顶点的最短路径要求 I 边上权值O 二、选择题(每题1分,共15分) 1.若某线性表最常用的操作是存取任一指立序号的元素和在最后进行插入和删除运算,则 利用存储方式最节省时间。 扎顺序表B.双链 表 C.单循环链表D.带头结点的双循环链表0 2.在一个具有n个单元的顺序栈中,假左以地址低端(即下标为0的单元)作为栈底,以 top作为栈顶指针,当出栈时,top的变化为oA.不 变B.top二0;=top-l;D.top二top+1; 3.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记 录的一趟快速排序结朿后的结果为oA、10,15,14,18,21,36,40, 20B、10,15,14,18,20,40,36,21C、10,15,14,20, 18,40,36,21 D、15,10,14,18,20,36,40,21 4.任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序。 扎肯宦不发生改变B.肯左发生改变 C.不能确定D.有时发生变化 5.用有向无环图描述表达式(A+B)*((A+B)/A),至少需要顶点的数目为。 B.6C.8 D.96.对线性表进行二分查找时,要求线性表必须。 A、以顺序方式存储B、以链接方式存储 C、以顺序方式存储,且数据元素有序D、以链接方式存储,且数据方式有序 7.设散列表表长m二1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈尔滨工业大学 数据结构 算法 历年 考题 汇总