资源描述
学院 专业 级 学号 姓名
…………………………密……………………封……………………线………………………………
一、判断题（每小题1分，共10分）
1、算法可以没有输出语句。
2、顺序存储结构的主要缺点是插入或者删除时效率较低。
3、如果某栈的输入序列为1, 2, 3, 4, 5, 6，则可以输出1, 5, 4, 6, 2, 3。
4、多维数组可以看成是线性结构的推广，因此与线性表一样，可以进行插入、删除等操作。
5、在完全二叉树中，如果一个结点没有左孩子，则它必是叶子结点。
6、一棵树中叶子结点总数一定等于与其对应二叉树的叶子结点总数。
7、用邻接矩阵存储某图所需的存储单元数量与该图的边数有关。
8、拓扑排序算法只能适用于有向无环图。
9、顺序查找法适用于存储结构为顺序或者链接存储的线性表。
10、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
二、填空题（每小题1分，共10分）
1、数据元素之间的逻辑关系称为数据的________结构。
2、在双向循环链表中插入一个新的结点时，应修改________个指针域的值。
3、使用一个100 个元素空间的数组存储循环队列，如果采取少用一个元素空间的方法来区分循环队列的队空和队满，当队头标志front = 68, 队尾标志rear = 27 时，该队列中的元素个数为________。
4、假设某15 阶的对称矩阵A 按行优先的顺序，压缩存储在以B[0] 开始的一维数组B 中，则元素A7, 11 在B 中的存储位置为________。（注：对称矩阵元素下标从1 开始）
5、当使用二叉链表作为n 个结点二叉树的存储结构时，空指针域的个数是________。
6、设二叉树根结点的层次为1，则高度为h 的二叉树的最多可能的结点数为________。
7、在一个具有n 个顶点的无向图中，要连通全部顶点至少需要________条边。
8、某无向图具有n 个顶点e 条边，当使用邻接表表示时，邻接表中边结点的个数为________。
9、对任一m 阶的B- 树，每个结点中最多包含________个关键字。
10、用希尔排序对关键字序列(98, 36, 9, 0, 47, 23, 1, 8, 10, 7) 排序，增量序列依次是4, 2, 1，则排序共进行________趟。
三、单项选择题（每小题2分，共30分）
学院 专业 级 学号 姓名
1、如果一个算法的时间复杂度用T(n) 表示，则其中n 的含义是________。
…………………………密……………………封……………………线………………………………
A、问题规模 B、语句条数 C、循环层数 D、函数数量
2、在长度为n 的顺序表中删除第i 个元素(1 ≤ i ≤ n) 时，元素移动的次数为________。
A、n – i + 1 B、i C、i + 1 D、n – i
3、设非空带头结点的单循环链表头指针为head，则指针变量p 指向尾结点的条件是________。
A、p->next->next == head B、p->next == head
C、p->next->next == NULL D、p->next == NULL
4、栈是一种操作受限的线性结构，其操作的主要特征是________。
A、先进先出 B、后进先出 C、进优于出 D、出优于进
5、引起循环队列队头位置发生变化的操作是________。
A、出队 B、入队 C、取队头元素 D、取队尾元素
6、设10 × 12 的二维数组A 按“行优先顺序”存储，每个元素占1个存储单元，已知A[1][1] 的存储地址为420，则A[5][5] 的存储地址为________。
A、470 B、471 C、472 D、473
7、对于广义表A，如果head(A) 等于tail(A)，则表A为________。
A、( ) B、(( )) C、(( ), ( )) D、(( ), ( ), ( ))
8、已知一棵含50 个结点的二叉树中只有一个叶子结点，则该树中度为1 的结点个数为________。
A、0 B、1 C、48 D、49
9、使用线索二叉树的目的是便于________。
A、在二叉树中插入或者删除结点
B、在二叉树中查找双亲
C、确定二叉树的高度
D、查找某结点在遍历序列中的前趋和后继
10、无向完全图G 有n 个顶点，则其边的总数为________条。
A、n2 B、n(n – 1) C、n(n – 1) / 2 D、n – 1
11、如右图所示的有向图可以排出________种不同的拓扑序列。
A、 5 B、6 C、12 D、其它
12、要输出二叉排序树结点的有序序列，则可以采用的遍历方法是________遍历。
A、按层 B、先序 C、中序 D、后序
13、下列查找方法中，平均查找长度与关键字数量n 不直接相关的查找方法是________查找。
A、分块 B、顺序 C、折半 D、哈希
14、用“大数下沉”的冒泡排序法对初始关键字序列(8, 13, 26, 55, 29, 44) 递增排序，第一趟排序时关键字需要交换________次。
A、2 B、3 C、4 D、5
15、下列关键字序列中，构成小根堆的是________。
A、(84, 46, 62, 41, 28, 58, 15, 37)
B、(84, 62, 58, 46, 41, 37, 28, 15)
C、(15, 28, 46, 37, 84, 41, 58, 62)
D、(15, 28, 46, 37, 84, 58, 62, 41)
…………………………密……………………封……………………线………………………………
学院 专业 级 学号 姓名
四、综合应用题（每小题6分，共30分）
1、已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF：
1) 画出该二叉树； 2) 写出该二叉树的后序序列。
2、假设通信电文使用的字符集为{a, b, c, d, e, f, g, h}，各字符在电文中出现的频度分别为：7, 26, 2, 28, 13, 10, 3, 11，试为这8个字符设计Huffman 编码。
1) 画出该Huffman 树(左孩子权值不大于右孩子权值)；
2) 按左分支0、右分支1，分别写出各字符的编码。
3、某有向图的邻接表如右图，分别写出从顶点A 出发进行深度优先遍历和广度优先遍历的序列。
4、对关键字序列 (5, 8, 1, 3, 9, 6, 2, 7, 4, 0) 进行递增快速排序，以最左元素为基准，写出排序过程中第一趟的划分结果。
5、设带权无向图如右图所示，用Prim 算法从顶点a 开始求得最小生成树，请写出算法的每一步结果。
五、算法设计题（每小题10分，共20分）
1、编写完整的算法，原地逆置顺序表L 中的元素，顺序表的类型声明和算法的原型如下：
typedef struct
{ // 顺序表的类型声明
ElemType *elem; // 存储空间基址
int length; // 顺序表当前长度
int listsize; // 当前分配的存储容量
} SqList;
void Reverse(SqList &L); // 逆置函数原型
2、设二叉树以二叉链表为存贮结构，设计算法统计二叉树中度为1 的结点个数。二叉树的类型声明和算法的原型声明如下：
typedef struct BiTNode
{ // 二叉链表的类型声明
TElemType data;
struct BiTNode *lchild,*rchild; // 左右孩子指针
} BiTNode, *BiTree;
int Count(BiTree T); // 统计函数原型，T 指向根结点
13-14-1《数据结构》A卷参考答案
一、判断题（10 × 1 = 10分）
´ Ö ´ ´ Ö ´ ´ Ö Ö ´
二、填空题（10 × 1 = 10分）
1、逻辑 2、4
3、59 4、B[61]
5、n + 1 6、2h – 1
7、n – 1
8、2e
9、m – 1
10、3
三、单项选择题（15 × 2 = 30分）
A D B B A C B D D C C C D A D
四、综合应用题（5 × 6 = 30分）
1、二叉树（3分）、后序DHEBIFCA（3分）
2、Huffman 树（3分）、Huffman 编码共（3分）
字符
编码
字符
编码
a
0101
e
011
b
10
f
000
c
01000
g
01001
d
11
h
001
3、深度优先：ABCED；广度优先：ABCDE
（每个遍历序列3分）
4、(0, 4, 1, 3, 2, 5, 6, 7, 9, 8) （6分）
5、Prim 算法步骤 (6分)
第一步
第二步 第三步 第四步 第五步
五、算法设计题（2 × 10 =20分）
1、 （本题共10分）
void Reverse(SqList &L)
{ // 原地逆置顺序表L 中的元素
int i, j;
ElemType temp; // 交换用中间变量 （2分）
for (i = 0, j = L.length – 1; i < j; ++ i, -- j)
{ // i 当前最左元素下标，j 当前最右元素下标 （3分）
temp = L.elem[i]; （5分）
L.elem[i] = L.elem[j];
L.elem[j] = temp;
}
}
2、 （本题共10分）
int Count(BiTree T)
{ // 使用先序遍历
int count = 0; （1分）
if (T) （2分）
{
if (! T->lchild && T->rchild || T->lchild && ! T->rchild)（3分）
++ count;
count += Count(T->lchild) + Count(T->rchild); （3分）
}
return count; （1分）
}
作为一名测量人员，xx认真履行岗位职责，紧密配合施工，制定切实可行的的测量放线方案。保罗回忆自己年少时癿经历，丌断怃耂生命、医疗、道德不哲学乊间癿兰系，丌仅为从医考提供了新规觇，使他们对自己癿职业呾使命有更为深入癿怃耂，耄丏为读考引路，觑人们更勇敢、沉着地看待生命、死亜不未来。situation, causing the livelihood of 100 tailings project management project and South Mining Technology in two engineering work lag. Corrective measures: (LED Leadership: Luo Mingjun, rectification time: before September 25th, insist for a long time) 1, strictly abide by the party's political discipline. Strictly abide by the constitution, the principle of Party organization and party political life standards, do not spread against the party's theory and policy advice, not contrary to published The central and provincial Party committee decided to talk, not to divulge the secrets of the party and the state, do not make no illegal organization and participate in various activities, political, spread rumors and false information, not to publish lossy unity of speech, do not damage the unity of things, and never allow individuals above the organization. 2, adhere to the scientific and democratic decision-making the decision to make decisions. Correctly handle to ensure that government decrees and based on the actual creative work, giving full play to subjective initiative, put an end to implement the conference meeting, to document the implementation of documents and so on. To improve the scientific and democratic decision-making mechanism, improve and implement the decision to solicit opinions, experts, public hearings and other health system. All major decisions before the risk assessment mechanism and legitimacy review mechanism. Adhere to the interests of the masses and the intention reflected in the policy making process and carry out the work, not acting on their behalf, "across the board" and coercion. (two) the existence of "negative communication" or unwilling to communication problems due to maintenance party team unity. The team members of the division of responsibilities, temperament, interestsDifferences in demand, often leads to different views, different opinions. Individual members of organization and coordination ability, team spirit is not good, work style is not real, simple working methods, lack of knowledge of the wisdom of the people, forgiveness and art for the people, can not deal with different opinions, there are "self sweep the snow in front of the door, all kinds of responsibility fields". Some members of the team division of work coordination, lack of coordination, as extreme liberalization, did not form a work force. In addition, individual cadres lack of leadership training, love "command communication", "negative communication", talk in the work did not take the initiative to talk not correct The science team differences, resolve conflicts. Corrective measures: (LED Leadership: Luo Mingjun, rectification time: before September 25th, insist for a long time) 1, to further strengthen the education and guidance on the implementation of the central eight provisions, the provincial nine provisions of the county committee of the "ten provisions" extensive publicity, eliminate the ideological
A－7 共 8 页
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
