《西北工业大学22春《数据结构》离线作业一及答案参考40》由会员分享，可在线阅读，更多相关《西北工业大学22春《数据结构》离线作业一及答案参考40（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学22春数据结构离线作业一及答案参考1. 在长度为n的顺表表的第i个位置上插入一个元素(1in+1)，元素的移动次数为( )。A.n-i+1B.n-iC.iD.i-1参考答案：C2. 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。( )A.正确B.错误参考答案：A3. 下列四种排序中( )的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序参考答案：C4. AOV网的含义是以顶点表示活动的网。( )A.正确B.错误参考答案：A5. 用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存储器D.光盘参考答案：A6. 任何一棵二叉树的叶结点在前序、中序和后序遍历序
2、列中的相对次序( )。A.稍有改变B.发生改变C.不能确定D.不发生改变参考答案：D7. 一组记录的关键字经一趟二路归并排序后得到含有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，40，72D.16，25，35，48，79，23，36，40，72，82参考答案：D8. 一个加权的无向连通图的最小生成树( )。A.有一
3、颗或多颗B.只有一颗C.一定有多颗D.可能不存在参考答案：A9. 引入二叉线索树的目的是( )。A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除参考答案：A10. 下面哪些方法可以判断出一个有向图是否有环(回路)?( )A.求最短路径B.求关键路径C.拓扑排序D.广(宽)度优先遍历参考答案：C11. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是( )。A.10B.11C.12D.15参考答案：A12. 深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-1参考答案：A13
4、. 一个关键字序列为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参考答案：C14. 假设以行优先顺序存储三维数组A567，其中元素A000的地址为1100，并且每个元素占2个存储单元，则A432的地址是1264。( )A、错误B、正确参考答案：A15. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。A.逆拓扑有序B.拓扑有序C.无序的D.
5、A和B参考答案：A16. 在计算机内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考答案：A17. 结构就是用户定义的，( )的一个集合体。参考答案：不同数据类型18. 在一个单链表中，已知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参考答案：B19. 在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是( )。A.r=r-nextB.r=f-nextC.f=r-
6、nextD.f=f-next参考答案：D20. 将森树转成二叉树，根结点没有右子树。( )A.正确B.错误参考答案：B21. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用( )。A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示参考答案：C22. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是( )A.O(n)B.O(e)C.O(n+e)D.O(n*e)参考答案：C23. 由带权为9，2，5，7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为( )。A.23B.37C.46D.44
7、参考答案：D24. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。( )A、错误B、正确参考答案：A25. 散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值?( )A.最小概率B.最大概率C.平均概率D.同等概率参考答案：D26. 与单链表相比，双链表的优点之一是( )。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活参考答案：C27. 链表中的表头指针与表头结点起到相同的作用。( )A.正确B.错误参考答案：B28. head指向的带表头结点的单链表为空的判定条件是( )。A.head-next=
8、headB.head-next=NULLC.head=NULLD.head!=NULL参考答案：B29. 若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列( )。A.存在B.可能不存在C.不存在D.不一定存在参考答案：A30. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素。A.8B.63.5C.63D.7参考答案：B31. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案：B32. 若进栈序列为a，b，c，则通过入出栈
9、操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B33. 线性表的链式存储结构是一种( )。A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构参考答案：A34. 无向图的邻接矩阵可用一维数组存储。( )A.正确B.错误参考答案：A35. Prim(普里姆)算法适用于求( )的网的最小生成树; kruskal(克鲁斯卡尔)算法适用于求( )的网的最小生成树。A.边稠密，边稀疏B.边稀疏，边稠密C.边稠密，边稠密D.边稀疏，边稀疏参考答案：A36. 在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是(
10、 )。A、p-next=headB、p-next-next=headC、p-next=NULLD、p=head参考答案：A37. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：C38. 对无序表用折半查找比顺序查找快。( )A.正确B.错误参考答案：B39. 下列说法中，不正确的是( )。A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成参考答案：D40. 在有向图中，以顶点v为终点的边的数目称为v的入度。( )A、错误B、正确参考答案：B41
11、. 若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现6个不同的出栈序列。( )A、错误B、正确参考答案：A42. 如果某种排序算法是不稳定的，则这种算法不可用。( )A.正确B.错误参考答案：A43. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( )。A.n-1B.nC.n+lD.2n参考答案：C44. 健壮的算法不会因非法的输人数据而出现莫名其妙的状态。( )A.正确B.错误参考答案：A45. 数据的逻辑结构是指各数据元素之间的逻辑关系。( )A.正确B.错误参考答案：A46. 一个具有4个顶点的无向完全图有6条边。( )A、错误B、正确参考答案：B47. 通常
12、将链串的结点大小设置为大于1是为了( )。A、提高串匹配效率B、提高存储密度C、便于插入操作D、便于删除操作参考答案：A48. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A49. 基数排序需要进行关键字的比较。( )A.正确B.错误参考答案：B50. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next=head，则( )。A、p指向头结点B、p指向尾结点C、*p的直接后继是头结点D、*P的直接后继是尾结点参考答案：D51. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用( )存储方式最节省运算时间。A
13、.单链表B.给出表头指针的单循环链表C.双链表D.带头结点的双循环链表参考答案：D52. 已知函数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参考答案：A53. 二叉树中必有度为2的结点。( )A、错误B、正确参考答案：A54. 有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。( )A、错误B、正确参考答案：B55. 判断线索二叉树中某结点p有右子女的条件是( )。A.p-rtag=1B.p-rtag=0C.p-lchild!=NULLD.p!=
