山西农业大学数据结构期末考试(山西农业大学大数据专业)
求数据结构期末测试题一套
一、单选题
1. 以下数据结构中哪一个是线性结构？( )
A. 有向图 B. 栈 C. 线索二叉树 D. B树
2. 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。
A. HL=p; p-next=HL; B. p-next=HL; HL=p;
C. p-next=HL; p=HL; D. p-next=HL-next; HL-next=p;
3. 在一个带有头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。
A. HL=p; p-next=HL; B. p-next=HL; HL=p;
C. p-next=HL; p=HL; D. p-next=HL-next; HL-next=p;
4. 单链表的每个结点中包括一个指针next，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针p指向的单链表结点之后，下面的操作序列中哪一个是正确的？（ ）
A．q=p-next; p-next=q-next; B.p-next=q-next;q=p-next
C. q-next=p-next; p-next=q; D. P-next=q; q-next=p-next;
5. 在一个循环顺序存储的队列中，队首指针指向队首元素的（ ）位置。
A． 前一个 B. 后一个 C. 当前
6. 以下哪一个不是队列的基本运算？（ ）
A.从队尾插入一个新元素 B.从队列中删除第i个元素
C.判断一个队列是否为空 D.读取队头元素的值
7. 用链接方式存储的队列，在进行删除运算时( ).
A.仅修改头指针 B.仅修改尾指针
C.头、尾指针都要修改 D.头、尾指针可能都要修改
8. 对线性表，在下列哪种情况下应当采用链表表示？( )
A.经常需要随机地存取元素 B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变
9. 字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串？
A.5 B.4 C.6 D.1
10. 下述哪一条是顺序存储方式的优点？（ ）
A．存储密度大 B.插入运算方便
C. 删除运算方便 D.可方便地用于各种逻辑结构的存储表示
二、填空题
1. 数据的逻辑结构被分为_________、________、__________和___________四种。
2. 数据的物理结构被分为_________、________、__________和___________四种。
3. 一个算法的时间复杂度为(3n2+2nlog2 n+4n-7)/(5n)，其数量级表示为________。
4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。
5. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。
6. 在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为________和________。
7. 一个广义表中的元素分为________元素和________元素两类。
8. 从一个链栈中删除一个结点时，需要把栈顶结点的_________域的值赋给________。
9. 进行函数调用时，需要把每个实参的值和调用后的________传送给被调用的函数中。
10. 设W为一个二维数组，其每个数据元素占用6个字节，行下标i从0到8 ，列下标j从0到3 ，则二维数组W的数据元素共占用＿＿个字节。W中第6 行的元素和第4 列的元素共占用＿＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组W的最后一个数据元素的起始地址为＿＿。
更多的在
谁有数据结构的期末试题，借我参考下马上考试了
A：
06－07第一学期期末考试试卷
试卷代码：03266A 授课课时：112
课程名称：数据结构与算法 适用对象：本科
一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)
1.数据结构被形式地定义为(K,R)，其中K是数据元素的有限集，R是K上的___有限集。
A.操作 B.映像 C.存储 D.关系
2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址____。
A.必须连续的 B.部分地址必须连续的 C.一定是不续的 D.连续不连续都可以
3.一个栈的入栈序列是a、b、c、d、e，则栈的不可能输出序列是____。
A.edcba B.decba C.dceab D.abcde
4.一个队列的入队序列是1、2、3、4，则队列输出序列是____。
A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、1
5.栈和队列的共同点是____。
A.都是先进后出 B.都是先进先出
C.只允许在端点处插入、删除元素 D.没有共同点
6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。
A. s-next = p-next; p-next=s; B. p-next = s-next; s-next = p;
C. q-next = s; s-next = p; D. p-next = s; s-next = q;
7.设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con (x, y) 返回x与y串的连接串，函数subs (s, i, j) 返回串s的从序号i的字符开始的j个字符组成的子串，函数len (s) 返回串s的长度，则con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) 的结果串是____。
A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF
8.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。
A. 2h B. 2h-1 C. 2h +1 D. h +1
9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是dgbaechf，则其后序遍历结点访问顺序是____。
A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca
10.具有6个顶点的无向图至少应有____条边才能确保是一个连通图。
A. 5 B. 6 C. 7 D. 8
11.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为–。
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
12.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(注：初始时为空)的一端的方法，称为____。
A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序
二、填空题(请在每小题的横线上填入正确内容，每空1分，共7分。)
1.在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点。
2.对n个元素的序列进行起泡排序时，最少的比较次数是 。
3.空串是 ，其长度等于0。
4.一棵有n个结点的满二叉树共有 个叶子结点。
5.在散列函数H(key)=key % p中，p应取 。
6.已知模式串t=‘abcaabbabc’， 其用KMP法求得的每个字符对应的next函数值为 。
三、简答题(本大题共3小题，每小题5分，共15分)
1.在对线性表的处理中一般使用两种存储结构，顺序存储结构和链式存储结构。试叙述在什么情况下使用顺序表比链表好？
2.简述什么是稳定的排序，什么是不稳定的排序。
3.下列中缀表达式对应的后缀形式是什么？
(1) (A + B) * D + E / (F + A * D) + C
(2) A B|| ! (E F) {注：按C的优先级)
四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)
1.数据元素不是数据的最小单位( )。
2.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。( )
3.AOE网是一种带权的无环连通图。( )
4.对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的( )。
5.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。( )
6.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。( )
7.折半插入排序是稳定的。( )
8.在散列法中，使用双散列函数可保证绝对不产生冲突。( )
9.消除递归不一定需要使用栈( )
10.堆排序是交换排序的一种。( )
五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）
1．阅读后分析下面程序段的功能是什么? （6分）
SeqStack S1, S2, tmp;
DataType x; //设栈tmp和S2已做过初始化
while ( ! StackEmpty (S1))
{ x=Pop(S1) ;
Push(tmp,x);
}
while ( ! StackEmpty (tmp) )
{ x=Pop(tmp);
Push( S2, x);
}
2.某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。（7分）
3.设散列表为HT[13], 散列函数为 H (key) = key %13。用线性探测再散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。（7分）
4.设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试写出使用希尔排序(增量为5,2,1)方法每趟排序后的结果。（6分）
六、算法设计题（本题共18分，第1小题10分，第2小题8分）
1.编写一个算法frequency，统计在一个输入字符串中所含各个不同字符出现的频度。用适当的测试数据来验证这个算法。(10分)
2.在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，并统计树中具有度为1的结点数目的算法。要求给出二叉链表的类型定义。(8分)
答案：
06－07第一学期
期末考试参考答案与评分标准
试卷代码：03266A 授课课时：112
课程名称：数据结构与算法 适用对象：本科
一、单项选择题(每小题2分，共24分。)
1. D 2. D 3. C 4. B 5. C 6. C
7. D 8. B 9. D 10. A 11. C 12. D
二、填空题(每空1分，共7分。)
1.父(或前驱)， 1
2. n-1
3. 不包含任何字符的串
4. (n+1)/2
5. 素数
6. 0111223123
三、简答题(每小题5分，共15分)
1.答：① 顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小(1)，存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
2.答：在排序序列中，任何两个相等的关键字Ki=Kj,如果在排序前的序列中Ki领先于Kj，若在排序后的序列中Ki仍领先于Kj，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中Kj领先于Ki，则称所用的排序方法是不稳定的。
3.答：各中缀表达式的后缀形式如下：
(1)AB+D*EFAD*+/+C+
(2)ABEF!||
四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)
1.T 2.F 3.T 4.F 5.F
6.F 7.T 8.F 9.T 10.F
五、分析应用题（1、4小题各6分，2、3小题各7分）
1．（6分）
答：程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。
2．（7分）
答：为方便起见，设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示：
赫夫曼编码为：概率为0.23的字符编码为：00
概率为0.11的字符编码为：010
概率为0.05的字符编码为：0110
概率为0.03的字符编码为：0111
概率为0.29的字符编码为：10
概率为0.14的字符编码为：110
概率为0.07的字符编码为：1110
概率为0.08的字符编码为：1111
3.（7分）
答：使用散列函数H(key)=key mod 13 有：
H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10
利用线性探查法造表：
0 1 2 3 4 5 6 7 8 9 10 11 12
78 15 03 57 45 20 31 23 36 12
1 1 1 1 1 1 4 1 2 1
搜索成功的平均搜索长度为：
ASL=1/10（1+1+1+1+1+1+4+1+2+1）=14/10
4.（6分）
答： 希尔排序(增量为5,2,1)
六、算法设计题（第1小题10分，第2小题8分）
1. (10分)
include iostream.h
include”string.h”
int charnumber=128;
void frequency(strings,int C[ ]){
for(int i=0;i charnumber;i++) C[i]=0;
for( i=0;i s.length();i++) C[atoi(s[i])]++;
for( i=0;i charnumber;i++)
if(C[i]0) cout”(”i”):\t”C[i]”\t”;
}
2. (8分)
类型定义（略）
int Level(BiTree bt) //层次遍历二叉树，并统计度为1的结点的个数
{
int num=0; //num统计度为1的结点的个数
if(bt){
QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉树结点指针为元素的队列
while(!QueueEmpty(Q))
{ p=QueueOut(Q); printf(p-data); //出队,访问结点
if(p-lchild !p-rchild ||!p-lchild p-rchild)
num++;//度为1的结点
if(p-lchild) QueueIn(Q,p-lchild); //非空左子女入队
if(p-rchild) QueueIn(Q,p-rchild); //非空右子女入队
}
}
return(num); //返回度为1的结点的个数
}
B：
06－07第一学期期末考试试卷
试卷代码：03266B 授课课时：112
课程名称：数据结构与算法 适用对象：本科
一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)
1.数据结构被形式地定义为 (K, R)，其中K是____的有限集，R是K上的关系有限集。
A.算法 B.数据元素 C.数据操作 D.逻辑结构
2.在数据结构中，从逻辑上可以把数据结构分成____。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.线性结构和非线性结构 D.内部结构和外部结构
3.以下的叙述中，正确的是____。
A.线性表的存储结构优于链式存储结构
B.二维数组是其数据元素为线性表的线性表
C.栈的操作方式是先进先出
D.队列的操作方式是先进后出
4.若一个栈的入栈序列是1、2、3、… 、n，其输出序列为p1、p2、p3、… 、pn，若p1=n，则pi为____。
A. i B. n = i C. n - i +1 D.不确定
5.判断一个循环队列QU (最多元素为m) 为空的条件是____。
A. QU-front == QU-rear B. QU-front != QU-rear
C. QU-front == (QU-rear+1)%m D. QU-front != (QU-rear+1)%m
6.在某单链表中，已知p所指结点不是最后结点，在p之后插入s所指结点，则执行____。
A. s-next = p; p-next=s; B. s-next = p-next; p-next = s;
C. s-next = p-next; p = s; D. p-next = s; s-next = p;
7.串是一种特殊的线性表，其特殊性体现在____。
A.可以顺序存储 B.数据元素是一个字符
C.可以链接存储 D.数据元素可以是多个字符
8.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，前序遍历序列是____。
A. acbed B. decab C. deabc D. cedba
9.对于一个满二叉树，m个树叶，n个结点，深度为h，则____。
A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2h -1
10.一个有n个顶点的无向图最多有____条边。
A. n B. n(n-1) C. n(n-1)/2 D. 2n
11.顺序查找法适合于存储结构为____的线性表。
A. 散列存储 B. 顺序存储或链接存储
C. 压缩存储 D. 索引存储
12.在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。
A. 插入排序 B.选择排序 C.快速排序 D. 归并排序
二、填空题(请在每小题的横线上填入正确内容，每空1分，共7分。)
1.在线性结构中，第一个结点 前驱结点，其余每个结点有且只有1个前驱结点。
2.在无权图G的邻接矩阵中，若A[i][j]等于1，则等于A[j][i] = 。
3.根据二叉树的定义，具有三个结点的二叉树有 种不同的形态。
4.空格串是指 ，其长度等于 。
5.在散列存储中，装填因子α的值越大，则存储元素时发生冲突的可能性就 。
6.已知模式串t= ‘abacabaaad’， 其用KMP法求得的每个字符对应的next函数值为 。
三、简答题(本大题共3小题，每小题5分，共15分)
1.比较静态查找与动态查找的主要区别，它们的基本运算有哪些不同？
2.逻辑结构分哪几种，存储结构有哪几种？
3.在具有n(n1)个结点的各棵不同形态树中，其中深度最小的那棵树的深度是多少？它共有多少叶子和非叶子结点？
四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)
1.每种数据结构都应具备三种基本运算：插入、删除、搜索( )。
2.满二叉树不一定是完全二叉树。( )
3.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( )
4.任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。( )
5.线性链表中所有结点的类型必须相同。( )
6.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关( )。
7.在散列法中解决冲突时，其装载因子的取值一定在(0，1)之间。( )
8.任何一个关键活动延迟，那么整个工程将会延迟。( )
9.平衡二叉树的左右子树深度之差的绝对值不超过1。( )
10.n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。( )
五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）
1.下述算法的功能是什么? （6分）
LinkList Demo(LinkList L)
{ // L 是无头结点单链表
ListNode *Q,*P;
if(LL-next){
Q=L;
L=L-next;
P=L;
while (P-next) P=P-next;
P-next=Q; Q-next=NULL;
}
return L;
}
2.将给定的图简化为最小的生成树，要求从顶点1出发。（7分）
3.设散列表为HT[13], 散列函数为 H (key) = key %13。用双散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个地址的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。（7分）
4.设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18},写出使用快速排序法每趟排序后的结果。（6分）
六、算法设计题（本题共18分，第1小题10分，第2小题8分）
1.试设计一个实现下述要求的查找运算函数Locate。设有一个带表头结点的双向链表L， 每个结点有4个数据成员：指向前驱结点的指针llink、指向后继结点的指针rlink，存放字符数据的成员data和访问频度freq。所有结点的freq 初始时都为0。每当在链表上进行一次Locate(L, x) 操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。(10分)
2.设一棵二叉树以二叉链表为存贮结构，设计一个算法将二叉树中所有结点的左，右子树相互交换。要求给出二叉链表的类型定义。(8分)
答案：
06－07第一学期
期末考试参考答案与评分标准
试卷代码：03266B 授课课时：112
课程名称：数据结构与算法 适用对象：本科
一、单项选择题(每小题2分，共24分。)
1. B 2. C 3. B 4. C 5. A 6. B
7. B 8. D 9. D 10.C 11. B 12. A
二、填空题(每空1分，共7分。)
1. 无
2. 1
3. 5
4. 串中字符全为空格 ， 空格的个数
5. 大
6. 0112123422 。
三、简答题(本大题共5小题，每小题5分，共15分)
1．答：两种查找方法最大的区别在于：
静态查找方法不修改查找表；动态查找在查找不成功时，将结点插入查找表中，即有可能修改查找表；
静态查找的基本运算有建表、查找和读表元；动态查找除上述基本操作外还有初始化、插入和删除操作；
2.答：根据数据元素之间关系的不同特性，通常有下列四类基本结构：(1)集合；(2)线性结构；(3)树形结构；(4)图状结构或网状结构。有两种不同的存储结构：顺序存储结构和链式存储结构。
3.答：深度最小的那棵树的深度为2。对于这n个结点，除了一个根结点之外，其余得n-1个结点均为叶子结点，故其深度为2。该树叶子结点数为n-1，非叶子结点数为1。
四、判断题(每小题1分，共10分)
1. (T) 2. (F) 3. (T) 4. (F) 5. (T)
6. (T) 7. (F) 8. (T) 9. (T ) 10.(T)
五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）
1.（6分）
答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
2.（7分）
答:
3.（7分）
答：使用散列函数H(key)=key mod 13 有：
H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10
利用双散列法造表：Hi =（Hi-1+RH(key)）%13, Hi =H(key)
0 1 2 3 4 5 6 7 8 9 10 11 12
78 15 03 57 45 20 31 36 23 12
1 1 1 1 1 1 3 5 1 1
搜索成功的平均搜索长度为：ASL =1/10（1+1+1+1+1+1+3+5+1+1）=16/10
4.（6分）
答：
六、算法设计题（第1小题10分，第2小题8分）
1.(10分)
答：
(1) 定义链表结构
struct DoubleListNode {
char data ;
int freq;
DoubleListNode * llink, *rlink ;
};
初始时，所有结点的freq域的值都为0。
(2) 定义函数
DoubleListNode * locate ( DoubleListNode *f ; char x ) {
DoubleListNode * p, *q;
p = f→rlink; /*跳过表头结点*/
while ( p != NULL p→data != x ) p = p→rlink; /*搜索*/
if ( p ) {
p→freq ++; q = p→llink;
p→rlink→llink = q; q→rlink = p→rlink; /*从链中摘下p*/
while ( q != f q→freq p→freq ) q =q→llink;
p→llink = q;
p→rlink = q→rlink; q→rlink→llink = p;
q→rlink = p; /*在q后面插入p*/
}
return p;
}
2． (8分)
答：类型定义（略）
void exchange(BiTree bt)//将二叉树bt所有结点的左右子树交换
{
if(bt)
{ BiTree s；
s=bt-lchild; bt-lchild=bt-rchild; bt-rchild=s; //左右子女交换
exchange(bt-lchild); //交换左子树上所有结点的左右子树
exchange(bt-rchild); //交换右子树上所有结点的左右子树
}
}
数据结构期末考试题难不难
难。
数据结构期末考试难程度解析及题型分析由考研信息网发布，主要内容:在计算机这一专业当中，考研是一项十分艰巨的任务。
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成。
数据结构（C#语言版）笔试试题与答案
《数据结构》期末考试试卷（ A ）
一、 选择题（每小题2分，共24分）
1．计算机识别、存储和加工处理的对象被统称为( A )
A.数据 B.数据元素
C.数据结构 D.数据类型
2．栈和队列都是（ A ）
A．限制存取位置的线性结构 B．顺序存储的线性结构
C．链式存储的线性结构 D．限制存取位置的非线性结构
3．链栈与顺序栈相比，比较明显的优点是( D )
A.插入操作更加方便 B.删除操作更加方便
C.不会出现下溢的情况 D.不会出现上溢的情况
4．采用两类不同存储结构的字符串可分别简称为( B )
A.主串和子串 B.顺序串和链串
C.目标串和模式串 D.变量串和常量串
5． 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：B
A. 110 B .108
C. 100 D. 120
6．串是一种特殊的线性表，其特殊性体现在：B
A.可以顺序存储 B .数据元素是一个字符
C. 可以链接存储 D. 数据元素可以是多个字符
7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为： C
A. 2h B .2h-1
C. 2h+1 D. h+1
软件开发网
8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？ A
A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D. 以上都不对
9．一个有n个顶点的无向图最多有多少边？C
A. n B .n(n-1)
C. n(n-1)/2 D. 2n
10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?C
A. 1/2 B .1
C. 2 D. 4
11．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ A ）
A．左子树的叶子结点 B．左子树的分支结点
C．右子树的叶子结点 D．右子树的分支结点
软件开发网
12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )
A.35和41 B.23和39
C.15和44 D.25和51
二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分）
原理见课本128页
三、有图如下，请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分)
深度优先；C0-C1-C3-C4-C5-C2
宽度优先：C0-C1-C2-C3-C4-C5
四、有图如下，按Kruskal算法求出其最小生成树。要求写出完整的步骤。（10分）
原理见课本250页
五、给定线性表（12，23，45，66，76，88，93，103，166），试写出在其上进行二分查找关键字值12，93，166的过程。并写出二分查找的算法。（20分）
0 1 2 3 4 5 6 7 8
12 23 45 66 76 88 93 103 166
过程：
mid=(0+8)/2=4
high=3,low=0 mid=1
high=0,low=0 mid=0（找到12）
high=8,low=5,mid=6（找到93）
high=8,low=7,mid=7
high=8 low=8 mid=8
算法：见课本84页上
六、知单链表的结点结构为
Data next
下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。
请在空缺处填入合适的内容，使其成为完整的算法。 (可用文字说明该算法的基本思想及执行的过程，10分)
void SelectSort(LinkedList L)
{
LinkedList p,q,min;
DataType rcd;
p= (1) ;
while(p!=NULL) {
min=p;
q=p-next;
while(q!=NULL){
if( (2) )min=q;
q=q-next;
}
if( (3) ){
rcd=p-data;
p-data=min-data;
min-data=rcd;
}
(4) ;
}
}
本题不会。嘿嘿。。。。
七、一个完整的算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分)
输入：
四个基本性质：1.输入：有零个或多个有外部提供的量作为算法的输入
2：输出：算法产生至少一个量作为输出
3.：确定性：组成算法的每条指令是清晰的，无歧异的。
4.：有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的
八、何谓队列的"假溢"现象？如何解决？（5分）
队列的假溢现象是指数组实现的顺序队列中，队尾指针已到达数组的下表上界产生上溢而队头指针之前还有若干 空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间的首尾相连。
九、说明并比较文件的各种物理结构。（6分）