专业年级学号。
姓名成绩。一、 选择题（本题共25分）
1. （1分）简单队列对数据处理的方式是。
a. 先来先服务 b. 后来先服务。
c. 先来后服务 d. 以上均不对。
2. （2分）下面哪些问题的求解应用了栈。
a．函数调用时保存函数的参数、局部变量等。
b．检查括号匹配。
c．图的宽度优先搜索。
d．基于深度优先搜索的图的拓扑排序过程。
3. （2分）通过相邻元素比较－交换进行排序的算法，如插入排序、起泡排序等，其平均时间复杂性最好只能达到。
a．(n) b．(nlogn)
c．(n2) d．(n3)
4. （2分）基数排序要求每阶段的排序算法是。
a．稳定的 b．不稳定的。
c．a、b皆可 d．以上均不对。
5. （2分）f(n)=o(n)，g(n)=o(n)，下面哪些等式成立。
a．f(n)+g(n) =o(n) b．f(n)-g(n) =o(n)
c．f(n)/g(n) =o(1) d．f(n) =o(g(n))
6. （2分）采用hash技术，下面哪些操作性能不佳。
a．搜索给定关键字。
b．按关键字升序排列输出所有元素。
c．删除给定关键字的元素。
d．输出关键字升序排列位于第k位的元素。
7. （4分）7个关键字的4阶b-树有几种可能的结构。
a．8 b．9
c．10 d．11
8. （2分）二叉搜索树中一个节点两棵子树均非空，删除它可转换为删除或。
a．该节点的左子树的最左节点。
b．该节点的左子树的最右节点。
c．该节点的右子树的最左节点。
d．该节点的右子树的最右节点。
9. （2分）设有一个双端队列deque，允许在队列的两端进行插入和删除操作。可以形象地把双端队列看作是两个对底的栈。
设双端队列的输入顺序是1,2,3,4,5,6，以下结果中不可能是双端队列的输出结果。
a. 1 2 3 4 5 6 b. 2 4 3 6 5 1
c. 1 5 2 4 3 6 d. 4 2 1 3 5 6
e. 1 2 6 4 5 3 f. 5 2 6 3 4 1
10. （3分）下述编码具有前缀特性：
a. a=0, b=1, c=01, d=10, e=11, f=100
b. a=0, b=10, c=1111, d=11101, e=111101, f=110
c. a=1110, b=101, c=01, d=10, e=11, f=100
d. a=0, b=1, c=01, d=011, e=11, f=110
11. （3分）以下序列是堆？
a.｛100，86，48，73，35，39，42，57，66，21｝
b.｛12，70，33，65，24，56，48，92，86，33｝
c.｛103，97，56，38，66，23，42，12，30，52，6，26｝
d.｛5，56，20，23，40，38，29，61，35，76，28，100｝
二、 画出下面程序段运行过程中，栈mystack的变化情况，假定初始时为空（本题共5分）
integer num =
integer num =
三、 对下面的整数列表，利用基数排序算法整理为递增序列，写出每趟分配收集的过程，及最终排序结果（本题共6分）
四、 一个反对称矩阵a是一个n×n的矩阵，且对所有满足，即（）。为反对称矩阵设计高效的存储方案，使用一个一维数组a保存它。（本题共6分）
五、 对下面这棵树，回答下列问题。（本题共14分）
1) （2分）指出根节点和叶节点。
根节点。叶节点。
2) （2分）指出节点d的父节点、孩子节点和兄弟节点。
父节点。孩子节点。
兄弟节点。3) （4分）将它转换为二叉树。
4) （6分）给出转换后的二叉树的先序、中序和后序遍历的结果。
先序遍历。中序遍历。
后序遍历。六、 一个文件**现的字符及它们出现的频率如下表所示，为它们构造huffman编码，需要画出huffman树。（本题共8分）
七、 对下面aoe，回答下列问题。（本题共16分）
1) （8分）求出每个事件和每个活动的最早开始时间和最迟开始时间；
2) （2分）完成该工程至少需要多少时间。
3) （4分）求出该工程的所有关键活动；
4) （2分）求出该工程的关键路径。
八、 漏失栈（drop-out stack）的动作与栈很类似，只是当已经保存最大个数元素（n）时，如果第n+1个元素入栈，则栈底的元素丢失。使用循环数组实现漏失栈，试完成入栈、出栈操作。（本题共8分）
九、 有一种起泡排序算法的变形称为gap（间隔）排序，每次扫描表时它不是比较表中相邻的元素，而是比较位置相隔某个值（i）的元素，其中i是小于n的一个整数。例如，第一个元素应与第(i+1)个元素进行比较，第二个元素应与第(i+2)个元素进行比较，第n个元素应与第(n-i)个元素进行比较，等等。当所有能比较的元素都比较过时，完成一次迭代。
下一次迭代中，i减去一个大于1的一个值，继续这个过程，直到i小于1时为止。（本题共12分）
2019试卷数据结构A卷
济南大学2012 2013学年第一学期课程考试试卷 a卷 课程数据结构授课教师。考试时间 201 年月日考试班级。学号姓名。一 选择题 每小题2分，共40分 1 对顺序存储的线性表，设长度为n，在任何位置上插入或删除操作都是等概率的，删除一个元素时平均要移动表中的 个元素。a b cd n 2设一条...
数据结构 I卷
班级学号姓名得分。题目部分，卷面共有45题，100分，各大题标有题量和总分 一 判断正误 11小题，共11分 1 即使对不含相同元素的同意输入序列进行两组不同的 合法的入栈和出栈组合操作，所得的输出序也一定相同。2 栈和队列都是限制存取点的线性结构。3 任何一个非空广义表，其表头可能是单元素或广义表...
2019《数据结构》期末试卷A卷
一 本题10分 1 线性表和广义表的主要区别是什么？2 已知广义表 c a,b,a,b a,b a,b 则tail head tail c 二 本题10分 简述二叉树的两种存储结构 顺序存储和链式存储 的数据结构及主要优缺点。在哈夫曼树中，使用哪种存储结构，并说明理由。三 本题10分 一棵二叉树的先...