16秋浙大《数据结构与算法》在线作业

浙江大学远程教育学院《数据结构与算法》课程离线作业姓名：陈翠学号：713009014001年级：2013秋学习中心：金华学习中心—————————————————————————————一、填空题：（【序号，章，节】。

）【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

【2，1，2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。

【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构___，链式存储结构___。

【4，1，3】度量算法效率可通过时间复杂度___来进行。

【5，1，3】设n 为正整数，下面程序段中前置以记号@的语句的频度是n(n+1)/2 。

for (i=0; i<n; i++){for (j=0; j<n; j++)if (i+j==n-1)@ a[i][j]=0;}【6，1，3】设n 为正整数，试确定下列各程序段中前置以记号@的语句的频度:(1) i=1; k=0;while (i<=n-1){i++;@ k+=10 * i; // 语句的频度是_________n-1_______________。

}(2) k=0;1for (i=1; i<=n; i++){for (j=i; j<=n; j++)@ k++; // 语句的频度是_________n(n+1)/2________________。

}【7，3，2】线性表(a1，a2，…，a n)有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：___顺序_ 存储密度较大；___顺序____存储利用率较高；___顺序____可以随机存取；__链式_____不可以随机存取；__链式____插入和删除操作比较方便。

【8，3，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动n-i 个元素。

数据结构与算法试题+答案一、单选题（共86题，每题1分，共86分）1.栈和队列的共同点是（）。

A、只允许在端点处插入和删除元素B、都是先进后出C、都是先进先出D、没有共同点正确答案：A2.数据元素在计算机存储器内表示时，物理相对位置和逻辑相对位置相同并且是连续的，称之为（）。

A、逻辑结构B、顺序存储结构C、链式存储结构D、以上都不对正确答案：B3.假设我们只有2条磁带Ta和Tb用于做外部排序。

假设内存可以一次处理M条记录。

初始状态下Ta上存有N条记录。

下列简单算法的执行步骤为：第1步：从Ta一次读入M条记录到内存，做内部排序，然后将有序的结果写到Tb。

第2步：从Ta一次读入M条记录到内存，做内部排序，然后将其与Tb上存储的有序列做归并，将有序的（2M条记录）结果写到Ta。

第3步：从Ta一次读入M条记录到内存，做内部排序，然后将其与Tb上存储的2M条记录的有序列做归并，将有序的（3M条记录）结果写到Tb。

重复第2、3步，直到全部记录有序。

上述算法需要执行__轮。

A、⌈N/M⌉B、logNC、⌈log(N/M)⌉D、logMN正确答案：A4.对任意给定的含 n (n>2) 个字符的有限集 S，用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树 T1 和 T2。

下列叙述中，正确的是：A、出现频次不同的字符在 T2 中处于相同的层B、出现频次不同的字符在 T1 中处于不同的层C、T1 与 T2 的结点数相同D、T1 的高度大于 T2 的高度正确答案：A5.对初始数据序列{ 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 }进行希尔排序。

若第一趟排序结果为（ 1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ），第二趟排序结果为（ 1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 ），则两趟排序采用的增量（间隔）依次是：A、3, 1B、5, 2C、3, 2D、5, 3正确答案：D6.从一个具有N个结点的单链表中查找其值等于X的结点时，在查找成功的情况下，需平均比较多少个结点？A、N/2B、(N+1)/2C、ND、(N−1)/2正确答案：B7.下面代码段的时间复杂度是（）。

