当前位置：文档之家 › 数据结构_期中试卷(含答案)

数据结构_期中试卷(含答案)

  • 格式：doc
  • 大小：191.00 KB
  • 文档页数：7

一、选择题（每小题 1分，共10分）1、队列是插入和删除受限的线性表，其删除操作是在线性表的（1）进行。

A．表头B．表尾C．任意位置D．指定位置2、下述哪一条是顺序存储结构的优点？（2）。

A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示3、设有一个栈，元素的进栈次序为A, B, C, D, E，下列哪个是不可能的出栈序列（3）。

A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A4、若二叉树的根结点所在的层次为第1层，则该二叉树的第k层上至多有（4）个结点。

2k B．2k C．2k-1 D．2k+1A. 15、设单链表中指针p指向结点m，若要删除m的后继结点（假设该后继结点存在），则需修改指针的操作为（5）。

A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;6、下面程序段的时间复杂度为（6）。

for(int i=0; i<m; i++)for(int j=0; j<n; j++) a[i][j] = i*j;A．O(m2) B．O(n2) C．O(m+n) D．O(m*n)7、非空的循环单链表head的尾结点指针p满足（7）。

A．p==NULL B．p== head C．p->next==head D．p->next==NULL8、已知二维数组A[0..9,0..9]中，元素a[2][0]的地址为560，每个元素占4个字节，则元素a[1][0]的地址为（8）。

A. 518B. 520C. 522D. 5249、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（9）。

A．rear％n= = front B．（front+l）％n= = rearC．rear％n -1= = front D．(rear+l)％n= = front10、假设在一棵二叉树中，度为2的结点数为15，度为1的结点数为10个，则该二叉树的分支总数为（10）个。

A. 41B. 40C. 30D. 25二、填空题（每空2分，共20分）1. 一棵深度为k的完全二叉树（假定根结点所在的层次为第1层），则其结点总数的最小值为（1），最大值为（2）。

2．对于一个具有n个结点的单链表（n≥1），在指针变量p指向的结点后插入一个新结点的时间复杂度为（3），在给定值为x的结点后插入一个新结点的时间复杂度为（4）。

3. 设有一空栈，现有输入序列A，B，C，D，E，经过push, push, pop, push, pop, push, push后，此时的输出序列为（5）。

4. 有一个100*90整型数据的稀疏矩阵，非0元素有10个，设每个整型数据占2字节，则用三元组表示该矩阵时，所需的字节数是（6）。

5. 设栈S和队列Q初始为空。

6个元素依a,b,c,d,e,f的顺序通过栈S，一个元素出栈后立即进入队列Q。

若这6个元素出队的序列为d,c,b,f,e,a，则栈S 的最小容量需（7）。

6. 若对n阶对称矩阵A[0..n-1,0..n-1]以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定a ij（i≤j）的位置k的关系为（8）。

7. 表达式a+((b*c-d)/e+f*g/h)+x/y对应的后缀表达式是（9）。

8. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S="Beijing＆Nanjing"，T="jing"，INDEX（S，T）= （10）。

三、判断题（每小题2分，共10分，错误打×，正确打√）1．二叉树结构中，任何一个结点都有一个且仅有一个直接前驱和直接后继。

............ ( ) 2．在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，对它分别进行中序遍历和后序遍历，则具有相同的结果。

............. ( )3. 对线性链表来说，从任意结点开始均能扫描表中全部结点。

............. ( )4. 线性表的特点是每个元素都有一个前驱和一个后继。

............. ( )5. 栈和队列都是限制存取点的线性结构。

............. ( )四、简答题(本大题有5小题，共 40 分，每小题分值见各题标注)1．（6分）已知一棵二叉树如下，请分别写出按前序、中序、后序遍历时得到的字符序列。

AB CD E FG H IJ2．（6分）设x，n为整型变量，且n>0，下面程序片段中语句x /= 2执行次数的数量级是多少？试进行分析。

用“O”记号表示。

