数据结构与算法分析 复习试卷A1
四川大学期末考试试题（闭卷）
（2009~2010学年第1学期）
课程号：311036030课程名称：数据结构与算法分析（A卷）任课教师：孙界平，张卫华
适用专业年级：软件工程2008级学号：姓名：
考试须知
四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。
四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。
题号一(40%) 二(8%) 三(42%) 四(10%) 卷面成绩得分
阅卷时间
注意事项：1. 请务必将本人所在学院、姓名、学号、任课教师姓名等信息准确填写在试题纸和添卷纸上；
2. 请将答案全部填写在本试题纸上；
3. 考试结束，请将试题纸、添卷纸和草稿纸一并交给监考老师。
一、单项选择题（本大题共20小题，每小题2分，共40分）提示：在每小题列
评阅教师得分
出的备选项中只有一个是符合题目要求的，请将其代码写到答题纸上。错选、多选或未选均
无分。
1. An algorithm must be or do all of the following EXCEPT:
a) correct
b) composed of concrete steps
*c) ambiguous
d) composed of a finite number of steps
e) terminate
2. For set P, the notation |P| indicates
*a) The number of elements in P.
b) The inverse of P.
c) The pow erset of P.
d) N one of the above.
3. Pick the growth rate that corresponds to the most efficient algorithm when n =
4.
a) 5n
b) 20 log n
c) 2n^2
*d) 2^n
4. When the upper and lower bounds for an algorithm are the same, we use:
a) big-Oh notation.
b) big-Omega notation.
*c) Theta notation.
d) asymptotic analysis.
e) Average case analysis.
f) Worst case analysis.
5. As compared to the linked list implementation for lists, the array-based list implementation requires:
a) More space
b) Less space
*c) More or less space depending on how many elements are in the list.
6. When comparing the doubly and singly linked list implementations, we find that the doubly linked list implementation
*a) Saves time on some operations at the expense of additional space.
b) Saves neither time nor space, but is easier to implement.
c) Saves neither time nor space, and is also harder to implement.
7. The correct traversal to use on a BST to visit the nodes in sorted order is:
a) Preorder traversal.
*b) Inorder traversal.
c) Postorder traversal.
8. When every node of a full binary tree stores a 4-byte data field, two 4-byte child pointers, and a 4-byte parent pointer, the overhead fraction is approximately:
a) one quarter.
b) one third.
c) one half.
d) two thirds.
*e) three quarters.
f) none of the above.
9. I f a node is at position r in the array implementation for a complete binary tree, then its right child is at:
a) (r - 1)/2 if r > 0
b) 2r + 1 if (2r + 1) < n
*c) 2r + 2 if (2r + 2) < n
d) r - 1 if r is even
e) r + 1 if r is odd.
10. The H uffman coding tree works best when the frequencies for letters are
a) Roughly the same for all letters.
*b) Skewed so that there is a great difference in relative frequencies for various letters.
11. A topological sort requires all of the following ex cept:
a) The graph be directed.
b) The graph contain no cycles.
*c) The graph contain w eights on the edges.
12. When sorting n records, Mergesort has worst-case cost:
a) O(log n).
b) O(n).
*c) O(n log n).
d) O(n^2)
e) O(n!)
f) N one of the above.
13. As compared to the time required to access one unit of data from main memory, accessing one unit of data from disk is:
a) 10 times faster.
b) 1000 times faster.
c) 1,000,000 time faster.
d) 10 times slower.
e) 1000 times slower.
*f) 1,000,000 times slower.
14. The basic unit of I/O when accessing a disk drive is:
a) A byte.
*b) A sector.
c) A cluster.
d) A track.
e) An extent.
15. The most time-consuming part of a random access to disk is usually:
*a) The seek.
b) The rotational delay.
c) The time for the data to move under the I/O head.
16. Which is generally more ex pensive?
a) A successful search.
*b) An unsuccessful search.
17. The 80/20 rule indicates that:
a) 80% of searches in typical databases are successful and 20% are not.
*b) 80% of the searches in typical databases are to 20% of the records.
c) 80% of records in typical databases are of value, 20% are not.
18. Hashing is most appropriate for:
a) I n-memory applications.
b) Disk-based applications.
*c) Either in-memory or disk-based applications.
19. The primary key is:
*a) A unique identifier for a record.
b) The main search key used by users of the database.
c) The first key in the index.
20. Depth-first search is best implemented using:
*a) A stack or recursion.
b) A queue.
c) A tree.
二、判断题（本大题共8小题，每小题1分，共8分）提示：正确答T ，错误答F ，
将其结果写到答题纸上。
T 1. There is TWO queues needed to implement the priority queue. One queue is used for actual storing of data and another for storing priorities.
T 2. A binary tree is a tree in which each node have 2 child except leaf node. F 3. When sorting n records, Quicksort has worst-case cost O(n log n). T 4. Depth-first search is best implemented using stack or recursion. T 5. We say two vertices are connected if there is a path connect them.
F 6. Consider a node in an AVL tree, the height of left sub-tree minus height of right sub-tree can only be -1 or 1. T 7. Build a hash table of set {23,44,36,48,52,73,64,58}, h(K)=K%13, then the address of element 64 is 12 F 8. The Huffman coding tree works best when the frequencies for letters are roughly the same for all letters.
三、问答题（本大题共6小题，每小题7分，共42分）。
1. Determine (in a "Big-O" sense) the order of the following method as a function of the parameter n.
A) x=0;
for(i=1;i for(i=0;i for(j=0;j<=n;j++) { c[i][j]=0; for(k=0;k A) O(n 2) B) O(n 3) 2. Suppose a binary-tree, the pre-order sequence of this binary-tree is EBADCFHGIKJ , and the in-order sequence of it is ABCDEFGHIJK, please write down the post-order sequence of this binary-tree. ACDBGJKIH FE 3. Build the Huffman coding tree for the following set of w eights (5，9，11，2，7，16) 答案 评阅教师 得分 评阅教师 得分 4. Draw A VL of the following sequence 16, 3, 7, 11, 9, 26, 18, 14, 15 答案： 5. Write down the DFS and BFS sequence of graph below: (Attention: while traversing, choose vertex from numeric sequence w hen more than one vertex can be chosen) 深度优先搜索序列：0,1,2,8,3,4,5,6,7,9 广度优先搜索序列：0,1,4,2,7,3,8,6,5,9 6 Give out the topologic sort result of the graph below , using BFS. (Attention! w hile traversing, choose vertex from numeric sequence w hen more than one vertex can be chosen) 1 6 5 9 4 8 3 7 2 50 9 20 30 11 16 14 7 7 2 5 答案： C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7 四、编程、设计及分析题（本大题共1小题，共10分）。提示：题目给出了一个程 序设计要求，请按照要求写出源程序代码，如果源程序代码中出现语法错误或逻辑错误，则酌情扣分。 Write a recursive function that returns the height of a binary tree. 答案 template int height(BinNode if (subroot == NULL) return 0; // Empty subtree return 1 + max(height(subroot->left()), height(subroot->right())); 评阅教师 得分 《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 小学一年级数学下册期中试卷分析 本试卷从基础知识、能力测试方面对学生的知识和能力进行较全面的检测，试卷与教材密切取系，关注学习的生活实际。题量、难易适中，覆盖面较广。本试卷共四道大题，都是对基础知识的运用。 一、成绩分析: 一年级班参加考试的有22人，平均分是90分，及格率为100%，优秀率为77%。 二、试卷题目难易分析： 试卷难易程度总体适中，基础题考核面全，呈现的基础性强，后半部分能力题，拉开了层次，有适当的提高。 三、答题情况分析： 第一题，我会填。共有7个小题，包括100以内数的认识和组成，数序，数的大小的比较几个知识点，第2题和第7小题上出现错误，主要原因是读题和审题能力不强，特别是第7小题，学生由于对一个数的前后不理解，就出现错误。因此在今后的教学中要培养学生读题和审题这方面的能力训练。 第二题。我会算是计算题，出现错误最多的是有关人民币的计算。学生对人民币的单位的换算这个知识点的掌握情况都有不同程度。 第三题。我会辩，对多一些，少一些，题目理解不够，在以后的教学中还需加强练习。 第四题。用数学解决实际问题，主要是考核学生对数学的理解能力和解决问题的应用能力，学生在这部分失分比较多，主要有：①学 生的思维不够开阔，不会用所学的知识举一反三，或是老师的读题对学生有误导，不会灵活解决问题。②应用题的审题能力差，不理解数量间的关系。失分最严重的就是最后一题,由于学生的分析问题的能力不强,不能很好的理解题意,所以在教学中要加强审题训练。 四、从本次考试的难易程度和所取得的成绩来看，个别小朋友有所落后。存在不足之处： 1．个别学生的字迹较潦草，书写不认真，要培养小朋友认真书写的习惯。 2．学生的听读能力和审题能力还需要进一步加强，有些题目学生会做，但是没有听懂意思，有些学生对试卷的题目要求不明确，不理解题目意思。在以后的练习中我们会加强学生对题意理解的训练以及题型的多样性练习。 3．学生的基础知识掌握不够牢固，加减法计算还要进一步加强训练，必须提高学生的计算速度，保证百分之百的的正确率。 4．学生对所学知识的灵活运用程度还很不够，在以后的练习当中我们会多让学生自己探索和思考问题，培养学生能够把一个知识点运用到各种题型当中去的能力。 5、培养学生养成良好的学习习惯，要求学生把字写工整、清晰，做题时认真细致、静下心来做题目，学会理解题意，学会检查。 6、重视考后反思，师生共同分析试题。 教师和学生要通过考后的试卷分析，教师反思教学存在的问题，学生反思自己在知识、方法和发挥上存在的不足，以便查漏补缺提高教和 数据分析基础测试题含答案 一、选择题 1．已知一组数据a，b，c的平均数为5，方差为4，那么数据a﹣2，b﹣2，c﹣2的平均数和方差分别是.（） A．3，2 B．3，4 C．5，2 D．5，4 【答案】B 【解析】 试题分析：平均数为（a?2 + b?2 + c?2 ）=（3×5-6）=3；原来的方差： ；新的方差： ，故选 B. 考点：平均数；方差. 2．甲、乙、丙三个不同品种的苹果树在同一地区进行对比试验，从每个品种的苹果树中随机各抽取10棵，对它们的产量进行统计，绘制统计表如下： 品种甲乙丙 平均产量/(千克/棵)9090 方差10.224.88.5 若从这三个品种中选择一个在该地区推广，则应选择的品种是() A．甲B．乙C．丙D．甲、乙中任选一个【答案】A 【解析】 【分析】 根据平均数、方差等数据的进行判断即可． 【详解】 根据平均数、方差等数据的比较可以得出甲品种更适在该地区推广． 故选：A 【点睛】 本题考查了平均数、方差，掌握平均数、方差的定义是解题的关键． 3．某射击俱乐部将11名成员在某次射击训练中取得的成绩制成如图所示的条形统计图，由图可知，11名成员射击成绩的众数和中位数分别是（） A．8，9 B．8，8 C．8，10 D．9，8 【答案】B 【解析】 分析：中位数，因图中是按从小到大的顺序排列的，所以只要找出最中间的一个数（或最中间的两个数）即可，本题是最中间的那个数；对于众数可由条形统计图中出现频数最大或条形最高的数据写出． 详解：由条形统计图知8环的人数最多， 所以众数为8环， 由于共有11个数据， 所以中位数为第6个数据，即中位数为8环， 故选B． 点睛：本题主要考查了确定一组数据的中位数和众数的能力．注意找中位数的时候一定要先排好顺序，然后再根据奇数和偶数个来确定中位数，如果数据有奇数个，则正中间的数字即为所求．如果是偶数个，则找中间两个数的平均数． 4．已知一组数据a、b、c的平均数为5，方差为4，那么数据a+2、b+2、c+2的平均数和方差分别为（） A．7，6 B．7，4 C．5，4 D．以上都不对 【答案】B 【解析】 【分析】 根据数据a，b，c的平均数为5可知a+b+c=5×3，据此可得出1 3 （-2+b-2+c-2）的值；再由 方差为4可得出数据a-2，b-2，c-2的方差． 【详解】 解：∵数据a，b，c的平均数为5，∴a+b+c=5×3=15， ∴1 3 （a-2+b-2+c-2）=3， ∴数据a-2，b-2，c-2的平均数是3；∵数据a，b，c的方差为4， ∴1 3 [（a-5）2+（b-5）2+（c-5）2]=4， 数据结构复习题 第一章概论 一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。 习题9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n个数据放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL要比有序表的ASL小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图所示)，如果用二次探测再散列处理冲突，关键字为49的记录的存储地址是( )。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 A ．8 B. 3 C ．5 D. 9 答：D (计算H(k)，即H(49)=49 mod 11 = 5,冲突，进行二次探测再散列。而二次探测再散列的增量序列为：d i =12，-12，22，-22，32，…，土k 2，(k ≤m/2), 沿着增量序列选择不同的增量按照开放定址公式： H i ＝( H(key)+d i ) MOD m i ＝1，2，…，k (k ≤m-1) 2012-2013年第一学期期中考试试卷分析 刘婷婷 一、命题范围及特点： 1 、命题范围：新外研版七年级英语预备级M1-M4及M1—M3共7个模块的内容，主要包含英语中简单的交际用语如：向别人介绍自己及家人，介绍自己的好爱及了解其他人的爱好，介绍学校等。 2、命题特点： （1）依据考试纲要命题 本次检测试题以教学大纲和教材为依据，重点考查学生语言基础知识及基本技能，同时进一步加大了对英语的运用能力的考查力度。增加了试题的灵活性、开放性、探究性及综合性。 （2）立足基础知识和基本技能的考查，突出交际，强调运用 本次英语命题体现了《英语课程标准》的精神，正确处理了课内学习向课外延伸的关系。试题的整体设计力求加强对基础知识的考查。基础知识中的大部分内容不再是单纯知识性的，而是将知识置于特定的语境中。知识难度较小，但灵活性强。在此基础上侧重考查学生综合运用语言的能力，对语言材料的整体感知能力和捕捉信息的能力。命题材料结合了课本内容与课外知识，尽量挖掘课本的命题价值，但适当高于课本，让学生看到试题既有亲切感又不乏新鲜感。题量设计恰当，考试期间调查，中等水平的学生能在规定时间内完成试卷。整体看，各部分结构基本合理。 二、试卷分析 （一）成绩统计如下： 参加考试人数为329人，100分以上的为67人，占总人数的20.4%。90分以上的为151人，占总人数的45.9%。不及格的有105人，占总人数的32%。从分数段来看，各班集中在90-99的学生占的比重要大，其次为100-109的分数段，优秀率为20.4％，及格率仅为68.4％。这份试卷反映了学生对基础知识的掌握以及个人综合能力情况，也暴露出学生平时学习的问题，为今后教学工作奠定了基础。 （二）存在的问题 1、听力部分：共20分，试题难度适中，属中等偏易，大部分都在14-15分以上。对于基础较好的学生来说，此套听力题略显简单，但得满分的同学并不说是很多，往往是在听力的第一个题 数据分析期末试题及答案 一、人口现状.sav数据中是1992年亚洲各国家和地区平均寿命(y)、按购买力计算的人均GDP(x1)、成人识字率(x2)，一岁儿童疫苗接种率(x3)的数据，试用多元回归分析的方法分析各国家和地区平均寿命与人均GDP、成人识字率、一岁儿童疫苗接种率的关系。(25分) 解： 1.通过分别绘制地区平均寿命(y)、按购买力计算的人均GDP(x1)、成人识字率(x2)，一岁儿童疫苗接种率(x3)之间散点图初步分析他们之间的关系 上图是以人均GDP(x1)为横轴，地区平均寿命(y)为纵轴的散点图，由图可知，他们之间没有呈线性关系。尝试多种模型后采用曲线估计，得出 表示地区平均寿命(y)与人均GDP(x1)的对数有线性关系 上图是以成人识字率(x2)为横轴，地区平均寿命(y)为纵轴的散点图，由图可知，他们之间基本呈正线性关系。 上图是以疫苗接种率(x3)为横轴，地区平均寿命(y)为纵轴的散点图，由图可知，他们之间没有呈线性关系 。 x）为横轴，地区平均寿命(y)为纵轴的散点图，上图是以疫苗接种率(x3)的三次方（3 3 由图可知，他们之间呈正线性关系 所以可以采用如下的线性回归方法分析。 2.线性回归 先用强行进入的方式建立如下线性方程 设Y=β0+β1*（Xi1）+β2*Xi2+β3* X+εi i=1.2 (24) 3i 其中εi（i=1.2……22）相互独立，都服从正态分布N（0，σ^2）且假设其等于方差 R值为0.952，大于0.8，表示两变量间有较强的线性关系。且表示平均寿命(y)的95.2%的信息能由人均GDP(x1)、成人识字率(x2)，一岁儿童疫苗接种率(x3)一起表示出来。 建立总体性的假设检验 提出假设检验H0：β1=β2=β3=0，H1,：其中至少有一个非零 得如下方差分析表 上表是方差分析SAS输出结果。由表知，采用的是F分布，F=58.190，对应的检验概率P值是0.000.，小于显著性水平0.05，拒绝原假设，表示总体性假设检验通过了，平均寿命(y)与人均GDP(x1)、成人识字率(x2)，一岁儿童疫苗接种率(x3)之间有高度显著的的线性回归关系。 习 9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图 《数据结构与算法》（c语言版）期末考复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 五年级下册语文半期试卷分析 一、总的情况 （一）数据分析 本次期中考试五年级共330人参考，年级平均分85.41分，优生率为43.94%，良好率为96.49%，及格率为98.79%。年级平均分82.89、优生率等指标均较上期末有所提高。 （二）总体情况 这次五年级语文半期试卷分为三大块，总分为100分。分“积累运用”（占总分的46%。包括看拼音写词语，选择多音字的正确读音，再用另一个读音组词，按查字典的知识填空，补充成语并选两词写一段话，按一定规律排序，积累与运用）；“阅读理解”（占总成绩21%。一篇来自课内、一篇来自课外）；“习作表达”（占总成绩30%）这几类。此次的测试题型比较丰富，内容注重书本基础知识的练习，重视考查字音、句式，课文重点片段的积累及运用；同时也检测学生的阅读理解和习作表达能力。 从本次测试来看，题量很大。学生总体情况较好，主要失分的原因是审题不清，课外知识积累不够。下面是具体的分析和思考。 二、典型错题分析 积累运用 （一）看拼音写词语 这个题大多的学生都能够拿到满分，另20%学生的错误比较多，重点错在“涩、祭奠、傻、吟。” （二）给下面带点字的另一种读音组词。 1、一部分学生答题抓住了“读音”，把带点词的读音写出来或者写出了另外一种读音； 2、有些学生虽然抓住了“组词”，但是却用了带点字的读音去组。 （三）我会按查字典的知识填空 1、首先学生对“卸”的解释理解不够，选解释有很多错误。 2、“凹”字是（）结构的字，用部首查字法，先查（）部，在 （）画里找，它的第二画是（）。 这个题错得很多，这三个空都错很多。 （五）按要求写句子 2、这本书太有价值了，你必须看。（改为双重否定句） 典型错误： 数据分析专项训练及解析答案 一、选择题 1．分析题中数据，将15名运动员的成绩按从小到大的顺序依次排列，处在中间位置的一个数即为运动员跳高成绩的中位数； 2．对于一组统计数据：1，1，4，1，3，下列说法中错误的是（） A．中位数是1 B．众数是1 C．平均数是1.5 D．方差是1.6 【答案】C 【解析】 【分析】 将数据从小到大排列，再根据中位数、众数、平均数及方差的定义依次计算可得答案．【详解】 解：将数据重新排列为：1、1、1、3、4， 则这组数据的中位数1，A选项正确； 众数是1，B选项正确； 平均数为11134 5 ++++ ＝2，C选项错误； 方差为1 5 ×[（1﹣2）2×3+（3﹣2）2+（4﹣2）2]＝1.6，D选项正确； 故选：C． 【点睛】 本题主要考查中位数、众数、平均数及方差，解题的关键是掌握中位数、众数、平均数及方差的定义与计算公式． 3．有甲、乙两种糖果，原价分别为每千克a元和b元．根据调查，将两种糖果按甲种糖果x千克与乙种糖果y千克的比例混合，取得了较好的销售效果．现在糖果价格有了调整：甲种糖果单价下降15%，乙种糖果单价上涨20%，但按原比例混合的糖果单价恰好不 变，则x y 等于（） A．3 4 a b B． 4 3 a b C． 3 4 b a D． 4 3 b a 【答案】D 【解析】 【分析】 根据已知条件表示出价格变化前后两种糖果的平均价格，进而得出等式求出即可．【详解】 解：∵甲、乙两种糖果，原价分别为每千克a元和b元， 两种糖果按甲种糖果x千克与乙种糖果y千克的比例混合， ∴两种糖果的平均价格为：ax by x y + + ， ∵甲种糖果单价下降15%，乙种糖果单价上涨20%， ∴两种糖果的平均价格为： 1520 (1)(1) 100100 a x b y x y -?++ + ， ∵按原比例混合的糖果单价恰好不变， ∴ax by x y + + ＝ 1520 (1)(1) 100100 a x b y x y -?++ + ， 整理，得15ax＝20by ∴ 4 3 x b y a =， 故选：D． 【点睛】 本题考查了加权平均数，解决本题的关键是表示出价格变化前后两种糖果的平均价格．4．某青年排球队12名队员的年龄情况如下： 则12名队员的年龄（） A．众数是20岁，中位数是19岁B．众数是19岁，中位数是19岁 C．众数是19岁，中位数是20.5岁D．众数是19岁，中位数是20岁 【答案】D 【解析】 【分析】 中位数是指将统计总体当中的各个变量值按大小顺序排列起来，形成一个数列，处于变量数列中间位置的变量值就称为中位数；众数是指在统计分布上具有明显集中趋势点的数值，代表数据的一般水平（众数可以不存在或多于一个）． 【详解】 解：在这一组数据中19岁是出现次数最多的，故众数是19岁；将这组数据从小到大的顺序排列后，处于中间位置的数是20岁，那么由中位数的定义可知，这组数据中的中位数是20岁．故选：D. 【点睛】 理解中位数和众数的定义是解题的关键． 复习题集─参考答案 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续存空间时，为提高存利用率，减少溢出机会，应把两个栈的栈底分别设在这片存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据] （×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] （√）28.树形结构中每个结点至多有一个前驱。 （×）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。 （×）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。 （×）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。 （×）32.顺序查找方法只能在顺序存储结构上进行。 （×）33.折半查找可以在有序的双向链表上进行。 浅谈试卷评讲 ——初三3、12班半期试题评析 文淑芬 一、分析目的：通过试题本身和学生考试结果的分析，找出教师教学生学中存在问题；便于提升。 二、试题分析 试题难易度 1、除听力第三节第一篇短文，任务型阅读，和短文填空3个题与中考偏差大外，其余题与中考题难易度持平，听力的第一篇短文（6分），内容偏难；任务型阅读的6分，问题设置过难；而短文填空的16分过于简单，一是提供了首字母，再有就是篇幅过短，整篇短文词数只有80词，中考这个题的词数一般在280个左右。而同学们实际做得差是心理因素（压根就怕这种题） 2、整套试题的难度分值比例符合中考要求。即：基础题、中等题、难度题的比例按 7 : 2 : 1 考试结果 1、从总分看最高分3班136分12班130分，120分以上3班12人，12班8人，及格3班25人，12班15人，最低分3班28分，12班27分，学生考试成绩相差大的12班有赵炳灿，卢琳珺，王媛媛，陈坤、韩雨欣未达到应有的分数，罗德伟又超过了应有水平，3班文宇航，廖小雨，黄钦宇钟治民没达到相应水平，而张杰超过实际水平 2、从各题得分情况：见附表一、二。 三、试题评讲设计的步骤及目的 1、自改试题 2、小组讨论彼此试卷中的错误或疑问，记下不能解决的错误或疑问 3、提出不能解决的错误或疑问 4、答疑（简单的学生答，难点教师指导学生解答） 5、针对性练习（预设） ( )1. Our teacher told us that light _____ much faster than sound. A. traveled B. travels C. is traveling D. was traveling ( )2.He has made his baby _______ . It’s quiet now. A. stop crying B. stop to cry C. stops to cry D. to stop crying ( )3. -_______ you _______ your bag yet? -Yes, I _______ it yesterday. A. Did, find, found B. Have found, have found C. Will, find; find D. Have found; found ( )4.—David has made great progress recently. —_____, and _____. A. So he has; so you have B. So he has; so have you C. So has he; so have you D. So has he; so you have ( )5. Sanya is a beautiful city . I _____there twice . A 、have gone B、have been C、have gone to D、have been to （专题精选）初中数学数据分析真题汇编及答案 一、选择题 1．校团委组织开展“医助武汉捐款”活动，小慧所在的九年级(1)班共40名同学进行了捐款，已知该班同学捐款的平均金额为10元，二小慧捐款11元，下列说法错误的是( ) A．10元是该班同学捐款金额的平均水平B．班上比小慧捐款金额多的人数可能超过20人 C．班上捐款金额的中位数一定是10元D．班上捐款金额数据的众数不一定是10元【答案】C 【解析】 【分析】 根据平均数，中位数及众数的定义依次判断. 【详解】 ∵该班同学捐款的平均金额为10元， ∴10元是该班同学捐款金额的平均水平，故A正确； ∵九年级(1)班共40名同学进行了捐款，捐款的平均金额为10元， ∴班上比小慧捐款金额多的人数可能超过20人，故B正确； 班上捐款金额的中位数不一定是10元，故C错误； 班上捐款金额数据的众数不一定是10元，故D正确， 故选：C. 【点睛】 此题考查数据统计中的平均数，中位数及众数的定义，正确理解定义是解题的关键. 2．已知一组数据a、b、c的平均数为5，方差为4，那么数据a+2、b+2、c+2的平均数和方差分别为（） A．7，6 B．7，4 C．5，4 D．以上都不对 【答案】B 【解析】 【分析】 根据数据a，b，c的平均数为5可知a+b+c=5×3，据此可得出1 3 （-2+b-2+c-2）的值；再由 方差为4可得出数据a-2，b-2，c-2的方差． 【详解】 解：∵数据a，b，c的平均数为5，∴a+b+c=5×3=15， ∴1 3 （a-2+b-2+c-2）=3， ∴数据a-2，b-2，c-2的平均数是3；∵数据a，b，c的方差为4， ∴1 3 [（a-5）2+（b-5）2+（c-5）2]=4， 单选题（每题2 分，共20分） 1.对一个算法的评价，不包括如下（B ）方面的容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 6.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的存储中，每个单链表中的结点都具有相同的（A ）。 A．行号B．列号C．元素值D．非零元素个数 10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为(C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题6 分，共24分） 1.数据结构是指数据及其相互之间的_联系。当结点之间存在M对N（M：N）的联系时，称这种结构为 __图__。 2.队列的插入操作是在队列的___尾_进行，删除操作是在队列的_首_进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为___ O（1）__，在表尾 插入元素的时间复杂度为___ O（n）___。 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ， 则二维数组W的数据元素共占用＿128__个字节。W中第6 行的元素和第4 列的元素共占用__44_个字节。 若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址__108_。 7.二叉树是指度为2的___有序___树。一棵结点数为N的二叉树，其所有结点的度的总和是 ___n-1____。 8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个_有序序列__。对一棵由算术表达式组 成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__后缀表达式____。 9.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中 _______________个用于指向孩子，_________________个指针是空闲的。 10.若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0 的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________。 11.在线性表的散列存储中，处理冲突的常用方法有________________________和 _____________________________两种。 最新初中数学数据分析经典测试题附答案 一、选择题 1．已知一组数据a，b，c的平均数为5，方差为4，那么数据a﹣2，b﹣2，c﹣2的平均数和方差分别是.（） A．3，2 B．3，4 C．5，2 D．5，4 【答案】B 【解析】 试题分析：平均数为（a?2 + b?2 + c?2 ）=（3×5-6）=3；原来的方差： ；新的方差： ，故选 B. 考点：平均数；方差. 2．已知一组数据a、b、c的平均数为5，方差为4，那么数据a+2、b+2、c+2的平均数和方差分别为（） A．7，6 B．7，4 C．5，4 D．以上都不对 【答案】B 【解析】 【分析】 根据数据a，b，c的平均数为5可知a+b+c=5×3，据此可得出1 3 （-2+b-2+c-2）的值；再由 方差为4可得出数据a-2，b-2，c-2的方差． 【详解】 解：∵数据a，b，c的平均数为5，∴a+b+c=5×3=15， ∴1 3 （a-2+b-2+c-2）=3， ∴数据a-2，b-2，c-2的平均数是3；∵数据a，b，c的方差为4， ∴1 3 [（a-5）2+（b-5）2+（c-5）2]=4， ∴a-2，b-2，c-2的方差=1 3 [（a-2-3）2+（b-2-3）2+（c--2-3）2] = 1 3 [（a-5）2+（b-5）2+（c-5）2]=4， 故选B．【点睛】 本题考查了平均数、方差，熟练掌握平均数以及方差的计算公式是解题的关键. 3．对于一组统计数据：1，1，4，1，3，下列说法中错误的是（） A．中位数是1 B．众数是1 C．平均数是1.5 D．方差是1.6 【答案】C 【解析】 【分析】 将数据从小到大排列，再根据中位数、众数、平均数及方差的定义依次计算可得答案．【详解】 解：将数据重新排列为：1、1、1、3、4， 则这组数据的中位数1，A选项正确； 众数是1，B选项正确； 平均数为11134 5 ++++ ＝2，C选项错误； 方差为1 5 ×[（1﹣2）2×3+（3﹣2）2+（4﹣2）2]＝1.6，D选项正确； 故选：C． 【点睛】 本题主要考查中位数、众数、平均数及方差，解题的关键是掌握中位数、众数、平均数及方差的定义与计算公式． 4．2022年将在北京﹣﹣张家口举办冬季奥运会，很多学校为此开设了相关的课程，下表记录了某校4名同学短道速滑成绩的平均数x和方差S2，根据表中数据，要选一名成绩好又发挥稳定的运动员参加比赛，应选择（） A．队员1 B．队员2 C．队员3 D．队员4 【答案】B 【解析】 【分析】 根据方差的意义先比较出4名同学短道速滑成绩的稳定性，再根据平均数的意义即可求出答案． 《数据结构与算法》复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑 B．存储 C．逻辑和存储 D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何 B．结点个数的多少 C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是 O(n2) 。 s =0; for( I =0; i for(j=0;j 语文四年级试卷分析 一、命题目的、范围及特点 通过四年级的语文试卷，我们不难看出这份试卷命题坚持力求体现新课标精神，拓宽语文教学领域，打通课内外学习语文的渠道，检查学生掌握语文基础知识的能力及课内外阅读能力。试卷力求通过一些开放性的试题，答案多元的试题，引导学生设计出自己理想的答案，培养学生创新能力。试卷还力求体现人文性、趣味性和灵活性，打破旧的命题模式。同时整份试卷还体现了“三重”，即重基础（基础知识和基本技能），重能力（识字能力、写字能力、阅读能力、写作能力和积累运用能力），重创新（运用所学知识创造性地解决问题）。 二、学生答题情况 本次语文考试本班共44名学生，全班平均分87。本次测试，学生对汉语拼音、生字掌握较牢，基础较好，尤其是生字词扣分较少,看来这段时间的强化复习收效不错。对凡是要求背诵的课文，基本掌握。成语和句子都能较好的掌握，学生都已经掌握了这种题的答题方法，基本上很少丢分。 三、试卷分析 这份试题做到全、新、活，符合学生的知识水平，认知规律和心理特征。在考查“双基”的基础上求提高、求发展。以适应新课标提出的“学生的全面发展和终身学习”的总目标。纵观这次质量检测，可以看出还存在许多问题。 （1）词语积累不够。 重视积累，就等于给了学生一把学好语文的金钥匙，语文教学效率就会迅速提高。学生平时缺乏大量的阅读、积累、欣赏、感悟，遇到一些较灵活的题，就感到束手无策。本次检测中“填填成语“老马（）（）”很多学生填不出来。平时积累了不少的成语，但是到了关键时刻，却想不出来，源于练习太少，学生无法得心应手地运用起来。 （2）语言训练缺少 本次试卷失分较多的地方是修改病句以及缩句。缩句，庙门前的石头身子很威武很镇静地蹲着。其实很简单：石头狮子蹲着。但是学生对于缩句掌握得不好，几乎每个学生都做错了。 （3）综合能力薄弱 由于学生平时学的知识较规范，缺乏对知识整合的处理，故失分较多。本次考查的内容不仅涉及拼音、词义、逻辑思维训练，还考查学生对短文内容准确理解能力及平时积累词语的能力。由于在教学中注重教材的系统讲解，引导学生对知识的归类、整理及对新旧知识前后渗透的训练相对少些，导致学生对综合性较强试题缺乏独立分析能力，失分较多。有的学生做题时不细心，不读题乱写一气，有的没能真正领会句子含义，更缺乏理解的深度，尤其体现在第二篇的课外阅读《飞翔的蜘蛛》。这篇短文题型较多，判断题，写感受，以及课外词语的运用等，多方面考核学生。判断题都是简单的，没有失分。第1小题是为什么带引号，学生没有深入思考，理解出现片面性，失分较多。数据结构与算法C语言版期末复习题
小学一年级数学下册期中试卷分析
数据分析基础测试题含答案
数据结构与算法复习题库含答案
数据结构与算法复习题10(C语言版)
期中考试试卷分析
数据分析期末试题及答案
数据结构与算法复习题10(C语言版)
数据结构(c语言版)期末考试复习试题
五年级下册语文半期试卷分析-
数据分析专项训练及解析答案
数据结构与算法复习题及参考答案
初三英语半期考试试卷分析
(专题精选)初中数学数据分析真题汇编及答案
数据结构与算法分析—期末复习题及答案
最新初中数学数据分析经典测试题附答案
数据结构与算法期末考试复习试题
四年级期中考试试卷分析