《西北工业大学21春《数据结构》在线作业二满分答案64》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》在线作业二满分答案64（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构在线作业二满分答案1. 单链表中，增加一个头结点的目的是为了( )。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储参考答案：C2. 具有65个结点的完全二叉树其深度为(根的层次号为1)( )。A.8B.7C.6D.5参考答案：B3. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( )A、错误B、正确参考答案：A4. 数组是同类型值的集合。( )A.正确B.错误参考答案：B5. 二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点X的值;其右子树根结点的值大于等于该结点X的值，则
2、此二叉树一定是二叉排序树。( )A.正确B.错误参考答案：B6. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是( )。A.6B.4C.3D.2参考答案：C7. 在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?( )A.直接选择排序B.直接插入排序C.快速排序D.冒泡排序参考答案：A8. 散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值?( )A.最小概率B.最大概率C.平均概率D.同等概率参考答案：D9. 计算机识别、存
3、储和加工处理的对象被统称为( )。A、数据B、数据元素C、数据结构D、数据类型参考答案：A10. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。A.插入B.选择C.交换D.二路归并参考答案：A11. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。( )A.正确B.错误参考答案：A12. 线性表是具有n个( )的有限序列。A.字符B.数据元素C.数据项D.表元素参考答案：B13. 假设以行优先顺序存储三维数组A567，其中元素A000的地址为1100，并且每个元素占2个存储单元，则A432的地址是1264
4、。( )A、错误B、正确参考答案：A14. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用( )存储方式最节省运算时间。A.单链表B.给出表头指针的单循环链表C.双链表D.带头结点的双循环链表参考答案：D15. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是( )。A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front参考答案：B16. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行( )。A.s-next=p-next; p
5、-next=sB.q-next=s; s-next=pC.p-next=s; s-next=qD.p-next=s-next; s-next=p参考答案：B17. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A18. 二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的相对位置出现。( )A.正确B.错误参考答案：A19. 在对链队列作出队操作时，不会改变front指针的值。( )A、错误B、正确参考答案：A20. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考
6、答案：B21. 链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。( )A.正确B.错误参考答案：A22. 插入、删除只能在同一端进行的线性表，称为( )。A.队列B.栈C.循环队列D.循环栈参考答案：B23. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是( )。A.单链表B.静态链表C.线性链表D.顺序存储结构参考答案：C24. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是( )A.O(n)B.O(e)C.O(n+e)D.O(n*e)参考答案：C25. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关
7、键字可能存在的块号，然后再在相应的块内进行顺序查找。( )A.正确B.错误参考答案：A26. 若让元素1，2，3依次进栈，则出栈次序不可能出现种情况( )A.3，2，1B.2，1，3C.3，1，2D.1，3，2参考答案：C27. 已知指针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参考答案：A28. 采
8、用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。A.n/2B.nC.(n-1)/2D.(n+1)/2参考答案：D29. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。A.希尔排序B.快速排序C.插入排序D.选择排序参考答案：D30. 高度为5的完全二叉树中含有的结点数至少为( )。A、16B、17C、31D、32参考答案：A31. 在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是( )。A.r=r-nextB.r=f-nextC.f=r-nextD.f=f-next参考答案：D32. 向顺序栈中压入新元素时，应当( )A.先移动栈
9、顶位置，再存入元素B.先存入元素，再移动栈顶位置C.先后 次序无关紧要D.同时进行参考答案：A33. 在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则执行( )A.q-next=p-next;p=qB.p-next=q-next;q=pC.q-next=p-next;p-next=qD.p-next=q-next;q-next=p参考答案：D34. 深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-1参考答案：A35. 一棵树可以只有1个结点。( )A、错误B、正确参考答案：B36. 稀疏矩阵常用的压缩存储方法有两种，它们是( )
10、。A.散列和十字链表B.二维数组和三维数组C.三元组和散列D.三元组和十字链表参考答案：D37. 下列程序段for(i=1; iA.O(1)B.O(0)C.O(1+n)D.O(n)参考答案：D38. 下列存储表示中，哪一个不是树的存储形式( )。A.双亲表示法B.孩子链表表示法C.顺序存储表示法D.孩子兄弟表示法参考答案：C39. 下列描述中正确的是( )。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A40. 假设一棵完全二叉树含1000个结
11、点,则其中度为2的结点数为512个。( )A、错误B、正确参考答案：A41. 某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：A42. 数据项是数据的基本单位。( )A.正确B.错误参考答案：A43. 一个有向图的邻接表和逆邻接表中结点的个数可能不等。( )A.正确B.错误参考答案：B44. 有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。( )A、错误B、正确参考答案：B45. 在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为4
12、5、89和12的结点时，所需进行的比较次数分别为( )。A.4，4，3B.4，3，3C.3，4，4D.3，3，4参考答案：B46. 引入二叉线索树的目的是( )。A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除参考答案：A47. 某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是( )。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：B48. 邻接表法只能用于有向图存储。( )A.正确B.错误参考答案：B49. 在图G的最小生成树T中，可能会有某条边的权值超过未选边的
13、权值。( )A.正确B.错误参考答案：A50. 链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B51. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储( )。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法参考答案：C52. 对于哈希函数，冲突只能尽可能得少，不可能完全避免。( )A.正确B.错误参考答案：A53. 串S=”I am a worker的长度是10。( )A、错误B、正确参考答案：A54. 在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的定位操作。( )A、错误B、正确参考答案：B55. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素。A.8B.63.5C.63D.7
