《西北工业大学21秋《数据结构》在线作业一答案参考14》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》在线作业一答案参考14（14页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构在线作业一答案参考1. 右图中的拓扑序列为( )A.C1，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C6，C3参考答案：D2. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案：B3. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。A.n/2B.nC.(n-1)/2D.(n+1)/2参考答案：D4. 在图G的最小生
2、成树T中，可能会有某条边的权值超过未选边的权值。( )A.正确B.错误参考答案：A5. 采用分快查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。A.10B.25C.6D.625参考答案：B6. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。( )A.正确B.错误参考答案：B7. 散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值?( )A.最小概率B.最大概率C.平均概率D.同等概率参考答案：D8. 下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并
3、D.堆参考答案：C9. 某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：A10. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是( )。A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front参考答案：B11. 下列说法中，不正确的是( )。A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成参考答案：D12.
4、在含100个结点的完全二叉树中，叶子结点的个数为36。( )A、错误B、正确参考答案：A13. head指向的带表头结点的单链表为空的判定条件是( )。A.head-next=headB.head-next=NULLC.head=NULLD.head!=NULL参考答案：B14. 一个关键字序列为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参考答案：C15. 稀疏矩阵压缩存储后，必会失
5、去随机存取功能。( )A.正确B.错误参考答案：A16. 由于排序过程中涉及的存储器不同，可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外部排序参考答案：CD17. 程序一定是算法。( )A.正确B.错误参考答案：B18. 在无向图中，若从顶点a到顶点b存在通路，则称a与b之间是连通的。( )A、错误B、正确参考答案：B19. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的( )。A.层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法参考答案：C20. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的
6、是( )。A.直接选择排序B.直接插入排序C.快速排序D.堆排序参考答案：C21. 中序遍历的递归算法平均空间复杂度为( )。A.2(n)B.n(2)C.0(n)D.2n参考答案：C22. 假设以行优先顺序存储三维数组A567，其中元素A000的地址为1100，并且每个元素占2个存储单元，则A432的地址是1264。( )A、错误B、正确参考答案：A23. 基数排序需要进行关键字的比较。( )A.正确B.错误参考答案：B24. 队列的修改是按照先进先出的原则进行的。( )A、错误B、正确参考答案：B25. 已知广义表LS=(a，b，c)，(d，e，f)，运算head和tail函数取出元素e的运
7、算是( )。A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)参考答案：C26. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共( )个，单链表为( )个。A.4，1B.4，2C.1，4D.2，4参考答案：B27. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储( )。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法参考答案：C28. 用链表表示线性表的优点是( )A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素
8、的物理顺序与逻辑顺序相同参考答案：C29. 算法分析的目的是( )。A、辨别数据结构的合理性B、评价算法的效率C、研究算法中输入与输出的关系D、鉴别算法的可读性参考答案：B30. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )A.正确B.错误参考答案：A31. 链式队列Q为空的判定条件：( )A.Q.front=Q.rearB.Q.front=QC.Q=Q.rearD.没有正确参考答案：A32. 在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行操作：( )A.s-next=p-next; p-
9、next=sB.s-next=p; q-next=sC.q-next=s; s-next=pD.p-next=s; s-next=q参考答案：B33. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考答案：A34. 已知函数Sub(s,I,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( )。A、P=SCIENCEB、P=STUDYC、S=SCIENCED、S=STUDY参考答案：A35. 在k叉树中，度为0的结点称为( )。A.祖先B.根C.
10、子孙D.叶参考答案：D36. 某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为( )。A.3B.2C.4D.5参考答案：C37. 深度为5的二叉树至多有( )个结点。A.16B.32C.31D.10参考答案：C38. 在一个单链表中，已知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参考答案：B39. 设栈S和队列Q的初始状态为空，元素e1，e2，e
11、3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是( )。A.6B.4C.3D.2参考答案：C40. 数据结构中所定义的数据元素，是用于表示数据的( )。A.最小单位B.最大单位C.基本单位D.不可分割的单位参考答案：C41. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用( )。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法参考答案：B42. 设有100个关键字，用折半查找法进行查找时，最大比较次数为( )。A.7B.6C.50D.25参考答案：A43.
12、 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。A.2m-1B.2mC.2m+1D.4m参考答案：B44. 下列存储表示中，哪一个不是树的存储形式( )。A.双亲表示法B.孩子链表表示法C.顺序存储表示法D.孩子兄弟表示法参考答案：C45. 计算机识别、存储和加工处理的对象被统称为( )。A、数据B、数据元素C、数据结构D、数据类型参考答案：A46. 下面程序段的时间复杂度为( )。for(i=0; im; i+)for(j=0; jn; j+)Aij=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)参考答案：C47. 对于
13、哈希函数H(key)=key%13，被称为同义词的关键字是( )。A、35和41B、23和39C、15和44D、25和51参考答案：D48. 平衡二叉树的平衡因子只可能是-1、0、1。( )A.正确B.错误参考答案：A49. 若要在单链表中的结点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参考答案：A50. 深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-1参考答案：A51. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( )。A.9B.11C.15D.不能确定参考答案：C52. 数
