数结构简答题
11 简述列术语：数数元素数象数结构存储结构数类型抽象数类型
解：数客观事物符号表示计算机科学中指输入计算机中计算机程序处理符号总称
数元素数基单位计算机程序常作整体进行考虑处理
数象性质相数元素集合数子集
数结构相互间存种种特定关系数元素集合
存储结构数结构计算机中表示
数类型值集合定义值集组操作总称
抽象数类型指数学模型定义该模型组操作般数类型扩展
12 试描述数结构抽象数类型概念程序设计语言中数类型概念区
解：抽象数类型包含般数类型概念含义般数类型更广更抽象般数类型具体语言系统部定义直接提供编程者定义户数称预定义数类型抽象数类型通常编程者定义包括定义数数进行操作定义抽象数类型中数部分操作部分时求定义数逻辑结构操作说明考虑数存储结构操作具体实现样抽象层次更高更户提供良接口
17 程序设计中采列三种方法实现输出输入：
(1) 通scanfprintf语句
(2) 通函数参数显式传递
(3) 通全局变量隐式传递
试讨三种方法优缺点
解：(1)scanfprintf直接进行输入输出处形象直观缺点需进行格式控制较烦琐果出现错误会引起整系统崩溃
(2)通函数参数传递进行输入输出便实现信息隐蔽减少出错
(3)通全局变量隐式传递进行输入输出方便需修改变量值全局变量程序维护较困难
21 描述三概念区：头指针头结点首元结点（第元素结点）
解：头指针指链表中第结点指针首元结点指链表中存储第数元素结点头结点首元结点前附设结点该结点存储数元素指针域指首元结点作方便链表操作空表非空表首元结点操作进行统处理
22 填空题
解：(1) 序表中插入删元素需均移动表中半元素具体移动元素数元素表中位置关
(2) 序表中逻辑相邻元素物理位置必定紧邻单链表中逻辑相邻元素物理位置定紧邻
(3) 单链表中首元结点外结点存储位置前驱结点链域值指示
(4) 单链表中设置头结点作插入删首元结点时进行特殊处理
23 什情况序表链表？
解：线性表数元素物理位置连续存储时候序表链表特点进行机存取
32 简述栈线性表差
解：线性表具相特性数元素限序列栈限定仅表尾进行插入删操作线性表
311 简述队列堆栈两种数类型相点差异处
解：栈种运算受限线性表限制仅允许表端进行插入删运算
队列种运算受限线性表限制仅允许表端进行插入表端进行删
41 解：空格串指空格字符(ASCII码20H)组成串空串中没字符
42 解：串赋值(StrAssign)串较(StrCompare)求串长(StrLength)串连接(Concat)求子串(SubString)五种基操作构成串类型操作子集
62 棵度2树棵二叉树区？
解：二叉树颗序树度2树未必序
三简答题
1 描述三概念区：头指针头结点表头结点
1．头指针指链表中第结点（表头结点）指针表头结点前附设结点称头结点表头结点链表中存储线性表中第数元素结点链表中附设头结点线性表否空表头指针均空否表示空表链表头指针空
2 线性表两种存储结构优缺点？
2．线性表具两种存储结构序存储结构存储结构线性表序存储结构直接存取数元素方便灵活效率高插入删操作时会引起元素量移动降低效率：存储结构中存采动态分配利率高需增设指示结点间关系指针域存取数元素序存储方便结点插入删操作较简单
3 线性表两种存储结构果n线性表时存处理程中表长度会动态发生变化线性表总数会动改变情况应选种存储结构？什？
3．应选存储结构链式存储结构组意存储单元次存储线性表中元素里存储单元连续连续：种存储结构元素删插入运算需移动元素需修改指针容易实现表容量扩充
4 线性表两种存储结构线性表总数基稳定少进行插入删操作求快速度存取线性表中元素应选种存储结构？试说明理
4．应选序存储结构数元素存储位置线性表起始位置相差数元素线性表中序号成正常数确定起始位置线性表中数元素机存取线性表序存储结构种机存取存储结构链表种序存取存储结构
5 单循环链表中设置尾指针设置头指针？什
5．设尾指针设头指针尾指针指终端结点指针表示单循环链表查找链表开始结点终端结点方便设带头结点单循环链表尾指针rear开始结点终端结点位置分rear>next>next rear 查找时间O(1)头指针表示该链表查找终端结点时间O(n)
6 假定四元素A B C D次进栈进栈程中允许出栈试写出出栈序列
6．14种出栈序列：
ABCD ABDCACBD ACDBBACDADCBBADCBCAD BCDABDCACBAD CBDACDBA DCBA
7 什队列溢现象？般种解决方法试简述
7．队列序存储结构中设队头指针front队尾指针rear队列容量（存储空间）maxnum元素加入队列（入队）时rearmaxnum会发生队列溢现象时该元素加入队列队列种假溢出现象队列余足够空间元素入队般队列存储结构操作方式选择致循环队列解决
般解决队列溢现象种方法：
（1）建立足够存储空间避免溢出样做会造成空间率低浪费存储空间
（2）避免出现假溢出现象方法解决：
第种：采移动元素方法新元素入队队列中已元素队头移动位置假定空余空间足够
第二种：删队头元素次移动队列中元素总front指针指队列中第位置
第三种：采循环队列方式队头队尾作首尾相接循环队列循环数组实现时队首队尾前作插入删运算时遵循先进先出原
8 述算法功什
LinkList *Demo(LinkList *L)
{ L头结点单链表
LinkList *q*p
if(L&&L>next)
{ qL LL>next pL
while (p>next)
pp>next
p>nextq q>nextNULL
}
return (L)
}
8．该算法功：开始结点摘终端结点成新终端结点原第二结点成新开始结点返回新链表头指针
四应题
1 已知棵树边集合{}请画出棵树回答列问题：
（1）根结点？
（2）叶子结点？
（3）结点g双亲？
（4）结点g祖先？
（5）结点g孩子？
（6）结点e孩子？
（7）结点e兄弟？结点f兄弟？
（8）结点bn层次号分什？
（9）树深度少？
（10）结点c根子树深度少？
1 解答：
a
b
c
d
e
g
f
h
i
m
n
j
k
i
图515
根定边确定树图515示
中根结点a
叶子结点：dmnjkfl
c结点g双亲
ac结点g祖先
jk结点g孩子
mn结点e子
e结点d兄弟
gh结点f兄弟
结点bn层次号分25
树深度5
2 棵度2树棵二叉树区
2 解答：
度2树两分支分支没左右分棵二叉树两分支左右分左右子树交换
3 试分画出具3结点树二叉树形态？
3 解答： 略
4 已知维数组存放棵完全二叉树：ABCDEFGHIJKL写出该二叉树先序中序序遍历序列
4 解答：
先序序列：ABDHIEJKCFLG
中序序列：HDIBJEKALFCG
序序列：HIDJKEBLFGCA
5 棵深度H满k叉树性质：第H层结点叶子结点余层结点k棵非空子树果层次左右序1开始全部结点编号回答列问题：
（1）层结点数目少？
（2）编号n结点父结点果存编号少？
（3）编号n结点第i孩子结点果存编号少？
（4）编号n结点右兄弟条件什？右兄弟编号少？
5 解答：
（1）第i层结点数目mi1
（2）编号n结点父结点果存编号((n2)m)+1
（3）编号n结点第i孩子结点果存编号(n1)*m+i+1
（4）编号n结点右兄弟条件(n1)m≠0右兄弟编号n+1
6 找出满足列条件二叉树：
（1）先序遍历中序遍历时遍历序列相
（2）序遍历中序遍历时遍历序列相
（3）先序遍历序遍历时遍历序列相
6 解答：
（1）先序序列中序序列相二叉树：空树者结点均左孩子非空二叉树
（2）中序序列序序列相二叉树：空树者结点均右孩子非空二叉树
（3）先序序列序序列相二叉树：空树仅结点二叉树
7 假设棵二叉树先序序列EBADCFHGIKJ中序序列ABCDEFGHIJK请写出该二叉树序遍历序列
7 解答：序序列：ACDBGJKIHFE
8 假设棵二叉树序序列DCEGBFHKJIA中序序列DCBGEAHFIJK请写出该二叉树序遍历序列
8 解答：先序序列：ABCDGEIHFJK
9 出图514示森林先根根遍历结点序列然画出该森林应二叉树
9 解答：
先根遍历：ABCDEFGHIJKLMNO
根遍历：BDEFCAHJIGKNOML
森林转换成二叉树图516示
10．定组权值（59112716）试设计相应哈夫曼树
10 解答：构造成哈夫曼树图517示
A
B
D
E
F
C
G
H
J
I
K
N
O
M
L
图514
例65 带权图生成树否定唯？什情况构造出生成树唯？
解：带权图生成树定唯Kruskal算法构造生成树程出图中选择前权值边时果存条样边边已选取边构成回路时边时出现棵生成树中边选择结果会产生生成树
三应题
1 已知序存储序表(15263439455658637476)试画出应折半查找判定树求出均查找长度
1 折半查找判定树图73示均查找长度等2910图73中结点序表中元素应关系表示
图73
10
9
4
5
6
7
8
1
2
3
1
2
3
4
5
6
7
8
9
10
15
26
34
39
45
56
58
63
74
76
2 假定线性表(38522574681630549072)画出线性表中元素次序生成棵二叉排序树求出均查找长度
图74
38
52
25
16
74
30
68
90
54
72
2 二叉排序树图74示均查找长度等3210
3 假定哈希存储线性表(32752963489425461870)哈希址空间HT[13]采留余数法构造哈希函数线性探测法处理突试求出元素哈希表中初始哈希址终哈希址画出哈希表求出均查找长度
元素 32 75 29 63 48 94 25 46 18 70
初始哈希址
终哈希址
0 1 2 3 4 5 6 7 8 9 10 11 12
哈希表
3 H(K)K 13均查找长度1410余解答
元素 32 75 29 63 48 94 25 46 18 70
初始哈希址 6 10 3 11 9 3 12 7 5 5
终哈希址 6 10 3 11 9 4 12 7 5 8
0 1 2 3 4 5 6 7 8 9 10 11 12
哈希表 29 94 18 32 46 70 48 75 63 25
4 假定哈希存储线性表(327529634894253618704980)哈希址空间HT[12]采留余数法构造哈希函数拉链法处理突试画出哈希表求出均查找长度
4 H(K)K 11哈希表图75示均查找长度1712
图75
0
∧
三简答题
2严题集12②数结构数类型两概念间区？
答：简单说数结构定义组某关系结合起数组元素数类型仅定义组带结构数元素定义组操作
3 简述线性结构非线性结构点
答：线性结构反映结点间逻辑关系 非线性结构反映结点间逻辑关系
四简答题
1 严题集23②试较序存储结构链式存储结构优缺点什情况序表链表？
答：① 序存储时相邻数元素存放址相邻（逻辑物理统）求存中存储单元址必须连续
优点：存储密度（＝1？）存储空间利率高缺点：插入删元素时方便
②链式存储时相邻数元素意存放占存储空间分两部分部分存放结点值部分存放表示结点间关系指针
优点：插入删元素时方便灵活缺点：存储密度（<1）存储空间利率低
序表适宜做查找样静态操作链表宜做插入删样动态操作
线性表长度变化操作查找采序表
线性表长度变化较操作插入删操作采链表
2 严题集21①描述三概念区：头指针头结点首元结点（第元素结点）单链表中设置头结点作什？
答：首元结点指链表中存储线性表中第数元素a1结点操作方便通常链表首元结点前附设结点称头结点该结点数域中存储线性表数元素作链表进行操作时空表非空表情况首元结点进行统处理头指针指链表中第结点（头结点首元结点）指针链表中附设头结点线性表否空表头指针均空否表示空表链表头指针空三概念单链表双链表循环链表均适否设置头结点存储结构表示逻辑结构问题
头结点
head
à
data
link
头指针 首元结点
简言
头指针指链表中第结点（头结点首元结点）指针
头结点链表首元结点前附设结点数域放空表标志表长等信息（放头指针？配头指针）
首元素结点指链表中存储线性表中第数元素a1结点
四简答题（题4分20分）
1 严题集32①311①说明线性表栈队异点
答：相点：线性结构逻辑结构概念序存储链表存储栈队列两种特殊线性表受限线性表插入删运算加限制
点：①运算规线性表机存取栈允许端进行插入删运算进先出表LIFO队列允许端进行插入端进行删运算先进先出表FIFO
② 途堆栈子程调保护现场队列道作业处理指令寄存运算等等
4 统考书P60 413序队假溢出样产生？知道循环队列空满？
答：般维数组队列尾指针已数组界入队操作实数组中空位置假溢出
采循环队列解决假溢出途径
外解决队满队空办法三：
设置布尔变量区队满队空
浪费元素空间区队满队空
计数器记录队列中元素数（队列长度）
常采法②队头指针队尾指针中指实元素指空闲元素
判断循环队列队空标志： frear 队满标志：f(r+1)N
2全国专升资格考试递算法非递算法花费更时间？什？
答：定时间复杂度样数n关指深层执行语句耗费时间递算法非递算法深层语句执行没区循环次数没太差异仅仅确定循环否继续方式递栈隐含循环次数非递循环变量显示循环次数已
四简答题（题4分20分）
严题集62①棵度2树棵二叉树区？
答：度2树形式二叉树相似子树序二叉树序般树中某结点孩子需区分左右次序二叉树中孩子左右分
三简答题（题4分16分）
1全国专升题分（折半）查找适适合链表结构序列什？二分查找查找速度必然线性查找速度快种说法？
答：适合然序单链表结点（）序排列存储结构单链表查找结点时头指针开始逐步搜索进行折半查找
二分查找速度般情况快特殊情况未必快例查数位首位时线性查找快二分查找慢
3 全国专升题较两元素方法定序列中查找某元素时间复杂度限什 果求时间复杂度更采什方法？方法时间复杂度少
答：查找某元素时间复杂度限果理解短查找时间关键字值表头元素相时较1次想降低时间复杂度改Hash查找法方法表元素较次数O（1）
四分析题（题6分24分）
1 严题集93②画出长度10序表进行折半查找判定树求等概率时查找成功均查找长度
解：判定树应描述次查找位置：
5
8
1 3 6 9
4 7 10
2 全国专升考题棵空二叉查找树中次插入关键字序列1271711162139214请画出二叉查找树
答：
12
17
2 11 16 21
4 9 13
验算方法： 中序遍历应排序结果： 2479111213161721
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
11 简述列术语：数数元素数象数结构存储结构数类型抽象数类型
解：数客观事物符号表示计算机科学中指输入计算机中计算机程序处理符号总称
数元素数基单位计算机程序常作整体进行考虑处理
数象性质相数元素集合数子集
数结构相互间存种种特定关系数元素集合
存储结构数结构计算机中表示
数类型值集合定义值集组操作总称
抽象数类型指数学模型定义该模型组操作般数类型扩展
12 试描述数结构抽象数类型概念程序设计语言中数类型概念区
解：抽象数类型包含般数类型概念含义般数类型更广更抽象般数类型具体语言系统部定义直接提供编程者定义户数称预定义数类型抽象数类型通常编程者定义包括定义数数进行操作定义抽象数类型中数部分操作部分时求定义数逻辑结构操作说明考虑数存储结构操作具体实现样抽象层次更高更户提供良接口
17 程序设计中采列三种方法实现输出输入：
(1) 通scanfprintf语句
(2) 通函数参数显式传递
(3) 通全局变量隐式传递
试讨三种方法优缺点
解：(1)scanfprintf直接进行输入输出处形象直观缺点需进行格式控制较烦琐果出现错误会引起整系统崩溃
(2)通函数参数传递进行输入输出便实现信息隐蔽减少出错
(3)通全局变量隐式传递进行输入输出方便需修改变量值全局变量程序维护较困难
21 描述三概念区：头指针头结点首元结点（第元素结点）
解：头指针指链表中第结点指针首元结点指链表中存储第数元素结点头结点首元结点前附设结点该结点存储数元素指针域指首元结点作方便链表操作空表非空表首元结点操作进行统处理
22 填空题
解：(1) 序表中插入删元素需均移动表中半元素具体移动元素数元素表中位置关
(2) 序表中逻辑相邻元素物理位置必定紧邻单链表中逻辑相邻元素物理位置定紧邻
(3) 单链表中首元结点外结点存储位置前驱结点链域值指示
(4) 单链表中设置头结点作插入删首元结点时进行特殊处理
23 什情况序表链表？
解：线性表数元素物理位置连续存储时候序表链表特点进行机存取
32 简述栈线性表差
解：线性表具相特性数元素限序列栈限定仅表尾进行插入删操作线性表
311 简述队列堆栈两种数类型相点差异处
解：栈种运算受限线性表限制仅允许表端进行插入删运算
队列种运算受限线性表限制仅允许表端进行插入表端进行删
41 解：空格串指空格字符(ASCII码20H)组成串空串中没字符
42 解：串赋值(StrAssign)串较(StrCompare)求串长(StrLength)串连接(Concat)求子串(SubString)五种基操作构成串类型操作子集
62 棵度2树棵二叉树区？
解：二叉树颗序树度2树未必序
三简答题
1 描述三概念区：头指针头结点表头结点
1．头指针指链表中第结点（表头结点）指针表头结点前附设结点称头结点表头结点链表中存储线性表中第数元素结点链表中附设头结点线性表否空表头指针均空否表示空表链表头指针空
2 线性表两种存储结构优缺点？
2．线性表具两种存储结构序存储结构存储结构线性表序存储结构直接存取数元素方便灵活效率高插入删操作时会引起元素量移动降低效率：存储结构中存采动态分配利率高需增设指示结点间关系指针域存取数元素序存储方便结点插入删操作较简单
3 线性表两种存储结构果n线性表时存处理程中表长度会动态发生变化线性表总数会动改变情况应选种存储结构？什？
3．应选存储结构链式存储结构组意存储单元次存储线性表中元素里存储单元连续连续：种存储结构元素删插入运算需移动元素需修改指针容易实现表容量扩充
4 线性表两种存储结构线性表总数基稳定少进行插入删操作求快速度存取线性表中元素应选种存储结构？试说明理
4．应选序存储结构数元素存储位置线性表起始位置相差数元素线性表中序号成正常数确定起始位置线性表中数元素机存取线性表序存储结构种机存取存储结构链表种序存取存储结构
5 单循环链表中设置尾指针设置头指针？什
5．设尾指针设头指针尾指针指终端结点指针表示单循环链表查找链表开始结点终端结点方便设带头结点单循环链表尾指针rear开始结点终端结点位置分rear>next>next rear 查找时间O(1)头指针表示该链表查找终端结点时间O(n)
6 假定四元素A B C D次进栈进栈程中允许出栈试写出出栈序列
6．14种出栈序列：
ABCD ABDCACBD ACDBBACDADCBBADCBCAD BCDABDCACBAD CBDACDBA DCBA
7 什队列溢现象？般种解决方法试简述
7．队列序存储结构中设队头指针front队尾指针rear队列容量（存储空间）maxnum元素加入队列（入队）时rearmaxnum会发生队列溢现象时该元素加入队列队列种假溢出现象队列余足够空间元素入队般队列存储结构操作方式选择致循环队列解决
般解决队列溢现象种方法：
（1）建立足够存储空间避免溢出样做会造成空间率低浪费存储空间
（2）避免出现假溢出现象方法解决：
第种：采移动元素方法新元素入队队列中已元素队头移动位置假定空余空间足够
第二种：删队头元素次移动队列中元素总front指针指队列中第位置
第三种：采循环队列方式队头队尾作首尾相接循环队列循环数组实现时队首队尾前作插入删运算时遵循先进先出原
8 述算法功什
LinkList *Demo(LinkList *L)
{ L头结点单链表
LinkList *q*p
if(L&&L>next)
{ qL LL>next pL
while (p>next)
pp>next
p>nextq q>nextNULL
}
return (L)
}
8．该算法功：开始结点摘终端结点成新终端结点原第二结点成新开始结点返回新链表头指针
四应题
1 已知棵树边集合{
（1）根结点？
（2）叶子结点？
（3）结点g双亲？
（4）结点g祖先？
（5）结点g孩子？
（6）结点e孩子？
（7）结点e兄弟？结点f兄弟？
（8）结点bn层次号分什？
（9）树深度少？
（10）结点c根子树深度少？
1 解答：
a
b
c
d
e
g
f
h
i
m
n
j
k
i
图515
根定边确定树图515示
中根结点a
叶子结点：dmnjkfl
c结点g双亲
ac结点g祖先
jk结点g孩子
mn结点e子
e结点d兄弟
gh结点f兄弟
结点bn层次号分25
树深度5
2 棵度2树棵二叉树区
2 解答：
度2树两分支分支没左右分棵二叉树两分支左右分左右子树交换
3 试分画出具3结点树二叉树形态？
3 解答： 略
4 已知维数组存放棵完全二叉树：ABCDEFGHIJKL写出该二叉树先序中序序遍历序列
4 解答：
先序序列：ABDHIEJKCFLG
中序序列：HDIBJEKALFCG
序序列：HIDJKEBLFGCA
5 棵深度H满k叉树性质：第H层结点叶子结点余层结点k棵非空子树果层次左右序1开始全部结点编号回答列问题：
（1）层结点数目少？
（2）编号n结点父结点果存编号少？
（3）编号n结点第i孩子结点果存编号少？
（4）编号n结点右兄弟条件什？右兄弟编号少？
5 解答：
（1）第i层结点数目mi1
（2）编号n结点父结点果存编号((n2)m)+1
（3）编号n结点第i孩子结点果存编号(n1)*m+i+1
（4）编号n结点右兄弟条件(n1)m≠0右兄弟编号n+1
6 找出满足列条件二叉树：
（1）先序遍历中序遍历时遍历序列相
（2）序遍历中序遍历时遍历序列相
（3）先序遍历序遍历时遍历序列相
6 解答：
（1）先序序列中序序列相二叉树：空树者结点均左孩子非空二叉树
（2）中序序列序序列相二叉树：空树者结点均右孩子非空二叉树
（3）先序序列序序列相二叉树：空树仅结点二叉树
7 假设棵二叉树先序序列EBADCFHGIKJ中序序列ABCDEFGHIJK请写出该二叉树序遍历序列
7 解答：序序列：ACDBGJKIHFE
8 假设棵二叉树序序列DCEGBFHKJIA中序序列DCBGEAHFIJK请写出该二叉树序遍历序列
8 解答：先序序列：ABCDGEIHFJK
9 出图514示森林先根根遍历结点序列然画出该森林应二叉树
9 解答：
先根遍历：ABCDEFGHIJKLMNO
根遍历：BDEFCAHJIGKNOML
森林转换成二叉树图516示
10．定组权值（59112716）试设计相应哈夫曼树
10 解答：构造成哈夫曼树图517示
A
B
D
E
F
C
G
H
J
I
K
N
O
M
L
图514
例65 带权图生成树否定唯？什情况构造出生成树唯？
解：带权图生成树定唯Kruskal算法构造生成树程出图中选择前权值边时果存条样边边已选取边构成回路时边时出现棵生成树中边选择结果会产生生成树
三应题
1 已知序存储序表(15263439455658637476)试画出应折半查找判定树求出均查找长度
1 折半查找判定树图73示均查找长度等2910图73中结点序表中元素应关系表示
图73
10
9
4
5
6
7
8
1
2
3
1
2
3
4
5
6
7
8
9
10
15
26
34
39
45
56
58
63
74
76
2 假定线性表(38522574681630549072)画出线性表中元素次序生成棵二叉排序树求出均查找长度
图74
38
52
25
16
74
30
68
90
54
72
2 二叉排序树图74示均查找长度等3210
3 假定哈希存储线性表(32752963489425461870)哈希址空间HT[13]采留余数法构造哈希函数线性探测法处理突试求出元素哈希表中初始哈希址终哈希址画出哈希表求出均查找长度
元素 32 75 29 63 48 94 25 46 18 70
初始哈希址
终哈希址
0 1 2 3 4 5 6 7 8 9 10 11 12
哈希表
3 H(K)K 13均查找长度1410余解答
元素 32 75 29 63 48 94 25 46 18 70
初始哈希址 6 10 3 11 9 3 12 7 5 5
终哈希址 6 10 3 11 9 4 12 7 5 8
0 1 2 3 4 5 6 7 8 9 10 11 12
哈希表 29 94 18 32 46 70 48 75 63 25
4 假定哈希存储线性表(327529634894253618704980)哈希址空间HT[12]采留余数法构造哈希函数拉链法处理突试画出哈希表求出均查找长度
4 H(K)K 11哈希表图75示均查找长度1712
图75
0
∧
三简答题
2严题集12②数结构数类型两概念间区？
答：简单说数结构定义组某关系结合起数组元素数类型仅定义组带结构数元素定义组操作
3 简述线性结构非线性结构点
答：线性结构反映结点间逻辑关系 非线性结构反映结点间逻辑关系
四简答题
1 严题集23②试较序存储结构链式存储结构优缺点什情况序表链表？
答：① 序存储时相邻数元素存放址相邻（逻辑物理统）求存中存储单元址必须连续
优点：存储密度（＝1？）存储空间利率高缺点：插入删元素时方便
②链式存储时相邻数元素意存放占存储空间分两部分部分存放结点值部分存放表示结点间关系指针
优点：插入删元素时方便灵活缺点：存储密度（<1）存储空间利率低
序表适宜做查找样静态操作链表宜做插入删样动态操作
线性表长度变化操作查找采序表
线性表长度变化较操作插入删操作采链表
2 严题集21①描述三概念区：头指针头结点首元结点（第元素结点）单链表中设置头结点作什？
答：首元结点指链表中存储线性表中第数元素a1结点操作方便通常链表首元结点前附设结点称头结点该结点数域中存储线性表数元素作链表进行操作时空表非空表情况首元结点进行统处理头指针指链表中第结点（头结点首元结点）指针链表中附设头结点线性表否空表头指针均空否表示空表链表头指针空三概念单链表双链表循环链表均适否设置头结点存储结构表示逻辑结构问题
头结点
head
à
data
link
头指针 首元结点
简言
头指针指链表中第结点（头结点首元结点）指针
头结点链表首元结点前附设结点数域放空表标志表长等信息（放头指针？配头指针）
首元素结点指链表中存储线性表中第数元素a1结点
四简答题（题4分20分）
1 严题集32①311①说明线性表栈队异点
答：相点：线性结构逻辑结构概念序存储链表存储栈队列两种特殊线性表受限线性表插入删运算加限制
点：①运算规线性表机存取栈允许端进行插入删运算进先出表LIFO队列允许端进行插入端进行删运算先进先出表FIFO
② 途堆栈子程调保护现场队列道作业处理指令寄存运算等等
4 统考书P60 413序队假溢出样产生？知道循环队列空满？
答：般维数组队列尾指针已数组界入队操作实数组中空位置假溢出
采循环队列解决假溢出途径
外解决队满队空办法三：
设置布尔变量区队满队空
浪费元素空间区队满队空
计数器记录队列中元素数（队列长度）
常采法②队头指针队尾指针中指实元素指空闲元素
判断循环队列队空标志： frear 队满标志：f(r+1)N
2全国专升资格考试递算法非递算法花费更时间？什？
答：定时间复杂度样数n关指深层执行语句耗费时间递算法非递算法深层语句执行没区循环次数没太差异仅仅确定循环否继续方式递栈隐含循环次数非递循环变量显示循环次数已
四简答题（题4分20分）
严题集62①棵度2树棵二叉树区？
答：度2树形式二叉树相似子树序二叉树序般树中某结点孩子需区分左右次序二叉树中孩子左右分
三简答题（题4分16分）
1全国专升题分（折半）查找适适合链表结构序列什？二分查找查找速度必然线性查找速度快种说法？
答：适合然序单链表结点（）序排列存储结构单链表查找结点时头指针开始逐步搜索进行折半查找
二分查找速度般情况快特殊情况未必快例查数位首位时线性查找快二分查找慢
3 全国专升题较两元素方法定序列中查找某元素时间复杂度限什 果求时间复杂度更采什方法？方法时间复杂度少
答：查找某元素时间复杂度限果理解短查找时间关键字值表头元素相时较1次想降低时间复杂度改Hash查找法方法表元素较次数O（1）
四分析题（题6分24分）
1 严题集93②画出长度10序表进行折半查找判定树求等概率时查找成功均查找长度
解：判定树应描述次查找位置：
5
8
1 3 6 9
4 7 10
2 全国专升考题棵空二叉查找树中次插入关键字序列1271711162139214请画出二叉查找树
答：
12
17
2 11 16 21
4 9 13
验算方法： 中序遍历应排序结果： 2479111213161721
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
