微机原理与接口2

《微机原理与接口2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、济南铁道职业技术学院专升本辅导《数据结构》试题(模B)一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,答题写在其它地方无效；每小题1分,共11分)题号1234567891011答案1.数据的基本单位是____。A.结点B.数据元素C.数据类型D.数据项2.下列算法suanfa1中语句"x=x2；"的执行次数是____。voidsuanfa1(intn){inti,j,x=1；for(i=1；i<=n；i++)for(j=i；j<=n；j++)x=x2；printf("%d",x)；}A.n(n-1)/2B.

2、n(n+1)/2C.n2D.énlog2nù3.当需要随机查找线性表的元素时,宜采用____作存储结构。A.双向链表B.循环链表C.顺序表D.单链表4.若8行6列的数组以行序为主序顺序存储,基地址为2000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是____。A.2086B.2032C.2068D.答案A,B,C都不对5.广义表(a,(b),c,(d,(e)))的表尾是____。A.(d,(e))B.(d,(e))）C.(b),c,(d,(e))D.((b),c,(d,(e)))6.____是"YuJiaShan"的子串。

3、A.YuB."jia"C."Shan"D."YuJiaShan"7.无向完全图的邻接矩阵是____矩阵。A.对称B.上三角C.下三角D.稀疏8.有n(n>0)个结点的完全二叉树的深度是____。A.élog2(n)+1ùB.élog2(n)-1ùC.ëlog2(n)-1ûD.ëlog2(n)+1û9.与中缀表达式a-b/c+d等价的前缀表达式是____。A.-a+/bcdB./-+bcdC.+-a/bcdD.abcd-/+10.对有3600个记录的索引顺序表(分块表)进行查找,最理想的块长为____。A.1800B.60C.1200D.élog23600

4、ù11.对n个元素的表作堆排序,在最坏情况下,算法的时间复杂度为____。A.O(log2n)B.O(nlog2n)C.O(n2)D.O(2n)二、填空题(每空1分,共11分)1.一个算法具有5个特性:__________________、__________________、________________、有零个或多个输入、有一个或多个输出。2.设长度为n的线性表顺序存贮,若在它的第i-1和第i个元素之间插入一个元素,共需移动_________个元素(1

5、.树中结点A的____________________称为结点A的度。5.一棵深度为4的二叉树最多有_______个结点。6.具有10个顶点的无向图,边的总数最多为_____________。7.顺序查找n个元素的顺序表,当不使用监视哨时,若查找成功,比较关键字的次数最多为____次；若查找失败,比较关键字的次数为_____次。8.折半查找有序表(2,4,6,12,20,28,38,50,70,100),若查找表中元素12,它依次与表中元素___________________比较大小。三、回答下列问题(每小题5分,共10分)1.线性表的存储结构,在什么

6、情况下采用链接表(如:单链表)结构?为什么?2.空格串与空串有区别?举例说明之。四、试画出下列存储结构图(每小题5分,共20分)1.试画出下列稀疏矩阵以列序为主序的三元组表。稀疏矩阵2.试画出下列二叉树的中序线索二叉树存储结构图。二叉树3.试用孩子兄弟(左孩子右兄弟)表示法画出下列树的存储结构图。树4.试画出下列有向网的逆邻接表。有向网五、求解下列问题(每小题6分,共24分)1.已知二叉树的前序遍历序列和中序遍历序列分别是：B,A,C,D,F,E,G和D,C,A,F,G,E,B,试画出该二叉树。2.试按表(25,15,19,24,20,5,16,45,4

7、0,38)中元素的排列次序,将所有元素插入一棵初始为空的二叉排序树中,使之仍是一棵二叉排序树。(1)试画出插入完成之后的二叉排序树；(2)若查找元素17,它将依次与二叉排序树中哪些元素比较大小?(3)假设每个元素的查找概率相等,试计算该树的平均查找长度ASL；(4)对该树进行中序遍历,试写出中序遍历序列。3.试用权集合{4,6,5,12,2,1,13},构造赫夫曼(Huffman)树,(1)列出构造过程,(2)分别计算该赫夫曼树的路径长度和带权路径长度。4.找出下面网络的最小生成树:六、执行下面的C程序,指出输出结果。(8分)#include

8、.h>#includestructnode{chardata