x = n*n;while (x>=1)x /= 2;3．（8分）用栈实现将中缀表达式：8*(3+5)+5/3# 转换成后缀表达式，画出栈的变化过程图（符号“#”为表达式结束符）。

4．（10分）已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和DECBHGFA，请画出这棵二叉树，并写出对其先序遍历的序列。

5. （10分）线性表有两种常用存储结构：一是顺序表，二是线性链表。

试问：（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动的改变。

在此情况下，应选用哪种存储结构？为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，那么应采取哪种存储结构？为什么？五、算法题(本大题有2小题，每题10分，共 20 分)1. 以下算法利用栈的基本操作将一个十进制正整数转换成二进制正整数，填空完善之。

void conversion( ){InitStack(S);scanf("%d",&x);while (x!=0){push(S, （1）);x=x/2;}while( !StackEmpty(S) ){ （2）;printf("%d",x);}}注：栈的基本操作如下：InitStack(s)：初始化一个栈；Push(s,x)：元素x进栈；Pop(s,x)：栈顶元素出栈；GetTop(s,x)：读出栈顶元素；StackEmpty(s)：判栈是否为空。

2. 编写二叉树（以二叉链表存储）先序遍历的递归算法。

答案一、选择题(每小题 1分，共10分)1—5. A A C A A6.—10. D C B D B二、填空题（每空2分，共20分）1. 【1】2k-1 +1【2】2k-12. 【3】 O(1) 【4】O(n)3. 【5】 B C4. 【6】 605. 【7】 46. 【8】7. 【9】8. 【10】 4三、判断题（每小题2分，共10分，错误打×，正确打√）1．×2．√3．×4．×5．√四、简答题(本大题有5小题，共 40 分，每小题分值见各题标注)1．（6分）解：前序遍历：A，B，D，E ，G，H ，J，C，F,I ................. (2分) 中序遍历：D，B，G，E，J，H，A，C，I，F ................. (2分)后序遍历：D，G，J，H，E，B，I，F，C，A ................. (2分)2．（6分）解：根据题意，可知：第1次循环时， 21*2x n =； ................. (1分) 第2次循环时， 221*2x n =； 第3次循环时， 231*2x n =； 由此可作如下假设： 当x = 1或接近1时， 已经循环了k 次，则必有：21*12k x n ==， ................. (2分) =〉22k n ==〉22log n k ==〉22log n k =;所以，x/=2执行次数的数量级是2(log )n O ................. (3分)3．（8分）解：后缀式为：835+*53/+，(3分) ； 栈的结构变化如下图所示（每图1分）：(1)(2)(3)(4)(5)4．（10分）解：该二叉树如下：先序遍历：A B C D E F G H ................. 5分................. 5分5（10分）解：（1）在此情况下，应该选择线性链表的存储结构，应为各表的长度经常动态变化，意味着此表经常进行插入和删除的操作，而对于链表来说，插入一个元素或删除一个元素的算法复杂度为O(1)，比顺序存储结构的算法复杂度要小很多。

................. 5分（2）由于顺序存储结构对数据的存取方式是随机存取的，算法复杂度为O(1)；而链表对数据的存取方式是顺序存取的，算法复杂度为O(n)，所以应该选择顺序存储结构。

........... 5分五、算法题(本大题有2小题，每题10分，共 20 分)1．解：（1）x%2 ................. 5分(2) Pop( S, x ) ................. 5分2．解：先序遍历递归算法如下：Status PreOrderTraverse( BiTree T , Status( *Visit )( TelemType e ) ){ ................. 2分If( T ){ .................2分If( Visit( T-> data ) ) ................. 2分If( PreOrderTraverse( T->lchild, Visit ) ) ................. 2分If( PreOrderTraverse( T->rchild, Visit ) ) ................. 2分return OK;Return ERROR;}Else return OK;}。

合集下载

数据结构期中试题及参考答案

