2018年10月高等教育自学考试《数据结构》试题课程代码：02331一、单项选择题1．下列数据结构中，逻辑结构不同的是A．线性表B．栈C．队列D．二叉树2．将16个数据元素的线性表按顺序存储方式存储在数组中，若第一个元素的存储地址是1000，第6个元素的存储地址是1040，则最后一个元素的存储地址是A．1112B．1120C．1124D．11283．设栈的初始状态为空，元素1,2,3,4,5依次入栈，不能得到的出栈序列是A．1，2，3，4，5B．4，5，3，2，1C．1，2，5，4，3D．1，2，5，3，44．设指针变量p指向非空单链表中的结点，next是结点的指针域，则判断p所指结点为尾结点前一个结点的逻辑表达式中，正确的是A．p->next!=NULL&&p->next->next->next==NNULLB．p->next!=NULL&&p->next->next==NULLC．p->next->next==NULLD．p->next==NULL5．已知广义表LS=(((a,b,c),d)，(e,(f,8),(h,i)))，LS的深度是A．2B．3C．4D．56．己知一棵完全二叉树T的第5层上共有5个叶结点，则T中叶结点个数最少是A．5B．8C．10D．277．已知二叉树T的前序遍历序列为a，b，c，e，d，中序遍历序列为c，e，b，d，a，则T的后序遍历序列为A．c，e，d,b，aB．d,e，c，b，aC．e，c，d，b，aD．e，c，b，a，d8．有向图G有n个顶点和e条边，G保存在邻接矩阵M中，M中0与1的个数差是A．n(n+1)／2-eB．n(n+1)／2-2eC．n×n-eD．n×n-2e9．有向图G中所有顶点的度数之和是24，则G中弧的数量是A．10B．12C．14D．1610．设有向图G含有／1个顶点、e条边，使用邻接表存储，对G进行深度优先搜索遍历算法的时间复杂度是A．O(n)B．O(e)C．O(n+e)D．O(n×e)11．对数据序列(26，14，17，12，7，4，3)采用二路归并排序进行升序排序，两趟排序后，得到的排序结果为A．14，26，17，12，4，7，3B．12，14，17，26，3，4，7C．14，26，12，17，3，4，7D．14，26，12，17，3，7，412．下列选项中，不稳定的排序方法是A．希尔排序B．归并排序C．直接插入排序D．冒泡排序13．一组记录的关键字为(35，48，47，23，44，88)，利用堆排序算法进行降序排序，建立的初始堆为A．23，35，48，47，44，88B．23，35，47，48，44，88C．35，23，47，48，44，88D．35，23，47，44，48，8814．一棵二叉排序树中，关键字n所在结点是关键字m所在结点的孩子，则A．n一定大于mB．n一定小于mC．n一定等于mD．n与m的大小关系不确定15．设散列表长m=16，散列函数H(key)=key％15。表中已保存4个关键字：addr(18)=3，addr(35)=5，addr(51)=6，addr(22)=7，其余地址均为开放地址。存储关键字36时存在冲突，采用线性探测法来处理。则查找关键字36时的探查次数是A．1B．2C．3D．4二、填空题16．数据项是具有独立含义的标识单位。17．指针p和q分别指向单链表l中的两个相邻结点，即q->next=p。若要在q所指结点后插入指针r所指结点，则执行的语句是r->next=p；。18．递归算法设计中的最小子问题称为递归的。19．广义表((a,b),(c,d),e,(f,(g,h)))的表尾是。20．已知二叉树的前序遍历序列和后序遍历序列，则对应的二叉树确定。21．如果有向无环图G中仅有一个顶点的入度为0，若要求G的拓扑序列不唯一，则G中必须存在一个出度至少为的顶点。22．将森林T转换为一棵二叉树T1，在T中结点A是结点B的右邻的兄弟(下一个兄弟)，则在T1中，A是B的。结点。23．对含n个元素的数据序列采用快速排序算法进行排序，平均时间复杂度是。24．散列存储中，常用的解决冲突的方法有开放地址法和两大类。25．假设顺序存储的有序表R含有8个关键字，进行二分查找时，平均查找长度为。三、简答题26．设电文字符集是{e1,e2,e3,e4,e5}，各字符出现的次数分别为{36，13，26，18，23)。现要为该字符集设计哈夫曼编码。请回答下列问题。(1)给出构造的哈夫曼树。(2)给出各字符的哈夫曼编码。(3)计算电文编码总长。27．已知图G采用邻接矩阵存储，邻接矩阵如题27图所示。(1)根据邻接矩阵画出图G。(2)根据图G写出从顶点A开始图G的1个深度优先搜索遍历序列。(3)根据图G写出从顶点A开始图G的1个广度优先搜索遍历序列。28．有数据序列(12，17，05，10，20，24，45，11，10，12)，使用希尔排序方法将其排成升序序列。请回答下列问题。(1...
