数据结构习题集附答案

数结构题集附答案
第章 绪
选择题
1组成数基单位（ ）
A．数项 B．数类型 C．数元素 D．数变量
2数结构研究数（ ）间相互关系
A．理想结构物理结构 B．理想结构抽象结构
C．物理结构逻辑结构 D．抽象结构逻辑结构
3数结构中逻辑数结构分成（ ）
A．动态结构静态结构 B．紧凑结构非紧凑结构
C．线性结构非线性结构 D．部结构外部结构
4数结构门研究非数值计算程序设计问题中计算机 （①）间（②）运算等学科
①A．数元素 B．计算方法 C．逻辑存储 D．数映
②A．结构 B．关系 C．运算 D．算法
5算法分析两方面（ ）
A．数复杂性程序复杂性 B．正确性简明性
C．读性简明性 D．空间复杂性时间复杂性
6算法分析目（ ）
A．找出数结构合理性 B．研究算法中输入输出关系
C．分析算法效率求改进 D．分析算法易懂性文档性
7计算机算法指（①）必须具备输入输出（②）等5特性
①A．计算方法 B．排序方法
C．解决问题限运算序列 D．调度方法
②A．执行性移植性扩充性 B．行性确定性穷性
C．确定性穷性稳定性 D．易读性稳定性安全性
二判断题
1数机表示称数存储结构（ ）
2算法程序（ ）
3数元素数单位（ ）
4算法五特性：穷性输入输出完成性确定性（ ）
5算法时间复杂度取决问题规模处理数初态（ ）
三填空题
1数逻辑结构包括________________________________四种类型中树形结构图形结构合称________
2线性结构中第结点________前驱结点余结点________前驱结点结点________续结点余结点________续结点
3树形结构中树根结点没________结点余结点________前驱结点叶子结点没________结点余结点续结点________
4图形结构中结点前驱结点数续结点数________
5线性结构中元素间存________关系树形结构中元素间存________关系图形结构中元素间存________关系
6算法五重特性________________________________________
7数结构三素指________________________
8链式存储结构序存储结构相较优点________________________________
9设批数元素快存储某元素数结构宜________结构方便插入元素数结构宜________结构
四算法分析题
1求列算法段语句频度时间复杂度
for(i1 ifor(j 1 j xx+1
分析：该算法二重循环执行次数外循环次数相循环次数固定外循环关时间频度T(n)1+2+3+…+nn*(n+1)2
14≤T(n)n2≤1时间复杂度Ｏ(n2) Ｔ(n)n2 数量级相
2分析列算法段时间频度时间复杂度
for （i1ifor (j1jfor ( k1kxi+jk
分析算法规律知时间频度T(n)1+(1+2)+(1+2+3)++(1+2+3+…+n)
16 ≤ T（n） n3 ≤1时间复杂度Ｏ(n3)
第二章 线性表
选择题
1线性表第元素存储址100元素长度2第5元素址( )
A．110 B．108 C．100 D．120
2127元素序表中插入新元素保持原序变均移动（ ）元素
A．64 B．63 C．635 D．7
3线性表采链式存储结构时址（ ）
A．必须连续 B．部分址必须连续
C．定连续 D．连续否均
4单链表中p指结点结点p插入s指结点执行（ ）
A．s>nextpp>nexts B．s>nextp>nextp>nexts
C．s>nextp>nextps D．p>nextss>nextp
5单链表中删p指结点续结点执行（ ）
A．p>nextp>next>next B．pp>next p>nextp>next>next
C．p>nextp>next D．pp>next>next
6列关线性表叙述中正确（ ）
A．线性表中元素间隔线性关系
B．线性表中少元素
C．线性表中元素仅直接前趋
D．线性表中元素仅直接继
7线性表具n（ ）限序列（n≠0)
A．表元素 B．字符 C．数元素 D．数项
二判断题
1线性表链接存储表中元素逻辑序物理序定相（ ）
2果没提供指针类型语言法构造链式结构（ ）
3线性结构特点结点没前驱结点没继余结点前驱继（ ）
4语句pp>next完成指针负值p指针p指针指继结点数域值（ ）
5想删p指针继结点应该执行qp>next p>nextq>next free(q)（ ）
三填空题
1已知P单链表中非首尾结点P结点插入S结点语句：________
2序表中逻辑相邻元素物理位置( )相邻 单链表中逻辑相邻元素物理位置________相邻
3线性表L＝（a1a2an）采序存储假定n＋1位置插入概率相插入新元素均需移动元素数________
4非空双循环链表中结点q前面插入结点p程：
p>priorq>prior
q>prior>nextp
p>nextq
________
5已知L表头结点单链表列提供答案中选择合适语句序列实现：
表尾插入s结点语句序列________
A．p>nexts B．pL
C．Ls D．p>nexts>next
E．s>nextp>next F．s>nextL
G．s>nextnull H．while(p>next0) pp>next
I．while(p>nextnull) pp>next
四算法设计题
1试编写求已知单链表数域均值函数（数域数类型整型）
2已知带头结点循环链表中头指针head试写出删释放数域值x结点c函数
3某百货公司仓库中批电视机价格低高次序构成循环链表结点价格数量链指针三域现出库（销售）m台价格h电视机试编写算法修改原链表

4某百货公司仓库中批电视机价格低高次序构成循环链表结点价格数量链指针三域现新m台价格h电视机试编写算法修改原链表
5线性表中元素值递增序排列针序表循环链表两种存储方式分编写C函数删线性表中值介ab（a≤b）间元素
6设A(a0a1a2an1)B(b0b1b2bm1)两定线性表结点数分nm结点值均整数
nm ai bi （0≤in存j jB
试编写较ABC函数该函数返回 1 0 1分表示 AB
7试编写算法删双循环链表中第k结点
8线性表前两部分性质元素组成(a0a1an1b0b1bm1)mn两部分元素数线性表分采数组链表两种方式存储编写算法两部分元素换位成(b0b1bm1a0a1an1)分析两种存储方式算法时间空间复杂度
9循环链表作线性表(a0a1an1)（b0b1bm1）存储结构头指针分ahbh设计C函数两线性表合成形（a0b0a1b1…）线性表求开辟新动态空间利原循环链表结点完成合操作结构循环链表头指针head分析算法时间复杂度
10试写出线性表分解两带头结点循环链表两循环链表长度放头结点数域中C函数中线性表中序号偶数元素分解第循环链表中序号奇数元素分解第二循环链表中
11试写出线性链表改循环链表C函数
12知非空线性链表中x结点直接前驱结点y试写出删x结点C函数
第三章 栈队列
选择题
1栈入栈序列abcde栈输出序列（ ）
A．edcba B．decba C．dceab D．abcde
2栈结构通常采两种存储结构（ ）
A．线性存储结构链表存储结构 B．散列方式索引方式
C．链表存储结构数组 D．线性存储结构非线性存储结构
3判定栈ST(元素m0)空条件（ ）
A．ST〉top0 B．ST〉top0
C．ST〉topm0 D．ST〉topm0
4判定栈ST(元素m0)栈满条件（ ）
A．ST>top0 B．ST>top0
C．ST>topm01 D．ST>topm01
5队列入列序列1234队列输出序列（ ）
A．4321 B．1234 C．1432 D．3241
6循环队列数组A[0m1]存放元素值已知头尾指针分frontrear前队列中元素数（ ）
A．(rearfront+m)m B．rearfront+1 C．rearfront1 D．rearfront
7栈队列点（ ）
A．先进出 B．先进先出
C．允许端点处插入删元素 D．没点
8表达式a*(b+c)d缀表达式（ ）
A．abcd*+ B．abc+*d C．abc*+d D．+*abcd
94元素a1a2a3a4次通栈a4进栈前栈状态出栈序（ ）
A．a4a3a2a1 B．a3a2a4a1
C．a3a1a4a2 D．a3a4a2a1
10数组Q[0m－1]存放循环队列中元素变量rearqulen分指示循环队列中队尾元素实际位置前队列中元素数队列第元素实际位置（ ）
A．rear－qulen B．rear－qulen＋m
C．m－qulen D．1＋（rear＋m－qulen）m
二填空题
1栈特点________队列特点________
2线性表栈队列________结构线性表________位置插入删元素栈________插入删元素队列________插入元素________删元素
3栈输入序列12345栈输出序列12345________(正确错误)
4设栈S队列Q初始状态皆空元素a1a2a3a4a5a6次通栈元素出栈进入队列Q6元素出队列序a3a5a4a6a2a1栈S少应该容纳________元素
三算法设计题
1假设两栈s1s2享数组stack[M]中栈底设stack[0]处栈底设stack[M1]处试编写栈作进栈出栈运算C函数push（xi)pop(i)il2中i1表示左边栈i2表示右边栈求整数组元素占时产生溢出
2．利两栈s1s2模拟队列时栈运算实现该队列运算写出模拟队列插入删C函数
栈s1插入元素栈s2删元素
第四章 串
选择题
1列关串叙述中正确（ ）
A．串字符数该串长度 B．串长度少1
C．空串空格字符组成串 D．两串S1S2长度相两串相等
2字符串abaaababnextval值( )
A．(0101104101) B．(0100002101)
C．(010100011) D．(010101011)
3字符串满足式中headtail定义广义表类似head(xyz’)x’tail(xyz’) yz’s( )concat(head(tail(s))head(tail(tail(s)))) dc’
A．abcd B．acbd C．acdb D．adcb
4串种特殊线性表特殊性表现（ ）
A．序存储
B．数元素字符
C．链式存储
D．数元素字符
5．设串S1ABCDEFG’s2PQRST’函数CONCAT（XY）返回XY串连接串SUBSTR（SIJ）返回串S序号I开始J字符组成字串LENGTH（S）返回串S长度CONCAT（SUBSTR（S12LENGTH（S2））SUBSTR（S1LENGTH（S2）2））结果串（ ）
A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF
二算法设计
1分序存储般链接存储两种方式C语言写出实现串s1复制串s2串复制函数strcpy(s1s2)
2般链接存储(结点存放字符)方式写出采简单算法实现串模式匹配C语言函数int L_index(tp)
第五章 数组广义表
选择题
1．常数组进行两种基操作（ ）
A．建立删 B．索引修改 C．查找修改 D．查找索引
2二维数组M元素4字符(字符占存储单元)组成串行标i范围04列标j范围05M行存储时元素M[3][5]起始址M列存储时元素( )起始址相
A．M[2][4] B．M[3][4] C．M[3][5] D．M[4][4]
3数组A[8][10]中元素A长度3字节首址SA开始连续存放存储器存放该数组少需单元数（ ）
A．80 B．100 C．240 D．270
4数组A[8][10]中元素A长度3字节首址SA开始连续存放存储器该数组行存放时元素A[7][4]起始址（ ）
A．SA+141 B．SA+144 C．SA+222 D．SA+225
5数组A[8][10]中元素A长度3字节首址SA开始连续存放存储器该数组列存放时元素A[4][7]起始址（ ）
A．SA+141 B．SA+180 C．SA+222 D．SA+225
6稀疏矩阵般压缩存储方法两种（ ）
A．二维数组三维数组 B．三元组散列
C．三元组十字链表 D．散列十字链表
7采三元组压缩技术存储稀疏矩阵元素行标列标互换完成该矩阵转置运算种观点（ ）
A．正确 B．错误
8设矩阵A称矩阵节省存储三角部分行序存放维数组B[1n(n1)2]中三角部分中元素aij(iA．i(i1)2+j1 B．i(i1)2+j C．i(i+1)2+j1 D．i(i+1)2+j
二填空题
1知二维数组A[m][n]采行序方式存储元素占k存储单元第元素存储址LOC(A[0][0])A[0][0]址________
2二维数组A[10][20]采列序方式存储元素占存储单元A[0][0]存储址200A[6][12]址________
310阶称矩阵A采压缩存储方式(行序LOC(A[0][0])1)A[8][5]址________
4设n行n列三角矩阵A已压缩维数组S[1n*(n+1)2]中行序存储A[i][j]应S中存储位置________
5A列序序进行存储4×6二维数组元素占3存储单元A[0][0]存储址1000元素A[1][3]存储址________该数组占________存储单元
三算法设计
1果矩阵A中存样元素A[i][j]满足条件A[i][j]第i行中值元素第j列中值元素称该矩阵马鞍点编写函数计算出1×n矩阵A马鞍点
算法思想：题意先求出行值元素放入min[m]中求出列值元素放入max[n]中某元素min[i]中max[j]中该元素A[i][j]便马鞍点找出样元素找马鞍点

2n猴子选王选举办法猴子12n编号围坐圈1号开始12m报数报m号退出圈外循环报数直圈剩猴子时猴子王nm键盘输入印出剩猴子号编写程序实现述函数
算法思想题含n元素数组a初始时a[i]中存放猴子编号i计数器似值0a[i]开始循环报数报次计数器值加1报m时便印出a[i]值(退出圈外猴子编号)时a[i]值改O(参加报数)计数器值重新置0该函数直进行n猴子全部退出圈外止退出猴子王现题功程序
3数组广义表算法验证程序
编写列程序
(1)求广义表表头表尾函数head()tail()
(2)计算广义表原子结点数函数count_GL()
(3)计算广义表原子结点数域(设数域整型〉函数sum_GL()
#include stdioh
#include malloch
typedef struct node
{ int tag
union
{struct node *sublist
char data
}dd
struct node *link
}NODE
NODE *creat_GL(char **s)
{
NODE *h
char ch
ch*(*s)
(*s)++
if(ch＇＼0＇)
{
h(NODE*)malloc(sizeof(NODE))
if(ch＇(＇)
{
h>tag1
h>ddsublistcreat_GL(s)
}
Else
{
h>tag0
h>dddatach
}
}
else
hNULL
ch*(*s)
(*s)++
if(hNULL)
if(ch＇＇)
h>link creat_GL(s)
else
h>linkNULL
return(h)
}
void prn_GL(NODE *p)
{
if(pNULL)
{
if(p>tag1)
{
printf(()
if(p>ddsublist NULL)
printf( )
else
prn_GL(p>ddsublist )
}
else
printf(cp>dddata)
if(p>tag1)
printf())
if(p>linkNULL)
{
printf()
prn_GL(p>link)
}
}
}
NODE *copy_GL(NODE *p)
{
NODE *q
if(pNULL) return(NULL)
q(NODE *)malloc(sizeof(NODE))
q>tagp>tag
if(p>tag)
q>ddsublist copy_GL(p>ddsublist )
else
q>dddata p>dddata
q>linkcopy_GL(p>link)
return(q)
}
NODE *head(NODE *p) *求表头函数 *
{
return(p>ddsublist)
}
NODE *tail(NODE *p) *求表尾函数 *
{
return(p>link)
}
int sum(NODE *p) *求原子结点数域函数 *
{ int mn
if(pNULL) return(0)
else
{ if(p>tag0) np>dddata
else
nsum(p>ddsublist)
if(p>linkNULL)
msum(p>link)
else m0
return(n+m)
}
}
int depth(NODE *p) *求表深度函数 *
{
int hmaxdh
NODE *q
if(p>tag0) return(0)
else
if(p>tag1&&p>ddsublistNULL) return 1
else
{
maxdh0
while(pNULL)
{
if(p>tag0) h0
else
{qp>ddsublist
hdepth(q)
}
if(h>maxdh)maxdhh
pp>link
}
return(maxdh+1)
}
}
main()
{
NODE *hd*hc
char s[100]*p
pgets(s)
hdcreat_GL(&p)
prn_GL(head(hd))
prn_GL(tail(hd))
hccopy_GL(hd)
printf(copy after)
prn_GL(hc)
printf(sumd＼nsum(hd))
printf(depthd＼ndepth(hd))
}
第六章 树
选择题
1线索化二叉树中t指结点没左子树充条件（ ）
A．t〉leftNULL B．t〉ltag1
C．t〉ltag1t〉leftNULL D．
2二叉树某种序线索化结点均指前趋继线索种说法（ ）
A．正确 B．错误 C．情况答案确定
3二叉树前序遍历序列中意结点均处子女结点前面种说法（ ）
A．正确 B．错误 C．情况答案确定
4二叉树中结点度2二叉树种特殊树种说法（ ）
A．正确 B．错误 C．情况答案确定
5设高度h二叉树度0度2结点类二叉树中包含结点数少（ ）
A．2h B．2h1 C．2h+1 D．h+1
6已知某二叉树序遍历序列dabec中序遍历序列debac前序遍历序列（ ）
A．acbed B．decab C．deabc D．cedba
7果T2序树T转换二叉树T中结点前序T2中结点（ ）
A．前序 B．中序 C．序 D．层次序
8某二叉树前序遍历结点访问序abdgcefh中序遍历结点访问序dgbaechf序遍历结点访问序（ ）
A．bdgcefha B．gdbecfha C．bdgaechf D．gdbehfca
9二叉树二叉排序树充分必条件结点值均左孩子值右孩子值种说法（ ）
A．正确 B．错误 C．情况答案确定
10二叉树定义具3结点二叉树（ ）种
A．3 B．4 C．5 D．6
11非空二叉树中序遍历序列中根结点右边（ ）
A．右子树结点 B．右子树部分结点
C．左子树部分结点 D．左子树结点
12树适合表示（ ）
A．序数元素 B．序数元素
C．元素间具分支层次关系数 D．元素间联系数
13棵二叉树叶结点先序中序序遍历序列中相次序（ ）
A．发生改变 B．发生改变 C．确定 D．
14实现意二叉树序遍历非递算法栈结构佳方案二叉树采（ ）存储结构
A．二叉链表 B．广义表存储结构 C．三叉链表 D．序存储结构
15满二叉树m树叶n结点深度h（ ）
A．nh+m B．h+m2n C．mh1 D．n2h1
16果某二叉树前序stuwv中序uwtvs该二叉树序（ ）
A．uwvts B．vwuts C．wuvts D．wutsv
17具五层结点二叉衡树少（ ）结点
A．10 B．12 C．15 D．17
二判断题
1二叉树中结点度2（ ）
2二叉树结点先根序列根序列唯确定棵二叉树（ ）
3棵哈夫曼树中存度1结点（ ）
4衡二叉排序树结点左右子树高度差绝值2（ ）
三填空题
1指出树二叉树三差________________________
2概念讲树二叉树两种数结构树转化二叉树基目________
3结点A三兄弟(包括A身)BA双亲结点B度________
4棵具n结点二叉树采标准链接存储结构该二叉树结点________空指针域
5已知二叉树前序序列ABDEGCFHIJ中序序列DBGEAHFIJC写出序序列________
6已知二叉树序序列FGDBHECA中序序列BFDGAEHC 写出前序序列________
7找出满足列条件二叉树
1）先序中序遍历结点访问序样________
2）序中序遍历结点访问序样________
3）先序序遍历结点访问序样________
8棵含n结点k叉树达深度深度少？________
9棵二叉树67结点结点度02棵二叉树中度2结点________
10含100结点树________条边
四问答题
1棵深度h满m叉树具性质第h层结点叶结点余层结点m棵非空子树层次层左右序1开始全部结点编号试计算
(1)第k层结点数(1≤k≤h)
(2)整棵树结点数
(3)编号i结点双亲结点编号
(4)编号i结点第j孩子结点()编号
2证明：满k叉树叶子结点数n0非叶子结点数n1间满足关系： n0（k1）n1+1
3已知组元素(502878652336134271）请完成操作
(1)画出元素排列序逐点插入生成二叉排序树BT
(2)分计算BT中查找元素进行元素间较次数均较次数
(3)画出BT中删(23〉二叉树
4七带权结点权值分378261014试叶结点构造棵哈夫曼树(请结点左子树根结点权等右子树根结点权次序构造〉计算出带权路径长度WPL该树结点总数
5电文五种字符abcde出现频率次47529
(1)试画出应编码哈夫曼树(求左子树根结点权等右子树根结点权)
(2)求出字符晗夫曼编码
(3)求出传送电文总长度
(4)译出编码系列1100011100010101相应电文
五算法设计
已知棵具n结点完全二叉树序存储维数组A[n]中试编写算法输出A[i]结点双亲孩子
二叉树运算算法（作参考）
#include stdioh
#include malloch
typedef struct node
{
char data
struct node *lchild*rchild
}NODE
NODE *T
void create(NODE **T) 创建二叉树
{ char ch
chgetchar()
if(ch＇ ＇) *TNULL
else
{ *T(NODE *)malloc(sizeof(NODE))
(*T)>datach
create(&((*T)>lchild))
create(&((*T)>rchild)) } }
void inorder(NODE *p) 中序编历二叉树
{ if(pNULL)
{ inorder(p>lchild)
printf(c p>data)
inorder(p>rchild) } }
int num0
void count(NODE *p) 统计出二叉树中单孩子结点数方法1
{
if(pNULL)
{
count(p>lchild)
if(p>lchildNULL&&p>rchildNULL||p>lchildNULL&&p>rchildNULL)
num++
count(p>rchild)
}
}
void count1(NODE *pint *num1)
{
if(pNULL)
{
count1(p>lchildnum1)
if(p>lchildNULL&&p>rchildNULL||p>lchildNULL&&p>rchildNULL)
(*num1)++
count1(p>rchildnum1)
}
}
int onechild(NODE *t) 统计出二叉树中单孩子结点数方法2
{
int num1num2
if(tNULL) return(0)
else if(t>lchildNULL&&t>rchildNULL||t>lchildNULL&&t>rchildNULL)
return(onechild(t>lchild)+onechild(t>rchild)+1)
else
{
num1onechild(t>lchild)
num2onechild(t>rchild)
return(num1+num2)
}
}
int sum(NODE *t) 统计出二叉树中结点数
{if(tNULL) return(0)
else
return(sum(t>lchild)+sum(t>rchild)+1)
}
int leaf(NODE *t) 统计出二叉树中叶子结点数
{
if(tNULL) return(0)
else
if(t>lchildNULL&&t>rchildNULL)
return(leaf(t>lchild)+leaf(t>rchild)+1)
else
return(leaf(t>lchild)+leaf(t>rchild))
}
void preorder1(NODE *root) 非递二叉树前序编历
{ NODE *p*s[100]*q qp双亲结点
int top0 top栈顶指针
prootqp
while((pNULL)||(top>0))
{ while(pNULL)
{printf(d p>data)
s[++top]p pp>lchild }
ps[top] pp>rchild }}
void delk(NODE **rootchar k) 删释放数值k叶结点
{ NODE *p*s[100]*q qp双亲结点
int top0 top栈顶指针
if((*root)NULL)return
if((*root)>lchildNULL &&(*root)>rchildNULL&&(*root)>datak) {*rootNULLreturn}
p*rootqp
while((pNULL)||(top>0))
{
while(pNULL)
{
if(p>lchildNULL&&p>rchildNULL &&p>datak)
{if(q>lchildp) q>lchildNULL
else q>rchildNULL
free(p)
return
}
s[++top]p qp pp>lchild }
ps[top] qppp>rchild }}
void lev_traverse(NODE *T) 层次层右左序列出二叉树结点数信息
{NODE *q[100]*p
int headtail
q[0]Thead0tail1
while(head {pq[head++]
printf(cp>data)
if(p>rchildNULL)
q[tail++]p>rchild
if(p>lchildNULL)
q[tail++]p>lchild
}}
int depth(NODE *t) 求二叉树深度
{
int num1num2
if(tNULL) return(0)
if(t>lchild NULL&&t>rchild NULL) return(1)
else
{
num1depth(t>lchild )
num2depth(t>rchild )
if(num1>num2)
return(num1+1)
else
return(num2+1)
}
}
int onechild3(NODE *root) 非递统计出二叉树少度1结点
{ NODE *p*s[100]
int top0num0 top栈顶指针
proot
while((pNULL)||(top>0))
{ while(pNULL)
{if(p>lchildNULL&&p>rchildNULL ||p>lchildNULL&&p>rchildNULL)
num++
s[++top]p pp>lchild }
ps[top] pp>rchild }
return num
}
int like(NODE *t1NODE *t2) 判定两颗二叉树否相似
{
int like1like2
if(t1t2&&t2NULL) return(1)
else
if(t1NULL &&t2NULL||t1NULL&&t2NULL) return(0)
else
{
like1like(t1>lchildt2>lchild)
like2like(t1>rchild t2>rchild )
return(like1&&like2)
}
}
char a[100] 数组序存储二叉树
void change(NODE *tint i) 二叉树链接存储转换序存储
{
if(tNULL)
{a[i]t>data
change(t>lchild2*i)
change(t>rchild2*i+1)
}
}
int complete(NODE *t) 判断二叉树否完全二叉树
{
int iflag0
change(t1)
for(i1i<100i++)
{if(flag&&a[i]＇＼0＇) flag1
if(flag&&a[i]＇＼0＇) break
}
if(i100) return(1)
else return(0)
}
第七章 图
判断题
1图邻接矩阵中非零元素图中边条数相等（ ）
2图邻接矩阵中非零元素图中边条数相等（ ）
3称矩阵定应着图（ ）
4图邻接矩阵定非称矩阵（ ）
二选择题
1图中顶点度数等边数（ ）倍
A．12 B．1 C．2 D．4
2图中顶点入度等顶点出度（ ）倍
A．12 B．1 C．2 D．4
3n顶点图（ ）条边
A．n B．n(n1) C．n(n1）2 D．2n
4具4顶点完全图（ ）条边
A．6 B．12 C．16 D．20
5具6顶点图少应（ ）条边确保连通图
A．5 B．6 C．7 D．8
6具n顶点图中连通全部顶点少需（ ）条边
A．n B．n+1 C．n1 D．n2
7具n顶点图采邻接矩阵表示该矩阵（ ）
A．n B．(n1) 2 C．n1 D．n2
8具n顶点e条边图采邻接表表示表头量（ ）邻接表中结点总数（ ）
①A．n B．n+1 C．n1 D．n+e
②A．e2 B．e C．2e D．n+e
9采邻接表存储图深度优先遍历算法类似二叉树（ ）
A．先序遍历 B．中序遍历 C．序遍历 D．层遍历
10采邻接表存储图宽度优先遍历算法类似二叉树（ ）
A．先序遍历 B．中序遍历 C．序遍历 D．层遍历
11判定图否存回路利拓扑排序方法外利（ ）
A．求关键路径方法 B．求短路径Dijkstm方法
C．宽度优先遍历算法D．深度优先遍历算法
1
4
3
2
5
6
12
12
3
3
10
6
5
7
8
4
11
12Prim算法求列连通带权图代价生成树算法执行某刻已选取顶点集合U＝{125}边集合TE＝{（12）（25）}选取条权值边应（ ）组中选取
A．{（14）（34）（35）（25）}
B．{（54）（53）（56）}
C．{（12）（23）（35）}
D．{（34）（35）（45）（14）}
三填空题
1n顶点连通图少________条边
2环图G中存条顶点i顶点j弧顶点拓扑序列中顶点i顶点j先次序________
3图邻接表中表结点数m图中边条数________条
4 果顶点出发回该顶点路径做________
5果图意顶点出发进行次深度优先搜索访问顶点该图定________
6采邻接表存储结构图广度优先搜索类似二叉树________遍历
7 连通图生成树该图________连通子图连通图n顶点 生成树________条边
四算法设计：
1试图邻接矩阵邻接链表实现算法：
(1)图中插入顶点
(2)图中插入条边
(3)删图中某顶点
(4)删图中某条边


2面伪代码广度优先搜索算法试图中v0源点执行该算法请回答述问题：
(1)图中顶点vn+1需入队少次？重复访问少次
(2)避免重复访问顶点错误应修改算法
　void BFS(ALGraph *Gint k)
{省略局部变量说明visited分量初值假
InitQueue(&Q)置空队列
EnQueue(&Qk)k入队
while(QueueEmpty(&Q)){
iDeQueue(&Q)vi出队
visited[i]TRUE置访问标记
printf(cG>adjlist[i]vertex访问vi
for(pG>adjlist[i]firstedgeppp>next)
次搜索vi邻接点vj(妨设p>adjvexj)
if(visited[p>adjvex])vj没访问
EnQueue(&Qp>adjvex)vj入队
}endofwhile
}BFS
3试邻接表邻接矩阵存储结构分写出基DFSBFS遍历算法判顶点vivj(i<>j)间否路径
4试分写出求DFSBFS生成树(生成森林)算法求印出树边
5写算法求连通分量数输出连通分量顶点集
6设图中边权值相等试邻接矩阵邻接表存储结构分写出算法：
(1)求顶点vi顶点vj(i<>j)短路径
(2)求源点vi余顶点短路径
求输出路径顶点(提示：利BFS遍历思想)
7邻接表存储结构写基DFS遍历策略算法求图中通某顶点vk简单回路(存)
8写算法求图根(存)分析算法时间复杂度
第八章 排 序
选择题
1排序方法中关键字较次数记录初始排列次序关（ ）
A．希尔排序 B．起泡排序 C．插入排序 D．选择排序
2设1000序元素希快速度挑选出中前10元素（ ）排序法
A．起泡排序 B．快速排序 C．堆排序 D．基数排序
3排序元素序列基序前提效率高排序方法（ ）
A．插入排序 B．选择排序 C．快速排序 D．排序
4组记录排序码(467956384084)利堆排序方法建立初始推（ ）
A．794656384080 B．847956384046
C．847956464038 D．845679404638
5组记录关键码(467956384084)利快速排序方法第记录基准次划分结果（ ）
A．384046567984 B．403846795684
C．403846567984 D．403846845679
6组记录排序码(25481635798223403672)中含5长度2序表排序方法该序列进行趟结果（ ）
A．16253548234079823672 B．16253548798223364072
C．16254835798223364072 D．16253548792336407282
7排序方法中未排序序列中次取出元素排序序列(初始时空)中元素进行较放入排序序列正确位置方法称（ ）
A．希尔排序 B．起泡排序 C．插入排序 D．选择排序
8排序方法中未排序序列中挑选元素次放入排序序列(初始空)端方法称（ ）
A．希尔排序 B．排序 C．插入排序 D．选择排序
9某种排序方法线性表(258421471527683520)进行排序时元素序列变化情况
(1)258421471527683520 (2)201521254727683584
(3)152021253527476884 (4)1520212527354768845
采排序方法（ ）
A．选择排序 B．希尔排序 C．排序 D．快速排序
10述种排序方法中均查找长度（ ）
A．插入排序 B．选择排序 C．快速排序 D．排序
11述种排序方法中求存量（ ）
A．插入排序 B．选择排序 C．快速排序 D．排序
12快速排序方法情况利发挥长处( )
A．排序数量太 B．排序数中含相值
C．排序数已基序 D．排序数数奇数
13设10000元素组成序序列希快挑选出中前10值元素改变已算法结构前提种排序算法中( )合适
A．选择排序法 B．快速排序法 C．堆排序法 D．泡排序法
14列四种排序方法中稳定方法（ ）
A．直接插入排序 B．泡排序 C．排序 D．直接选择排序
二判断题
1直接选择排序方法分序列S1＝（1234567）序列S2＝（7532416）进行排序两者较次数相（ ）
2快速排序排序中速度快种（ ）
3堆排序直趟排序结束前元素终位置（ ）
三填空题
1试五种排序方法应操作联系起
(A)排序________
(B)选择排序________
(C)泡排序________
(D)插入排序________
(E)快速排序________
(1)排序序列中次取出元素排序序列中元素作较放入排序序列中正确位置
(2)排序序列中挑选元素放入排序序列端
(3)次相邻序表合成序表
(4)次排序区间划分左右两子区间中左区间中元素键值均等基准元素键值右区间中元素键值均等基准元素键值
(5)两元素较出现反序(逆序)时相互交换位置
2组记录（43896231572604583）进行直接插入排序时第7记录60插入序表时寻找插入位置需较________次
3利快速排序方法组记录(543896231572604583)进行快速排序时递调栈达深度________需递调次数________中第二次递调________组记录进行快速排序
4堆排序快速排序排序中存储空间考虑应首先选取________方法次选取________方法选取________方法排序结果稳定性考虑应选取________方法均情况排序快考虑应选取________方法坏情况排序快节省存考虑应选取________方法
5插入排序希尔排序选择排序快速排序堆排序排序基数排序中排序稳定________
6插入排序希尔排序选择排序快速排序堆排序排序基数排序中均较次数少排序________需存容量________
7堆排序快速排序中原始记录接正序反序选________原始记录序选________
8插入选择排序中初始数基正序选________初始数基反序选________
9n元素序列进行起泡排序时少较次数________
10两序列：
L1＝{2557483792861233}
L2＝{2537331248578692}
泡排序方法分序列L1L2进行排序交换次序较少序列________
四算法设计
1种简单排序算法做计数排序种排序算法排序表(数组表示)进行排序排序结果存放新表中必须注意表中排序关键字互相计数排序算法针表中记录扫描排序表趟统计表中少记录关键字该记录关键字假设某记录统计出数值c记录新序表中合适存放位置c
(1)出适计数排序数表定义
(2)编写实现计数排序算法
(3)n记录表较次数少
(4)直接选择排序相种方法否更什
解 (1) typedef struct
{
ElemType data
KeyType key
}listtype
(2) void countsort(listtype a[]listtype b[]int n)
{
int i1jcount
for(i10i1{
count0
for(j0jif(a[j]keyb[count]a[i1] }
}
(3) n记录表关键字较次数n2
(4)直接选择排序种计数排序直接选择排序较次数n*(n1)2原进行排序（稳定排序）计数排序稳定排序需辅助空间O(n)
2修改泡排序法实现双泡排序第次记录放表尾第二次记录放表头反复进行直排序结束试编写算法
第九章 查 找
判断题
1二分查找法序表进行查找序表键值排序没键值排序（ ）
2哈希表查找进行关键字较（ ）
3哈希表定义函数H（key）keyp(p4装填子α值越越容易发生突( )
5选择hash函数标准：机性均匀性量避免突( )
二填空题
1序查找法均查找长度________二分查找法均查找长度________分块查找法(序查找确定块)均查找长度________分块查找法(二分查找确定块〉均查找长度________哈希表查找法采链接法处理突时均查找长度________
2种查找方法中均查找长度结点数n关查法方法________
3二分查找存储结构仅限________________
4分块查找方法中首先查找________然查找相应________
5长度255表采分块查找法块佳长度________
6散列函数H(key)keyp中p应取________
7假设序线性表A[120]进行二分查找较次查找成功结点数________较二次查找成功结点数________较三次查找成功结点数________较四次查找成功结点数________较五次查找成功结点数________均查找长度________
8长度n线性表进行序查找时间复杂度________采二分法查找时间复杂度________
9知序表(121820252932406283909598)二分查找值2990元素时分需________次________次较查找成功采序查找时分需________次________次较查找成功
三选择题
1序查找法适合存储结构（ ）线性表
A．散列存储 B．序存储链接存储 C．压缩存储 D．索引存储
2线性表进行二分查找时求线性表必须（ ）
A．序方式存储 B．链接方式存储
C．序方式存储结点关键字序排序
D．链接方式存储结点关键字序排序
3采序查找方法查找长度n线性表时元素均查找长度（ ）
A．n B．n2 C．(n+1)2 D．(n1)2
4采二分查找方法查找长度n线性表时元素均查找长度（ ）
A．O(n2) B．O(log2n) C．O(n) D．O(log2n)
5二分查找二叉排序树时间性（ ）
A．相 B．相 C．法较
6序表{139123241456275778295100}二分查找值82结点时（ ）次较查找成功
A．1 B．2 C．4 D．8
7设哈希表长m14哈希函数H(key)key11表中已4结点
addr(15)4
addr(38)5
addr(61)6
addr(84)7余址空二次探测散列处理突关键字49结点址（ ）
A．8 B．3 C．5 D．9
8长度12序表二分查找法该表进行查找表元素等概率情况查找成功需均较次数（ ）
A．3512 B．3712 C．3912 D．4312
9采分块查找时线性表中625元素查找元素概率相假设采序查找确定结点块时块应分（ ）结点佳
A．10 B．25 C．6 D．625
10果求线性表较快查找适应动态变化求采（ ）查找方法
A．分块 B．序 C．二分 D．散列
11设长度100已排序表二分查找进行查找查找成功少较（ ）次
A．9 B．8 C．7 D．6
四问答题
1已知线性表(382574635248)假定采H(k)k7计算散列址进行散列存储试分求出利线性探测开放定址法处理突利链接法处理突该散列表进行查找均查找长度
2知线性表元素(87253108271326895187123706347)散列函数h(k)k13采链接法处理突设计出种链表结构求该表均查找长度
3假定散列存储线性表(327563489425361870)散列址空间[010]采留余数法构造散列函数线性探查法处理突试出应散列表求出等概率情况均查找长度
4试连线右边四种线性表存储结构左边应操作特点连接起
(A）散列表 (1）查找存取速度快插入删速度慢
(B)序序表 (2）查找插入删速度快进行序存取
(C)序表 (3）插入删序存取速度快查找速度慢
(D)链接表 (4)查找插入删速度慢序存取机存取第i元素速度快
五应题
设闭散列表容量7定表（3036475234）散列函数H（K）＝k mod 6采线性探测解决突求：
（1）构造散列表(散列址0~6)
（2）求查找34需进行较次数
六算法设计
哈希表删
hashtable del_hashtable (hashtable &hash keytype K)
{th(k)
if ( hash[t] null) return (infeasible)
else if (hash[t] K) hash[t]hash[t]>next
else { found0
qhash[t]
phash[t]>next
while ((found)&&(p<> null))
if ( p>key K)
{found1
q>nextp>next
}
else{qp pp>next}
if(found) return (infeasible)
}
return(hash)
}
第十章 文 件
1常见文件组织方式种特点 文件操作种 评价文件组织效率
2索引文件散列文件关键字文件适合存放磁带什
3设职工文件记录格式(职工号姓名性职务年龄工资)中职工号关键字设该文件五记录：
址 职工号 姓名 性 职务 年龄 工资
A 39 张恒珊 男 程序员 25 3270
B 50 王莉 女 分析员 31 5685
C 10 季迎宾 男 程序员 28 3575
D 75 丁达芬 女 操作员 18 1650
E 27 赵军 男 分析员 33 6280
(1)该记录序文件请写出文件存储结构
(2)该文件索引序文件请写出索引表
(3)该文件倒排序文件请写出关性倒排表关职务倒排表
4题述文件中列检索写出检索条件表达式写出结果记录职工号
(1)男性职工
(2)工资超均工资职工
(3)职务程序员分析员职工
(4)年龄超25岁男性程序员分析员
5B+树B树差异什？
6编写计算二叉树中叶节点数递函数（14分）


































第章 绪
选择题
1 C 2C 3 C 4 AB 5 C 6CB
二判断题
1√ 2 × 3× 4× 5√
三填空题
1线性树形图形集合 非线性（网状） 2没1没1 3前驱1继意 4意 56穷性确定性行性输入输出 7数元素逻辑结构存储结构 8插入删合等操作较方便 9序存储链式存储
四算法分析题
for(i1 ifor(j 1 j xx+1
分析：该算法二重循环执行次数外循环次数相循环次数固定外循环关时间频度T(n)1+2+3+…+nn*(n+1)2
14≤T(n)n2≤1时间复杂度Ｏ(n2) Ｔ(n)n2 数量级相 2分析列算法段时间频度时间复杂度
for （i1ifor (j1jfor ( k1kxi+jk
分析算法规律知时间频度T(n)1+(1+2)+(1+2+3)++(1+2+3+…+n)
16 ≤ T（n） n3 ≤1时间复杂度Ｏ(n3)

第二章 数结构
选择题
1 B 2C 3 D 4 B 5 A 6A 7C
二判断题
参考答案：1×2√3×4×5√
三填空题
1s>nextp>next p>nexts 2定定 3n2 4q>priorp 5(1)6) 3)
(2) 2) 9）1) 7)
四算法设计题
1
#include stdioh
#include malloch
typedef struct node
{int data
struct node *link
}NODE
int aver(NODE *head)
{int i0sum0ave NODE *p
phead
while(pNULL)
{pp>link++i
sumsum+p>data}
avesumi
return (ave)}
2
#include stdioh
#include malloch
typedef struct node
{
int data * 假设数域整型 *
struct node *link
}NODE
void del_link(NODE *headint x) * 删数域x结点*
{
NODE *p*q*s
phead
qhead>link
while(qhead)
{if(q>datax)
{p>linkq>link
sq
qq>link
free(s)}
else
{
pq
qq>link
}
}
}
3
void del(NODE *headfloat priceint num)
{
NODE *p*q*s
pheadqhead>next
while(q>price{
pq
qq>next
}
if(q>priceprice)
q>numq>numnum
else
printf(产品)
if(q>num0)
{
p>nextq>next
free(q)
}
}
4
#include stdioh
#include malloch
typedef struct node
{
float price
int num
struct node *next
}NODE
void ins(NODE *headfloat priceint num)
{
NODE *p*q*s
pheadqhead>next
while(q>price{
pq
qq>next
}
if(q>priceprice)
q>numq>num+num
else
{
s(NODE *)malloc(sizeof(NODE))
s>priceprice
s>numnum
s>nextp>next
p>nexts
}
}
5序表：
算法思想：0开始扫描线性表k记录元素值ab间元素数满足该条件元素前移k位置修改线性表长度
void del（elemtype list[]int *nelemtype aelemtype b）
{
int i0k0
while（i{
if(list[i]>a&&list[i]else
list[ik]list[i]
i++
}
*n*nk * 修改线性表长度*
}
循环链表
void del(NODE *headelemtype aelemtype b)
{
NODE *p*q
p headqp>link * 假设循环链表带头结点 *
while(qhead && q>data{
pq
qq>link
}
while(qhead && q>data{
rq
qq>link
free(r)
}
if(pq)
p>linkq
}
6
#define MAXSIZE 100
int listA[MAXSIZE]listB[MAXSIZE]
int nm
int compare(int a[]int b[])
{
int i0
while(a[i]b[i]&&ii++
if(nm&&in) return(0)
if(nif(n>m&&im) return(1)
if(iif(a[i]else if(a[i]>b[i]) return(1)
}
7
void del(DUNODE　**headint i)
{
DUNODE *p
if(i0)
{
*head*head>next
*head>priorNULL
return(0)
}　
Else
{for(j0jpp>next
if(pNULL||j>i) return(1)
p>prior>nextp>next
p>next>priorp>proir
free(p)
return(0)
}
8
序存储
void convert(elemtype list[]int lint h) * 数组中第l第h元素逆置*
{
int i
elemtype temp
for(ihi<(l+h)2i++)
{
templist[i]
list[i]list[l+hi]
list[l+hi]temp
}
}
void exchange(elemtype list[]int nint m)
{
convert(list0n+m1)
convert(list0m1)
convert(listmn+m1)
}
该算法时间复杂度O(n+m)空间复杂度O(1)
链接存储(带头结点单链表)
typedef struct node
{
elemtype data
struct node *link
}NODE
void convert(NODE **headint nint m)
{
NODE *p*q*r
int i
p*head
q*head
for(i0iqq>link *q指an1结点 *
rq>link
q>linkNULL
while(r>linkNULL)
rr>link *r指bm1结点 *
*headq
r>linkp
}
该算法时间复杂度O(n+m)序存储节省时间(需移动元素需改变指针)空间复杂度O(1)
9
typedef struct node
{
elemtype data
struct node *link
}NODE
NODE　*union(NODE　*ahNODE *bh)
{
NODE　*a*b*head*r*q
headah
aah
bbh
while(a>linkah&&b>linkbh)
{
ra>link
qb>link
a>linkb
b>linkr
ar
bq
}
if(a>linkah) *a结点数等b结点数 *
{
a>linkb
while(b>linkbh)
bb>link
b>linkhead
}
if(b>linkbh) *b结点数a结点数 *
{
ra>link
a>linkb
b>linkr
}
return(head)
}
该算法时间复杂度O(n+m)中nm两循环链表结点数
10
typedef struct node
{
elemtype data
struct node *link
}NODE
void analyze(NODE *a）
{
NODE　*rh*qh*r*q*p
int i0j0*i序号奇数结点数 j序号偶数结点数 *
pa
rh（NODE *）malloc（sizeof（NODE））*rh序号奇数链表头指针 *
qh(NODE *)malloc(sizeof(NODE)) *qh序号偶数链表头指针 *
rrh
qqh
while(pNULL)
{
r>linkp
rp
i++
pp>link
if(pNULL)
{
q>linkp
qp
j++
pp>link
}
}
rh>datai
r>linkrh
qh>dataj
q>linkqh
}
11
typedef struct node
{
elemtype data
struct node *link
}NODE
void change(NODE　*head)
{
NODE　*p
phead
if(headNULL)
{
while(p>linkNULL)
pp>link
p>linkhead
}
}
12
typedef struct node
{
elemtype data
struct node *link
}NODE
void del(NODE *xNODE *y)
{
NODE *p*q
elemtype d1
py
qx
while(q>nextNULL) * 结点数域前移前结点*
{
p>dataq>data
qq>link
pq
p>linkNULL * 删结点*
free(q)
}
第三章 栈队列
选择题
1 C 2A 3 B 4 B 5 B 6B 7C 8C 9C 10D
二填空题
1先进先出先进出2线性 栈顶队尾头3正确 43

三算法设计题
1
#define M 100
elemtype stack[M]
int top10top2m1
int push(elemtype xint i)
{
if(top1top21) return(1) *溢处理*
else
if(i1) stack[top1++]x
if(i2)stack[top2]x
return(0)
}
int pop(elemtype *pxint i)
{
if(i1)
if(top10) return(1)
else
{
top1
*pxstack[top1]
return(0)
}
else
if(i2)
if(top2M1) return(1)
else
{
top2++
*pxstack[top2]
return(0)
}
}
2
elemtype s1[MAXSIZE]s2[MAZSIZE]
int top1top2
void enqueue(elemtype x)
{
if(top1MAXSIZE) return(1)
else
{
push(s1x)
return(0)
}}
void dequeue(elemtype *px)
{
elemtype x
top20
while(empty(s1))
{
pop(s1&x)
push(s2x)
}
pop(s2&x)
while(empty(s2))
{
pop(s2&x)
push(s1x)
}
}
第四章 串
选择题
1 A 2B 3 D 4 D 5 D
二算法设计
1
序存储：
#include stringh
#define MAXN 100
char s[MAXN]
int S_strlen(char s[])
{
int i
for(i0s[i]＇＼0＇i++)
return(i)
}
void S_strcpy(char s1[]char s2[]) 43题
{
int i
for(i0s1[i]＇＼0＇i++)
s2[i]s1[i]
s2[i]＇＼0＇
}
般链接存储：
#include stdioh
typedef struct node
{
char data
struct node *link
}NODE
NODE *L_strcpy(NODE *s1)
{
NODE *s2*t1*t2*s
if(s1NULL) return(NULL)
else
{
t1s1
t2(NODE *)malloc(sizeof(NODE))
s2t2
while(t1NULL)
{
s(NODE *)malloc(sizeof(NODE))
s>datat1>data
t2>links
t2s
t1t1>link
}
t2>linkNULL
ss2
s2s2>link
free(s)
return(s2)
}
}
2
#include stdioh
typedef struct node
{
char data
struct node *link
}NODE
int L_index(NODE *tNODE *p)
{
NODE *t1*p1*t2
int i
t1ti1
while(t1NULL)
{
p1p
t2t1>link
while(p1>datat1>data&&p1NULL)
{
p1p1>link
t1t1>link
}
if(p1NULL) return(i)
i++
t1t2
}
return(0)
}
第五章 数组广义表
选择题
1 C 2B 3 C 4 C 5 B 6C 7B 8B
二填空题
1loc(A[0][0])+(n*i+j)*k 2332 342 4i*(i+1)2+j+1 5103972
三算法设计题
1
算法思想：题意先求出行值元素放入min[m]中求出列值元素放入max[n]中某元素min[i]中max[j]中该元素A[i][j]便马鞍点找出样元素找马鞍点实现题功程序
#include
#define m 3
#define n 4
void minmax(int a[m][n])
{
int i1jhave0
int min[m]max[n]
for(i10i1{
min[i1]a[i1][0]
for(j1jif(a[i1][j]}
for(j0j{
max[j]a[0][j]
for(i11i1if(a[i1][j]>max [j]) max[j]a[i1][j]
}
for(i10i1for(j0jif(min[i1]max[j])
{
printf((dd)d＼ni1ja[i1][j])
have1
}
if(have) printf(没鞍点＼n)
}
2
算法思想题含n元素数组a初始时a[i]中存放猴子编号i计数器似值0a[i]开始循环报数报次计数器值加1报m时便印出a[i]值(退出圈外猴子编号)时a[i]值改O(参加报数)计数器值重新置0该函数直进行n猴子全部退出圈外止退出猴子王现题功程序
#include stdioh
main()
{
int a[100]
int countdjmn
scanf(d d&m&n)* n>m*
for(j0ja[j]j+1
count0d0
while(dfor(j0jif(a[j]0)
{
count++
if(countm)
{
printf( d a[j])
a[j]0
count0
d++
}
}
}
3
#include stdioh
#include malloch
typedef struct node
{ int tag
union
{struct node *sublist
char data
}dd
struct node *link
}NODE
NODE *creat_GL(char **s)
{
NODE *h
char ch
ch*(*s)
(*s)++
if(ch＇＼0＇)
{
h(NODE*)malloc(sizeof(NODE))
if(ch＇(＇)
{
h>tag1
h>ddsublistcreat_GL(s)
}
Else
{
h>tag0
h>dddatach
}
}
else
hNULL
ch*(*s)
(*s)++
if(hNULL)
if(ch＇＇)
h>link creat_GL(s)
else
h>linkNULL
return(h)
}
void prn_GL(NODE *p)
{
if(pNULL)
{
if(p>tag1)
{
printf(()
if(p>ddsublist NULL)
printf( )
else
prn_GL(p>ddsublist )
}
else
printf(cp>dddata)
if(p>tag1)
printf())
if(p>linkNULL)
{
printf()
prn_GL(p>link)
}
}
}
NODE *copy_GL(NODE *p)
{
NODE *q
if(pNULL) return(NULL)
q(NODE *)malloc(sizeof(NODE))
q>tagp>tag
if(p>tag)
q>ddsublist copy_GL(p>ddsublist )
else
q>dddata p>dddata
q>linkcopy_GL(p>link)
return(q)
}
NODE *head(NODE *p) *求表头函数 *
{
return(p>ddsublist)
}
NODE *tail(NODE *p) *求表尾函数 *
{
return(p>link)
}
int sum(NODE *p) *求原子结点数域函数 *
{ int mn
if(pNULL) return(0)
else
{ if(p>tag0) np>dddata
else
nsum(p>ddsublist)
if(p>linkNULL)
msum(p>link)
else m0
return(n+m)
}
}
int depth(NODE *p) *求表深度函数 *
{
int hmaxdh
NODE *q
if(p>tag0) return(0)
else
if(p>tag1&&p>ddsublistNULL) return 1
else
{
maxdh0
while(pNULL)
{
if(p>tag0) h0
else
{qp>ddsublist
hdepth(q)
}
if(h>maxdh)maxdhh
pp>link
}
return(maxdh+1)
}
}
main()
{
NODE *hd*hc
char s[100]*p
pgets(s)
hdcreat_GL(&p)
prn_GL(head(hd))
prn_GL(tail(hd))
hccopy_GL(hd)
printf(copy after)
prn_GL(hc)
printf(sumd＼nsum(hd))
printf(depthd＼ndepth(hd))
}
第六章 树二叉树
选择题
1 B 2B 3 A 4 B 5 B 6D 7A 8D 9B 10C 11A 12C 13A 14C 15D 16C 17 C
二判断题
1× 2× 3√ 4√
三填空题
1①树结点数少1二叉树结点数0
②树种结点读书没限制二叉树结点度数超2
③树结点左右分二叉树结点左右分
2树采二叉树存储结构利二叉树已算法解决树关问题 34 4n+1 5DGEBHJIFCA 6ABDEGCEH
7①左子树②右子树③仅结点二叉树 8n┕log2n┙+1 922 1099
四问答题
1
答：（1）mk1 （2）（mh1）（m1）
（3）i1时该结点根双亲结点否双亲结点编号（i+m2）m
（4）编号i结点第j孩子结点()编号i*m+（j（m1））
2
证明：设树结点n nn0+n1
满k叉树 非叶子结点引 出k分支k*n1分支
根外分支引出结点树k*n1 +1结点
n0+n1k*n1+1
n0(k1)*n1+1
五算法设计
void parent(int a[]int nint i)
{
if(i1)
{
printf(双亲 ＼n)
return
}
Else
printf(双亲d＼na[(i1)2])
}
void child(int a[]int nint i) *i序号 *
{
int queue[MAX]front0tail0p * 队列作辅助存储孩子序号*
queue[0]itail++
while(front{
pqueue[front++]
if(pi)
printf(d a[p1]) *身输出 *
if(2*pqueue[tail++]2*p
if(2*p+1}
main()
{
int a[MAX]ni
printf( 请输入二叉树结点数)
scanf(d&n)
input(an)
printf(请输入i)
scanf(d&i)
parent(ani)
child(ani)
}
二叉树运算算法（作参考）
#include stdioh
#include malloch
typedef struct node
{
char data
struct node *lchild*rchild
}NODE
NODE *T
void create(NODE **T) 创建二叉树
{ char ch
chgetchar()
if(ch＇ ＇) *TNULL
else
{ *T(NODE *)malloc(sizeof(NODE))
(*T)>datach
create(&((*T)>lchild))
create(&((*T)>rchild)) } }
void inorder(NODE *p) 中序编历二叉树
{ if(pNULL)
{ inorder(p>lchild)
printf(c p>data)
inorder(p>rchild) } }
int num0
void count(NODE *p) 统计出二叉树中单孩子结点数方法1
{
if(pNULL)
{
count(p>lchild)
if(p>lchildNULL&&p>rchildNULL||p>lchildNULL&&p>rchildNULL)
num++
count(p>rchild)
}
}
void count1(NODE *pint *num1)
{
if(pNULL)
{
count1(p>lchildnum1)
if(p>lchildNULL&&p>rchildNULL||p>lchildNULL&&p>rchildNULL)
(*num1)++
count1(p>rchildnum1)
}
}
int onechild(NODE *t) 统计出二叉树中单孩子结点数方法2
{
int num1num2
if(tNULL) return(0)
else if(t>lchildNULL&&t>rchildNULL||t>lchildNULL&&t>rchildNULL)
return(onechild(t>lchild)+onechild(t>rchild)+1)
else
{
num1onechild(t>lchild)
num2onechild(t>rchild)
return(num1+num2)
}
}
int sum(NODE *t) 统计出二叉树中结点数
{if(tNULL) return(0)
else
return(sum(t>lchild)+sum(t>rchild)+1)
}
int leaf(NODE *t) 统计出二叉树中叶子结点数
{
if(tNULL) return(0)
else
if(t>lchildNULL&&t>rchildNULL)
return(leaf(t>lchild)+leaf(t>rchild)+1)
else
return(leaf(t>lchild)+leaf(t>rchild))
}
void preorder1(NODE *root) 非递二叉树前序编历
{ NODE *p*s[100]*q qp双亲结点
int top0 top栈顶指针
prootqp
while((pNULL)||(top>0))
{ while(pNULL)
{printf(d p>data)
s[++top]p pp>lchild }
ps[top] pp>rchild }}
void delk(NODE **rootchar k) 删释放数值k叶结点
{ NODE *p*s[100]*q qp双亲结点
int top0 top栈顶指针
if((*root)NULL)return
if((*root)>lchildNULL &&(*root)>rchildNULL&&(*root)>datak) {*rootNULLreturn}
p*rootqp
while((pNULL)||(top>0))
{
while(pNULL)
{
if(p>lchildNULL&&p>rchildNULL &&p>datak)
{if(q>lchildp) q>lchildNULL
else q>rchildNULL
free(p)
return
}
s[++top]p qp pp>lchild }
ps[top] qppp>rchild }}
void lev_traverse(NODE *T) 层次层右左序列出二叉树结点数信息
{NODE *q[100]*p
int headtail
q[0]Thead0tail1
while(head{pq[head++]
printf(cp>data)
if(p>rchildNULL)
q[tail++]p>rchild
if(p>lchildNULL)
q[tail++]p>lchild
}}
int depth(NODE *t) 求二叉树深度
{
int num1num2
if(tNULL) return(0)
if(t>lchild NULL&&t>rchild NULL) return(1)
else
{
num1depth(t>lchild )
num2depth(t>rchild )
if(num1>num2)
return(num1+1)
else
return(num2+1)
}
}
int onechild3(NODE *root) 非递统计出二叉树少度1结点
{ NODE *p*s[100]
int top0num0 top栈顶指针
proot
while((pNULL)||(top>0))
{ while(pNULL)
{if(p>lchildNULL&&p>rchildNULL ||p>lchildNULL&&p>rchildNULL)
num++
s[++top]p pp>lchild }
ps[top] pp>rchild }
return num
}
int like(NODE *t1NODE *t2) 判定两颗二叉树否相似
{
int like1like2
if(t1t2&&t2NULL) return(1)
else
if(t1NULL &&t2NULL||t1NULL&&t2NULL) return(0)
else
{
like1like(t1>lchildt2>lchild)
like2like(t1>rchild t2>rchild )
return(like1&&like2)
}
}
char a[100] 数组序存储二叉树
void change(NODE *tint i) 二叉树链接存储转换序存储
{
if(tNULL)
{a[i]t>data
change(t>lchild2*i)
change(t>rchild2*i+1)
}
}
int complete(NODE *t) 判断二叉树否完全二叉树
{
int iflag0
change(t1)
for(i1i<100i++)
{if(flag&&a[i]＇＼0＇) flag1
if(flag&&a[i]＇＼0＇) break
}
if(i100) return(1)
else return(0)
}
第七章 图
判断题
1×2√3×4×
二选择题
1 C 2B 3 C 4 A 5 A 6C 7B 8AC 9A 10D 11D 12B
三填空题
1n1 2i前j 3m2 4回路 5强连通图 6层 7极n1
够够够够…………………………
第八章 排 序
选择题
1 D 2C 3 A 4 B 5C 6A 7C 8D 9D 10C 11D 12C 13C 14C
二判断题
1× 2× 3√
三填空题
23 3①2②4③（233815） 4①堆排序②快速排序③排序④排序⑤快速排序⑥堆排序 5希尔排序选择排序快速堆排序 6快速排序基数排序
7①堆排序②快速排序 8①插入排序②选择排序 9n1 10L2
四算法设计
1解 (1) typedef struct
{
ElemType data
KeyType key
}listtype
(2) void countsort(listtype a[]listtype b[]int n)
{
int i1jcount
for(i10i1{
count0
for(j0jif(a[j]keyb[count]a[i1]}
}
(3) n记录表关键字较次数n2
(4)直接选择排序种计数排序直接选择排序较次数n*(n1)2原进行排序（稳定排序）计数排序稳定排序需辅助空间O(n)

第九章 查 找
判断题
1× 2 × 3× 4× 5√
二填空题
1(n+1)2((n+1)*log2(n+1))n1(s2+2s+n)2slog2(ns+1)+s21+α 2哈希表查找 3序序 4索引块 515 6表长素数 7①1 ②2 ③4 ④8 ⑤5 ⑥37 8①O(n) ② O(log2n) 944510
三选择题
1 B 2C 3 C 4 D 5 B 6C 7D 8 B 9B 10A
六算法设计
哈希表删
hashtable del_hashtable (hashtable &hash keytype K)
{th(k)
if ( hash[t] null) return (infeasible)
else if (hash[t] K) hash[t]hash[t]>next
else { found0
qhash[t]
phash[t]>next
while ((found)&&(p<> null))
if ( p>key K)
{found1
q>nextp>next
}
else{qp pp>next}
if(found) return (infeasible)
}
return(hash)
}




文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档