数据结构试题1new

《数据结构试题1new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、网计(专升本)《数据结构》试题(模A)一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号1.数据的不可分割的基本单位是____。A.元素B.结点C.数据类型D.数据项2.下列算法suanfa2的时间复杂度为____。intsuanfa2(intn){intt=1；while(t<=n)t=t*2；returnt；}A.O(log2n)B.O(2n)C.O(n2)D.O(n)3.____又称为FIFO表。A.队列B.散列表C.栈D.哈希表4.若6行8列的数组以列序为主序顺序存储,基地址为1000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是__

2、__。A.1086B.1032C.1068D.答案A,B,C都不对5.广义表(a,((b,()),c),(d,(e)))的深度是____。A.5B.4C.3D.26.有n(n>0)个结点的完全二叉树的深度是____。A.élog2(n)ùB.élog2(n)+1ùC.ëlog2(n+1)ûD.ëlog2(n)+1û7.与中缀表达式a+b*c-d等价的前缀表达式是____。A.+a-*bcdB.*+-abcdC.-+a*bcdD.abcd+*-8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次与表中元素____进行比较,。A.65,15,

3、37B.68,30,37C.65,15,30D.65,15,30,379.对长度为10的表作选择(简单选择)排序,共需比较____次关键字。A.45B.90C.55D.11010.对n个元素的表作快速排序,在最坏情况下,算法的时间复杂度为____。A.O(log2n)B.O(nlog2n)C.O(n2)D.O(2n)共5页第1页11.对长度为10的表作2_路归并排序,共需移动____次(个)记录。A.20B.45C.40D.30二、填空(每空1分,共11分)1.一个数据结构在计算机中的表示(映象)称为________________。2.线性表中_____________________

4、_______称为表的长度。3.栈中元素的进出原则为_____________________。4.设数组A[1..10,1..8]的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素A[4,5]的存储地址为_____；若以列序为主序顺序存储,则元素A[4,5]的存储地址为______。5.一棵深度为6的满二叉树有______个非终端结点。6.若一棵二叉树中有8个度为2的结点,则它有_____个叶子。7.顺序查找n个元素的顺序表,当使用监视哨时,若查找成功,比较关键字的次数至少为____次,最多为____次；若查找失败,比较关键字的次数为____次。8.对长度为40

5、0的表采用分块(区)查找,最理想的块长为____。三、回答下列问题(每小题5分,共10分)1.线性表的存储结构,在什么情况下采用顺序结构?为什么?2.二叉树有哪几种基本形态?画图说明之。四、试画出下列存储结构图(每小题4分,共20分)1.数组A[1..2,0..2]的以列序为主序的顺序存储结构。2.依次将元素A,C,D,B插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈。3.二叉树的顺序存储结构:4.图的邻接矩阵:5.有向图的逆邻接表:五、求解下列问题(每小题6分,共24分)1.给定30个字符组成的电文:DDDDDAAABEEAAFCDAACABBCCCBAADD试为字符A

6、、B、C、D、E、F设计哈夫曼(Huffman)编码。(1)画出相应的哈夫曼树；(2)分别列出A、B、C、D、E、F的哈夫曼码；(3)计算该树的带权路径长度WPL。2.试按表(10,8,9,12,20,5,6,15,19,25)中元素的排列次序,将所有元素插入一棵初始为空的二叉排序树中,使之仍是一棵二叉排序树。(1)试画出插入完成之后的二叉排序树；(2)若查找元素17,它将依次与二叉排序树中哪些元素比较大小?(3)假设每个元素的查找概率相等,试计算该树的平均查找长度ASL。(4)对该树进行中序遍历,试写出中序遍历序列。3.试将森林F={T1,T2,T3,T4}转换为一棵二叉树。T1T2T

7、3T44.找出下面网络的最小生成树。六、填空题(在算法中有下划线____的位置填空,使之成为完整、正确的算法)算法说明:已知r[1..n]是n个记录的递增有序表,用折半查找法查找关键字为k的记录,若查找失败,则输出”Failure”,返回零；否则输出”Success”,并返回该记录的序号值。(共8分)算法(C函数):共5页第4页intbin_search(structarecordr[],intn,k:keytype)/*r[1..