(总分：100.00，做题时间：150分钟)
一、课程**：02331 (总题数：15，分数：30.00)
1.数据的四种存储结构是( )
分数：2.00）
a.顺序存储结构、链接存储结构、索引存储结构和散列存储结构√
b.线性存储结构、非线性存储结构、树型存储结构和图型存储结构。
c.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构。
d.顺序存储结构、树型存储结构、图型存储结构和散列存储结构。
解析：2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是( )
分数：2.00）
a.无头结点的单向链表。
b.带头结点的单向链表。
c.带头结点的双循环链表√
d.带头结点的单循环链表。
解析：3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( )
分数：2.00）
next=null√
next!=head
解析：4.若元素的入栈顺序为1，2，3...n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)个元素是( )
分数：2.00）
d.无法确定√
解析：5.串匹配算法的本质是( )
分数：2.00）
a.串复制。
b.串比较。
c.子串定位√
d.子串链接。
解析：6.设有一个10阶的对称矩阵a，采用行优先压缩存储方式，a11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a85的地址为( )
分数：2.00）
a.13b.18
c.33√d.40
解析：7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( )
分数：2.00）
a.树中没有度为2的结点。
b.树中只有一个根结点√
c.树中非叶结点均只有左子树。
d.树中非叶结点均只有右子树。
解析：8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是( )
分数：2.00）
b. c.
解析：9.在图g中求两个结点之间的最短路径可以采用的算法是( )
分数：2.00）
a.迪杰斯特拉（dijkstra）算法√
b.克鲁斯卡尔（kruskal）算法。
c.普里姆(prim)算法。
d.广度优先遍历(bfs)算法。
解析：10.下图g=(v,e)是一个带权连通图，g的最小生成树的权为( )
分数：2.00）
a.15b.16
c.17d.18√
解析：11.在下图中，从顶点1出发进行深度优先遍历可得到的序列是( )
分数：2.00）
a.1 2 3 4 5 6 7
b.1 4 2 6 3 7 5√
c.1 4 2 5 3 6 7
d.1 2 4 6 5 3 7
解析：12.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( )
分数：2.00）
a.不稳定的。
b.稳定的√
c.基于交换的。
d.基于选择的。
解析：13.设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数h(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为( )
分数：2.00）
a.1b.2
c.3√d.4
解析：14.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( )
分数：2.00）a.b.√
c.d.
解析：15.若需高效地查询多关键字文件，可以采用的文件组织方式为( )
分数：2.00）
a.顺序文件。
b.索引文件√
c.散列文件。
d.倒排文件。
解析：二、填空题（本大题共10小题，每小题2分，共20分） (总题数：10，分数：20.00)
16.下面程序段的时间复杂度为 1。 sum=1； for（i=0；sum
分数：2.00）
填空项1正确答案：o（n））
解析：17.已知链表结点定义如下： typedef struct node linkstrnode； 如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是 1。
分数：2.00）
填空项1正确答案：4/5（或0.8））
解析：18.使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。
若为front=8，rear=7，则队列中的元素个数为 1。
分数：2.00）
填空项1正确答案：99）
解析：19.3个结点可以组成 1种不同树型的二叉树。
分数：2.00）
填空项1正确答案：5）
解析：20.用5个权值构造的哈夫曼(huffman)树的带权路径长度是 1。
分数：2.00）
填空项1正确答案：33）
解析：21.若无向图g中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为 1。
分数：2.00）
填空项1正确答案：2m）
解析：22.影响排序效率的两个因素是关键字的 1次数和记录的移动次数。
分数：2.00）
填空项1正确答案：比较）
解析：23.对任一m阶的b树，每个结点中最多包含 1个关键字。
分数：2.00）
填空项1正确答案：m-1）
解析：24.若两个关键字通过散列函数映射到同一个散列地址，这种现象称为 1。
分数：2.00）
填空项1正确答案：冲突（或碰撞））
解析：25.如果要为文件中的每个记录建立一个索引项，则这样建立的索引表称为 1。
分数：2.00）
填空项1正确答案：稠密索引）
解析：三、解答题（本大题共4小题，每小题5分，共20分）(总题数：4，分数：20.00)
要在［0..n-l］的向量空间中建立两个栈stackl和stack2，请回答：（分数：5.00）
1).应该如何设计这两个栈才能充分利用整个向量空间？（分数：2.50）
正确答案：()
解析：2).若stackl的栈顶指针为topl,stack2的栈顶指针为top2，如果需要充分利用整个向量空间，则：
栈stackl空的条件是栈stack2空的条件是栈stackl和栈stack2满的条件是分数：2.50）
正确答案：()
解析：已知广义表如下： a=(b,y) b=(x，l) l=(a，b) 要求： （分数：5.00）
1).写出下列操作的结果 tail(ahead(b分数：2.50）
正确答案：()
解析：2).请画出广义表a对应的图形表示。（分数：2.50）
正确答案：()
解析：26.已知二叉树如下： 请画出该二叉树对应的森林。
分数：5.00）
正确答案：()
解析：请回答下列问题：（分数：5.00）
1).英文缩写dag的中文含义是什么？（分数：2.50）
正确答案：()
解析：2).请给出下面dag图的全部拓扑排序。 （分数：2.50）
正确答案：()
27.已知线性表(a1,a2,a3...an)按顺序存放在数组a中，每个元素均为整数，下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。
例如，有7个整数的原始序列为(x,x,-x,-x,x,x,-x)，变换后数组中保存的序列是(-x,-x,-x,x,x,x,x)。请在程序处填入合适的内容，使其成为完整的算法。 f30(int a［］，int n) {int k，m,temp； m= (1) ；while (a［m］=0&&k
分数：5.00）
全国高等教育自学考试数据结构导论试题
全国2002年10月高等教育自学考试数据结构导论试题课程 02142 一 单项选择题 在下列每小题四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。每小题2分，共30分 1 下列数据组织形式中，的结点按逻辑关系依次排列形成一个 锁链 a.集合b.树形结构。c.线性结构d.图状结构。2 ...
自学考试《数据结构》复习指导
一 概念 是一门研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。数据 是描述额观事物的数 字符以及所有能输入到计算机中被计算机程序加工处理的信息的集合。数据元素 数据元素是数据的基本单位。一个数据项或多个数据项 域 数据项是数据的最小单位。结点 顶点 记录。数据对象 是性质相同的数...
全国数据结构导论试题
全国2011年10月数据结构导论试题课程 02142 一 单项选择题 本大题共15小题，每小题2分，共30分 1.设栈s和队列q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈s，元素退栈后即进入队列q，若6个元素的出队序列是e2，e4，e3，e6，e5，e1，则栈s的容量至少为 a...