本文目录
数据结构高手进，帮忙答下题
一、1、B2、B3、 ?4、C 《 A的深度为1，B的深度为3，D的深度为3》5、C6、B?7、C8、B 直接插入排序 ：n个不同的数据元素，最多需要比较n*(n-1)/29、C10、A二、1.线性结构 ，非线性结构 。2. 352 《 100+ (6*20+6)*2 》 ， 232 《 100+ (6*10+6)*2》 。3. i能被2整除， i+1 4、log2(2n+1) ，2n-15、n-1 0 n*(n-1)/26、只在栈顶进行操作 插入删除受限。7、子表 数据元素三、1、对2、错 数组中的元素必须 类型相同3、错 4、错 拓扑序列不唯一5、用Ch1，Ch3表示两个字符，若Ord(Ch1)＜Ord(Ch3)，则称Ch1＜Ch3。（ ）四
谁有数据结构的期末试题，借我参考下马上考试了
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.abcde4.一个队列的入队序列是1、2、3、4，则队列输出序列是____。 A.4、3、2、1 B.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/2 C. (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.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。( )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, 散列函数为 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. C7. 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)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的字符编码为：11113.（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利用线性探查法造表：0123456789101112781503574520312336121111114121搜索成功的平均搜索长度为：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(string&s,int C){ for(int i=0;i《 charnumber;i++) C=0; for( i=0;i《 s.length();i++) C++; for( i=0;i《 charnumber;i++) if(C《《”\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)%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 = 。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, 散列函数为 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. C5. A6. B7. B 8. D9. D10.C11. 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) 0123456789101112781503574520313623121111113511搜索成功的平均搜索长度为：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); //交换右子树上所有结点的左右子树} }
哪里有数据结构期末考题
（三）简答题1．简述顺序存储结构和链式存储结构的特点答：顺序存储结构的优点无需为表示元素间的逻辑关系而增加额外的指针空间；可以随机存取表中的任一元素。缺点是必须事先进行空间分配，表的容量难以扩充；插入和删除操作时需移动大量结点，效率较低。链式存储结构的优点是结点的存储采用动态存储，表的容量很容易扩充；插入和删除操作方便，不必移动结点，只要修改结点中的指针即可。缺点是每个结点中需要有指针空间，比顺序存储结构的存储密度小；只能进行顺序查找结点。2．链表中为何要引入头结点？答：链表进行插入和删除操作时要判断是否在链表的首端操作，若在第一结点前插入新结点和删除第一个结点则会引起首指针head值的改变；否则head的值不会改变。在链表前加一个头结点（只用指针域指向链表的首结点）就避免了两种情况的判断，使程序设计简单了，程序的结构更清楚。2． 简述由二叉树的前序、中序和后序遍历序列确定二叉树答：在三种遍历序列中，前序序列和中序序列、中序序列和后序序列能唯一确定一棵二叉树，因为前序序列或后序序列能确定二叉树的根结点而中序序列能确定根的左、右子树。前序序列和后序序列不能唯一确定一棵二叉树，但注意树的先根序列和后根序列能唯一的确定该树，因为树的后根序列就是二叉树的中序序列。4．快速排序最坏情况的改进答：当待排序的序列为有序序列时快速排序的效率很低，蜕变为冒泡排序了，为了避免这种情况，选序列的首元素为枢轴元素（或称基准元素）改为选序列的首元素、中间元素和末元素三个元素中中间大的元素为基准元素（简单的就用中间元素为基准），这可大大改善快速排序的性能。例如：8，0，4，9，6，3，5，2，7，1以中间大元素6为基准，基准元素与最后元素交换后为：8，0，4，9，1，3，5，2，7，6↑ ↑i j将i,j指的内容比较，若i的内容比基准小，i推进，否则i停下，开始进行j的比较；若j的内容比基准大，j推进,，否则j停下，将i的内容与j的内容交换，重复上述过程，直至j《I《 SPAN》止，将基准与i的内容交换，一次分段完成。,如下所示：8，0，4，9，1，3，5，2，7，62，0，4，9，1，3，5，8，7，62，0，4，5，1，3，9，8，7，62，0，4，5，1，3，6，8，7，9 5．简述动态规划法的基本思想答：为了节约重复求相同子问题的时间，引入一个表（数组），不管它们是否对最终解有用，把新的子问题的解答存于该表中，待以后遇到同样子问题时，就不再重复求该子问题，而直接从表中取出该子问题的解答，这就是动态规划法所采用的基本思想。（四）选择题1．循环队列用数组A存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是 。A．(rear-front+m)% m B．read-front+1C．read-front-1 D．read-frontn 参考答案 A2．递归算法的执行过程一般来说，可分成 (1) 和 (2) 两个阶段。 (1)A．试探 B．递推 C．枚举 D．分析 (2)A．回溯 B．回归 C．返回 D．合成n 参考答案 (1) B (2) B3．设哈希表长m=11，哈希函数H（key）=key%11。表中已有4个结点：addr（15）=4， addr（38）=5，addr（61）=6，addr（84）=7，其余地址为空，如果二次探测再散列处理冲突，关键字为49的结点地址是 。 A．8 B．3 C．5 D．9n 参考答案 D4．m阶B-树中所有非终端（除根之外）节点中的关键字个数必须大于或等于 。 A． －1 B． +1 C． －1 D．mn 参考答案 C5．一组记录的关键码为（46，79，56，38，40，84），则采用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。 A．38，40，46，56，79，84 B．40，38，46，79，56，84 C．40，38，46，56，79，84 D．40，38，46，84，56，79n 参考答案 C6．若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用 (1) 算法，因为 (2) 。 （1）A．先递归后递推 B．先递推后递归 C．递归 D．递推 （2）A．递推的效率比递归高 B．递归宜于问题分解 C．递归的效率比递推高 D．递推宜于问题分解n 参考答案 （1）D （2）A7．将一棵有100节点的完全二叉树从上到下、从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为 。 A． 99 B．98 C．50 D．48n 参考答案 B8．二叉树在线索化后，仍不能有效求解的问题是 。 A．前序线索二叉树中求前序后继 B．中序线索二叉树中求中序后继 C．中序线索二叉树中求中序前趋 D．后序线索二叉树中求后序后继n 参考答案 D9．判断线索二叉树中某结点P有左孩子的条件是 （1） 。若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 （2） 。 （1）A．P！=null B．P-》lchild！=null C．P-》ltag=0 D．P-》ltag=1 （2）A．根结点无右子树的二叉树 B．根结点无左子树的二叉树 C．根结点可能有左子树和右子树 D．各结点只有一个孩子的二叉树n 参考答案 （1）C （2）C10．在一个单链表head中，若要在指针p所指结点后插入一个q指针所指结点，则执行_____。A． p-》next=q-》next; q-》next=p;B． q-》next=p-》next; p=q;C． p-》next=q-》next; p-》next=q;D． q-》next=p-》next; p-》next=q;n 参考答案 D11．设二维数组a的地址为________。A． loc(a) +(j×m+i) ×d C．loc(a) +((j-1)×m+i-1) ×dn 参考答案 B 12．如果一个栈的进栈序列是1,2,3,4且规定每个元素的进栈和退栈各一次,那么不可能得到的退栈序列_____。 A 4,3,2,1 B 4,2,1,3 C 1,3,2,4 D 3,4,2,1n 参考答案 B13．对n个元素进行快速排序时，最坏情况下的时间复杂度为 。A．O（log2n） B．O（n） C．O（nlog2n） D．O（n2）n 参考答案 D14．任何一个基于“比较”的内部排序的算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为 。 A．10 B．11 C ．21 D．36n 参考答案 A四、模拟试题1．二叉树的前序、中序和后序遍历法最适合采用 （1） 来实现。查找树中，由根结点到所有其它结点的路径长度的总和称为 （2） ，而使上述路径长度总和达到最小的树称为 （3） 。它一定是 （4） 。在关于树的几个叙述中，只有 （5） 是正确的。（1）A．递归程序 B．迭代程序 C．队列操作 D．栈操作（2）A．路径和 B．内部路径长度 C．总深度 D．深度和（3）A．B-树 B．B+树 C．丰满树 D．穿线树（4）A．B-树 B．平衡树 C．非平衡树 D．穿线树（5）A．用指针方式存储有n个结点的二叉树，至少要有n+1个指针B．m阶B-树中，每个非叶子结点的后件个数≥ C．m阶B-树中，具有k个后件的结点，必含有k-1个键值D．平衡树一定是丰满树n 参考答案（1）A （2）B （3）C （4）B （5）C2．一棵查找二叉树，其结点A、B、C、D、E、F依次存放在一个起始地址为n（假定地址以字节为单位顺序编号）的连续区域中，每个结点占4个字节：前二个字节存放结点值，后二个字节依次放左指针、右指针。若该查找二叉树的根结点为E，则它的一种可能的前序遍历为 （1） ，相应的层次遍历为 （2） 。在以上两种遍历情况下，结点C的左指针Lc的存放地址为 （3） ，Lc的内容为 （4） 。结点A的右指针Ra的内容为 （5） 。（1）A．EAFCBD B．EFACDB C．EABCFD D．EACBDF（2）A．EAFCBD B．EFACDB C．EABCFD D．EACBDF（3）A．n+9 B．n+10 C．n+12 D．n+13（4）A．n+4 B．n+8 C．n+12 D．n +16（5）A．n+4 B．n+8 C．n+12 D．n +16n 参考答案 （1）D （2）A （3）B （4）A （5）B3．对于给定的一组关键字（12，2，16，30，8，28，4，10，20，6，18），按照下列算法进行递增排序，写出每种算法第一趟排序后得到的结果：希尔排序（增量为5）得到 （1） ，快速排序（选第一个记录为基准元素）得到 （2） ，基数（基数为10）排序得到 （3） ，二路归并排序得到 （4） ，堆排序得到 （5） 。 （1）A．2,4,6,8,10,12,16,18,20,28,30 B．6,2,10,4,8,12,28,30,20,16,18 C．12,2,10,20,6,18,4,16,30,8,28 D．30,10,20,12,2,4,16,6,8,28,18 （2）A．10,6,18,8,4,2,12,20,16,30,28 B．6,2,10,4,8,12,28,30,20,16,18C．2,4,6,8,10,12,16,18,20,28,30 D．6,10,8,28,20,18,2,4,12,30,16 （3）A．10,6,18,8,4,2,12,20,16,30,28 B．1,12,10,20,6,18,4,16,30,8,28 C．2,4,6,8,10,12,16,18,20,28,30 D．30,10,20,12,2,4,16,6,8,28,18 （4）A．2,12,16,8,28,30,4,6,10,18,20 B．2,12,16,30,8,28,4,10,6,20,18 C．12,2,16,8,28,30,4,6,10,28,18 D．12,2,10,20,6,18,4,16,30,8,28 （5）A．30,28,20,12,18,16,4,10,2,6,8 B．20,30,28,12,18,4,16,10,2,8,6 C．2,6,4,10,8,28,16,30,20,12,18 D．2,4,10,6,12,28,16,20,8,30,18n 参考答案 （1）C （2）B （3）D （4）B （5）C4．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 （1） 。从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 （2） 。设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用 （3） 排序法。 （1）A．希尔排序 B．起泡排序 C．插入排序 D．选择排序 （2）A．希尔排序 B．起泡排序 C．插入排序 D．选择排序 （3）A．起泡排序 B．快速排序 C．堆排序 D．基数排序n 参考答案 （1）D （2）C （3）C 5．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时,元素序列的变化情况如下： ①25,84,21,47,15,27,68,35,20 ②20,15,21,25,47,27,68,35,84 ③15,20,21,25,35,27,47,68,84 ④15,20,21,25,27,35,47,68,84 则所采用的排序方法是 （1） 。下列（2）中不稳定的排序是 （2） 。外排序是指 （3） 。 （1）A．选择排序 B．希尔排序 C．归并排序 D．快速排序 （2）A．直接插入排序 B．冒泡排序 C．Shell排序 D．归并排序 （3）A．用机器指令直接对硬盘中需排序数据排序 B． 把需排序数据，用其它大容量机器排序 C． 把外存中需排序数据一次性调入内存，排好序后再存储外存D．对外存中大于内存允许空间的待排序的数据，通过多次内外间的交换实现排序。n 参考答案 (1) D (2) C （3）D6．在内部排序中，通常要对被排序数据进行多次扫描。各种排序方法有不同的排序实施过程和时间复杂性。对给定的整数数列（541,132,984,746,518,181,946,314,205,827）进行从小到大的排序时,采用冒泡排序和简单选择排序时,若先选出大元素,则第一次扫描结果分别是 （1） 采用快速排序（以中间元素518为基准）的第一次扫描结果是 （2） 。设被排序的序列有n个元素，冒泡排序和简单选择排序的时间复杂度是 （3） ；快速排序的时间复杂度是 （4） 。（1） A．(181,132,314,205,541,518,946,827,746,984）和（541,132,827,746,518,181,946,314,205,984） B．（132,541,746,518,181,946,314,205,827,984）和（541,132,827,746,518,181,946,314,205,984）C．（205,132,314,181,518,746,946,984,541,827）和（132,541,746,518,181,946,314,205,827,984）D．(541,132,984,746,827,181,946,314,205,518）和（132,541,746,518,181,946,314,205,827,984）（2）A．（181,132,314,205,541,518,946,827,746,984）B．（541,132,827,746,518,181,946,314,205,984）C．（205,132,314,181,518,746,946,984,541,827）D．(541,132,984,746,827,181,946,314,205,518）（3）A．O(nlog2n) B．O(n) C．log2n D．O(n2)（4）A．O(nlog2n) B．O(n2log2n) C．O(log2n) D．O(n2)n 参考答案 （1）B （2）C （3）D （4）A7．结定结点的关键字序列（F、B、J、G、E、A、I、D、C、H），对它按字母的字典顺序进行排列，采用不同方法，其最终结果相同。但中间结果是不同的。Shell排序的第一趟扫描（步长为5）结果应为 （1） 。冒泡排序（大数下沉）的第一趟冒泡的效果是 （2） 。快速排序的第一次扫描结果是 （3） 二路归并排序的第一趟结局是 （4） 。若以层次序列来建立对应的完全二叉树后，采用筛选法建堆，其第一趟建的堆是 （5） 。（1）A．（B、F、G、J、A、D、I、E、H、C）B．（B、F、G、J、A、E、D、I、C、H）C．（A、B、D、C、E、F、I、J、G、H）D．（C、B、D、A、E、F、I、G、J、H）（2）A．（A、B、D、C、F、E、I、J、H、G）B．（A、B、D、C、E、F、I、H、G、J）C．（B、F、G、E、A、I、D、C、H、J）D．（B、F、G、J、A、E、D、I、C、H）（3）A．（C、B、D、A、F、E、I、J、G、H）B．（C、B、D、A、E、F、I、G、J、H）C．（B、A、D、E、F、G、I、J、H、C）D．（B、C、D、A、E、F、I、J、G、H）（4）A．（B、F、G、J、A、E、D、I、C、H）B．（B、A、D、E、F、G、I、J、H、C）C．（A、B、D、C、E、F、I、J、G、H）D．（A、B、D、C、F、E、J、I、H、G）（5） n 参考答案 （1）C （2）C （3）B （4）A （5）B8．二叉树 （1） 。在完全二叉树中，若一个结点没有 （2） ，则它必定是叶结点。每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子树是N在原树里对应结点的 （3） ，而N的右子树是它在原树里对应结点的 （4） 。二叉排序树的平均检索长度为 （5） 。（1）A．是特殊的树 B．不是树的特殊形式 C．是两棵树的总称 D．是只有二个根结点的树形结构（2）A．左子树 B．右子树 C．左子树或没有右子树 D．兄弟（3）～(4)A．最左子树 B．最右子树 C．最邻近的右兄弟 D．最邻近的左兄弟（5）A．O(n2) B．O(n) C．O(log2n) D．O(nlog2n)n 参考答案 （1）B （2）A （3）A （4）C （5）C9．哈希存储的基本思想是根据 （1） 来决定 （2） ，冲突（碰撞）指的是 （3） ， __(4)___越大，发生冲突的可能性也越大。处理冲突的两种主要方法是 （5） 。（1）～（2）A．存储地址 B．元素的序号 C．元素个数 D．关键码值（3） A．两个元素具有相同序号 B．两个元素的关键码值不同，而非码属性相同C．不同关键码值对应到相同的存储地址 D．数据元素过多（4） A．非码属性 B．平均检索长度 C．负载因子 D．哈希表空间（5） A．线性探查法和双散列函数法 B．建溢出区法和不建溢出区法C．除余法和折叠法 D．拉链法和开放地址法n 参考答案 （1）D （2）A （3）C （4）C （5）D10． 设二维数组F的行下标为1至5，列下标为0至8，F的每个数据元素均占4个字节。在按行存储的情况下，已知数据元素F的第一个字节的地址分别为 （1） 和 （2） ，而数组的第一个数据元素的第一个字节和数组最后一个元素的最后一个字节的地址分别为 （3） 和 （4） 。对一般的二维数组G而言，当 （5） 时，其按行存储的G的地址相同。（1）A．1088 B． 1084 C．1092 D．1120（2）A．1092 B． 1088 C．1120 D．1124（3）A．1004 B． 1044 C．1000 D．984 （4）A．1183 B． 1179 C．1164 D．1187（5）A．G的列数与行数相同B．G的列的上界与G的行的上界相同C．G的列的上界与G的行的下界相同D．G的列的上下界与G的行的上下界相同n 参考答案 （1）A （2）C （3）C （4）B （5）D11．某顺序存储的表格，其中有90,000个元素，已按关键字递增有序排列，现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字皆不相同。用顺序查找法查找时，平均比较次数约为 (1) ，最大比较次数为 (2) 。现把90,000个元素按排列顺序划分成若干组，使每组有g个元素（最后一组可能不足g个）。查找时，先从第一组开始，通过比较各组的最后一个元素的关键字，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的平均比较次数最小的g是 (3) ，此时的平均比较次数是 (4) 。当g的值大于等于90,000时，此方法的查找速度接近于 (5) 。(1)～(2) A. 25,000 B. 30,000 C. 45,000 D. 90,000(3)～(4) A. 100 B. 200 C. 300 D. 400(5) A. 快速分类法 B. 斐波那契查找法 C. 二分法 D. 顺序查找法n 参考答案 （1）C （2）D （3）C （4）C （5）D12．已知无向图的邻接表如图2-35所示：此邻接表对应的无向图为 (1) 。此图从F开始的深度优先遍历为 （2） 。从F开始的广度优先遍历为 （3） 。从F开始的深度优先生成树为 （4） 。从F开始的广度优先生成树为 （5） 。（1）（2）A. F G I L J M K H B. F G I L J K H M C. F G I L J K M H D. F G H M I L J K（3）A. F G I L J K M H B. F G H M I L J K C. F G H I L J K M D. F G H M K I L J（4） （5）n 参考答案 （1）C （2）B （3）B （4）A （5）B13．图2-36是带权的有向图G的邻接表。以结点V1出发深度遍历图G所得的结点序列为 （1） ；广度遍历图G所得的结点序列为 （2） ；G的一种拓扑序列是 （3） ；从结点V1到V8结点的最短路径是 （4） ；从结点V1到V8结点的关键路径是 （5） 。 （1）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V3，V8，V4，V5，V6，V7 C. V1，V2，V3，V8，V4，V5，V7，V6 D. V1，V2，V3，V8，V5，V7，V4，V6（2）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V4，V6，V5，V3，V7，V8 C. V1，V2，V4，V6，V3，V5，V7，V8 D. V1，V2，V4，V6，V7，V3，V5，V8（3）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V4，V6，V5，V3，V7，V8 C. V1，V2，V4，V6，V3，V5，V7，V8 D. V1，V2，V4，V6，V7，V3，V5，V8(4)～(5)A.( V1，V2，V4，V5，V3，V8) B. (V1，V6，V5，V3，V8) C.( V1，V6，V7，V8) D. ( V1，V2，V5，V7，V8)n 参考答案 （1）D （2）C （3）B （4）D （5）B
求数据结构期末测试题一套
一、单选题 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的最后一个数据元素的起始地址为＿＿。 ***隐藏网址***
