数组习题课
- 格式:ppt
- 大小:408.50 KB
- 文档页数:21
习题五--数组⼀、A类程序设计题1、求⼀个4x4矩阵对⾓线元素之和。
2、⽤数组的⽅法求Fibonacci数列的值(要求输出前20个数)。
3、将⼀个3x4矩阵转置(⾏列互换)存放。
4、将⼀个数组中的数按逆序存放,例如原来的顺序为8,7,6,4,2,要求改为2,4,6,7,8。
5、⽤选择法对10个整数进⾏降序排序。
6、⽤冒泡法对10个整数进⾏升序排序。
7、编写⼀个简单程序,要求:(1)从键盘上输⼊8个整数放⼊数组a[8]中(⽤for循环实现);(2)求出数组元素的最⼤值及数组的平均值。
8、求3×4矩阵中每⼀列元素的最⼤值并输出。
9、求4×4矩阵中每⼀⾏元素的最⼩值并输出。
10、某班有30个学⽣,进⾏了数学考试,编写程序将考试成绩输⼊⼀维数组,并求数学的平均成绩及不及格学⽣的⼈数。
11、有⼀个3x4矩阵,求出最⼤元素,以及其所在的⾏号和列号。
12、从键盘上输⼊10个实数,然后按输⼊顺序的逆序输出这10个数。
13、从键盘输⼊10个整数,找出其中最⼤值和最⼩值。
14、输⼊10个学⽣的姓名、学号和成绩,将其中不及格者的姓名、学号和成绩输出。
15、输⼊字符串 s,统计出 s 中共出现了多少个数字字符。
⼆、B类程序设计题1、对⼀个已按由⼩到⼤排好顺序的整型数组,若从键盘输⼊⼀个数x,现要查询该数是否在此整型数组中,若存在则删除该数,否则显⽰“不存在”信息。
2、对⼀个已按由⼩到⼤排好顺序的整型数组,若从键盘输⼊⼀个数x,现要将该数插⼊到该数组中,使其插⼊后整个数组排序规律不变。
3、编写⼀程序,要求从键盘上输⼊10个整数放⼊⼀个数组中(⽤for循环实现),并编写求最⼤值的函数max,在主程序调⽤这个函数实现输出数组中10个整数的最⼤值,要求⽤数组名作为函数参数。
4、输⼊⼀个4⾏4列的⼆维数组,编程实现:(1) 求出其中的最⼤值和最⼩值及其对应的⾏列位置;(2) 求出对⾓线上各元素之和。
5、⽤筛选法求100之内的素数。
第一章一、填空题:1.数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。
2.从逻辑上可以把数据结构分为线性结构和非线性结构。
3.线性结构的顺序存储结构是一种随机存取的存储结构,线性结构的链式存储是一种顺序存取的存储结构。
4.线性结构中元素的关系是一对一,树形结构中元素的关系是一对多,图形结构中元素的关系是多对多。
5算法的5个重要特征是有穷性、确定性、可行性、输入、输出。
6 算法分析的两个主要方面是:时间复杂度和空间复杂度二、判断题:1、顺序存储方式只能用于线性结构、不能用于非线性结构。
×2、基于某种逻辑结构之上的运算,其实现是唯一的。
×3、数据元素是数据的最小单位。
×4、数据结构是带有结构的数据元素的集合。
√5、算法分析的目的是研究算法中的输入和输出的关系×三、分析以下程序段的时间复杂度:5.(1)i=1;k=100while(i<n){K=k+1;i+=10;}(2)i=1;j=0;while(i+j<=n)if(i>j) j++;else i++;(3)x=n;y=0;while(x>=(y+1)*(y+1))y++;(4)x=91;y=100;while(y>0)if(x>100){x-=10;y--}else x++;(5)for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+y;(1)O(n)(2)O(n)(3)O(n1/2)(4)O(1)(5)O(n3)第二章一、选择题:1.带头结点的单链表head为空的判断条件是(B)A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL2. 若在线性表中做以下两个操作:(1)在最后一个元素之后插入一个元素(2)删除第一个元素在(D)存储方式最节省时间:A. 单链表B. 单循环链表C. 双向链表D. 带尾指针的单循环链表3. 若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素算法的时间复杂度为(C)。
1.用二分(对半)查找表的元素的速度比用顺序法( )A.必然快 B. 必然慢 C. 相等 D. 不能确定2.具有12个关键字的有序表,折半查找的平均查找长度()A. 3.1B. 4C. 2.5D. 53.如果要求一个线性表既能较快的查找,又能适应动态变化的要求,则可采用( )查找法。
A. 分块查找B. 顺序查找C. 折半查找D. 基于属性4.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( )A.(100,80,90,60,120,110,130) B.(100,120,110,130,80,60,90)C.(100,60,80,90,120,110,130)D. (100,80,60,90,120,130,110)5. 在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。
A. LLB. LRC. RLD. RR7. 下面关于B和B+树的叙述中,不正确的是( )A. B树和B+树都是平衡的多叉树。
B. B树和B+树都可用于文件的索引结构。
C. B树和B+树都能有效地支持顺序检索。
D. B树和B+树都能有效地支持随机检索。
8. m阶B-树是一棵( )A. m叉排序树B. m叉平衡排序树C. m-1叉平衡排序树D. m+1叉平衡排序树9. 设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链地址法构造散列表,散列函数为H(key)=key MOD 13,散列地址为1的链中有()个记录。
A.1 B. 2 C. 3 D. 410.下面关于哈希(Hash,杂凑)查找的说法正确的是( )A.哈希函数构造的越复杂越好,因为这样随机性好,冲突小B.除留余数法是所有哈希函数中最好的C.不存在特别好与坏的哈希函数,要视情况而定D.若需在哈希表中删去一个元素,不管用何种方法解决冲突都只要简单的将该元素删去即可11. 若采用链地址法构造散列表,散列函数为H(key)=key MOD 17,则需((1))个链表。