《西北工业大学21春《数据结构》在线作业一满分答案15》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》在线作业一满分答案15（14页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构在线作业一满分答案1. 数组是同类型值的集合。( )A.正确B.错误参考答案：B2. 数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。( )A、错误B、正确参考答案：B3. 设某算法的问题规模函数f(n)=300n2+8000n+900，则它的渐进时间复杂度为( )A.O(n3)B.O(n2)C.O(n)D.O(1)参考答案：B4. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的( )。A.层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法参考答案：C5. 基数排序需要进行关键字的比较。( )A.正确B.错误参考答案：B6. 在一
2、个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B7. 线性链表不具有的特点是( )A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比参考答案：A8. 在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是( )。A、p-next=headB、p-next-next=headC、p-next=NULLD、p=head参考答案：A9. 在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是( )。A.r=r-next
3、B.r=f-nextC.f=r-nextD.f=f-next参考答案：D10. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A11. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p-next-next=null。( )A、错误B、正确参考答案：B12. 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。( )A.正确B.错误参考答案：A13. 设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度
4、为( )。A.21B.23C.41D.62参考答案：C14. 一棵树可以只有1个结点。( )A、错误B、正确参考答案：B15. 某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：A16. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。( )A.正确B.错误参考答案：B17. 一个队列的入队序列是a、b、c、d，则队列的输出序列是( )。A.dcbaB.cbdaC.adcbD.abcd参考答案：D18. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，8，列下
5、标为j=1，2，10。设每个字符占一个字节，若按行先存储，元素A8，5的起始地址与A按列存储时起始地址相同的元素是( )。A.A8，5B.A3，10C.A5，8D.A0，9参考答案：B19. 一个关键字序列为46，79，56，38，40，84，采用快速排序以位于最左位置的元素为基准而得到的第一次划分结果为( )A.38，46，79，56，40，84B.38，79，56，46，40，84C.40，38，46，56，79，84D.38，46，56，79，40，84参考答案：C20. 若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )。A.一定存在B.一定不存在C.不一定
6、存在D.不确定参考答案：A21. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)的值为( )。A、15B、16C、17D、18参考答案：D22. 用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为( )。A.5B.6C.8D.9参考答案：A23. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B24. 循环队列SQ采用数组空间SQ.base0，n-1存储其元素值，已知其头尾指针分别是front和rezr，则判断此循环队列Q为满队列的条件
7、是( )。A.Q.front=Q.rearB.Q.rear!=Q.frontC.Q.front=(Q.rear+1)%nD.Q.front!=(Q.rear+1)%n参考答案：C25. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。A.逆拓扑有序B.拓扑有序C.无序的D.A和B参考答案：A26. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。A.n/2B.nC.(n-1)/2D.(n+1)/2参考答案：D27. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.32B.30C.28D.24参考答案：B28.
8、计算机识别、存储和加工处理的对象被统称为( )。A、数据B、数据元素C、数据结构D、数据类型参考答案：A29. 带行表的三元组表是稀疏矩阵的一种( )。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构参考答案：A30. 如果入栈序列是1，3，5，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为47。( )A、错误B、正确参考答案：B31. 在指定结点之后插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：B32. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储( )。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据
9、的存储方法参考答案：C33. 含n个顶点的无向连通图中至少含有n条边。( )A、错误B、正确参考答案：A34. 在一个图中所有顶点的度数之和等于所有边数的( )倍。A.1/2B.2C.1D.4参考答案：B35. 求图的最小(代价)生成树问题，考虑的是下面的哪一种图?( )A.有向图B.无向图C.带权的有向图D.带权的无向图参考答案：D36. 一个有向图的邻接表和逆邻接表中结点的个数可能不等。( )A.正确B.错误参考答案：B37. 两个串相等的充分必要条件是两个串的长度相等且字母相同。( )A、错误B、正确参考答案：B38. 在二叉树的第i层上至多可以有2i个结点。( )A、错误B、正确参考答
10、案：A39. 链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B40. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )A.正确B.错误参考答案：A41. 由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。( )A、错误B、正确参考答案：A42. 假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为abbccddedc。( )A、错
11、误B、正确参考答案：A43. 具有n个结点的连通图至少有( )条边。A.n-1B.nC.n(n-1)/2D.2n参考答案：A44. 二叉树中必有度为2的结点。( )A、错误B、正确参考答案：A45. 对长度为n的关键字序列进行堆排序的空间复杂度为( )。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)参考答案：B46. 深度为k的二叉树至多有2k-1个结点。( )A、错误B、正确参考答案：A47. 在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则执行( )A.q-next=p-next;p=qB.p-next=q-next;q=pC.q-nex
12、t=p-next;p-next=qD.p-next=q-next;q-next=p参考答案：D48. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。( )A、错误B、正确参考答案：A49. 将一个A1.100，1.100的三对角矩阵，按行优先次序存入一维数组B1.298中，A中元素A66，65在数组B中的位置K为( )。A.199B.197C.195D.193参考答案：C50. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )。A.5B.6C.16D.17参考答案：C51.
13、 对于哈希函数H(key)=key%13，被称为同义词的关键字是( )。A、35和41B、23和39C、15和44D、25和51参考答案：D52. 中序遍历的递归算法平均空间复杂度为( )。A.2(n)B.n(2)C.0(n)D.2n参考答案：C53. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共( )个，单链表为( )个。A.4，1B.4，2C.1，4D.2，4参考答案：B54. 在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C55. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9参考答案：C
