哈尔滨工程学试卷
考试科目 数结构A 卷
题号
二
三
四
五
总分
分数
评卷
单项选择题（空1分15分）
1数结构中逻辑结构（ ）数结构
A．树 B．字符串 C．队列 D．栈
2序存储线性表访问结点增加删结点时间复杂度（ ）
A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1)
3六元素ABCDEF序进栈（ ）合法出栈序列
A．DEFCBA B．EDCBFA C．EFDBCA D．EDCFBA
4字符串ABCDEF子串（ ）
A．19 B．20 C．21 D．22
5序表中插入元素需均移动元素数（ ）
A．(n1)2 B．n2 C．(n+1)2 D．n1
6非空单循环链表head尾结点（P指）满足（ ）
A．p>next NULL B．pNULL C．p>nexthead D．phead
7A中序线索二叉树中结点A根A前驱( )
A．A右子树中右结点 B．A左子树中左结点
C．A右子树中左结点 D．A左子树中右结点
8某二叉树30叶子结点20结点仅孩子该二叉树中两孩子结点数（ ）
A．29 B．30 C．31 D．19
9二维数组A元素8字符组成串行标i01…9列标j12…10A行序序存储元素A[8][7]起始址A列序序存储时元素（ ）起始址相（设字符占字节）
A．A[7][9] B．A[6][8] C．A[7][8] D．A [6][9]
10图深度优先遍历算法类似二叉树（ ）
A．中序遍历 B．先序遍历 C．序遍历 D．层遍历
11图邻接表存储结构中结点数图中边数（ ）倍
A．1 B．2 C．3 D．4
12面关m阶B树说法正确（ ）
①结点少两棵非空子树
②树中结点m1关键字
③叶子层
④插入数项引起B树结点分裂树长高层
A．①②③ B．②③④ C．②③ D．③
13判定图否存回路利( )方法
A．求关键路径方法 B．广度优先遍历算法
C．求短路径Dijkstra方法 D．拓扑排序
14长度17序表折半查找法该表进行查找表元素等概率情况查找成功需均较次数（ ）
A．5317 B．5517 C．5717 D．5917
15排序方法中关键字较次数记录初始排列次序关（ ）
A．起泡排序 B．选择排序 C．快速排序 D．插入排序
二 判断题（空1分10分）
1算法设计取决数逻辑结构 ( )
2栈线性表区操作限制表两端进行操作 ( )
3稀疏矩阵压缩存储中般采三元组表示法进行存储 ( )
4空格串空串长度0 ( )
5中序线索二叉树中结点指针域空 ( )
6方便插入删数双链表存放数 （ ）
7二叉树排序树中插入新结点总插入叶结点面 ( )
8图应邻接矩阵定称矩阵图应邻接矩阵定非称矩阵 ( )
9（101223584629152277）趟简单选择排序结果序列 ( )
10快速排序速度排序方法中快 ( )
三 填空题（空1分10分）
1循环队列Q入队列时指针操作（队列长度m）________
26层衡二叉树少________结点
3广义表A((a)b(c(d)e))取出原子e操作________
4中缀表达式(A*B+(CD)E)*F(G+H)缀表达式________
5已知二叉树30叶子结点该二叉树总结点数少________
6求图生成树两种算法 算法适合求稀疏图生成树
710阶称阵A[09][110]采压缩存储方式进行存储 (行序序)首址100A[8][9]址________
8棵完全二叉树311结点叶子结点数________
9关键码序列28163212602572快速排序次划分结果
10n顶点构成环________棵生成树
四 应题（题7分35分）
1假设棵二叉树序序列CKHBIJGEFDA中序序列CBKHAIGJEDF请画出棵二叉树转换应森林
2关键字序列建立哈希表：(SUNMONTUEWEDTHUFRISAT)哈希函数H（K）（关键字中第字母字母表中序号）MOD 7线性探测法处理突求构造装填子07哈希表分计算出等概率情况查找成功均查找长度
3已知关键字序列R{11432173019}请算法步骤：
（1）构造棵哈夫曼树计算出带权路径长度WPL
（2）构造棵二叉排序树果关键字查找概率相求查找成功时均查找长度ASL
4图带权图G邻接表表示法求：
（1）结点V1出发广度遍历图G结点序列
（2）结点V1结点V8关键路径
5出组关键字{zhaoqiansunlizhouwuzhengwang}写出初始建顶堆程（关键字较字母表序准）
五算法设计题（题15分30分）
1设计算法带头结点单链表LA分解两具相结构链表LBLC中LB表结点LA表中值零结点LC表结点LA表中值零结点（链表数域元素类型整型求LBLC表利LA表结点）
2样棵二叉树表示家族中已婚男子
父子夫妻兄弟三种关系（图示）存
储结构二叉链表存储请编写查找意父
亲结点值X子算法结点结构：
typedef struct BiTNode
{ TElemType data
struct BiTNode *lchild *rchild
} BiTNode *BiTree
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
哈尔滨工程学试卷
考试科目 数结构A 卷
题号
二
三
四
五
总分
分数
评卷
单项选择题（空1分15分）
1数结构中逻辑结构（ ）数结构
A．树 B．字符串 C．队列 D．栈
2序存储线性表访问结点增加删结点时间复杂度（ ）
A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1)
3六元素ABCDEF序进栈（ ）合法出栈序列
A．DEFCBA B．EDCBFA C．EFDBCA D．EDCFBA
4字符串ABCDEF子串（ ）
A．19 B．20 C．21 D．22
5序表中插入元素需均移动元素数（ ）
A．(n1)2 B．n2 C．(n+1)2 D．n1
6非空单循环链表head尾结点（P指）满足（ ）
A．p>next NULL B．pNULL C．p>nexthead D．phead
7A中序线索二叉树中结点A根A前驱( )
A．A右子树中右结点 B．A左子树中左结点
C．A右子树中左结点 D．A左子树中右结点
8某二叉树30叶子结点20结点仅孩子该二叉树中两孩子结点数（ ）
A．29 B．30 C．31 D．19
9二维数组A元素8字符组成串行标i01…9列标j12…10A行序序存储元素A[8][7]起始址A列序序存储时元素（ ）起始址相（设字符占字节）
A．A[7][9] B．A[6][8] C．A[7][8] D．A [6][9]
10图深度优先遍历算法类似二叉树（ ）
A．中序遍历 B．先序遍历 C．序遍历 D．层遍历
11图邻接表存储结构中结点数图中边数（ ）倍
A．1 B．2 C．3 D．4
12面关m阶B树说法正确（ ）
①结点少两棵非空子树
②树中结点m1关键字
③叶子层
④插入数项引起B树结点分裂树长高层
A．①②③ B．②③④ C．②③ D．③
13判定图否存回路利( )方法
A．求关键路径方法 B．广度优先遍历算法
C．求短路径Dijkstra方法 D．拓扑排序
14长度17序表折半查找法该表进行查找表元素等概率情况查找成功需均较次数（ ）
A．5317 B．5517 C．5717 D．5917
15排序方法中关键字较次数记录初始排列次序关（ ）
A．起泡排序 B．选择排序 C．快速排序 D．插入排序
二 判断题（空1分10分）
1算法设计取决数逻辑结构 ( )
2栈线性表区操作限制表两端进行操作 ( )
3稀疏矩阵压缩存储中般采三元组表示法进行存储 ( )
4空格串空串长度0 ( )
5中序线索二叉树中结点指针域空 ( )
6方便插入删数双链表存放数 （ ）
7二叉树排序树中插入新结点总插入叶结点面 ( )
8图应邻接矩阵定称矩阵图应邻接矩阵定非称矩阵 ( )
9（101223584629152277）趟简单选择排序结果序列 ( )
10快速排序速度排序方法中快 ( )
三 填空题（空1分10分）
1循环队列Q入队列时指针操作（队列长度m）________
26层衡二叉树少________结点
3广义表A((a)b(c(d)e))取出原子e操作________
4中缀表达式(A*B+(CD)E)*F(G+H)缀表达式________
5已知二叉树30叶子结点该二叉树总结点数少________
6求图生成树两种算法 算法适合求稀疏图生成树
710阶称阵A[09][110]采压缩存储方式进行存储 (行序序)首址100A[8][9]址________
8棵完全二叉树311结点叶子结点数________
9关键码序列28163212602572快速排序次划分结果
10n顶点构成环________棵生成树
四 应题（题7分35分）
1假设棵二叉树序序列CKHBIJGEFDA中序序列CBKHAIGJEDF请画出棵二叉树转换应森林
2关键字序列建立哈希表：(SUNMONTUEWEDTHUFRISAT)哈希函数H（K）（关键字中第字母字母表中序号）MOD 7线性探测法处理突求构造装填子07哈希表分计算出等概率情况查找成功均查找长度
3已知关键字序列R{11432173019}请算法步骤：
（1）构造棵哈夫曼树计算出带权路径长度WPL
（2）构造棵二叉排序树果关键字查找概率相求查找成功时均查找长度ASL
4图带权图G邻接表表示法求：
（1）结点V1出发广度遍历图G结点序列
（2）结点V1结点V8关键路径
5出组关键字{zhaoqiansunlizhouwuzhengwang}写出初始建顶堆程（关键字较字母表序准）
五算法设计题（题15分30分）
1设计算法带头结点单链表LA分解两具相结构链表LBLC中LB表结点LA表中值零结点LC表结点LA表中值零结点（链表数域元素类型整型求LBLC表利LA表结点）
2样棵二叉树表示家族中已婚男子
父子夫妻兄弟三种关系（图示）存
储结构二叉链表存储请编写查找意父
亲结点值X子算法结点结构：
typedef struct BiTNode
{ TElemType data
struct BiTNode *lchild *rchild
} BiTNode *BiTree
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档