数据结构期中试题及参考答案


}LNode, *LinkList;
阅读算法 f31，并回答问题；
（1）设节点结构为id score next
,成绩链表 A 和 B 如图所示，画
出执行算法 f31(A,B)后节点 A 所指的链表；
A
1 70
2 40
3 90
4 48
5 56
B
2 38
4 65
题 31 图
（2）减速算法 f31 的功能。 Void f31(LinkList A, LinkList B) { LinkList p,q; p = A->next; q = B->next; while (p && q) { if(p->id < q->id) p = p ->next; else if(p->if > q-> id) q =q –>next; else { if (p->score < 60)
I + = j + lt ;
}
}while (i+lt <= ls && j>=0);
Return k;
}
４
五、算法设计题（本题 14 分） 34.假设线性表采用顺序存储结构，其类型定义如下：
#define ListSize 100 typedef struct{
int data[ListSize]; int length; }SeqList, *Table; 编写算法，将顺序表 L 中所有值为奇数的元素调整到表的前端。
（1）设 n=10，元素
p=8
２
存储在 sa[p]，写出下标 p 的值；
题 3-1 图
数据结构期中测试题答案

数据结构期中测试题答案

《数据结构》期中测试
班级：
姓名：
学号：
对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行高中资料试卷调整试验；通电检查所有设备高中资料电试力卷保相护互装作置用调与试相技互术关，系电，力通根1保据过护生管高产线中工敷资艺设料高技试中术卷0资配不料置仅试技可卷术以要是解求指决，机吊对组顶电在层气进配设行置备继不进电规行保范空护高载高中与中资带资料负料试荷试卷下卷问高总题中2体2资配，料置而试时且卷，可调需保控要障试在各验最类；大管对限路设度习备内题进来到行确位调保。整机在使组管其高路在中敷正资设常料过工试程况1卷下中安与，全过要，度加并工强且作看尽下护可1都能关可地于以缩管正小路常故高工障中作高资；中料对资试于料卷继试连电卷接保破管护坏口进范处行围理整，高核或中对者资定对料值某试，些卷审异弯核常扁与高度校中固对资定图料盒纸试位，卷置编.工写保况复护进杂层行设防自备腐动与跨处装接理置地，高线尤中弯其资曲要料半避试径免卷标错调高误试等高方，中案要资，求料编技试5写术卷、重交保电要底护气设。装设备管置备4高线动调、中敷作试电资设，高气料技并中课3试术且资件、卷中拒料中管试包绝试调路验含动卷试敷方线作技设案槽，术技以、来术及管避系架免统等不启多必动项要方高案式中；，资对为料整解试套决卷启高突动中然过语停程文机中电。高气因中课此资件，料中电试管力卷壁高电薄中气、资设接料备口试进不卷行严保调等护试问装工题置作，调并合试且理技进利术行用，过管要关线求运敷电行设力高技保中术护资。装料线置试缆做卷敷到技设准术原确指则灵导：活。在。对分对于线于调盒差试处动过，保程当护中不装高同置中电高资压中料回资试路料卷交试技叉卷术时调问，试题应技，采术作用是为金指调属发试隔电人板机员进一，行变需隔压要开器在处组事理在前；发掌同生握一内图线部纸槽故资内障料，时、强，设电需备回要制路进造须行厂同外家时部出切电具断源高习高中题中资电资料源料试，试卷线卷试缆切验敷除报设从告完而与毕采相，用关要高技进中术行资资检料料查试，和卷并检主且测要了处保解理护现。装场置设。备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况，然后根据规范与规程规定，制定设备调试高中资料试卷方案。
数据结构试题集(8套卷子+答案)

数据结构试题集(8套卷子+答案)

《数据结构》试卷一一、填空题：（共２０分）1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。

2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。

3、在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。

4、二叉树的前序遍历序列等同于该二叉树所对应森林的遍历序列5、对一棵二叉排序树，若以遍历该树，将得到一个以关键字递增顺序排列的有序序列。

6、三个结点a,b,c组成二叉树，共有种不同的结构。

7、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用型平衡旋转。

8、图的遍历有两种,它们是。

9、堆排序的时间复杂度为。

10、在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。

