《西北工业大学21春《数据结构》离线作业2参考答案61》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》离线作业2参考答案61（11页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构离线作业2参考答案1. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。A.插入B.选择C.交换D.二路归并参考答案：A2. 一组记录的关键字经一趟二路归并排序后得到含有5个长度为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
2、，40，72D.16，25，35，48，79，23，36，40，72，82参考答案：D3. 不含任何字符的串称为空串。( )A、错误B、正确参考答案：B4. 数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是( )。A.线性表B.树形结构C.广义表D.图结构参考答案：A5. 两个串相等的充分必要条件是两个串的长度相等且字母相同。( )A、错误B、正确参考答案：B6. 判断线索二叉树中某结点p有右子女的条件是( )。A.p-rtag=1B.p-rtag=0C.p-lchild!=NULLD.p!=NULL参考答案：B7. 下列程序段for(i=1; iA.O(1)B.O(0)C.O
3、(1+n)D.O(n)参考答案：D8. 一个队列的入队序列是1、2、3、4，则队列的首次输出元素是( )。A.1B.2C.3D.4参考答案：A9. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9参考答案：C10. 链接存储结构属静态存储方式。( )A.正确B.错误参考答案：B11. 结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比。( )A.正确B.错误参考答案：A12. 空格串的长度是空格的个数。( )A、错误B、正确参考答案：B13. 在关键字序列(12，23，34，
4、45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为( )。A.4，4，3B.4，3，3C.3，4，4D.3，3，4参考答案：B14. 按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号，当iA.2i-1B.2iC.2i+1D.不确定参考答案：B15. 队列的插入操作是在( )。A.队尾B.队头C.队列任意位置D.队头元素后参考答案：A16. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。( )A、错误B、正确参考答案：A17. 在指定结点之前插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：A1
5、8. 以下关于线性表的说法不正确的是( )。A.线性表中的数据元素可以是数字、字符、记录等不同类型B.线性表中包含的数据元素个数不是任意的C.线性表中的每个结点都有且只有一个直接前趋和直接后继D.存在这样的线性表：表中各结点都没有直接前趋和直接后继参考答案：C19. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A20. 有关二叉树下列说法正确的是( )。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2参考答案：B21. 数据的逻辑结构是指各数据元素之间的逻辑关系。( )A.正确B.错误参考答案：
6、A22. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( )。A.n-1B.nC.n+lD.2n参考答案：C23. 链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。( )A.正确B.错误参考答案：A24. 下列存储表示中，哪一个不是树的存储形式( )。A.双亲表示法B.孩子链表表示法C.顺序存储表示法D.孩子兄弟表示法参考答案：C25. 链式队列Q为空的判定条件：( )A.Q.front=Q.rearB.Q.front=QC.Q=Q.rearD.没有正确参考答案：A26. AOV网的含义是以顶点表示活动的网。( )A.正确B.错误参考答案：A27. B+树应用在(
7、)文件系统中。A.顺序B.散列C.VSAMD.ISAM参考答案：C28. 算法分析的目的是( )。A、辨别数据结构的合理性B、评价算法的效率C、研究算法中输入与输出的关系D、鉴别算法的可读性参考答案：B29. 为使平均查找长度达到最小，当由关键字集合05，11，21，25，37，40，41，62，84构建二叉排序树时，第一个插入的关键字应为( )。A.5B.37C.41D.62参考答案：B30. 在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C31. 对任何一棵二叉树，如果其终端结点数为n0，度为2的
8、结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B32. 链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B33. 下面说法错误的是( )。 (1)算法原地工作的含义是指不需要任何额外的辅助空间; (2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法; (3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界; (4)同一个算法，实现语言的级别越高，执行效率就越低。A.(1)B.(1)，(2)C.(1)，(4)D.(3)参考答案：C34. 若一个算
9、法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为O(n)。( )A、错误B、正确参考答案：A35. 如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是( )。A.顺序查找B.折半查找C.基于属性的查找D.分块查找参考答案：D36. 按照二叉树的定义，具有3个结点的二叉树有( )种。A.3B.4C.5D.6参考答案：C37. 对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为( )A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC参考答案：B38. 用链表表示线性表的优点是( )A.便
10、于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同参考答案：C39. 若要在单链表中的结点p之后插入一个结点s，则应执行的语句是( )。A.s-next=p-next; p-next=sB.p-next=s; s-next=p-nextC.p-next=s-next; s-next=pD.s-next=p; p-next=s-next参考答案：A40. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。( )A、错误B、正确参考答案：A41. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )A.正确B.错误参考答案：B4
11、2. 采用分快查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。A.10B.25C.6D.625参考答案：B43. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A44. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为( )。A.nB.n/2C.(n+1)/2D.(n-1)/2参考答案：C45. 对无序表用折半查找比顺序查找快。( )A.正确B.错误参考答案：B46. 在一个单链表中，若删除*p结点的后继结点，则执行
12、操作( )。A.q=p-next; p-next=q-next; free(q)B.p=p-next; p-next=p-next-next; free(p)C.p-next=q-next; free(p-next)D.p=p-next-next; free(p-next)参考答案：A47. 抽象数据类型是指数据逻辑结构及与之相关的操作。( )A、错误B、正确参考答案：B48. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。A.0B.1C.2D.3参考答案：B49. 若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D50. 中序遍历二叉排序树可以得到一个有序的序列。( )A.正确B.错误参考答案：A
