西北工业大学21秋《数据结构》平时作业1答案参考38.docx

西北工业大学21秋《数据结构》平时作业1答案参考1. 对线性表进行二分查找时，要求线性表必须( )A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列参考答案：C2. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案：B3. 在目标串T[0..n-1]=“xwxxyxy”中，对模式串P[0..m-1]=“xy”进行子串定位操作的结果是( )A.1B.2C.3D.5参考答案：C4. 假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，并且每个元素占2个存储单元，则A[4][3][2]的地址是1264 )A、错误B、正确参考答案：A5. 二叉树是度为2的有序树 )A、错误B、正确参考答案：A6. 在有向图中，以顶点v为终点的边的数目称为v的入度 )A、错误B、正确参考答案：B7. 数据的不可分割的最小标识单位是( )A.数据项B.数据记录C.数据元素D.数据变量参考答案：A8. 在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是( )。

A、p->next==headB、p->next->next==headC、p->next==NULLD、p==head参考答案：A9. 具有n个结点的连通图至少有( )条边A.n-1B.nC.n(n-1)/2D.2n参考答案：A10. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98 )A、错误B、正确参考答案：B11. 设有以下四种排序方法，则( )的空间复杂度最大A.冒泡排序B.快速排序C.堆排序D.希尔排序参考答案：B12. 结构就是用户定义的，( )的一个集合体参考答案：不同数据类型13. 若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个( )A.队头元素的前一个位置B.队头元素的后一个位置C.队头元素位置D.队尾元素的前一位置参考答案：A14. 顺序查找法适合于存储结构为( )的线性表A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储参考答案：B15. 深度为5的二叉树至多有( )个结点A.16B.32C.31D.10参考答案：C16. 若一个广义表的表头为空表，则此广义表亦为空表 )A.正确B.错误参考答案：B17. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是( )A.O(n)B.O(e)C.O(n+e)D.O(n*e)参考答案：C18. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head，则( )。

A、p指向头结点B、p指向尾结点C、*p的直接后继是头结点D、*P的直接后继是尾结点参考答案：D19. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个 )A、错误B、正确参考答案：A20. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )A.1234B.4132C.4231D.4213参考答案：C21. 一个关键字序列为{46，79，56，38，40，84}，采用快速排序以位于最左位置的元素为基准而得到的第一次划分结果为( )A.{38，46，79，56，40，84}B.{38，79，56，46，40，84}C.{40，38，46，56，79，84}D.{38，46，56，79，40，84}参考答案：C22. 中序遍历的递归算法平均空间复杂度为( )A.2(n)B.n(2)C.0(n)D.2n参考答案：C23. 线性表中的所有元素都有一个前驱元素和后继元素 )A.正确B.错误参考答案：A24. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n) )A、错误B、正确参考答案：B25. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C26. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。

A.插入B.选择C.交换D.二路归并参考答案：A27. 若已知一个栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，...，pn，若p1=n，则pi为( )A.iB.n-iC.n-i+1D.不确定参考答案：C28. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用( )存储方式最节省运算时间A.单链表B.给出表头指针的单循环链表C.双链表D.带头结点的双循环链表参考答案：D29. 数据结构中所定义的数据元素，是用于表示数据的( )A.最小单位B.最大单位C.基本单位D.不可分割的单位参考答案：C30. 在一个单链表中，已知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参考答案：B31. 数组的逻辑结构不同于下列( )的逻辑结构A.线性表B.栈C.队列D.树参考答案：D32. 通用的处理哈希冲突的方法有( )A、开放定址法B、再哈希法C、链地址法D、建立公共溢出区参考答案：ABCD33. 带行表的三元组表是稀疏矩阵的一种( )。

A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构参考答案：A34. 数据结构是( )A、一种数据类型B、数据的存储结构C、一组性质相同的数据元素的集合D、相互之间存在一种或多种特定关系的数据元素的集合参考答案：D35. 数据结构是带有结构的数据元素的集合 )A.正确B.错误参考答案：A36. 在指定结点之前插入新结点时，双链表比单链表更方便 )A.正确B.错误参考答案：A37. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素A.8B.63.5C.63D.7参考答案：B38. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为( )A.nB.n/2C.(n+1)/2D.(n-1)/2参考答案：C39. 一个具有4个顶点的无向完全图有6条边 )A、错误B、正确参考答案：B40. 含n个顶点的无向连通图中至少含有n条边 )A、错误B、正确参考答案：A41. 设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为( )。

A.3700B.4376C.3900D.4620参考答案：D42. 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( )A、n-i+1B、n-iC、iD、i-1参考答案：A43. 对于哈希函数，冲突只能尽可能得少，不可能完全避免 )A.正确B.错误参考答案：A44. 设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是( )A.高度等于其结点数B.空或只有一个结点C.任一结点无左子女D.任一结点无右子女参考答案：A45. 数组是同类型值的集合 )A.正确B.错误参考答案：B46. 向顺序栈中压入新元素时，应当( )A.先移动栈顶位置，再存入元素B.先存入元素，再移动栈顶位置C.先后 次序无关紧要D.同时进行参考答案：A47. 任何有向网的拓扑排序的结果是唯一的 )A.正确B.错误参考答案：B48. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( )A.9B.11C.15D.不能确定参考答案：C49. 基数排序需要进行关键字的比较 )A.正确B.错误参考答案：B50. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是( )。

A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表参考答案：A。