数据结构期末考试试卷（a）答案。
一、 单项选择题：（每小题2分，共计20分）
1、 栈和队列的共同特点是( a )。
a. 只允许在端点处插入和删除元素。
b. 都是先进后出。
c. 都是先进先出。
d. 没有共同点。
2、 指针q指向单链表中结点a，指针p指向单链表中结点a的后继结点b，指针s指向被插入的结点x，则在结点a和结点b之间插入结点x的操作序列为（b ）。
a. (a) s->next=p->next；p->next=s；
b. (b) q->next=s； s->next=p；
c. (c) p->next=s->next；s->next=p；
d. (d) p->next=s；s->next=q；
3、 若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（d）
a 上三角矩阵
b 稀疏矩阵
c 对角矩阵
d 对称矩阵。
4、 用链表表示线性表的优点是（c）
a 便于随机存取
b 花费的存储空间比顺序表少。
c 便于插入与删除
d 数据元素的物理顺序与逻辑顺序相同。
5、深度为6（根的层次为1）的二叉树至多有（ b ）个结点。
a. 64b. 63
c. 31d. 32
6、 一棵二叉树具有8个度为2 的结点，则该二叉树的叶子数是：c
a. 16
b. 7 c. 9
d. 不确定。
7、折半查找法查找一个表长为10的线性表，当表中没有要查的数据时，最多要比较多少次（ c ）
a．5 b. 2 c. 4 d. 1
8、设某二叉树有2000个结点，请问该树最小高度是多少？（注：约定树根高度为1）c
a. 9 b.10 c. 11d. 12
9、关键路径是事件结点网络中（ c ）
a. 最短的回路。
b. 最长的回路。
c. 从开始结点到完成结点的最长路径。
d. 从开始结点到完成结点的最短路径。
阶对称矩阵a，以行序为主压缩存储后，a11的地址为1，a85的地址为：b
a. 13b. 33
c. 18d. 40
二、 填空题（每小题2分，共计20分）
1、已知一颗度为3的树，每个结点的结构中均有3个指针域，那么有n个结点的这样一棵树会有多少指针域是浪费的 （ 2n+1 ）。
2、对一个有100个数据结点的完全二叉树从上到下，从左到右用1到100进行标注，那么27号结点的双亲结点的标号是 （ 13 ） 左孩子的标号是（ 54 ）右孩子的标号是 （ 55 ）
3、拓扑排序不是一种内部排序方法，它只是为了验证一个 （ aov ） 网中是否存在 （ 环 ）
4、已知一个无向图的邻接表如下图。
请问其中v3点的入度是 （ 2 ），出度是 （ 2 ）。如果对该图进行深度优先遍历可能得到的结果是： （12534 ），对该图的广度优先可能得到的结果是 （ 12453 ）。
三、 操作题（每小题8分，共计40分）
1、 给定权值，构造相应的哈夫曼树，要求写出构造步骤。
2、 已知一表为（38,25,46,30,52,21,47），试按表中数据顺序依次画出构造的二叉排序树。然后对这棵二叉排序树进行前序遍历，中序遍历和后序遍历，并分别写出遍历的输出结果。
前序：38,25,21,30,46,52,47
中序：21,25,30,38,46,47,52
后序：21,30,25,47,52,46,38
3、 下图表示一个地区的交通网，顶点表示城市，边表示城际公路，边上的权代表运费，怎样构造运输网络图才能使整个城市网络中总运价最省，试画出所有可能的方案。
4、 已知一组数据为49,38,65,97,76,13,27，请写出采用快速排序的每一趟结果，直至算法结束。
5、 已知一组数据为6,4,1,2,8,4,7,3,0,9，请首先建立初始小顶堆，然后画出每一趟堆排序的中间结果。
建初始堆正确给4分。
没有建初始堆，给出正确的排序结果也不得分。
四、 综合题（每小题10分， 共计20分）
1、 编写算法，生成带头结点的在单链表。要求从键盘上输入数据，形成结点，并按照输入数据在链表中从小到大的顺序插入到合适的位置，如果恰好链表中已有相同数值的结点，则在该结点之前插入新的结点。
给分点：正确建立单链表 5
正确循环查找正确位置 2
正确插入 3分。
2、 前几年微软公司对前来应聘的人员出了一道试题，问，怎样编写一个算法判断一个字符串是否是对称的？请你写出相应的算法。
给分点：使用数组前后比较可以算作正确。
最好使用栈。
2019数据结构A卷
数据结构 试卷a 1.算法的时间复杂度取决于 问题的规模 待处理数据的初态和 的长短。2 从逻辑上可以把数据结构分为 两大类。动态结构 静态结构 顺序结构 链式结构 线性结构 非线性结构 初等结构 构造型结构。3.对于栈操作数据的原则是。先进先出 后进先出后进后出不分顺序。4.一个栈的输入序列为12...
数据结构卷二
姓名。班级学号。系部名称。专业名称。数据结构 试题 卷二 适用班级 2012 2013学年第二学期期末试题。一 单项选择题 每小题1分，共15分 1.下面程序段的时间复杂度是 a s 0 for i 0 is a i a o nb o 1c o 0 d o n2 2.在以下的叙述中，正确的是 c a...
数据结构试题 A卷2019 答案
2012 2013学年第一学期期末考试。数据结构 试题a答案。一 选择 每空2分，共30分 bcdbd bccbb cabbc 二 1.答 1 应选择链式存储结构。它可动态申请内存空间，不受表长度 即表中元素个数 的影响，插入 删除时间复杂度为o 1 2 应选择顺序存储结构。顺序表可随机存取，时间复...