2011专升本插班生《数据结构》试卷.doc

《2011专升本插班生《数据结构》试卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、韩山师范学院2011年专升本插班生考试试题计算机科学与技术专业数据结构试卷（A卷）题号一二三四五六七八总分评卷人得分一、单项选择题（每题2分，共40分）题号12345678910答案题号11121314151617181920答案1、下列选项中不是算法的必须具有的重要特性的是。A.有穷性B.正确性C.确定性D.可行性2、下列关于算法渐近阶表达式中，时间复杂度最高的是。A.5n2B.n3/2C.2nD.nlognE.n23、数据是对客观事物的符号表示，在计算机科学中，数据的含义广泛，如图像、声音等都属于数据范

2、畴，数据不意义的最小不可分割的单位是。A.数据元素B.数据对象C.数据结构D.数据项E.位4、下列有关线性表的叙述中，正确的是。A.线性表中的元素必须具有相同的特性B.线性表中的元素都有且仅有一个直接前驱C.线性表中的元素都有且仅有一个直接后继D.以上表述都不正确5、在一个长度为n有序的链式存储的线性表中插入一个元素，使其保持有序，其操作的时间复杂度是。A.O(n)B.O(1)C.O()D.O(n2)6、关于线性表的结点的存储地址表述正确的是。A.必须是不连续的B．连续与否由其存储方式确定C．必须是连续的D

3、．和头结点的存储地址相连续7、如下陈述中正确的是。A．串是一种特殊的线性表B．串的长度必须大于零C．串元素中的字母不区分大小写D．空串与空格串是相同的概念8、数组的逻辑结构不同于下列的逻辑结构。A.线性表B.栈C.树D.队列9、设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为。A．2n-1B．n2C．(n2+n)/2D．(n2+n)/2-1E.(n2-n)/2-1F.以上都不对10、中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是。A.ABD

4、EFADC+*+/+*+B.D*AB+EFAD*+/+C+C.+*+/+*+ABDEFADCD.AB+D*EFAD*+/+C+11、链表不具有的特点是。A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比12、在一个图中，所有边数等于所有顶点的度数之和的倍。A.1/2B.1C.2D.413、设某棵二叉树中有2000个结点，则该二叉树的最小高度为。A.10B.11C.12D.1314、设某棵二叉树的中序遍历序列为BGDAECHFI，前序遍历序列为ABDGCEF

5、HI，则后序遍历该二叉树得到序列为。A.GDBAECHFIB.IHGFEDCBAC.GDBECHIFAD.GDBEHIFCA15、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是。A.head（tail（tail（L）））B.tail（head（head（tail（L））））C.head(tail(head（tail(L））））D.head(tail(head(tail(tail（L）））))16、设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为。A．top

6、=top-1B.top=top->nextC.top->next=topD.top->next=top->next17、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为n1，n2和n3。则与森林F对应的二叉树根结点的右子树上的结点个数是。A.n1+n2B.n1+n3C.n2+n3D.n1+n2+n318、设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为。A.430B.45C.50D.5519、设无向图的顶点个数为n，则该图最多有条边。A．n-1B．nC．n(

7、n-1)D．n(n+1)/2E．n(n-1)/220、在二叉排序树中插入一个关键字值的平均时间复杂度为。A．O(1ogn)B.O(n)C.O(nlogn)D.O(n2)。二、名词解析（每题3分，共6分）1、平衡二叉树：2、哈夫曼（Huffman）树：三、填空题（每空2分，共18分）1、在完全二叉树的第6层上最少有__________个结点，最多有_________个结点。2、普里姆（Prime）算法的时间复杂度为______,它对______图较为适合。3、顺序查找n个元素的顺序表，若查找成功，则比较关键字

8、的次数最多为__次；当使用监视哨时，若查找失败，则比较关键字的次数为。4、设有一组初始记录关键字序列为(49，38，65，85,97，76，13，90,27，50)，则以d=3为增量的一趟希尔排序结束后的结果为_____________________________。5、设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i与顶点j互为邻接点的条件是______________________，无向