数据结构试题(白明)试题 参考答案

试卷编号试卷编号命题人：白明试卷分类〔A卷或B卷〕A五邑大学试卷学期：2021至2021学年度第二学期课程：数据结构专业：班级：AP0706姓名：学号：题号一二三四五总分得分一、单项选择题(10小题，每题1分，共10分)1．假设一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，那么第i个输出元素是____D________。A．不确定 B．n-i C．n-i-1 D．n-i+12．设计一个判别表达式中左右括号是否配对的算法，采用_____B______数据结构最正确。A．顺序表 B．栈 C．队列 D．链表3．设有两个串p和q，求q在p中首次出现的位置的运算称作___C_____。A．连接 B．求子串 C．模式匹配 D．求串长4．线性表的顺序存储结构是一种_____A______的存储结构。A．随机存取 B．顺序存取 C．索引存取 D．散列存取 5．对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是____C_____。A．O(1) B．O(n) C．O(n2) D．O(nlog2n)6．关键路径是AOE网中____A______。A．从源点到终点的最长路径 B．从源点到终点的最短路径C．最长的回路 D．最短的回路7．数据元素为〔34,76,45,18,26,54,92,65〕，按照依次插入结点的方法生成一棵二叉排序树，那么该树的深度为_____B______。A．3 B．5 C．7 D．98．对数列〔25,84,21,47,15,27,68,35,20〕进行排序，元素序列的变化情况如下：(1)25，84，21，47，15，27，68，35，20(2)20，15，21，25，47，27，68，35，84(3)15，20，21，25，35，27，47，68，84(4)15，20，21，25，27，35，47，68，84那么采用的排序方法是______A_____。A．快速排序 B．归并排序 C．基数排序 D．希尔排序9．任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序____A_____。A．肯定不发生改变 B．肯定发生改变C．不能确定 D．有时发生变化10．对特殊矩阵采用压缩存储的目的主要是为了___D____。A．表达变得简单 B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素 D．减少不必要的存储空间二、判断题(10小题，每题1分，共10分)〔×〕1．一个图的邻接矩阵表示是惟一的，邻接表表示也惟一。〔×〕2．设有5000个元素，希望用最快的速度挑选出前10个最大的，采用快速排序方法比采用堆排序更好。〔√〕3．在散列函数H(k)=kmodm中，一般来讲，m应取素数。〔√〕4．从逻辑关系上讲，数据结构主要分为集合、线性结构、树结构和图结构。〔√〕5．一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，那么第1个元素的地址为112。〔√〕6．数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为(rear－front＋n)%n。〔×〕7．将数组称为随机存取结构是因为数组元素是随机的。〔√〕8．排序的主要目的时为了以后对已排序的数据进行查找。〔√〕9．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。〔×〕10．拓扑排序算法和广度优先遍历算法都能判断一个有向图是否存在回路。三、填空题(10小题，每空1分，共16分)1．表示有100个顶点，1000条边的有向图的邻接矩阵有__1000__个非零矩阵元素。2．如果要将序列〔50,16,23,68,94,70,73〕建成堆，只须把16与____50_____交换。3．具有6个顶点的无向图至少应该有_____5____条边才能确保是一个连通图。4．含A、B、C这3个结点的不同形态的树有___2___棵，不同形态的二叉树有___5___棵。5．中缀表达式(56－20)／(4＋2)转换为后缀表达式为56#20-4#2+/，后缀表达式AB／CDE＋×－转换为中缀表达式为A/B-C*〔D+E〕。6．一个有序表的关键字序列为1，8，12，25，29，32，40，62，98，当二分查找值为29的元素时，需要__1__次比拟才能查找成功；假设采用顺序查找时，需要__5__次比拟才能查找成功。7．一棵树T的边集为{〔I,M〕,〔I,N〕,〔E,I〕,〔B,E〕,〔B,D〕,〔C,B〕,〔G,J〕,〔G,K〕,〔A,G〕,〔A,F〕,〔H,L〕,〔A,H〕,〔C,A〕}，那么该树的根结点是__C__，叶子结点共__7__个，该树的深度为___5____。8．设待处理问题的规模为n，假设一个算法的时间复杂度为一个常数，那么表示成数量级的形式为__O(1)__；假设为n×log25n,那么表示成数量级的形式为_O(nlog2n)_。9．在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是s->next=rear->next;rear->next=s;和rear=s。10．二叉树的前序序列和后序序列正好相反，那么该二叉树一定是___高度等于其结点数__的二叉树。四、应用题(共有7小题，共计50分)一棵二叉树的中序遍历序列是ABCDEFG，后序遍历序列是BDCAFGE，画出该二叉树，并给出该二叉树的前序遍历序列，画出该二叉树对应的森林。(10分)解答：二叉树如下〔5分〕：对应的森林如下〔3分〕：ECAGFDECAGFDBECADBGF前序遍历序列是：EACBDGF〔2分〕证明：对于一棵非空的二叉树，如果叶结点数为n0，度为2的结点数为n2，那么有n0=n2+1。〔5分〕证明：设n为二叉树的结点总数，n1为二叉树中度为1的结点数，那么有：n＝n0＋n1＋n2〔2分〕在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由于这些分枝是由度为1和度为2的结点射出的，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有：n＝n1＋2n2＋1〔2分〕合并两式，可以得到：n0＝n2＋1。〔1分〕假设输入序列是{3，5，1，9，4，10，2，8，7，6}，试画出所产生的大根堆和所对应的二叉排序树。〔7分〕大根堆：4分二叉排序树：3分1313456971082某字符串S中共有5种字符(A，B，C，D，,E)，各种字符出现的频率分别是{15，36，3，6，20}，建立相应的哈夫曼树，对该字符串用[0，1]进行前缀编码，给出5种字符的哈夫曼编码，并计算其WPL。〔7分〕哈夫曼树：4分哈夫曼编码：2分WPL：1分A：111A：111B：0C：1100D：1101E：10WPL=36+40+45++36=157给定表〔19,14,22,01,66,21,83,27,56,13,10〕，按表中元素顺序构造一棵AVL树。〔7分〕每个平衡步骤1分。6．某图的邻接表如下〔7分〕：分别给出从A、B点出发进行广度优先搜索的序列。画出该图。解答：分别给出从A、B点出发进行广度优先搜索的序列。〔各2分〕A：ABCD B：BACD对应的图如下：〔3分〕7．设有一组关键字{72，35，124，153，84，57}需要插入到表长为12的散列表中。试设计一个适当的散列函数；用此散列函数将上述关键字插入散列表，用线性探测法解决冲突。试画出最终的散列表结构。说明：哈希函数不同，数据在哈希表中的位置不同。〔多解〕假设设：H(key)=key%11〔2分〕那么最终的哈希表结构为：〔3分〕所有关键字求散列值：〔2分〕012345678……72153124358457〔3〕五、算法设计题(2小题，每题7分，共14分)1．设计一个算法，判断一个单链表中的元素是否递增有序。template<classT>intorder(Node<T>*h){ Node<T>*p=h;以上1分 while(p->next!=NULL) if(p->data<p->next->data) p=p->next;以上3分 else break; if(p->next==NULL) return1; else return0;} 以上3分2．一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历。说明：仅给出一种参考算法，可以用递归算法或其它情况。template<classT>voidPreOrder(Ta[],intn){top=-1;i=1;cout<<a[i];S[++top]=i;j=2*i; 以上2分while(top!=-1){while(j<=n){cout<<a[i];S[++top]=j;i=j;j=2*i} 以上3分i=S[top--];j=2*i+1;}} 以上2分• • • • • • • • • • • • • • • • • • 【唯美句子】走累的时候，我就到升国旗哪里的一角台阶坐下，双手抚膝，再闭眼，让心灵受到阳光的洗涤。懒洋洋的幸福。顶3收藏2• 【唯美句子】一个人踮着脚尖，在窄窄的跑道白线上走，走到很远的地方又走回来。阳光很好，温暖，柔和。漫天的安静。顶7收藏7• 【唯美句子】清风飘然，秋水缓淌。一丝云起，一片叶落，剔透生命的空灵。轻轻用手触摸，就点碎了河面的脸。落叶舞步婀娜不肯去，是眷恋，是装点？瞬间回眸，点亮了生命精彩。顶11收藏9• 【唯美句子】几只从南方归来的燕子，轻盈的飞来飞去，“几处早莺争暖树，谁家新燕啄春泥，〞其乐融融的山林气息，与世无争的世外桃源，让人心旷神怡。顶0收藏2• 【唯美句子】流年清浅，岁月轮转，或许是冬天太过漫长，当一夜春风吹开万里柳时，心情也似乎开朗了许多，在一个风轻云淡的早晨，踏着初春的阳光，漫步在碧柳垂青的小河边，看小河的流水因为解开了冰冻而欢快的流淌，清澈见底的的河水，可以数得清河底的鹅软石，偶尔掠过水面的水鸟，让小河荡起一层层的涟漪。河岸换上绿色的新装，刚刚睡醒的各种各样的花花草草，悄悄的露出了嫩芽，这儿一丛，那儿一簇，好似是交头接耳的议论着些什么，又好象是在偷偷地说着悄悄话。顶3收藏4• 【唯美句子】喜欢海子写的面朝大海春暖花开，不仅仅是因为我喜欢看海，还喜欢诗人笔下的意境，每当夜深人静时，放一曲纯音乐，品一盏茶，在脑海中搜寻诗中的恬淡闲适。在春暖花开时，身着一身素衣，站在清风拂柳，蝶舞翩跹的百花丛中，轻吹一叶竖笛，放眼碧波万里，海鸥，沙滩，还有扬帆在落日下的古船，在心旷神怡中，做一帘红尘的幽梦。顶0收藏2• 【唯美句子】繁华如三千东流水，你只在乎闲云野鹤般的采菊东篱、身心自由，置身置灵魂于旷野，高声吟唱着属于自己的歌，悠悠然永远地成为一个真真正正的淡泊名利、鄙弃功名利禄的隐者。顶1收藏3• 【唯美句子】世俗名利和青山绿水之间，你选择了淡泊明志，持竿垂钓碧泉绿潭；权力富贵和草舍茅庐之间，你选择了宁静致远，晓梦翩跹姹紫嫣红。顶2收藏3• 【唯美句子】那是一株清香的无名花，我看到了它在春风夏雨中风姿绰约的模样，可突如其来的秋雨，无情的打落了它美丽的花瓣，看着它在空谷中单独凋零，我莫名其妙的心痛，像针椎一样的痛。秋雨，你为何如此残忍，为何不懂得怜香惜玉，我伸出颤抖的双手，将散落在泥土里的花瓣捧在手心。顶4收藏5• 【唯美句子】滴答滴答，疏疏落落的秋雨，赶着时间的脚步，哗啦啦的下起来。听着雨水轻轻地敲击着微薄的玻璃窗，不知不觉，我像是被催眠了一样，渐渐的进入了梦乡。顶3收藏5• 【唯美句子】在这极致的悲伤里，我看到了世间最美的爱，可谁又能明白，此刻的我是悲伤还是欢喜，也许只有那拨动我心弦的秋季，才知道潜藏在我心中的眼泪。顶4收藏3• 【唯美句子】看着此情此景，我细细地聆听。像是听到了落叶的呢喃，秋风的柔软，在这极短的瞬间，他们一起诉说着最美的爱恋，演绎着永恒的痴缠。当落叶安详的躺在大地，露出幸福的模样，你看，它多像一个进入梦乡的孩子。突然发现，秋风并非是想象中的刽子手，原来它只是在叶子生命的最后一刻，让它体会到爱的缠绵，飞翔的滋味。顶1收藏1• 【唯美句子】很感谢那些耐心答复我的人，公交上那个姐姐，还有那位大叔，我不知道他们是不是本地人，但我们遇到的一个交警协管，一位头发花白的大姐，她是上海本地人，很和蔼，并不像有些人说的上海人很排外。事实上，什么都不是绝对的。顶2收藏0• 【唯美句子】我嗅到浓郁的香奈尔，却也被那种陌生呛了一鼻。也许，我却不知道，那时的感受了。那里没有那么美好，没有平安感，归属感。我想要的自由呢，不完全地体验到了。顶2收藏1• 【唯美句子】那些繁华的都市，车水马龙，灯红酒绿，流光溢彩，却充满着一种悲哀，浮夸。我看到各种奢华，却也看到各种卑微，我看到友善亲和，也看到暴躁粗鲁，我看到金光熠• 【优美语句】踏过一片海，用博识的学问激起片片微澜；采过一丛花，正在聪明的碰碰外送来缕缕清喷鼻；无过一个梦，决定从那里启程。顶0收藏0• 【优美语句】人生如一本书，应该多一些精彩的细节，少一些乏味的字眼；人生如一支歌，应该多一些昂扬的旋律，少一些忧伤的音符；人生如一幅画，应该多一些亮丽的色彩，少一些灰暗的色调。顶0收藏0• 【优美语句】母爱是一滴甘露，亲吻干涸的泥土，它用细雨的温情，用钻石的坚毅，期待着闪着碎光的泥土的肥沃；母