11年韩山专插本专业科试卷2011专升本插班生《数据结构》试卷

（A卷）第 1 页 共 7 页 韩山师范学院2011年专升本插班生考试 试题 中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载 计算机科学与技术 专业 数据结构 试卷 （A卷） 题号 一 二 三 四 五 六 七 八 总分 评卷人 得分 一、单项选择题（每题2分，共40分） 题号 1 2 3 4 5 6 7 8 9 10 答案 题号 11 12 13 14 15 16 17 18 19 20 答案 1、下列选项中不是算法的必须具有的重要特性的是 。 A. 有穷性 B. 正确性 C. 确定性 D. 可行性 2、下列关于算法渐近阶表达式中，时间复杂度最高的是 。 A. 5n2 B. n3/2 C. 2n D. nlogn E. n2 3、数据是对客观事物的符号表示，在计算机科学中，数据的含义广泛，如图像、声音等都属于数据范畴，数据不意义的最小不可分割的单位是 。 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．和头结点的存储地址相连续 7、如下陈述中正确的是 。 A．串是一种特殊的线性表 B．串的长度必须大于零 C．串元素中的字母不区分大小写 D．空串与空格串是相同的概念 8、数组的逻辑结构不同于下列 的逻辑结构。 A. 线性表 B.栈 C. 树 D. 队列 9、设 S 为一个长度为 n 的字符串，其中的字符各不相同，则 S 中的互异的非平凡子串（非空且不同于S本身）的个数为 。 A．2n-1 B．n2 C．(n2+n)/2 D．(n2+n)/2-1 E. (n2-n)/2-1 F.以上都不对 10、中缀表达式 (A + B) * D + E / (F + A * D) + C的后缀形式是 。 A. A BDEFAD C +*+ / +*+ B. D *A B + E F A D * + / + C + C. +*+ / +*+A BDEFADC D. A B + D * E F A D * + / + C + 11、链表不具有的特点是 。 A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 12、在一个图中，所有边数等于所有顶点的度数之和的 倍。 A.1/2 B.1 C.2 D.4 13、设某棵二叉树中有2000个结点，则该二叉树的最小高度为 。 A.10 B.11 C.12 D.13 14、设某棵二叉树的中序遍历序列为BGDAECHFI，前序遍历序列为ABDGCEFHI，则后序遍历该二叉树得到序列为 。 A. GDBAECHFI B. IHGFEDCBA C.GDBECHIFA D. GDBEHIFCA 15、已知广义表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=top-1 B. top=top->next C. top->next=top D. top->next=top->next 17、设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为 n1，n2 和 n3。则与森林 F 对应的二叉树根结点的右子树上的结点个数是 。 A. n1+n2 B. n1+n3 C. n2+n3 D. n1+n2+n3 18、设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为 。 A. 430 B. 45 C. 50 D. 55 19、设无向图的顶点个数为 n，则该图最多有 条边。 A．n-1 B． n C． n(n-1) D．n(n+1)/2 E．n(n-1)/2 20、在二叉排序树中插入一个关键字值的平均时间复杂度为 。 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 个元素的顺序表，若查找成功，则比较关键字的次数最多为__ 次；当使用监视哨时，若查找失败，则比较关键字的次数为 。 4、设有一组初始记录关键字序列为(49，38，65，85,97，76，13，90,27，50)，则以d=3为增量的一趟希尔排序结束后的结果为_____________________________。 5、设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i与顶点j互为邻接点的条件是______________________，无向图的邻接矩阵具有 特性。 6、若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__ ____和记录的__ ___。 7、在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= 。 8、数据的存储结构包括 的表示和 的表示。 9、散列检索技术的关键是__ ____和 __ ____。 四、判断题（每小题1分，共8分） 1、调用一次深度优先遍历可以访问到图中的所有顶点。（ ） 2、完全二叉树一定是满二叉树，满二叉树不一定是完全二叉树。（ ） 3、顺序存储结构的主要缺点是不利于插入或删除操作。( ) 4、数组不适合作为任何二叉树的存储结构。（ ） 5、任何一个递归过程都可以转换成非递归过程。 （ ） 6、设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ ） 7、带权无向图的最小生成树的权值必是固定的。（ ） 8、在 AOE 图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。 （ ） 五、程序填空题（每个空1分，共12分） 1、如下的算法是从串s中删除所有与t相同的子串,并返回删除次数。 int SubString_Delete(Stringtype &s,Stringtype t) //从串s中删除所有与t相同的子串,并返回删除次数 {   for(n=0,i=1;i<=s[0]-t[0]+1;i++)   {     for(j=1;j<=t[0] && s[i+j-1]== （1） ;j++);     if(j> （2） ) //找到了与t匹配的子串     {       for(k=i;k<=s[0]-t[0];k++) s[k]=s[k+t[0]]; //左移删除        s[0]-=t[0]; （3）     }   }//for   return （4） ; }//Delete_SubString 2、n 个顶点的有向图用邻接矩阵 array 表示，下面是其拓扑排序算法，试补充完整。 注：（1）图的顶点号从 0 开始计； （2）indegree 是有 n 个分量的一维数组，放顶点的入度；（3）函数 crein 用于算顶点入度；（4）有三个函数 push(data),pop( ),check( )其含义为数据 data 进栈，退栈和测试栈是否空（不空返回 1，否则 0）。 crein( array ,indegree,n) { for (i=0;i