本文目录导航：
谁有数据结构的期末试题，借我参考上任上考试了
A：06－07第一学期期末考试试卷试卷代码A授课课时：112课程称号：数据结构与算法 实用对象：本科 一、单项选用题(从下列各题四个备选答案当选出一个正确答案，并将其代号写在答题纸相应位置处。
答案错选或未选者，该题不得分。
每小题2分，共24分。
)1.数据结构被方式地定义为(K,R)，其中K是数据元素的有限集，R是K上的___有限集。
A.操作 B.映像C.存储D.相关2.线性表若驳回链式存储结构时，要求内存中可用存储单元的地址____。
A.必定延续的B.局部地址必定延续的C.必定是不续的D.延续不延续都可以3.一个栈的入栈序列是a、b、c、d、e，则栈的无法能输入序列是____。
4.一个队列的入队序列是1、2、3、4，则队列输入序列是____。
A.4、3、2、1B.1、2、3、4 C.1、4、3、2 D.3、2、4、15.栈和队列的独特点是____。
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. BCDEFEF8.设高度为h的二叉树上只要度为0和度为2的结点，则此类二叉树中所蕴含的结点数至少为____。
A. 2h B. 2h-1 C. 2h +1 D. h +19.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是dgbaechf，则其后序遍历结点访问顺序是____。
A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca10.具有6个顶点的无向图至少应有____条边能力确保是一个连通图。
A. 5 B. 6 C. 7 D. 811.驳回顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为–。
A. n B. n/2C. (n+1)/2 D. (n-1)/212.排序方法中，从未排序序列中筛选元素，并将其依次放入已排序序列(注：初始时为空)的一端的方法，称为____。
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.已知一棵二叉树的前序序列和后序序列可以惟一地结构出该二叉树。
( )网是一种带权的无环连通图。
( )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第一学期期末考试参考答案与评分规范试卷代码A授课课时：112课程称号：数据结构与算法 实用对象：本科 一、单项选用题(每小题2分，共24分。
)1. D2. D3. C4. B5. C 6. C7. D8. B9. D10. A 11. C12. D二、填空题(每空1分，共7分。
)1.父(或前驱)， 1 2. n-13. 不蕴含任何字符的串 4. (n+1)/2 5.素数 6. 三、简答题(每小题5分，共15分)1.答：① 顺序存储时，相邻数据元素的寄存地址也相邻(逻辑与物理一致)；要求内存中可用存储单元的地址必定是延续的。
好处：存储密度大，存储空间应用率高。
缺陷：拔出或删除元素时不繁难。
②链式存储时，相邻数据元素可轻易寄存，但所占存储空间分两局部，一局部寄存结点值，另一局部寄存示意结点间相关的指针好处：拔出或删除元素时很繁难，经常使用灵敏。
缺陷：存储密度小(<1)，存储空间应用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做拔出、删除这样的灵活操作。
若线性表的长度变动不大，且其重要操作是查找，则驳回顺序表；若线性表的长度变动较大，且其重要操作是拔出、删除操作，则驳回链表。
2.答：在排序序列中，任何两个相等的关键字Ki=Kj,假设在排序前的序列中Ki上游于Kj，若在排序后的序列中Ki仍上游于Kj，则称所用的排序方法是稳固的；反之，若或许使排序后的序列中Kj上游于Ki，则称所用的排序方法是不稳固的。
3.答：各中缀表白式的后缀方式如下： (1)AB+D*EFAD*+/+C+ (2)AB&&EF>!||四、判别题(本大题共10小题，命题正确的在题后括号内写 “T”，失误的在题后括号内写“F”，每小题1分，共10分)1.T2.F3.T4.F5.F6.F7.T8.F9.T10.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的字符编码为.（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应用线性探查法造表21搜查成功的平均搜查长度为：ASL=1/10（1+1+1+1+1+1+4+1+2+1）=14/104.（6分） 答： 希尔排序(增量为5,2,1)六、算法设计题（第1小题10分，第2小题8分）1. (10分)include <iostream.h>include”string.h”int charnumber=128;void frequency(string&s,int C[ ]){for(int i=0;i< charnumber;i++)C[i]=0;for( i=0;i< ();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第一学期期末考试试卷试卷代码B授课课时：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 = iC. n - i +1 D.不确定5.判别一个循环队列QU (最多元素为m) 为空的条件是____。
A. QU->front == QU->rearB. QU->front != QU->rearC. QU->front == (QU->rear+1)%mD. QU->front != (QU->rear+1)%m6.在某单链表中，已知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. cedba9.关于一个满二叉树，m个树叶，n个结点，深度为h，则____。
A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2h -110.一个有n个顶点的无向图最多有____条边。
A. n B. n(n-1) C. n(n-1)/2 D. 2n11.顺序查找法适宜于存储结构为____的线性表。
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(n>1)个结点的各棵不同外形树中，其中深度最小的那棵树的深度是多少？它共有多少叶子和非叶子结点？四、判别题(本大题共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(L&&L->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第一学期期末考试参考答案与评分规范试卷代码B授课课时：112课程称号：数据结构与算法 实用对象：本科 一、单项选用题(每小题2分，共24分。
)1. B2. C3. B4. C5. A6. B7. B8. D9. D10.C11. B12. A二、填空题(每空1分，共7分。
)1. 无2.1 3. 54. 串中字符全为空格，空格的个数5.大 6. 。
三、简答题(本大题共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)11搜查成功的平均搜查长度为：ASL =1/10（1+1+1+1+1+1+3+5+1+1）=16/104.（6分）答：六、算法设计题（第1小题10分，第2小题8分）1.(10分) 答：(1) 定义链表结构 struct DoubleListNode {chardata ;intfreq;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; while ( q != f &&q→freq < p→freq )q =q→llink;p→llink = q; p→rlink = q→rlink; q→rlink→llink = p;q→rlink = 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);//替换右子树上一切结点的左右子树} }
数据结构考试试题
一.判别题（）1.某线性表驳回顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。
正确。
第0个元素地址为100，则第i个元素地址为100+4*i，将12代入得148。
（）2.在任何一种线性链表上都无法启动随机访问。
失误。
比如只需知道顺序表首地址和每个数据元素所占存储单元的个数，就可以求出第i个数据元素的存储地址来，这也是顺序表具有按数据元素的序号随机存取的特点。
（）3.顺序栈是一种规则了元素进栈顺序的栈。
失误。
按存储结构来分，堆栈分为顺序栈和链栈，其中栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表，却并没有规则元素进栈顺序。
（）4.循环列表中每一个元素都有后继。
正确。
留意，这里或许有笔误，应写为“循环链表”而非“循环列表”。
（）5.删除一个二叉树中的一个结点，再从新拔出下来，必定能获取原来的二叉排序树。
失误。
二.填空题。
6.上方程序的期间复杂度为___________。
for(inti=1;i<=m;i++)for(intj=1;j<=n;j++)S+=i规律1：for循环：一个for循环的运转期间至少是该for循环内语句（蕴含测试）的运转期间乘以迭代的次数。
规律2：嵌套循环：从里向外剖析这些循环。
在一组嵌套循环外部的一条语句总的运转期间为该语句的运转期间乘以该组一切循环的大小的乘积。
关于此处嵌套的for循环，依据以上规律，期间复杂度为O(m*n)。
7.在长度为n的顺序表的第i（1≤i≤n+1）个位置上拔出一个元素，元素的移动次数是____________。
从第i个元素（原来的）到第n个元素，每个元素后移一位，一共须要n+1-i次。
8.在一个具有n个结点的有序单链表中拔出一个新结点，并让拔出后的单链表依然有序，则该操作的期间复杂性数量级为______。
找到节点位置，O(n)；单链表拔出操作，O(n)；总的期间复杂度为O(n+n)=O(n)。
9.若用s[1]～s[n]作为两个顺序栈的独特存储空间，左右两个栈的栈顶区分为t1和t2，则判别某个栈能否可以拔出新元素的条件是_________________。
当程序中同时经常使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向两边加长。
当一个栈里的元素较多，超越向量空间的一半时，只需另一个栈的元素不多，那么前者就可以占用后者的局部存储空间。
此处判别某个栈能否可以拔出新元素的条件是&t1!=&t210.设森林T中有三棵树，第一，二，三棵树的结点个数区分为n1,n2,n3,将森林转换成二叉树后，其根结点的左子树上有____________个结点。
将一个森林转换为二叉树的详细方法是：①将森林中的每棵树变为二叉树；②由于转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一同，就构成了一棵二叉树。
团体以为此处可以填3个答案，n1-1或许n2-1或许n3-1。
11.在带权值有向图的邻接矩阵中，第i行上非零元素的个数等于_______________。
当节点Vi与某节点Vj相邻接,则A(i,j)取非0值。
12.在各种查找方法中，平均查找长度与结点个数n有关的查找方法是_____________。
散列（Hash）查找。
数据结构试题 求答案
1： 线性结构
树结构
图结构
2 ：顺序存储结构：把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑相关由存储单元的邻接相关来表现。
链式存储结构：在计算机中用一组恣意的存储单元存储线性表的数据元素(这组存储单元可以是延续的,也可以是不延续的).每个结点是由数据域和指针域组成。
3：栈是一种不凡的线性表。
其不凡性在于限定仅在表尾启动拔出或删除操作。
队列，其不凡性在于限定拔出在线性表的一端启动，删除在线性表的另外一端启动。
以下是栈和队列的几个经典运行：
栈：“括号婚配”，“迷宫求解”，“进制转换”。
队列：“回文判别”，“排队取号”。
5：先序：12，8，6，2，10，20，16，15
中序：2，6，8，10，12，15，16，20
后序：2，6，10，8，15，16，20，12
注：最后一题最后一步E的右子树是F
