数据结构试题-考研精选-医药卫生.docxVIP

数据结构试题-考研精选-医药卫生 部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我 （1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材 （2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为*****,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题 （3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6 （4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足 ki=k2i ki=k2i+1 （5）试卷1第一套填空题第9题模式匹配的BF算法以书中答案为准，两者区别在于，教材中存储字符串的数组的0号单元不存放有效字符，而试卷答案认为0号单元也放数组 （6）试卷1第二套填空题第7题给定初始序列建堆未声明建大顶堆还是小顶堆，答案中给出的是小顶堆，大顶堆也要会建 （7）试卷1第二套应用题第1题第4趟直接插入排序的结果应为(22，40，45，48，80，78)；答案中给出的实际为第三趟，关键在于首元素自身有序不算一趟 （8）试卷1第二套填空题第2题入栈操作以教材为准，教材中top是指向的栈顶(第一个空位置)的指针，与该套试卷中栈顶结构不一样，以教材为准 （9）试卷1第三套填空题第12题答案中给出的不是拓扑序列，正确的是1423 （10）试卷1中多处遇到空指针NULL时写的是0而非NULL，实际两者皆可 （11）试卷1第4套填空题第2题双向链表的删除答案错，应为p―llink-rlink=p-rlink; p-rlink-llink=p-llink;此外，注意课堂中讲的指针名和操作方法 （12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。 （13）第5套选择第8题答案应为A:设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为 (A) abedfc (14)第5套应用题第3题题目未指明查找方法，没法作 （15）第6套选择第5题应选B，实际是任意结点至多只有一个孩子：设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B) 高度等于其结点数 （16）第7套填空1题问题本身错，设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s-left_____=p；s-right=p-right；___p-right_______=s； s-right-left=s；（设结点中的两个指针域分别为left和right）。 （17）第8套填空题第8题答案错 （18）第7套选择第3题题目错，应以60为基准关键字，答案为C．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（ ）。 (C) 42，40，55，60，80，85 （17）第6套填空9题．快速排序算法的空间复杂度平均情况下为_O(logn)_，最坏的情况下为_O(n)_。 (18)第9套填空第3题，题目说循环队列有m个元素实际指循环队列总长为m，此外，该题关于队头和队尾指针的约定不同于教材 （19）第9套填空第4题答案错，9个元素冒泡排序，第一趟比较次数为8，最多8趟 数据结构试卷（一） 1．组成数据的基本单位是（C ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={1，2，2，3，3，4，4，1}，则数据结构A是（ C ）。 (A) 线性结构 (B) 树型结构 (C) 图型结构 (D) 集合 3．数组的逻辑结构不同于下列（D ）的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 (D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（B ）个。 (A) 2i (B) 2i (C) 2i-1 (D) 2i