17春北理工《实用数据结构与算法》在线作业_2.docx

《17春北理工《实用数据结构与算法》在线作业_2.docx》由会员分享，可在线阅读，更多相关《17春北理工《实用数据结构与算法》在线作业_2.docx（36页珍藏版）》请在第一文库网上搜索。

1、2017秋17春北理工实用数据结构与算法在线作业一、单选题(共20道试题，共40分。)1 .具有2000个结点的二叉树，其高度至少为0。A.9B. 10C. I1D. 12正确答案：2.含4个结点(元素值均不相同)的二叉搜索树有O种。A. 12B. 14C.5D.15正确答案：3 .当两个元素比较出现反序时就相互交换位置的排序方法称为()。A.归并排序B.选择排序C.交换排序D.插入排序正确答案：4 .对线性表进行二分查找时，要求线性表必须()。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列正确答案：5 .设有50行60

2、列的二维数组A5060,其元素长度为4字节，按行优先顺序存储，基地址为200,则元素A1825的存储地址为()。A.3700B.4376C.3900D.4620正确答案：6 .一棵高度(假定树根结点为第。层)为4的完全二叉树中的结点数最少为()。A. 15B. 16C. 17D. 31正确答案：7.根据二叉树的定义可知二叉树共有O种不同的形态。A.4B.5C.6D.7正确答案：8 .对哈希(HASH)函数H(k)=kMODm,一般来说，m应取()。A.素数B.很大的数C.偶数D.奇数正确答案：9 .一个数组第一个元素的存储地址是100,每个数组元素的长度为2,则第5个元素的地址是()。A. I

3、IOB. 108C. 100D. 120正确答案：10 .用链接方式存储的队列，在进行插入运算时()。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改正确答案：11 .一个栈的入栈序列是abcde,则栈的不可能的输出序列是()。A. edcbaB. decbaC. dceabD. abcde正确答案：12 .图的存储结构不包括0A.数组表示B.邻接表C.邻接多重表D.孩子兄弟表示正确答案：13 .有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100),当采用折半查找值为82的节点时，()次比较后查找成功。A.1B.2C.4D.8

4、正确答案：14 .二分查找(又称折半查找)要求查找表中的记录按关键字()。A.有序B.无序C.既可有序也可无序正确答案：15 .在一个长度为n的顺序线性表中顺序查找值为X的元素时，查找成功时的平均查找长度(即X与元素的平均比较次数，假定查找每个元素的概率都相等)为().A.nB.n/2C. (n+1)2D. (n-1)2正确答案：16 .以下不稳定的排序方法是()A.直接插入排序B.冒泡排序C.直接选择排序D.二路归并排序正确答案：17 .若构造一棵具有n个结点的二叉排序树，最坏情况下，其深度不会超过()。A. n/2B. nC. (n+1)2D. n+1正确答案：18 .以下说法错误的是()

5、A.每个存储结点只能存放一个数据元索B.数据元素之间的关联方式可由存储结点之间的关联方式直接表达C.一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级D.语言级描述可经编译自动转换成机器级因此也可以看成是一种机内表示正确答案：19 .顺序查找适合于存储结构为()的查找表。A.压缩存储B.散列存储C.索引存储D.顺序存储或链式存储正确答案：20 .若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用哪一种存储结构算法的时间效率最高?()A.单链表B.给出表头指针的单循环链表C.双向链表D.给出表尾指针的双向循环链表正确答案:北理工实用数据结构与算法在线作业二

6、、多选题(共10道试题，共20分。)1.下面几个符号串编码集合中，是前缀编码的是OA. 0,10,110,1111)B. 11,10,001J01,0001C. 00,010,0110,1000)D. (b,c,aa,ac,aba,abb,abc)正确答案：2.二叉树的遍历方式有OA.先序遍历B.中序遍历C.后序遍历D.线索遍历正确答案：3.某堆栈的输入序列为a,b,ad,下面的四个序列中，可能是它的输出序列的是OA.a,c,b,dB.b,c,d,aC. c,d,b,aD. d,c,a,b正确答案：4 .以下说法正确的是OA.二叉树可以是空集B.二叉树的任一结点至多有两棵子树C.二叉树与树具有

7、相同的树形结构D.二叉树的子树有次序之分正确答案：5 .下述哪些不是顺序存储结构的优点？OA.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示正确答案：6 .下面关于哈希(HaSh)查找的说法不正确的是OA.哈希函数构造的越复杂越好，因为这样随机性好，冲突小B.除留余数法是所有哈希函数中最好的C.不存在特别好与坏的哈希函数，要视情况而定D.若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可正确答案：7 .下面关于求关键路径的说法正确的是OA.求关键路径是以拓扑排序为基础的B. 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间

