2012年韩山师范学院本科插班生《数据结构》试卷

1、2012年韩山师范学院本科插班生考试试卷计算机科学与技术专业 数据结构试卷(A卷)一、单项选择题(每题2分，共40分)1、 下列选项中不是算法的必须具有的重要特性的是。有穷性 B.正确性 C.确定性 D.可行性2、 下列关于算法渐近阶表达式中，时间复杂度最高的是。5n2 B. n3/2C. 2n D. nlogn E. n23、数据是对客观事物的符号表示，在计算机科学中，数据的含义广泛，如图 像、声音等都属于数据范畴，数据不意义的最小不可分割的单位 是。A.数据元素B.数据对象C.数据结构D.数据项 E.位4、 下列有关线性表的叙述中，正确的是。线性表中的元素必须具有相同的特性线性表中的元素都

2、有且仅有一个直接前驱线性表中的元素都有且仅有一个直接后继以上表述都不正确5、在一个长度为n有序的链式存储的线性表中插入一个元素，使其保持有序，其操作的时间复杂度是。A. O(n) B. O(1)C.O(an)D.O(n2)6、关于线性表的结点的存储地址表述正确的是。A.必须是不连续的B.连续与否由其存储方式确定C.必须是连续的D.和头结点的存储地址相连续7、如下陈述中正确的是。B.串的长度必须大于零D.空串与空格串是相同的概念的逻辑结构。D.队列A.串是一种特殊的线性表C.串元素中的字母不区分大小写8、数组的逻辑结构不同于下列A.线性表 B.栈 C.树9、设S为一个长度为n的字符串，其中的字符

3、各不相同，则S中的互异 的非平凡子串(非空且不同于S本身)的个数为。A. 2n-1B. n2C. (w+n)/2D. (n2+n)/2-1E. (n2-n)/2-1F.以上都不对10、中缀表达式(A + B) *D + E/ (F +A*D) +C的后缀形式是nextC. top-next=top D. top-next=top-next17、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为n1，n2和n3。则与森林F对应的二叉树根结点的右子树上的结点个数是。A. n1+n2 B. n1+n3 C. n2+n3 D. n1+n2+n318、设一组权值集合W=2, 3, 4, 5, 6,

4、则由该权值集合构造的哈夫曼树 中带权路径长度之和为。A. 430 B. 45C. 50D. 5519、 设无向图的顶点个数为n,则该图最多有 条边。A. n-1B. n C. n(n-1)D. n(n+1)/2 E. 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)算法的时间复杂度为，它对 图较为

5、适合。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=。

6、8、 数据的存储结构包括 的表示和 的表示。9、 散列检索技术的关键是 和。四、判断题（每小题1分，共8分） TOC o 1-5 h z 1、调用一次深度优先遍历可以访问到图中的所有顶点。（）2、完全二叉树一定是满二叉树，满二叉树不一定是完全二叉树。（）3、顺序存储结构的主要缺点是不利于插入或删除操作。（）4、数组不适合作为任何二叉树的存储结构。（）5、 任何一个递归过程都可以转换成非递归过程。（）6、 设一棵树T可以转化成二叉树BT,则二叉树BT中一定没有右子树。（）7、带权无向图的最小生成树的权值必是固定的。（）8、在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。（

7、）五、程序填空题（每个空1分，共12分）1、如下的算法是从串s中删除所有与t相同的子串，并返回删除次数。int SubString_Delete（Stringtype &s,Stringtype t）从串s中删除所有与t相同的子串，并返回删除次数for(n=0,i=1;i=s0-t0+1;i+)(for(j=1;j (2)/找到了与t匹配的子串(for(k=i;k=s0-t0;k+) sk=sk+t0;左移删除s0-=t0;(3)/forreturn 4);/Delete_SubString2、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试 补充完整。注：(1)图的顶点号从

8、0开始计；(2)indegree是有n个分量的一 维数组，放顶点的入度；(3)函数crein用于算顶点入度；(4)有三个 函数push(data),pop( ),check()其含义为数据data进栈，退栈和测 试栈是否空(不空返回1，否则0)。crein( array ,indegree,n)(for (i=0;in;i+)indegreei= _(1)_ for(i=0,in;i+)for (j=0;jn; j+)indegreei+= (2) _;topsort (array,indegree,n)(count= (3)_for (i=0;in;i+)if (4) _) push(i)while (check()(vex=pop();printf(vex);count+;for (i=0;in;i+)(k=(5)if ( (6)(indegreei-;if (7)push(i);if( )printf( “图有回路”);六、算法设计题(每题8分，16分)1、设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedef struct (int vertexm;int edgemm;gadjmatrix;typedef struct node1(int info;int adjvertex;struct node1 *nextarc;glink