《西北工业大学21春《数据结构》离线作业2参考答案3》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》离线作业2参考答案3（11页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构离线作业2参考答案1. 下列描述中正确的是( )。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A2. 结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比。( )A.正确B.错误参考答案：A3. 在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C4. 一组记录的关键字经一趟二路归并排序后得到含有5个长度为2的有序
2、表如下：25，48，16，35，79，82，23，40，36，72，在此基础上按二路归并排序方法再对该序列进行一趟归并后的结果为( )A.16，25，35，48，23，40，79，82，36，72B.16，25，35，48，23，40，79，82，72，36C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，82参考答案：D5. 具有65个结点的完全二叉树其深度为(根的层次号为1)( )。A.8B.7C.6D.5参考答案：B6. 用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存储器D.光盘参考答案：A7. 如果在排序过
3、程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为( )。A.插入排序B.归并排序C.冒泡排序D.堆排序参考答案：A8. 程序一定是算法。( )A.正确B.错误参考答案：B9. 算法分析的两个主要方面是( )。A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性参考答案：A10. 最佳二叉排序树是AVL树(平衡二叉排序树)。( )A.正确B.错误参考答案：A11. 顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示元素之间的关系的。A.物理上相邻，指针B.逻辑上相邻，指针C.逻辑上相临，结
4、点D.物理上相邻，结点参考答案：A12. 一个队列的入队序列是a、b、c、d，则队列的输出序列是( )。A.dcbaB.cbdaC.adcbD.abcd参考答案：D13. 将森树转成二叉树，根结点没有右子树。( )A.正确B.错误参考答案：B14. 数据结构是带有结构的数据元素的集合。( )A.正确B.错误参考答案：A15. 已知一组关键字为25，48，36，72，79，82，23，40，16，35，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是( )。A.25，36，48，72，23，40，79，82，16，35B.25，36，48，72，16，23，40，79，82，35
5、C.25，36，48，72，16，23，35，40，79，82D.16，23，25，35，36，40，48，72，79，82参考答案：D16. 以下关于线性表的说法不正确的是( )。A.线性表中的数据元素可以是数字、字符、记录等不同类型B.线性表中包含的数据元素个数不是任意的C.线性表中的每个结点都有且只有一个直接前趋和直接后继D.存在这样的线性表：表中各结点都没有直接前趋和直接后继参考答案：C17. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B18. 数组的逻辑结构不同于下列( )的逻辑结构。A.线性表B.栈C.队列D.树参考答案：D19. 在计算机
6、内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考答案：A20. 深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-1参考答案：A21. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。A.插入B.选择C.交换D.二路归并参考答案：A22. 线性表的顺序存储结构是一种( )存储结构。A.散列存取B.顺序存取C.随机存取D.索引存取参考答案：C23. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)
7、的值为( )。A、15B、16C、17D、18参考答案：D24. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边。A.n(n-1)/2B.n(n-1)C.n2D.n2-1参考答案：A25. 下列四种排序中( )的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序参考答案：C26. 在指定结点之后插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：B27. 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有( )条有向边。A.nB.n-1C.mD.m-1参考答案：C28. 指针p所指的元素是双向循环链表L的尾元素的条件是( )。A.p=LB.p=NU
8、LLC.p-prior=LD.p-next=L参考答案：D29. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B30. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )。A、3，2，6，1，4，5B、3，4，2，1，6，5C、1，2，5，3，4，6D、5，6，4，2，3，1参考答案：B31. 一个关键字序列为46，79，56，38，40，84，采用快速排序以位于最左位置的元素为基准而得到的第一次划分结果为( )A.38，46，79，56，40，84B.38，79，56，46，40，8
9、4C.40，38，46，56，79，84D.38，46，56，79，40，84参考答案：C32. 在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。( )A.正确B.错误参考答案：A33. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A34. 一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。A.edcbaB.decbaC.dceabD.abcde参考答案：C35. 邻接表法只能用于有向图存储。( )A.正确B.错误参考答案：B36. 某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是( )。A.空或只有一个结点B.高度等于其结点
10、数C.任一结点无左孩子D.任一结点无右孩子参考答案：B37. 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。( )A.正确B.错误参考答案：A38. 串是一种特殊的线性表，其特殊性体现在( )。A.数据元素是一个字符B.数据元素可以是多个字符C.可以顺序存储D.可以链接存储参考答案：A39. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。A.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表参考答案：C40. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。A.逆拓扑有序B.拓扑有序
11、C.无序的D.A和B参考答案：A41. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )A.正确B.错误参考答案：B42. 对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为( )A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC参考答案：B43. 线性链表不具有的特点是( )A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比参考答案：A44. 假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为abb
12、ccddedc。( )A、错误B、正确参考答案：A45. 对于哈希函数，冲突只能尽可能得少，不可能完全避免。( )A.正确B.错误参考答案：A46. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A47. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。( )A、错误B、正确参考答案：B48. Prim(普里姆)算法适用于求( )的网的最小生成树; kruskal(克鲁斯卡尔)算法适用于求( )的网的最小生成树。A.边稠密，边稀疏B.边稀疏，边稠密C.边稠密，边稠密D.边稀疏，边稀疏参考答案：A49. 栈下溢是指在栈空时进行出栈操作。( )A、错误B、正确参考答案：B50. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。A.直接选择排序B.直接插入排序C.快速排序D.堆排序参考答案：C