8、相同C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D.关键活动一定位于关键路径上正确答案：8.以下说法正确的是OA.对于线性表来说，定位运算在顺序表和单链表上的量级均为O(n)8 .读表元运算在顺序表上只需常数时间O(1)便可实现，因此顺序表是一种随机存取结构C.在链表上实现读表元运算的平均时间更杂性为O(1)D.插入、删除操作在链表上的实现可在O(1)时间内完成正确答案：9 .以下不稳定的排序方法是OA.快速排序B.冒泡排序C.希尔排序D.堆排序正确答案：10.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形可能出现的是()AG中有弧B.

9、G中有一条从Vi到Vj的路径C. G中没有D. G中有一条从Vj到Vi的路径正确答案：北理工实用数据结构与算法在线作业三、判断题(共20道试题，共40分。)1 .中序遍历二叉排序树可以得到一个有序的序列。A.错误B.正确正确答案：2 .对于同一组结点，由于建立二叉排序树时插入结点的先后次序不同，所构成的二叉排序树的形态及深度也不同，所以含有n个结点的二叉排序树不唯一。A.错误B.正确正确答案：3 .完全二叉树的某结点若没有左孩子，则它必是叶子结点。A.错误B.正确正确答案：4 .完全二叉树中，若一个结点没有左孩子，则它必是树叶。A.错误B.正确正确答案：5 .做进栈运算时应先判别,栈是否为空。

10、A.错误B.正确正确答案：6 .一个循环链表可以由所给定的头指针或者尾指针惟一地确定。A.错误B.正确正确答案：7 .空格也是合法字符，它可以出现在较长的字符串中，也可以单独出现。A.错误8 .正确正确答案：8 .算法必须具备的5个特征是：有穷性、确定性、可行性、有。或多个输入量，至少有1个输出量。A.错误B.正确正确答案：9 .快速排序是排序算法中平均性能最好的一种排序。A.错误B.正确正确答案：10 .设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。A.错误B.正确正确答案：11 .深度为6的二叉树最多有64个结点。A.错误B.正确正确答案：12 .顺序查找法适用于存储结

11、构为顺序或链接存储的线性表。A.错误B.正确正确答案：13 .哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。A.错误B.正确正确答案：14.一个栈的输入序列是12345,则栈的输出序列可以是54312。A.错误B.正确正确答案：15.快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。A.错误B.正确正确答案：16.二叉树是二叉排序树的充要条件是其任意非叶结点的值均大于其左孩子的值、小于其右孩子的值。A.错误B.正确正确答案：17.散列法存储的基本思想是由关键码的值决定数据的存储地址。A.错误B.正确正确答案：18.队列和栈都是运算受限的线性表。A.错误B.正确正确答案：

12、19.任何一棵二叉树中至少有一个结点的度为2。A.错误B.正确正确答案：20.广义表中原子个数即为广义表的长度。A.错误B.正确正确答案：北理工实用数据结构与算法在线作业一、单选题（共20道试题，共40分。）1 .栈的插入和删除操作在。进行。A.栈顶B.栈底C.任意位置D.指定位置正确答案：2 .具有65个结点的完全二叉树其深度为(根的层次号为1)OoA.8B.7C.6D.5正确答案：3 .具有线性结构的数据结构是()A.赫夫曼树B.栈C.图D.树正确答案：4 .下列排序方法中，排序趟数与序列的原始状态有关的方法是()。A.选择排序B.希尔排序C.堆排序D.冒泡排序正确答案：5 .长度为256

13、的表,采用分块查找,每块最佳长度为0。A. 14B. 16C. 18D. 26正确答案：6 .下述几种排序方法中，平均查找长度最小的是()。A.插入排序B.选择排序C.快速排序D.归并排序正确答案：7 .学习数据结构主要目的是()。A.处理数值计算问题8 .研究程序设计技巧C.选取合适数据结构，写出更有效的算法D.是计算机硬件课程的基础正确答案：8 .下列存储表示中,哪一个不是树的存储形式()。A.双亲表示法B.孩子链表表示法C.顺序存储表示法D.孩子兄弟表示法正确答案：9 .以下排序方法中，稳定的排序方法是0。A.直接插入排序和希尔排序B.直接插入排序和冒泡排序C.希尔排序和快速排序D.冒泡

14、排序和快速排序正确答案：10 .对哈希(HASH)函数H(k)=kMODm,一般来说，m应取0。A.素数B.很大的数C.偶数D.奇数正确答案：11 .一个栈的入栈序列是abcde,则栈的不可能的输出序列是()。A. edcbaB. decbaC. dceabD. abcde正确答案：12.任何一个无向连通图的最小生成树()。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在正确答案：13 .当待排序列基本有序时，下列排序方法中0最好。A.直接插入排序B.快速排序C.堆排序D.归并排序正确答案：14 .顺序查找适合于存储结构为()的查找表。A.压缩存储B.散列存储C.索引存储D.顺序存储或链式存储正确答案：15 .稀疏矩阵一般的压缩存储方法有两种，即0。A.二维数组和三维数组B.三元组表和散列表C.三元