西北工业大学21秋《数据结构》离线作业2-001答案_84

西北工业大学21秋数据结构离线作业2-001答案1. 用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为( )。A.5B.6C.8D.9参考答案：A2. AVL树是一种平衡的二叉排序树，树中任一结点的( )A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度参考答案：B3. 线性链表是通过( )方式表示元素之间的关系A.后继元素地址B.元素的存储顺序C.左、右孩子地址D.元素的相对存储位置参考答案：A4. 在数据结构中，数据的逻辑结构可以分成( )。A、内部结构和外部结构B、线性结构和非线性结构C、紧凑结构和非紧揍结构D、动态结构和静态结构参考答案：C5. 以下关于线性表的说法不正确的是( )。A.线性表中的数据元素可以是数字、字符、记录等不同类型B.线性表中包含的数据元素个数不是任意的C.线性表中的每个结点都有且只有一个直接前趋和直接后继D.存在这样的线性表：表中各结点都没有直接前趋和直接后继参考答案：C6. 设二维数组A0.m-10.n-1按行优先顺序存储且每个元素占c个单元，则元素Aij的地址为( )。A.LOC(A00)+(j*m+i)*cB.LOC(A00)+(j-1)*m+i-1*cC.LOC(A00)+(i*n+j)*cD.LOC(A00)+(i-1)*n+j-1*c参考答案：C7. 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。( )A.正确B.错误参考答案：A8. n个顶点的强连通图中至少含有( )。A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边参考答案：B9. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储( )。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法参考答案：C10. 若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D11. 无向图的邻接矩阵可用一维数组存储。( )A.正确B.错误参考答案：A12. 带行表的三元组表是稀疏矩阵的一种( )。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构参考答案：A13. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。( )A.正确B.错误参考答案：A14. 数组的逻辑结构不同于下列( )的逻辑结构。A.线性表B.栈C.队列D.树参考答案：D15. 具有线性结构的数据结构是( )A.赫夫曼树B.栈C.图D.树参考答案：B16. 二叉排序树上左子树上所有结点的值均小于它的根结点的值。( )A.正确B.错误参考答案：A17. 程序一定是算法。( )A.正确B.错误参考答案：B18. 在k叉树中，无父母的结点称为( )。A.祖先B.根C.子孙D.叶参考答案：B19. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行( )。A.s->next=p->next; p->next=sB.q->next=s; s->next=pC.p->next=s; s->next=qD.p->next=s->next; s->next=p参考答案：B20. 在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的定位操作。( )A、错误B、正确参考答案：B21. 栈下溢是指在栈空时进行出栈操作。( )A、错误B、正确参考答案：B22. 下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆参考答案：C23. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head，则( )。A、p指向头结点B、p指向尾结点C、*p的直接后继是头结点D、*P的直接后继是尾结点参考答案：D24. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.32B.30C.28D.24参考答案：B25. 抽象数据类型的三个组成部分分别为( )。A、数据对象、数据关系和基本操作B、数据元素、逻辑结构和存储结构C、数据项、数据元素和数据类型D、数据元素、数据结构和数据类型参考答案：A26. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行( )趟的分配和回收才能使得初始关键字序列变成有序序列。A.3B.4C.5D.8参考答案：A27. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的( )。A.层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法参考答案：C28. 健壮的算法不会因非法的输人数据而出现莫名其妙的状态。( )A.正确B.错误参考答案：A29. 下面说法错误的是( )。 (1)算法原地工作的含义是指不需要任何额外的辅助空间; (2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法; (3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界; (4)同一个算法，实现语言的级别越高，执行效率就越低。A.(1)B.(1)，(2)C.(1)，(4)D.(3)参考答案：C30. 链表不具备的特点是( )。A.可随机访问任意一个结点B.插入和删除不需要移动任何元素C.不必事先估计存储空间D.所需空间与其长度成正比参考答案：A31. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是( )。A.栈B.队列C.树D.图参考答案：C32. 内部排序是根据关键词的大小重新安排各( )的顺序。A.关键词B.数据项C.文件D.数据元素参考答案：B33. 广义表运算式tail(a，b)，(c，d)的操作结果是( )。A.dB.c，dC.(c，d)D.(c，d)参考答案：D34. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为( )。A、q->next=s->next; s->next=pB、s->next=p; q->next=s->nextC、p->next=s->next; s->next=qD、s->next=q; p->next=s->next参考答案：A35. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。( )A、错误B、正确参考答案：A36. 对于线性表(7，34，55，25，64，46，20，10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有( )个。A.1B.2C.3D.4参考答案：D37. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为( )。A.9B.10C.11D.12参考答案：C38. 对5个不同的数据元素进行直接插入排序，最多需要进行( )次比较A.8B.10C.15D.25参考答案：B39. 在二叉树中插入结点，则此二叉树便不再是二叉树了。( )A.正确B.错误参考答案：B40. 无向图中一个顶点的度是指图中( )。A、通过该顶点的简单路径数B、与该顶点相邻接的顶点数C、通过该顶点的回路数D、与该顶点连通的顶点数参考答案：B41. 求图的最小(代价)生成树问题，考虑的是下面的哪一种图?( )A.有向图B.无向图C.带权的有向图D.带权的无向图参考答案：D42. 数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。( )A.正确B.错误参考答案：A43. 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( )。A、n-i+1B、n-iC、iD、i-1参考答案：A44. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( )A.正确B.错误参考答案：A45. 在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行操作：( )A.s->next=p->next; p->next=sB.s->next=p; q->next=sC.q->next=s; s->next=pD.p->next=s; s->next=q参考答案：B46. 链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B47. 线性表的链接实现有利于( )运算。A.插入B.读表元C.查找D.定位参考答案：A48. 假设以行优先顺序存储三维数组A567，其中元素A000的地址为1100，并且每个元素占2个存储单元，则A432的地址是1264。( )A、错误B、正确参考答案：A49. 设有50行60列的二维数组A5060，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A1825的存储地址为( )。A.3700B.4376C.3900D.4620参考答案：D50. 下列排序中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。A.直接插入排序B.冒泡排序C.快速排序D.堆排序参考答案：A