2012韩山师范学院专升本插班生考试《数据结构》试卷

（A卷）第1页共8页韩山师范学院2012年专升本插班生考试计算机科学与技术专业数据结构试卷（A卷）题号一二三四五六总分评卷人得分一、单项选择题（每题1.5分，共30分）题号12345678910答案题号11121314151617181920答案1、数据的不可分割的最小单位是（C）。A．数据元素B．数据对象C．数据项D．数据串2、一个算法应该具有一些重要特性，下列不是算法特性的是（D）。A．有穷性B．确定性C．可行性D．健壮性E．至少一个输出3、下面关于线性表的表述中，（B）是错误的？A．若线性表采用顺序存储，必须占用一片连续的存储单元。B．若线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，占用的存储单元不一定是连续的。D．线性表采用链接存储，便于插入和删除操作。4、下列哪个不是链表所具有的特点是（A）。A．可随机访问表中元素B．插入、删除不需要移动元素C．线性链表必须有一个指针域D．所需空间与线性长度成正比[解析]链表是线性表的链式存储，是用结点来存储数据元素。线性表采用链表作为存储结构时，不能进行数据元素的随机访问，其优点是插入和删除操作不需要移动得分评卷人（A卷）第2页共8页元素。5、若线性表的长度为n，且采用顺序存储结构，则等概率删除其第i个元素的算法的时间复杂度为（D）(1=i=n)。A.O(i)B.O(n-i)C.O(1)D.O(n)6、静态链表中指针表示的是（B）。A．内存地址B．数组下标C．表头地址D．下一元素地址7、下列关于串的叙述中正确的是B。A．串中所含的字母个数称为串的长度B．串是一种特殊的线性表C．串中的字母不区分大小写D．由空格组成的串称为空串8、设有一个采用压缩存储的9阶对称矩阵A，以行序为主存储，第一个元素a11的存储地址为0，每个元素占一个地址空间，则a86的地址为（）。A.26B.27C.36D.37E.46F.479、判断一个带表头的循环链表H为空表的判定条件是（A）A.H＝＝NULLB.H-next==NULLC.H-next＝NULLD.H－next==H10、若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（B）。A.不确定的B.i-jC.j-i+1D.i-j-111、在一个单链表中,若q所指结点是p所指结点的前驱结点,若要删除p所指的结点,则执行(B)。A.q-next=pB.q-next=p-next;C.p=q-next;D.p-next=q-next;12、广义表A=(a,(b,c),(d,e),(f,g)),则Head(Tail(Head(Tail(Tail(A)))))式子的值为（C）。A.(f)B.fC.eD.(e)13、在一棵度为3的树中,度数为3的结点有2个,度数为2的结点有2个，则度为0的结点个数为(A)A．7B．8C．9D．1014、在下述结论中，正确的是（C）（A卷）第3页共8页①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④15、算术表达式a+b*（c+d/e）转为后缀表达式后为（A）A．abcde/+*+B．ab+cde/+*C．abcde/*++D．abcde*/++16、一个有n个结点的图，最多有（A）个连通分量。A．nB．n-1C．1D．017、若目标串的长度为n，模式串的长度为[n/4]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（D）A．O（nlogn）B．O（n/4）C．O（n）D．O（n2）18、设一组初始记录关键字序列(7，2，8,6，3，10,5)，以第一个关键字7为基准进行一趟快速排序的结果为（B）。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、向二叉搜索树中插入一个元素的时间复杂度是(B)。A．O(n）B．O(log2n)C．O(n*log2n)D．O(n+log2n)E.O(n2)F.O(n3)20、一个递归算法必须包括（C）。A.初始条件和递归部分B.初始条件和迭代部分C.终止条件和递归部分D.终止条件和迭代部分二、问答题（共10分）1、什么叫完全二叉树（4分），深度为K的，有N个结点的二叉树，当且仅当其每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应时，称之为完全二叉树。得分评卷人（A卷）第4页共8页2、简述顺序存储队列的假溢出的避免方法及队列满和空的条件。（6分）三、填空题（每空1分，共20分）1、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成__单链表__和__双链表_；而又根据指针的连接方式，链表又可分成________和________。得分评卷人（A卷）第5页共8页2、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有___________个和__________个。3、数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。4、循环队列的引入，目的是为了克服_______。5、串是一种特殊的线性表，其特殊性表现在_数据元素是一个字符_；串的两种最基本的存储方式是_顺序存储方式_、_链式存储方式_；两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同_。6、设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i][j]对应的B中存储位置为_______。7、二叉树中某结点的左子树深度减去右子树深度称为该结点的______________，平衡二叉树的结点的可能取值是______________。8、已知一个图如右图所示，若采用深度优先遍历该图，则遍历的序列为abcdegf。9、设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为__N0-1_；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。10、直接插入排序用监视哨的作用是缓冲作用。四、判断题（每小题1分，共10分）1、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。（）2、链表中的头结点仅起到标识的作用。()3、为了很方便的插入和删除数据，可以使用双向链表存放数据。()4、若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。（）5、完全二叉树一定是满二叉树，满二叉树不一定是完全二叉树。（）得分评卷人（A卷）第6页共8页6、线性表中的所有元素都有一个前驱元素和后继元素。（）7、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）8、若一个广义表的表头为空表，则此广义表亦为空表。（）9、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（）10、最小生成树的Kruskal算法是一种贪心法（Greedy）。（）五、程序填空题（每个空1分，共10分）1、下列算法的功能是比较两个链串的大小，其返回值为：101121212当当当ssssssintcomstr(LinkStrings1,LinkStrings2){//s1和s2为两个链串的头指针while(s1&&s2){if(s1－dates2－date)return－1；if(s1－dates2－date)return1；①；②；}if(③)return－1；if(④)return1；⑤；}2、如下为二分查找的非递归算法，试将其填写完整。IntBinsch(ElemTypeA[],intn,KeyTypeK){得分评卷人comstr(s1,s2)=请在空白处填入适当的内容。（A卷）第7页共8页intlow,high=0;①____________________;②____________________;while(low=high){intmid=③_______________________________；if(K==A[mid].key)returnmid;elseif(K[mid].key)④______________________________________;else⑤__________________________________;}return-1;//查找失败}六、算法设计题（20分）1、设计判断单链表中结点是否关于中心对称算法。（8分）得分评卷人（A卷）第8页共8页2、试编写一个求解Josephus问题的函数。用整数序列1,2,3,……,n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n=9,s=1,m=5，以及n=9,s=1,m=0，作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。（12分）