02331 - 2016年04月 - 数据结构试题及答案.docVIP

数据结构 试卷 第 PAGE10 页 共 NUMPAGES10 页 2016年4月高等教育自学考试全国统一命题考试 数据结构 试卷 (课程代码02331) 注意事项： 1．本试卷分为两部分，第一部分为选择题，第二部分为非选择题。 2．应考者必须按试题顺序在答题卡(纸)指定位置上作答，答在试卷上无效。 3．涂写部分、画图部分必须使用2B铅笔书写部分必须使用黑色字迹签字笔。 第一部分 选择题 一、单项选择题（本大题共15小题，每小题2分，共30分） 1．下列选项中，属于非线性数据结构的是（ ） A．队列 B．栈 C．二叉排序树 D．线性表 2．瑞士计算机科学家沃思教授曾指出：算法+数据结构=程序．这里的数据结构指的是（ ） A．数据的逻辑结构和存储结构 B．数据的线性结构和非线性结构 C．数据的紧凑结构和非紧凑结构 D．数据的顺序结构和链式结构 3．线性表顺序存储时，逻辑上相邻的两个数据元素，其存储地址（ ） A．一定相邻 B．一定不相邻 C．不一定相邻 D．可能不相邻 4．数据元素1，2，3，4，5依次入栈，则不可能得到的出栈序列是（ ） A．4，5，3，2，1 B．1，2，3，4，5 C．4，3，5，1，2 D．5，4，3，2，1 5．设顺序表首元素A[0]的存储地址是4000，每个数据元素占5个存储单元，则元素A[20]的起始存储地址是（ ） A．4005 B．4020 C．4100 D．4105 6．广义表 A=(a，(b，c，(e，f)))，函数 head(head(tail(A)))的运算结果是（ ） A．a B．b C．c D．e 7．设高度为h的二叉树中，只有度为0和2的结点，则此类二叉树包含的结点数至少是（ ） A．2h B．2h-1 C．2h+1 D．h+1 8．—棵非空二叉树T的前序遍历和后序遍历序列正好相反，则T一定满足（ ） A．所有结点均无左孩子 B．所有结点均无右孩子 C．只有一个叶子结点 D．是一棵满二叉树 9．设图的邻接矩阵A如下所示。各顶点的度依次是（ ） A．1，2，1，2 B．2，2，1，1 C．3，4，2，3 D．4，4，2，2 1O．无向图G如题10图所示，从顶点a开始进行深度优先遍历，下列遍历序列中，正确的是（ ） A．a，b，e，c，d，f B．a，c，f，e，d，b C．a，c，b，e，f，d D．a，e，d，f，c，b 11．设带权连通图G中含有n（n1）个顶点，下列关于G的最小生成树T的叙述中，正确的是（ ） A．T中可能含有回路 B．T中含有图G的所有边 C．T是唯一的，且含有n-1条边 D．T可能不唯一，但权一定相等 12．若要求对序列进行稳定的排序，则在下列选项中应选择（ ） A．希尔排序 B．快速排序 C．直接插入排序 D．直接选择排序 13．下列排序算法中，空间复杂度最差的是（ ） A．归并排序 B．希尔排序 C．冒泡排序 D．堆排序 14．下列排序算法中，初始数据有序时，花费的时间反而更多的算法是（ ） A．插入排序 B．冒泡排序 C．快速排序 D．希尔排序 15．对线性表L进行二分查找时，要求L必须满足（ ） A．以顺序方式存储 B．以顺序方式存储，且数据元素有序 C．以链接方式存储 D．以链接方式存储，且数据元素有序 第二部分 非选择题 二、填空题（本大题共10小题，每小题2分，共20分） 16．下面程序段的时间复杂度是_________。i=1;while(i n) i=i*2; 17．在单链表的p结点之后插入s结点的操作是_________。 18．只能在线性表的两端进行插入或删除操作的两种逻辑结构分别是_________。 19．广义表A=(x，(y，z，(u，v，w)))的长度是_________。 20．一棵树的后序遍历序列与其对应的二叉树的_________序遍历序列相同。 21．在有向图、无向图中，其邻接矩阵一定对称的是_________。 22．要计算图中从某一顶点出发到其余各顶点的最短路径，可选用_________算法。 23．设关键字序列为28，72，97，63，4，53，84，使用希尔排序法将其排成升序序列，若第一趟采用的间隔是3，则该趟排序的结果是_________。 24．对具有15个关键字的关键字序列进行顺序查找时，查找成功的平均查找长度为_________。 25．在二叉排序树的查找过程中，若当前结点的关键字值大于待查找关键字，则应该再该结点的_________子树上继续查找。 三、解答题（本大题共4小题，每小题5分，共20分） 26．设Q是有N个存储空间的循环队列，初始状态front=rear=0，约定指针rear