假设一字符序列己存入计算机，请分析用线性表、栈和队列正确输出其回文的可能性？
6.假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，编写一个判别表达式屮括弧是否正确配对的函数correct（exp,tag）；其中：
exp为字符串类型的变量（可理解为每个字符占用一个数组元素），表示被判别的表达式，tag为布尔型变量。
7.假设一个数组squLmJ存放循环队列的元素。
若要使这m个分量都得到利用，则需另一个标志tag,以tag为0或1來区分尾指针和头指针值相同时队列的状态是“空”还是“满”。
试编写相应的入队和出队的算法。
8.试写一个算法，判别读入的一个以'@'为结束符的字符序列是否是“回文”。
1.选择题
1）以下说法正确的是（
A・串是一种特殊的线性表
C.串中的元素只能是字母
）o
B.串的长度必须大于零
D.空串就是空白串
2）设有一个字符串S二“WelcometoShenyang!
”，问该串的长度为（
A.18B.19
C.20D.21
3）设有一个字符串S=t4abcdefgh,\问该串的最大子串个数为（
A.8
C.37
4）两个字符串相等的条件是（
A.两串的长度相等
B.两串包含的字符相同
C.两串的长度相等，并且两串包含的字符相同
D.两串的长度相等，并且对应位置上的字符相同
5）某串的长度小于一个常数，则采用（）存储方式最节省空间。
A.链式B.顺序
C.堆结构D.无法确定
6）以下论述正确的是（）o
A・空串与空格串是相同的
B.“tel”是“Teleptone”的子串
C.空串是零个字符的串
D.空串的长度等于1
7）以下论断正确的是（
A.
B.
C.
D.
B.
D.
36
9
）o
）o
）。
）o
“”是空串，“”是空格串
“BEIJING”是“BEIJING”的子串"something”<“Somethig"
“BIT”=“BITE”
8）设有两个串S1和S2,则StrCompare（S1,S2）运算称做（
A.串连接
C.求子串
9）串的模式匹配是指（
A.判断两个串是否相等
B.对两个串比较大小
B.模式匹配
D.串比较
）o
）o
C・找某字符在主串屮第一次出现的位置
D.找某子串在主串中第一次出现的第一个字符位置
10）若SubString（Sub,S,pos,len）^示用Sub返冋串S的笫pos个字符起长度为len的子串
的操作，则对于S="DataStructureSubString（Sub,S,6,3）的结果为（）。
A.“taStr”B.“Str”
C・“mi”D.以上均不正确
11）若StrIndex（S,T）表示求T在S中的位置的操作,则对于S="BeijingandNanjing”,
T=“jing”，StrIndex（S,T）的结果为（）。
A.2B.3C.4D.16
12）S二“moming”，执行求子串函数SubStr（S,2,2）后的结果为（）。
A.“mo”B.“or”C.“in”D.“ng”
13）Sl=“Good”,S2=“Morning”,执行串连接函数ConcatStr（S1,S2）后的结果为（）。
A."GoodMoming”B."GoodMorning"
C.“GOODMORNING”D.“GOODMORNING”
14）S1二“good”,S2=morning”,执行函数SubStr（S2,4,LenStr（S1））后的结果为（）。
A.“good”B.“ning”C.“go”D.“mom”
15）设串SI二“ABCDEFG”，S2=“PQRST”,则ConcatStr（SubStr（S1,2,LenStr（S2））»
SubStr（S1,LenStr（S2）,2））的结果串为（）。
A.BCDEFB.BCDEFG
C・BCPQRSTD.BCDEFEF
2.填空题
1）字符串按存储方式可以分为：
顺序存储、链接存储和。
2）在C语言中，以字符表示串值的终结。
3）空格串的长度等于。
4）在空串和空格串屮，长度不为0的是o
5）两个串相等是指两个串长度相等，且对应位置的o
6）设S二“Mymathei•”，则LenStr（s）=。
7）两个字符串分别为:
Sl=“Todayis",S2=“24July,201lM,ConcatStr（S1,S2）的结果是：
8）假设有两个字符串SI和S2,其中Sl=ttabcdxyz,\S2="resf\那么如果进行了下而的运算StrCat（SubString（Sub,S1,3,2）,SubString（Sub,SI,StrLength（S2）,3）），其结果为
3.应用题
1）下面程序是把两个串rl和r2首尾相连的程序，即：
rl=rl+r2，试完成程序填空。
typedefstruct{
charvec[MAXLEN];〃定义合并后串的最大长度
intlen;//len为串的长度
intsame（Str*x,*y）{
inti=0,tag=l;
if（x->len
（1）y->len）
return0;
else{
while（ilen
（2）lag）{if（x->vec[i1（3）y->vec[i1）
（4）;
（5）;
returntag;
}
}
3）编写算法，求串S中所含不同字符的总数和每种字符的个数。
4）有两个串S1和S2,设计一个算法，求一个串T,使其中的字符是S1和S2中的公共字符。
1.选择题
1）对于C语言的二维数组DataTypearr[m][n],每个数据元素占k个存储单元，二维数组屮任意元素arr[i,j]的存储位置可由（）式确定。
A.Loc[i,j]=arr[m,n]+[（n+l）*i+j]*kB.Loc[i,j]=Loc[0,0]+[（m+n）*i+j]*k
C・Loc[i,j]=Loc[0,0]+[（n+l）*i+j]*kD.Loc[i,j]=[（n+l）*i+j]*k
2）数组arr[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素arrl5,5J的地址是（）。
A.1175B.1180C.1205D.1210
3）A[N,N]是对称矩阵，将下三角（含对角线）以行序存储到一维数组arr[N（N+l）/2]中,
则对任一上三角元素arr[i,j]对应air[k]的下标k是（）。
6）有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2个字节，则用三元组
）o
C.33D.66
对其运用Head和Tai】运算，取出其中原子e的
表示该矩阵时，所需的字节数是（
A.18000B.60
7）已知广义表LS二（（a,b,c）,（d,e,f））,
运算是（）。
B•Head（Tail（Head（Tail（LS））））
D.Tail（Head（LS））
）,表尾是（
）o
C・（a,b,c,d）
D.（b）
度分别为（
）o
C.1和1
D.2和3
A.Head（Tail（LS））
C.Head（Tail（Tail（Head（LS））））
8）广义表（（a,b,c,d））的表头是（
A.aB.（）
9）设广义表L二（（a,b,c））,则L的长度和
A.1和2B.1和3
2.数组、广义表与线性表之间有什么用的关系？
3.特殊矩阵和稀疏矩阵，哪一种压缩存储后失去随机存取的功能？
为什么？
4.画出广义表（（（（a）,b））,（（（）,d）,（e,f）））的链式存储结构图示。
5.设二维数组a[l..m,l..n]含有m*n个整数。
（1）写出算法：
判断a中所有元素是否互不相同？
输出相关信息（yes/no）；
（2）试分析算法的时间复杂度。
1.分析树结构的特征，并举例说明其实际的应用。
2.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
3.一棵度为2的树与一棵二叉树有何区别？
4.选择题
1）树中所有结点的度等于所有结点数加（）。
A.0
5.填空题
1）在一棵树中，结点没有前驱结点，其余每个结点有并且只有一
个，可以有任意多个结点。
2）对于一棵具有n个结点的树，该树中所有结点的度数之和为。
3）一棵深度为5的完全二叉树中的结点数最少为个，最多为
个。
4）一棵完全二叉树上有1001个结点，其中叶子结点的个数是o
5）利用二叉链表存储一般树，则根结点的右指针是。
6）用4个权值｛3,2,4,1｝构造的哈夫曼（Huffman）树的带权路径长度是。
6.IE］出和下列已知序列对应的二叉树。
1）二叉树的先序访问序列为：
GFKDAIEBCHJ
2）二叉树的中序访问序列为：
DIAEKFCJHBG
7.画出和下列已知序列对应的二叉树。
1）二叉树的后序访问序列为：
CFEGDBJLKIHA
2）二叉树的中序访问序列为：
CBEFDGAJIKLH
8.画出和下列已知序列对应的二叉树。
1）二叉树的层次访问序列为：
ABCDEFGHIJ
2）二叉树的屮序访问序列为：
DBGEHJACIF
9.给定一棵用二叉链表表示的二叉树，其根指针为root。
试写出求二叉树结点的数目的算法（递归算法或非递归算法）。
10.设计一个算法，要求该算法把二叉树的叶子按从左至右的顺序链成一个单链表。
二叉树按二叉链表方式存储，链接时用叶子的rchild域存放链指针。
11•给定一棵用二叉链表表示的二叉树，其根指针为wot。
试写出求二叉树的深度的算法。
12.给定一棵用二叉链表表示的二叉树，其根指针为root。
试写出求二叉树各结点的层数的算法。
13.给定一棵用二叉链表表示的二叉树，其根指针为root。
试写出将二叉树屮所有结点的左、右子树相互交换的算法。
14.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07,0.19,
0.02,0.06,0.32,0.03,0.21,0.10。
1）试为这8个字母设计哈夫曼编码。
2）使用0〜7的二进制表示的等长编码方案。
3）对于上述实例，比较两种方案的优缺点。
13.画出和下列二叉树相应的森林。
1.选择题
1）在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s,则所有顶点的入度
数Z和为（）。
A・s
C.s-1
B.s+1
D.n
2）在一个具有n个顶点的有向图屮，若所有顶点的出度数之和为s,则所有顶点的度数
之和为（）o
A.s
C.s-1
B.s+1
D.2s
3）在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为（）。
B.e
A・n
C.n+eD.2e
4）在一个具有n个顶点的无向完全图中，所含的边数为（）。
A.nB・n（n-l）
C.n（n-l）/2D.n（n+1）/2
5）在一个具有n个顶点的有向完全图中，所含的边数为（）。
A.nB.n（n-l）
C.n（n-l）/2D.n（n+l）/2
6）对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（）。
A.nB・1
C・0D.n+1
7）若一个图屮包含有k个连通分量，若按照深度优先搜索的方法访问所有顶点，则必须
调用（）次深度优先搜索遍历的算法。
A.kB.1
C.k-1D.k+1
8）若要把n个顶点连接为一个连通图，则至少需要（）条边。
A.nB.n+1
C.n-1D.2n
9）在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量
的大小至少为（）。
A.nB.e
C.2eD.2n
10）对于一个有向图，若一个顶点的度为kl,出度为k2,则对应邻接表中该顶点单链表
屮的边结点数为（
）o
A.kl
B.kl-k2
C.k2
D.kl+k2
11）深度优先遍历类似于二叉树的
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
12）广度优先遍历类似于二叉树的（）。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
13）用邻接表表示图进行广度优先遍历时，通常借助（
A.栈
B.队列
C.树
D.图
14）用邻接表表示图进行深度优先遍历吋，通常借助（
A.栈
B.队列
C.树
D.图
15）下面（
）方法可以判断出一个有向图是否有环。
A・深度优先遍历
B.拓扑排序
C.求最短路径
D.求关键路径
2.填空题
）来实现算法。
）来实现算法。
1）在一个图中，所有顶点的度数之和等于所有边数的倍。
2）在一个有n个顶点的无向完全图屮，包含有条边，在一个具有n个顶点
的有向完全图中，包含有条边。
3）在一个有n个顶点的无向图中，要连通所有顶点则至少需要条边。
4）表示图的两种存储结构为和°
5）在一个连通图中存在着个连通分量。
6）图屮的一条路径长度为k,该路径所含的顶点数为c
3.已知如图所示的有向图，请给出:
1每个顶点的入度和11!
度；
2邻接矩阵；
3邻接表；
4逆邻接表；
5强连通分量。
4.请对如图所示的无向网:
1写出邻接矩阵，并按普里姆算法求其最小生成树；
2写出邻接表，并按克鲁斯卡尔算法求其最小生成树。
3
5.编写算法，由依次输入的顶点数冃、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
6.编写算法，由依次输入的顶点数目、边的数目、各顶点的信息和各条边的信息建立有向图的邻接矩阵。
7.试在邻接矩阵存储结构上实现图的基本操作：
DeleteArc（G,v,w）,即删除一条边的操作。
&试在邻接表存储结构上实现图的基本操作：
DeleteArc（G,v,w）,即删除一条边的操作。
9.试在邻接矩阵存储结构上实现图的基木操作：
InsertVex（Gv）,即新增一个新顶点的操作。
10.试在邻接表存储结构上实现图的基本操作：
InsertVex（G,v）,即新增一个新顶点的操作。
11.采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。
1.选择题
1）若查找每个元素的概率相等，则在长度为n的顺序表上查找任一个元素的平均查找长
度为（
A・n
）o
B•n+1
C.（n-1）/2D.（n+l）/2
2）对长度为n的单链有序表，若查找每个元素的概率相等，则查找任一个元素的平均查
找长度为（
A.n/2
C.（n-l）/2
）o
B.（n+l）/2
D-n/4
3）对于长度为n的顺序存储的有序表，若采用折半查找，则对所有元素的最长查找长度
为（）的值向上取整。
A.log2（n+l）B・log2n
C.n/2D.
4）对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找反
度为（
A.20
C.25
）的值除以9。
B.18
D.22
5）对于长度为18的顺庁存储的有序表，若采用折半查找，则查找第15个元素的查找长
度为（
A.3
升级会员 