内容发布更新时间 : 2024/10/22 14:01:45星期一 下面是文章的全部内容请认真阅读。
精品文档
2018年10月高等教育自学考试全国统一命题考试
数据结构 试卷
(课程代码02331)
本试卷共7页，满分l00分，考试时间l50分钟。 考生答题注意事项：
1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。 2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4．合理安排答题空间，超出答题区域无效。
第一部分 选择题
一、单项选择题：本大题共l5小题，每小题2分，共30分。在每小题列出的备选项中 只有一项是最符合题目要求的。请将其选出。
1．下列数据结构中，逻辑结构不同的是
A．线性表 B．栈 C．队列 D．二叉树
2．将l6个数据元素的线性表按顺序存储方式存储在数组中，若第一个元素的存储地 址是l000，第6个元素的存储地址是1040，则最后一个元素的存储地址是 A．1112 B．1120 C．1124 D．1128
3．设栈的初始状态为空，元素1，2，3，4，5依次入栈，不能得到的出栈序列是
A．1，2，3，4，5 B．4，5，3，2，1 C．1，2，5，4，3 D．1，2，5，3，4 4．设指针变量P指向非空单链表中的结点，next是结点的指针域，则判断P所指结点 为尾结点前一个结点的逻辑表达式中，正确的是
A. p->next!=NULL&&p->next一>next->next == NULL B．p->next!=NULL&&p->next->next—NULL C．p->next->next==NULL D．p->next—NULL
5．已知广义表LS=(((a，b，c)，d)，(e，(fg，(h i)))，LS的深度是 A．2 B．3 C．4 D．5
6．已知一棵完全二叉树T的第5层上共有5个叶结点，则T中叶结点个数最少是 A．5 8．8 C．10 D．27
7．已知二叉树T的前序遍历序列为a，b，c，e，d，中序遍历序列为C，e，b，d，a，则T的后序遍历序列为
A．c，e，d,b，a B．d，e，c，b，a C．e，c，d，b，a D．e，c，b，a，d 8．有向图G有玎个顶点和e条边，G保存在邻接矩阵M中，M中0与1的个数差是 A．n(n+1)／2-e B．n(n+1)／2-2e C．n×n-e D．n×n-2e 9．有向图G中所有顶点的度数之和是24，则G中弧的数量是 A．10 B．12 C．14 D．16
10．设有向图G含有n个顶点、e条边，使用邻接表存储。对G进行深度优先搜索遍历 算法的时间复杂度是
A．O(n) B．O(口) C．O(n+e) D．O(n×e)
11．对数据序列(26，14，17，12，7，4，3)采用二路归并排序进行升序排序，两趟排序后，得到的排序结果为
A．14，26，17，l2，4，7，3 B．12，l4，l7，26，3，4，7 C．14，26，12，l7，3，4，7 D．14，26，l2，l7，3，7，4 精品文档
精品文档
12．下列选项中，不稳定的排序方法是
A．希尔排序 B．归并排序 C．直接插入排序 D．冒泡排序
13．一组记录的关键字为(35，48，47，23，44，88)，利用堆排序算法进行降序排序，建立 的初始堆为
A．23，35，48，47，44，88 B．23，35，47，48，44，88 C．35，23，47，48，44，88 D．35，23，47，44，48，88
14．一棵二叉排序树中，关键字n所在结点是关键字m所在结点的孩子，则 A．n一定大于m B．n一定小于m
C．n一定等于m D．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．1 B．2 C．3 D．4
第二部分 非选择题
二、填空题：本大题共l0小题，每小题2分，共20分。
16．数据项是具有独立含义的______标识单位。
17．指针P和q分别指向单链表L中的两个相邻结点，即q->next=P。若要在q所指结 点后插入指针r所指结点，则执行的语句是r->ne处=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．对含玎个元素的数据序列采用快速排序算法进行排序，平均时间复杂度 是_________。
24．散列存储中，常用的解决冲突的方法有开放地址法和_________两大类。 25．假设顺序存储的有序表R含有8个关键字，进行二分查找时，平均查找长度 为_________。
三、解答题：本大题共4小题，每小题5分，共20分。
26．设电文字符集是{el，e2，e3，e4，e5)，各字符出现的次数分别为{36，l3，26，l8，23}。现要为该字符集设计哈夫曼编码。请回答下列问题。 (1)给出构造的哈夫曼树。 (2)给出各字符的哈夫曼编码。 (3)计算电文编码总长。
27．已知图G采用邻接矩阵存储，邻接矩阵如题27图所示。
精品文档
精品文档
(1)根据邻接矩阵画出图G。
(2)根据图G写出从顶点A开始图G的1个深度优先搜索遍历序列。
(3)根据图G写出从顶点A开始图G的1个广度优先搜索遍历序列。
28．有数据序列(12，l7，O5，l0，20，24，45，ll，l0，l2)，使用希尔排序方法将其排成升序序列。请回答下列问题。
(1)分别写出增量为3和1的希尔排序结果。
(2)计算第一趟希尔排序中数据元素之间的总交换次数(两个 (a) 元素之间的交换记l次)。
29．设有二叉排序树T如题29图所示。现需在T中删除结点e，请 回答下列问题。
(1)画出删除后的二叉排序树(仅需画出一棵)。
(2)在你实现的删除过程中，指针域更新的次数是多少?
精品文档