二、单项选择题（共２０分）１、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（）（A）２，４，１，３（B）３，１，４，２（C）３，４，１，２（D）１，２，３，４２、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？（）（A）２i（B）２1-i（C）２1+i（D） i３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（）（A）１０（B）１１０（C）１１１０（D）１１１１４、下面关于数据结构的叙述中，正确的叙述是（）（A）顺序存储方式的优点是存储密度大，且插、删除运算效率高（B）链表中每个结点都恰好包含一个指针（C）包含n个结点的二叉排序树的最大检索长度为logn2（D）将一棵树转为二叉树后，根结点无右子树５、程序段：y:＝0while n>=(y+1)*(y+1) doy:=y+1enddo的时间复杂度为（）（A）O(n) （B）O(n2) （C）O(n2/1) （D）O(1)6、排序方法中,关键码比较的次数与记录的初始排列无关的是( )(A) shell排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序7、数组q[0..n-1]作为一个环行队列,f 为当前队头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数总小于n,则队列中元素个数为( )(A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n8、为了有效的利用散列查找技术,需要解决的问题是:( )Ⅰ:找一个好的散列函数Ⅱ:设计有效的解决冲突的方法Ⅲ:用整数表示关键码值(A) Ⅰ和Ⅲ (B) Ⅰ和Ⅱ (C) Ⅱ和Ⅲ (D) Ⅰ,Ⅱ和Ⅲ9、引入线索二叉树的目的是（）(A) 加快查找结点的前驱或后继的速度(B) 为了能在二叉树中方便的进行插入与删除(C) :为了能方便的找到双亲(D) 使二叉树的遍历结果唯一10、用二分（折半）查找表的元素的速度比用顺序法（）(A) 必然快(B) 必然慢(C): 相等(D): 不能确定三、简答题：（共40分）１、已知某二叉树按中序遍历序列为BFDAEGC，按前序遍历序列为ABDFCEG,试画出该二叉树形状，并写出它的后序遍历序列。

数据结构期中试卷答案（信计11）

数据结构期中试卷答案（信计11）

数据结构期中试卷答案（信计11）嘉兴学院试卷2012 —2013学年第2学期期中考试试卷课程名称：数据结构使⽤班级：信计11级考试形式：闭卷在题⼲的括号内。

每个选择1分，共10分)1．抽象数据类型可⽤三元组（D，R，P）表⽰，其中R是 D 的有限集。

A．算法B．数据元素C．数据操作D．数据关系2．数据结构的研究包含三个⽅⾯的内容，它们分别是数据的 B 、数据的存储结构和数据运算。

A．数据元素B．逻辑结构C．存储结构D．计算⽅法3．线性结构的顺序存储结构是⼀种随机存取的存储结构，⽽链式存储结构是⼀种 A 的存储结构。

A．顺序存取 B．随机存取 C．索引存取 D．散列存取4．线性表L在 B 情况下，最适合使⽤链接结构实现算法。

A．不需经常对L进⾏修改 B．需经常对L进⾏删除和插⼊C．需经常修改L中结点值 D．L中结点结构复杂5．⼀个队列的⼊列序列是a，b，c，d，则队列的输出序列是 A 。

A．a，b，c，d B．a，d，c，b C．c，b，d，a D．d，c，b，a6．循环队列Q中的数据元素值存放在长度为m的数组中，且此数组最多只能存放m-1个数据元素。

已知头尾指针分别是Q．front和Q．rear, 则判断Q为满队列的条件是 B 。

A．Q．front= =Q．rear B．Q．front= =(Q．rear+1) %mC．Q．front!=Q．rear D．Q．front!= (Q．rear+1) %m7．⼀个栈的⼊栈序列是a, b, c, d, e, 则栈的不可能的输出序列是D 。

A．abcde B．decba C．edcba D．dceab8．判定⼀个顺序栈S（最多存放元素个数是m）为空栈的条件是 C 。

(顺序栈类型定义为：typedef struct {Selemtype *base;Selemtype *top;Int stacksize; } Sqstack；) A．S．top= =0 B．S．top= =m C．S．top= = S．base D．S．base= =0 9．从数据结构来看，串是⼀种特殊的线性表，其特殊性体现中 B 。