目录
目录 1
选择题 2
第章绪 2
第二章 线性表 4
第三章 栈队列 5
第四章 串 6
第五章 数组广义表 7
第六章 树二叉树 7
第七章 图 9
第八章 查找 11
第九章 排序 12
简答题 15
第章绪 15
第二章 线性表 20
第三章 栈队列 22
第四章 串 24
第五章 数组广义表 24
第六章 树二叉树 26
第七章 图 31
第八章 查找 33
第九章 排序 34
编程题 36
第章绪 36
第二章线性表 36
第三章 栈队列 46
第四章 串 46
第五章 数组广义表 46
第六章 树二叉树 46
第七章 图 46
第八章 查找 46
第九章 排序 51
选择题
第章绪
1 数结构门学科针什问题产生?(A )
A针非数值计算程序设计问题 B针数值计算程序设计问题
C数值计算非数值计算问题针 D两者针
2 数结构门学科研究容面选项准确(D )
A研究数象数间关系 B研究数象
C研究数象数操作 D研究数象数间关系操作
3 某班级学生成绩表中查张三学科成绩记录中数结构考90分面关数象数元素数项描述正确(C )
A某班级学生成绩表数元素90分数项
B某班级学生成绩表数象90分数元素
C某班级学生成绩表数象90分数项
D某班级学生成绩表数元素90分数元素
4 *数结构指(A )
A数元素组织形式 B数类型
C数存储结构 D数定义
5 数计算机存储器表示时物理址逻辑址相称(C )
A存储结构 B逻辑结构
C链式存储结构 D序存储结构
6 算法分析目(C )
A找出数合理性 B研究算法中输入输出关系
C分析算法效率求改进 D分析算法易懂性文档型性
7 算法分析方法(A )
A空间复杂度时间复杂度 B正确性简明性
C读性文档性 D数复杂性程序复杂性
8 计算机部处理基单元(B )
A数 B数元素 C数项 D数库
9 数计算机链式序两种存储方式存储空间灵活性链式存储序存储(B )
A低 B高 C相 D说
10 算法时间复杂度取决( C )
A 问题规模 B处理数初始状态
C问题规模处理数初始状态 D说
11 数结构研究数逻辑结构研究物理结构种观点(B )
A正确 B错误
C前半句半句错 D前半句错半句
12 数结构中逻辑数结构分成( C )
A动态结构静态结构 B紧凑结构非紧凑结构
C线性结构非线性结构 D部结构外部结构
13 线性表序存储结构种( )存储结构线性表链式存储结构种( A )存储结构
A机存取 B序存取
C索引存取 D散列存取
14 *列程序时间复杂度(A )
for (i1 i
}
}
AO(n2) BO(n) CO(2n) DO(2n2)
15 *列程序空间复杂度(A )
for (i1 i
}
}
AO(m*n) BO(m+n) CO(mn) DO(mn)
16 *求列程序段时间复杂度( B )
for( i1 i
AO(n2) BO(n) CO(1) DO(0)
第二章 线性表
1 关线性表说法正确?(D )
A存唯称第数元素(开始结点)
B存唯称数元素(终端结点)
C第外集合中数元素均前驱
D第外集合中数元素均继
2 关序表说法正确?(D )
A逻辑关系相邻两元素物理存储位置相邻
B机存取表中元素方便快捷
C线性表中插入某元素时需移动量元素
D线性表中删某元素时需移动量元素
3 线性表元素总数基稳定少进行插入删操作求快速度存取线性表中元素时应采什存储结构?(A )
A序表 B单链表 C循环链表 D双链表
4 长度n序表中第i元素(1An1 Bni Cni+1 Dni1
5 单链表中设置头结点作( )
A单链表定义已 B指定表起始位置
C双链表做准备 D循环链表做准备
6 根线性表链式存储结构中结点包含指针数线性链表分成(C )
A单链表循环链表 B单链表十字链表
C单链表双链表 D循环链表链表
7 链接存储特点利什表示数元素间逻辑关系(A )
A引 B串联 C挂接 D指派
8 已知指针p指单链表L中某结点删继结点语句(D )
Ap pnext Bp null Cpnextnull Dpnext pnextnext
9 *单链表L中指针p指结点继结点条件(B )
Ap pnext Bpnextnull
Cpnextnull Dpnext pnextnext
10 *单链表p结点插入s结点操作(C )
Apnexts snextpnext Bsnext pnext pnextpnextnext
Csnext pnext pnext s Dsnextp pnexts
第三章 栈队列
1 栈队列通常采两种存储结构(B )
A散列方式索引方式 B序存储结构链式存储结构
C链表存储结构数组 D 线性非线性存储结构
2 栈入栈序列abcd 栈输出序列(C )
Adcba Bcdba Cdcab Dabcd
3 判断序栈(结点数m)栈满条件(D )
Atop0 B topm C top0 Dtopm
4 栈存取数原(栈特点)(B )
A进出 B进先出 C先进先出 D意进出
5 *栈运算x值(A )
InitStack(s)
Push(sd)
Push(se)
Pop(sx)
Pop(sx)
GetTop(sx)
A d B e C x D s
6 队列进队序列:abcd出队序列: ( A )
Aabcd B dcba
Cadcb D cbda
7 循环队列空队列条件:(D)
AQfront0 B Q(rear+1)MaxSizeQfront
C Qrear0 D QrearQfront
8 存储结构果带头节点单链表实现队列(假定frontrear分队首队尾指针)删结点操作(A )
Afrontnextfrontnextnext Brearrearnext
Crearfrontnext Dfront frontnext
9 栈队列点(C )
A先进出 B先进先出
C允许端点处进行操作线性表 D点
10 插入删端进行线性表(B )
A循环队列 B栈
C队列 D循环栈
11 插入删分两端端进行线性表(C )
A循环队列 B栈
C队列 D循环栈
12 循环队列满队列条件:(B )
AQfront0 B Q(rear+1)MaxSizeQfront
C Qrear0 D QrearQfront
第四章 串
1 关串叙述错误:(B )
A.串字符限序列 B.空串空格构成串
C.模式匹配串重运算 D.串序链式两种存储方式
2 串长度指(B )
A.串含字母数目 B.串含字符数目
C.串含字符数目 D.串含非空格字符数目
3 *串Sdatabase子串数目(B )
A.16 B.37 C.8 D.36
4 设串S1串S子串求S1S中定位运算称(B )
A.求子串 B.串匹配 C.联接 D.求串长
5 设串s1welcome to zdsoft colleages2sos2s1中索引位置(C )
A.12 B.14 C.13 D.10
6 *串Ssoftware子串数目(B )
A.8 B.37 C.36 D.9
第五章 数组广义表
第六章 树二叉树
1 假设棵二叉树中双分支结点数15单分支结点数30叶子结点数( B )
A 15 B 16 C 17 D 47
2 假定棵三叉树结点数50高度(C )
A 3 B 4 C 5 D 6
3 棵二叉树第4层结点数(D )
A 2 B 4 C 6 D 8
4 序存储方法完全二叉树中结点逐层存放数组中R[1n]结点R[i]左孩子左孩子编号结点(B )
A R[2i+1] B R[2i] C R[i2] D R[2i1]
5 设n m 棵二叉树两结点中序遍历序列中nm前条件(B )
A nm右方 B nm 左方
C nm祖先 D nm子孙
6 面叙述正确(D )
A 二叉树特殊树
B 二叉树等价度2树
C 完全二叉树必满二叉树
D 二叉树左右子树次序分
7 现深度5二叉树请问( D )结点
A 32 B 5 C30 D 31
8 现深度4二叉树请问( A )结点
A 15 B 16 C17 D6
9 棵二叉排序树( B )遍历结点序列序序列
A 先序 B 中序 C序 D头序
10 棵二叉树中度0结点数n0度2结点数n2n0( C )
A n+1 B n+2 Cn2+1 D2n+1
11 三结点构成二叉树(B )种形态
A 4 B 5 C6 D7
12 棵含n结点树( A )形态达深度
A 单支树 B 二叉树 C三 叉树 Dn叉树
13 含结点空树( C )
A棵树 B棵二叉树
C棵树棵二叉树 D树二叉树
14 二叉树非线性数结构( C )
A序存储结构存储 B链式存储结构存储
C序存储结构链式存储结构存储
D序存储结构链式存储结构
15 具n(n>0)结点完全二叉树深度(C )
Alog2(n)ù B log2(n)û C[ log2(n) ] +1 Dlog2(n)+1ù
16 棵三元树中度3结点数2度2结点数1度1结点数2度0结点数(D )
A 4 B 5 C6 D7
17 关二叉树列说法正确(B )
A.二叉树度2 B.棵二叉树度2
C.二叉树中少结点度2 D.二叉树中结点度2
18 完全二叉树中结点叶结点没(C )
A.左子结点 B.右子结点
C.左子结点右子结点 D.左子结点右子结点兄弟结点
19 列情况中称二叉树(B )
A.结点两棵子树树 B 哈夫曼树
C.结点两棵子树序树 D 结点棵右子树
第七章 图
1 图深度优先遍历类似二叉树( A )
A.先序遍历 B.中序遍历 C.序遍历 D.层次遍历
2 已知图图示顶点a出发深度优先遍历种顶点序列(C )
A.abecdf B.acfebd C.aebcfd D.aedfcb
3 图意顶点出发进行次深度优先搜索访问图中顶点该图定( B )图
A.非连通 B.连通 C.强连通 D.
4 图中顶点度数等边数( C )倍
A 12 B 1 C 2 D 3
5 图中顶点入度等顶点出度( B )倍
A 12 B 1 C 2 D 3
6 N顶点图( B )条边
A N B N(N1) C N(n1)2 D 2N
7 具4顶点完全图( A )条边
A 6 B 12 C 18 D 20
8 具6顶点图少( A )条边确保连通图
A 5 B 6 C 7 D 8
9 具N顶点图采邻接矩阵表示该矩阵(D )
A N B (N1)2 C N1 D N*N
10 具N顶点图中连通全部顶点少( C )条边
A N B N+1 C N1 D N2
11 *已知图邻接矩阵图示顶点0出发深度优先遍历结果( C )
A.0 2 4 3 1 5 6 B.0 1 3 6 5 4 2 C.0 1 3 4 2 5 6 D.0 3 6 1 5 4 2
12 已知图邻接表图示顶点0出发广度优先遍历结果( )深度优先遍历结果( D )
A.0 1 3 2 B.0 2 3 1 C.0 3 2 1 D.0 1 2 3
13 已知图邻接表图示顶点0出发广度优先遍历结果( )深度优先遍历结果( )
A.0 1 3 2 B.0 2 3 1 C.0 3 2 1 D.0 1 2 3
14 序序表查找数时折半查找序查找前者者查找速度( C )
A.必定快 B.定
C.部分情况快 D.取决表递增递减
15 折半查找序表(4610122030507088100)查找表中元素58次表中( A )较查找结果失败
A.20703050 B.30887050
C.2050 D.308850
第八章 查找
1 序查找法适合存储结构(B )线性表
A.散列存储 B.序存储链式存储
C.压缩存储 D.索引存储
2 查找程中时增删工作种查找称( B )
A 静态查找 B 动态查找 C 查找 D 外查找
3 索引序表特点序表中数( A )
A 序 B 序 C 块间序 D 散列
4 采序查找方法查找长度n线性表时元素均查找长度(C)
A n Bn2 C(n+1)2 D(n1)2
5 *10元素散列1000000单元哈希表( C )产生突
A 定会 B定会 C会 D
6 *散列表址区间0~16散列函数H(k)k17采线性探测法解决址突关键字2625723811859次存储散列表中元素59存放散列表中址( A )
A 8 B 9 C 10 D 11
7 设序表关键字序列{139123241456275778295100}采二分查找法查找值82节点时( C )次较查找成功
A 1 B 2 C 3 D 4
8 设100元素折半查找法进行查找时较次数分时( A )
A 71 B61 C51 D81
第九章 排序
1 n记录排序码值次序重新排列泡(起泡)排序方法初始序列 (A ) 情况排序码值总较次数少
A.排序码值排列 B.排序码值排列
C.机排列(完全序) D.基排序码值升序排列
2 n记录排序码值次序重新排列泡(起泡)排序方法 (B) 情况排序码值总较次数
A.排序码值排列 B.排序码值排列
C.机排列(完全序) D.基排序码值升序排列
3 n记录排序码值次序重新排列直接插入排序方法初始序列 (A) 情况排序码值总较次数少
A.排序码值排列 B.排序码值排列
C.机排列(完全序) D.基排序码值升序排列
4 n记录排序码值次序重新排列直接插入排序方法初始序列 (B) 情况排序码值总较次数
A.排序码值排列 B.排序码值排列
C.机排列(完全序) D.基排序码值升序排列
5 n记录排序码值次序重新排列快速排序方法 (C) 情况排序码值总较次数少
A.排序码值排列 B.排序码值排列
C.机排列(完全序) D.基排序码值升序排列
6 n记录排序码值次序重新排列快速排序方法 (A) 情况排序码值总较次数
A.排序码值排列 B.排序码值排列
C.机排列(完全序) D.基排序码值升序排列
7 泡排序方法n记录排序码值排序时初始序列排序码值排列时码值总较次数 (D)
A.n1 B.n C.n+1 D.n(n1)/2
8 列排序方法中排序码值总较次数排序记录初始序列排列状态关 (D)
A.直接插入排序 B.泡排序 C.快速排序 D.直接选择排序
9 6整数进行排序少需较 (A) 次
A.5 B.6 C.15 D.21
10 6整数进行排序需较 (C) 次
A.5 B.6 C.15 D.21
11 *需时间复杂度O(nlog2n)整数数组进行排序求排序方法稳定选择排序方法 (B)
A.快速排序 B.排序 C.堆排序 D.直接插入排序
12 排序整数序序列时采 (B) 方法较时间复杂度O(n)
A.快速排序 B.泡排序 C.排序 D.直接选择排序
13 排序整数序序列时采 (A)方法较差达坏情况时间复杂度O(n2)
A.快速排序 B.泡排序 C.排序 D.直接选择排序
14 排序整数序序列时排序序列排列否序采 (D)方法时间复杂度O(n2)
A.快速排序 B.泡排序 C.排序 D.直接选择排序
15 *堆种 (B) 排序
A.插入 B.选择 C.交换 D.
16 *组记录排序码值序列{408050306070}利堆排序方法进行排序初建顶堆 (D )
A.804050306070 B.807060504030
C.807050403060 D.806070304050
17 组记录排序码值序列{508030407060}利快速排序方法第记录基准趟快速排序结果(B )
A.304050607080 B.403050807060
C.503040706080 D.405030706080
18 *列种排序方法中求辅助空间(C )
A.堆排序 B.直接选择排序 C.排序 D.快速排序
19 已知A[m]中数组元素距终位置远采列 (A) 排序方法节省时间
A.直接插入 B.堆 C.快速 D.直接选择
20 *设10000互相等序整数仅求找出中前10整数采 (B) 排序方法
A. B.堆 C.快速 D.直接选择
21 *列排序方法中需排序码值进行较进行排序 (A)
A:基数排序 B.快速排序 C.直接插入排序 D.堆排序
22 *定排序码值序列{FBJCEAIDCH}字母字典序列次序进行排列希尔(Shell)排序第趟(d15)结果应(D )
A.{BFCJAEDICH}
B.{CBDAEFICJH}
C.{BFCEAIDCHJ}
D.{ABDCEFIJCH}
23 定排序码值序列{FBJCEAIDCH}字母字典序列次序进行排列泡排序(数沉)第趟排序结果应(C )
A.{BFCJAEDICH}
B.{CBDAEFICJH}
C.{BFCEAIDCHJ}
D.{ABDCEFIJCH}
24 定排序码值序列{FBJCEAIDCH}字母字典序列次序进行排列快速排序第趟排序结果(B )
A.{BFCJAEDICH}
B.{CBDAEFICJH}
C.{BFCEAIDCHJ}
D.{ABDCEFIJCH}
25 *定排序码值序列{FBJCEAIDCH}字母字典序列次序进行排列二路排序第趟排序结果(A )
A.{BFCJAEDICH}
B.{CBDAEFICJH}
C.{BFCEAIDCHJ}
D.{ABDCEFIJCH}
简答题
第章绪
1 请分出数数象数元素数项含义说明四者关系
数(Data)信息种符号表示计算机科学中指输入计算机中计算机程序处理符号总称(分点)
数元素(Data Element)数基单位计算机程序中通常作整体进行考虑处理相表中条记录(分点)
数项:相记录域 数分割单位学号(分点)
数象:性质相数元素集合数子集例 班学生记录集合(分点)
关系:包含关系:数泛指数象数子集数元素组成数元素数项组成(分点)
评分标准总5分点段话分
2 请出数逻辑结构含义举例说明数逻辑结构通常
数逻辑结构:指数元素间逻辑关系然语言描述数数存储关独立计算机逻辑结构四种(分点)
集合结构: 仅属集合(结构名字05分点举例05分点)
线性结构 (11) (结构名字05分点举例05分点)
树 结 构 (1n) (结构名字05分点举例05分点)
图 结 构 (mn) (结构名字05分点举例05分点)
评分标准:段话分点总5分点
什数物理结构?物理结构?数物理结构逻辑结构什区联系?
数物理结构:物理结构称存储结构数逻辑结构计算机存储器表示(映)赖计算机(分点)
存储结构分4类:序链式索引散列(2分点05分点)
区:数逻辑结构属户视图面问题数存储结构属具体实现视图面计算机(分点)
联系:种数逻辑结构种存储结构存储采存储结构处理效率(分点)
评分标准:5分点段话标注分点进行评分
3 求两正整数 mn 中数MAX算法
(1) m > n maxm
(2) m < n maxn
请根述算法解释算法组成素分什
算法操作控制结构数结构3素组成
操作包含:算术运算关系较逻辑运算数传送(输入输出赋值)(分点)
例子中关系较赋值计算操作(分点)
控制结构包含:序结构选择结构循环结构(分点)
例子中选择结构(分点)
数结构:算法操作象数数间逻辑关系数存储方式处理方式数结构(分点)
例数值问题涉两正整数基整数类型解决问题(分点)
评分标准:题6分点段话分点
4 简述算法基性质
1)输入:0输入
2)输出:1输出
3)穷性:算法必须限步结束
4)确定性:组成算法操作必须清晰二义性
5)行性:组成算法操作必须够计算机实现
评分标准题5分点点分
5 简述算法设计求
1正确性(correctness)
2读性(readability)
3健壮性(robustness)
4通性(generality)
5效率存储求(执行算法耗费存储空间执行算法耗费时间)
评分标准题5分点点分
6 评价算法坏3条标准
1)算法实现耗费时间
2)算法实现耗费存储空间中考虑辅助存储空间
3)算法应易理解易编码易调试等
评分标准题3分点点分
7 请简述数结构研究三种基结构数元素间关系
线性结构:数元素间关系(2分)
树形结构:数元素间关系(15分)
图形结构:数元素间关系(15分)
8 请问算法分析评价两标准作
时间复杂度:评估算法运行需时间(15+1分)
空间复杂度:评估算法运行时需存储空间(15+1分)
9 请说出三种逻辑数结构特点(5分)
(1)线性结构:数元素前驱数元素继数元素(2分)
(2)树结构:数元素前驱数元素零干继数元素(15分)
(3)图结构:数元素零干前驱数元素零干继数元素(15分)
10 评价算法标准什?
(1)算法实现耗费时间(2分)
(2)算法实现耗费存储空间中考虑辅助存储空间(2分)
(3)算法应易理解易编码易调试(1分)
11 请说出三种逻辑数结构分画图表示
(a 2分bc15分)
12 算法基性质?简述特性(5分)
(1)穷性—— (1分)
(2)确定性—— (1分)
(3)行性—— (1分)
(4)输入性—— (1分)
(5)输出性—— (1分)
13 通常方面评价算法质量 (5分)
通常四方面评价算法质量:正确性读性健壮性高效性(少扣1分)
14 请描述线性数结构两种存储方式说出什特点
序存储:连续存储易定位易插入删(1+15分)
链式存储:非连续存储易定位易插入删(1+15分)
15 请问算法分析评价两种方法关注点什?(简单)
空间效率:关注算法存占度(1+15分)
时间效率:关注算法运算速度(1+15分)
第二章 线性表
1 请问果插入数线性表中序表链表效率高?什?
链表效率高(2分)序表移动插入位置元素位置新数腾位置(15分)链表需前数指针指新数新数指针指数(15分)
2 线性表特点?
1)第数元素外数元素前驱数元素继数元素(2分)
2)第数元素没前驱数元素(15分)
3)数元素没继数元素(15分)
3 序存储结构优缺点 (中等)
序存储结构优点(25分)
存储空间连续
逻辑相邻物理相邻
机存取元素
缺点(25分)
插入删操作需移动量元素
预先分配空间需空间分配利充分
表容量难扩充
4 单链式存储结构优缺点 (中等)
单链式存储结构优点(25分)
需预先分配空间空间利充分
插入删操作简单 需移动量元素
表容量易扩充
缺点(25分)
数元素存储身信息外需空间存储直接继信息
逻辑相邻物理定相邻
机存取元素 链表头次查找
5 序表A(a0 a1 a2a8a9…a19)a8a9间插入元素a20请描述操作(思想)步骤(中等)
插入思想步骤:根序表存储特点表中某位置10插入新数元素进行两步操作:
(1)位置10表尾位置数元素均前次移存储位置新插入结点腾出第10位置(2分)
(2)新结点插入空余位置10处2分)
(3)表长度加1 (1分)
6 序表A(a0 a1 a2a8a9…a19)删元素a9请描述操作(思想)步骤(中等)
(1)然位置11表尾数元素次前移存储位置(3分)
(2)表长度减1 (2分)
7 请描述序表中第i位置插入新数x操作程
根序表存储特点表中某位置i插入新数元素进行两步操作:
(1)位置i表尾位置数元素均前次移存储位置新插入结点腾出第i位置(2分)
(2)新数x插入空余位置i处(2分)
(3)表长度加1 (1分)
8 请描述序表中删第i位置数程
(1)然位置i表尾数元素次前移存储位置(3分)
(2)表长度减1 (2分)
9 请描述单链表中插入数q插入程
(1) 找插入数位置前结点p (1分)
(2) qnext值等pnext值(2分)
(3)pnext值等q(2分)
10 请描述单链表中删数删程
(1)找删数前结点p (2分)
(2)pnext指针指删数结点(2分)
(3)删数原next指针指null (1分)
第三章 栈队列
1 请简述线性表栈队列三者间联系(简单)
(1)线性表栈队列属线性结构(2分)
(2)栈队列特殊线性表序存储链式存储两种存储方式(1分)
(3)栈种先进出线性表队列种先进先出线性表(2分)
2 计算机进行运算时需十进制转换二进制请问答:种数制转换助种数结构实现原
答栈(2分)
原:(3分)
进行数值转换时实质求余程余数倒序序列正求结果
栈种先进出线性结构够满足种操作
3 字符序列abcde次某线性结构存储请回答问题:
(1)果该线性结构队列写出出队序列
(2)果该线性结构栈输出序列dceab什?
(3)果该线性结构栈输出序列abcde请写出操作程(push (x):表示x压入栈pop (x):表示x弹出栈)
答:
(1)abcde(1分)
(2):d第出栈字符说明ab已压入栈压入栈次序abcde出:ab出栈序baab出栈序列dceab(2分)
(3)(2分)
push (a)pop (a)
push (b)pop (b)
push (c)pop (c)
push (d)pop (d)
push (e)pop (e)
4 简述栈队列异点
相点:栈队列允许表端点处进行插入删操作线性表(2分)
点:栈特点先进出队列特点进先出(3分)
5 次读入数元素序列123进栈程中允许出栈试写出种出栈序列
答123132213231321(1分)
6 果入栈序列ABC组成 请问输出序列 (较难)
输出序列5种:
C B A B C A B A C A C B A B C(1分)
7 果abcde五数次全部存入果采队列栈进行存储次取出分获什容(简单)
队列:abcde (25分)
栈 edcba (25分)
8 设整数 1234次进栈否1423出栈序列1432说明什者(中等)
14231432(2分)
4必须数入栈样次获取1432获1423采pushpoppushpushpushpoppoppop获1432(3分)
9 循环队列优点什?判断空满?(考)
循环队列优点克服序队列假溢现象够存储队列量空间充分利(3分)采牺牲元素空间方法循环队列队空条件frontrear循环队列队满条件:(rear+1)Mfront(2分)
第四章 串
1 字符串S’abcde’请问:(简单)
(1)字符串S长度少?
(2)字符串S子串列出子串?
答:
(1)5 (1分)
(2)16(1分)字串:’a’’b’’c’’d’’e’ ’ab’ ’ bc’ ’ cd’ ’de’’abc’
’ bcd’ ’cde’ ’abcd’ ’bcde’ ’abcde’Φ(3分)
2 字符串S’12345’请问:(简单)
(1)字符串S长度少?
(2)字符串S子串列出子串?
答:
(1)5 (1分)
(2)16(1分)字串:’1’’2’’3’’4’’5’ ’12’ ’ 23’ ’ 34’ ’45’’123’
’ 234’ ’345’ ’1234’ ’2345’ ’12345’Φ(3分)
3 请问答:什串模式匹配?模式匹配算法种?(简单)
答:串模式匹配指子串定位运算串中查找子串第次出现位置
模式匹配算法两种:简单匹配算法(BruteForce)KMP算法
(该题4分点答串匹配定义意基相 2 分答两种匹配算 2 分答错少答 扣 1分)
第五章 数组广义表
1 数结构中数组基结构请完成求:
(1)定义容纳5整型元素数组iAry元素值1020304050 (2)*画出数组iAry序存储结构(规定:整型长度两字节)
(1)int iAry[5]{ 1020304050 } (2 分)
(2)图:(3分根情况酌情扣分)
2 简述数组定义特点分类(简单)
定义:数组n相数类型数元素a0a1a2an1构成限集合(1分点)
特点:
1)数组中元素具统类型(1分点)
2)数组元素标般具固定界界数组旦定义维数维界改变(1分点)
3数组基操作较简单结构初始化销毁外存取元素修改元素值操作 (1分点)
分类:维度分维数组二维数组维数组(1分点)
3 已知二维数组A示(较难)
(1)请行优先列优先方式进行序存储出序存储序列(2分点)
行优先:a11a12a13a21a22a23
列优先:a11a21a12a22a13a23
(2)a11存中存储址α元素存储空间L行优先方式列优先方式分存储中a22址loc(a22)分少(2分点)
行优先:loc(a22)α+4L
列优先:loc(a22)α+3L
(3)数组序存储外没存储方式?没填请说明
链式存储图示(1分点)
第六章 树二叉树
1 树图示: (简单)
请回答问题:
(1)树叶子结点度
(2)非终端结点度
(3)树深度
答:
(1)叶子结点:D EFG度零(2分)
(2)非终端结点:A 度3B 度2C 度1(2分)
(3)树深度3(1分)
2 请回答:树二叉树什区?(中等)
答:区两点:
(1)二叉树结点两子树树然(25分)
(2)二叉树结点子树左右分树子树没次序(25分)
3 棵具n结点满二叉树请问:该满二叉树叶子结点数目少写出分析推理程(中等)
答:(n+1)2(2分)
分析程:满二叉树中度2度0结点设叶子结点数目:n0 度2
结点数目:n2 n0 n2+1n n2+n0 出:n0(n+1)2 (3分)
4 棵二叉树图示:(简单)请问答问题:
(1)先序遍历法遍历该二叉树遍历结果什?
(2)中序遍历法遍历该二叉树遍历结果什?
(3)序遍历法遍历该二叉树遍历结果什?
答:(1)A B D C E F
(2)D B A E C F
(3)D B E F C A (错扣15分)
5 请问二叉树果采前序\中序\序遍历结果什?(中等)
前序ABDECF中序DBEAFC序DEBFCA(错扣15分)
6 颗树
前序\中序\序遍历结果什 (中等)
前序遍历结果:A B D G C E F
中序遍历结果:D G B A E C F
序遍历结果:G D B E F C A (错扣15分)
7 假定通信电文8字符ABCDEFGH组成字母电文中出现概率5%25%4%7%9%12%30%8%现字符出现概率扩100倍作8字母应权值(52547912308)权值构成霍夫曼树图示:
请问答问题:(中等)
(1)参考霍夫曼树字符ABCDEFGH进行编码(写出8字
符霍夫曼编码)
(2)果发送电文信息HECDB发送数什(者说发送编码序列什)
答:(1)A0011B01C0010 D1010E000 F100G11H1011 (3分)
(2)1011 000 0010 1010 01 (2分)
8 请简述满二叉树完全二叉树联系
答:(1)特殊二叉树遵循着二叉树性质 (25分)
(2)满二叉树指层结点数达值叶子结点均层完全二叉树遵循着满二叉树结点编号序列规律种树(25分)
9 颗树
请问度2节点度3节点颗树度少树深度 (中等)
答度2节点BE(15分) 度3节点A D(15分) 颗树度4(1分) 树深度4(1分)
10 请画出深度4满二叉树(较难)
11 请画出深度4完全二叉树(较难)
12 定组权值{62396} 根哈夫曼算法构造哈夫曼树 (难)
1) 62396成5 棵树森林(棵树仅结点)
2) 森林中选出两根结点权值23树合作棵新树左右子树新树根结点权值左右子树根结点权值5森林中删选取两棵树新树加入森林
3) 森林中选出两根结点权值56树合作棵新树左右子树新树根结点权值左右子树根结点权值11森林中删选取两棵树新树加入森林
4)森林中选出两根结点权值69树合作棵新树左右子树新树根结点权值左右子树根结点权值15森林中删选取两棵树新树加入森林
5)森林中选出两根结点权值1115树合作棵新树左右子树新树根结点权值左右子树根结点权值26森林中删选取两棵树新树加入森林
第七章 图
1 什图G生成树
答:连通图G子图果棵包含G顶点树该子图称G生成树
2 写出面图邻接矩阵
答案
3 邻接表表示图存储结构
答案
4 已知图请出:
① 顶点入度出度
② 邻接矩阵
③ 邻接表
答案
第八章 查找
1 什查找静态查找动态查找?说出关静态查找种算法(简单)
查找:定值K含n记录文件中进行搜索寻找关键字值等K记录找输出该记录否输出查找成功信息(1分点)
静态查找:查找改变集合数元素(05分点)
动态查找:查找改变(增减)集合数元素(05分点)
静态查找算法:序二分分块查找(3分点)
2 请回答出四种查找方法查找方法评价标准什?(简单)
答:序查找二分查找(折半查找法)索引查找哈希表查找(4分)
查找方法评价标准:均查找长度(1分)
3 请回答出二分查找序查找优缺点?(简单)
1)序查找
优点:算法简单序结构链表结构均适(1分点)
缺点:查找性较低均查找长度(1分点)
2)二分查找
1)优点:查找效率高均查找长度(1分点)
2)缺点:
a查找表需关键字排序(序表) (1分点)
b二分查找适序存储结构保持表序性序结构里插入删必须移动量结点(1分点)
第九章 排序
1 组数{645798624} 请列出直接选择排序(升序)程 (难)
初始序列 64 5 7 98 6 24
第1次排序 [5] 64 7 98 6 24
第2次排序 [5 6] 7 98 64 24
第3次排序 [5 6 7] 98 64 24
第4次排序 [5 6 7 24] 64 98
第5次排序 [5 6 7 24 64] 98
终结果 [5 6 7 24 64 98]
2 组数{645798624} 请列出泡排序(升序)程 (难)
初始序列 64 5 7 98 6 24
第1次排序 5 7 64 6 24 [98]
第2次排序 5 7 6 24 [64 98]
第3次排序 5 6 7 [24 64 98]
第4次排序 5 6 [7 24 64 98]
第5次排序 5 [6 7 24 64 98]
终结果 [5 6 7 24 64 98]
3 组数{645798624} 请列出直接插入排序(升序)程 (难)
初始序列 [64] 5 7 98 6 24
第1次排序 [5 64] 7 98 6 24
第2次排序 [5 7 64] 98 6 24
第3次排序 [5 7 64 98] 6 24
第4次排序 [5 6 7 64 98] 24
第5次排序 [5 6 7 24 64 98]
4 关键字序列(1615181617182013)现采直接插入排序关键字递增序排列请画出具体程(难)
初始序列 [16]15181617182013
第1次排序 [1516]181617182013
第2次排序 [151618]1617182013
第3次排序 [15161618]17182013
第4次排序 [1516161718]182013
第5次排序 [151616171818]2013
第6次排序 [15161617181820]13
第7次排序 [1315161617181820]
5 关键字序列(1615181617182013)现采泡排序关键字递增序排列请画出具体程(难)
初始序列 16 15 18 16 17 18 20 13
第1次排序 15 16 16 17 18 18 13 [20]
第2次排序 15 16 16 17 18 13 [18 20]
第3次排序 15 16 16 17 13 [18 18 20]
第4次排序 15161613[17181820]
第5次排序 151613[1617181820]
第6次排序 1513[161617181820]
第7次排序 13[15161617181820]
6 关键字序列(1615181617182013)现采直接选择排序关键字递增序排列请画出具体程(难)
初始序列 1615181617182013
第1次排序 [13]15181617182016
第2次排序 [1315]181617182016
第3次排序 [131516]1817182016
第4次排序 [13151616]17182018
第5次排序 [1315161617]182018
第6次排序 [131516161718]2018
第7次排序 [13151616171818 ]20
编程题
第章绪
第二章线性表
1 已知某班级学生信息表表示请序表结构编程实现学生信息( 120010101 杨三)插入表中第条位置
学号(ID)
姓名(Name)
120010102
李华
120010103
王丽
具体求:编写代码定义序表结构完成该信息表已数初始化工作完成数插入
class Student{两分点
public String no 学生学号
public String name 学生姓名
public Student(String no String name){
thisnono
thisnamename
}
}
public class LineList{ LineList线性表名
int length 35 表长度(1分点)
Student data[] new Student[length] 序表数组1分点
int curlen 0 实际表长(1分点)
插入方法
public boolean insert(int iStudent stu){
插入位置正确否判断(1分点)
if(i<1||i> this curlen+1|| thiscurlen>thislength){
return false
}
第i位置开始序表结点均移位置(1分点)
int n thiscurlen
for(n>in)
data[n] data[n1]
插入新结点stu(1分点)
data[n] stu
thiscurlen++(1分点)
return true
}
public static void main(String[] args){
初始化数(2分点)
LineList lstnew LineList()
Student stu1 new Student(120010102李华)
Student stu2 new Student(120010103王丽)
lstdata[0] stu1
lstdata[1] stu2
进行插入操作(1分点)
Student stu3 new Student(120010101杨三)
lstinsert(1 stu3)
}
}
评分标准:总15分点中程序规范语法(3分点语法问题影响程序逻辑05分点处扣分扣完止)程序逻辑12分点(程序代码处标注分数进行分)
2 已知某图书馆图书信息表表示请序表结构编程实现图书信息(10101 鹿鼎记)插入表中第条位置
图书号(ID)
书名(Name)
10102
神雕侠侣
10103
鸳鸯刀
具体求:编写代码定义序表结构完成该信息表已数初始化工作完成数插入
class Book{两分点
public String no 图书编号
public String name 图书名称
public Book(String no String name){
thisnono
thisnamename
}
}
public class LineList{ LineList线性表名
int length 35 表长度(1分点)
Book data[] new Book[length] 序表数组1分点
int curlen 0 实际表长(1分点)
插入方法
public boolean insert(int iBook book){
插入位置正确否判断(1分点)
if(i<1||i> this curlen+1|| thiscurlen>thislength){
return false
}
第i位置开始序表结点均移位置(1分点)
int n thiscurlen
for(n>in)
data[n] data[n1]
插入新结点book(1分点)
data[n] book
thiscurlen++(1分点)
return true
}
public static void main(String[] args){
初始化数(2分点)
LineList lstnew LineList()
Book book1 new Book(10102神雕侠侣)
Book book2 new Book(10103鸳鸯刀)
lstdata[0] book1
lstdata[1] book2
进行插入操作(1分点)
Book book3 new Book(10101鹿鼎记)
lstinsert(1 book3)
}
}
评分标准:总15分点中程序规范语法(3分点语法问题影响程序逻辑05分点处扣分扣完止)程序逻辑12分点(程序代码处标注分数进行分)
3 已知某教务系统课程信息表表示请序表结构编程实现课程信息(10101 数结构)插入表中第条位置
课程号(ID)
课程名(Name)
10102
软件工程
10103
UML
具体求:编写代码定义序表结构完成该信息表已数初始化工作完成数插入
class Lession{两分点
public String no 课程编号
public String name 课程名称
public Lession(String no String name){
thisnono
thisnamename
}
}
public class LineList{ LineList线性表名
int length 35 表长度(1分点)
Lession data[] new Lession[length] 序表数组1分点
int curlen 0 实际表长(1分点)
插入方法
public boolean insert(int iLession lession){
插入位置正确否判断(1分点)
if(i<1||i> this curlen+1|| thiscurlen>thislength){
return false
}
第i位置开始序表结点均移位置(1分点)
int n thiscurlen
for(n>in)
data[n] data[n1]
插入新结点lession(1分点)
data[n] lession
thiscurlen++(1分点)
return true
}
public static void main(String[] args){
初始化数(2分点)
LineList lstnew LineList()
Lession lession1 new Lession(10102软件工程)
Lession lession2 new Lession(10103UML)
lstdata[0] lession1
lstdata[1] lession2
进行插入操作(1分点)
Lession lession3 new Lession(10101数结构)
lstinsert(1 lession3)
}
}
评分标准:总15分点中程序规范语法(3分点语法问题影响程序逻辑05分点处扣分扣完止)程序逻辑12分点(程序代码处标注分数进行分)
4 已知某班级学生信息表表示请序表结构编程实现表中第条学生信息删
学号(ID)
姓名(Name)
120010101
杨三
120010102
李华
具体求:编写代码定义序表结构完成该信息表已数初始化工作完成数删
class Student{2分点
public String no 学生学号
public String name 学生姓名
public Student(String no String name){
thisnono
thisnamename
}
}
public class LineList{ LineList线性表名
int length 35 表长度(1分点)
Student data[] new Student[length] 序表数组1分点
int curlen 0 实际表长(1分点)
删方法
public Student delete(int i){
删位置正确否判断(1分点)
if(i<1||i>thiscurlen){
Systemoutprintln(删位置误)
return null
}
保存删前第i数元素(行代码计分)
Student stu thisdata[i1]
第i+1位置开始次前移位置(1分点)
for(int n in
}
data[thiscurlen1] null(1分点)
thiscurlen(1分点)
return stu
}
public static void main(String[] args){
初始化数(2分点)
LineList lstnew LineList()
Student stu1 new Student(120010101杨三)
Student stu2 new Student(120010102李华)
lstdata[0] stu1
lstdata[1] stu2
进行删操作(1分点)
lst delete (1)
}
}
评分标准:总15分点中程序规范语法(3分点语法问题影响程序逻辑05分点处扣分扣完止)程序逻辑12分点(程序代码处标注分数进行分)
5 已知某图书馆图书信息表表示请序表结构编程实现表中第条图书信息删
书号(ID)
书名(Name)
10101
鹿鼎记
10102
鸳鸯刀
具体求:编写代码定义序表结构完成该信息表已数初始化工作完成数删
class Book{2分点
public String no 图书书号
public String name 图书书名
public Book(String no String name){
thisnono
thisnamename
}
}
public class LineList{ LineList线性表名
int length 35 表长度(1分点)
Book data[] new Book[length] 序表数组1分点
int curlen 0 实际表长(1分点)
删方法
public Book delete(int i){
删位置正确否判断(1分点)
if(i<1||i>thiscurlen){
Systemoutprintln(删位置误)
return null
}
保存删前第i数元素(行代码计分)
Book book thisdata[i1]
第i+1位置开始次前移位置(1分点)
for(int n in
}
data[thiscurlen1] null(1分点)
thiscurlen(1分点)
return book
}
public static void main(String[] args){
初始化数(2分点)
LineList lstnew LineList()
Book book1 new Book(10101鹿鼎记)
Book book2 new Book(10102鸳鸯刀)
lstdata[0] book1
lstdata[1] book2
进行删操作(1分点)
lst delete (1)
}
}
评分标准:总15分点中程序规范语法(3分点语法问题影响程序逻辑05分点处扣分扣完止)程序逻辑12分点(程序代码处标注分数进行分)
6 已知某教务系统课程信息表表示请序表结构编程实现表中第条课程信息删
课程号(ID)
课程名(Name)
10101
dos操作系统
10102
数结构
具体求:编写代码定义序表结构完成该信息表已数初始化工作完成数删
class Lession{2分点
public String no 课程号
public String name 课程名
public Lession(String no String name){
thisnono
thisnamename
}
}
public class LineList{ LineList线性表名
int length 35 表长度(1分点)
Lession data[] new Lession[length] 序表数组1分点
int curlen 0 实际表长(1分点)
删方法
public Lession delete(int i){
删位置正确否判断(1分点)
if(i<1||i>thiscurlen){
Systemoutprintln(删位置误)
return null
}
保存删前第i数元素(行代码计分)
Lession lession thisdata[i1]
第i+1位置开始次前移位置(1分点)
for(int n in
}
data[thiscurlen1] null(1分点)
thiscurlen(1分点)
return lession
}
public static void main(String[] args){
初始化数(2分点)
LineList lstnew LineList()
Lession lession1 new Lession(10101dos操作系统)
Lession lession2 new Lession(10102数结构)
lstdata[0] lession1
lstdata[1] lession2
进行删操作(1分点)
lst delete (1)
}
}
评分标准:总15分点中程序规范语法(3分点语法问题影响程序逻辑05分点处扣分扣完止)程序逻辑12分点(程序代码处标注分数进行分)
第三章 栈队列
第四章 串
第五章 数组广义表
第六章 树二叉树
第七章 图
第八章 查找
1 已知某班级学生信息表表示请序表结构编程实现查找学生( 120010103 王丽)表中位置
学号(ID)
姓名(Name)
120010102
李华
120010103
王丽
具体求:编写代码定义序表结构完成该信息表已数初始化工作完成数查找输出查找位置
class Student{2分点
public String no 学生学号
public String name 学生姓名
public Student(String no String name){
thisnono
thisnamename
}
}
public class LineList{ LineList线性表名
int length 35 表长度(1分点)
Student data[] new Student[length] 序表数组1分点
int curlen 0 实际表长(1分点)
查找方法
public int locate(Student stu){
循环次查找
for (int i0 i< thiscurlen i++){循环1分点
判断1分点
if (data[i]noequals(stuno)&& data[i]nameequals(stuname)){
return i+1 返回值05分点
}
}
return 0 返回值05分点
}
public static void main(String[] args){
初始化数(2分点)
LineList lstnew LineList()
Student stu1 new Student(120010102李华)
Student stu2 new Student(120010103王丽)
lstdata[0] stu1
lstdata[1] stu2
curlen2
进行查询操作(1分点)
int retlstlocate(stu2)
if(ret>0){判断输出结果1分点
Systemoutprintln(查找成功数表中第+ret+位置)
}else{
Systemoutprintln(查找失败数表中未找)
}
}
}
评分标准:总15分点中程序规范语法(3分点语法问题影响程序逻辑05分点处扣分扣完止)程序逻辑12分点(程序代码处标注分数进行分)
2 已知某图书馆图书信息表表示请序表结构编程实现查找图书( 10103 鸳鸯刀)表中位置
书号(ID)
书名(Name)
10102
神雕侠侣
10103
鸳鸯刀
具体求:编写代码定义序表结构完成该信息表已数初始化工作完成数查找输出查找位置
class Book{2分点
public String no 图书书号
public String name 图书书名
public Book(String no String name){
thisnono
thisnamename
}
}
public class LineList{ LineList线性表名
int length 35 表长度(1分点)
Book data[] new Book[length] 序表数组1分点
int curlen 0 实际表长(1分点)
查找方法
public int locate(Book book){
循环次查找
for (int i0 i< thiscurlen i++){循环1分点
判断1分点
if (data[i]noequals(bookno)&& data[i]nameequals(bookname)){
return i+1 返回值05分点
}
}
return 0 返回值05分点
}
public static void main(String[] args){
初始化数(2分点)
LineList lstnew LineList()
Book book1 new Book(10102神雕侠侣)
Book book2 new Book(10103鸳鸯刀)
lstdata[0] book1
lstdata[1] book2
curlen2
进行查询操作(1分点)
int retlstlocate(book2)
if(ret>0){判断输出结果1分点
Systemoutprintln(查找成功数表中第+ret+位置)
}else{
Systemoutprintln(查找失败数表中未找)
}
}
}
评分标准:总15分点中程序规范语法(3分点语法问题影响程序逻辑05分点处扣分扣完止)程序逻辑12分点(程序代码处标注分数进行分)
3 已知某教务系统课程信息表表示请序表结构编程实现查找课程( 10103 数机构)表中位置
书号(ID)
书名(Name)
10102
dos操作系统
10103
数结构
具体求:编写代码定义序表结构完成该信息表已数初始化工作完成数查找输出查找位置
class Lession{2分点
public String no 课程书号
public String name 课程书名
public Lession(String no String name){
thisnono
thisnamename
}
}
public class LineList{ LineList线性表名
int length 35 表长度(1分点)
Lession data[] new Lession[length] 序表数组1分点
int curlen 0 实际表长(1分点)
查找方法
public int locate(Lession lession){
循环次查找
for (int i0 i< thiscurlen i++){循环1分点
判断1分点
if (data[i]noequals(lessionno)&& data[i]nameequals(lessionname)){
return i+1 返回值05分点
}
}
return 0 返回值05分点
}
public static void main(String[] args){
初始化数(2分点)
LineList lstnew LineList()
Lession lession1 new Lession(10102dos操作系统)
Lession lession2 new Lession(10103数结构)
lstdata[0] lession1
lstdata[1] lession2
curlen2
进行查询操作(1分点)
int retlstlocate(lession2)
if(ret>0){判断输出结果1分点
Systemoutprintln(查找成功数表中第+ret+位置)
}else{
Systemoutprintln(查找失败数表中未找)
}
}
}
评分标准:总15分点中程序规范语法(3分点语法问题影响程序逻辑05分点处扣分扣完止)程序逻辑12分点(程序代码处标注分数进行分)
第九章 排序
1 编程题 关键字序列(1615181617182013)请泡排序编成实现关键字递增序排列(难)
public class BubbleSort{
public void bubbleSort(int[] data){1分点
int i j flag1
int temp
for(i 1 i < datalength && flag 1 i++){1分点
flag 01分点
for(j 0 j < datalengthi j++){1分点
if(data[j] > data[j+1]){
flag 11分点
temp data[j]1分点
data[j] data[j+1]1分点
data[j+1] temp1分点
}
}
}
}
public static void main(String[] args){
int[] test {1615181617182013}1分点
BubbleSort ssnew BubbleSort()1分点
ssbubbleSort(test)1分点
for(int i 0 i < testlength i++)输出1分点
Systemoutprint(test[i] + )
}
}
评分标准:总15分点中程序规范语法(3分点语法问题影响程序逻辑05分点处扣分扣完止)程序逻辑12分点(程序代码处标注分数进行分)
2 编程题 关键字序列(161617181815 2013)请泡排序编成实现关键字递增序排列(难)
public class BubbleSort{
public void bubbleSort(int[] data){1分点
int i j flag1
int temp
for(i 1 i < datalength && flag 1 i++){1分点
flag 01分点
for(j 0 j < datalengthi j++){1分点
if(data[j] > data[j+1]){
flag 11分点
temp data[j]1分点
data[j] data[j+1]1分点
data[j+1] temp1分点
}
}
}
}
public static void main(String[] args){
int[] test {161617181815 2013}1分点
BubbleSort ssnew BubbleSort()1分点
ssbubbleSort(test)1分点
for(int i 0 i < testlength i++)输出1分点
Systemoutprint(test[i] + )
}
}
评分标准:总15分点中程序规范语法(3分点语法问题影响程序逻辑05分点处扣分扣完止)程序逻辑12分点(程序代码处标注分数进行分)
3 编程题 关键字序列(341617183415 643)请泡排序编成实现关键字递增序排列(难)
public class BubbleSort{
public void bubbleSort(int[] data){1分点
int i j flag1
int temp
for(i 1 i < datalength && flag 1 i++){1分点
flag 01分点
for(j 0 j < datalengthi j++){1分点
if(data[j] > data[j+1]){
flag 11分点
temp data[j]1分点
data[j] data[j+1]1分点
data[j+1] temp1分点
}
}
}
}
public static void main(String[] args){
int[] test {341617183415 643}1分点
BubbleSort ssnew BubbleSort()1分点
ssbubbleSort(test)1分点
for(int i 0 i < testlength i++)输出1分点
Systemoutprint(test[i] + )
}
}
评分标准:总15分点中程序规范语法(3分点语法问题影响程序逻辑05分点处扣分扣完止)程序逻辑12分点(程序代码处标注分数进行分)
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
该内容是文档的文本内容,更好的格式请下载文档