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

1、wordword格式-感谢下载支持wordword格式-感谢下载支持2013 年韩ft师范学院本科插班生考试试卷计算机科学与技术专业 数据结构 试卷 （A卷）一、 单项选择题（每题1.5分，共30分1、数据的不可分割的最小单位是（。A数据元素B数据对象C数据项D数据串2、一个算法应该具有一些重要特性，下列不是算法特性的是（） 。A有穷性B确定性C可行性D健壮性E至少一个输3、下面关于线性表的表述中（）是错误的？ A若线性表采用顺序存储，必须占用一片连续的存储单元B若线性表采用顺序存储，便于进行插入和删除操作。 C线性表采用链接存储，占用的存储单元不一定是连续的D线性表采用链接存储，便于插入和删

2、除操作。4、下列哪个不是链表所具有的特点是（。 A可随机访问表中元素B插入、删除不需要移动元C线性链表必须有一个指针域D所需空间与线性长度成正比5、若线性表的长度为n，且采用顺序存储结构，则等概率删除其第i个元素的算法的时复杂度为（）(1=inext=NULLC.H-nextNULL D.Hnext=H10、若一个栈的输入序列为 1,2,3,n，输出序列的第一个元素是 i，则第 j 个输出元素是（。A.不确定的B. i-jC. j-i+1D. i-j-111、在一个单链表中,若q所指结点是p所指结点的前驱结点,若要删除p所指的结点,则行()。A. q-next=pC. p=q-next;B.

3、q-next=p-next;D. p-next= q-next;12A=(a,(b,c),(d,e),(f,g),Head(Tail(Head(Tail(Tail(A)（。A. (f)B.fC. eD. (e)13在一棵度为3的树中,度数为3的结点有2个,度数为2的结点有2个则度为0的结个数为()A7B8C914、在下述结论中，正确的是（）只有一个结点的二叉树的度为 0; 二叉树的度为 2； 二叉树的左右子树可意交换;深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。ABCD15、算术表达式a+b*（c+d/e）转为后缀表达式后为（） Aabcde/+*+B ab+cde/+*C

4、abcde/*+16、一个有n 个结点的图，最多有（）个连通分量。AnBn-1C1D017、若目标串的长度为 n，模式串的长度为n/4，则执行模式匹配算法时，在最坏情况的时间复杂度是（）AO（nlogn）BO（n/4）CO（n）DO（n2）18、设一组初始记录关键字序列(7，2，8,6，3，10,5)，7趟快速排序的结果为（ 。A. 2，5，6，3，7,8, 10B. 5，2，3，6，7,10, 8C. 2，3，5，6, 7, 8，10D. 5，2，6，3, 7， 8, 1019、向二叉搜索树中插入一个元素的时间复杂度是()AO(n）BO(logn)CO(n*logn)22DO(n+logn)

5、E.O(n2)F.O(n3)220、一个递归算法必须包括（。A.初始条件和递归部分B.初始条件和迭代部C.终止条件和递归部分D.终止条件和迭代部得分评卷人得分评卷人1、什么叫完全二叉树4分，2、简述顺序存储队列的假溢出的避免方法及队列满和空的条件。（6 分）得分评卷人三得分评卷人1根据线性表的链式存储结构中每一个结点包含的指针个数将线性链表分成 和；而又根据指针的连接方式，链表又可分成和 。2、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结分别有个和个。3、数据结构中评价算法的两个重要指标是算法的和。4、循环队列的引入，目的是为了克服 5串是一种特殊的线性表其特殊性

6、表现在 。 方式是、；两个串相等的充分必要条件是 。6nn 列的下三角矩阵 A 已压缩到一维数组 存储，则Aij对应的 B 中存储位置为。7、二叉树中某结点的左子树深度减去右子树深度称为该结点的 二叉树的结点的可能取值是。_，平衡8、已知一个图如右图所示，若采用深度优先遍历该图，则遍8、已知一个图如右图所示，若采用深度优先遍历该图，则遍历 的 序 列为。90N1N012的结点数为若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有 个空指针域。10、直接插入排序用监视哨的作用是。得分评卷人四、判断题得分评卷人1数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构（）word 格

7、式-可编辑-感谢下载支持2、链表中的头结点仅起到标识的作用。()3、为了很方便的插入和删除数据，可以使用双向链表存放数据。()4、若输入序列为 则通过一个栈可以输出序列word 格式-可编辑-感谢下载支持2、链表中的头结点仅起到标识的作用。()3、为了很方便的插入和删除数据，可以使用双向链表存放数据。()4、若输入序列为 则通过一个栈可以输出序列。（）5（）6（）word word 格式-可编辑-感谢下载支持7、KMP算法的特点是在模式匹配时指示主串的指针不会变小。 （）8、若一个广义表的表头为空表，则此广义表亦为空表（）9、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度（ 1

8、、最小生成树的 Kruskal 算法是一种贪心法（Greedy（）得分评卷人得分评卷人1、下列算法的功能是比较两个链串的大小，其返回值为：comstr(s1,s2)=1当scomstr(s1,s2)=0当 1 2请在空白处填入适当的内容。ss请在空白处填入适当的内容。1当1 2ss12int comstr(LinkString s1,LinkString s2)/s1 和 s2 为两个链串的头指针while (s1&s2)if (s1datedate) if (s1dates2date)return1；if()return1；if()return1；2、如下为二分查找的非递归算法，试将其填写完整。IntBinsch(ElemTypeA , int n,KeyTypeK)int low, high =0;while (low=high)int mid=if (K=Amid.key)return mid;else if (Kmid.key)else return -1;/查找失败得分评卷人六、算法设计题（20得分评卷人1、设计判断单链表中