《西北工业大学21春《数据结构》离线作业一辅导答案3》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》离线作业一辅导答案3（11页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构离线作业一辅导答案1. 在一个长度为100的顺序表中删除第10个元素时，需移动90个元素。( )A、错误B、正确参考答案：B2. 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为( )。A.插入排序B.归并排序C.冒泡排序D.堆排序参考答案：A3. 用链接方式存储的队列，在进行插入运算时( )。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改参考答案：D4. 某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无
2、左孩子D.任一结点无右孩子参考答案：A5. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A6. 一棵树可以只有1个结点。( )A、错误B、正确参考答案：B7. 向二叉搜索树中插入一个元素时，其时间复杂度大致为( )A.O(log2n)B.O(n)C.O(1)D.O(2n)参考答案：A8. 在指定结点之前插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：A9. 栈的插入和删除操作在( )进行。A.栈顶B.栈底C.任意位置D.指定位置参考答案：A10. 深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-1参考答案：A1
3、1. 以下( )不是队列的基本运算。A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值参考答案：B12. 串是一种特殊的线性表，其特殊性体现在( )。A.数据元素是一个字符B.数据元素可以是多个字符C.可以顺序存储D.可以链接存储参考答案：A13. 一个队列的入队序列是a、b、c、d，则队列的输出序列是( )。A.dcbaB.cbdaC.adcbD.abcd参考答案：D14. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)的值为( )。A、15B、16C、17D、18参考答案：D15.
4、 二叉树是度为2的有序树。( )A、错误B、正确参考答案：A16. 在一个单链表中，若删除*p结点的后继结点，则执行操作( )。A.q=p-next; p-next=q-next; free(q)B.p=p-next; p-next=p-next-next; free(p)C.p-next=q-next; free(p-next)D.p=p-next-next; free(p-next)参考答案：A17. 在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则执行( )A.q-next=p-next;p=qB.p-next=q-next;q=pC.q-next=p-ne
5、xt;p-next=qD.p-next=q-next;q-next=p参考答案：D18. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。( )A.正确B.错误参考答案：A19. 在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为( )。A.4，4，3B.4，3，3C.3，4，4D.3，3，4参考答案：B20. 链接存储结构属动态存储方式。( )A.正确B.错误参考答案：A21. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是( )A.O(n)B.O(
6、e)C.O(n+e)D.O(n*e)参考答案：C22. 产生冲突现象的两个关键字称为该散列函数的同义字。( )A、错误B、正确参考答案：B23. 在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是( )。A.r=r-nextB.r=f-nextC.f=r-nextD.f=f-next参考答案：D24. 对无序表用折半查找比顺序查找快。( )A.正确B.错误参考答案：B25. 数据结构是( )。A、一种数据类型B、数据的存储结构C、一组性质相同的数据元素的集合D、相互之间存在一种或多种特定关系的数据元素的集合参考答案：D26. 一棵含18个结点的二叉树的高度至少为( )。A、3B
7、、4C、5D、6参考答案：C27. n个顶点的强连通图中至少含有( )。A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边参考答案：B28. 已知广义表LS=(a，b，c)，(d，e，f)，运算head和tail函数取出元素e的运算是( )。A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)参考答案：C29. 二叉树在线索化后，仍不能有效求解的问题是( )。A.后序线索二叉树中求后序后继B.前序线索二叉树中求前序后继C.中序线索二叉树中求中序后继D.中
8、序线索二叉树中求中序前驱参考答案：A30. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A31. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )。A.5B.6C.16D.17参考答案：C32. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用( )存储方式最节省运算时间。A.单链表B.给出表头指针的单循环链表C.双链表D.带头结点的双循环链表参考答案：D33. 抽象数据类型是指数据逻辑结构及与之相关的操作。( )A、错误B、正确参考答案：B34. 插入、删除只能在同一端进行的线性表，
9、称为( )。A.队列B.栈C.循环队列D.循环栈参考答案：B35. 线性表的链式存储结构是一种( )。A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构参考答案：A36. 若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D37. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。( )A.正确B.错误参考答案：B38. 对于哈希函数，冲突只能尽可能得少，不可能完全避免。( )A.正确B.错误参考答案：A3
10、9. 若有序表的关键字序列为(b，c，d，e，f，g，q，r，s，t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为( )。A.f，c，bB.f，d，bC.g，c，bD.g，d，b参考答案：A40. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( )。A.n-1B.nC.n+lD.2n参考答案：C41. 归并排序的辅助存储空间代价为O(1)。( )A.正确B.错误参考答案：B42. 若一棵满三叉树中含有121个结点，则该树的深度为6。( )A、错误B、正确参考答案：A43. 中序遍历的递归算法平均空间复杂度为( )。A.2(n)B.n(2)C.0(n)D.2n参考答
11、案：C44. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B45. 具有n个结点的连通图至少有( )条边。A.n-1B.nC.n(n-1)/2D.2n参考答案：A46. 字符串“sgabacbadfgbacst”中存在有6个与字符串“ba”相同的子串。( )A、错误B、正确参考答案：A47. 假设三维数组A1098按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A987的存储地址是501。( )A、错误B、正确参考答案：A48. 不含任何字符的串称为空串。( )A、错误B、正确参考答案：B49. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。( )A、错误B、正确参考答案：A50. 在有向图中，以顶点v为终点的边的数目称为v的入度。( )A、错误B、正确参考答案：B