数据结构与算法试题库含答案一、单选题（共100题，每题1分，共100分）1.定义学生选修课程的关系模式如下：SC (S#,Sn,C#,Cn,G)（其属性分别为学号、姓名、课程号、课程名、成绩）则该关系的主键为A、S#,C#B、S#C、C#D、S#,C#,G正确答案：A2.下列叙述中正确的是A、解决同一个问题的不同算法的时间复杂度必定是相同的B、对同一批数据作不同的处理，如果数据存C、对同一批数据作同一种处理，如果数据存储结构不同，不同算法的时间复杂度肯定相同D、解决同一个问题的不同算法的时间复杂度一般是不同的正确答案：D3.小张的毕业论文设置为 2 栏页面布局，现需在分栏之上插入一横跨两栏内容的论文标题，最优的操作方法是：A、在两栏内容之前空出几行，打印出来后手动写上标题。

B、在两栏内容之上插入一个文本框，输入标题，并设置文本框的环绕方式。

C、在两栏内容之上插入一个艺术字标题。

第 7 组D、在两栏内容之上插入一个分节符，然后设置论文标题位置。

正确答案：D4.连接数据库所使用的开放数据库互连（ODBC）属于：A、数据库B、数据库中间件C、共享软件D、云操作系统正确答案：B5.中学教师和授课班级之间的联系是A、一对多B、多对一C、一对一D、多对多正确答案：D6.小王要将一份通过 Excel 整理的调查问卷统计结果送交经理审阅，这份调查表包含统计结果和中间数据两个工作表。

他希望经理无法看到其存放中间数据的工作表，最优的操作方法是：A、将存放中间数据的工作表删除B、将存放中间数据的工作表移动到其他工作簿保存C、将存放中间数据的工作表隐藏，然后设置保护工作表隐藏D、将存放中间数据的工作表隐藏，然后设置保护工作簿结构正确答案：D7.循环队列的存储空间为 Q(1:100)，初始状态为 front=rear=100。

经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为A、2B、99第 17 组C、0 或 100D、1正确答案：C8.下列设备组中，完全属于计算机输出设备的一组是：A、喷墨打印机，显示器，键盘B、打印机，绘图仪，显示器C、键盘，鼠标器，扫描仪D、激光打印机，键盘，鼠标器正确答案：B9.现代微型计算机中所采用的电子元器件是：A、电子管B、大规模和超大规模集成电路C、晶体管D、小规模集成电路正确答案：B10.软件生存周期中，解决软件“怎么做”的阶段是A、需求分析B、软件设计C、可行性研究D、软件测试正确答案：B11.设一棵度为 3 的树，其中度为 2，1，0 的结点数分别为 3，1，6。

单选题1.从原理上讲，折半查找法要求查找表中各元素的键值必须是____∙ A 递增或递减∙ B 递增∙ C 递减∙ D 无序单选题2.关于判定树，下列说法不正确的是____∙ A 判定树是对有序序列进行二分查找得到的树∙ B n个结点的判定树的深度为[log2n]+1∙ C 判定树的叶子结点都在同一层∙ D 判定树除去最后一层结点以后是满二叉树或空二叉树单选题3.在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做____次关键码比较∙ A 2∙ B 3∙ C 4∙ D 5单选题4.对线性表进行二分查找时，要求线性表必须____ ∙ A 以顺序方式存储∙ B 以顺序方式存储且元素有序∙ C 以链式方式存储∙ D 以链式方式存储且元素有序单选题5.折半查找算法的时间复杂度是____∙ A O(n2)∙ B O(n)∙ C O(log2n)∙ D O(nlog2n)单选题6.若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至____∙ A 该中间位置∙ B 该中间位置－1∙ C 该中间位置＋1∙ D 该中间位置／2单选题7.对包含N个元素的散列表进行查找，平均查找长度____∙ A 为O(log2N)∙ B 为O(N)∙ C 不直接依赖于N∙ D 上述三者都不是单选题8.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过____∙ A n/2∙ B n∙ C (n+1)/2∙ D n+1单选题9.分别以下列序列构造二叉排序树，则与其它几个序列构造的结果不同的是____∙ A （80，70，60，75，90，85，100，10）∙ B （80，90，85，70，60，10，75，100）∙ C （80，90，70，85，10，60，75，100）∙ D （80，90，100，70，85，60，10，75）单选题10.如果某二叉树的左右子树的高度差的绝对值不大于1，则一定是平衡二叉树∙ A 正确∙ B 不正确单选题11.AVL树的任何子树都是AVL树。